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

Пусть игра задана платёжной матрицей Р размером m x n:

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

    Игрок А обладает стратегиями А₁, А₂, ..., А_m, игрок В – стратегиями В₁, В₂, ..., В_n. Необходимо определить оптимальные стратегии    S_А^*=(р₁^*, р₂^*, ..., р_m^*) и S_В^*=(q₁^*, q₂^*, ..., q_n^*), где р_i^*, q_j^* – вероятность применения соответствующих чистых стратегий А_i, В_j, причём

р₁^* + р₂^* + ... + р_m^* = 1, q₁^* + q₂^* + q_n^* = 1.

    Оптимальная стратегия S_А^* удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока В. Величина v (цена игры) неизвестна. Будем считать v > 0, этого можно добиться, прибавляя ко всем элементам матрицы некоторое положительное число. Если игрок А применяет смешанную стратегию S_А^* = (р₁^*, р₂^*, ..., р_m^*) против любой чистой стратегии В_j игрока В, то он получат средний выигрыш, или математическое ожидание выигрыша а_j = a_1j p₁ + a_2j p₂+ … + a_mj p_m, .

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

                                                     (7.11)

    Разделим каждое неравенство на v > 0. Введём новые переменные

                                             (7.12)

Тогда система 7.11 примет вид:

                                                      (7.13)

    Цель игрока А – максимизировать свой гарантированный выигрыш, т.е. цену игры v.

    Разделив на v ≠ 0 равенство р₁ + р₂ + ... + р_m = 1, получаем, что переменные x_i  удовлетворяют условию: х₁ + х₂ + ... + х_m = 1 / v. Максимизация цены игры v эквивалентна минимизации величины , поэтому задача может быть сформулирована следующим образом: определить значения переменных x_i ≥ 0 , так, чтобы они удовлетворяли ограничениям (7.13) и целевая функция

                                        Z = x₁ + x₂ + … + x_m                                   (7.14)

обращалась в минимум. Это задача линейного программирования. Решая задачу (7.13) – (7.14), получаем оптимальные значения х_i^* и величину , затем находим р_i^* = v ∙ х_i^* и оптимальную стратегию S_А^* = (р₁^*, р₂^*, ..., р_m^*).

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

                                                      (7.15)

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

    Если обозначить y_j = q_j / v, ,                                         (7.16)

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

                                                      (7.17)

Переменные y_j  удовлетворяют условию у₁ + у₂ + ... + у_n = 1/v.

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

                                  W = у₁ + у₂ + ... + у_n.                                         (7.18)

    Решение задачи (7.17) – (7.18) даёт оптимальные значения y_j^* и величину 1/v, затем находим q_j^* = v ∙ y_j^* и оптимальную стратегию S_В^*=(q₁^*, q₂^*, ..., q_n^*). При этом цена игры

                                        v = 1/max W = 1/min Z.                               (7.19)

    Рассмотренные задачи (7.13), (7.14), (7.17) и (7.18) являются симметричными двойственными задачами. Таким образом, для решения игры нужно решить одну из задач, требующую меньших вычислений, затем найти решение второй с помощью теорем двойственности.

    Пример 7.5. Предприятие может выпускать три вида продукции (А₁, А₂ и А₃), получая при этом прибыль, зависящую от спроса, который может быть в одном из четырёх состояний (В₁, В₂, В₃, В₄). Дана матрица (таблица 7.4), её элементы a_ij характеризуют прибыль, которую получит предприятие при выпуске i-й продукции с j-м состоянием спроса.

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

    Решение. Задача сводится к игровой модели, в которой игра предприятия А против спроса В задана платёжной матрицей (таблица 7.4).

Таблица 7.4 – Платёжная матрица

    Определим нижнюю и верхнюю цены игры: α = max(2, 3, 1) = 3,   β = min(4, 5, 6, 5) = 4. Так как α ≠ β, то матрица не имеет седловой точки и оптимальное решение следует искать в смешанных стратегиях игроков S_А^* = (р₁, р₂, р₃) и S_В^*=(q₁, q₂, q_3, q₄). Обозначим x_i = p_i/v, y_j = q_j/v, , . Составим симметричные двойственные задачи.

    Задача 1                                                    Задача 2

    Задачу 2 приведём к канонической:

    Решим каноническую задачу симплексным методом в симплексных таблицах (таблица 7.5).

Таблица 7.5 – Симплексная таблица

Сi	Баз.	0	1	1	1	1	0	0	0	θ
		Св. члена	у1	у2	у3	у4	у5	у6	у7
0	у5	1	4	3	4	2	1	0	0	1/4
0	у6	1	3	4	6	5	0	1	0	1/3
0	у7	1	2	5	1	3	0	0	1	1/2
	W	0	– 1	– 1	– 1	– 1	0	0	0
1	у1	1/4	1	3/4	1	1/2	1/4	0	0	1/4 : 1/2=1/2
0	у6	1/4	0	7/4	3	7/2	–3/4	1	0	1/4:7/2=1/14
0	у7	1/2	0	7/2	– 1	2	–1/2	0	1	1/2 : 2=1/4
	W	1/4	0	–1/4	0	–1/2	1/4	0	0
1	у1	3/14	1	1/2	4/7	0	5/14	–1/7	0
1	у4	1/14	0	1/2	6/7	1	–3/14	2/7	0
0	у7	5/14	0	5/2	–19/7	0	–1/14	–4/7	1
	W	2/7	0	0	3/7	0	1/7	1/7	0
							х1	х2	х3

Из таблицы находим ; , следовательно, .

Учитывая, что q_j = y_j ∙ v, получим оптимальную стратегию игрока В:

Из последней строки симплексной таблицы получаем , т.к. p_i^*= x_i^* ∙ v, то получаем оптимальную стратегию игрока А: . Находим цену игры

Следовательно, предприятие должно выпускать 50% продукции А₁, 50% продукции А₂, а продукцию А₃ не выпускать.

 – оптимальная стратегия спроса означает, что оптимальный спрос в 75% находится в состоянии В₁ и в 25% – в состоянии В₄. Средняя величина прибыли составит при этом .

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

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

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

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

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

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

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

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

Пример 7.6. Предприятие выпускает скоропортящуюся продукцию, которую может сразу отправить потребителю (стратегия А₁), отправить на склад для хранения (стратегия А₂) или подвергнуть дополнительной обработке (стратегия А₃) для длительного хранения.

Потребитель может приобрести продукцию: немедленно (стратегия В₁), в течение небольшого времени (В₂), после длительного периода времени (В₃).

В случае стратегий А₂ и А₃ предприятие несёт дополнительные затраты на хранение и обработку продукции, которые не требуются для А₁, однако при А₂ следует учесть возможные убытки из-за порчи продукции, если потребитель выберет стратегии В₂ или В₃.

Определить оптимальные пропорции продукции для применения стратегий А₁, А₂, А₃, руководствуясь «минимаксным критерием» (гарантированный средний уровень убытка) при матрице затрат (таблица 7.6).

Таблица 7.6 –  Платёжная матрица

    Решение. Получаем игру с платёжной матрицей .

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

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

По формулам (7.8), (7.9), (7.11) находим:

; ;

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