Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 46
Текст из файла (страница 46)
Покажем, что этот минимум не превосходит Т,. В нервом случае это следует из (262), поскольку р(т)=0. Возьмем теперь при т > Т;! р, (!) = 1 при ! ( Т, — е, р,(!)=а при Т,— е(!()„ р,(!)=О при ! > 1,. Имеем Т,=-(! — а)(Т,— е)+а)„ Т;+ Р, = (1 — а)(Т,— е)'+ аф Отсюда Г! — а Т,— аТ,— Ъ~а(! — а) Р, Т вЂ” е= Устремляя а к О, имеем 1,— оо, (Т,— е) — Т,. При этом (262) для т' Т, дает Т (т, р,(1Ц =(Т,— е)+а(т — Т,+е)+аТ„ т.е. Т )т, р ° (!)) стремится к Т,. Теперь осталось только получить сам максимин.
Поскольку т=О и т=оо обеспечивают всегда получение платежа Т„то рассмотрение т ) Т„т > 1, интереса не представляет. То же относится к случаю, когда ие выю(267). О (М 7,'— Р,. М Н теж равен (268). Производная этого выражения равна (Т1 — т)~ — 2Р~т (Т вЂ” т)-1- Р1 1(Т1 — т)'+ Р11' При т=О она положительна; следовательно, т выгодно увеличивать до значения, получающегося из решения уравнения (Т, — т)' — 2 Р,т (Т, — т) + Р', = О.
(269) Т Т' т(Т,— т) ие превосходит — '; поэтому, когда О,>— 0,'— 20,т(Т,— т)) О, и, значит, (269) не имеет решения; тогда т выгодно увеличивать до )ГТ,'— Р, и далее до Т„ что не дает, впрочем, платежа, большего Т,. 288 (гл, ш оптимальные стглтегии Итак, при Р,) 0,5Т' наивыгоднейшими т остаются заведомо 0 и оо, а наилучший гарантированный платеж равен Т,.
Здесь следует обратить внимание на то, что при т=О имеет место разрыв. Если с = О, то (262) дает при р(0) = 1 Т,. Однако при т — 0 гарантированный платеж в силу (268) стремится к Т,— —, о,т, т'+р ' При малых Р, (269), очевидно, имеет решение. Его можно приближенно получить, отбрасывая члены высшего порядка малости по Р„т.е.
Р,', и полагая т=Т,; тогда (Т вЂ” то)' ж 2Т,Р, н Т,— тв ж ~~12Р,Т,. (270) Платеж при таком т (гарантированный) по (268) будет 3 Р, У е ~ з г ) т,' Уже при Р,= 1а включение второгоэлемента по (270) в момент т,= — (хотя это и не точно оптимальное т) т, даст Т, равное 1-Т„т.е. заметно больше, чем Т,. 1з Таким образом, доказано следующее предложение: Если уравнение (269) не имеет решений, как, например, при Р, ) 0,5Т'„то оптимальными стратегиями включения дублера являются т= О или т =- оо (т.
е. будет работать только один из дублеров). Если лсе решение у (269) есть, то наименьшее из них и дает оптимальный момент включения, гарантирующий получение среднего времени безотказной работы не меньше, чем (268). При Р, 0 оптимальный момент включения стремится к Т„а среднее время работы дублеров — к 2Т,.
При доказательстве этого предложения возникает, естественно, идея использовать теорему ХХЧ1. Однако при этом придется преодолеть затруднения, связанные с априорной неограниченностью интервала изменения т и компактностью пространства р(1). Эти затруднения, видимо, 289 э 21) примеры млкснмивов в мивимлксов преодолимы; так, например, выше была показана возможность рассмотрения лишь т(Т,. Путь, выбранный выше, хотя и несколько громоздок, но значительно более элементарен. В то же время использование теоремы Х является полезным примером приема, который может быть использован почти во всех случаях игры против «природы», если ее поведение описывается случайностями.
Вычисление минимакса для этой задачи нельзя выполнить на основании теоремы Х или теорем 5 17. Однако задача о вычислении минимакса в чистых стратегиях эквивалентна решению задачи в смешанных стратегиях относительно т и в чистых — по р(1). Это следует из линейности критерия по р(1). Если поэтому искать оптимальную гарантирующую стратегию природы (наихудшую стратегию для оперирующей стороны), то следует рассмотреть платеж — ~ р(г)Ю вЂ” р(т) Т, и искать для него максимин. Линейность платежа по р(1), а, значит, и вогнутость его по р(1), позволяет на основе теоремы ХЧ утверждать, что здесь максимин совпадает с ценой игры, т.е. можно рассматривать смешанные стратегии только по т. Определение цены игры будет проведено в следующей главе работы.
Здесь мы говорили о линейности и вогнутости платежа по р(1), т.е. по функции, хотя теорема ХЧ сформулирована для векторов. Однако это обстоятельство несущественно, поскольку монотонную функцию р (г) всегда можно сколь угодно точно заменить кусочно-постоянной функцией, то есть вектором. Возможность такой приближенной замены игры и соответствующего предельного перехода следует по существу из 9 18.
1о ю. в. гермевер ГЛАВА 1Ч ОБЩИЕ ТЕОРЕМЫ О РЕШЕНИИ АНТАГОНИСТИЧЕСКИХ ИГР В СМЕШАННЫХ СТРАТЕГИЯХ 5 22. Основная теорема теории матричных нгр н свойства оптимальных стратегий Пусть дана платежная матрица (матрица эффективности) ~~а;~)~; Г<л; 1(т, % (Р, Я)=~ч~', Д агыр;д . (271) Это уже критерий эффективности в непрерывной игре на выпуклых множествах М и )Ч стратегий Р и Я соот- ветственно. элемент а,г которой дает значенне критерия эффективности при применении первым игроком (оперирующей стороной) (-й стратегии (1 строки матрицы) н вторым игроком (противником) †(ьй стратегии.
Представленные в таком виде игры с конечным числом стратегий (л н т) у обеих сторон обычно называются матричными. Изучение матричных игр необходимо потому, что они в некотором смысле наиболее просты и в то же время к ним могут быть приближенно сведены игры более общего вида. Если в игре прн выборе своих стратегий оба игрока не имеют информации о выборе другого, то для них имеет определенный смысл применение смешанных стратегий. Смешанная стратегия первого игрока, т.
е. вектор Р=(РД (прн 1(л), где р,— вероятность применения нм л (-й стратегии, прн условии ~р~ — — 1, и аналогичная смеГЫ1 шанная стратегия второго игрока Я = (д~) (1 (т) определяют математическое ожидание платежа Й 221 СВОЙСТВА ОПТИМАЛЬНЫХ СТРАТЕГИЙ 29! Множества М и Ф определяются условиями (272) Напомним, что игра (271) — (272) по определению имеет седловую точку, если Гпахппп РР'(Р, О)=ш!Пгпах К'(Р, О). (273) Р»м о»н СЕН РЧМ Теорема ХХХЧП1. (Основная теорема матричных игр фон Неймана).
8 игре (27!) — (272) имеется седловая точка, Гп. е. выполнено (273). Иначе, любая матричная игра имеет седловую точку в смешанных стратегиях. Доказательство. Прежде всего, М и й( замкнуты и ограничены из-за 0<р;<1, 0<от<1, а функция (271) непрерывна по Р ЕМ и Я Е ГЧ.
Далее функция (27!) линейна по Р при фиксированном Я, и наоборот; значит, она является вогнутой по Р при фиксированном Я и выпуклой по Я при фиксированном Р. Наконец, множества М и й(, очевидно, выпуклы, ибо если, например, Р и Р' удовлетворяют (272), то и ХР+ (! — Х) Р' также удовлетворяют (272) при О < Х < 1. Но тогда в силу теоремы о вогнуто-выпуклых критериях из 9 16 игра (27!) — (272) имеет седловую точку, что и требовалось доказать.
Множество оптимальных смешанных стратегий оперирующей стороны (равно как и противника в антагонистической игре) является, очевидно, выпуклым и замкнутым. Основные свойства оптимальных смешанных стратегий содержатся в следующей теореме. Теорема ХХХ1Х. Пусть Р' и Я' — оптимальные смешанные стратегии, а о — цена игры, т. е.
величина (273). Оптимальная смешанная стратегия оперирующей спюроны Р' = «р'„..., Р») состоит только иэ тех чистых стратегий ! (т. е. толысо те р, 'могут быть отличны от нуля), для которых (274) 2~ ь У 10» 292 тзогзмы о гешзнии кнткгояистичзских иге (гл. !ч Аналогично, только ом !7! могут бьинь отлична от нуля, для которых Х «р)=' (275) !=1 Имеет место равенство пнп ~; а«рл! = так ппп г„а!7 р! = !<у<т!-! Р !;.
! < л! ! = ! =ппп шах Ха! О!лл шах Х а«дл!= !<!<лГ=~ !<!<л7=~ = шах ш(п ((У (Р, Я) = ш(п шах УР(Р, Я) = о. (276) е е Доказательство. Прежде всего, так как (Р', Ял) является седловой парой, имеем йу(ро Ол) '~.' ч;~, ! !=!с=! шах ~~',а! дл!) Ха!~д) (при 1<!(л), (277) !<<!<л,=! Г='! так как чистые стратегии (р!=1, рь — — О при й~!) составляют часть общего множества смешанных стратегий. Предположим теперь, что для какого-то ю, р!ь, > О, но ~,'а!дд) < о.
(278) у=! Умножая левые и правые части неравенства (277) для ! чь !, на р1 и сложив их, имеем 'Ц а рл у),-- !л:1, ! — ! Умножив также и (278) на р~! и прибавив к только что полученной сумме, придем к л л! л ~~ Да«рл!ц~ <о Д р7=о. Но зто противоречит тому, что о =Тl(Рл, Ял) и, следовательно, справедливо (274). Аналогично доказывается и (275).
ф 22! свойства оптиилльиых стглтвгий 293 Теперь уже очевидно, поскольку есть хоть одно р! ) 9 (из-за ~ р, '= !), что из (277) и (274) следует ог шах ~ ац 1)!=о. 1 <! < л т=! Точно так же из аналога (2?7) л о < ~~ ац Р), ! < !' < 1и, 1= ! и (275) следует ппп ~ а; р,'=о. ! <1<гл1Ы! Имеем далее, что лл л е /л ~~', ~ ацр1 д/= ~ Я ацр; д/) / л т л ) пип (~~~ ацр1),~! !7/ — — ппп ~ а1/р; !<ш 1=! т=! /(~и! 1 и, следовательно, л л ппп ~~,'! а, р; < т!п ч~'~ ~ч'., а1 р, р .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
