XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 46
Текст из файла (страница 46)
В дальнейших рассуждениях под о)спгмвмымм ствротпег))лмт) игрока будем понимать те чистые стратегии, которые с ненулевыми вероятностями содержатся в его оптимальной смешанной стратегии. В играх двух участников с нулевой суммой, каждый из которых имеет две чистые стратегии, платежная матрица имеет порядок два. При отсутствии седловой точки решение может быть найдено в смешанных стратегиях и обе чистые стратегии каждого игрока являются активными. Если первый игрок придерживается своей оптимальной смет шанной стРатегии 8" ) = (Р!' Рг*), то его выигРыш остаетсЯ неизменным и равным ожидаемой цене игры и независимо от действий второго игрока. Таким образом, о.
ЭЛЕМЕНТЫ ТЕОРИИ ИГР 332 Бомбарлировщиии Истребитель откуда Рис. 8.б шахпппП, ( ппптахП; . 1 1 1 1 рй" > О, й, 1' = 1, 2. Аналогично если второй игрок придерживается своей опти2 т мальной стратегии а*„, = (рг* рг*), то его проигрыш остается неизменным и равным цене игры и" независимо от действий первого игрока. Таким образом, П~гр *+ Пггрг — — и, Пг,р,'+Пггрг = и, р, +рг* =1, 2* ге 2 2* е 2* 2* Пгг — П гг 2* (П,1+ Пгг) — (П,2+П21) ' (Пы + Пгг) — (Пгг+ Пг,) Завершая наши рассуждения, напомним, что отсутствие седловой точки означает выполнение неравенства В рассматриваемом случае каждый из индексов 1 и 2 может принимать два значения: 1 и 2.
Можно показать, что при отсутствии седловой точки выполняется условие П11+ Пгг ф 1 П~г + Пю, а также условия Пример 8.5. Предположим, что сторона А (первый игрок) посылает в расположение противника В (второй игрок) два бомбардировщика. Бомбардировщик 1 летит спереди, а бомбардировщик 2 — сзади. Один из них (заранее не известно какой) несет мощную бомбу для поражения наземной цели, а второй выполняет функции сопровождения. В районе расположения противника бомбардировщики подвергаются нападению истребителя стороны В, который атакует их со стороны задней полусферы (рис.
8.5). Если истребитель атакует задний бомбардировщик, то по нему ведут огонь пушки только этого бомбардировщика и поражают его с вероятностью 0,3. Если же истребитель атакует передний бомбардировщик, то по нему ведут огонь пушки как переднего, так и заднего бомбардировщи- 8.3. Решение игр с нулевой суммой в смешанных стратегиях 333 ка; они поражают его с вероятностью 1 — (1 — 0,3)2 = 0,51. Если истребитель не сбит огнем бомбардировщика, то он поражает атакованную цель с вероятностью 0,8.
Задача бомбардировщиков — донести бомбу до цели, а задача истребителя — воспрепятствовать этому. Необходимо найти оптимальные стратегии игроков. В распоряжении каждого игрока имеются по две стратегии: Х1 — сделать носителем бомбы бомбардировщик 1, 1 Е Е (1, 2); Хг — атаковать бомбардировщик 2, т' Е (1, 2), Составим платежную матрицу игры, для чего определим средний выигрыш П,, 1, 2 = 1, 2, первого игрока (вероятность непоражения носителя) при каждой возможной комбинации стратегий игроков. П11 — вероятность непоражения бомбардировщика 1, являющегося носителем, при атаке истребителя.
Носитель выполнит свою задачу в случае, если истребитель будет сбит огнем бомбардировщиков, или же в случае, если они его не собьют, но и он не поразит свою цель. Таким образом, Пп = 0,51 + (1 — 0,51) (1 — 0,8) = 0,608. Пгг — вероятность непоражения бомбардировщика 1, являющегося носителем, при атаке истребителем бомбардировщика 2. Очевидно, что П12 = 1. 8. ЭЛЕМЕНТЫ ТЕОРИИ ИГР 334 0,608 — 1 — 0,952 0,44 — 1 р,"= ' =0,588, — 0,952 0,608 — 1 ргг' = ' = 0,412, — 0,952 0,44 — 1 рг" = ' = 0,588, — 0,952 0,608 ° 0,44 — 1 1 — 0,952 вх' —— вхг = (0 588 0412) Пг1 — вероятность непоражения бомбардировщика 2, являющегосн носителем, при атаке истребителем бомбардировщика 1.
Очевидно, что Пм — — 1. Пгг — вероятность непоражения бомбардировщика 2, являющегося носителем, при его атаке истребителем. Носитель выполнит свою задачу, если истребитель будет сбит огнем носителя или же, уцелев от огня носителя, он не поразит свою цель.
Поэтому Пгг = 0,3+ (1 — 0,3) (1 — 0,8) = 0,44. Записываем платежную матрицу Нижняя цена игры равна П. = 0,608, а верхняя цена игры равна П' = 1. Игра не имеет седловой точки, поэтому решение следует искать в смешанных стратегиях. Найдем оптимальные смешанные стратегии и цену игры: Пм + Пгг — (Пгг+ Пщ) = -0,952, Оптимальные смешанные стратегии найдены с точностью до третьего знака после запятой.
Таким образом, сторона А (первый игрок) в 58,8% всех случаев 8.8. Решение нгр с нулевой суммой в смешанных стратегиях 335 (с вероятностью 0,588) должна делать носителем бомбардировщик 1, а в 41,2% случаев — бомбардировщик 2. Оптимальная стратегия стороны В (второй игрок) состоит в том, чтобы в 58,8% случаев истребитель атаковывал головной бомбардировщик, в 41,2% случаев — замыкающий. При этом носитель будет выполнять свою задачу с вероятностью 0,769%, что больше нижней цены игры П. = 0,608 и меньше верхней цены игры П"=1.
Графяческий метод, Этот метод можно использовать, когда у одного из игроков в распоряжении лишь две чистые стратегии. В случае отсутствия седловой точки обе чистые стратегии будут активными. Рассмотрим игру двух участников с нулевой суммой, в которой нет седловой точки, а первый игрок может применять две чистые стратегии, т.е. (П; ) 6 Мг„(аь). Пусть ° ы !я т в, = (р, рг ) — оптимальная смешанная стратегия первого игрока. Тогда и его ожидаемый выигрыш, соответствующий чистой страте- гии Хг второго игрока, у = 1, п, равен г У(Х~,Р1') = ~> р,'*П, = (П11 — Пг )р,'"+Пг, г'= 1, и.
Таким образом, ожидаемый выигрыш первого игрока при любой стратегии второго игрока является линейной функцией вероятности р," выбора первым игроком своей первой чистой стратегии. В соответствии с минимаксным критерием для игр двух участников с нулевой суммой при отсутствии седловой точки первый игрок должен выбирать значение р," так, чтобы максимизировать свой минимальный ожидаемый выигрыш. Эта 8.
ЭЛЕМЕНТЫ ТЕОРИИ ИГР 336 3 2 6 Нижняя цена зтой игры П, = шахш1пП; =2 > р! отличается от ее верхней цены П* = ппп шахП; = 3, > Рис. 8.6 задача легко решается графически путем построения прямых, соответствующих ожидаемым выигрышам первого игрока при азличных чистых стратегиях второго игрока и являющихся Р 1 линейными функциями аргумента р1 6 (О, 1). Если второй игрок располагает двумя чистыми стратегиями, т.е. (П; ) 6 М з(й1), то все проведенные рассуждения можно повторить для второго игрока. Пример 6.6. Рассмотрим игру двух участников с нулевой суммой и платежной матрицей т.е.
игра не имеет седловой точки. Чтобы определить оптимальную смешанную стратегию первого игрока, представим его ожидаемые выигрыши для всех возможных стратегий Хз, й' = 1,4, второго игрока в виде линейной функции вероятности р1 1выбора первым игроком своей первой чистой стратегии Х1 .. 1. у(Хз Р1) = — 2Р1+ 4, У(Хз,р1) = — Р1+ 3> у'(Хз,Р1) =Р1-1-2, У(Х4 Р1|) = — 7Р, + 6. На рис. 8.6 изображены графики линейных зависимостей ыожидаемых выигрышей первого игрока от вероятности р выбора им своей первой чистой стратегии Х1.
Выделенн 1 д дя ломаная линия Ада определяет минимальный гарантирован- 8.3. Решение игр с нулевой суммой в смешанных стратегиях 337 ный выигрыш первого игрока независимо от действий второго игрока. Таким образом, согласно максиминному критерию, р~~* = 0,5, р* = 2,5, что соответствует точке М(0,5; 2,5). А так как в рассматриваемом случае первый игрок располагает лишь двумя стратегиЯми, то Р1*+Рзы — — 1 и его оптимальнаЯ смешаннаЯ стРатегиЯ лх> (05 0>5) При использовании графического метода для решения игр двух участников, один из которых имеет две стратегии, все построения в смешанных стратегиях соответствуют ожидаемому проигрышу второго игрока.
т ПУсть лхх — — (Р,' Рзз') — оптимальнаЯ смешаннаЯ стРате- гиЯ втоРого игРока, Располагающего стРатегиЯми Х~з и Хзз. Тогда и его ожидаемый проигрыш, соответствующий чистой стратегии Х,, 1= 1, т, первого игрока, равен 1 3 с'(Х> Р1 ) = ~ Р;*ПИ = (П» — П>я)рз*+ Пв 8.
ЭЛЕМЕНТЫ ТЕОРИИ ИГР 338 г 6 2 4 2 3 3 2 -2 6 р[ Рмс. 8.7 ~(Х1 Рз1) р', + 3, Я(Х4',р',) = -8р',+6. Я(Х~,рз1) = — 2р~1+4, Я(Хз1 рз1) =рз1+2 3' 3' х [,3 3/' Рис. 8.8 Все дальнейшие рассуждения аналогичны предыдущим, если учесть, что второй игрок использует минимаксный критерий. Пример 8.7. Рассмотрим игру двух участников с нулевой суммой, в которой платежная матрица равна В данном случае нижняя цена игры П, = 2 отличается от ее верхней цены П* = 3, т.е. игра не имеет седловой точки. Чтобы определить оптимальную смешанную стратегию второго игрока, представим его ожидаемые проигрыши для всех возможных стратегий Х1, 1= 1, 4, первого игрока как линейные функции вероятности рз1 выбора вторым игроком своей первой чистой стратегии Х1 ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
