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

Нехай процес оптимізації розбитий на п кроків. На кожному кроці потрібно визначити два типи змінних - змінну стану S та змінну керування х. Змінна стану S визначає, в яких станах може бути система на к-му кроці. Залежно від S на цьому кроці можна використати деякі керування, які характеризуються змінною х. Використання керування х на к-му кроці дає деякий результат f_k(S,x_k) iпереводить систему в деякий новий стан S'(S,x_k). Для

кожного можливого стану на к-му кроці (з усіх можливих керувань) вибирається таке керування х_к, щоб результат, якии отримаємо з к-то

по п-ии крок був оптимальним. Числова характеристика цього результату називається функцією Белмана F_k(S) та залежить від

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

Весь розв’язок задачі розбивається на два етапи. На першому етапі знаходять функцію Белмана й оптимальне керування для всіх можливих станів на кожному кроці, починаючи з першого. На останньому п-му кроці знайти оптимальне керування і значения функції Белмана F_n(S) нескладно, оскільки F_n(S) = max{f_k(S,x_n)}, де

максимум знаходять за всіма можливими значениями х„.

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

F_k(S) = max{f_k(S^,,x_k) + F_k__l(S,x_k)}. (7.4)

Цей максимум (чи мінімум) знаходиться за всіма можливими для к iS значениями керованої змінної х_k.

Після того, як функція Белмана і відповідне оптимальне керування знайдені для всіх кроків з першого до п-то (на першому кроці k=l стан системи рівний її початковому стану So), виконуємо другий етап розв’язання задачі згідно з алгоритмом зворотної прогонки. Знаючи оптимальне керування на и-му кроці х_п, ми можемо шукати оптимальне керування на (п-\) кроці доти, доки не дійдемо до першого.

Таким чином, в процесі оптимізації керування методом динамічного програмування багатокроковий процес «проходиться» двічі: перший раз - з початку до кінця, в результаті чого знаходимо умовні оптимальні керування і умовні оптимальні виграші; другий раз - від кінця до початку, коли нам залишається тільки «прочитати» вже готове керування, що складається з оптимальних покрокових управлінь.