Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 53
Текст из файла (страница 53)
Из этой связи следует, что для нападения можно ожидать сохранения оптимальных стратегий, поскольку они и в задаче (322) состояли только из чистых концентрированных стратегий. Если согласиться с этим предположением, то оптимальная стратегия первого игрока (нападепия) для (325) должна быть: 1-я чистая стратегия имеет вероятность Р)= (326) 1 (! — а1) ~ ~' 1 — аз 1=! Взяв такую смешанную стратегию, получим при любой чистой з-й стратегии второй стороны платеж: !Фа ч 1 ч~ 1 (1 — а1) à — (1 — аг)~ 1 — ау ! — ау который оказывается, как и следовало ожидать, независимым от з.
Предположим в силу симметричности матрицы (325), что стратегия (326) оптимальна и для второго игрока. Взяв эту стратегию, опять получим для любой з-й чистой стратегии первого игрока платеж (327). Но тогда этим и доказана оптимальность стратегии (326) для обоих сторон. Цена игры равна величине (327). Сравнивая эту игру с (322) при У =и и р!(1, приходим к выноду, что ограничение стратегий лишь концентрированными распределениями сил, без изменения цены 334 ткогкмм о гкшкнии лнтлгонистичкскях игг [гл. (т игры, приводит только к замене чистой стратегии защиты (324) на совпадающую с ней по написанию смешанную стратегию, где настоящее распределение сил, пропорцио- 1 нальное величинам о , трактуется уже как вероят- 1,( р ность направления всех сил защиты на (-й пункт. Но тогда, конечно, в самой задаче (322) наряду с чистой оптимальной стратегией (324) при М=л имеется еще и указанная смешанная оптимальная стратегия.
Эти стратегии эквивалентны по результатам, если имеются условия, разрешающие защите применять смешанные стратегии (т. е. у нападения нет информации о выборе чистой стратегии защиты), и если согласиться с осреднением результатов по вероятностям. 1Ч.
В качестве четвертого примера решения игр возьмем уже разбиравшуюся задачу о поиске оптимального момента т включения дублирующего элемента (см., например, $ 21). Платежом в этой задаче является функционал Т [т, р (1)]= ~ р(1)й+р(т) Т„(328) о где р(1) — стратегия природы (закон надежности первого элемента), подчиненная ограничениям Ф ОЪ ~ р(1)(11 =Т,; 2 ~ 1р(1)((1=Т,'+О, (329) о о при условии Р, < Т',. Поставим задачу: нужно получить максимин в смешанных стратегиях оперирующей стороны и попытаться определить оптимальную стратегию, т. е. функцию распределения Ф„(т), для которой Ф Ф (п1 ) Т [т, р(1)](Ю,(т) = зпр 1п1 ~ Т [т, р(1)]((Ф(т).
о(о о Ф(г) о(О о Решение этой задачи проведем на основе не совсем строгих рассуждений. й 261 ПРИМЕРЫ РЕШЕНИЯ ИГР 335 Пренще всего рассмотрим только р(1), имеющие вид р (1) = р (1;) при (;, ( 1 ( 1Ь причем 1 = 1, 2, ..., и и 1~— фиксированы. Тогда (328) приобретает вид ~ а;р(1;)+р(1,)Т„ (330) Ь<л где 1, — наибольшее из 1; ( т. Вместо (329) получим условия вида л л ~ а;р(1;)=Т;, ~.", Ь!р(1;)=Т,'+Р,.
(331) Как следует из $ 21, рациональные т ограничены. Множество стратегий природы р=(р(11), ..., р(1„)», удовлетворяющих (331), очевидно, ограничено, замкнуто и выпукло. Платеж (330) линеен по р, а, значит, и выпукл при любом фиксированном т. Согласно теореме ХЧП игра (330) имеет оптимальную чистую стратегию природы. Это обстоятельство сохранится и при переходе к пределу, когда л оо и шах (г';+,— 1;) О, т.
е. для игры (328). 1<~< л Таким образом, нужно искать седловую точку (Ф, (т); р, (г)» в игре с платежом (Ф(0) =0; Ф(оо) =1): 60 Ф Ю ~Т (т, р (1)» НФ (т) = ~ ~ р Я г(( йФ (т) + Т, ~ р! (т) бФ(т) = о оо о л Е О 1 = ~ » Т, — ~ р (1) Ю~ ИФ (т) + Т, ~ р (т) ИФ (т) = о о ОФ 60 =Т,— ~ Ф(т)р(1)й+Т, ~ р(т)о(Ф(т) = о о Ф =Т,+~»Т,Ф'(т) — Ф(т)) р(т)Ж (332) о при ограничениях (329). Если (Фо(т) Рл(г)» — седловая точка для (332), то: 1) Ф,(т) реализует для неубывающих Ф(т) с Ф(0) =0; Ф(оо)=1 шах $1Т,Ф' (т) — Ф (т)] р„(т) Ж; (333) Ф (о о 336 ТЕОРЕМЫ О РЕШЕНИИ АНТАГОНИСТИЧЕСКИХ ИГР [ГЛ. (Т 2) ро(г) реализует для невозрастающих р(1), удовлетворяющих р(0)=1; р(оо)=0 и условиям (329), т!и ')(Т,Ф~(т) — Ф,(тЦ р(т)([т. (334) РП) о Решим обе эти задачи, используя принцип максимума Понтрягина (см.
В. Г. Болтянский «Математические методы оптимального управленияо). 1. Положим и(т)=Ф'(т); — „'=и(т); — „'=1 (х,=т). (Ьо . (Ьо Тогда (333) приобретет вид ор тпах $Ч,Т,М(т) — х,(т)) р (т)([т, (336) и(о)~0 Е причем х,(0)=0; х,(оо)=1; х,(оо)=0; х,(0)=0. Гамильтониан равен Я=о[)о'[Т,и — хор,(т)+)[), и, (336) .р- - о.>о;Ро =р.(.)о;, о,-о.[[р.(р)а(-.1.
Отсюда я.'=о,[[р,( )т,-(-[р,(()и(. ~ — *,р,()~ . (337) о Выражение (337) при р,(т)Т,+) ро(1)([[+с)0 не о имеет максимума по и. Поэтому должно быть при некоторой с: ро(т)Т,+ ~р,([)([[+с(0. (338) о Для тех т, при которых в (338) имеется неравенство, оптимальное и = Фо (т) = О. (339) Итак, все т разбиваются на две категории: или выполрено (339) или в (338) имеет место равенство; интегрируя, 337 в 261 ПРИМЕРЫ РЕШЕНИЯ ИГР имеем Е р,(Г)й+с=с,е г., о т. е. ре(т)=с1е г' (340) 2.
Положим и = р (1); 0 ( и < 1; .Е, = '» Р (1) й; х,= 2 ~ х, (1) й; — „д = 2х,; х, (0) = 0; о Ю ф Ф х,(оо)=2)х,(Г)й=2) ~ р(1)ййт=Т,*+Р. о Е Е Тогда, поскольку отыскивается минимум, Я= — ~р,(Т,Ф;(т) — Ф,(т)»и — ф~и+ф, 2х,. — „' = — и; х,(0)=Т;, х,(со)=0; ит Здесь ф,)0; +'= — 2~),; +=О. Отсюда М . ~Ив ,Рс = — и (ф, (Т,Ф; (т) — Ф, (т)»+(с т+ с,)» — с,х,. (341) (342) то и=р,(т)=0; в) максимум (341) достигается при любом и, если для некоторых ф, > О, с, и с, ь|~, '1Т,Ф; (т) — Ф, (т)» + сРЕ+ с, = О, т.
е. Ф,(т)=йгг +с,'т+с'. (344) Максимум этого выражения достигается при следующих и=р,(т): а) если ~>, »Т,Ф;(т) — Ф,(т)»+с1т+с, (О, то и=р,(т)=1; б) если 1р, »(Т,Ф;(т) — Ф,(т)»+с,т+с, ) О, (343) 338 твогеиы о вешании антагонистических иге [гл. ш Ф,(т)=0 при т( т, Фо (т) = г ~1 — Й (ет — ета + Ь (ет ег, ~ (346) при т,(т«т„ СРе('г)=1 при т>т,. Осталось определить т, и т, из условий (329); подставляя в них (345), получим гс-ч[ ,+Т, '[[ — ° )' =-Т„ тз-и1 та и т',+2тТ,(1 — е г ) — 2(т,— т)Те г те- И ~ +2Т,'~1 — е ' (=Т,'+Р,. (347) Введем г = — '' и преобрузуем второе из условий т, (347) с учетом первого: Т;+ Р, = 2Т,'— 2Т',ге-* — Т,'е-'* Отсюда получаем 1 — е-" — 2ге '= — '; ти ' т,=Т,е ', т,=т,+гТ,. (349) Уравнение (348) имеет решение только при Р,(Т',. При Р,=Т', г= со; т,=О' те= оо' ро(1) =е- ~т, При Р,=О г=О; [ 1 прн 1<Т„ О 1 Т.
Поскольку р,(1) не возрастает, а Ф, (1) не убывает и обе заключены между 0 и 1 так, что р,(0) = Ф,(оо) = 1; р,(оо)=Ф,(0)=0, то, объединяя все сказанное, имеем для оптимальных р,(т) и Ф,(т): существуют т,>0 и т,)~т, такие, что Ра(т)=1 — при т(т, Ре(т)=е ' при т <т<т (345) Ре (т) = О при т >т„ 6 26! пгимагы гашения иге 339 Определим теперь цену игры, т. е.
интересующий нас максимин. Она, очевидно, должна быть равна гпах Т[т, р,(1)), где Т[т, р(1)1 задано (328). О~т~ Ф Имеем при т(т,: Т [т, р,(1)) =т+Т,(т,+Т,", при т,(т(т,: т — тф Т[т ра(1)) =т, ',-Т, [1 — е г '1 -1-е т, Т,=т,+Т, при т>т,: та-т,1 Т[т, ро(1))=т,+Т,(1 — е т ) <Т,-1-т,. Отсюда получаем цену игры о= пшх Т[т, р,(1))=т,+Т,=Т,(1+е-*), (350) 0<т< ~ где г определяется из (348); о меняется от Т, до 2Т, при уменьшении 1У, от Т, 'до О. Из сказанного ясйо также, что в оптимальной смешанной стратегии Ф,(т) должны участвовать только чистые т из интервала (т„т,); это совпадает с определением Ф,(т) по (346), ибо Ф'(т) =О при т < т, и т >т,.
Из (346) следует, что необходимым условиям оптимальности удовлетворяет целое семейство стратегий Ф,(т), зависящих от параметра Й. Полный ответ об оптимальной стратегии Ф,(т) можно получить, видимо, так же, как и в 3 21, находя для каждого фиксированного и (и значит, Ф,(т)) пцп ~ Т [т, р(1))ЙФ,(т) =п(а) еш о и затем шахи(е). Определение п(А) можно произвести, используя опять-таки теорему Х, согласно которой достаточно искать минимум (см.
3 21) по таким р(1), для которых только три точки имеют вероятности, отличные от нуля. Зля того чтобы иметь возможность использовать 340 ткогкны о гкшкннн лнткгоннстнчкскнк нгг [гл. ю теорему Х, достаточно обратить внимание на выражение ~ Т [т Р (()1 о[~~'о (т) = о О~ =[( и- .оп~-[~ ~го .оф~ — оя о о Итак, рассмотрев [Ч пример решения игр в смешанных стратегиях, мы выяснили, что в задаче о выборе времени замены элемента с заданным Т, и Р, (Т', целесообразно использовать смешанные стратегии, т. е.
производить замену в случайные моменты времени. При оптимальной смешанной стратегии можно рассчитывать на среднее время работы элемента н его дублера (350), что превосходит оптимальное гарантированное время при использовании чистых стратегий (см, ~ 21). Разумеется, если у оперирующей стороны будет информация о г', то оптимальной (мнннмаксной) стратегией будет т=1, что даст среднее время работы 2Т,) Т,(1+к-'). Однако не всегда можно рассчитывать на эту информацию, дающую не очень большую выгоду при малых Р,(Т,*.
УЛАВЛ Ч ИГРЫ 0 ПЛАТЕЖНЫМИ ФУНКЦИЯМИ ЧАСТНОГО ВИДА и 27. Игры с разделимой платежной функцией и конечные выпуклые игры Под игрой с разделимым платежом (илн вырожденной игрой) понимают игру с платежной функцией л ш Р(х, у) = ~~",,У, 'а! г,(х)з (у), ! =1 з=! где х и у изменяются на отрезке [О; 1], а го(х) н з (у) непрерывны на этом отрезке. Частным случаем(351) являются полиномнальные игры с платежом ч~~ ~~.", а! х!у~. В литературе по теории игр уделяется довольно много внимания решению игр (351) в смешанных стратегиях. Изложим основные, связанные с этим идеи.
Пусть 1(х) и д(у) — смешанные стратегии. Обозначим через а! и ]17 обобщенные моменты 1(х) и й!(у): ! ! а, = ~ го(х) Щх) Р~ — — ~ з!(у) Иа(у). (352) о о Легко увидеть, что для смешанных стратегий 1(х) и й!(у) платеж в игре (351) может быть выражен через а! и ()~ в виде и я Р(1, у)= ~ ~~.", а!,а!]1~ —— Р!(а, р). (353) Обозначим множество возможных векторов а = (а!], получаемых при всевозможных 1(х), через и. Аналогично введем множество о векторов () = (р ]. Множества и и о есть соответственно множества л и ло-мерных пространств. Эти 342 нггы с платежными чтнкцяямя члстного вяла [гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
