Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 32
Текст из файла (страница 32)
19! $161 о сгдлозых точкьх В пределах данного раздела будет говориться о седловых точках, принадлежащих М,хФ. Легко заметить, что теорема ХЧ1П справедлива, если х и у есть точки любого пространства. Почти очевидным достаточным условием существования седловой точки является Теорема Х1Х.
Если Р(х, у) непрерывна назамкнупюм ограниченном ('в оби(ем случае, компактном) множестве МехМ и если при любых х, и х, из М, Р(х„у) — Р(х„у) не меняет знака, когда у пробегает У 1или если Р(х, у«) — Р(х„уе) не меняет знака при любых у„ у, из й1, когда х пробегает М,), то Р(х, у) имеет на М«ХУ седловую точку.
При этом в первом случае есть абсолютно оптимальная х, а во втором абсолютно оптимальная у. До к аз а тел ь ство. Фиксируем какую-либо точку у„ и пусть х,— точка, в которой достигается щах Р(х, у,). «ЕМв Тогда в силу условия сохранения знака Р(х„у)— — Р(х, у) Ъ 0 при любых у и для любых х. Имеем поэтому Р(х„у)= гпах Р(х, у) при всех у. Таким образом, х, ХЕМа абсолютно оптимальна. Пусть теперь у, таково, что Р(х„у,)= пппР(х„у).
УЕУ Пара (х„у,) и есть искомая седловая точка, т.е. удовлетворяет (186). Действительно, по построению, Р(х„у,) =ппп Р(х„у) и Р(х„у,) = щах Р(х, у,), Рен «ЕМ. поскольку это равенство верно для любого у. Во втором случае вначале будет найдено у, такое, что Р(х, у,) = ппп Р (х, у) при х Е М,. вен Следствия. 1. Если Р(х, у) =ф(х)+1(у), то при непрерывных ф и 1 на компактных М, и 1Ч всегда есть седловая точка и существуют абсолютно оптимальные х, и у,. 192 [гв. щ оотимкльные стглтегни Аналогично обстоит дело и с Р(х, у) =ф(х]1".(у), если хоть одна из ф(х) или 1(у) не меняет знака на своем множестве; так, если, скажем, 1(у) = О, то Р(х„у) — Р(х„у) = [ф(х,) — ф(х,)]1(у) и не меняет знака при изменении у.
В этом случае существует абсолютно оптимальная х,. Можно снять и условие постоянства знака хоть одной из ф(х) или ~(у). Действительно, пусть и ф(х), и 1(у) меняют знак, и пусть х, и у,— точки, в которых ф(х,) = = О = Ду,). Пара (х„у,) есть седловая точка, ибо Р(х„у)=Р(х, у,)=Р(х„у,)=О при любых х н у, что и обеспечивает условия (186). Од- нако в этом случае абсолютно оптимальных страте- гий нет. 2.
Если х=х — скаляр, М,=(а, Ь) и Р(х, у) имеет Р;(х, у) на М, х АС, причем эта производная не меняет знака при всех х и у, то Р(х, у) имеет седловую точку, ибо Р(х„у) — Р(х„у)=(х,— х,)Р„'(х', у), и, следовательно, не меняет знака при любых у, если х, и х, произвольно фиксированы. Примером такого рода случая может быть л Р (х, у„..., у„) = ~ (х — уг)''ч+', 1=! где и,— целые числа. Значительно более интересно достаточное условие существования седловой точки, связанное с понятием выпуклости функций. Т е о р е м а ХХ. Если ограниченные М, и )ч' выпуклы и замкнуты, а Р(х, у) непрерывна, вогнута по х при калсдом у и выпукла по у при калсдом х, то Р(х, у) имеет седловую точку.
Дока з а тел ь ство. Предположим сначала, что Р(х, у) строго выпукла по у и строго вогнута по х (т. е. соответствующие неравенства строги при О < к < 1). ф 16! 1йЗ О СЕДЛОВЫХ ТОЧКАХ Согласно непрерывности платежа и его строгой выпуклости существует у (х) такое, что Р[х, у(х)] =пи'пР(х, у)=т(х), причем у(х) однозначна (минимум достигается в одной точке).
Действительно, если бы были две точки у,(х) ~ Фу,(х), то Р [х, Лу,(х)-1-(1 — Л) у,(х)] < <Л Р [х, у,(х)]+(1 — Л) Р(х, у, (х)] = т(х), что противоречит определению т(х). Из равномерной непрерывности Р(х, у) и однозначности у(х) следует непрерывность т(х) и у(х). Действительно, если бы существовала последовательность х„— х„для которой у(х„) — у,7ьу(хе), то по непрерывйости Р [хе[у(х„)] — Р [х„у,]. Но для любого п и уй!Ч Р [х„, у(х„)] <Р [х„у]. Отсюда в пределе для любого у Р [х„уе] < Р [х„у], и, следовательно, у„являлась бы второй, кроме у(х,), точкой реализации минимума. Непрерывность т(х) яв- ляется прямым следствием непрерывности у(х) и Р(х, у). Пусть х" — точка, в которой т(х') = гпах т(х) =щах йп!пР(х, у).
е 7 р Для любого х из множества стратегий имеем Р [(1 — 1) х'+ !х, у] ) (1 — !) Р (х', у) + !Р (х, у) ) )(! — !)т(х')+!Р(х, у). Выберем у=у [(1 — !) х'+!х] =-у. Тогда и И! — !) х'+!х] ~ ~(1 — !) т(х')+!Р(х, у). Ю. в. Гермейер 194 1гл, ги ОИТИМАИЬИЫР СТРЛТК!'ИИ Но ввиду того, что т(х') ) т(х), т (х') ) т [(! — 1) х'+ гх); поэтому 1Р(х, у) < 1т(х'), т. е.
Р (х, у) < т (х*) = Р [х', у (х')]. Пусть теперь 1 — О, так что (1 — 1)х'+1х - х' и у — у ( х') Отсюда получим Р [х, у(х')) <Р [х", у(х')). Если положить у(х') =у', то по только что полученному неравенству и определению у(х) Р(х, у*) =.Р(х', у*) Р(х*, у), а это согласно теореме ХЧ!П и означает наличие седловой точки. Остается освободиться от требования строгой выпуклости и вогнутости. Если Р(х, у) просто вогнута по х и выпукла по у, то 1,(х, у) = Р(х, у) — е ч~~ ~х! + а ~ч'.' ,у' 1=1 1=!.
строго вогнута по х и строго выпукла по у. Поэтому существуют х, и у, такие, что Р(х, у,) — е ч~~~ х,' <1,(х, у,) <1,(х„у,) < <1,(х„у) < Р(х„у)+е ~ч'"„у';. / ! Возьмем теперь последовательность е- О и подпоследовательность этой последовательности, для которой х, сходится к х' и у, сходится к у'. В силу непрерывности 195 6 16! О СЕДЛОВЫХ ТОЧКАХ Р (х, у) в пределе получим Р(х, у')<Р(х*, у')<Р(х*, у).
Этим и завершено доказательство. Основным признаком выпуклости функции 1(г), скалярного аргумента гЕ [а, б] является условие !"(г) > О при гц [а, Ь). Эго легко получить следующим образом. Пусть г' = Лг, + (1 — Л) г,, г, ) г„О < Л < ! . Тогда Л7 (г,)+ (! — Л) 1(г,) — ! (г') == = Л [1(г,) — 7 (г')) — (1 — Л) [7 (г') — 1 (г,)) = =Л(1 — Л)(г — г*) К [г'+0(1 — Л)(г — г*Я— — !' [г' — Е,Л (г, — г,)!1. Но последний сомпожитель неотрицателеп из-за !" (г) ) О. Отс~ода и следует Ц(г,)+(! — л) !'(г,) ) 7(г').
Для общего случая векторного г, вводя ер (Л) = 1 [Лг, + (1 — Л) г,), при <р" (Л))0 [О- Л<1[ имеем согласно доказанному р(Л) <(1 — Л) р(О)+Ля (1), а это означает, что 1(Лг, +(1 — Л) г,) <(1 — Л) 7(г,)+ Л7". (г1). Таким образом, условие <р" (Л) ) 0 является общим достаточным условием выпуклости !'(г). Для вогнутости соответствующие вторые производные в достаточных условиях имеют другой знак. В качестве примера вогнуто-выпуклой функции можно привести " (х, у) = д 1я (х+ 2) + ху', где 0 < х =" 1 и О -" у < ! . Для нее имеем что н обеспечивает вогнутость по х и выпуклость по у. Фундаментальная для теории игр и исследования операций теорема ХХ в качестве следствия дает результат 196 !гл. ш ОПТИМАЛЬНЫЕ СТРАТЕГИИ о седловых точках для так называемых разделимых игр, т.
е. игр с платежной функцией вида Р(х, у) = ~ ~; (х) ~р! (у). (189) Теорема ХХ!. Пусть 1,(х) и <р;(у) в (189) непрерывны на М, и У, и пусть далее множества М, и У значений векторов и =(и;) =(~;(х) ) и о=(о!) =(<р;(у)) при хЕМ, и уЕМ, !(з, замкнуты, выпуклы и ограничены. Тогда игра (189) на М, х Ф имеет сгдловую пючку. Д о к а з а т е л ь с т в о этой теоремы почти очевидно. Через векторы и и О платеж (!89) выражается в виде Р,(и, Й) = „~~ ири (190) С=1 Зта билинейная функция, будучи линейна по и при фиксированных о и, наоборот, линейна по о при фиксированных и, тем самым вогнута по и и выпукла по с. Поэтому игра на М,ХЛ1, имеет седловую точку. Пусть это будет (и„о,), и пусть х, и у, — любые векторы, для которых и, = Щх,)); о,=(~р;(у,)). Зта пара х, и у, составляет седловую точку игры (!89). Действительно, по свойству седловой точки й„о, имеем для любых у и х: Р (х, у,)=Р,(и„о,)(Р,(и„о,) = = Р (х„у,) и Р, (й„о) = Р (х„у).
Определенный интерес представляет расширение этой теоремы на случай, когда М, или М, (или оба сразу) бесконечны, но остаются выпуклыми н замкнутыми. Тогда они могут быть представлены как предел расширяющихся множеств М„"" и Уы', для которых теорема ХХ1 справедлива и, значит, есть седловые точки ОМ <М ь ю о Если множества и,'"' и о',"' имеют предельные точки и„о„то в силу замкнутости М, и У, они и дадут сед- 5 161 197 о седяовых точках ловую пару на М„и У .
Проверка всего этого для (190) не представляет труда в каждом конкретном случае. Отметим отдельно следующее. Теорем а ХХГ. Пусть М, замкнуто, ограничено и выпукло, а У„=У,,хУ„х... хУ хУ", выпукло и замкнуто, причем У,, =( — оо; +со) при !(т, а У;, представляюи!ее собой множество векторов (о „, ... о,), выпукло, замкнуто и ограничено. Тогда (189) на М,хУ будет иметь седловую точку (х„, у,) тогда и только тогда, когда М„содержит хоть одну яичку и', для которой при ! (т все и,'. = О. В седловой точке и! „также равны нулю при ! е .т. Доказательство. Необходимость. Пусть (х„у,) — седловая точка (189), а (и„о,) — соответствующая ей седловая точка (190).
Тогда -1- оо ~Р!(и„о,) = =ш1Р!(и„о)(ш1 ~~ и„о,+ .У, имо! !1=! 1=ги+! Если имеются им~О при г(т, то, устремляя те о; к — оо, для которых и!,)О, и остальные о; к +во (при !~т), получим, что 1п1Р!(им о) = — ьо, а это ь противоречит конечности Р!(и„ о,). Таким образом, им — — 0 при 1 ( т, что и доказывает одновременно необходимость условия и утверждение о координатах седловой точки. Достаточность. Пусть М"„— множество всех векторов и из М„, обладающих и;=0 при 1(т.
Это множество, очевидно, выпукло, ограничено и замкнуто вслед за выпуклостью, ограниченностью и замкнутостью М,; У," выпукло, ограничено и замкнуто по предположению.. в Игра на М„" и У; с платежом ~~', и!о! удовлетво8=а+1 рвет всем условиям теоремы ХХ1 и потому имеет седловую точку (и!,), (о!,), где !от+1. Определим полные и, и о„приняв их координаты при 1 я т равными и„= о„= О. 198 (ГЛ.
Ш ОПТИМАЛЬНЫЕ СТРАТРГИП Имеем Р! (ие оо)=Х и!О!А= .ГГ и!о!о ~(гГ(йод ое)= Г=! Г=ЛГ+1 ил,оГ„( ~ иГАПà — — ~.', ИГ,ПГ = Р! (и„о). Г= +! ' ' Г= +! ' Г=! Это неравенство и показывает, что и, о, есть седловая точка на М, и У,. Но тогда так же, как н в теореме ХХ1, любая (хм д,), соответствующая им ом дает седловую точку для (!89). Теоремы ХХ1 и ХХ!' показывают, что дли получения седловых точек в разделимых играх желательно добиваться выпуклости М, и ГГ(„а не М, и 1Ч. Требование выпуклости М, можно считать, таким образом, желательным условием на множество стратегий М (если стремиться получить седловую точку). Однако выполнение тех же требований для ПГ', находится вне пределов возможностей оперирующей стороны — это и подчеркивает нетипичность случая наличия седловой точки на М,х)т'.
Легко убедиться, что множества Мтч и У„Г выпуклы и замкнуты вместе с М, и Ф, если соответствующие 1Г(х) и ГрГ(у) непрерывны. Это следует из простого рассуждения. пусть и1ГГ, иГГЫ Ем„„тогда и)!'=1Г(х!) и и'," =1Г(х ), где х„х,~М,. Если М, выпукло, то и Лх,+(1 — Цх при О(Л(1 принадлежит к М,. Непрерывная функция аргумента Л ~Г [Лх,+(1 — Л)) х,) принимает все промежуточные значения между 1Г(х!) = ио' и 1Г(х,)=и)". А это значит, что для любого р из [О; Ц найдется Л„, для которого 1Ги,"' -!- (1 — р) и!" = 1! [Л х, + (1 — Л Д х ). Поскольку ЛРТ,+(1 — Л )х, ЕМ„то )АМ!!!+(! — )А) и'," принадлежит М„„чем и доказана выпуклость М„Г Выпуклость М, и Гт'Р при выпуклых М, и !Ч обеспечена, о сздловых точкАх гп9 если МиМ~|хМд~ххМ4УуУр~хУ~дххУюю ° Однако такое положение носит достаточно исключительный характер. Так, если и,=-гзшф и и,=гсозф при О < Я,<г<Я, и ф0<ф<ф„то М, выпукло, а М, представляет собой часть кольца й не является ни прямым произведением М„, и М„„ни даже просто выпуклым.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
