Метод динамического программирования Беллмана (Лекции)

МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ БЕЛЛМАНАДинамическое программирование, наряду с принципом максимума,является основным математическим методом, с помощью которогоопределяется оптимальное управление. В отличие от принципа максимума,который формулируется таким образом, что оказывается ориентированным,прежде всего, на определение оптимального управления в виде оптимальнойпрограммы, динамическое программирование позволяет определятьоптимальное управление только в форме синтезирующей функции.Динамическое программирование хорошо обосновано для дискретныхпроцессов. Обоснованное применение динамического программирования длянепрерывных процессов не всегда возможно.

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

Его можно сформулироватьследующим образом. Оптимальная стратегия обладает тем свойством,что независимо от того, каким было первоначальное состояние ипервоначальноерешение,последующиерешениядолжныбытьоптимальными относительно состояния, которое возникло после принятияпервого решения.Рассмотрим применение динамического программирования для решениязадачи оптимального управления.Пусть движение объекта задается системой уравненийdxifi x1, x2 , , xn , u1, u2 , , um , i 1, n,dtили в векторной форме уравнениемdxf (x, u),(4.1)dtx1, , xn — n-мерный вектор состояния, u u1, , um — mздесь xf1, , f nмерный вектор управления, f— n-мерный вектор.Предполагается, что вектор u может принимать свои значения из некоторогомножества U, т.е.

u(t ) U . В качестве минимизируемого будемрассматривать функционалTIG (x, u)dt.(4.2)0В рассматриваемой задаче полагаем фиксированным начальное состояние,которое будем обозначать через x, и конечное состояние x*. Время переходаиз начального состояния в конечное не фиксируется. Так как цельюоптимизации является получение оптимальной синтезирующей функции(оптимальной стратегии), то начальной точкой x может быть любая точкафазового пространства.Минимальное значение функционала (4.2) однозначно определяетсяначальным значением вектора x. Обозначим минимальное значениефункционала S (x) S x1, x2 , , xn .Пусть x(t ), 0 t T , — оптимальная траектория, переводящая фазовуюточку из начального положения x(0)x в конечную точку x*. ТогдаTS ( x)minG x(t ), u(t ) dt.ut U0Представим функционал в видеTTG x(t ), u(t ) dt0G x(t ), u(t ) dtG x(t ), u(t ) dt.0Будем предполагать, что оптимальное управление u(t ) кусочно-непрерывно.Условимся за значения управления в точках разрыва принимать пределысправа.Пусть в интервале (0, ) выбрано некоторое управление u(t ), а вдальнейшем в соответствии с принципом оптимальности выбираетсяоптимальное управление.

ТогдаTG x(t ), u(t ) dtS x( ) .В силу непрерывности траектории x(t )x( ) x(0) x(0)гдеo( )lim0.o( ),0Принимая во внимание уравнение (4.1), можно записатьx( ) x f (x, u) t 0o( ),илиx( )xf (x, u)o( ),здесь u — значение управления в момент t0 . Таким образом,TG x(t ), u(t ) dtS xf ( x, u )o( ) .Далее,G x(t ), u(t ) dtG (x, u)o( ).0Если в начальный момент t 0 выбрано управление u U , а в дальнейшем всоответствии с принципом оптимальности выбиралось оптимальноеуправление, то функционал принимает значениеG (x, u)o( ) S x f (x, u)o( ) .(4.3)Для оптимизации функционала надо минимизировать выражение (4.3). Такимобразом,S (x) min G (x, u)o( ) S x f (x, u)o( ) .(4.4)u UБудем предполагать, что функция S (x) имеет непрерывные частныепроизводные по всем своим аргументам.

