Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 117
Текст из файла (страница 117)
Предположим, что каким-либо обрааом (например, из соотношений (16), (17) с приближенными функциями В„(х), ио(х) ), нам удалось найти некоторое управление [й<], и соответствующую ему траекторию [х<[<, удовлетворяющую условиям (6) — (8), т. е. х<~Х< [й<)о<нйо(х<), й<ыР<(х<) (<=О< 1 ° ° ., )(( 1) ° Согласно (26) тогда л-1 1о(хо, ~и(1о) = 2, 8<(х<,п<)+ гл(хя)+ Ко(хо).
<=о Отсюда и иэ (26) имеем 1о (х, [в<[о) — 1, (х„[и<[о) = я-< = ~ [Я< (х<, и<) — Ю<(х« и<)[ +гл(хк) — гл(хл)+Ко(хо) Ко(хо) (27) для любых хо <и Хо [в<)в <н Ло(хо) ° Учитывая, что хо хо ои Хо [й<[« н Ло(хо), [и<)« и <)о(хо), (х<, и,)<и Х<ХР<(х<), перейдем к нижней грани по (х„[и<)о) сначала в правой части (27), а затем в левой части (27). Получим неравенства 0(1о(хо, [(«[о) — 1о:< Д', [Я< (х<, («) — ЕпЕ ЕпЕ Я<(х, и)~ + (=о [ оол( ион<(о) + г„(х)о) — шЕ гл (х) + Ко (хо) — шЕ Ко (х)о (28) ля ла представляющие собой оценку погрешности, которая будет допущена, если [й<[о, [х<) будут взяты в качестве приближенного решения задачи (5) — (8).
Если К,(х)=В<(х) ()=О, 1, ..., <о), то В<(х, и) Л<(х, и), гг(х)=0. Кроме того, из (20) следует, что шЕг)[Л<(х,и)=0 иеп<(х) для всех хюХь тан что Еп1 шЕ В<(х,и) = О. Поэтому при х< иап<(о) К,(х)= В<(х) иа (28) получим и-2 0(<1о(хо< [и<[о) — 1о(~ Х В<(х< («) + о(хо) шЕВо(х). (29) (-о ло Из оценки (29) следует, что если определить В<(х)<и Л<(х), х, <иХ, так, чтобы В,(х, й<(х)) было поближе к шЕ Л<(х,и) = авеп<(о) О, х<-=Х», а В (хо) — поближе к шЕВо(х), и затем строить ло ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ~ГЛ. 7 управление [й») и траекторию [У<) следующим образом: Йе Йе(У<) х< =)те(У<< йо)» и< = й<(х<) ..., х» = =р -<(у -< й -<) то и величина 1,(х„[и;),) — 1е будет небольшой.
Заметим, что поскольку на практике конструктивное описание множеств Х<, Р<(х) часто отсутствует, то в правой части оценки (28) вместо Хь Р<(х) часто берут б< и т'» соответственно — такая замена, очевидно, может привести лишь к увеличению правой части (28). В результате получим достаточно удобную апостериорную оценку погрешности н-е 0 ( 1, (хо, [и<[о) — 1 ( ~~.", [ Я< (х<, и;) — ш1 ш1 Я (х, и)] + <=о [ »по< имк» + гн(хь<) — ш(гн(х) + К (х ) — 1П1Ко(х).
(30) ок ое Конечно, прн пользовании оценкой (30) надо помнить, что если правые части оценок (28), (30) отличаются намного, то оценка (30) может оказаться слишком грубой. 6. Оценка (28) полезна также и тем, что она укааывает пути получения достаточных условий оптимальности для задачи (5) — (8). Теорема 5. Для того чтобы управление [й), и траектория [У<)е, удовлетворяющие условиям (6) — (8), были решением задачи (5) — (8), достаточно, чтобы существовала функция К<(х) (< = О, 1, ..., <е') такая, что 8<(х<,и<) = ш1 1П1 Я;(хои) =Я<ш<„о 1 = 0,1,...,»е' — 1, (31) »ах< иио«и< гк(хн) = 1п1гк(х) = гк»<ье~ "Ко(хо) = 1П1»о (х) = Кое«п< (32) хн хо еде функции Я<(х, и), г <(х) определяются формулами (24), (25).
Доказательство следует из того, что при выполнении условий (31), (32) правая часть оценки (28) обращается в нуль, и 1,(х„[и<)о) = 1о. С помощью оценки (28) нетрудно также получить условия, достаточные для того, чтобы та или иная последовательность допустимых пар управлений и траекторий была минимизирующей для задачи (5) — (8). Т е о р е м а 6. Пусть последовательность управлений [и,„), и траекторий [х» ]е (т 1, 2, ...) удовлетворяет условиям (6) — (8). Для того чтобы Вш 1о (хе,е, [иье)о) = 1о, (33) достаточно существования функции Х<(х) (1 = О, 1, ..., <е) 6»1 50» схвмА веллмлнА такой, что Вш Ю» (х»т и»т) = Я»ш»п 1 = 0 1 Л 1» (34) Вш г»т (от)= гжш»п» Пш Ко (хоп») = Кош»п» (35) тт» т»п где 8»т»„ггт»„К»т»п определены в (31), (32).
Доказательство. В оценку (28) вместо [й»]о, [х»], поста- вим соответственно [и,„]„[х» ], и перейдем к пределу при т- С учетом условий (34), (35) получим равенство (33). Утверждения, аналогичные теоремам 5, 6, доказаны в [124, 188, 189] для более общих задач, чем задача (5) — (8). Всякую функцию К»(х) (1=0, 1, ..., Л»), удовлетворяющую условиям теоремы 5 (теоремы 6), назовем функ»оией Кротова задачи (5) — (8), соответствующей допустимой паре [и,]„[х,], [или последовательности допустимых пар [и»„]„[х»„]т»и=1, 2, ...].
Заметим, что если существует хотя бы одна функция Кро- това К»(х) (1= О, 1, ..., »т)» то функция К»(х)+а» (1=0, 1, ... ..., »т') при любых а, также является функцией Кротова. По- этому беэ ограничения общности в теоремах 5, 6 можно принять 8» »» = 0 (» О, 1, ..., )т' — 1), г„ „ = О, ибо в противном слу- чае функцию К,(х) заменим новой функцией К,(х)+ ап где а»=Я»т»п+Я»+» „+...+Юг» „„, 1=1,..., »»» — 1, ໠— — г„ Таким образом, функция Кротова для допустимой пары ([й»]о, [х,],) или последовательности ([и»..]„[х»т],) (т = 1, 2, ...) согласно теоремам 5, 6 удовлетворяет условиям Ю»(х, и) = К»+»(Р»(х, и)) — К» (х) + + Ро»(х,и))0, ион)7»(х), хан Хи 1= 0,1,...,»У — 1, (36) гг(х) = Ке(х)+Ф(х) > О, х»и Х„= С,, Ко (х) ~~ Ко т»п, х ш Хо, (37) причем неравенства (36), (37) должны обратиться в равенства при и=ип х=х, или при и=наш х х»„в пределе при ло- (»= О, 1, ..., »'т').
Сравнение соотношений (36), (37) с (13), (14), (16), (20) показывает, что функция Веллмана всегда является функцией Кротова, и обратное, вообще говоря, неверно. Заметим также, что с помощью функции Кротова удается установить оптималь- ность допустимых пар, не решая проблемы синтеза, так как согласно условиям (36), (37) функция К»(х) выбирается с уче- том индивидуальных свойств конкретной допустимой пары уп- равления и траектории (или последовательности пар), подоари- тельных на оптимальность. 7. Остановимся на одном специальном классе задач миними- зации функций большого числа переменных, которые с помощью динлмичвскон пгоп лммиговлннв [гл.
т 502 метода динамического программирования могут быть сведены к последовательности задач минимизации функций меньшего чис- ла переменных. А именно, пусть требуется минимизировать функцию <'о([п<)о) = ~о(~о ип ~л-г) = Х <<<(и<) <-о (38) при условиях и«н У<, и-1 ~ 4(иД(Ь<, 1= 1,...,р, < о О, 1, ..., <"о' — 1, и — 1 а<(п<) = Ь, 1 = р + 1, ...,п, (40) (39) где У,— заданные множества из Е'; Д(и), 8<(и), ие У< — заданные функции, Ь' — заданные числа.
Задачу (38) — (40), оказывается, нетрудно записать в виде задачи (5) — (8). В самом деле, введем переменные х< (1= = О, 1, ..., А<) как решение системы хо+<=хо+у„(ио)< й=О, 1, ..., )У-1< х,=О, (41) В том случае, когда ограничения (40) и, следовательно, (42) отсутствуют, то 6» =Е" н в (43) можно положить Рл(х)= У„ (й= О, 1, ..., <о' — 1). Уравнениями (43) можно пользоваться для решения задачи (38) — (40), как это показано выше в п. 3. где бл (и) = (Ел (и), ..., Ил (и)), хл = (хл, ..., хл) (й = О, 1,..., <<').
и-г Так как из (41) следует, что хи = ~ д (ил),то ясно, что ограл=о ничения (40) равносильны условию х«е Сх = (х: х <в Е", х< ~ (Ь<«1, ..., р< х' Ь<,1=р+1,..., и). (42) Таким образом, задача (38) — (40) эквивалентна задаче минимизации функции (38) при условиях (39), (41), (42) и является частным случаем задачи (5) — (8) при Е<~(х,и) = Д(и), Р<(х, и)=х+л<(и), Ф(х) -О, С<=Е" (1=1, ..., <<' — 1); Со =10), С определено соотношением (42).
Это аначит, что для исследования задачи (38) — (40) может быть применен метод динамического программирования, изложенный выше. Пользуясь введенными ранее обозначениями, можем переписать уравнение Беллмана (13), (14) применительно к задаче (38) — (40): Вл(х) = 1п1 [1ол(и) + Вл+<(х+ Р<(и))1, (43) иапо(х) х~Хь й= О, 1, ..., )У вЂ” 1, Ви(х)=0. без схемА велшялнА з ц Предлагаем читателю в качестве упражпения переформулировать теоремы 1 — б применительно к задаче (38) — (40).
Подчеркнем, что в аадаче (38) — (40) функция и ограниченна имеют весьма специальный вид — это обстоятельство было весьма существенно для применения метода динамического программирования. Этот метод применим и к несколько более общим, чем (38) — (40), задачам — об атом см.
подробнее, например, в (101). 8. Изложенный выше метод динамического программирования является достаточно эффективным средством решения задач вида (5) — (8) или (38) — (40) — с его помощью исходная задача сводится к последовательности вспомогательных и, вообще говоря, более простых задач минимизации функций меньшего числа переменных для определения В„(х), и„(х) (см. условия (13), (14) или (43)), Если эти вспомогательные задачи решены с достаточно хорошей точностью, то тем самым и в исходной задаче глобальный минимум функции будет найден с высокой точностью. Далее, метод динамического программирования позволяет решить важную в приложениях проблему синтеза. Как показано в п.
6, с помощью этого метода и его обобщений могут быть получены достаточные условия оптимальности для дискретных управляемых систем. Кроме того, этот метод дает значительный выигрыш в объеме вычислений по сравнению с простым перебором всевозможных допустимых управлений и траекторий, поскольку прн определении В,(а), и„(х) рассматриваются лишь такие управления, которые переводят точку хж С„в точку х,+, =г"(х, и)ж С,+„а дальнейшее движение из точки х,+, осуществляется по оптимальной траектории, при этом неоптимальные траектории вовсе не рассматриваются. Указанные достоинства метода динамического программирования, простота схемы, применимость к задачам оптимального управления с фазовыми ограничениями делают этот метод весьма привлекательным, и его широко используют при решении задач типа (5) — (8) или (38) — (40).
Что касается задачи (1) — (4), с которой мы начали изложение, то можно показать, что при некоторых ограничениях решение дискретной задачи (5) — (8) при 11ш шах (~;+, — Г;) = 0 будет приближаться в некотором л з~ы~я — т смысле к решению задачи (1) — (4). Заметим, что поскольку аналитическое выражение для В,(х), и„(х) при всех х<вХ„в общем случае найти не удается, то па практике приходится ограничиваться приближенным вычислением В,(х), иг(х) в некоторых заранее выбранных узловых точках множества Х,. Однако согласно (13) при вычислении В,(х) нужно знать значение В~+,(Р„(х, и)) при некоторых и, и адесь вполне возможны случаи, когда точка х„+, Г,(х, и) не будет принадлежать заранее выбранному множеству узловых точек иэ ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ сгл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
