MMP_5

5 q 1 1 q						13			2 q 3 1 q						13
							5
									или							5
	8			2						13						2
4q		,	q						q				3,	q
	5			5							5						5

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

2 n и m 2 – игры.

Решают такие игры графическим способом, описанным выше. Отличие от 2 2 – игр заключается в следующем.

1) Нижняя (верхняя) огибающая семейства прямых

z a1k p a2k 1 p ,

z ai1q ai 2 1 q ,

i

k 1, n

1, m

содержит большее число отрезков.

2)

Пусть

в

игре

2 n

в

верхней

точке

нижней

огибающей

пересекаются прямые k k1 и

k k2 . Тогда при нахождении оптимальной

смешанной стратегии игрока В согласно Теореме 2

полагают,

что qk q ,

1

qk2

1 q , qk 0,

k k1 , k2 , где q – решение уравнения

a1k

q a1k

2

1 q

или

a2k

q a2k

1 q

1

1

2

3)

Пусть

в

игре

m 2

в

нижней

точке

верхней

огибающей

пересекаются прямые i i1 и

i i2 . Тогда при нахождении оптимальной

смешанной стратегии игрока А согласно Теореме 2

полагают,

что pi p ,

1

pi

1 p , pi 0 ,

i i1 , i2 , где p – решение уравнения

2

a1i

p a1i

1 p

или

a2i

p a2i

1 p .

1

2

1

2

m n – игры.

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

70

Правило доминировнаия.

Из платежной матрицы исключают чистые стратегии заведомо невыгодные по сравнению с другими:

а) для игрока А такими стратегиями являются те, которым соответствуют строки с элементами не большими по сравнению с элементами других строк;

б) для игрока В такими стратегиями являются те, которым соответствуют столбцы с элементами не меньшими по сравнению с элементами других столбцов.

Например, рассмотрим игру с матрицей

	2	5	8	3
	1	4	2	3
H	5	6	1	1
	5	6	1	1

Сравнивая строки, убеждаемся, что элементы 2-ой строки не больше соответствующих элементов 1-ой строки, а 3-ья строка совпадает с 4-ой.

Следовательно, стратегии A2 и A4 невыгодные и могут быть отброшены.

Матрица игры преобразуется к матрице

	2	5	8	3
	5	6	1	1

Сравнивая столбцы полученной матрицы, убеждаемся, что элементы 2-

го столбца не меньше соответствующих элементов 1-го столбца, а элементы

3-го столбца не меньше соответствующих элементов 4-го столбца, т.е.

стратегии B2 и B3 также могут быть отброшены. Окончательно усеченная матрица игры имеет вид

H			2	3
	1				.
			5	1

71

Таким образом, оптимальными стратегиями игроков А и В игры с

матрицей Н будут p p , 0,	p , 0 и	q q , 0, 0, q , где		p , p и		q , q
1	3	1	4	1	3	1	4

– оптимальные стратегии игры с матрицей H1 .

Аффинное правило.

Пусть p и q – оптимальные смешанные стратегии игроков А и В в

игре с платежной матрицей H aij , m n и ценой . Тогда p и q будут оптимальными стратегиями и в игре с матрицей H1 aij c m n и ценой

1 c .
			26	41
Например, игру с матрицей	H1		29	23		можно заменить игрой с
			32	20

		2	7
матрицей	H	3	1		, т.к. элементы этих матриц связаны соотношениями
		4	0

bij 3 aij 20 :	26 3 2 20;	41 3 7 20; 29 3 3 20; 23 3 1 20;
32 3 4 20 ;	20 3 0 20 .	При этом оптимальные стратегии игр

совпадают, а цены игр связаны соотношением 1 3 20 .

В общем случае решение игр размера m n в смешанных стратегиях

сводят к решению двух возможно двойственных ЗЛП. Изучению этого вопроса посвящена следующая лекция.

72

ЛЕКЦИЯ 9

Методы решения матричных игр в смешанных стратегиях.

В этой лекции рассматриваются матричные игры, не имеющие седловых точек.

2 2 – игры.

Рассмотрим игру с платежной матрицей

a	a
H 11	12
a21	a22

Пусть		игрок	A применяет набор своих оптимальных стратегий
p p , p .		По	основной теореме теории игр это обеспечивает ему
1	2

выигрыш при любых стратегиях игрока В, т.е. выполняются соотношения:

