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

Вместо исходной задачи ДП с фиксированным числом шагов- n и начальным состоянием So рассмотрим последовательность задач, полагая последовательно n =1,2,... при различных S — одношаговую, двухшаговую и т.д., — используя принцип оптимальности.

Введем ряд новых обозначений.

Обозначения в ДП несут большую информационную нагрузку, поэтому очень важно их четко усвоить.

На каждом шаге любого состояния системы Sk-1 решение Хk нужно выбирать "с оглядкой", так как этот выбор влияет на по­следующее состояние Sk и дальнейший процесс управления, зави­сящий от Sk.

Это следует из принципа оптимальности.

Но есть один шаг, последний, который можно для любого со­стояния Sn- 1 планировать локально-оптимально, исходя только из соображений этого шага.

Рассмотрим n -й шаг:

Sn- 1— состояние системы к началу n -го шага, Sk = S’ — конечное состояние, Хn — управление на n -м шаге, а f_n(Sn-1, Хn) — целевая функция (выигрыш) n -го шага.

Согласно принципу оптимальности, Хn нужно выбирать так, чтобы для любых состояний Sn-1 получить максимум ¹⁾ целевой функции на этом шаге.

Обозначим через Z*_n(Sn- 1 ) максимум целевой функции — показателя эффективности n -го шага при условии, что к на­чалу последнего шага система S была в произвольном состоя­нии Sn- 1, а на последнем шаге управление было оптималь­ным.

Z*_n(Sn- 1 ) называется условным максимумом целевой функции на п-м шаге.

Очевидно, что

Z*_n (Sn-1) = max f_n (Sn-1, X_n) (5)

Максимизация ведется по всем допустимым управлениям Хn.

Решение Хn, при котором достигается Z*_п(Sn- 1 ) также зависит от Sn- 1 и называется условным оптимальным управлением на п -м шаге.

Оно обозначается через Х*n (Sn- 1 ). Условно оптимальный

выигрыш на n - м шаге

Значение целевой функции (п- 1)-го шага при произвольном управлении

Хn -1 и состоянии Sn-2

fn-1(Sn-2,Xn-1)

Рис.2

Решив одномерную задачу локальной оптимизации по уравне­нию (5), найдем для всех возможных состояний Sn- 1 две функ­ции:

Z*_n (Sn-1) и X* (Sn-1). _____________________________________________________

¹⁾ Ограничимся здесь задачей максимизации целевой функции

Рассмотрим теперь двухшаговую задачу:

присоединим к n -му шагу (n- 1)-й (рис.2).

Для любых состояний Sn -2, произвольных управлений Хn- 1и оптимальном управлении на n-м шаге значение целевой функции на двух последних шагах равно:

fn-1(Sn-2, Xn-1)+ Z*_n(Sn-1). (6)

Согласно принципу оптимальности для любых Sn -2 решение нужно выбирать так, чтобы оно вместе с оптимальным управле­нием на последнем (n -м) шаге приводило бы к максимуму целе­вой функции на двух последних шагах. Следовательно, нужно найти максимум выражения (6) по всем допустимым

управле­ниям Хn- 1.

Максимум этой суммы зависит от Sn -2» обозначается через Z*n -1 (Sn -2) и называется условным максимумом целевой функции при оптимальном управлении на двух последних шагах.

Соответ­ствующее управление Хn- 1 на (n -1)-м шаге обозначается через Х*n- 1 (Sn- 2 ) и называется условным оптимальным управлением на (n -1)-м шаге.

Z*n-1(Sn -2) = max{fn-1 (Sn-2, Xn-1) + Z*n(Sn-1)} (7)

Следует обратить внимание на то, что выражение, стоящее в фигурных скобках (7), зависит только от Sn- 2 и Xn -1, так как Sn -1 можно найти из уравнения состояний (2) при k=n- 1

Sn- 1 =φn- l (Sn- 2, Хп- 1 )

и подставить вместо Sn -1 в функцию Z*n (Sn - 1 ).

В результате максимизации только по одной переменной Хn-1 согласно уравнению (7) вновь получаются две функции