XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 47
Текст из файла (страница 47)
2. На рис. 8 7 выделенная ломаная линия АМ%В определяет максимальный гарантированный проигрыш второго игрока независимо от действий первого игрока. Таким образом, согласно минимаксному критерию, Отметим, что графический метод позволяет находить не только ожидаемую цену игры и оптимальную смешанную стратегию одного из игроков, но и оптимальную смешанную стратегию другого игрока, т.е. полностью решить исходную задачу. Действительно, рассмотрим игру двух участников с нулевой суммой, в которой первый игрок имеет две стратегии и 8.3. Решенне нгр с нулевой суммой в смешанных стратегиях 339 нет седловых точек.
С помощью графического метода мы можем определить ожидаемую цену игры и* и оптимальную т смешанную стратегию первого игрока в~, — — (р[* рз*) . На рис. 8.8 изображены три возможных принципиально различных варианта ломаной, отражающей минимальный гарантированный выигрыш первого игрока. Пусть анализируемая ломаная имеет горизонтальный участок, соответствующий стратегии Х, второго игрока (см. рис.
8.8, а), что возможно лишь при 2 П1 — — Пз . В зтом случае р'" может принимать любое значение из отрезка [се,Я) С [О, 1), а второй игрок имеет единственную оптимальную смешанную стратегию, которая является чистой 8. ЭЛЕМЕНТЫ ТЕОРИИ ИГР 340 тахппп П;. = ппп тахП;.. » и*= пппП;,, 1 т я и* = ~» ~~1 р;*р *П;;, »м» 1м! и" = ~ р„"Пг1 стратегйей Хз. Отметим, что из равенств П»3 = Пгй .1 = 1~ и вытекает равенство Значит, ломаная на рис.
8.8, а соответствует игре двух участников с нулевой суммой и с седловой точкой, не представляющей интереса для нас. а Предположим теперь, что ломаная является „пиковой с абсциссой, равной 0 или 1 (см. рис. 8.8, б). Для определенности ограничимся случаем пиковой точки (О;и*), которой соответт ствует оптимальная смешанная стратегия в* » = (О 1) первого игрока, представляющая собой чистую стратегию.
Ожидаемая цена игры и* есть ожидаемый выигрыш первого игрока. Так как в данном случае гп = 2, р, = О, рз* = 1, то » 1* т.е. существует такой номер 1в, 1 < 1в < и» что и' = Пз1,. В то же время ожидаемая цена игры определяется равенством которое в данной ситуации имеет вид Сопоставив это равенство с равенством и* = Пз ., приходим к выводу, что чистая стратегия Х, является оптимальной 8 »о, *» для второго игрока. Таким образом, пиковои точке (О;и ) соответствует игра двух участников с нулевой суммой, решение которой может быть найдено в чистых стратегиях.
Можно показать, что в этом случае игра является игрой с седловой 8.8. Решение нгр с нулевой суммой в смешанных стратегиях 341 точкой. Для нас она не представляет интереса. Переходим к анализу ситуации, изображенной на рис. 8.8, в. Если 0 < р,'* < 1,то в точке (р,",и') пересекается не менее двух прямых, одна из которых имеет положительный наклон, а другая — отрицательный (см., например, рис. 8.6). Пусть эти прямые определены уравнениями 1'(Х, »р,') = (П, — П„, )р,'+ П„, у (Х»р,) = (П„, — П„,)р,'+ П,~з» где индексы и, 1з обозначают номера чистых стратегий второго игрока, (П»1» — Пзй»)(П»„— Пз„) < О. Если второй игрок откажется от использования всех своих стратегий, кроме стратегий ХЗ» Хз, то в получившейся игре с нулевой суммой т! .72» каждый игрок будет располагать двумя возможными стратегиями, а платежная матрица будет квадратной второго порядка.
При этом единственная оптимальная стратегия первого игрот ка 8* » = (р," 1 — р,'*) в игре с платежной матрицей второго порядка будет той же, что и в исходной игре. Таким образом, используя только стратегии Хз, Хй» второй игрок может т»» м» помешать первому игроку получить выигрыш, больший чем и*. Следовательно, оптимальной для второго игрока является т стратегия в*,, = (О ...
0 ре,* 0 ... 0 р~л,' 0 ... 0) . Используя аналитический метод для игр с платежной матрицей второго порядка, получаем 3* П вЂ” П,. 3* 1 2* (ПМ +Пзй ) (П» г 1 Пз ) Пример 8.8. В игре из примера 8.6 для второго игрока возможны две оптимальные смешанные стратегии (см. рис. 8,6), Для первой из них 1» — 3, 1з = 4, (3+6)-(2-1) 8' "" 8' " 1, 8 8( 8. ЭЛЕМЕНТЫ ТЕОРИИ ИГР 342 а цена игры в" = тахппп Г П; р!, в ов! Р; = 1, Р! > О, ! = 1, тп, т и = пип ~~> П;, р,'. 1 с=! и* = шахР т! а цена игры и имеют место неравенства п<~~П,,р,, у'=1,!!.
! Фт! а цена игры 7 1 7 1 и" =2.0+2 О+3 — — 1. — =25=4 О+3 О+2.-+6 8 8 Для второй оптимальной стратегии 7! — — 2, !т = 3, т г* рз"=-, .х.-- О - — О Рз — (2+ 2) (3+ 3) — 2 з — 2 х— и* = 2 0+ 2 0,5 + 3 ° 0,5 — 1 0 = 2,5 = =4 О+3 0,5+2 0,5+6 О. 46 Если платежная матрица имеет два столбца, т.е.
второй игрок имеет лишь две возможные стратегии, то все рассуждения повторяются для первого игрока. В этом случае П' х П' ! „ в (П,„+П...)-(П;„+П;„)' Пример 8.9. В игре иэ примера 8.7 для первого игрока возможна одна оптимальная смешанная стратегия (см. рис. 8.7), для которой е! = 1, а ез = 3. Таким образом, !* (2+2) — (4+3) 3' 3 ~3 3 и* = 2 — + 2 0 + 3 — — 2 0 = — = 4 — + 3 О+ 2 — + 6 О. 1 2 8 1 2 3 3 3 3 3 Метод линейного программирования.
Использование линейного программирования наиболее эффективно для игр двух участников с нулевой суммой без седловых точек и большим количеством стратегий у обоих игроков. В принципе 8.3. Решеиве вгр с нулевой суммой в смешввных стратегиях 343 любая конечная игра двух участников с нулевой суммой может быть преобразована в соответствующую задачу линейного программирования и, наоборот, каждую задачу линейного программирования можно интерпретировать как конечную игру двух участников с нулевой суммой.
Действительно, пусть (П; ) 6 М „(И) — платежная матрица в игре двух участников с нулевой суммой без седловых точек. Как мы уже знаем, в этом случае оптимальная смешанная стратегия первого игрока определяется условиями: где и' — ожидаемая цена игры; П; — элемент платежной матрицы, расположенный на пересечении ее !-й строки и 7'-го столбца и равный выигрышу первого игрока, если он использует стратегию Х<!, а его противник использует стратегию Хе; р! — вероятность выбора первым игроком стратегии Х,!. При этом величина представляет собой ожидаемый выигрыш первого игрока при т использовании им смешанной стратегии гх! — — (р! р~ ... р ) Таким образом, Поэтому задача об определении оптимальной смешанной стратегии для первого игрока может быть представлена в следую- 8.
ЭЛЕМЕНТЫ ТЕОРИИ ИГР Таким образом, щем виде: и-+ шах; ~ 'р,' =! .7=1знз з=! тогда и только тогда, когда 1 х,* = —. з=! 1=1,т. 1 . 1т пип — = пип — у р;:— ~ип у х;, ! и и. зм! з=! и ~;р,'=1, 1=! и" = пип шах~) П! Рзз р' 3' 3 р. >О, !=1,н, 2 х; ) О, ! = 1, ра. у, >О, 2=1,н, и* ! = 1, ти. Пбр; >и, Е ! з=! вз ! з=! р! >О, е=1,н. Предположим, что ожидаемая цена игры и* этой задачи положительна, т.е.
и* > О. Введем новые переменные Так как значению и!ахи соответствует значение то мы приходим к задаче линейного программирования для первого игрока х! -+ пи'и; Е' з=! ~~~ Пбх;>1,.1=1,н, Заметим, что в этой задаче отсутствует ограничение типа равенства, связывающее вероятности выбора первым игроком своих чистых стратегий. Данное обстоятельство обусловлено наличием функциональной зависимости между координатами х," оптимального решения рассматриваемой задачи линейного программирования, координатами р!' оптимальной смешанной стратегии первого игрока и ожидаемой ценой игры: 8.3. Решение игр с нулевой суммой в смешанных стратегиях 345 Найдя оптимальное решение (х* ...
х* ) задачи линейного программирования для первого игрока, мы можем вычислить ожидаемую цену игры и* и затем оптимальную смешанную стРатегию вл, — — 1Р!!' ... Р! ) пеРвого игРока. Для второго игрока оптимальная смешанная стратегия определяется условиями: где р — вероятность выбора вторым игроком стратегии Х~. 2 В новых переменных приходим к задаче линейного программирования для второго игрока у, — !шах; Е 1=! ~ Пбу,<1,;=~, являющейся двойственной задачей по отношению к задаче линейного программирования для первого игрока.
347 8лк Игры двух участников с ненулевой суммой 346 8. ЭЛЕМЕНТЫ ТЕОРИИ ИГР 2 -3 4 (П; )= -3 4 — 5, П,=-З<4=П". 4 -5 б Прибавляя ко всем элементам матрицы (П; ) число К = 5, приходим к матрице модифицированной игры (П1)= 2 9 0 которой соответствует задача линейного программирования х1+хз+из-> ш1п; 7х1+ 2х2+ 9хз ~> 1, 2х1+ 9хз+ > 1, 9х2+ 11хз Ъ 1, х; > Ф, 1=1,3. Воспользовавшись симплекс-методом, находим решение: 1, 1 х" = — х*= —. 10' з 20 1 х'=— 20' Прежде чем переходить к рассмотрению иллюстративного примера, отметим следую|цее.
1. Если р < О, то ко всем элементам платежной матрицы (П; ) можно прибавить настолько большое положительное число К > п1ахП;,, что все элементы платежной матрицы станут положительными. В этом случае цена игры увеличится на К, а решение не изменится. 2. Двойственность задач линейного программирования для первого и второго игроков приводит к тому, что решение одной из них автоматически приводит к решению другой. Учитывая это, как правило, решают задачу, имеющую меньшее число ограничений.
А зто, в свою очередь, зависит от числа чистых стратегий, находящихся в распоряжении каждого из игроков. Пример 8.10. Вернемся к игре „три пальца", которую мы рассматривали в примерах 8.2, 8.4. Для нее Таким образом, цена модифицированной игры 1 х'+х'+ х' 1 2 3 а цена исходной игры р" = (и1)* — 5 = 0. При этом р1' = (и )'х;, 1= 1, 3, т.е. оптимальная-смешанная стратегия первого игрока т В рассматриваемой игре (ПИ) = (ПИ) и 8'„, = в", Нетрудно найти оптимальную смешанную стратегию второго игрока, решив соответствующую задачу линейного программирования, и убедиться в том, что она совпадает с оптимальной смешанной стратегией первого игрока. ф Завершая рассмотрение игр двух участников с нулевой суммой без седловых точек, заметим, что при использовании смешанных стратегий перед каждой партией игры каждым игроком запускается некий механизм (бросание монеты, игральной кости или использование датчика случайных чисел), обеспечивающий выбор каждой чистой стратегии с заданной вероятностью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
