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

Принцип оптимальности был сформулирован Беллманом в 1953г. Сформулируем его так, как было предложено Венцель (несколько отличным образом).

Рассмотрим n-й последний шаг: S_n-1 состояние системы к началу n-ого шага, S_n – конечное состояние, Х_n – управление на n-ом шаге, а f_n (S_n-1, X_k) – целевая функция (или как еще говорят – выигрыш) n-ого шага.

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

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

Рекуррентные соотношения Беллмана. Вместо исходной задачи с фиксированным числом шагов n и начальным состоянием S₀ рассмотрим последовательность задач, полагая последовательно n = 1, 2, … при различных S – одношаговую, двухшаговую, и т.д. – используя принцип оптимизации.

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

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

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

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

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

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

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

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

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

f_n-1 (S_n-2, X_n-1) + (S_n-1) (2)

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

(S_n-2) и называется максимум целевой функции при оптимальном управлении на двух последних шагах.

Соотношение управления X_n-1 на (n-1) – шаге обозначается (S_n-2) и называется условным оптимальным управлением на (n-1) – шаге.

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

S_n-1 = φ_n-1 (S_n-2, X_n-1)

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

(S_n-2) и (S_n-2)

Далее рассматривается трех шаговая задача: к двум последним шагам присоединяется (n-2) шаг и т.д. Выражение (3) можно обобщить следующим образом.

Обозначим через (S_k-1) условный максимум целевой функции при оптимальном управлении на n-k+1 шагах, при условии, что к началу k-ого шага система находилась в состоянии S_k-1, т.е. k=n-1, n-2, …., 2, 1; если k=n-1, то

1. n-k+1 = n-n+1+1=2 – тогда (S_k-1) – условный максимум целевой функции при оптимальном управлении на двух последних шагах

2. k=n-2 n-n+2+1 = 3 – на трех последних шагах

3. k=1 n-1+1 = n - на n последних шагах.

Итак по аналогии: для любых состояний S_k-1, произвольном управлении Х_k и оптимальном уравнении на последующих (n-k) – шагах значение целевой функции на последних (n-k+1) – шагах равно

f_k (S_k-1, X_k) + (S_k)

Максимум этой суммы зависит от S_k-1 и обозначается (S_k-1), т.е.

k=n-1, n-2, ….., 2, 1

управление X_k на k-ом шаге, при котором достигается максимум (**)

при k=n

(S_k-1) = max {f_k (S_k-1, X_k) + (S_k)} (4)

k=n-1, n-2, ….., 2, 1

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

Уравнения (4) называются рекуррентными соотношениями Беллмана. Эти соотношения позволяют найти предыдущее значение функции, зная последующее. Если из (1) найти (S_n-1), то при k=n-1 из (4) можно определить, решив задачу максимизации для всех возможных значений S_n-2, выражение для (S_n-2) и соответствующее управление (S_n-2). Далее, зная (S_n-2), по аналогии (S_n-3) и (S_n-3) (k=n-2).

Процесс решения уравнений (1) и (4) называется условной оптимизацией.

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

(S_n-1), (S_n-2), ……, (S₂), (S₀) – условные максимумы целевой функции на последнем, на двух последних и т.д., наконец, на n- последних шагах.

При этом набор значений для разных возможных значений S_n-1

(S_n-1), (S_n-2), ……, (S₂), (S₀) – условные оптимальные управления на n-ом, (n-1)-м, …, 1-м шагах.

Используя эти последовательности, можно найти решение задачи динамического программирования при данных n и S₀. По определению (S₀) – условный максимум целевой функции за n шагов при условии, что к началу первого шага система была в состоянии S₀, т.е. Z_max= (S₀)

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

При фиксированном S₀ получаем = (S₀).

Далее из уравнений состояний находим = φ₁ (S₀, ), через здесь обязательно состояние системы после k-ого шага.

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

= (S₁) и т.д. по цепочке:

= (S₀) = φ₁ (S₀, ) => = () = φ₂ (, ) =>

= () ….. = φ_n-1 (, ) => = ()

означает уравнения состояния, а => - последовательность условных оптимальных управлений.

В результате получаем оптимальное решение задачи динамического программирования:

= , )