Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

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

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

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

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

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

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

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

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

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

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

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

(13.5)

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

.

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

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

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

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

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

 

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

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

(13.7)

 

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

Sп-1 = φ n-1(Sn-2, Xn1l)

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

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

 

Z*n-l (Sn-2) и Х*п1 (Sn-2).

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

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

Z*k (Sk-1) = max .

{Xk, …, Xn}

Тогда Z*k+ 1 (Sk) = max .

{Xk+1, …, Xn}

 

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

fk(Sk-1, Xk) + Z*k+1(Sk)

       
 
 
   
fk(Sk-1, Xk)

 

 


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

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

 

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

k}

 

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

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

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

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

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

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

Z*n(Sn-1), Z*n-1(Sn-2),..., Z*2(S1), Z*1(S0) ­

 

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

X *n(Sn-1), X*n-1(Sn-2),..., X *2(S1), X*1(S0) ­

 

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

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

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

 

Zmax = Z*(S0). (13.9)

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

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

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

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

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

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

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

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.01 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал