Приведение матричной игры к задаче линейного программирования.

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

Пусть игра m × n задана платежной матрицей p= (a_ij), i = 1, 2,..., m; j=1, 2,..., n. Игрок А обладает стратегиями A₁, A₂,..., A_m, игрок В — стратегиями B ₁, B₂ ,..., B_m . Необходимо определить оптимальные стратегии S*_A =(p*₁ , p*₂,..., p*_m) и S*_B =(q*₁ , q*₂,..., q*_n), где p*_i, q*_j — вероятности применения соответствующих чистых стратегий A_i, B_j, p*₁ + p*₂ +...+ p*_m =1, q*₁ + q*₂ +...+ q*_n = 1.

Оптимальная стратегия S*_A удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока B. Без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы a_ij ≥ 0. Если игрок А применяет смешанную стратегию S*_A = (p*₁ , p*₂,..., p*_m) против любой чистой стратегии B_j игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша a_j = a_1j p₁ + a_2j p₂ +...+ a_{m j} p_m, j = 1, 2,..., n (т.е. элементы j -го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A₁ , A₂ ,..., A_m и результаты складываются).

Для оптимальной стратегии S*_A все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:

(58.1)

Каждое из неравенств можно разделить на число v > 0. Введем новые переменные:

(58.2)

Тогда система (40.1) примет вид:

(58.3)

Цель игрока А — максимизировать свой гарантированный выигрыш, т.е. цену игры v. Разделив на v ≠ 0 равенство p₁ + p₂ +...+ p_m = 1, получаем, что переменные x_i (i = 1, 2,..., m) удовлетворяют условию: x₁ + x₂ +...+ x_m = 1/v. Максимизация цены игры v эквивалентна минимизации величины 1/v. Поэтому задача может быть сформулирована следующим образом: определить значения переменных x_i ≥ 0, i = 1, 2,..., m так, чтобы они удовлетворяли линейным ограничениям (58.3) и при этом линейная функция

(58.4)

обращалась в минимум. Это задача линейного программирования. Решая задачу (58.3)—(58.4), получаем оптимальное решение p*₁ + p*₂ +...+ p*_m и оптимальную стратегию S_A.

Для определения оптимальной стратегии S*_B = (q*₁ + q*₂ +...+ q*_n) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти . Переменные q₁ , q₂,..., q_n удовлетворяют неравенствам:

, (58.5)

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

, (58.6)

то получим систему неравенств:

. (58.7)

Переменные y_j (1, 2,..., n) удовлетворяют условию y₁ + y₂ +...+ y_n = 1/v.

Игра свелась к следующей задаче: определить значения переменных y_j ≥ 0, j = 1, 2,..., n, которые удовлетворяют системе неравенств (58.7) и максимизируют линейную функцию

(58.8)

Решение задачи линейного программирования (58.6), (58.7) определяет оптимальную стратегию S*_B = (q*₁ + q*₂ +...+ q*_n). При этом цена игры

(58.9)

Составив расширенные матрицы для задач (58.3), (58.4) и (58.7), (58.8), убеждаемся, что одна матрица получилась из другой транспонированием:

Таким образом, задачи линейного программирования (58.3), (58.4) и (58.7), (58.8) являются взаимно-двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности. Приведем примеры экономических задач, которые описываются игровыми моделями m × n и могут быть решены методами линейного программирования.

При решении произвольной конечной игры размера m × n рекомендуется придерживаться следующей схемы:

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

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

3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m × n рекомендуется симплексный метод, для игр размера 2×2, 2×n, n×2 возможно геометрическое решение.

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

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

Рассмотрим экономическую задачу, сводящуюся к игровой модели.

Пример: предприятие выпускает скоропортящуюся продукцию, которую может сразу отправить потребителю (стратегия A ₁), отправить на склад для хранения (стратегия A ₂) или подвергнуть дополнительной обработке (стратегия A ₃) для длительного хранения. Потребитель может приобрести продукцию: немедленно (стратегия B ₁), в течение небольшого времени (B ₂), после длительного периода времени (B ₃). В случае стратегий A ₂ и A ₃, предприятие несет дополнительные затраты на хранение и обработку продукции, которые не требуются для A ₁, однако при A ₂ следует учесть возможные убытки из-за порчи продукции, если потребитель выберет стратегии B ₂ или B ₃. Определить оптимальные пропорции продукции для применения стратегий A ₁, A ₂, A ₃ руководствуясь "минимаксным критерием" (гарантированный средний уровень убытка) при матрице затрат, представленной таблице.

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

Игра упростилась: .

По формулам находим: , , .

Вывод: оптимальная стратегия производителя продукции , т.е. стратегия A ₁ не применяется, 1/3 продукции отправляется на склад (стратегия A ₂), 2/3 продукции дополнительно обрабатывается (стратегия A ₃), при этом цена игры .