Алгоритм методу динамічного програмування

Вибір параметрів, які характеризують стан керованої системи перед кожним кроком. Розділ операції (процесу) на кроки. Формування набору крокових управлінь та обмежень, що на них накладаються. Формулювання “функції виграшу”, тобто визначення виграшу, який приносить на і-му кроці управління якщо система була у стані. (2.33) Формулювання функції “зміни стану”, тобто визначення як змінюється стан . системи Sі під впливом управління xi на і-тому кроці (2.34) Запис рекурентного співвідношення ДП, яке визначає умовно оптимальний виграш починаючи з і-кроку і до кінця через вже відому функцію (2.35) Цьому виграшу відповідає умовно оптимальне управління на і-кроці Проведення умовної оптимізації останнього (-го) кроку, при варіації набору станів, з яких за один крок можна дійти до кінцевого стану. Визначення для кожного стану умовно оптимального виграшу (2.36) та відповідного йому умовно оптимального управління при якому цей максимум досягається. Проведення умовної оптимізації -го,-го і т.д. кроків за рекурентною формулою (2.35) та визначення умовно оптимальних управлінь. Якщо стан системи на початок процесу відомий то здійснення варіювання стану системи на першому кроці не потрібне. Одразу визначається оптимальний виграш для даного стану системи . Це і є оптимальний виграш за всю операцію (2.37) Здійснення безумовної оптимізації управління “зчитуючи” відповідні рекомендації на кожному кроці. Визначення за оптимальним управлінням на першому кроці стану системи за залежністю (2.34); знаходження для нового стану оптимального управління на другому кроціі т.д. до кінця.

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

Оскільки критеріальна функція є адитивною, знаходження найкращого рішення можна здійснити методом ДП за алгоритмом, наведеним вище.

1. Керована система – це ресурси, які розподіляються. Стан системи перед кожним кроком- це запас ресурсів, який ще не розподілений.

2. Розподіл операції на кроки:

перший крок (i=1) - вкладення ресурсів в П₁

другий крок(i=2) – вкладення ресурсів в П₂

третій крок(i=3) – вкладення ресурсів в П₃

= = = = = = = = = = = = = = = = = = = =

m-ий крок(s=m) – вкладення ресурсів в П_m .

3. Крокові управління - ,це ресурси, що вкладаються в кожне підприємство. Візьмемо дуже грубий крок дискретизації ресурсів1од. Обмеження, що накладаються на крокові управління :

4. Функція виграшу задана в табличній формі (табл.. 2.13).

Оптимальне управління це управління, при якому сумарний прибуток є максимальним

(2.38)

5. Функція зміни стану (схема процесу подана на рис. 2.5):

(2.39)

Рис. 2.5.Схема розподілу ресурсів

Вузли схеми – це стан системи перед наступним кроком, тобто, наявні для розподілу ресурси. Зв’язки – управління при заданому стані.

6. Рекурентне співвідношення:

(2.40)

7. Почнемо оптимізацію з останнього 3-го (-го) кроку. Очевидно, що яким би не був запас ресурсівперед початком цього кроку, його повністю треба вкладати в підприємствоП₃(П_m). Тому умовно оптимальне управління на цьому кроці віддати 3-ому (-му) підприємству весь наявний запас ресурсів. Тобто,

А умовно оптимальний виграш

(2.41)

або у загальному вигляді:

(2.42)

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