a11 p1 a21 p2							при стратегии В1 игрока В								(62)
a	p a			p			при стратегии В игрока В
			22
12	1			2							2
Дополняя их уравнением
				p	p 1										(63)
				1			2
получим систему линейных уравнений относительно p , p и																	. Решая
															1	2
ее найдем
p		a22	a21			,	p		a11 a12	,		a11a22	a12 a21	,		(64)
1			d				2		d				d
где d a11 a22 a12								a21 .

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

уравнений

73

	a11q1		a12 q2
	a21q1 a22 q2									(65)
	q	q 1
	1		2
Ее решениями будут
q	a22 a12	,	q	a11 a21		,		a11a22 a12 a21	,	(66)
1	d		2		d			d

Пример. Молокозавод поставляет в магазин молочную продукцию (T1 )

и кисломолочную продукцию (T2 ). Согласно договора между ними продукция поступает в магазин два раза в день: с 10.00 до 11.00 (1-ый срок) и

с 17.00 до 18.00 (2-ой срок). Если молокозавод соблюдает сроки поставок, то магазин выплачивает премии по следующей схеме: при поставке продукции

T1 в первый срок выплачивает 5 тыс. руб., во второй срок – 3 тыс. руб.; при поставке продукции T2 в первый срок выплачивает 2 тыс. руб., во второй срок – 3 тыс. руб. Определить оптимальные стратегии поставок и получения

продукции.

Решение. Примем молокозавод за игрока А, а магазин – за игрока В.

Составим платежную матрицу игры:

Сроки	1-ый	2-ой
Продукция	срок	срок
T1	5	1
T2	2	3

или

	5	1
H
	2
		3

Найдем

max min aij		max 1; 2 2
i	j	min 5; 3 3 ,
min max a

ij

j i

74

, седловой точки нет. Применим формулы (63) – (65) для определения оптимальных стратегий и цены игры:

d 5 3 1 2 5													,	p	3 2							1		,			p		5 1									4			,	q			3 1			2	,
														1		5		5									2			5						5						1		5		5
q	5 2						3		,					5 3 1 2						13			2,6 ,
2		5				5								5				5
																			1						4					2						3
Оптимальные стратегии: p																							;			, q								;						, цена игры 2,6 .
																			5						5					5						5
Таким образом, молокозавод поставляет молочную продукцию с
вероятностью					1	,			а		кисломолочную												продукцию												–						с	вероятностью								4	, а
			5																																															5
магазин получает продукцию в 1-ый срок с вероятностью																																											2	, а во 2-ой срок –
																																										5
с вероятностью						3					и		выплачивает										2,6				тыс.			руб.											премии молокозаводу
						5
ежедневно.
Матричная										игра				2 2					допускает											простую														геометрическую
интерпретацию.
Нахождение цены игры																и оптимальной стратегии																												p		для игрока А
равносильно решению уравнения:
min a						p			a			2k	1 p			max min											a	p a				2k				1 p								(66)
1 k 2			1k			1								1				0 p 1 1 k 2									1k

Для нахождения правой части (66) применим графический метод.

Пусть игрок А выбрал смешанную стратегию p p,1 p , p 0;1 , а

игрок В – k-ую чистую стратегию, k 1,2 . Тогда средний выигрыш игрока А окажется равным

z a11 p a21 1 p при стратегии B1	(67)
z a12 p a22 1 p при стратегии B2	(68)
75

Очевидно, min a1k p a2k 1 p ломанная S0 S1S2 , которую называют

1 k 2

нижней огибающей прямых I и II.

Нетрудно видеть, что

max S S S			2	p
0 p 1	0	1		1

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

Проиллюстрируем описанный графичексий метод на рассмотренной

								5	1
выше игре с платежной матрицей H										.
								2
									3
На плоскости pOz построим две прямые, описываемые уравнениями:
z 5 p 2 1 p и z p 3 1 p или z 3p 2 (I) и z 3 2 p (II).
Решая систему уравнений
z 3 p 2
z 3 2 p,
найдем 3p 2 3 2 p ,					p	1	, z 3		1		2	13		2,6 .
									5
					5								5
															p		1		4
Таким образом,			имеем полученный выше ответ игры:															;		и
																	5		5
2,6 .
Теперь покажем как графическим методом найти стратегии игрока В.
max a q a				1 q min max a							q a		1 q		(69)
1 i 2	i1 1	i 2		1	0 q 1 1 i 2				i1		i 2
Пусть игрок В выбрал смешанную стратегию q q,1 q ,																q 0;1 , а

