Уравнение Беллмана

Выполнение этих условий иногда оказывается очевидным, а иногда достигается после соответствующих преобразований. Чтобы построить модель ДП, необходимо выяснить, как на основе принципа оптимальности строится оптимальное уравнение n-шагового процесса.
Пусть система на k-м шаге под действием управления u^k переходит из состояния ε^k-1в состояние ε^k. Из принципа отсутствия последействия имеем, что ε^k зависит только от ε^k-1 и u^k.
Эти условия записываются в виде уравнений состояний:
ε^k = T_k(ε^k-1, u^k), k = 1,..,n (5.1)
Из принципа оптимальности следует, что последующие управления u^k+1, …, uⁿ должны выбираться оптимальными относительно состояния ε^k. Это значит, что при этих управлениях оптимизируется целевая функция на шагах k + 1 ,..., n.

Задача оптимизации процесса, начиная с (k + 1)-го шага, похожа на исходную задачу при начальном состоянии системы ε^k, управлении u^k+1 = (u^k+1 , …, uⁿ) и показателе эффективности F_k+1 = F_k+1(ε^k, u^k+1, …, uⁿ). Выбрав оптимальное управление u^k+1 = (u^(k+1)*, …, u^n*) нa шагах k + 1,..., n, получим величину критерия , которая зависит только от ε^k – начального состояния для шагов k + 1,..., n.
Величина F^*_k+1(ε^k) называется условным максимумом.
Возникает задача, как выбрать оптимальное управление на k-м шаге, если известны оптимальные управления u^(k+1)*,..., u^n* на последующих шагах k + 1,..., n и максимальное значение показателя эффективности F^*_k+1(ε^k) на этих шагах k + 1,...., n.
Так как состояние ε^k зависит от управления u^k (5.1), то и величина F^*_k+1(ε^k) зависит от u^k. Поэтому u^k* необходимо выбирать так, чтобы это управление в совокупности с оптимальными управлениями u^(k+1)*,..., u^n* приводило бы к общему максимуму показателя эффективности на шагах k + 1, …, n плюс данный шаг k. Аналитически это записывается так:

. (5.2)

Это основное функциональное уравнение динамического программирования – уравнение Беллмана.
Оптимальное управление на k-м шаге u^k*, при котором достигается максимум (5.2), зависит от состояния ^k* в начале k-го шага u^k* = u^k*(ε^k-1) – это условное оптимальное управление на k-м шаге.
Отметим особенность уравнения (5.2) для k = n:
,
т. к. F^*_n+1 = 0, поскольку (n + 1) шага нет.

Общими рекомендациями при построении модели ДП являются следующие:
1. Выбирается способ деления процесса на шаги.
2. Вводятся параметры состояния ε^k = (ε₁^k,…, ε_s^k) и переменные управления u^k = (u₁^k,..,u_r^k)
3. Записываются уравнения состояний ε^k = T_k(ε^k-1, u ^k)
4. Из ограничений задачи определяется для каждого шага множество допустимых управлений D_k.
5. Вводятся показатели эффективности f_k(ε^k-1, u ^k) и суммарный показатель .
6. Вводятся условные максимумы показателя эффективности от k-го шага до конца процесса F*_k(ε^k-1) и условные оптимальные управления на k-м шаге u^k*(ε^k-1).
7. Записываются функциональные уравнения Беллмана:

Рассмотрим построение модели ДП на примере.
Задача 1. Планируется распределение начальной суммы средств ε⁰ между n предприятиями П₁, П₂, …, П_n. Выделение предприятию П_k средств u^k приносит доход f_k(u^k), . Определить, какое количество средств нужно выделить каждому предприятию, чтобы обеспечить максимальный суммарный доход.
Математическая модель задачи имеет вид

Построим модель динамического программирования.
Распределение средств между n предприятиями можно рассматривать как n-шаговый процесс. Поэтому за номер k-го шага процесса примем номер предприятия, которому выделяются средства u^k. Очевидно, что переменные u^k, k=1,n можно рассматривать как управляющие переменные. Начальное состояние системы характеризуется начальной величиной средств ε⁰. В конце первого шага состояние системы ε¹= ε⁰-u¹ характеризуется остатком средств после выделения предприятию П₁ средств u¹. Величины ε⁰, ε¹,…, εⁿ характеризуют остаток средств после распределения на предшествующих шагах, будем рассматривать их как параметры состояний. Уравнения состояний в этом случае имеют вид
ε^k= ε^k-1-u^k, k=1,n
Найдем допустимые управления. Рассмотрим k-й шаг. Предприятию П_k можно выделить любое количество из имеющих к началу шага средств ε^k-1. Поэтому допустимое управление u^k удовлетворяет неравенствам 0 ≤u^k ≤ ε^k-1.
Показателем эффективности каждого шага является доход f_k(u^k), суммарным показателем – суммарный доход .
Тогда условным максимумом F^*_k(ε^k-1) будет максимальный суммарный доход на шагах k,…, n с начальным состоянием k-го шага ε^k-1. Условное оптимальное управление u^*_k(ε^k-1) будет определять оптимальное количество средств, выделяемых предприятию П_k, если остаток средств для распределения ε^k-1. Запишем теперь функциональные уравнения Беллмана:
(5.3)
Эти уравнения Беллмана соответствуют обратному ходу вычислений, т. е. когда мы движемся от n-го шага к первому.