1.1.5. Решение матричной игры путем сведения к задаче линейного программирования

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

Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно воспользоваться правилом перевода элементов матрицы в область неотрицательных значений (см. п. 1.3). Следовательно, можно принять, что   0.

Применение игроком А оптимальной смешанной стратегии гарантирует ему, независимо от поведения игрока В, выигрыш, не меньший цены игры .

Если игрок А применяет свою оптимальную стратегию , а игрок В свою чистую стратегию В_j, то средний выигрыш игрока А будет равен:

.

Учитывая, что _j не может быть меньше , можем записать условие:

. (1.5)

Разделив левую и правую части неравенства (1.5) на цену игры   0, получим:

. (1.6)

Введем новые обозначения:

. (1.7)

Тогда неравенства (1.6) запишутся в виде:

. (1.8)

где x_i 0, так как p_i 0,  > 0.

Компоненты вектора р удовлетворяют следующему условию:

p₁ + p₂ + … + p_m = 1.

Учитывая соотношение (1.7) получим, что переменные x_i удовлетворяют условию:

.

Учитывая, что игрок А стремится максимизировать , получаем линейную функцию

. (1.9)

Таким образом, приходим к следующей задаче линейного программирования: найти неотрицательные значения переменных x_i ( ), минимизирующие линейную функцию (1.9) и удовлетворяющие ограничениям (1.8):

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

Аналогично для игрока В нужно решить двойственную задачу:

,

Решив двойственную задачу, найдем вероятности применения игроком В его чистых стратегий из выражения:

.

1.2. Пример решения задачи

Решить игру, представленную платежной матрицей:

.

Порядок выполнения работы

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

	B1	B2	B3	B4	i
A1	3	1	9	5	1
A2	1	5	7	0	0
A3	0	4	5	–1	–1
A4	1	5	7	0	0
A5	4	–2	5	2	–2
j	4	5	9	5

Рис. 1.3. Платежная матрица примера

Аналогично для каждой стратегии игрока B максимальный проигрыш . Нижняя цена игры (максимин):

.

Верхняя цена игры (минимакс):

.

Максиминная (перестраховочная) стратегия игрока A есть стратегия A₁. Применяя эту стратегию игрок A получит выигрыш не менее 1. Минимаксная (перестраховочная) стратегия игрока B есть стратегия B₁. Применяя эту стратегию, он проиграет не больше 4.

Так как   , будем решать игру в смешанных стратегиях. Цена игры при этом удовлетворяет условию 1    4.

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

Поскольку соответствующие элементы второй и четвертой строк равны, то имеет место случай с дублирующими стратегиями. Следовательно, одну из строк можно убрать (например, четвертую). Элементы третьей строки меньше соответствующих элементов второй строки. Поэтому игроку А, стремящемуся максимизировать выигрыш, выгоднее применять стратегию А₂, а не стратегию А₃. В связи с этим опустим третью строку. Преобразованная матрица будет иметь следующий вид:

.

Элементы третьего столбца больше соответствующих элементов первого столбца. Поэтому стратегия B₃ является для игрока B заведомо невыгодной. Опустим третий столбец и получим следующую матрицу:

.

Анализируя эту матрицу, делаем вывод, что дальнейшему упрощению она не подлежит.

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

.

Составим задачу линейного программирования для игрока А:

,

(1.10)

Для игрока B имеем двойственную задачу:

,

(1.11)

Для решения задачи (1.10) воспользуемся надстройкой Excel Поиск решения. Подготовьте исходные данные на листе Excel как показано на рис. 1.4.

Рис. 1.4. Исходные данные для решения матричной игры

Ячейки F2:F4 отведены под значения переменных x_i. В них введены начальные приближения, равные нулю. В ячейке F6 находится формула целевой функции (сумма переменных). В ячейках A6:C6 – формулы левых частей ограничений:

• A6: =СУММПРОИЗВ(A2:A4;$F$2:$F$4);

• B6: =СУММПРОИЗВ(B2:B4;$F$2:$F$4);

• C6: =СУММПРОИЗВ(C2:C4;$F$2:$F$4).

Формулу ячейки A6 в ячейки B6:C6 можно скопировать методом автозаполнения.

Вызовем надстройку Поиск решения и заполним диалоговое окно как показано на рис. 1.5 (необходимо также установить флажок Линейная модель, нажав кнопку Параметры).

Рис. 1.5. Окно Поиск решения для решения матричной игры

Нажмем кнопку Выполнить, получим сообщение об успешном решении задачи и выберем в списке Тип отчета пункт Устойчивость. Переключатель должен быть установлен в положение Сохранить найденное решение. После нажатия кнопки OK Excel сформирует отдельный лист рабочей книги, содержащий отчет по устойчивости. Отчет по устойчивости требуется для того, чтобы не решать заново двойственную задачу: оптимальные значения двойственных переменных z_j^* приведены в графе Теневая цена этого отчета. Скопируем ячейки, содержащие значение теневой цены, на лист с исходными данными задачи в ячейки B8:B10 (рис. 1.6).

Рис. 1.6. Результаты решения игры

Найдем вероятности применения игроком А чистых стратегий по формуле

.

Для этого в ячейке H2 запишем формулу для нахождения p₁:

= F2/$F$6.

Вероятности p₂ и p₃ находятся аналогично, поэтому скопируем формулу из ячейки H2 в ячейки H3 и H4 с помощью автозаполнения.

Итак, , , .

Вероятности применения игроком В чистых стратегий Вj находим по формуле

.

Для этого в ячейку D8 запишем формулу для нахождения q₁:

= B8/$F$6.

Вероятности q₂ и q₃ находятся аналогично, поэтому скопируем формулу из ячейки D8 в ячейки D9 и D10 с помощью маркера автозаполнения.

Итак, ; ; .

Цену игры найдем по формуле

.

Однако это будет цена игры для преобразованной матрицы. Чтобы вернуться к исходной задаче, нужно вычесть 2 из  (так как ранее мы прибавляли двойку ко всем элементам платежной матрицы, а это увеличивает цену игры на 2). Итак, в ячейку F8 запишем формулу

=1/F6–2.

Получим, что цена игры равна 2,33. Учитывая, что для данной задачи  = 1, а  = 4, убеждаемся, что условие      выполнено.

Окончательно возвращаясь к исходной задаче, необходимо вспомнить, какие стратегии игроков A и B мы посчитали заведомо невыгодными и вычеркнули из платежной матрицы. Этим стратегиям, очевидно, соответствуют вероятности, равные нулю. Итак, для исходной платежной матрицы имеем следующие смешанные стратегии:

• игрока A: ;

• игрока B: .

Полученные результаты можно сформулировать так: в случае многократного повторения игры игроку А для получения максимально возможного среднего выигрыша, равного 2,33, следует в приблизительно 67 % случаев применять первую стратегию, и в 33 % случаев – вторую. Например, если игра повторяется 100 раз, то 67 раз он должен применить первую стратегию и 33 раза – вторую. Остальные стратегии игроку А применять невыгодно.

Что касается игрока B, то он должен также применять свои первую и вторую стратегии в 67 % случаев и 33 % случаев соответственно. При этом его средний проигрыш будет 2,33, что значительно меньше верхней цены игры  = 4.