6 Основні елементи і принципи динамічного програмування
Розглянуті задачі ЗЗНШ, ЗОВР (ЗОВК) і ЗВРС мають особливості, характерні для всіх багатокрокових процесів прийняття рішень, тому поняття і принципи ДП будемо ілюструвати на прикладах цих задач. При цьому відзначимо, що будь-яка задача ДП може бути зведена до задачі знаходження найкоротшого шляху в мережі. Тому, якщо будемо говорити про мережу і її вершини то, це може відноситись і до будь-якої задачі ДП.
6.1 Адитивність цільової функції і етапи задачі
У
задачах ДП цільова функція (ЦФ)
повинна мати властивість
адитивності:
значення критерію, досягнуте за весь
період планування дорівнює сумі часткових
значень того ж критерію, досягнутих на
окремих кроках (етапах):
де
- це або скалярна величина, або вектор.
Саме
адитивність ЦФ задачі дозволяє розбити
задачу на етапи.
При цьому з кожним з етапів зв'язується
тільки одна керована змінна (
)
і кожному етапу відповідає одна складова
ЦФ:
ЗЗНШ:
- довжина
-го
кроку,
-
дуга, по якій перейшли з
-го
слою до
-го
слою (наприклад дуга
, тоді складова ЦФ:
=
);ЗОВР:
- прибуток від виробництва
-го
продукту в об'ємі
;ЗОВК:
- прибуток від модернізації
-го
підприємства за проектом
.
Якщо в початковій постановці задачі критерій не адитивний, то намагаються видозмінити постановку або сам критерій. Так, наприклад, якщо у вихідній постановці критерій мультиплікативний, то шляхом його логарифмування прийдемо до адитивного вигляду ЦФ. Відзначимо, що розроблено алгоритми ДП і для задач із мультиплікативним критерієм.
6.2 Принцип занурення
У
ЗЗНШ потрібно було визначити
(якщо застосовується АЗП) - довжину
найкоротшого шляху від вершини 1 до
вершини
,
що складається із кроків
.
Однак, замість того, щоб розв’язувати
задачу безпосередньо (відразу шукати
найкоротший
-кроковий
шлях) було здійснено занурення задачі
в клас задач про знаходження найкоротших
шляхів, тобто послідовно обчислювалися
найкоротші шляхи від кожної вершини
мережі до вершини
.
Спочатку шукали всі найкоротші однокрокові
шляхи
,
потім знаходили найкоротші двокрокові
шляхи
і т.д. до
.
В
ЗОВК було потрібно визначити таке
використання інвестицій у підприємства
від 1 до
,
при якому прибуток максимальний і
витрачено
одиниць ресурсу, тобто, визначити
(при застосуванні АПП). Для цього
обчислювалися послідовно:
;
;
…
...
Отже, принцип занурення полягає в наступному. Вихідна задача занурюється в множину оптимізаційних задач: для кожної вершини мережі розв’язується своя задача. Остання задача, що і дає шуканий розв’язок, - одна із множини оптимізаційних задач.
Занурення приводить до ефективних обчислювальних процедур.
6.3 Основне рекурентне співвідношення
Множина розв’язків оптимізаційних задач описується рекурентними співвідношеннями, аналогічними (1), (2), (4), (6) і (8).
Основне рекурентне співвідношення (ОРС) являє собою систему рівнянь, які зв'язують між собою розв’язки побудованої множини оптимізаційних задач.
У
такій системі кожне рівняння відповідає
одній вершині мережі. Ці рівняння
зазвичай містять оператори типу мінімум
або максимум праворуч від знака рівності,
а величини
й
(або
)
по обидві сторони від нього.
Синоніми ОРС: функціональне рівняння, основне функціональне рівняння Белмана.
Розв’язки множини оптимізаційних задач можна знайти за допомогою алгоритму зворотньої (або прямої) прогонки, що є впорядкованою процедурою розв’язання послідовності рекурентних рівнянь.