Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 118
Текст из файла (страница 118)
7 Х,+, и нужное значение Во+,(х,+,) еще не будет вычислено. Коли нсе мы захотим вычислить недостающее значение В,+,(х„+,), то здесь могут понадобиться значения ранее вычисленных функций Во+о(х), ..., Вл(х) в новых дополнительных точках, а для этого в спою очередь придется еще более расширить множества узловых точек в Х„+„Х„+„...
и т. д. На практике в таких случаях недостающее значение В,+,(х) получают с помощью интерполяции по значениям В„+,(х) в близлежащих узловых точках, что, вообще говоря, снижает точность. Заметим также, что принятый выше способ аппроксимации задачи (1) — (4) с помощью разностной задачи (5) — (8) довольно груб, поскольку Опирается на простейший метод ломаных Эйлера для интегрирования дифференциальных уравнений и квадратурную формулу прямоугольников.
В следующем параграфе будет описана схема Моисеева, которая не требует интерполяции и оставляет достаточную свободу при выборе способа аппроксимации задачи (1) — (4). В заключение отметим, что метод динамического программирования относится к классу методов декомпозиции — так нааываются методы минимизации, поаволяющие задачи большой размерности свести к задачам меньшей размерности; о методах декомпозиции см., например, в [111, 117, 194, 203, 242, 302, 320, 330). Упражнения. 1. Найти функцию Беллмана для задачи г»-1 то([и»]о) Х [(а»» х») + З»(и»)]+ (соха») » о х»».» = А»х» + В»(и»), и»»е У», » = О, 1, ..., /С/ — 1, хо = а, где А» — матрица порядка и»с и; В» (и) =(В»т (и), ..., В," (и)), Во» (и), ьо (и)— функции переменной и ш У» те Е", а», с, а — и-мерные векторы, » = О, 1 ...
..., »у — 1. Указ а ни е: функцию Беллмана искать в виде Во(*) =<»йо, х> (а=О, 1,..., /»). 2. Найти функци»о Беллмана для аадачи: !о(й/ = Ф(х») -«шй х»=хо+и, х»»ЕС» (»=О, 1); ишус, где Ф(х) =(1+о»о) ' при хчАО, Ф (О) = 1/2; бо = (х ш Е'. ] х] ( 1/2), 6» = Е»; Уо = (и»н Е'. ] и] ~~ 1). Паковать, что Х, = С„Х» = Е», и убедитьсл, что для этой задачи нижняя грань в (13), (16) не достигается. 3. Пусть функция Во(х) (х »е Хо, й = О, 1, ..., Д») удовлетворяет условиям (13), (14), а функция ио (х)»еда(х) и точки х, »ЕХо (з» = 1, 2, ...) таковы, что Пш (х, и,. (х)) =О, 11ш В (х ) = 1п(В (х). Пусть управление [и» ]о и траектория [х» ]о построены по правилу: ио =во (хо ), хоп=до(хо, ио ), и» =и»„(х»„), ..., хао»/ Ея-»(хо-» оо ии-»,~).
Тогда последовательность пар (хо, [и»а]о) — минимиаирующая для задачи (б) — (8), т. е. 1пп уо (х, [и»,]о) = 1 . )(Оказать. о» о 4. Доказать, что последовательность функций и» (х) (» = О, 1, ..., »У — 1, »и = 1, 2, ...) из упражнения 3 дает приближенное решение проблемы синтеаа для задачи (б) — (8), т. е. если в момент Ь система находится в точке хо=а»еХо, то движение по закону х»+»,,„=Е»(х»ао и»,„(х»,„)) (»=й, ... СХЕМА МОИСЕЕВА 505 ..., У вЂ” Ц; х»»»=х (»и 1, 2, ...), при больших т доставляет функцнн 1»(х, [и»)») значения, близкие к 1,.
5. Для задачи (9) — (12) получить оценку погрешности, аналогичную оценке (28). 6. Вывести уравнения Беллмана и докааать теоремы, аналогичные теоремам 1 — 4 для задачи: 1 (х, [и»[ ) = ~~~~ Ре» (х», и») + Ф (х ) + Ф (х „) -». 1п1, х»+» = Р»(х», и,), » = О, 1, ..., У вЂ” 1, х» »н 6», и» »и У», 1 = О, 1, ..., У, где х» = (х», ..., х»), Р = (Р», ..., Р»»), и. = (и[, ..., ии); множества 6»»жк", У» — е' (» =О, 1,..., У) заданы; функцииР»(х, и) определены при х»н 6»» и ш У» (» = О, 1, ..., У, 1 = О, 1, ..., и); функции Ф»(х), Ф»(х) определены при х»н Оь х ш 6и соответственно; » — дискретное время; момент У считается заданным.
7. Обобщить оценку (28) н теоремы 5, 6 для аадачи иэ упражнения 6. 8. Пусть в задаче (5) — (8) Ре»(х, и) и»0 (» О, 1, ..., У вЂ” 1). Показать, что тогда В»(х) = Ф(х) для всех й = О, 1, ..., У, причем функции В»(х) при различных й отличаются друг от друга областями своего определения Х». 9. Применить метод динамического программирования к задаче минимизации функции н-1 1.
(и., иы ". ин) - .'". 1»(и»"»+1)+ун(ин) » о при условиях и»»н У» (1=0, 1...„У). Указание: ввести функцию ! и-т В„(и) = 1п1 ~ ~з~ 1» (и», и»+ ) +»н(ин) где нижняя грань берется по всем наборам (иа = и, и»+и ..., ин), и» ш У» (» й,..., У) и показать, что Ва(и) = 1п1 [1а(и, и) +Ва+ (о)[ (й=» »ыга+» - О, 1, ..., У вЂ” П; В„(и) = 1„(и). 9 2.
Схема Моисеева 1. По-прежнему будем рассматривать задачу (1 1) — (1.4). Для приближенного решения атой задачи, как н раньше, разобьем отревок 1»<1<Т на Л частей точками 1,<1»<... ...<1, < 1х Т. На множестве»х» С(1») возьмем некоторую дискретную сетку точек хо»н»х„следуя [14, 217[ множество всех точек выбранной сетки будем называть шкалой состояний н обозначать через Н» (1 О, 1, ..., »(1). Шкалы состояний Н, н Н+, будем называть соседними. На двух соседних шкалах Н» н Н,+, возьмем точки х азН, н р»нН»»» и рассмотрим следующую ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ (ГЛ. 7 вспомогательную задачу: »(+, Х»(х,у,и( )) = )» )э(х(д),и(7),»)»11-+-шХ, (1) »» х(7) = ~(х(8), и(8), г), г»»= Ф ~ ц+», 'х(7») = х» х(7»+») = у, (2) х(8)»е 6(8), й ~ г 7»+„(3) и =и( ° ) кусочно-непрерывна и и(Ф)»н У(1) при й ~ 7 (1»+».
(4) Следуя (12, 217), задачу (1) — (4) будем называть элементарной операцией, соединяющей точки л и у. Через дд»(х, р) обоаначим множество всех управлений и=и( ) из (4), для которых соответствующая траектория х( ) удовлетворяет всем условиям (2), (3). Положим М;(х,у) = ш1 У((х,р,и); если(д»(х,у)=)»), х=А (х,з) то М»(х, р) = по определению. Пусть все точки всех соседних шкал попарно соединены элементарными операциями. Если ш1 »'» (х, у, и) достигается на А»(х,р) некотором управлении н»( )»н Ь»(х, у) н соответствующей траектории х»(.), то величина г»-д М((хп,, х»+д...) + Ф(е)7),.
) (5) »=о выражает собой значение исходной функции (1Л) на управлении и = и (7) = и» (7) (д» < 7 ( й+„д = О, 1, ..., »)» — 1) и соответствующей траектории х(7, и) = е»(7) (й ~ 7 ~ 7»+„д = — О, 1, ..., У вЂ” 1); х(7) = хм, при соблюдении всех ограничений (1.2) — (1.4). Поэтому исходную задачу (1Л) — (1.4) естественно аппроксимировать задачей отыскания минимума суммы (5) по всевозможньдм ~абоРам то~ек (ЕМ»» лддд» .» е)7))7)» х»)»~ »(е Н» (д = О, 1, ..., ()»). Такая аппроксимация задачи (1.1) — (1.4) имеет смысл, конечно, и в том случае, когда 1П1 У»(х,у,и) не достигается при А((х,г) каких-либо х, р, й Очевидно, приведенная аппроксимация задачи (1Л) — (1.4) более гибкая и лучше приспособлена для приближенного решения этой задачи, чем схема из 3 1, ибо здесь представляется свобода в выборе способа разрешения элементарной операции (1) — (4), и кроме того, рассмотрение лишь таких траекторий, концы которых лежат в иавестных точках соседних шкал, избавляет нас от необходимости интерполирования.
Па способах разрешения элементарной операции мы останевимся ниже. Описанная аппроксимация задачи (1Л) — (1.4) имеет простой геометрический смысл. А именно, траекторию х»(7) из (2), СХЕМА МОИСЕЕВА 507 на которой достигается ш1 Х» (х, у, и), назовем дугой, соедиАд<»,Ю няющей точки х, у, а числа М,(х, р) — длиной атой дуги, 1 = О, 1, ..., 1Ч вЂ” 1.
Дуги, последовательно соединяющие пары точек хп„хд+,... соседних шкал Н„ХХ,+, (1=0, 1, ..., 111 — 1) назовем путем, соединяющим шкалы Н, и Н» и проходящим через точки х«;,, хп„...,хкдл, и в качестве его длины примем величину (5). Тогда наша задача сведется к отысканию кратчайшего пути, соединяющего шкалы Н, и Н». 2. Обозначим где нижняя грань берется по всем наборам точек (хы„= х, х~,.«1,,„„,,...,Хед, ), хп,.
ее ХХ; (1= й,...,11'). Иначе говоря, С«(х) выражает собой кратчайшее расстояние между фиксированной точкой х жН, и шкалой Н». Покажем, что функции С„(х) удовлетворяют следующим рекуррентным соотношениям: й = О, 1, ..., Н вЂ” 1; Сь(х) = 1ЕХ (МА(х,у) + С««.1(у)), З яд+1 Ск (х) = — Ф (х), (6) аналогичным условиям (113), (114). Справедливость (6) при й = 1«' — 1 следует из определения С»,(х), С»(х). Докажем (6) при других й (О ~ й ~ 1«' — 1). Для этого сначала убедимся в том что СА(х)~ (1ЕХ (МА(х,у) + С««.д(У)), х~ Н« (7) РНН«+1 Возьмем произвольное ужН«+1. По определению С,+,(у) для любого з > О найдется путь, соединяющий точку у со шкалой Н, длина которого не превышает С,+,(у)+ з.
Если этот путь «удлинить», добавив к нему дугу, соединяющую точки х и у, то получим путь, соединяющий точку х ди Н„со шкалой Н», длина которого не превышает М„(х, у)+С„+,(у)+ з. Поэтому заведомо С„(х)< ЛХ,(х, у)+ С,+,(у)+ з. В силу произвольности точки у«ЕН,+, и величины е отсюда имеем неравенство (7). Теперь покажем, что в (7) на самом деле знак неравенства можно заменить знаком равенства. По определению С,(х) для любого з > О найдется путь, соединяющий точку х1ЕН« со шкалой Н», длина которого не превосходит С,(х)+ з.
Пусть этот путь проходит через точку у,дя Н„,. Ясно, что отрезок этого пути от у, до Н» не меньше С«+,(у,), и поэтому весь путь от х до Н„не меньше М„(х, у,)+ С,+, (у,). Следовательно, Мд(х, у,)+ С«+1(у,) < Сд(х)+ з. Так как у, дк Й.«э то отсюда име- ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [гл. 1 воз ем ш1 (Мд(х,у)+ Сд+,(у))(С»(х)+ е, или в силу произуннд+» вольности е: дв1 (Мд (х, у) + Сд+, (у)) ( С» (х). Сравнивая РнН»-~-» это неравенство с (7), немедленно получаем требуемые соотношения (6). 3. Соотношения (6) могут быть использованы так же, как и уравнение Беллмана (1 18), (1.14).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
