Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 48
Текст из файла (страница 48)
(280) и Ф о а Покажем теперь важную, но почти очевидную лемму. Лемма 3. Если Р [х(и;), у(г~)] непрерывна по й= [иг), г = (гу) на прямом произведении замкнутых множеств Ею и Е„,то гпах ~ Р [х(иг), у(г~)] ЙР(и„..., и„) = = гпах Р[х(иг), у(г)]=пгахР(х, у), (281) смели; к гкг<Л пг!п ~ Р [х(иг), у(гу)] йг'„г (гг...г„) = е ппп Р [х(иг), у(г )] =пппР(х, у), (281') Пеег, з 1~/Ч"аг !п1 гпах Р(Р, Щ = !п1 гпах ~ Р [х, У (гу)] йгч' (г„..
г ) Р о з (282) зцргп!п ) Р[х(иг), у]йР(и,,и„)=зцрпппР(Р, !«). (283) з о *) Приведенные здесь формулировки не совсем совпадают с прнведеннымн там, но зто не имеет существенного значення. В указанной книге зтн леммы сформулированы для многомерного случая. 300 тьогнмы о гншнннн кнгкгоннстнчнскнх нгг 1гл. Ф Поскольку (281') совершенно аналогично (281), а (282) является прямым следствием (281), то достаточно доказать (281). Пусть в силу непрерывности Р точка х, =х(и,', ..., и'„) реализует тахР(х, у). Тогда, очевидно, к ~ Р(х (и ), у] ЙР (и„..., и„) (тах Р (х, у) ~ ЙР (и „..., и„) = к = — тах Р(х, у) =Р(х„у).
к Следовательно, и тах ~ Р (х(и,), у) ЙР (и„..., и„) ( тах Р (х, у). к Но, с другой стороны, взяв Р'(и„..., и„)=ДР;(и;), г=~ где Ру(иг) — функция, равная нулю при иг (икг и единице при и;)и',, получим ~ Р (х (и;), у] ЙР' (и„..., и„) = = )г... ~Р(х(и;), у) ЙР'(и,)...ЙР„'(и„)= = Р (х (иг), у) = Р (х„у) = тах Р (х, у) к и, следовательно, тахР(х, у) (тах ~ Р (х(и;), у| ЙР(и„..., и„). к Наличие двух противоположных неравенств и доказывает справедливость (281). Отметим, что лемма 3 есть не что иное, как очередное воплощение общего тезиса о нецелесообразности или необязательности применения смешанных стратегий, если известна стратегия (чистая нли смешанная), принятая противником. Перейдем теперь к доказательству возможности замены зцр и 1п1 на максимум и минимум.
Доказательство проведем только для простейшего случая лг= и=1 при Е,=Е,= =[О; 1), хотя результат верен и в общем случае. Ограничимся в виду полной аналогии доказательством достижим ости 1 !п1 тах Р(Р, Я) =!п1 тах ~ Р (х, у (г)) ~Ц (г). Р О к к $23] основнля твоннмл длн нннннтынных нгР 301 По определению нижней границы имеется последовательность стратегий Яг= Яг(г) такая, что 1пп гпахР(Р, Яг) =!п1гпах Р(Р, Яг).
Г а Р Р В соответствии с сформулированной выше леммой 1 последовательность (гг может считаться выбранной так, Чтс Яг(Г) СХОднтея К НЕКОГОрОЙ До(Г) ВО ВСЕХ тОЧКаХ непрерывности последней функции. Платеж Р (х) = ) Р [х, у (гЦ Що (г) о непрерывен по и вслед за непрерывностью Р [х(и), у(гЦ, и, следовательно, к нему можно применить лемму 3. Пусть хо таково, что 1 1 ) Р [х„у(г)[ гЦ,(г) = игах ) Р [х, у (г)) г(Я, (г) = о о Г1 =гпах ~ Р [х(и), у(гЦ ггР(и) Щ (г). о По лемме 2 получим 1 1 1пп ) Р [х„у (гЦ ганг(г) = ) Р [х„у (гЦ г( Я о (г). Поскольку для любого 1 1 1 ~Р[х„у(гЦЩг(г)(гпах) Р[х, у(гЦЩ(г), о о 1 1 ) Р [х„у (гЦ гЦ, (г) ( 1пп шах ) Р [х, у (г)) Щ (г) = о 1- =1йп шах Р(Р, Щаа 1п1 гпахР(Р, Я), ! а Р Р и в силу определения хо игах Р(Р, Яо)(ш1 шах Р(Р, ()).
е 302 тгоггмы о гашении кнтлгоиистичаскнх иге (гл. ьт Поскольку, с другой стороны, всегда имеет место обратное неравенство, то Я, реализует 1п1 тах Р(Р„ Я), и, Р следовательно, верна следующая основная теорема теории непрерывных игр. Теорема Х1.1. Если игра с плагпежом Р(х, у) задана на множествах стратегий М и л1, являющихся образом соответственно и-мерного и и«-мерного кубов 0 < и; < 1; 1<1<я; 0<с <1; 1<1 <гп, и если функция Р (х(и,...и„), у(г,...г„)] является непрерывной функцией по всем пеРеменным сц и гу в совокУпности, то !п1 зцрР(Р, ф и зпр 1п1 Р(Р, Я) достижимы и Р Р шахт!пР(Р, Я)=тех ппп ~ Р (х(и;), у] йр(и,...и„)= Р о Р У =ппп шах ( Р (х, у (гт)] ИЯг,...
г„) = т!п тах Р (Р, Я). (284) В формулировке (284) заключены сразу аналоги собственно основной теоремы матричных игр (273) и теоремы ХХХ1Х, а именно равенств (276). Введение связи стратегий х и у с вспомогательными й и г потребовалось выше для того, чтобы избежать затруднений, связанных с введением понятия смешанных стратегий в абстрактных пространствах, а также и для построения аппроксимирующей матричной игры. $ 24. Решение матричных игр Решением игры называется определение ее цены (значения) и оптимальных смешанных стратегий. «Минимальная» игра получается, если у оперирующей стороны есть только две стратегии, между которыми надлежит сделать выбор или оптимальную смесь которых нужно определить.
Так возникают матричные игры 2хш с платежной матрицей з 24! гашение млтгичных иге Зоб Поскольку т отражает богатство стратегий противника, то здесь трудно рассчитывать на малые значения, особенно, если рассматриваемая матричная игра есть аппроксимация игры с платежной функцией Р(о, у), где о=1; 2. Как уже говорилось ранее, оперирующая сторона может ограничиться рассмотрением только двух стратегий, но не может предполагать то же относительно противника. Ситуация с наличием лишь двух конкурирующих стратегий оперирующей стороны отнюдь не является надуманной и возникает довольно часто, если нужно, например, оценить выгодность какой-либо технической новинки.
Это производится путем сравнения ее с аналогичным (наиболее близким) старым образцом или комплектом старых образцов, заменить которые может рассматриваемая новинка. Решение нгр 2 хт удобно проводить графическим методом. Применение оперирующей стороной смешанных стратегий при чистых стратегиях противника приводит к платежу Ра;+ (1 — Р) Ь,, где 0(Р (1, а ( — номер стратегии противника. Согласно теореме ХХХ1Х о двойном описании игры нахождение цены игры и оптимального РДравносильно решению уравнения т!п (Р а;+(! — Р,)Ь,)=гпах гпш (Ра;+(1 — Р) Ц, 1<!<т Р ! <1<~и но ш!и ~Раг+(! — Р)ЬД =ср(Р) 1<акт есть вогнутая полигональная функция, которая легко получается графически при нанесении на один и тот же график всех линейных функций Ра,+(1 — Р)Ье Любое максимальное значение ~р(Р,) этого полигона и есть цена игры, а соответствующее Р, дает одну из оптимальных стратегий оперирующей стороны.
Если полигон ~р(Р) содержит целый отрезок, проходящий через точку (Р„ф(Р,)) и параллельный оси Р, то весь этот отрезок н дает оптимальные стратегии; 'иначе, оптимальная стратегия единственна. Отсутствие других 304 теОРемы О Решении антАГОнистических иГР (Гл. Вт оптимальных стратегий следует из вогнутости ф(Р). Если Р,=О или 1, то оптимальна чистая стратегия*). Собственно этим и закончено решение игры для оперирующей стороны, поскольку ее интересует нахождение ее оптимальной стратегии и ожидаемого наилучшего гарантированного результата, т. е. цены игры. Однако некоторый интерес представляет и нахождение оптимальной смешанной стратегии противника.
В данном случае эти стратегии также очевидны: а) если Р, = О, то противнику выгодно применять чистую стратегию, соответствующую прямой, проходящей через точку (О, ф(0)) и при этом имеющую наименьшую производную (т. е. наибольший отрицательный наклон), поскольку Р,=О реализует максимум ф(Р); б) если Р, = 1, то оптимальна для противника опять чистая стратегия, соответствующая номеру прямой, имеющей наибольшую производную (т. е. наибольший положительный наклон), нз числа проходящих через точку (1, ф(1Н; в) если 0 < Р, (1, то у противника имеется оптимальная чистая стратегия только при наличии проходящей через !Р„ф(Р,)) прямой, параллельной оси Р; ее номер и есть оптимальная чистая стратегия.
Если такой прямой нет, то любая пара прямых аГР+(1 — Р)Ь,:, а~Р+(! — Р)Ьу, проходящих через (Р„ф(Ра)) и имеющих одна положйтельный, а другая отрицательный наклон, дает оптимальную смешанную стратегию д;=1; ду — — 1 — 1; д„=О при т~1, 1, как только 1 удовлетворяет уравнению 1(а; — Ь;)+(а — Ь )(1 — 1) =О. Прн этом платеж, очевидно, не зависит от Р и равен ф(Р,), т. е. цене игры.
Существование такой пары следует из того, что гр(Р,) есть максимум полигона ф(Р). Поскольку решена игра 2хгл, то, конечно, решена н игра типаТпх2. Однако этот случай в силу сказанного ранее маловероятен, ибо соответствует только двум стратегиям у противника. Перейдем к рассмотрению общего случая матричной игры ЛХт. *) Поиск шах ф(о) легко, конечно, производить и на ЭВМ., пользуясь, например, алгоритмом Кифера — Джонсона, ф 241 гашение мктгичных игг 305 Как уже говорилось, множество оптимальных смешанных стратегий для каждого игрока есть выпуклое замкнутое мнржество, заведомо ограниченное неравенствами 0 ( Р;(1.
Ка)! известно, это множество вполне характеризуется указанием его крайних точек. Имеет место Лемма. Замкнутое ограниченноемножество Х натянуто на свои крайние точки, т. е. каждая точка хЕ Х Г / г представима в виде х = ~)!„х!"! ( 1!г)0; ~ч~ ~3,„= 1 где х'"' — крайние точки. Мы не будем доказывать атой леммы (хотя она и не сложна), поскольку с развиваемой здесь точки зрения нет особой необходимости знать все решения игры; достаточно знать хоть одно решение, ибо все они относительно данной операции (игры) равноценны.
Так же, как и в случае линейного программирования (см. доказательство теоремы 1Х), удобно искать именно крайние решения игры, которые наиболее просто описываются. Используя же приведенную лемму и зная все крайние решения, всегда можно получить достаточное представление о всем множестве оптимальных решений. Пусть теперь Р,=(р'„..., Рч) и 9,=(д'„..., д')— оптимальные крайние стратегии оперирующей стороны и противника, а о пусть будет ценой игры с матрнцей 11 ау 11.
Имеем по теоремам $22 ппп ~ а;~р1 = о, !К!< к !=! !пах ~~'„а!ф = о. !к!кау=! Предположим, что строки и столбцы перенумерованы для Р, и Я, так, что первые ) от 1 до г(т дают и П$ ~~Р~а,,р1 = о, и также для первых ! от ! до Й ( и ~~~~ а,,д) = о; !=! /=! в то же время для всех 1' > г ~~р~а;,рч > о, а для 1>)! != ! соответствующие суммы меньше о, 306 теоРемы О Решении АИГАГОнистических иГР (гл, оч Тогда имеем совокупность равенств и неравенств л лг ~а;;р1=о, 1'<г; ~а!т!1ф=о, Г<й; ДИ=1, ~ф~=1, л гл ;Я~ а;~р~ > о, 1> г; ~ а!ф < о, ! > й. 1=! Т=! Пусть теперь е > О таково, что / л т!п ~ ~ч'.,а!~р1 ) о+е, лгж/> г+ ! ! ! / гл шах ~ Х а!Тд~ < о — е.
лВ!~АР! В силу теоремы ХХХ1Х имеем р1=0 при Г>й и ф=О при 1>г. Таким образом, для определения оптимальных стратегий будем иметь системы уравнений А г ~~'.,а! ру=о, 1<г; ~.'~аГф=о, Г<й; г=! Т=! А г ХИ=-1,Хр~=о (266) Г=! г=! при одновременном выполнении (285). Докажем теперь, что всегда г=й, а если очьО, то и (," "',", о. если, конечно, Р, и До †крайн оптимальные стратегии. Предположим сначала, что гчьй, и пусть, например, й > г. Тогда в системе уравнений ~агбар~=о1 1'<г, Г=! число уравнений меньше числа неизвестных и в матрице % 241 Решеа1ик мАтРичных иГР 307 число строк больше числа столбцов; следовательно, между строками есть линейная зависимость. Рассмотрим систему относительно величин а; А А ~а!г(1+а!)р)=о, 1(г, ~,'(1+и!)р)=1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
