Графический метод решения игровых задач с нулевой суммой

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

Воспользуемся табл. 2.

Строка (стратегия) А₁ является доминирующей по отношения к строке (стратегии) А₄, так как содержит элементы, большие соответствующих элементов строки А₄. Соответственно строка А₄ является поглощаемой и из дальнейшего рассмотрения удаляется (табл. 5).

Таблица.5

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

Таблица 6

Второй шаг упрощения таблицы

Стратегии	B1	В5
A1	5	4
А2	1	6
А3	2	2

Еще раз просматриваем строки. Первая строка поглощает третью строку.

Поглощаемые строки (столбцы) содержат самые плохие стратегии. Окончательно получим (табл. 7).

Таблица .7

Третий шаг упрощения таблицы

Стратегии	В1	в5
А1	5	4
А2	1	6

Вероятность использования первой фирмой первой стратегии обозначим через х₁,. Тогда вероятность использования второй стратегии вторым игроком будет х₂ =1- х₁. Ожидаемый выигрыш фирмы А от применения первой стратегии составит: а₁₁Х₁ + а₂₁Х₂ =а₁₁Х₁+ а₂₁(1-х₁) =(а₁₁-а₂₁) х₁+а₂₁. (1)

Аналогичным способом получим ожидаемый выигрыш фирмы А от применения второй стратегии:

(а₁₂-а₂₂)х₁+ а₂₂. (2)

В выражения (1) и (2) подставим конкретные значения.

(а₁₁-а₂₁) х₁+а₂₁ = (5- 1)х₁, + 1 =4х₁ + 1;

(а₁₂-а₂₂)х₁+ а₂₂ = (4 - 6) х₁ + 6 = -2х₁ + 6.

На оси х отложим две точки 0 и 1. Через эти точки проведем прямые линии, параллельные оси у. Затем в первое выражение подставим 0 вместо х₁, а потом — единицу. И по двум точкам построим прямую линию.

55

15

15

15

45

65

Аналогично построим вторую прямую линию. Пересечение двух прямых линий и даст решение задачи (рис. 1).

О 1

Рис. 1. Графический способ определения стратегии фирмы А

Итак, вероятность использования первой стратегии фирмой А составляет 0,83 (x₁ = 0,83), а второй стратегии — соответственно 0,17 (х₂ = 0,17).

Аналогично определим оптимальную стратегию поведения фирмы В

(а₁₁-а₁₂) y₁+а₁₂ = (5- 4)y₁, + 4 =y₁ + 4;

(а₂₁-а₂₂)y₁+ а₂₂ = (1 - 6) y₁ + 6 = -5y₁ + 6.

Рис..2. Графический способ определения стратегии фирмы В

Вероятность использования первой стратегии фирмой В составляет 0,33 (y₁ = 0,33), а второй стратегии — соответственно 0,67 (y2 = 0,67)

Общий метод решения игровых задач с нулевой суммой

Рассмотрим общий случай, когда игровая модель не имеет седловой точки. Тогда эту модель можно представить в виде матрицы (табл..8).

Таблица 8..

Надо найти смешанную стратегию фирмы А (первого игрока) — S_a = р₁ + P₂ + • • • + р_n и смешанную стратегию фирмы В (второго игрока) — S_b = q₁ + q₂ + • • • +q_m Выполним некоторые математические преобразования. Если первая фирма будет строго применять оптимальную стратегию (или комплекс стратегий), то фирма В не сможет изменить ход игры без дополнительного ущерба для себя. Тогда можно записать:

a ₁₁p₁+a₁₂p₂+a₁₃p₃+…+a_1mp_m>=ω

a₂₁p₁+a₂₂p₂+a₂₃p₃+…+a_2mp_m>=ω

(3)

a_n1p₁+a_n2p₂+a_n3p₃+…+a_nmp_m>=ω

где ω- гарантированный минимальный выигрыш.

Все неравенства в выражении (3) разделим на ω, и введем обозначения:

x₁=p₁/ ω x₂=p₂/ ω x_m=p_m/ ω

Получим:

a ₁₁x₁+a₁₂x₂+a₁₃x₃+…+a_1mx_m>=1

a₂₁x₁+a₂₂x₂+a₂₃x₃+…+a_2mx_m>=1

(4)

a_n1x₁+a_n2x₂+a_n3x₃+…+a_nmx_m>=1

где х_i >=0и X₁ + х₂ +х₃ +...+х_т = 1/ ω при i=1,m.

Но ω — это минимальный гарантированный выигрыш, поэтому его надо максимизировать. Следовательно, 1/ ω надо минимизировать. Таким образом, задача свелась к задаче линейного программирования с целевой функцией

F(x) — Х₁ + х₂ + х₃ + ... +х_m —> min (5)

и системой линейных ограничений (4).

Данную задачу можно решить симплексным методом. Прямая задача на минимум решается для фирмы А. Двойственная задача для фирмы В решается на максимум.