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

Рассматривается управляемый процесс. В результате управления система (объект управления) приводится из начального состояния S₀ в конечное S(S₀ → S). Предположим, что управление можно разбить на n шагов, то есть решение принимаются последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. Обозначим через X_k управление на k – ом шаге, k = 1,2,3…,n; X_k может быть числом, точкой в n-мерном пространстве или качественным признаком. Пусть X(X₁, X₂,..., X_n) – это управление, приводящее систему из S₀ в S. Обозначим через S_k состояние системы после k-го шага управления. Получаем последовательность состояний:

S₀, S₁, S₂,…, S_k-1, S_k,... S_n-1, S_n; которую изобразим кружками.

Показатель эффективности операции, целевая функция зависит от начального состояния S₀ и управления X

Z=f(S₀,x) (3.1)

Предположим:

1) Состояние системы S_k в конце k-го шага зависит от предшествующего состояния S_k-1 и управления на k-ом шаге X_k. Это требование называется отсутствием последствия:

Это положение записывают в виде уравнений

S_k = ϥ_k(S₀,x_k) k=1,2,3...n (3.2)

Которые называются уравнениями состояния.

2) Обозначим показатель эффективности k-го шага через

Z_k=f_k(S_k-1,x_k) k=1,2,3...n (3.3)

тогда

Z=∑ⁿ_k=1 а(S_k-1, x_k) (3.4)

Задача динамического программирования (пошаговой оптимизации) формируется так: определить такое управление X, переводящее систему S из состояния S₀ в состояние S, при котором целевая функция (3,4) принимает наибольшее (наименьшее) значение.

 

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

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

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

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

4) Состояние S_k после k-ого шага управления зависит только от предшествующего состояния S_k-1 и управления x_k (отсутствия последствий).

5) На каждом шаге управления x_k зависит от конечного числа управляющих переменных, а состояние S_k от конечного числа параметров.