Принцип оптимальности и рекуррентные соотношения Беллмана
Принцип оптимальности был сформулирован Беллманом в 1953г. Сформулируем его так, как было предложено Венцель (несколько отличным образом).
Рассмотрим n-й последний шаг: Sn-1 состояние системы к началу n-ого шага, Sn – конечное состояние, Хn – управление на n-ом шаге, а fn (Sn-1, Xk) – целевая функция (или как еще говорят – выигрыш) n-ого шага.
Согласно принципу оптимальности, Хn нужно выбирать так, чтобы для любых состояний Sn-1 получить максимум (или минимум – ограничимся задачей на максимум – это не принципиально) целевой функции на этом шаге. Каково бы ни было состояние S системы в результате какого-либо шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Принцип оптимальности утверждает, что для любого процесса без обратной связи оптимальное управление таково, что оно является оптимальным для любого подпроцесса по отношению к исходному состоянию этого процесса. Поэтому решение на каждом шагу оказывается наилучшим с точки зрения управления в целом.
Рекуррентные соотношения Беллмана. Вместо исходной задачи с фиксированным числом шагов n и начальным состоянием S0 рассмотрим последовательность задач, полагая последовательно n = 1, 2, … при различных S – одношаговую, двухшаговую, и т.д. – используя принцип оптимизации.
На каждом шаге для любого состояния системы Sk-1решениеХk (управление) нужно выбирать «с оглядкой», так как этот выбор влияет на последующее состояние Sk и дальнейший процесс управления, зависящий от Sk.
Но есть один шаг, последний, который может для любого состояния Sn-1планировать локально-оптимально, исходя только из соображений этого последнего шага.
Обозначим через (Sn-1) максимум целевой функции – показателя эффективности n-ого шага при условии, что к началу последнего шага система S была в произвольном состоянии Sn-1, а на последнем шаге управление было оптимальным.
(Sn-1) называется условным максимумом из функции на n-ом шаге. Очевидно, что
{ Хn}Хn} |
Максимизация ведется по всем допустимым управлениям Хn.
Решение Хn, при котором достигается (Sn-1), также зависит от Sn-1 и называется условным оптимальным управлением на n-ом шаге. Оно обозначается (Sn-1).
Решив одномерную задачу локальной оптимизации по уравнению (1), найдем для всех возможных состояний Sn-1 две функции (Sn-1) и (Sn-1).
Рассмотрим теперь двух шаговую задачу: присоединим к n-ому шагу (n-1) ша .
Для любых состояний Sn-2, произвольных уравнений Хn-1 и оптимальном уравнении на n-ом шаге значение целевой функции на двух последних шагах равно
fn-1 (Sn-2, Xn-1) + (Sn-1) (2)
согласно принципу оптимальности для любого Sn-2 решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем n-ом шаге приводило бы к максимуму целевой функции на двух последних шагах. Следовательно, нужно найти максимум выражения (2) по всем допустимым управлениям Xn-1. Максимум этой суммы зависит от Sn-2, обозначается
(Sn-2) и называется максимум целевой функции при оптимальном управлении на двух последних шагах.
Соотношение управления Xn-1 на (n-1) – шаге обозначается (Sn-2) и называется условным оптимальным управлением на (n-1) – шаге.
{Хn-1}Хn} |
Следует обратить внимание на то, что выражение в фигурных скобках зависит только от Sn-2 и Xn-1, т.к. Sn-1 можно найти из уравнения состояний при k=n-1
Sn-1 = φn-1 (Sn-2, Xn-1)
В результате максимизации по переменной Xn-1 согласно уравнению (3) вновь получаем две функции:
(Sn-2) и (Sn-2)
Далее рассматривается трех шаговая задача: к двум последним шагам присоединяется (n-2) шаг и т.д. Выражение (3) можно обобщить следующим образом.
Обозначим через (Sk-1) условный максимум целевой функции при оптимальном управлении на n-k+1 шагах, при условии, что к началу k-ого шага система находилась в состоянии Sk-1, т.е. k=n-1, n-2, …., 2, 1; если k=n-1, то
1. n-k+1 = n-n+1+1=2 – тогда (Sk-1) – условный максимум целевой функции при оптимальном управлении на двух последних шагах
2. k=n-2 n-n+2+1 = 3 – на трех последних шагах
3. k=1 n-1+1 = n - на n последних шагах.
Итак по аналогии: для любых состояний Sk-1, произвольном управлении Хk и оптимальном уравнении на последующих (n-k) – шагах значение целевой функции на последних (n-k+1) – шагах равно
fk (Sk-1, Xk) + (Sk)
Максимум этой суммы зависит от Sk-1 и обозначается (Sk-1), т.е.
{Хk}Хn} |
k=n-1, n-2, ….., 2, 1
управление Xk на k-ом шаге, при котором достигается максимум (**)
при k=n
{Хn} |
(Sk-1) = max {fk (Sk-1, Xk) + (Sk)} (4)
k=n-1, n-2, ….., 2, 1
Управление Xk на k-ом шаге, при котором достигается максимум (4), обозначается (Sk-1) и называется условным оптимальным управлением на k-ом шаге (в правую часть вместо Sk нужно подставить Sk = φk (Sk-1, Xk), найденное из уравнений состояний.
Уравнения (4) называются рекуррентными соотношениями Беллмана. Эти соотношения позволяют найти предыдущее значение функции, зная последующее. Если из (1) найти (Sn-1), то при k=n-1 из (4) можно определить, решив задачу максимизации для всех возможных значений Sn-2, выражение для (Sn-2) и соответствующее управление (Sn-2). Далее, зная (Sn-2), по аналогии (Sn-3) и (Sn-3) (k=n-2).
Процесс решения уравнений (1) и (4) называется условной оптимизацией.
В результате условной оптимизации получаются две последовательности
(Sn-1), (Sn-2), ……, (S2), (S0) – условные максимумы целевой функции на последнем, на двух последних и т.д., наконец, на n- последних шагах.
При этом набор значений для разных возможных значений Sn-1
(Sn-1), (Sn-2), ……, (S2), (S0) – условные оптимальные управления на n-ом, (n-1)-м, …, 1-м шагах.
Используя эти последовательности, можно найти решение задачи динамического программирования при данных n и S0. По определению (S0) – условный максимум целевой функции за n шагов при условии, что к началу первого шага система была в состоянии S0, т.е. Zmax= (S0)
Далее следует последовательность условных оптимальных управлений и уравнений состояний.
При фиксированном S0 получаем = (S0).
Далее из уравнений состояний находим = φ1 (S0, ), через здесь обязательно состояние системы после k-ого шага.
В последовательность условных оптимальных управлений
= (S1) и т.д. по цепочке:
= (S0) = φ1 (S0, ) => = ( ) = φ2 ( , ) =>
= ( ) ….. = φn-1 ( , ) => = ( )
означает уравнения состояния, а => - последовательность условных оптимальных управлений.
В результате получаем оптимальное решение задачи динамического программирования:
= , )
Дата добавления: 2016-01-30; просмотров: 2837;