Отметим, что справедливость всегопоследующего вывода зависит от того, выполняется это предположение илинет. Заранее функция S (x) неизвестна, и проверить справедливость этогопредположения по уравнениям движения нельзя. Можно решить задачу иопределитьфункциюЕслионаокажетсянепрерывноS (x).дифференцируемой, то приводимые ниже результаты являютсясправедливыми. Однако имеют место случаи, когда функция S (x) неявляется непрерывно дифференцируемой.Поскольку функция S (x) предполагается непрерывно дифференцируемой,тоdSdSS x f (x, u)o( ) S ( x)f (x, u)o( ),dxdxздесь в соответствии с правилами дифференцирования скалярной функции повекторному аргументуdSS SSdxx1 x2xn— матрица-строка.

Из (4.4) находимdSS (x) min G (x, u)S ( x)f (x, u)o( ) ,u UdxилиdS0 min G (x, u)f (x, u)o( ).(4.5)u UdxПоделим неравенство (4.5) наи перейдем к пределу при0. Врезультате получимdSf (x, u) .(4.6)u UdxРавенство (4.6) является функциональным уравнением Беллмана. Куравнению (4.6) необходимо присоединить граничное условиеS x0.(4.7)В частном случае, когда оптимизируется время движения, т.е.0min G (x, u)TIdt ,0уравнение Беллмана принимает видdSf (x, u),(4.8)u U dxздесь функция S (x) задает минимально возможное время движения от точки1minx до точки x*. Для уравнения в частных производных (4.8) граничноеусловие по-прежнему задается равенством (4.7).Решая уравнение в частных производных (4.6), наряду с функцией S (x),задающей в зависимости от начальной точки x минимальное значениефункционала, определяется также функция u(x), которая задаетоптимальную стратегию, или оптимальную синтезирующую функцию.Уравнение Беллмана (4.6) задает необходимое условие минимума.

Именно,если функция S (x) является непрерывно дифференцируемой по всем своимпеременным, то она удовлетворяет уравнению Беллмана (4.6).Пример 4.3. Рассмотрим объект, движение которого задается уравнениямиdx1dx2x2 ,u.dtdtВ качестве конечной точки x* выберем начало координат, т.е. положимx* 0. Качество процесса управления будем оценивать функционаломTx12Ix22u 2 dt.(4.9)0Таким образом, речь идет об определении оптимальной стратегииux1, x2 , которая обеспечивает перевод фазовой точки из произвольногоначального состояния в начало координат, и притом так, чтобы натраекториях движения функционал (4.9) принимал наименьшее значение.Выпишем функциональное уравнение БеллманаSS0 min x12 x22 u 2x2u.(4.10)ux1x2Так как на управляющий параметр u не наложено никаких ограничений, тодля определения минимума необходимо продифференцировать правую частьуравнения (4.10) по u:2uSx20.(4.11)1 S,2 x2и уравнение Беллмана принимает вид(4.12)Из (4.11) находимu2S1 Sx20.(4.13)x14 x2Будем искать решение уравнения (4.13) в виде квадратичной формыS (x) C1x12 C2 x1x2 C3 x22 .ТогдаSS2C1x1 C2 x2 ,C2 x1 2C3 x2 .x1x2Уравнение (4.13) принимает вид1x12 x224C32 x22 4C2C3 x1x2 C22 x122C1x1x2 C2 x22 0.4Коэффициенты C1, C2 , C3 определяются из системы уравнений:1 21C2 0,41 C32 C2 0,(4.14)2C1 C2C3 0.Система нелинейных алгебраических уравнений (4.14) имеет двавещественных решенияC2 2, C33, C13;x12x22C2 2, C33, C13.Эти решения в соответствии с (4.12) приводят к двум синтезирующимфункциямux13 x2 ,(4.15)ux13x2 .(4.16)В результате получаем две линейные системы, причем линейная система,порождаемая функцией (4.16), оказывается неустойчивой и, следовательно,не может обеспечить перевод фазовой точки в начало координат.Таким образом, оптимальная синтезирующая функция (оптимальнаястратегия) задается равенством (4.15).

На рис. 4.1 изображена структурнаясхема оптимальной системы.ux21p1px13Рис. 4.1. Структурная схема оптимальной системы.