Исследование операций / ИСО Учебник

	1		1	2	3	4
			2C	C	2C	3C
	2		3C	3C 2	C 2C
A =								,
	3		2C	2C	C	C
	4		C	C	C	C 2

где С > 0. Требуется найти решение игры.

Решение. Прежде всего заметим, что по свойству 6 достаточно решить игру G1 = (Х, Y, А), где А1 = C1 А. В матричной форме игра G1 определяется матрицей выигрышей

		1		1	2	3	4
				2	1	2	3
		2		3	3 2	1	2
A1	=
		3		2	2	1	1
		4		1	1	1	1 2

Элементы четвёртой строки этой матрицы «≤» соответствующих элементов третьей строки, и поэтому третья стратегия игрока 1 доминирует над четвёртой. Кроме того, элементы первого столбца матрицы А1 «≥» соответствующих элементов второго столбца, следовательно, вторая стратегия игрока 2 доминирует над его первой стратегией.

Далее, из свойства 5 следует, что всякое решение игры

G2 = (Х\{4}, Y\{1}, А1)

является решением игры G1. В матричной форме игру G2 можно представить матрицей

1		2	3	4
		1	2	3
A2 = 2		3 2	1	2
					.
3		2	1	1

Очевидно, что элементы второй строки «≥» полусуммы соответствующих элементов первой и третьей строк. Кроме того, элементы третьего

171

столбца матрицы А2 «≥» соответствующих элементов второго столбца. Применяя свойство 5, получим, что всякое решение игры

G3 = (Х\{4,2}, Y\{1,4}, А2)

есть решение игры G2, а следовательно и игры G1. Игра G3 определяется матрицей

				2	3
A3	=	1		1	2
						.
		3		2	1

Матрица А3 не имеет седловой точки, так как не выполнено равенство

max min aij = min max aij ,
i	j	j i

а игра G3 не имеет решения в чистых стратегиях, т.е. оптимальные стратегии игроков смешанные. Эти стратегии (в данном случае) легко найти из анализа структуры матрицы А3. Поскольку матрица А3 симметрична, можно предположить, что игроки в оптимальной стратегии используют свои чистые стратегии с равными вероятностями.

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

12 1+ 12 2 = 32 ,

либо

12 2 + 12 1 = 32 .

Аналогично, если игрок 2 использует свои чистые стратегии 2 и 3 с равными вероятностями, то математическое ожидание его проигрыша будет

равно 32 . Следовательно, указанные стратегии являются оптимальными в иг-

172

ре G3, а величина 32 — значением игры G3. Из предыдущего следует, что эти стратегии оптимальны и в G1.

Таким образом, стратегия Х = ( 12 , 0, 12 , 0) — оптимальная стратегия иг-

рока 1, стратегия Y = (0, 12 , 12 , 0) — оптимальной стратегией игрока 2 в игре

G1, а значение игры G1 равно 32 . В силу свойства 4 решением игры G будет тройка (Х, Y, 32C ).

Игры порядка 2×2

В общем случае игра 2×2 определяется матрицей

a	a
A = 11	12	.
a21	a22

Прежде всего необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причем оптимальными стратегиями игроков 1 и 2 будут, соответственно, чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет чистых стратегий, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями. В противном случае один из игроков (например, 1) имеет чистую оптимальную стратегию, а другой — только смешанные. Не ограничивая общности, можно считать, что оптимальной стратегией игрока 1 является выбор с вероятностью 1 первой строки. Далее, по свойству 1 следует, что а11 = а12 = w и матрица имеет вид

	w	w
		.
a21		a22

173

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

Пусть Х = (ξ, 1 − ξ) — оптимальная стратегия игрока 1. Так как игрок 2 имеет смешанную оптимальную стратегию, из свойства 1 получим, что (свойство 7)

a11ξ + a21(1 −ξ) = w,a12ξ + a22 (1 −ξ) = w.

Отсюда следует, что при w ≠ 0 столбцы матрицы А не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Если же коэффициент пропорциональности равен единице, то матрица А

принимает вид	a	a		и игрок 1 имеет чистую оптимальную стратегию
	11	11
	a	a
	12	12

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

Решая её, находим

ξ =			a22 − a21							;		(2.34)
	a		− a	− a	21		+ a	22
11			12
w =		a11 a22 − a12 a21									.	(2.35)
		a	− a	− a		21	+ a
11			12						22

Аналогичные рассуждения	приводят нас к тому, что	оптимальная
стратегия игрока 2 Y = (η, 1 – η)	удовлетворяет системе уравнений
a11η + a12 (1 −η) = w
a21η + a22 (1 −η) = w.		(2.36)

174

Откуда

η =		a22 − a12					.	(2.37)
	a	− a	− a	21	+ a	22
11		12

Графический метод решения игр 2×n и m×2

Рассмотрим графический метод решения матричных игр 2×n и m×2 метод на примерах.

Пример. Рассмотрим игру, заданную платёжной матрицей:

				2
	A	B1		B2	B3
1			2	3	11
	1		7	5	2
	A
	2

Требуется найти ее решение.

Решение. На плоскости хОy введём систему координат и на оси Ох отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (х, 1 − х). В частности, точке А1 (0;0) отвечает стратегия А1, точке А2 (1; 0) — стратегия А2 и т. д. (рис. 2.18).

