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

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

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

Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия x – это набор чисел x = (x1, ..., xm) удовлетворяющих соотношениям

xi >= 0 (i = 1,m), = 1.

Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y – это набор чисел

y = (y1, ..., yn), yj >= 0, (j = 1,n), = 1.

Так как каждый раз применение игроком одной чистой стратегии исключает применение другой, то чистые стратегии являются несовместными событиями. Кроме того, они являются единственными возможными событиями.

Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

Определение. Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей

E (A, x, y) == x A yT

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

 Е (А, х, y).

Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть

 Е (А, х, y).

Подобно играм, имеющим седловые точки в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборы хо, уо соответственно, которые удовлетворяют равенству

 Е (А, х, y) = Е (А, х, y) = Е (А, хо, уо).

Величина Е (А, хо ,уо) называется при этом ценой игры и обозначается через u.

Имеется и другое определение оптимальных смешанных стратегий: хо, уо называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку:

Е (А, х, уо)<= Е (А, хо, уо)<= Е (А, хо, у)

Оптимальные смешанные стратегии и цена игры называются решением матричной игры.

Основная теорема матричных игр имеет вид :

Теорема (о минимаксе). Для матричной игры с любой матрицей А величины

 Е (А, х, y) и  Е (А, х, y) существуют и равны между собой.

Игра 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 , о = 1, 2, ..., n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A₁ , A₂ , ..., A_m и результаты складываются).

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

(2.3.1)

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

x₁ = p₁/v, x₂ = p₂/v , ..., p_m/v (2.3.2)

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

(2.3.3)

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

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

Z = x₁ + x₂ + ...+ x_m, (2.3.4)

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

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

(2.3.5)

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

y_j = q_j/v, j = 1, 2, ..., n, (2.3.6)

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

(2.3.7)

Переменные y_j (1, 2, ..., n) удовлетворяют условию .

Игра свелась к следующей задаче

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

Z' = y₁ + y₂ + ...+ y_n, (2.3.8)

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

v = 1 / max, Z' = 1 / min Z (2.3.9)

Составив расширенные матрицы для задач (2.3.3), (2.3.4) и (2.3.7), (2.3.8), убеждаемся, что одна матрица получилась из другой транспонированием:

Таким образом, задачи линейного программирования (2.3.3), (2.3.4) и (2.3.7), (2.3.8) являются взаимно-двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности.

Похожие работы

Решение транспортной задачи линейного программирования в среде MS Excel

Скачать

62893

11

17

... . При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ...

O Л. В. Канторовиче и линейном программировании

Скачать

58662

0

0

... среди математиков, его разделяли А.Н.Колмогоров, И.М.Гельфанд, В.И.Арнольд, С.П.Новиков и др. Нельзя не восхищаться естественностью и внутренней стройностью математической работ Л.В. по двойственности линейного программирования и их экономической интерпретацией. 2. О математической экономике как области математики и о некоторых ее связях А) Связи линейного программирования с функциональным и ...

Решение оптимизационной задачи линейного программирования

Скачать

59893

13

0

... решения останется неизменным, т.е. будет состоять из переменных (Х3,Х6,Х4,Х5).   СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования. Ч.1. – Мн.: БГУИР, 1995. 2. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного ...

Линейное программирование: решение задач графическим способом

Скачать

32158

4

0

... области (если допустимая область ограничена и не пуста); 3.   ограниченность целевой функции в допустимой области является необходимым и достаточным условием разрешимости задачи. Гл 2 Решение задач линейного программирования графическим способом на ЭВМ 2.1 Описание работы программы Программа написана с использованием собственных функций и процедур и трех стандартных модулей System, Crt и ...