Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 115
Текст из файла (страница 115)
Таким образом, в случае Г Е" иэ принципа максимума следуют все основные необходимые условия, известные в классическом вариационном исчислении (64, 74, 108, 161, 172, 181, 182, 234, 342). Однако, если У в замкнутое множество и TчАЕ", то соотношение (4), вообще говоря, не выполняется. Более того, имеются примеры, когда и условие Вейерштрасса в этом случае не имеет места ((17, с. 284)). Условие максимума (2.9), являясь естественным обобщением условия Вейерштрасса нз классического вариационного исчислении, имеет то существенное преимущество перед условием Вейерштрасса, что оно применимо для любого (в частности, и замкнутого) множества У ~в Е' и для более общих задач.
Заметим, что именно случай замкнутого множества наиболее интересен в прикладных вопросах, поскольку значения оптимальных управлений чаще всего лежат на границе У. Глава 7 ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В этой главе мы остановимся на методе динамического программирования, часто используемом для численного решения задач оптимального управления при наличии фазовых ограничений, конечиомериых задач минимизации специального вида. С помощью динамического программирования можно также наметить пути решения проблемы синтеза, сформулировать достаточные условия оптимальности для задач оптимальйого управления и т.
д. Изложение метода динамического программирования начнем с простейшей схемы Беллмана для аадачи оптимального управления, затем опишем более совершенную и удобную длп практики схему Моисеева, а также обсудим некоторые другие аспекты атого метода [12, 14, 15, 25, 26, 50, 57 — 60, 65, 68, 81, 101, 124, 161, 169, 188 †1, 213, 215, 217, 225, 234, 262, 263, 265, 285, 305, 308, 317, 319, 326, 327).
й 1. Схема Беллмана. Проблема синтеза для дискретных систем 1. Рассмотрим следующую задачу оптимального управления: т У(1„х„и( )) = ) 7е(х(т), и(т), т)г[т+ Ф(х(Т))-~[в1, (1) ~е х(т) = ~(х(т) п(т) т)~ Йо < т < Т х(1а) хю (2) х(г)шб(т), 1,<т<Т, (3) и = и(т) аэ г'(т), 1, < т< Т; и(т) — кусочно-непрерывна; (4) моменты времени ае Т будем считать заданными (описание обозначений см.
в 3 6.1). Для приближенного решения этой задачи разобьем отрезок 1е <1< Тна У частейточками 1,<1, «...1, < Ь =Т, и, приняв эти точки в качестве узловых, интеграл в (1) заменим квадратурной формулой прямоугольников, уравнения (2) — разностными уравнениями с помощью явной схемы Эйлера [4, 13, 20, 39, 54]. В результате придем к следующей дискретной аадаче схима киллиана 491 оптимального управления н — г 7э (х; [и~),) = ~ Р~ (хь и;) + Ф (хн) -~ ш1, (5) ь=а хьы Г,(хь и,), 1 О, 1, ..., У-1, х,=хж6„(6) (7) [иД, (и„ ио ..., и„,): и~ж Уе 1 = О, 1, ..., Ж вЂ” 1, (8) где Р[(х, и) = )э (х, и, З;) (С;+, — ХД, Р,(х, и) = х+ 7(х, и, й) Х Х (й+, — й<), С, = С (й), У, У (й). Заметим, что задача (5) — (8) имеет также и самостоятельный интерес и возникает при описании управляемых дискретных (импульсных) систем, в которые сигналы управления поступают в дискретные моменты времени, фазовые координаты также меняются дискретно [44, 66, 101, 213, 254, 322, 323[.
Если задать какое-либо дискретное управление [и,),=(и„ ио ..., и„,) и начальное условие х, х~и С„то система (6) однозначно определяет соответствующую дискретную траекторию [х[о = [х~(х' [иЬ)[~ =(х„х„..., хз). Зафиксируем некоторое хж С, и через Л,(х) обозначим множество управлений [и~~ таких, что 1) выполнены условия (8); 2) дискретная траектория [х;)„соответствующая управлению [и4 и выбранному начальному условию х, х, удовлетворяют ограничениям (7). Пару ([и4 [хД,), состоящую из управления и траектории, будем называть допустимой для задачи (5) — (8) или, короче, допустимой парой, если эта пара удовлетворяет всем условиям (6) — (8) или, иначе говоря, [иД,жЛ,(х,). Множество Л,(х) может быть пустым или непустым.
Если Л,(х)= О при всех хай„то условия (6) — (8) несовместны и функция (5) будет определена на пустом множестве. Поэтому, чтобы задача (5) — (8) имела смысл, естественно требовать существование хотя бы одной точки х ж б„для которой Л,(х) Ф И. Обозначим Х, = (х: х ж С„Ь,(х) Ф И). Тогда задача (5) — (8) может быть сформулирована совсем кратко: минимизировать функцию Х,(х, [и;[,) при [и,),~я Ь,(х) (хжХ,).
Положим гэ = 1п1 1о1 ге(х, [паз). ~=хо Рч)а~ао~ю Допустимую пару ([и;]ю [х[],) назовем решением задачи (5)- (8), если 1а(хо~ [п[]о) = 7о [ию]э назовем оптимальным управлением, [х;], — оптимальной траекторией задачи (5) — (8). Как видим, задача (5) — (8) является уже известной нам задачей минимизации функции п +Хг переменных х, ио ио ... ..., и , и для ее решения в принципе могут быть использованы методы, описанные в главах 1 — 3, 5. Однако в практических эа- ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [ГЛ. 7 492 дачах число п+Ут обычно бывает столь большим, что непосред- ственное использование методов глав 1 — 3, 5, вообще говоря, сильно осложняется: вызывает трудности также и то обстоятель- ство, что множества <д,(х), Х„на которых минимиэируется функ- ция 1,(х, [и<),), заданы неявно.
Для преодоления этих трудностей здесь часто пользуются методом динамического программирова- ния, с помощью которого задачу (5) — (8) большого числа пере- менных удается свести к последовательности конечного числа задач минимизации функций меньшего числа переменных. 2. Для изложения метода динамического программирования нам понадобятся следующие вспомогательные задачи: и-1 Х» (х, [и<) д) = Д Р< (х„и<) + Ф (х;,) -+ (п1, (9) <=д х<+, =Р<(х<, и<), 1=й, ..., Ю вЂ” 1, х«н 6„1=й, ..., У, [и,)„(и„, и„+„..., и,): и«н )<„1 й, хд х, (10) (11) ..., У вЂ” 1, (12) где точка х и целое число й фиксированы, х<и 6» (0 <й< (<т' — 1). При й= О отсюда получим исходную задачу (5) — (8). Через Ь»(х) обозначим множество всех управлений [и,)„, удовлетворяющих условиям (12) и таких, что соответствующая ему траектория [х<[д = (х, х, х„+„ ..., х ) из (10) удовлетворяет фазовым ограничениям (11).
Пару ([и<[», [х,),) назовем допустимой парой для задачи (9) — (12), если [и<),<н Ь»(х). Допустимую пару ([и<]д, [х<]д) будем называть решением задачи (9) — (12), если <д(х, [и<]д) =1д(х) = ш1 <д(х, [и<)д); [и;]д назовем оптиА< <Ю мальным управлением, [х;]д — оптимальной траекторией задачи (9) — (12). Нетрудно видеть, что если Х, чь д<, то <д»(х)Ф О хотя бы для одного х <н Сд. Введем функцию Вд (х) = ш1 1» (х, [и<)д), й = О, 1,..., Л' — 1< Ад(Ю хек Хю й = О 1... <<< — 1 (13) называемую фуннуией Бел ана задачи (5) — (8).
Область определения функции В,(х) представляет собой множество Х, = = (хш 6»: Л»(х)Ф 8). Покажем, что функция Беллмана задачи (5) — (8) удовлетворяет некоторым рекуррентным соотношениям, называемым уравнением Белл ана. Теорема 1. Функция Беллмана задачи (5) — (8) необходимо является решением уравнения Вд (х) = 1п1 [Р'„(х, и) + Вд+, (Рд (х, и))], и< И»<в< схкмА веллмлнА где В (х) = Ф (х), х (и С», (14) Р,(х) — множество всех тех и «н )т„, для которых существует хотя бы одно управление [и]„ю Ь,(х) с компонентой и„и. Верно и обратное: функция В,(х), х(вХ„(й= О, 1, ..., У вЂ” 1), определяемая услови ми (13), (14), является функцией Беллмана задачи (5) — (8).
Доказательство проведем в предположении, что все упоминаемые в теореме 1 нижние грани конечны. Необходимость. Пусть В»(х) = ш1 1»(х, [и(]») (х«иХ„, Ь»(х) й = О, 1, ..., Л вЂ” 1); В (х) = Ф(х), х(и 6». Покажем, что зти функции удовлетворяют уравнению (13).
Из определения множеств Л,(х), Р,(х) видно, что множества Р,(х) и Л„(х) оба пусты или непусты одновременно, и поскольку х,+, —— Р„(х, и), то для непустоты зтнх множеств необходимо и достаточно, чтобы Л,+, (Р„(х, и) ) чь )(). Справедливость соотношения (13) при й=У вЂ” 1 очевидным образом вытекает из условия В (х) Ф(х) и представления 1к — д (х, [и;]к,) = Р«к, (х, и) + Ф (Рн ) (х, и)), верного для любого и(иР» ~(х)х Л» ~(х) х(и: и(и )т» „х» =р'»,(х, и)ыб», хжб»-,). Докажем (13) при й (О<й< <У вЂ” 1).
Для етого сначала убедимся в том, что Вь(х)( 1п1 [Рь(х, и)+ В»+,(Р»(х, и))], х~Хю (15) п),(х) Возьмем произвольное и ~и Р,(х) и с зтим управлением «выйдем» из точки х в момент й. В момент й+1 придем в точку х„», = = Р„(х, и), для которой Ьх+, (х,+,) чь а(.
По определению В»+) (х»+)) = 1п1 1»+) (хд+(, [и(]»+)) для любого е > О най- Ь„+,(х„+,) дется управление [и';]»+, ен Ла+, (х„+,) такое, что В„+, (х„+ ) < < 1»+((ха+), [й]»+,) < В»+, (ха+,) + е. Поскольку [и(]» = = (и, и»+„..., йк )) в= Л»(х), то В»(х)<1»(х, [и(]»)=Р»~(х, и)+ + 1»+)(х»+„[й(]»«.г) (Р»(х, и) + В»+,(хд+() + е=Р»~(х, и) + + В»+) (Р» (х, и)) + е.
В силу произвольности и ю Р„(х)' и величины е > О отсюда следует неравенство (15). Теперь покажем, что в (15) на самом деле знак неравенства можно заменить знаком равенства. По определению 1п1 1»(х, Ь),(х) [и(]„) = Ва (х) для каждого е > О найдется такое управление ~~и~] енЬ»(х), что В„(х)<1~(х, [о(]а)<В (х) + е. Но [о(]»+ = (о»+„..., ок,) ен Л»+) (Р» (х, о»)), поэтому Р',(х т4)+В,~,(Р,(х,о',))<Р'„(х 4)+1ь»,(Р,(х,о»), [и,],),) = 1»(х, Я»)<В),(х) + з. двндмичвсков пгоггьммиговднив )гл, т Так как ))~д~Рд(х), то отсюда имеем: 1пЯ~Рдд(х, и) + Вд+з Х »иод(») Х (Рд(х, и))1(Вд(х) + е, или в силу произвольности е)0) 1п1 (Рдд(х, и) + Вд+)(Рд(х, и))~<Вд(х), хе= Хм »и пд)») Отсюда и из (15) немедленно следует равенство (13). Достаточность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
