Ф.П. Васильев - Методы решения экстремальных задач (1125244), страница 64
Текст из файла (страница 64)
((„„., — („) = О. Следовательно, р (Г) ) 0 при (, ( Г < Гь„. Может случиться, что р(1„„,)=0. Тогда Гх„=Ä— искомый корень уравнения р(1)=0. Если р((ьм))0, то процесс (34) продолжаем дальше. Здесь имеются три возможности: 1) Процесс (34) закончится определением момента Гэ такого, что (,<(а<.Т, р(1;))О, 1=0, й — 1, р(гх) =О. Тогда (а=(, — задача решена.
2) р(Г,))0, 1„<Т, прн всех й=О, 1, ... Так как последовательность (г~) монотонна, то существует 1пп 1„= = („( Т. Из (34) при А -э со получим р (( ) = О. Кроме того, р (() ) 0 при (, == Г < („й = О, 1, ..., так что р (() ) 0 при (,(1<1„следовательно, Г, — искомое время. 3) Найдется номер ги такой, что Г„,~Т<1,„, р((;)) )О при всех ю'=О, ги. Тогда (, )Т. Таким образом, метод (34) позволяет выяснить, будет ли 1„принадлежать [(и Т1, и если это так, то найти приближение (» — („. В том случае, если выяснится, что 1 )Т, аналогично можно продолжать поиск 1„на отрезках )Т, ТД, ~Тм Т,~, ...; ири этом в методе (34) вао каждый раз нужно использовать ту константу Е, которая соответствует рассматриваемому отрезку. 6. Описанный метод (34) предполагает, что значения функции р (1) известны точно. Перейдем к изложению метода (34), свободного от этого недостатка. А именно, предположим, что при каждом 1, 1,(1( Т, вместо точного значения р(() может быть найдено его приближение рл(1) такое, что ~р(1) — рх (1) )($м рл(1) О, 1о =1==Т, (35) где (фл)-~0.
Пусть известно (У вЂ” 1)-е приближение (х „ У)1 (начальное приближение 1, нам задано). Для определения следующего приближения (л рассмотрим итерационный процесс 1ньы=1мь+рл(1мл)71- й=О 1 " !мо=Го (36) аналогичный процессу (34). Из-за погрешностей равенство рл (1) = 0 не влечет за собой равенства р (1) = 0 и наоборот, поэтому процесс (36) следует прекращать не по критерию рл((х~)=0, как было выше, а по условию вида рх (1дъ)(Ех, где (Вм) стремится к Нулю при М-~-оо согласованно с погрешностью Д,ч) из (35). В рассматриваемом случае, когда функция р(1) удовлетворяет условию (33), такое согласование означает, что Ех'--2Цх. У=1, 2, ... (37) Имеются две возможности: 1) (м,(Т при всех lг=О, 1, ... Так как ((„а) монотонна, то существует !пп (,чд(Т.
Тогда из (36) следует, что !нп рл ((л'а) = О 2) Существует номер з такой, что (х, ( Т ((л,+,. Отсюда следует, что за конечное число шагов процесса (36) найдется номер В=А такой, что будет выполнено одно из двух следующих условий: р (1„,) ~ Ел, й = О, т р (1 ) е, 1„. Т, (36) или Рл(Ь„,))ах, й=О, тл — 1, 1и -т~Т<Лл . (39) Положим (л = пнп (1лг , 'Т1, ,'40) Метод описан, ЗЕ1 Т е о р е м а 3. Пусть выполнены условия (33), (35), (37).
Тогда последовательность ((н), определяемая методом (36), (38) — (40), сходится к ш)п (Юь; Т). Д о к а з а т е л ь с т в о. Сначала рассмотрим случай 1ь«(,(Т. При каждом фиксированном Л~ имеются две возможности: 1) (л, ( („ при всех Й =О, 1, ... В силу монотонности ((нь) тогда существует Игп (нь « 1„, и из (36) следует ь со 1нп рн ((л„) = О. Это значит, что за конечное число шагов итерационный процесс (36) закончится выполнением условий (38). 2) Найдется номер з такой, что (н,«1,„(1н„,.
Тогда нз соотношений (33), (35), (36) имеем (и ь=1н +рн((л )77-= =( . + (Рл ((нз) — Р ((н.)УЯ+(Р Рнь) — Р ((.))Х « (не+ а%+ ((ь 1л5) (ь + $уХ Так как (ян)-эО и 1а -1 (Т, то 1н 1«1 +$лЛ .- Т при всех У)Лгь. Отсюда и из условий (35), (37) следует, что Рн(гн '1)= = (Рл (гл +1) — р ((н»))+ (р ((н. ~) — р (1ь)) == «Ь+ 7.
((л „1 — Гв) == 2$л «6н. Это значит, что условия (38) выполняются при некотором ты=в+1, Объединяя обе рассмотренные возможности, заключаем, что прн 1ь«1, (Т процесс (36) при каждом М) ) У, закончится за конечное число шагов выполнением условий (38), причем (н=~л «(,+$лу7-«Т, У- Л'ь. Отсюда имеем Игп (л«(„. Пусть Иш 1н= Иш (н =а. и сь Ф я l ОЭ Тогда с учетом условий (33), (35), (38) получаем О =.о(а) =(р(а) — р((н,))+(р(гн ) — он ((н ))+рн ((н )« «7,: а — (н, ~+ 8н, + 6л, -~ О и ри с -~- со.
362 Это значит, что р(а) =0 и, следовательно, а~1„,. Таким образом, имеем 1о<а= 11гп 1л = 1цп 1~д(1„т. е. л д У ш 11гп 1и =1„. Случай го<1,:,Т рассмотрен. Пусть теперь 1, ) Т. Зададим произвольное число е, О< е (Т вЂ” 1о. Так как функция р(1) непрерывна и р(1)) )0 при 1о(1<Т вЂ” е, то р,= ш)п р(1))0. Тогда и<о<т-е существует номер У, такой, что р,) $л,+0тт при всех Л' = У,. Следовательно, ри(1)>р(1) — зов)р,— Од,)0~, при 1о~1<Т вЂ” е. Из (38) — (40) тогда имеем Т вЂ” е(1л (Т при всех АГ) ) Ж,. В силу произвольности е отсюда получаем 1нп 1,д = = Т. Теорема 3 доказана.
Заметим, что если функция р(1) монотонно убывает, то вместо (37) можно взять условие Ь ==- 0и, М = 1, 2, ...; теорема 3 остается справедливой и в этом случае. Монотонность р(1) в задаче (1) — (5), (28) имеет место, например, при 1"= — О, 0 он )т, у=О. 7. Для получения величины рл,(1), удовлетворяющей условиям (35), можно воспользоваться разностной аппрок- симацией задачи (20) — (31). А ил1енно, пусть (1;: 1о(1,( (... (1т = Т',, Л" = 1, 2, ..., — разбиения отрезка [1„Т), удовлетворяющие условию бл = гпах (1;+~ — О) ~ (Т вЂ” 1о) Мо!АГ, о<о<и — 1 0=1, 2, ..., М,=сопз1)0. (41) Пусть 1 — некоторый фиксированный момент времени, (о<1 Т, и пусть 1 <1<1 „.
Если 1<1„,о„то на время вычисления искомого значения ри (1) узловую точку 1 „заменимточкой1,т. е. примем 1 „=1. Ясно, что от такого переопределения одной точки разбиения [1о) свойство (41) не изменится, нужно лишь в (41) вместо М, взять 2М,, Рассмотрим задачу 7л ([и]„, 1) = , 'х „([и1л) — у ~о — ~- (п1, (42) хм1=х;+ЛА(А;х;+В;и;+[;), 1=0, тль 1 ы —— 1, (43) [и~~ ен (о'и= (т'л (Т) = = ([и)л~ = (и„..., ии,): и; ~ )т, 1= О, Аà — 1). (44) Положим рл (1) = 1п1 1и ([и]„, 1). жи Ясно, что на задачу (42) — (44) величины и,,„т, ... ..., им т не влияют.
Но тем не менее, как и в задаче (29) — (31), мы здесь рассматриваем множество (44), так как при нижеследующих ссылках на ч 1 удобнее работать с множеством Ж'ы. А именно, важно заметить, что все оценки из ~ 1 для траекторий х(т, и), инн((У, и [хь([и)м))ы, [и4у ен((ум, получеььььые для отрезка [(„Т7, остаются справедливыми и для отрезка [(„(! с теми же постоянными фф..., не зависящими от выбора та~(-=.Т. Поэтому, повторив рассуждения из з 1, согласно оценке (1.31) получим !рлт(!) — р(Г)!(Сбы, !в(1(Т А(=1, 2,, (45) где С=шах[Се; С,), величина бы определяется формулой (1.26). Далее, учитывая, что задачу (42) — (44) придется решать приближенно, заметим, что на практике вместо величины ры (!) нам удастся найти лишь некоторое ее приближение ри(!) с погрешностью ~ рл (!) — рл(!) ~()(ы Будем считать, что с увеличением Аь точность решения задачи (42) — (44) повышается и (ул)-мО. Отсюда и из (45) будет следовать, что величина рьт(!) удовлетворяет условиям (35) при $л:=Сбл+)(и -О, Аь- со.
Заметим, что описанный выше метод поиска минимального корня уравнения р (г) может быть модифицирован на случай функций р(!), удовлетворяющих условиям !р(!)-р() [- (~ — !) . Т, где оь (ь() — неубывающая функция переменной д ) О, оь(0) =О, и применен для решения более сложных задач быстродействия [56, 601. О других аспектах задач быстродействия, различных приложениях, о дифференциальных играх преследования- уклонения, обобщающих задачи быстродействия на случай конфликтных ситуаций, см., например, в [15, 29, 36 — 39, 49, 54 — 56, 60, 82 — 86, 93, 104, 106, 107, 113, 116, 125 — 128, 156, 158, 167 †1, 175 †1, 183, 184, 199, 215, 216, 229, 230). 9 7.
Об аппроксимации максиминных задач Ь. Пусть Х, )' — множества произвольной природы, К (т — заданные множества, (т ~ Х, (т ы 'т', функция У(и, в) переменных и, и определена при всех (и, о) ш б иР, 364 Рассмотрим задачу: найти величину зир !п1,/(и, о)=?г. ишь/ ото Задачи такого типа возникают в теории игр и исследовании опера- циИ, в вопросах приближения функциИ, при исследовании влияния погрешности исходных данных на Решение задачи минимизации и т.
д. [6, 18 — 20, 76, 77, 88, 119, 12), !23, 127, 128, 131, 134, 136, 144, 149, 150, !60, 161, 170 в !7?, 181, 183 в 187, 205, 2!О, 217 †2 229, 230]. Пусть Х, 1', М=!, 2, ..., — некоторые множества произвольной пРиРоды, Ум, У/г — заданные множества, Ум ы Хм, Ум ы У ч, функции //ч ([и]м, [о],.ч) определены при всех ([и], [о],) ~ я У,х У , М = 1, 2, ... Рассмотрим последовательность задач: найти зор (п! /,ч([и]/ч, [о]/ч)=/, М=1, 2, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
