Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 116
Текст из файла (страница 116)
Пусть функции Вд(х) (хшХд, й *О, 1, ..., Ж вЂ” 1), определены из условий (13), (14). Спрашивается: какое отношение имеют зти функции к задаче (5) — (8)? Покажем, что при каждом хж Хд величина В,(х) равна нижней грани функции (9) при условиях (10) — (12). Отметим, что условия (13), (14) однозначно определяют функции Вд(х) (х ~в шХм й О, 1, ..., У). Это легко доказывается с помощью индукции последовательным перебором в (13), (14) номеров й = Л, К вЂ” 1, ..., 0 с учетом того, что функции Ф(х), Рд(х,и), Рд(х, и) однозначны и нижняя грань функций определяется также однозначно.
С другой стороны, как было установлено выше, функции ш( 1д(х, (и<]д) (хам Хд), также являются решением уравнения Ьд)») (13) при условии (14). Из единственности решения системы (13), (14) тогда следует, что Вд(х) = 1п( 1д(х, [и)]д) (х~вХ„ ьд(») й = О, 1, ..., ]т' — 1). Теорема 1 доказана. 3. Пользуясь условиями (13), (14), можно последовательно определить функции В„(х) и их области определения Х„(й= У, Л) — 1, ..., 1; 0). А именно В„(х) Ф(х), хаву» Хд— известны.
Если известны В,+,(х) и Х„+, (й~У-1), то для определения В„(х) нужно решить задачу минимизации функции )Р(х, и)=Р»д(х, и)+Вд+д(Рд(х, и)) пеРеменных и=(и', ..., и') на известном множестве Р„(х) (и: иж '»д, Рд(х, и)шХ,+,). Здесь могут быть использованы методы глав 1 — 3, 5. Очевидно, функция Вд(х) определена в точке х тогда и только тогда, когда Рд(х)чь И. Таким образом, при определении значений функции В„(х) одновременно находится и область ев определения Х, (х: хшбд, Рд(х)Ф»)) (х: хжб», Ьд(х)чьо). Так как Лд(х)чь 'Ф'Я) хотя бы при одном хшб„то Хдчь)З) (й У, У вЂ” 1, ... ,1,0).
Предположим, что нам удалось найти функции В,(х) из условий (13), (14) и, кроме того, пусть также известны функции ид(х)шР„(х) (хаХд, й О, 1, ..., У вЂ” 1), на которых достигается нижняя грань в правой части (13). Тогда, оказывается, решения задач (5) — (8) и (9) — (12) выписываются совсем г ° ) просто. А именно, оптимальное управление (и;1з и соотввтст- СХВМА ВВЛЛМАНА 495 вующая траектория [х» »з для задачи (5) — (8) определяются следующим образом: сначала из условия Ы В,(х) = В,(хе) (16) в~хе находят х, ен Х„затем последовательно полагают Е Е е Е Е Е Е1 и, = и (хе), х, = Р,(х„ие), и, = и,(х,), х, = Р, (х», и,), ..., хн = Рк 1(хь-», ик у. Е1 Г Е» Оптимальное управление [и»»А и траектория [х»»А длн задачи (9) — (12) определяются аналогично: е е е (18) хь=х, из=из хА), хА+, — — РА(х'„, и„'),..., хк = Рк 1(хк „ик 1). Для доказательства этих утверждений введем вспомогательные функции: Л»(х, и)=В»+,(Р»(х, и)) — В»(х)+ Ре»(х, и), » = О, 1, ..., »т — 1„ (19) Очевидно, уравнения Беллмана (13) тогда можно переписать в эквивалентном виде: 1в1 ЛА (х, и) =— ЛА (х, иА (х)) = О, й = О, 1,....
Л» — 1. (20) еЯОА»е) кроме того, с помощью функций л,(х, и) значение фун»щии (9) на любом управлении [и»)»юй»(х) и х»нХА можно выра- вить формулой К-1 11(х, [и»)А) = ~ Л»(х», и») + ВА(х) (21) » А при всех»» = О, 1,..., М вЂ” 1. В самом деле, учитывая равенство К вЂ” 1 и — 1 Вн(х)=»о(х), из (10), (19) имеем ~ Л»(хьи»)= ~ [В»+1(х»+1)— » А» А К вЂ” 1 — В. (х ) + Р»е (х», и ) [ = Вк (хк) — ВА (х) + ~л~~ ~Ре» (х», и») = гз (х» [и»[А) — ВА(х), что равносильно (21). Теорема 2. Пусть найдены функции Ве(х) ив (13), (14) и их области определения Х„, а также функции и и,(х) (х»и Хь й =О, 1, ..., »г'-1), на которых достигается нижняя срань в уравнении (13) или (20), и пусть хе определена условием (16). Тогда оптимальное управление [й»»е и траектория [х»)е для задачи (5) — (8) определяются соотношениями (16), (17).
ДИНАМИЧИСКОИ ПРОГРАММИРОВАНИИ »гл. т Доказательство. Из определения и(х), [и»)г, [х»]г и эквивалентности записей уравнения Веллмана (13) и (20) имеем В»(х», и»)=В»(х;, и»(х»)) = Ы В»(х», и) =0 х» Р (х*) »' = О, 1г..., А» — 1. (22) Возьмем произвольные х»ИХ,; управление [и»),»ИЛ,(х) с соответствующей траекторией [х»[, из (6). Так как и»ыП»(х»), то иа уравнения (20) и определения и»(х) следует В»(х;, и»)) ЕИЕ В;(хь и) =В»(хь и»(х»)) = О, хиР»(х;) » = О, 1,..., Аг — 1. (23) С помощью формулы (21) при й = 0 с учетом соотношений (16), и — 1 (22), (23) получаем 1,(х, [и»)г) — 1,(х,'„[и»]г) = ~ [В»(хь и»)— »=е — В»(х, и»)] +В (х) — В,(х,')>О для любых хыХ, и [и»),»и азу,(х), что и требовалось.
Теорема 3. Пусть известны В„(х) (х»иХ„) ив (13), (14), а также Функции и,(х), на которых достигается нижняя грань в уравнении (13) (или (20) ) . Тогда оптимальное управление [и» ]ь и траектория [х»]ь для задачи (9) — (12) определяются Формулами (18). Д о к а з а т е л ь с т в о. Воаьмем произвольное управление [и»[ь»и Л»(х) и соответствующую траекторию [х»)„из (10). Очевидно, соотношения (22), (23) остаются справедливыми и здесь при всех» = й, ..., А» — 1. Отсюда с помощью (21) получим Ж-» 1ь (х, [и»]А) — 1А (х, [и» ]„) = ~ [В, (х», и») — В» (х*;, и» )] ~) О, что и требовалось. 4. В теории оптимального управления и ее приложениях важное место занимает так называемая проблез»а синтеза, заключающаяся в построении функции и = и,(х), выражающей собой оптимальное управление при условии, что в момент й объект находится в точке х фазового пространства.
Такая функция и„(х) называется синтезирующей. Теорема 3 показывает, что решение уравнения Веллмана (13) равносильно решению проблемы синтеза для задачи (5) (8). А именно, функция и„(х), на которой достигается нижняя грань в (13), является синтезирующей: если в момент й объект находится в точке х»ИХ„то дальнейшее оптимальное движение объекта определяется условиями: х»+, Р»(х», и»(х»)) (1 Й, ... ..., А» — 1), х„х (если хФХм то Л„(х) и,— движение с со- СХЕМА ВЕЛЛМАНА блюдением условий (10) — (12) невозможно). Достаточные условия существования функции Белл мана и синтезирующей функции для задачи (5) — (8) даются в следующей теореме. Теорема 4.
Пусть з)ножгства 6» (й О, 1, ..., У) замкнуты, множества т» (й О, 1, ..., Л) — 1) замкнуты и ограничгны, функция Рг»(х, и) полунвпргрывна снизу, а Яункция Р„(х, и) непрерывна по совокупности аргументов (х, и) при х ~а б„и~и 'т» (й = О, 1, ..., Л- 1), Ф(х) полунвпргрывна снизу на множестве )»». Тогда: 1) множества Х» (й О, 1, ..., Ж) зал)кнуты, множвства Р„(х) (й О, 1, ..., У- 1) заз»кнуты и ограничены равномерно по х»пХ»; 2) нижняя грань в правой части (13) достигастся хотя бы при одном и=а»(х)вгР»(х); 3) сдункция В»(х) полунсиргрывна снизу на Х» (й= О, 1,...,У).
Доказательство. По условию С» Х„замкнуто, Ф(х) В„(х) полунепрерывна снизу на Х». Сделаем индуктивное предположение: пусть Х„+, замкнуто, В„+, (х) полунепрерывна снизу на Х„+, при некотором й (0»й()т' — 1). Докажем, что тогда Х„замкнуто и на Х, справедливы все утверждения теоремы, Так как Р,(х)= (гк ива т», Р,(х, и)с» Х»+,) а т» и )т» ограничено, то Р,(х) ограничено равномерно по хсгХ». Докажем замкнутость Р„(х) при любом фиксированном хиз Х„. Пусть ь =Р„(х) (т= 1, 2, ..., и - и) при ж- . Это значит, что о ы т'», Р»(х, и )ыХ»+, ()п=1, 2, ...). Из замкнутости Х„+, и непрерывности Р„(х, и) сразу имеем: о»и т'», Пш Р»(х, зй ао и,„) = Р»(х, и) е Х»+тл т.
е. и вг Р»(х). Замкнутость Р„(х) доказана. Покажем замкнутость Х» (и: хы0», Р»(х)чь)д). Пусть у„»и ыХ» (и» 1, 2, ...), у — у при и»- ь. Из замкнутости 6» следует уши». Если мы еще покажем, что Р»(у)чь И, то это будет означать, что ушХ», и замкнутость Х, будет доказана. Так как Р,(у )ч»8, то существует такое и ы )т„что Р„(у„, о„)шХ,+, (тл 1, 2, ...). В силу компактности ))„из последовательности (о ) можно выбрать подпоследовательность [о )-+рену» при р- . Поскольку Х,+, замкнуто, Р,(х, и) непрерывна, то Пш Р»(у, о )=Р»(у,о)яХ»+и т. е.
ивгР (у). Р1 Таким образом, Р»(у)чья). Далее, функция ф (х, и) = Р'„(х, и) + В»+, (Р» (х, и)) полу- непрерывна снизу по (х, и) при хегХ», нвгР„(х) — это следует из непрерывности Р»(х, и) и полунепрерывиости снизу Рг»(х, и), В,+,(х). Поскольку Р»(х) — замкнутое ограниченное множество, то в силу теоремы 2 1.1 ф(х, и) при каждом фиксированном х~-= ы Х, достигает своей нижней грани на Р„(х) хотя бы в одной точке и=и»(х)сгР»(х). Таким образом, В»(х)= (п1 ф(х, и) = »еР»(х) ф(х,и„(х) ), в силу уравнения Беллмана (13).
ДИНАМИЧЕСКОН ПРОГРАММИРОВАНИИ 1гл. 1 Остается еще доказать полунепрерывность снизу В„(х) на Хо. ПУсть х, У овХо, У вЂ” х пРи т- оо,Во(У„)=1Р(Ухо ио(У„)). Так как илу )окР,(у )ов Уо, то в силу компактности Уо последовательность (ио(у ), т 1, 2, ...) имеет хотя бы одну преДельнУю точкУ Ров Уо. Можем считать, что сама послеДовательность (и„(у,„)1- и при т - . Поскольку Р„(х, и) непрерывна, Х,+, замкнуто, кроме того, Р„(у, ио(у ))он Хо+„то 11ш РА(у, % ~00 РА (у,„)) = РА (у, Р) еи Хо+1. Это значит, что Р ш Р„(х) .
Тогда 1пп ВА(у ) = 11ш ор(у,ио(у )))<р(х,и)) 1п1 <р(х,и) =Во(х). щ-~ар о -~~ хань(х) Полунепрерызность В,(х) на Х„доказана, что и требовалось. 5. Нетрудно привести примеры задач типа (5) — (8), когда нижняя грань в (13) или (16) не достигается (см. ниже упражнение 2). В таких задачах, конечно, приходится пользоваться величинами, лишь приближенно реализующими нижнюю грань в (13), (16). Но даже в том случае, когда нижняя грань в (13), (16) достигается, получить точные выражения для функций В„(х), и„(х) и точки х, иэ (13), (16) часто бывает затруднительно.
Поэтому на практике часто пользуются соотношениями (16), (17) для приближенных Во(х), и„(х) и вместо оЗ г оо точных УпРавлений (ио1о и тРаектоРии [х11о полУчают какие-то их приближения. Возникает вопрос, насколько отличается полученное таким образом приближенное решение задачи (5) — (8) от ее точного решенияр Приводимая ниже оценка погрешности дает некоторый ответ на этот вопрос. Пусть Ко(х) — приближенное значение функции Беллмана В,(х) (1=0, 1, ..., Ж).
По аналогии с (19) введем функцию Юо(х,и) =Ко+1(Р1(х, и)) — Ко(х) + Роо(х,и), 1 = 0,1, ...,1у — 1, (24) и, кроме того, положим эх(х)= Ф(х) — Кх(х), х он бх. (25) Возьмем произвольную допустимую пару [иЬ (ио, ии ..., их-о), [хо)о (х„х„..., хх 1) задачи (5) — (8). Тогда х, ов Х„[и4 ои онЬо(хо), и,шР1(х~) (1 О, 1, ..., 11' — 1). Учитывая условие (6), из (24) имеем 81(хо, ио) = Ко+1(хо+1) — Ко (хо) + Роо (х;, ио), Е = О, 1, ..., 11' — 1. Суммируя эти равенства по 1 от 0 до 11' — 1, с помощью (25) получим формулу к-1 Уо (хо [ио) о) = Х 81 (хо~ ио) + эл (хк) + Ко (хо) ° (26) 1 схима ввллмань Если К,(х)=В,(х), то гг(х) О, и формула (26) превратится в знакомую нам формулу (21) при й = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