В точках А1 и А2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью Оy) отложим выигрыш игрока 1 при стратегии А1, а на втором — при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет при стратегии В1 игрока 2 — 2, при стратегии В2 — 3, а при стратегии В3 — 11. Числам 2, 3, 11 на оси Ох соответствуют точки В1, В2 и В3.

Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии В1 равен 7, при В2 — 5, а при В3 — 2. Эти числа определяют точки В′1, В2′, В3′ на перпендикуляре, восстановленном в точке А2. Соединяя между собой точки В1 и В′1, В2 и В′2, В3 и В′3 получим три прямые, расстояние до которых

175

от оси Oх определяет средний выигрыш при любом сочетании соответствующих стратегий. Например, расстояние от любой точки отрезка В1В′1 до оси Oх определяет средний выигрыш w1 при любом сочетании стратегий А1 А2 (с частотами х и 1 – х) и стратегией В1 игрока 2. Это расстояние равно

2х1 + 6(1 − х2) = w1.

Рис. 2.18. Графическое решение матричной игры

Таким образом, ординаты точек, принадлежащих ломаной В1MΝВ′3, определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке Ν; следовательно, этой точке соответствует оптимальная стратегия Х* = (х, 1 − х), а её ордината равна цене игры w. Координаты точки Ν находим как точку пересечения прямых В2 B′2 и В3 B′3.

Соответствующие два уравнения имеют вид

	3x + 5(1 − x) = w		x =		3		, w =	49	.
		− x) = w		11				11
	11x + 2(1

176

Следовательно, X =					3						9						w =		49
								;					при цене игры							. Оптимальную
									11										11
			11
															3		11
стратегию мы можем найти при помощи матрицы																		.
															5
																	2
Оптимальные стратегии для игрока 2 можно найти из системы
						3y + 5(1 − y) = w								y	=		9
																11
						5y + 2(1 − y) = w
	9				2
и, следовательно, Y = 0;				;				. Из рис. 2.18 видно, что стратегия B1 не вой-
	11
					11

дет в оптимальную стратегию.

Рис. 2.19. Графическое решение матричной игры

177

Пример. Найти решение игры, заданной матрицей

		B		2 B
	A		1	2
			6	5
	1		4	6
1	A2
	A		2	7
	3		1	8
	A
	4

Решение. Матрица имеет размерность 2×4. Строим прямые, соответствующие стратегиям игрока 1 (рис. 2.19).

Ломаная А1KА′4 соответствует верхней границе выигрыша игрока 1, а отрезок ΝΚ — цене игры. Решение игры таково:

	3	;	5			7	; 0; 0;	1		w =	43	.
Y =	8		8	,	X =	8		8	,		8

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

Рассмотрим игру m×n, определяемую матрицей

a	a	a
11	12	1n
a21	a22	a2n
A =	...	...	.
...
	am2
am1		amn
Для оптимальной стратегии	(теорема 3) первого игрока

X * = (x1*, x2*, xm *) и цены игры w выполняется неравенство:

m

∑aij xi * ≥ w ( j =1, n) .

i=1

Предположим для определенности, что w > 0.

Это всегда может быть достигнуто благодаря тому, что прибавление ко всем элементам матрицы А одного и того же постоянного числа С не при-

178

ведет к изменению оптимальных стратегий, а лишь увеличит цену игры на С. Разделив теперь обе части последнего неравенства на w , получим:

m ∑aij xi

i=1	≥1 ( j =1, n) .
w

Положим xi = ui , тогда w

m

∑aijui ≥1 ( j =1, n), ui ≥ 0 (i =1,m) .

i=1

Используя введенное обозначение, перепишем условие

	m	m	1
	∑xi ≥1 в виде	∑ui		.
	i=1	i=1	w

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

оптимальной стратегии второго игрока сводится к нахождению минимального значения функции

m	m
F* = ∑ui	при условиях ∑aijui	≥1 ( j =		), ui ≥ 0 (i =		). (2.38)
			1, n		1,m
i=1	i=1

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

	n	n						y j
	F* = ∑v j	при условиях ∑aijv j ≤1 (i =	1, m	), v j ≥ 0	( j =	1, n	) , v j =		. (2.39)
	j =1	j =1						w

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

179

Прямая задача: найти минимальное значение функции

m	m
F* = ∑ui	при условиях ∑aijui	≥1 ( j =	1, n	), ui ≥ 0 (i =	1,m	).
i=1	i=1

Двойственная задача: найти максимальное значение функции

n

F* = ∑v j

j=1

n

при условиях ∑aij v j ≤1 (i =1, m), v j ≥ 0 ( j =1,n) .

j=1

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

u

v j

x

j

* =

i

= wu

i

,

y

j

* =

= wv

j

,

(2.40)

m

n

∑ui

∑v j

i=1

j=1

w =

1

=

1

;

(i =

; j =

).

(2.41)

1,m

1,n

n

m

∑v j

∑ui

j=1

i=1

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

1.Составить пару двойственных задач линейного программирования, эквивалентных данной матричной игре.

2.Определить планы пары двойственных задач.

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

Пример. Найти решение игры, определяемой матрицей

	0	1	−1
	0	−1	0
A =				.
	1	0
			−1

180