Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 37
Текст из файла (страница 37)
Примеры демонстрируют возможность обоих случаев (208) и (209) даже для полиномов при т=-1. Пример 1. Р (х, у) = (х — у)' — 0,5х', — 1 < х < 1; — 0,5 < у < 0,5. Здесь нет седловой точки. Очевидно, что гпах пппР(х, у)=0, к у причем х, = у' = О. Определим ппп гпах Р(х, у). у к Имеем для гпах((х — у)* — 0,5хк) внутри ( — 1; 1) услок вие 2(х — у) — х=0, т.
е. х=2у. Учитывая возможность достижения максимума на границе, получаем так Р(х, у)=гпах [ — у', (1 — у)' — 0,5; (1+у)' — 0,5). Отсюда видно, что пппгпахР(х, у)=-0,5 и достигается у к при у=0. Для этого примера, очевидно, выполнено (208), т. е. Р„'(0„0) = Р„'(О, О) = О. Пример П. Р(х, у) = — (х — у(1 — у*))', — 1 < х < 1; — 1 <у < 1. Имеем условие для пппР(х, у): !х — у (1 — у')1 (Зу* — Ц = О. Г! Если х — у(1 — у*)=0, то Р(х, у)=0; при у=~ ~ —, /"! ~ Г 2 1к Р ~х, ~ р' — ) = — ~х~= ~ при у=~1, Р(х, ~1)= — у~ з) ~ зу"з! = — х'.
Отсюда ясно, что поп Р (х, у) = т! п ( — (х+ =); — (х — =) ~ . з ю. Б. Гермеуер 171 НЕОБХОДИИЫЕ уСЛОВИя ОПТимАЛЬнОСТИ 227 димо численно получить ппп(хь р) и притом, конечно, глобальный. Отсюда видно, что задача определения макснмина в общем случае сложна даже прн одномерном векторе х и скорее всего должна решаться своими методами в каждом конкретном случае. При этом не следует забывать пользоваться теоремами 1Х и Х, упрощающими возможные стратегии противника и их богатство при определении пппР(х, р), Ы а, значит, н шахш1пР(х, у). Применение теоремы ХХЧ1 отвечает выше сформулированному принципу отношения к стратегиям оперирующей стороны н противника.
Как видно из условий теоремы, возможности противника не умаляются, в то время как оперирующая сторона выбирает только одну величину. Последнее легко преодолевается для общего случая Р(х, у) при записи х;=хан Придавая системе а,(Ха~ = 1) дискретные значения и находя максимин по х и у, найдем затем общий максимин как максимальный по (а;) из максиминов пох иу. Дискретизация (даже сколь угодно грубая) по (ох;) не противоречит приведенным выше принципам, поскольку возможности противника учитываются при этом достаточно полно. Однако интересно получить необходимые условия и для произвольного вида вектора х. Для того чтобы стал понятным путь, по которому такое обобщение может происходить, отметим, что оба варианта а) и б) необходимых условий в теореме ХХЧ1 могут быть записаны в виде одного: Существуют р и р, (не обязательно различные между собой) и ХЕ ~0, 1] так, что Р (х„р) = Р(х„р,) = ппп Р (х„р) и Л 7РА(хоэ Р)+(1 )о)Ро(хо~ Ро)=б Действительно, если выполнено а), то, взяв А,=1 и р, р, выполним укаэанное условие.
Если выполнено б), 9' 228 (гл. ш оптямьльныг стеьткгии и хоть одно из чисел Р„'(х„р), Р„'(х„р,) равно нулю, тогда действуем аналогично; если же они оба отличны от нуля и не равны между собой, то всегда найдется нужное»,. Обратное еше более очевидно: если р, и р различны, то уже выполнено б), а если они совпадают, то при любом к получаем Р;(х„р)=0.
Таким образом, если пренебречь одним неясным случаем Р„'(х„р) = Р;(х„р,) Ф О, то напрашивается мысль, что обобщение на векторное х нужно искать в аналогичном виде. И в самом деле имеет место Т е ар е ма ХХЧП. Пусть М, и 1«' — ограниченные замкнутые множества соответственно и- и т-мерных пространств; пусть, далее, Р(х, у) и Р;,(х, у) при 1(1(п, непрерывны на М«х1«'. Тогда для оптимальности внутренней точки х,ЕМ, необходимо существование неотрицательных чисел го ..., г„, и стратегий у„..., у„+, (не обязательно различных между собой) такйх, что и+! « ~-1 ~ г;=1; .'~~~ г;Р; (х„у;)=0; й=!, ..., и, (210) Р(х„у;)=пппР(х,,у); 1=1, ..., и+!. уел Доказательство этой теоремы довольно громоздко; поэтому приводить здесь его не будем, отослав к статье автора «Необходимые условия максмина» в «Журнале вычислительной математики и математической физики».
Используя необходимые условия для пппР(х„у) и учитывая возможность попадания х, или у; на границу, легко получить из (210) необходимые условия, совершенно аналогичные (201), с той лишь разницей, что первые условия и+» на производные по х; будут относиться к ~г;Р(х, у,.), 1=1 а вторые должны быть выполнены для всех уь Кроме того, необходимо Р(х„у;) = Р(х„у,).
Легко увидеть, что количество условий при этом совпадает с количеством неизвестных, позволяя тем самым в принципе определять х„ «подозреваемые» на оптимальность одновременно с определением Р(х„у;), которое для оптимального х, и дает искомый максимин. К сожалению, условия (210) при сколь- З 171 неовходи(гые УслОБНЯ ОитимАльности 229 ко-нибудь большой размерности вектора х, становятся громоздкими.
Следует поэтому использовать те или иные априори известные свойства Р(х, у) для их упрощения. В частности, если заранее известно, что ппп Р (х, у) уен может реализоваться разве лишь в 1(п точках, то, очевидно, условия (210) заменяются на следующие. Необходимо существование неотрицательных чисел г„..., г, и не обязательно различных стратегий противника у„..., у, таких, что ( ! ~ !';=1; ~ г;Р„' (хю у!)=0; й=1, ..., и, (=1 (=1 Р (х„у;) = пнп Р (х„у). (210') ден Например, если известно, что Р (х, у) унимодальна по у, т.
е. минимум реализуется только в одной точке, то необходимые условия оптимальности становятся тождественными с необходимыми условиями на седловую точку типа (20!). Другой путь (работы В. Н. Пшеничного и В. Ф. Демьянова) основан на использовании производных по направлению для функции ф (х) = ппп Р (х, у) . Демьяновым по этому поводу доказана, например, следующая весьма интересная теорема. Теорема ХХЧП1.
Пусть Р(х, у) непрерывна вместе с ограниченными производными Р„,(х, у) на произведении ограниченных замкнутых параллелепипедов Е„и Е соответственно и- (ерного пространства векторов х и т-мерного пространства векторов у. Пусть, далее, имеется произвольный единичный вектор у=(а„..., а„), и пусть множество Я(х) состоит из точек у„для которых Р(х, у()=ф(х)= ппп Р(х, у). уе ещ Тогда у функции ф(х) существует производная по любому направлению д, не выводящему из Е„(х-1- Ь йбЕ„ 230 (гл.
Ии ОПТИМАЛЬНЫЕ СТРАТЕГИИ при достаточно малых Л ) 0), т. е. Суи(есп(вует ' ~(") = 1пп ~( + у) 'Р(") при х+ЛдбЕ„. ду ь о Ь> о Для этой производной справедливо равенство др(.) 1,,„Р 1.+ьу, у) — $(.) ду ь о,—,е Ь>о если последний предел существует. Имеем для любого у'ЕЕ, поскольку Л ) О, Р(х+Ьу, у) — (Ь(х) Р(у+Ьу, у) — (Ь(х) ппп Л ( уо ео( Отсюда для всех у' Г(Г(.Я О вЂ” ОО( ( ( Р(Г4М~ — А(6 Ь о Ь>о Ь>о Потому 1пп ппп — "~-~~~-У~:-~["-)-оь, уо В(о ( ( (ыоао(ЬЕà — огл уоае Ь о д Ь>о == пнп [Ге(Р„,(х, у)+...
+а„Р,„[х, у)) = уол ьа В (211) для краткости через =' обозначен вектор дР(х, у) дл (Р„(), а квадратные скобки означают скалярное произведение. Перейдем к доказательству теоремы, подразумевая все время, что речь идет только о направлениях, не выводящих нз Е„. Прежде всего, очевидно, что Е(х) — ограниченное замкнутое множество. Согласно определению )р(х) й 171 неовходимые головня оптимьльности 231 Но при у', не принадлежащем Я(х), — Р (х+ Ьл, у') — оя (х) 1пп ' =+ос, ь о А р(х, у') > ф(х)= пип Р(х, у).
уо ещ ибо дГ(х, о) Напомним, что производная по направлению ду согласно условиям равномерно непрерывна по х и у в Ео ХЕ Введем множество У„~Е такое, что при уЕУ„ Р (х, у) — ф (х) ( е (Р(х, у)~~ф(х) по определению ф(х)). Очевидно, Я(х)~У„и при е- О )'„— )т(х) из-за непрерывности функции Р(х, у), на ограниченных Е„и Е„. Поэтому для любого е, найдутся е и А такие, что для Поэтому — о)! (х+ Ле) — о(! (х) —. п!П! Г(х+ Ье, у) — о)! (х) Ь ь о ь о хоеоо ь>о ь>о ( ппп 1пп (х+ и' ") (х' " = ппп ~ (х' ") , а .
хо я!-„! ь яои(х! ь дх (212) Отметим, что при выводе (212) использовалось по существу только условие существования у Р(х, у) производной по любому направлению д, а не дифференцируемость этой функции. Сложнее обстоит дело с неравенством обратного типа. Имеем прежде всего = — ппп (Р(х+ Ау, у) — ф(х))= яо Лов = ! !П1 Ф(Л, у), хо и„ Ф(Л, у)=Р(х, у) — ф(х)+ ~ ~' " о(т.
(2!3) !гл. и! оптимальные стглтегИИ любого у Е У„ найдется у' Е Я (х), так что ду(х, у) ду(х, у') (е„ ду ду причем если т(д, то -'- -1' ду (х+ъд, у) дР (х, у) ~ дд дд Имеем поэтому при уЕ г„ д7(х, у) . др(х, у') Ъ |п(п ' — е„ У'Ей <Й Ь (п1 Ф(Д, у)) !п1 ) У' " Ж~~ УЕ ГЕ» УЕГ»» Е ду дР (х+ЕУ У) д 1 дР (х У ) 2е д УЕ~ „Е<Е<Ь У'е лс»» ду (214) РУ~~ стерпим при у ~ ) Е Ь п1 Ф(Д у): е+,п1 ~ дг( + ду где й еир ~ дУ(+ту,еу) у,е~ ду Д~м, ~.~ 1!(„-) „, (д» У)( !п1 Ф(д у) У Е Ум УЕ Я (х! 1п1 у ду(х+ у, у) хе и (х! е ду По муе ид(е то !п1 Ф(д, у)( (п1 Ф(д, у) УЕтм УЕ УЕ» 171 ИВОВходимыВ услОВия Оптимхльиости 233 и, следовательно, ;„1 Ф (д, р) = 1п1 Ф (Л, у).
(215) УЕЛ„, У»У» Таким образом, при фиксированных В, и В и достаточно малых Л из-за (214) и (215) Р— ш1 Ф(Л, у)) ш1 ' " — 2В,. уеи» у'ен(к) В силу определения ер(х+ дд) ер(У+ай) — ер(х) . 1 дР(х, у') Произвольиостьа„равенство ' У = ~ ' ", й'~ ду дх и (212) доказывают существование у ф(х) производной по любому направлению 3Т и равенство Теорема ХХЧ111 дана в формулировке В. Ф.
Демья- нова. Однако из доказательства легко усмотреть, что тео- рема остается справедливой и в том случае, когда у есть точка любого замкнутого компактного пространства, а не только Е„. Эффективность этой теоремы, вернее, формулы (211) уменьшается необходимостью знать все множество К (х). Между тем определение ф(х), а значит, и ее производных по направлению требует знания только величины ппп Р (х, у), а вовсе не всего множества реализаций этого минимума.
Это снова те же затруднения, как и при использовании теоремы ХХЧ1. Тем не менее значение теоремы ХХЧП1, видимо, велико. Из нее, в частности, следует, что если 1т(х,) состоит из одной точки ре и х, не лежит на границе Е„, то ф(х„) д»Э (хе) дл (хе, у») дифференцируема и дх дх оптимлльные стглтегии [гл. ш Но тогда, если х,— наилучшая гарантирующая стратегия, то необходимо 0=== ', что вполне со- дФ (хю) дР (хо уо) дх дх впадает со смыслом первого варианта условий (207).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
