Постановка задачи динамического программирования

Динамическое программирование – это поэтапное планированиемногошагового процесса, при котором на каждом этапе оптимизируется толькоодин шаг. Управление на каждом шаге должно выбираться с учетом всех его последствий в будущем.

В общем виде постановка задачи ДП сводится к следующему.

Имеется некоторая управляемая операция или целенаправленное действие, распадающаяся естественно или искусственно на n шагов. На каждом шаге осуществляется распределение и перераспределение ресурсов, участвующих в операции, с целью улучшения ее результата в целом. Это распределение ДП называется управлением операции и обозначается Y.

Эффективность операции в целом оценивается тем же показателем, что и эффективность ее управления. При этом эффективность управления зависит от совокупности управлений на каждом шаге операции:

w(u) = w(u1,u2,…,un).

Управление, при котором показатель достигает максимума, называется оптимальным управлением.

w(u^*) = max w(u)

u

Оптимальное управление многошаговым процессом состоит из совокупности оптимальных пошаговых управлений.

u* = (u₁^*, u₂^*,…,u_n^*)

Задача ДП – определит оптимальное управление на каждом шаге и тем самым оптимальное управление всей операцией в целом.

В большинстве практических задач принимается, что показатель эффективности операции в целом – сумма эффективности действий на всех этапах операции.

Выделим особенности модели динамического программирования:

- задача оптимизации интерпретируется как n-шаговый процесс управления;

- целевая функция равна сумме целевых функций каждого шага;

- выбор управления на k-м шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги (нет обратной связи);

- состояние s_k после k-го шага управления зависит только от предшествующего состояния s_k-1 и управления Х_k (отсутствие по­следействия);

- на каждом шаге управление Х_k зависит от конечного числа управляющих переменных, а состояние s_k - от конечного числа па­раметров.