Учебники Онлайн


Динамическое программирование

Понятие и область применения

Динамическое программирование - метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разделен на отдельные этапы (шаги). В основе метода лежит принцип оптимальности, сформулирован ульований. РБеллманом. Оптимальное управление характеризуется такими свойствами, что независимо от исходного состояния на любом шаге управления и последующее управление должно избираться оптимальным относительно состояния, к которому придет система в конце этого шагоку.

Метод, построенный на использовании принципа оптимальности, позволяет установить соотношение между экстремальными значениями целевой функции в задачах, характеризующихся различной продолжительности процесса и разными начальными состояниями. При этом необходимо учитывать последствия реализации найденного оптимального решения и для последующих решений. Такой подход обусловлен разработкой оптимальной стратегии. Процесс принятия решения в этом случае является многошаговойвим.

При этом, если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейные, то в задачах динамического программирования эти зависимости могут иметь и нелинейный и характе.

Динамическое программирование применяется в основном для решения задач двух классов: планирование деятельности экономической системы (предприятий) с учетом изменения изготавливаемой во времени отв в соответствии с изменения потребности; перераспределения ресурсов по различным направлениям во время.

Наиболее целесообразно динамическое программирование применить для решения таких практических задач, в которых поиск оптимального решения требует поэтапного подхода: например, определение времени замены оборудования я с учетом затрат на эксплуатацию оборудования, на приобретение нового, первоначальной стоимости данного оборудования, стоимости полученной на нем продукции.

Концептуальный подход

Построение модели динамического программирования сводится к следующим основным моментам:

1) выбирают способ деления процесса на шаги:

3) записывают уравнения состояния:

4) вводят показатели эффективности на к-м шаге

и суммарной - целевую функцию:

5) вводят для рассмотрения условные максимумы

показателя эффективности от к-го шага (включительно) до конца процесса и условные оптимальные управления на к-м шаге

6) с учетом ограничений задачи определяют для каждого шага множество. ПК допустимых управлений на этом шаге;

7) записывают основные для расчетов функциональные уравнения. Беллмана:

Несмотря на однообразие в общем построении модели динамического программирования, что приведенная выше, схема расчетов видоизменяется в зависимости от размерности задачи, характера модели (дискретная или не еперервна), вида функций и других характеристик модел.

Общие характеристики

Каким же условиям должна отвечать задача оптимизации, чтобы ее можно было описать моделью динамического программирования. Эти условия следующие:

1. Задача может интерпретироваться как n-шаговый процесс управления, а показатель эффективности процесса может быть представлен в аддитивной форме, то есть как сумма показателей эффективности на каждом шагу

2. Структура задачи инвариантна относительно числа шагов п, т.е. должна быть определена для любого п и не зависеть от этого числа

3. На каждом шагу состояние системы определяется конечным числом бы параметров состояния и управляется конечным числом г переменных управления, причем г и в не зависят от количества шагов п

4. Выбор управления на. К-м шаге не влияет на предыдущие шаги, а состояние в начале этого шага является функцией только предшествующего состояния и выбранного нем управления (условие отсутствия последействия)

Отметим также, что выполнение указанных условий иногда очевидно, а иногда достигается после соответствующих преобразований

Пример применения

Автомашина эксплуатируется в течение 6 лет. В начале каждого года может быть принято решение о замене машины новой. Стоимость новой машины на к-м году эксплуатации составляет я ^ = 5ооо 5ОО (гривен. После г лет эксплуатации машины на к-ом году ее можно продать за р (и) 2 - / гривен. Стоимость содержания машины в течение k-го года составляет ^ (Оь0'1 / ^ '* 1) гривен. Найти оптимальный способ : когда нужно заменить машину новой, чтобы суммарные расходы (с учетом расходов на закупку новой машины в начале срока эксплуатации и компенсация за счет окончательной продажи) были минимальными имиальними;

Рк - начальная стоимость машины, если она приобретена в начале k-го года;

гк (и) - затраты на эксплуатацию в течение к-го года, если со времени последней замены прошло и лет;

* 0) ~ ~ ликвидационная стоимость оборудования возрасте / лет, если оно продается в начале k-го года

Процесс эксплуатации машины является б-шаговым. Состояние% к_х системы в начале k-го шага характеризуется одним параметром - / - возрастом машины. Управление на каждом шагу заключается в выборе одного из двух решений: цс - эксплуатировать старую машину;. Ц3 - продать старую машину, купить новую (заменить). Уравнение состояния для этого процесса имеет видяд:

Показатель эффективности в этой задаче-суммарные затраты на эксплуатацию оборудования. Расходы на к-м шаге зависят от выбранного управления. При управлении щ = ис эти расходы равны: 2кс =. ГДП, а при уп правлении ик == и3 составляют: Z ^ 3 =-фк. Ри 7"Д0uot;Д0).

Пусть. Хк и) условные минимальные затраты зап - к шагов по к-го по п-й включительно, если на начало к-го шага возраст машины составляет и лет, при условии, что был выбран оптимальный режим эксплуатации

Рекуррентные соотношения для. Хк (/) имеют в нашем примере вид:

Для 6-го шага соответственно получим:

Запишем последнее уравнение, учитывая заданные в условиях функции р. Условная оптимизация на 6-м шаге сводится к оптимизации по уравнению: