4.3.2. Алгоритм решения матричной игры (исследования игры)

1. Исключить в матрице игры заведомо невыгодные стратегии.

2. Полученную упрощенную матрицу проверить на наличие в ней седловой точки. Если такая точка имеется, то определить решение и цену игры. Если седловой точки нет, то перейти к шагу 3.

3. Применить методы определения оптимальных смешанных стратегий. С некоторыми из них можно познакомиться, например, по задачнику: Калихман И.Л. Сборник задач по математическому программированию.– М. 1975., с.174–185.

28. Записать платежную функцию для игры, задаваемой матрицей . Определить цену игры, оптимальные стратегии и оптимальное решение.

Решение. Для записи функции выигрыша игры воспользуемся формулой : . Определим верхнюю и нижнюю цены игры. 1) , . Отсюда нижняя цена игры ; 2) , , и верхняя цена игры . Таким образом, , оптимальные стратегии = . Для отыскания векторов и составим системы уравнений: 1) и 2) Решая эти системы, получим

=(0, 1). =(0, 1, 0).

29. Рассчитайте величину платежа для игр, заданных матрицами:

1) и 2) , если , .

30. Два игрока А и В играют в следующую игру. Игрок А записывает одно из чисел 1,2,3., а игрок В – одно из чисел 1, 2. Если сумма записанных чисел четная, то это выигрыш А, а если нечетная, то его проигрыш. 1) Составьте матрицу игры; 2) найдите нижнюю цену игры; 3) выясните, есть ли седловая точка; 4) какое число или числа должен выбрать игрок А, чтобы обеспечить себе минимальный проигрыш?

31. Два игрока А и В независимо друг от друга выбирают красный или зеленый цвет бумаги. Если выбранные ими цвета совпадают, то выигрыш игрока А составляет 5. Если игрок А выбирает зеленый цвет, а игрок В красный, то проигрыш игрока А составляет 4, если же цвета выбраны наоборот, то его проигрыш равен 6. 1) Составьте платежную матрицу; 2) найдите нижнюю верхнюю цены игры; 3) определите, есть ли седловая точка; 4) какой цвет должен выбрать игрок А, чтобы обеспечить себе минимальный проигрыш?

32. Исследовать игры, заданные следующими матрицами

1) ; 2) ; 3)

Решение. 1) Стратегия невыгодна по сравнению со стратегией , поэтому ее можно исключить. В оставшейся матрице можно исключить доминирующие стратегии и . После их исключения получим матрицу . В этой матрице невыгодными оказались стратегии и . Их исключение приводит к матрице . Итак, для игрока А осталась одна стратегия , а для игрока В более выгодной является стратегия , обеспечивающая ему проигрыш 6, вместо 8 при стратегии .

Окончательно получили решение игры в виде чистых стратегий и и цену игры . Решение в виде чистых стратегий говорит о том, что исходная матрица имела седловую точку

2) Первая строка доминирует над 2-ой и 3-ей, так как все ее элементы соответственно не меньше элементов 2-ой и 3-ей строк. Поэтому стратегии и заведомо менее выгодны, чем , и могут быть исключены. В результате получится матрица . В этой матрице 1-ый, 4-ый и 5-ый столбцы доминируют над вторым. Так как столбцы характеризуют стратегии игрока В, который стремится уменьшить выигрыш игрока А, то эти стратегии заведомо невыгодны для В. После их исключения получится матрица , в которой нет доминирующих стратегий. В ней строки соответствуют стратегиям и , а столбцы – стратегиям и . Определим теперь нижнюю и верхнюю цены игры.

1) , и отсюда – нижняя цена игры; 2) , и тогда – верхняя цена игры.

Так как , то игра не имеет седловой точки и ее решением будет смешанная стратегия.

33. Провести возможные упрощения матрицы А игры, если:

1) ; 2) ; 3) .

Решение следующих задач использует теорему 2.

34. Исследовать и решить игру, заданную матрицей .

Исследовать матричную игру – это значит, выяснить, имеет ли она седловую точку, определяющую цену игры, и указать наиболее выгодные стратегии для каждого из игроков; если седловой точки нет, то выбрав смешанные стратегии, найти оптимальную стратегию игры и среднюю величину выигрыша для одного из игроков и, соответственно, проигрыша, для другого игрока.

Решение. 1) Найдем верхнюю и нижнюю цены игры: и, следовательно, ; аналогично, и . 2) проверяем наличие седловой точки: , следовательно, седловой точки нет. 3) Будем искать оптимальную смешанную стратегию. Пусть для игрока А эта стратегия задается вектором и цена игры равна v. Тогда на основании теоремы 2, при применении игроком В стратегии или игрок А получит средний выигрыш, равный цене игры v:

(при стратегии ),

(при стратегии ). Кроме этих двух уравнений , имеем еще уравнение для частот:

. Из этой системы из трех уравнений с тремя неизвестными найдем

Аналогичным образом находится оптимальная стратегия для игрока В: Таким образом, решением игры являются смешанные стратегии , а цена игры . Полученный результат означает, что средняя величина выигрыша игрока А и, соответственно, проигрыша игрока В равна , если игрок А применяет стратегию с частотой , а стратегию с частотой , независимо от того, какие стратегии применяет игрок В; при этом для игрока В оптимальный результат достигается, если он будет применять стратегию с вероятностью , а стратегию – с вероятностью .

35. Решить игры, заданные матрицами: 1) ; 2) ; 3) ; 4) .

36. Группа террористов продвигается с запада на восток по одной из трех возможных дорог (1, 2, 3). Отряду ОМОНа поставлена боевая задача: выйти наперерез террористам, навязать им открытый бой и разгромить. ОМОН также имеет три маршрута движения (а, б, в). Пересечение путей движения определит место проведения боя, поэтому имеется 9 возможных участков столкновения. Все они располагаются на разных относительных высотах, которые приведены в следующей таблице

Маршруты движения	1	2	3
а	4,0 км	1,5 км	3,0 км
б	0,5 км	1,0 км	0,0 км
в	2,0 км	1,0 км	1,5 км

Отряду полиции выгоднее навязать открытый бой противнику на местности с наименьшей высотой. Террористы чувствуют себя уверенней в горах. Участки предполагаемой схватки имеют разные высоты. Необходимо определить, какой маршрут движения ОМОНа оптимален .

37.Задача оперуполномоченного – задержать подозреваемого, который может находиться в двух местах– А и В. Если оперативник направляется в то же место, где находится подозреваемый, то задерживает его. В этом случае его стратегия оценивается выигрышем +1. Если же оперативник выбирает место, противоположное тому, где находится подозреваемый, то подозреваемый скрывается от правоохранительных органов. Выигрыш оперативника составит при этом . Найти оптимальную стратегию действий оперативника и его выигрыш.