Пупков К.В. Методы классической и современной теории автоматического управления. Том 2 (2000) (1095389), страница 103
Текст из файла (страница 103)
Рассмотрим еше несколько функционалов. Пусть качество многошагового процесса принятия решений (4.2) оценивается функционалом 542 Методы тео ии оптимального п авленид. Часть П! Пусть, например, к началу четырехлетнего производственного процесса имеется оборудование, возраст которого три года. Максимальный доход, которыЯ можно получить от производственного процесса, равен 6 (7 (3) = 6 ) Оптимальная стратегия, которая обеспечивает этот доход, не является однозначной, а имеет слелуюшие варианты Все три варианта оптимальной стратегии эквивалентны межау собой, если интересоваться только четырехлетним производственным процессом, т к они обеспечивают один и тот же доход равный 4 Однако они не эквивалентны, если принимать во внимание состояние оборудования в конце производственного процесса В первом варианте по окончанию производственного процесса оборудование имеет возраст 3 года, во втором - 4 года, в третьем - 2 гола Пример 4.2.
Крашчайшие луши через сети [4) Рассмотрим сеть, состоящую из Н узлов, занумерованных 1,2,,6( и взаимосвязанных звеньев. Обозначим га (га >О) время прохожаения звена (ы) Будем решать задачу о нахождении пути через сеть, который соединяет два зааанных узла и время движения вдоль которою минимально. Данная задача имеет важное значение при выборе маршругов движения автомобилей, самолетов по транспортным сетям, передачи сообщений по сетям связи и т п Числа га могут необязательно означать время прохождения звена (гы), а, например, задавать расход топлива Пусть конечным узлом, с которым следует соединить начальный узел, является узел Ф.
В соответствии с формализмом динамического программирования в качестве начальных узлол необходимо рассматривать все узлы сети Обозначим л, время перевода системы из узла г в узел У по кратчайшему пути (г = 1, 2,, )У-!). Принцип оптимальности Беллмана приводит к функциональному уравнению ! и, =ш(п)Г, еи 2, 1=1,2,,3( — 1, / (4 17) и„=о Покажем, что уравнение (4 17) имеет единственное решение Пусть лн и, и„и Ин((з,...,((л — два различных решения уравнения (4 17).
Пусть, дюее, т является индексам, для которого разность (7 — и достигает максимального значения. Покажем, что эта разность равна нулю В соответствии с (4.17) запишем (г =г +((„, л =г„, ьл,. Очевидно, г„, +(г, >г„„+((„. Тогда из соотношений ()„кг, ь((„ и„= г„, + и, следует неравенство и„- „ки,— и,. Поскольку для индекса т ршность ΄— и„достигает максимального значения, поэтому причем г и м Далее, рассмотрев разность ((, -и,, подобным образом найлем узел з(з и ж,ли г), ляя которого гг -» =гг -и =11 -ь Глава 4.
инамическое п о амми ование 543 Поскольку число узлов конечно, то, перебрав все узлы, окончательно получим и.— „=и„-,=о Полученное равенство доказывает единственность решения уравнения (4 17) Остановимся теперь на численном решении уравнения (4!7) Воспользуемся методом последовательных приближений В качестве начального приближения л,", ~ = 11, й, положим и,"=гш, 1=),дг-), г =О, что соответствует времени прохождения звена (Ьи), те непосредственному переводу из узла ~ в узел Ф (минуя другие узлы) Если звено (л )У) отсутствует или вообще отсутствует какое-либо звено (су), то можно в качестве г,л(гв) взять подходящее большое число Таким обраюм удастся очень просто решить трудные вопросы связей между узлами. Следующее приближение получим по формуле и,' = ш(п [гк + и,"~, ~ = 1, Ф вЂ” 1, и,', = О (4 18) Предусмотренную равенством (4 18) минимизацию следует выполнять путем непосредственного сравнения встречающихся сумм, что быстро выполняется на ЭВМ Переход от Вго приближения к Ь-1 осуществляется с помощью соотношений изы =пцп[г, +и,"~, ! = 1,)т'-1, иь,' =0 Рассмотренный алгоритм имеет простую физическую интерпретацию.
Величина и,' соответствуег времени перехода непосредственно из узла г в узел У, минуя другие узлы Величина и,' задает минималь- нос время перехода из узла ! в узел У при наличии не более одного промежуточною узлж величина и'— при наличии не более двух промежугочных узлов и т д Из этой интерпретации следует, что последовательные приближения приводят к монотонному убыванию величины и'(1 = 1, У), т е Они,' 5и,, что гарантирует сходимость последовательных приближений 4.3.
МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ НЕПРЕРЫВНЫХ СИСТЕМ Рассмотрим применение динамического программирования для решения задачи оптимального управления. 4.3.1. АВТОНОМНАЯ СИСТЕМА Пусть движение обьекта задается системой уравнений с(т, — ' = /, (х1,хы...,х„,и),из,...,им ),! =1,п, или в векторной форме уравнением — =Г(х,н), д(х Й здесь х =(х,,...,х„) — и-мерный вектор состояния, н =(иы...,и ) — ш-мерный вектор управления, Г=Я,..., Г'„) — п-мерный вектор.
Предполагается, что вектор н может принимать свои значения из некоторого множества У, т.е. н(1) н(7. В качестве ми- нимизируемого будем рассматривать функционал г .l =10(х,н)с(1. (4.20) о В рассматриваемой задаче полагаем фиксированным начальное состояние, кото- рое будем обозначать через х и конечное состояние х . Время перехода нз начального состояния в конечное не фиксируется. Так как целью оптимизации является получе- 544 Методы тео ииоптимального п авления.
Часть Ш ние оптимальной синтезируюшей функции (оптимальной стратегии), то начальной точкой х может быть любая точка фазового пространства. Минимальное значение функционала (4.20) однозначно определяется начальным значением вектора х. Обозначим минимальное значение функционала Я(х) = Я(х,,хз,...,х„) . Пусть х(~), 0 < г < Т вЂ” оптимальная траектория, переводяшая фазовую точку из начального положения х(0) = х в конечную точку х .
Тогда г Я(х) = пйп ) б(х(г),и(г))с(ь .() и о Представим функционал в виде г ь г (б(х(г),и(г))ьз = (б(х(г),и(г))г(г+ (б(х(г),и(г))ьь о о ь Будем предполагать. Оптимальное управление и(Г) кусочно-непрерывно. Условимся за значения управления в точках разрыва принимать пределы справа.
Пусть в интервале (О,Ь) выбрано некоторое управление и(г), а в дальнейшем в соответствии с принципом оптимальности выбирается оптимальное управление. Тогда )б(х(г),и(г))й =б(х(Л)). ь В силу непрерывности траектории х(Г) х(Л)=х(0)+х(0) А+о(Ь), где 1пп — = О. о(Л) ь-о Л Принимая во внимание уравнение (4.19), можно записать х(гь) = х+$'(х,и)1 А+о(Л), или х(Л) = х+з(х,и) А+о(Ь), здесь и — значение управления в момент г = О. Таким образом, г ) б(х(г),и(г))И = Я(х+г(х,и) А+о(Л)).
ь Далее, ь ) б(х(г),и(г))иг =б(х,и) й+оЯ. о Если в начальный момент г = 0 выбрано управление и и б, а в дальнейшем в соответствии с принципом оптимальности выбиралось оптимальное управление, то функционал принимает значение б(х,и) А+о(Л)+о(х+Г(х,и) Ь+о(Л)).
(4.21) Для оптимизации функционала надо минимизировать выражение (4.21). Таким образом, ь(х)=ш!п(б(х,и) Ь+о(Л)+Я(х+г(х,и).А+о(Л))). (422) Глава 4. Динамическое п о амму рвание 545 Будем предполагать, что функция Я(х) имеет непрерывные частные производные по всем своим аргументам. Отметим, что справедливость всего последующего вывода зависит от того, выполняется это предположение или нет. Заранее функция Я(х) неизвестна и проверить справедливость этого предположения по уравнениям движения нельзя. Можно решить задачу и определить функцию Я(х) . Если она окажется непрерывно дифференцируемой, то приводимые ниже результаты являются справедливыми. Однако имеют место случаи, когда функция Б(х) не является непрерывно дифференцируемой. Поскольку функция Я(х) предполагается непрерывно дифференцируемой, то Я(х+Г(х,п) А+о(Л))=Б(х)+ — Г(х,и) Л+ —.о(Л), гГБ аБ дх с(х здесь в соответствии с правилами дифференцирования скалярной функции по векторному аргументу — матрица-строка.
Из (4.22) находим Я(х) =пйп б(х,ц) А+Я(х)»- — Г(х,и).Л»-о(Ь) Ж ННУ Их или О =пил с (х,п)+ — Г(х,п) А+о(Л). дБ .и ' Ых (4.23) Поделим неравенство (4.23) на Ь и перейдем к пределу при Л -+ ьь. В результате получим О=ш1п~б(х,и)+ — Г(х,и) . нно 'Ь ах (4.24) уравнение Беллмана принимает вид НГБ -(=ш(п — Г(х,ц), нну»Гх (4.26) здесь функция Я(х) задает минимально возможное время движения от точки х до точки х .
Для уравнения в частных производных (4.26) граничное условие по- прежнему задается равенством (4.25). Решая уравнение в частных производных (4.24), наряду с функцией Б(х), задающей в зависимости от начальной точки х минимальное значение функционала, определяется таклсе функция н(х), которая задает оптимальную стратегию, или оптимальную синтезирующую функцию. Равенство (4.24) является функциональным уравнением Беллмана. К уравнению (4.24) необходимо присоединить граничное условие Б(х')= О.
(4.25) В частном случае, когда оптимизируется время движения, т.е. г 546 Методы тес ии оптимального п авления. Часть!П Уравнение Беллмана (4.24) задает необхог) имое условие минимума. Именно, если функция Б(к) является непрерывно дифференцируемой по всем своим переменным, то она удовлетворяет уравнению Беллмана (4.24). Пример 4л. Рассмотрим объект, движение которого задается уравнениями г(т1 с'.хг хг' и' г(г си В качестве конечной точки х' выберем начало координат, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
