Принцип оптимальности и уравнения Беллмана

Принцип оптимальности впервые былсформулирован Ричардом Белл­маном в 1953 г. Каково бы ни было состояние S системы в резуль­тате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управле­нием на всех последующих шагах приводило к оптимальному выигры­шу на всех оставшихся шагах, включая данный.

Отметим, что эта формулировка принципа несколько отличается от исходной, сформулированной Беллманом и дана Е. С. Вентцель.

Беллманом сформулированы и условия, при которых принцип верен. Основное требование - процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно ока­зывать влияния на предшествуюшие шаги.

Принцип оптимальности утверждает, что для любого процесса без обратной связи оптимальное управление таково, что оно явля­ется оптимальным для любого подпроцесса по отношению к исходному состоянию этого подпроцесса. Поэтому решение на каж­дом шаге оказывается наилучшим с точки зрения управления в целом. Если изобразить геометрически оптимальную траекторию в виде ломаной линии, то любая часть этой ломаной будет яв­ляться оптимальной траекторией относительно начала и конца.

Уравнения Беллмана. Вместо исходной задачи динамического программирования с фиксированным числом шагов п и начальным состоянием S₀ рассмотрим последовательность задач, полагая последовательно п=l, 2,... при различных S - одношаговую, двухшаговую и т. д., используя принцип оптимальности. ­

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

На каждом шаге любого состояния системы S_k-1 решение X_k необходимо выбирать «с оглядкой», так как этот выбор влияет на по­следуюшее состояние S_k и дальнейший процесс управления, зави­сящий от S_k. Это следует из принципа оптимальности.

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

Рассмотрим n-й шаг: S _n-1 - состояние системы к началу n-го шага, S _n= S_i - конечное состояние, Хп - управление на n-м шаге, fn(S_n-1, Х_n) - целевая функция (выигрыш) n-го шага.

Согласно принципу оптимальности, Х_n нужно выбирать так, чтобы для любых состояний S_n-1 получить максимум целевой функции на этом шаге (будем для конкретности рассматривать только задачу максимизации).

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

Z_n*(S_n-1) называется условным максимумом целевой функции на n-м шаге. Очевидно, что

(13.5)

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

.

Решение Х_n, при котором достигается Z_n*(S_n-1), также зависит от S_{n-1 и} называется условным оптимальным управлением на n-м шаге. Оно обозначается через X_n* (S_n-1).

Решив одномерную задачу локальной оптимизации по уравнению (13.5), определим для всех возможных состояний S_n-1 две функции: Z_n*(S_n-1) и X_n* (S_n-1).

_ Рассмотрим теперь двухшаговую задачу: присоединим к n-му шагу (п-1)-й (рисунок 13.2).

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

f,, -1(Sn-2, Xn-l)+ Z; (Sn-l)' ( 13.6)

Согласно принципу оптимальности для любых S_n-2 решение нужно выбирать так, чтобы оно вместе с оптимальным управле­нием на последнем (n-м) шаге приводило бы к максимуму целе­вой функции на двух последних шагах. Следовательно, нужно определить максимум выражения (13.6) по всем допустимым управлениям X_n-1. Максимум этой суммы зависит от S_n-2, обозначается через Z*_n-I (S_n-2) и называется условным максимумом целевой функции при оптимальном управлении на двух последних шагах.

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

(13.7)

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

S_п-1 = φ _n-1(S_n-2, X_n1l)

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

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

Z*_n-l (S_n-2) и Х*_п1 (S_n-2).

Далее рассматривается трехшаговая задача: к двум последним шагам присоединяется (п-2)-й и т.д.

Обозначим через Z*_k (S_k-1) - условный максимум целевой функции, полученный при оптимальном управлении на n – k + 1 шагах, начиная с k- го до конца, при условии, что к началу k-го шага система находи­лась в состоянии S_k-. Фактически эта функция равна

Z*_k (S_k-1) = max .

{X_k, …, X_n}

Тогда Z*_{k+ 1} (S_k) = max .

{X_k+1, …, X_n}

Целевая функция на n – k последних шагах (рисунок 13.1) при произвольном управлении X_k на k- м шаге и оптимальном управлении на последующих n – k шагах равна f_k(S_k-1, X_k) + Z*_k+1 (S_k).

		fk(Sk-1, Xk)

Рисунок 13.1 - Пояснение к получению выражения для целевой функции

Согласно принципу оптимальности, X_k выбирается из условия максимума этой суммы, т.е.

, k = n-1, n-2, …, 2, 1. (13.8)

{Х_k}

Управление X_k на k-м шаге, при котором достигается максимум в (13.8), обозначается через Х*(S_k-1) и называется условным оптимальным управлением на k-м шаге (в правую часть уравнения (13.8) следует вместо S_k подставить выражение Sk = φ _k(S_k-1, X_k), полученное из уравнений состояния).

Уравнения (13.8) называют уравнениями Беллмана. Это рекуррентные соотношения, позволяющие получить предыдущее значение функции, зная последующие.

Если из (13.5) получить Z^*_n(S_n-1), то при k = n-1 из (13.8) можно определить, решив задачу максимизации, решив для всех возможных значений S_n-2, выражения для Z^*_n-1 (S_n-2) и соответствующее Х_п-1 (S_n-2).

Далее, зная Z^*_n-1 (S_n-2), получаем, используя (13.8) и (13.2), уравнения состояний.

Процесс решения уравнений (13.5) и (13.8) называется условной оптимизацией. В данном случае рассмотрен способ решения задачи динамического программирования, начиная с последнего шага (так называемая «обратная схема»). В принципе можно n-1 и 1-й шаги поменять местами и это будет, так называемая «прямая схема».

В результате условной оптимизации получаются две последовательности:

Z*_n(S_n-1), Z*_n-1(S_n-2),..., Z*₂(S₁), Z*₁(S₀) ­

условные максимумы целевой функции на последнем, на двух последних, на ...п шагах и

X *_n(S_n-1), X*_n-1(S_n-2),..., X *₂(S₁), X*₁(S₀) ­

условные оптимальные управления на п-м, (п-1)-м,..., l-м шагах.

Используя эти последовательности, можно получить решение задачи динамического программирования при данных п и S₀.

По определению Z*₁ (S₀) - условный максимум целевой функции за п шагов при условии, что к началу l-го шага система была в состоянии S₀, т.е.

Z_max = Z*(S₀). (13.9)

Далее следует использовать последовательность условных оп­тимальных управлений и уравнения состояний (13.2).

При фиксированном S₀ получаем Х^*₁ = Х*₁ (S₀). Далее из урав­нений (13.2) получаем S₁= φ ₁(S₀', X*₁) и подставляем это выраже­ние в последовательность условных оптимальных управлений: Х^*₂ = Х*₂ (S₁) и т.д.по цепочке:

В результате получается оптимальное решение задачи динамического программирования X^* = (X^*₁, X^*₂, …, X^*_n).

В приведенной цепочке используются следующие обозначения:

→ - использование уравнений состояния;

- использование последовательности условных оптимальных управлений;

S_k - состояние системы после k-го шага при условии, что на k- м шаге выбрано оптимальное управление.