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

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

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

1. Обрати пораметри, що характеризують стан системи S

2. Розбити операцію на кроки

3. Визначити набір можливих крокових рішень хі та обмеження накладені на них

4. Визначити функцію виграшу на і-ому кроці:

w_i=f_i(S, x_i)

5. Визначити функцію переходу стану на і-ому кроці в залежності від дії:

S′=φ_i(S, x_i)

6. Записати головне рекурентне рівняння динамічного програмування, що визначає умовний оптимальний виграш:

7. Виконати умовну оптимізацію останнього кроку, таким чином, щоб:

Знаходимо умовне оптимальне рівняння x_M(S)

8. Проводимо умовну оптимізацію для m-1 кроку і відповідно усіх попередніх, визначаючи x_i(S) і якщо початковий стан відомий, то

9. Провести безумовну оптимізацію згідно рекомендаціям на кожному кроці: x_i*=x_i(S₀) відповідно змінюючи стан