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

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

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

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

На кожному з кроків з метою покращення результату операції в цілому здійснюється розподіл і перерозподіл ресурсів, тобто управління змінними u_i (u ₁, u ₂,… u_m). Ефективність операції в цілому характеризується показником W, який залежить від всієї сукупності управлінь u і на кожному з кроків

W = W (u)= W (u ₁, u ₂,..., u_m) (2.19)

Управління, при якому показник W досягає оптимального значення - максимуму чи мінімуму, називається оптимальним управлінням u *, яке складається з оптимальних кроків управлінь

u * = (u ₁*, u ₂*,..., u_m *) (2.20)

Задача динамічного програмування – визначити u_i * на кожному кроці, i =1,2..., m, і u * – всієї операції в цілому.

Метод динамічного програмування був запропонований Р. Беллманом та його учнями на початку 50-х років і полягає в тому, що оптимальний розв’язок функції мети шукається при загальному обмеженні на змінні параметри.

Характерним для задачі динамічного програмування є те, що змінні розглядаються разом, а не послідовно одна за одною. При цьому обчислення здійснюють так, що замість однієї задачі з n змінними розв’язується декілька задач з меншою кількістю змінних, а найчастіше – з однією змінною. Сам процес розв’язку здійснюється на основі методу послідовних наближень в два етапи:

1. Від останнього кроку до першого;
2. Від першого кроку до останнього, або навпаки, в залежності від початкових даних.

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

Неможливо побудувати оптимальне значення функції мети i-крокового процесу, якщо для будь-якого u_i, вибраного на i-му кроці, значення функції мети для решти i-1 кроків не є оптимальним, при цьому вибраному на i-му кроці значенні u_i.

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

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

Після цього настає другий етап, протягом якого можна побудувати не умовно оптимальне, а дійсно оптимальне управління u * і знайти шуканий оптимальний виграш W*. Для цього достатньо, переміщуючись від початку до кінця, прочитати вже готові рекомендації і знайти u *, що складається з u ₁*, u ₂*,..., u_m *. Стосовно самого оптимального виграшу W* за всю операцію, то він вже відомий, оскільки саме в процесі його оптимальності вибрано управління на першому кроці.