21.Общая постановка задачи динамического программирования (дп). Особенности задачи дп

ДП – метод оптимизации многошаговых операций. Такие задачи начал рассматривать Беллман в середине 20 века. Объект управления S:S₀→S начальное состояние – конечное состояние. Пусть это управление можно разбить на n шагов, при этом решение будет приниматься на каждом шаге. x_k – решение на каждом шаге, S_k – состояние объекта управления после k шага.

Вводится показатель эффективности управления – целевая функция.

Z = f(S₀,x)→opt (1); x = (x₁, x₂,…,x_n)

Состояние системы после k шага зависит только от состояния системы на предыдущем шаге k-1 и управления. S_k=f_k(S_k-1,x_k)

Прибыль на k шаге зависит от x_k и S_k-1. Z=f_k(S_k-1,x_k)

Прибыль за всю операцию составляет сумма прибыли на каждом шаге

Задача: Определить такое допустимое управление x, приводящее систему из S₀ в S_п, в котором целевая функция (1) принимает свое оптимальное значение. Особенности: Каждая ЗЛП разбивается по n шагов; отсутствует обратная связь, выбор x_k зависит только от x_k-1; Состояние системы зависит S_k зависит от x_k и S_k-1; принцип отсутствие последствия.