60. Динамічне програмування.

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

; (8.159) ; (8.160) . (8.161)

Замість мінімізації витрат може ставитися вимога максимізації зиску. Часто обмеження (8.161) задають у вигляді нерівностей типу .

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

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

Рис. 8.26

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

На передостанньому етапі перевезення продукту в пп. , , можна здійснити з пп. , , . Якщо транспортування починається з п. , то оптимальний перехід в п. визначається з порівняння перевезень по маршрутах , , що можна записати як

.

Припустимо, що мінімальним є значення . Цей час є умовно оптимальним на даному кроці. Якщо перевезення здійснюється з п. , то маємо

.

Припустимо, що мінімальним є час , тобто тут він є умовно оптимальним. Під час перевезення з п. –

.

Припустимо, що мінімальним є час . Тепер на цьому етапі необхідно вибрати мінімальне значення з отриманих значень , , . Тобто треба знайти

.

Припустимо, що мінімальним є час .

На останньому етапі необхідно мінімізувати суми значень часу по маршрутах , , й умовно мінімальних значень часу під час перевезень продукту з пп. , , і . Отже, маємо

.

Припустимо, що мінімальним є час . Отже, оптимальним є маршрут за шляхом, що відповідає ребрам 3, 9, 12.

Очевидно, задачу динамічного програмування можна розв’язувати повним перебором усіх можливих варіантів. Але такий метод неекономічний порівняно з поетапною оптимізацією. Це ясно видно з наведеного прикладу. Справді, якщо процес розбитий на етапів, на кожному з яких прийнято станів, то при прямому переборі варіантів необхідно розглянути варіантів, а методом динамічного програмування всього варіантів. Наприклад, при і маємо відповідно і варіантів.