Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 29
Текст из файла (страница 29)
Наиболее полная информация об у соответствует случаю 1с(р) =у; именно так получается множество М,. 172 !гл. ш оптпмлльпыз стглтлгпп Выражение Ь~(, =Р,— Ц,= ьцр Ы Р(х, у) — зпр Ы Р(х, я)= ««и, у«ч ««м, у«м = ш1 зпр Р(х, у) — зпр ш1 Р(х, у) (!79) у«м «ем« х«мх у«лг дает оценку ценности изменения информированности от соответствующей М, до полной информированности; это, так сказать, ценность «остатка» возможной информированности. Случай, когда (!79) дает нуль, обобщает (174). Стоит обратить внимание на следующее: поскольку значения функций х=х(у) при всех убей принадлежат М„ знр Р(х, И)( зцр Р(х, р) ««м, «ЕМ» Но тогда и Р„= — !п1 зпр Р(х, у) > !п1 зпр Р(х, у).
у«й ««ма у«м ««м, Но, с другой стороны, согласно определению М, в нем содержатся все функции вида х=х при хЕМ„т. е. М, ~ М,. Поэтому выше написанные неравенства должны быть верны и в обратну|о сторону, что дает Р„= ш1 зир Р(х, у)= ш1 зцр Р(х, у), (179') у«м ««м, у«м х«м, Ц,= !п1 знр Р(х, р) — зир !п1 Р(х, у). у«м ««м~ ««м, у«м Легко убедиться в справедливости (179') для любого М, ~ М„если даже входящие в М, стратегии не описы- ваются видом (!78), но, конечно, при хЕМ».Отсюдаслу- чай, когда 4, = О, эквивалентен равенству ш1 зпр Р(х, у)= зир !п1 Р(х, у), у«м х«м, ««м, р«лг которое полностью аналогично (!74) и также может на- зываться случаем наличия у Р(х, у) обобщенной седло- вой точки на М,хй!.
Само собой разумеется, что опреде- ление (174) — (!74') седловой точки носит совершенно об- $15! понятие Оптимкльяой стгктзгия ший характер и может применяться к любым функциям, заданным на любых абстрактных множествах М, и !Ч. Очевидна следующая теорема, устанавливающая связь между существованием абсолютно оптимальной стратегии и равенством Ц,=О. Теорема Х1Ч. Если для любого е>0 существует в множестве М, и-абсолютно оптимальная стратегия, то соответствующее значение Ц, (формула (179')) равно нулю.
Действительно, пусть для любого е > О имеется х,' Е М„ для которой при любых х ЕМ, и ус 7»! Р(х'„у) > Р(х, у) — е. Отсюда зпр Р(х, у)(Р(х„у)+е, «ЕМ» ш1 зпр Р(х, у)< !п1Р(х„у)+е( зцр !п1 Р(х, у)+з. УЕЛ «ЕМ, «ЕМ» ЕЕН В силу произвольности е поэтому !п1 зцр Р(х, у)( зпр 1п1 Р(х, у). ЕЕФ «ем» «ЕМ» УЕФ Но в силу леммы предыдущего параграфа всегда справедливо и обратное неравенство; тем самым теорема доказана. Следствие. Поскольку в множестве М„всегда есть абсолютно оптимальная стратегия х„, определяемая (169), или хотя бы е-абсолютно оптимальная х„' (для любого е > 0), то Р(х, у) всегда имеет хотя бы обобщенную седловую точку на М„х У.
Замечание. Пример Р(х, у)=ху при М,=М, = =[ — 1; !) =Ф показывает, что теорема, обратная Х1Ч, не верна; здесь нет е-абсолютно оптимальных стратегий при е ( 1, а седловая точка есть, ибо Ц,=О. Из теоремы следует также полезное утверждение о том, что если на М»хЛ~ нет седловой точки, то в М, нет и е-абсолютно оптимальных стратегий для некоторых е > О. Интересна и часто применяема на практике следующая теорема, устанавливающая достаточные условия для Ц„= О, т. е.
для того, чтобы было нерациональным применение смешанных стратегий даже при М =М„т. е. при 174 [гл. ш оптимллю!ые стглтегни отсутствии надежд на получение оперирующей стороной какой-либо новой информации о у. Теорема ХЧ. Если Р(х,у) вогнута и непрерывна по х на выпуклом ограниченном замкнутом множестве М, при люба!х убй!, и!о Р„=Р,. Доказательство. Согласно определению вогнутой функции для любых х, и хм принадлежащих М„имеем при 0(Л„О(Л„Л!+Л,=1: Х,Р(х„у)+ Х,Р(х„у) ( Р(Л,х, + Х,х„у), причем в силу выпуклости М, Л,х,+Х,х, Е М,. Отсюда следует, что если х„ х„ х, взяты из М, и Х,+Х,+ Х, = =1 при Х!)О, то з Х!Р(хо у)=Х,Р(х„у)+(Х,+Л,) [ ' Р(х„у)+ Ф=! .3"Э + — 'Р(х„у)1 (Л,Р(хо у)+(Л,+Л,) Р( ' х,+ Повторяя это по индукции, получим общее неравенство при любом и: ц ~ Л П Д Х!Р(хоУ)(Р ~ Д Х;ход); Х!) О, ~х.'~Х! — — 1.
(180) Пусть теперь задан закон распределения [(х). Разобьем М, на достаточно большое число и частей Ми' так, чтобы колебание Р(х, у) на М',о и сам диаметр М! не превышали е. Тогда при любых х;цМ,'ос:М, имеем ~ Р (х, у)!11(х) = ~ч; ~ Р (х, у) 4 (х) = м, !=! а! мо И л = ~ Р(хо у) ) 4(х)+ ~ ) (Р(хьу) — Р(х,у))Щ(х)( мв! !=!,иса о е б л (е ~ 4(х)+ ~ р!Р(хо у) = е+ ~ч'„р,Р(хоу), м 1=! к=! 175 5 151 ПОНЯТИЕ ОПТИМАЛЬНОЙ СТРАТЕГИИ Е гдеР! — — .~ е!7(х))0 и ~ р,=-!.
Поэтому в силу (180) ми) )=! Е / и ~ Р (х, У) Г!!' (х) ( е + Р ~ ~) Р;хо У) = м, )= ! Р11 е!)-*) — Х 1! — Уде!)4. )1, ~м, '=)ми) Е Отсюда из-за ]х — х! ~(е при хЕ Ме)!), переходя кпределу, получим 1 Р)*, ))е!)!)АР!1 е!)!), )] ми) ьмв (180') Отсюда следует, что при любом /(х) существует х„так что !п! ] Р (х, у) 4 (х) = ш! Р (х„у) ( зпр Гп! Р (х, у) = Р,.
УЕЧ У Е А) .к Е Мв У Е А) Но тогда и Р, = зар ш! ) Р (х, у) дЦх) ( Р, . г(Е! УЕФ Но всегда Р, ) Р'„, поскольку множество смешанных стратегий шире множества М, чистых стратегий. Сравнение двух противоположных неравенств и доказывает теорему. Простым примером вогнутых по хкритериевэффективности является критерий (5) в задаче об аппроксимации, где в качестве х выступает вектор а=(а„..., а„) коэффициентов полинома степени л.
Действительно, если а и Ь вЂ д таких вектора, то — (Х]Ь,+...-1-5„1" — )Я)+(1 — А)]а,+... +а„г„— 1Я]]( ( — ] А(Ь,+...+Ь„1- — 1(1)]+ +(1 — А) !а,+...+а„!" — ! (1)]~= =-] Ц)е+(1 — А)а, + ... + (Ц)„+(1 — "А)ае]!" — ] Я ], а это и доказывает вогнутость критерия. В теории игр величина Р, имеет особое значение; ее определению и посвящены основные разработки этой теории. 176 [гл. ш оптимлльныв стгатягии В силу теоремы ХЧ задача определения гпах гп)п 1 — ) (1) — ~ аггг ы-:-сжь г=о — ппп гпах~~(г) — ~~' аггг ь юг жь —, ! г=о может трактоваться как задача определения Р, для игры с платежом (5).
Существует, следовательно, тесная связь между задачей наилучшей аппроксимации Чебышева и теорией игр с вогнутыми по х платежами. Теоремы Х1Ч и ХЧ имеют «двойников», получающихся простой переменой мест между оперирующей стороной и «противником». Здесь уместно уточнить некоторые общие теоретико-игровые понятия. В теории игр совокупность множеств М и гЧ любых стратегий Р и Я с определенным на декартовом произведении этих множеств платежом ') — функцией 0 (Р, Я)— принято называть антагонистической игрой (в нормальной форме), если при этом сторона, выбирающая Р, стремится увеличивать О, а сторона, выбирающая 9, увеличивать ( — б).
Выражения зцр )п( гг(Р, Я) и !пг зцр 0(Р, Я) Р ем О «аг очаг нем называются соответственно нижней и верхней ценой игры; если они совпадают, а все верхние и нижние границы достижимы, то игра называется игрой с седловой точкой и общее значение максимина и мииимакса — ценой**) игры. В этих терминах теорема Х)Ч и ее следствие означают, что при соответствующем расширении множества стратегий М путем рассмотрения функций РЯ) игра станет игрой с седловой точкой с ценой, равной верхней цене исходной игры, если верхние и нижние границы достижимы.
Это, конечно, не единственная теорема подобного рода; в дальнейшем будет видно, что расширение обоими противниками множеств стратегий путем применения смешанных стратегий опять приводит к игре с седловой точкой. *) Вместо термина платеж употребляют и термиа выигрыиь *") Вместо термина цена игры часто употребляется, видимо, более правильный термин — значение игры (а также верхнее и нижнее значение). $151 ПОНЯТИЕ ОПТИМАЛЬНОЙ СТРАТЕГИИ лт Обратим внимание на «симметричность» игры относительно противников. Так, если взять за основного игрока (оперирующую сторону) второго игрока (распоряжающегося (г), то тогда критерий эффективности оперирующей стороны будет — 6(Р, (г) и потому п(ах пип [ — 6 (Р, (г)) = п(ах [ — щах 6 (Р, (г)) = е О Р = — пип щах 6(Р, (1), Р п(!пп(ах [ — 6(Р, (,()) = — п(ахпип6(Р, (1).
е е (181) Но тогда, применяя следствие теоремы Х1Ч к противнику оперирующей стороны, очевидно, получим следующее утверждение. Теорема ХЧ1. П(ах пипР(х, у) дает цену игрывигре ««Мв у«У Р [х, у (х)), где х Е М, и у (х) Е И,— множеству всевозможных функций у(х) со значениями из (Ч; вта игра имеет седловую точку и абсолютно оптимальную стратегию для противника. В этом случае оптимальные стратегии х, уже не могут быть, конечно, определены путем рассмотрения только максимума или минимума; нужно рассматривать максимин. Обратим внимание теперь на то, что если — 6(Р, Я) вогнута по (г, то 6(Р, (г), конечно, выпукла по (г.
Кроме того, забегая вперед, отметим, что по основной теореме теории игр, когда критерий эффективности Р(х, у) непрерывен по х и у, а М, и !(! выпуклы, ограничены и замкнуты, то Р,=ыр !п1 ) Р(х, у)(!(р(х)= 1п! Еир ) Р(х, у)йф(у). Ф(«) г«Ф Ф(ю»«мо Используя эти замечания, формулу (!81) и теорему ХЧ, немедленно получим следующеа Те орем а ХЧН. Если Р(х, у) вьшукла по у и непрерывна на выпуклых замкнутых и ограниченных М, и !Ч, то Р„=Р, и, следовательно, точная информация оперирующей стороны о у не мохсет иметь гарантированной положительной ценности Цр.
178 (гл. ш оптимлльныв стР»тзгии В этом случае, следовательно, если применение смешанных стратегий допустимо, то они уже и обеспечивают получение максимально возможной гарантированной эффективности г"„ хотя, как уже ранее отмечалось, и не обеспечивают, как правило, получения абсолютно оптимальной стратегии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
