Постановка задачі динамічного програмування

ТЕМА 8. ДИНАМІЧЕ ПРОГРАМУВАННЯ

8.1 Постановка задачі динамічного програмування.

8.2 Методи розв’язування задач динамічного програмування.

8.3 Прикладні моделі динамічного програмування.

Динамічне програмування - це математичний апарат, який дозволяє швидко знаходити оптимальне рішення у випадку, коли ситуація, що вивчається, має велику кількість варіантів поведінки, які дають різні результати і серед них треба вибрати найкращий. Динамічне програмування використовують при розв’язуванні певного типу задач шляхом їх розкладу на менші та простіші підзадачі. Розв’язок такого виду задачі можна знайти шляхом перебору всіх можливих варіантів і вибору серед них найкращого, але в більшості випадків такий перебір є досить трудомістким. Тому процес прийняття оптимального рішення розбивається на етапи (кроки) і досліджується з допомогою методу динамічного програмування.

Динамічне програмування використовується для розв’язання таких задач: розподіл дефіцитних капітальних вкладень між новими напрямками їх використання; розробка сценаріїв управління попитом чи запасами; розробка принципів календарного планування виробництва і вирівнювання зайнятості в умовах нестабільного попиту на продукцію; складання календарних планів поточного та капітального ремонту устаткування та його заміни; формування послідовності розвитку комерційної операції тощо.

Розглянемо деякий керований процес. Припустимо, що керування можна розбити на п кроків, тобто рішення приймається послідовно на кожному кроці, а процедура, яка переводить систему з початкового стану в кінцевий, є сукупністю п покрокових керувань. В результаті керування система переходить із стану в .

Позначимо через керування на k- мукроці (), де - множина допустимих керувань на k- мукроці. Нехай - керування, яке переводить систему з стану в . Позначимо через стан системи після k- гокроку керування. Отримуємо послідовність станів , , , …, , , , …, .

Показник ефективності процесу керування залежить від початкового стану системи і керованої змінної:

(8.1)

Власне, задача динамічного програмування формулюється таким чином: знайти таке значення керованої змінної ,яке переводить систему з початкового стану в кінцевий , при якому цільова функція (8.1) набуває найбільшого (найменшого) значення.

Розглянемо характерні особливості математичної моделі динамічного програмування:

1) задача оптимізації формулюється як скінчений багатокроковий процес управління;

2) цільова функція (8.1) є адитивною від показника ефективності кожного кроку, тобто виграш від всієї операції складається з виграшів, отриманих на кожному кроці.

, (8.2)

де - показник ефективності на k- мукроці;

3) вибір керування на кожному кроці залежить тільки від стану системи до цього кроку і не впливає на попередні кроки (немає зворотного зв’язку);

4) стан системи після кожного кроку керування залежить тільки від попереднього стану системи ікеруючої дії х_k на k -му кроці та не залежить від попередніх станів системи і керувань (відсутність післядії):

, (8.3)

де - оператор переходу;

5) на кожному кроці керування залежить від скінченого числа керованих змінних, а стан системи S_k залежить від скінченого числа параметрів;

6) оптимальним керуванням є вектор х, який знаходиться шляхом послідовних оптимальних покрокових керувань:

, кількість яких і визначає число кроків задачі.

Дата добавления: 2014-11-18