игрок А – i-ую чистую стратегию, i 1,2 . Тогда средний выигрыш игрока В окажется равным

z a11q a12 1 q при стратегии A1	(70)
76

z a21q a22 1 q при стратегии A2					(71)
Очевидно,				max ai1q ai 2 1 q ломанная r0 r1r2 , которую		называют
				1 i 2
верхней огибающей прямых III и IV.
Нетрудно видеть, что
min r r r q
0 q 1	0	1	2	1
Таким образом, нижняя точка верхней огибающей – r1						определяет
оптимальную стратегию игрока В: q q ,1 q и цену игры .
				1	1

Для рассмотренной выше гры с матрицей H найдем стратегии игрока В.

На плоскости qOz построим две прямые, описываемые уравнениями: z 5q 1 q и z 2q 3 1 q или z 4q 1 (III) и z 3 q (IV).

Решая систему уравнений

z 4q 1z 3 q,

найдем 4q 1 3 q , q	2	,	z 4				2	1	13			2,6 .
	5						5			5
			2		3
Таким образом, имеем q				;		и 2,6 .
			5		5

Замечания. На практике оптимальную стратегию игрока В, если оптимальная стратегия игрока А, следовательно, и цена игры известны,

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

цене игры:

a11q a12 1 q или a21q a212 1 q .

Для рассмотренного примера такими уравнениями будут

5 q 1 1 q						13			2 q 3 1 q						13
							5
									или							5
	8			2						13						2
4q		,	q						q				3,	q
	5			5							5						5

77

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

2 n и m 2 – игры.

Решают такие игры графическим способом, описанным выше. Отличие

от 2 2 – игр заключается в следующем.

4)

Нижняя (верхняя) огибающая семейства прямых

z a1k p a2k 1 p ,

z ai1q ai 2 1 q ,

i

k 1, n

1, m

содержит большее число отрезков.

5)

Пусть

в

игре

2 n

в

верхней

точке

нижней

огибающей

пересекаются прямые

k k1 и

k k2 . Тогда при нахождении оптимальной

смешанной стратегии

игрока В полагают,

что

qk q , qk

1 q , qk 0,

1

2

k k1 , k2 , где q – решение уравнения

a1k

q a1k

2

1 q

или

a2k

q a2k

1 q

1

1

2

6)

Пусть

в

игре

m 2

в

нижней

точке

верхней

огибающей

пересекаются прямые

i i1 и

i i2 . Тогда

при

нахождении

оптимальной

смешанной стратегии

игрока А полагают,

что

pi p , pi

1 p , pi 0 ,

1

2

i i1 , i2 , где p – решение уравнения

a1i

p a1i

1 p

или

a2i

p a2i

1 p .

1

2

1

2

m n – игры.

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

Правило доминировнаия.

Из платежной матрицы исключают чистые стратегии заведомо невыгодные по сравнению с другими:

78

а) для игрока А такими стратегиями являются те, которым соответствуют строки с элементами не большими по сравнению с элементами других строк;

б) для игрока В такими стратегиями являются те, которым соответствуют столбцы с элементами не меньшими по сравнению с элементами других столбцов.

Например, рассмотрим игру с матрицей

	2	5	8	3
	1	4	2	3
H	5	6	1	1
	5	6	1	1

Сравнивая строки, убеждаемся, что элементы 2-ой строки не больше соответствующих элементов 1-ой строки, а 3-ья строка совпадает с 4-ой.

Следовательно, стратегии A2 и A4 невыгодные и могут быть отброшены.

Матрица игры преобразуется к матрице

	2	5	8	3
	5	6	1	1

Сравнивая столбцы полученной матрицы, убеждаемся, что элементы 2-

го столбца не меньше соответствующих элементов 1-го столбца, а элементы

3-го столбца не меньше соответствующих элементов 4-го столбца, т.е.

стратегии B2 и B3 также могут быть отброшены. Окончательно усеченная матрица игры имеет вид

		H			2	3
			1				.
					5	1
Таким образом, оптимальными стратегиями игроков А и В игры с
матрицей Н будут	p p , 0, p , 0 и				q		q , 0, 0, q , где		p , p и		q , q
	1	3					1	4	1	3	1	4

– оптимальные стратегии игры с матрицей H1 .

79