ях. Третья строка является доминируемой относительно второй строки и, следовательно, не выгодна для первого игрока А.

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

После удаления данных столбцов и строки получаем матрицу

3p1* +2 p2* =ν

Для игрока А: −2 p1* +6 p2* =ν ,

p1* + p2* =1

p1* = 94 , p2* = 95 , ν = 229 .3q1* −2q2* =ν

Для игрока В: 2q1* +6q2* =ν ,

q1* +q2* =1

q1* = 89 , q2* = 19 , ν = 229 .

Ответ. pопт = (94 ; 95 ;0) , qопт = (0;0; 89 ; 19) , ν = 229 .

Задачи для самостоятельного решения.

3		−2
	2	6

№90-91. Найти решение игры в смешанных стратегиях аналитическим и графическим способом.

90.	9		8
	Р =			.
		6	9
91.		0,6		1
	Р =				.
		1		0,4

№92-97. Найти решение игры, предварительно упростив ее.

	3 −5			1 −2							2		−3 5					1 1 3			2
92.								93.	Р			4	−2	3		. 94.			0 0 1		2
	Р =						.				=						Р =					.
		4 2		−4 3
												6	−1 4						1 2 5		3
	2		5	8					4 1				3				3 −1 3			7
95.		7	6	10		. 96.								97. Р =
	Р =							Р =					.								.
										2 3								−1 9 3		0
			10	8									4
	12

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

Пусть игра задана платежной матрицей Pm×n . Первый игрок А обладает стратегиями Ai, i =1,m ; игрок В – стратегиями Bj, j =1,n .

85

Оптимальная стратегия SA* обеспечивает игроку А при любой

стратегии игрока В средний выигрыш, не меньший, чем цена игры ν , и при оптимальной стратегии игрока В выигрыш равный цене игры

ν .

Пусть ν > 0 (этого можно добиться, если все элементы платежной матрицы неотрицательны). Для оптимальной старении SA* все средние выигрыши не меньше цены игры ν .

a11 p1 +a21 p2 + +am1 pm ≥ν

a12 p1 +a22 p2 + +am2 pm ≥ν .

a1n p1 +a2n p2 + +amn pm ≥ν

Пусть νp j = x j , тогда

a11x1 +a21x2 + +am1xm ≥1a12 x1 +a22 x2 + +am2 xm ≥1.

a1n x1 +a2n x2 + +amn xm ≥1

Цель игрока А – максимизировать свой гарантированный вы-

	m	m	p j		1	m	1
	игрыш. Рассмотрим ∑x j = ∑			=		∑p j =		.
			ν		ν		ν
	j=1	j=1				j=1

m

Так как ν → max , то ∑x j → min . Таким образом, получим задачу

j=1

линейного программирования:

f	= x1 + x2 + + xm → min
a11x1 +a21x2 + +am1xm ≥1
a12 x1 +a22 x2 + +am2 xm ≥1,
a1n x1 +a2n x2 + +amn xm ≥1
	≥ 0, x2 ≥ 0, , xm ≥ 0
x1

решением которой будет оптимальная стратегия SA* Для определения оптимальной стратегии SB*

игрока А. игрока В следует

учесть, что игрок В стремиться минимизировать гарантированный выигрыш игрока А. В этом случае ЗЛП имеет вид:

ϕ = y1 + y2 + + yn → max
	+a12 y2	+ +a1n yn ≤1
a11 y1
a21 y1 +a22 y2		+ +a2n yn ≤1	, где y j =	q j	.
				ν

am1 y1 +am2 y2 + +amn yn ≤1
	≥ 0, y2	≥ 0, , yn ≥ 0
y1

Решением данной ЗЛП будет оптимальная стратегия SB* игрока В.

86

Полученные задачи являются взаимодвойственными. Пример 6.5. Найти решение игры с помощью линейного про-

граммирования:

4		2	0
	0	5	0
Р =
	2	1	3

Решение. Найдем решение игры для второго игрока В. Задача линейного программирования в этом случае имеет вид:

ϕ = y1 + y2 + y3 → max

4y

+2y

2

≤1

1

q j

, где

.

5y2

≤1

y j =

+3y

ν

2y

+ y

2

3

≤1

1

≥ 0

y

≥ 0, y

2

≥ 0, y

3

1

Приведем данную систему к каноническому виду:

ϕ = y1 + y2 + y3 → max

4y1 +2y2 + y4 =15y2 + y5 =1

2y1 + y2 +3y3 + y6 =1

yi ≥ 0, i =1,6

Решая ЗЛП симплекс-методом, имеем

			Б.П.				с.ч.					y1 y2 y3 y4 y5 y6
				y4				1				4	2	0	1	0	0
				y5				1				0	5	0	0	1	0
				y6				1				2	1	3	0	0	1
				φ				0			-1 -1 -1 0 0 0
		Б.П.				с.ч.				y1		y2		y3	y4	y5 y6
			y1			1/4				1		1/2		0	1/4	0		0
			y5			1				0			5	0	0	1		0
			y6			1/2				0			0	3	-1/2	0		1
			φ			1/4				0		-1/2		-1	1/4	0		0
	Б.П.				с.ч.				y1			y2		y3	y4	y5		y6
		y1			1/4					1		1/2		0	1/4	0		0
		y5			1					0		5		0	0	1		0
		y3			1/6					0		0		1	-1/6	0		1/3
		φ			5/12					0		-1/2		0	1/12	0		1/3
Б.П.					с.ч.					y1 y2 y3					y4	y5			y6
	y1			3/20						1		0	0	1/4 -1/10				0
	y2			1/5						0		1	0		0	1/5		0
	y3			1/6						0		0	1	-1/6		0		1/3
		φ		31/60						0		0	0	1/12		1/10		1/3

87

y	*		3	;	1	;	1		,	ϕmax =	31
		=
			20		5		6				60

Так как y1 + y2 + y3 = νq1 + qν2 + qν3 =ν1 (q1 +q2 +q3 )=ν1 , то ν = 6031 и

q1* = y1* ν = 203 6031 = 319 ; q2* = y2* ν = 15 6031 = 1231;

q3* = y3* ν = 16 6031 = 1031.

Используя теоремы двойственности, имеем

p1* = x1* ν = 121 6031 = 315 ; p2* = x2* ν = 101 6031 = 316 ; p3* = x3* ν = 13 6031 = 2031.

Ответ. p	=		5	;	6	; 20		, q	=		9	;12 ;10		, ν = 60 .
опт			31 31			31		опт			31	31 31		31

Задачи для самостоятельного решения.

№98-100. Найти решение игры путем сведения ее к задаче линейного программирования.

	3 1			2			4 5			3			4		9	5	3
														7	8	6	9
98.		5	1	0		99.		6	7	4		100.
	Р =				.		Р =				.		Р =	7	4	2	6	.
		0	2	5				5	2	3
														8	3	4	7

6.4. Игра с природой.

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

Пусть А1А2,…,Аm – возможные чистые стратегии игрока А; П1, П2,…, Пn – возможные состояния природы; aij – выигрыш игрока при применении им своей i-й чистой стратегии при j-ом состоянии природы. Тогда платежная матрица имеет вид

88

P ={aij },

a11		a12		a1n A1
P = a21		a22		a2n		A2
		a				.
a	m1		m2	a		A
					mn m
П1		П2		Пn

Возможен и другой способ задания матрицы игры с природой

– в виде матрицы упущенных возможностей или матрицы рисков. Риском rij игрока А при использовании им стратегии Аi и состоянии

природы Пj называется разность между выигрышем, который получил бы игрок, если бы знал, что состоянием природы будет Пj, и выигрышем, который получит игрок, не зная этого, т.е.

rij = max aij −aij

1≤i≤m

Замечание 6.3. Игра с природой может быть задана матрицей i =1,m , j =1,n , где aij – потери игрока А при применении им

своей i-й чистой стратегии при j-ом состоянии природы. В этом случае элементы матрицы рисков вычисляются по формуле

rij = aij −min aij

1≤i≤m

Для определения оптимальной стратегии игрока А в игре с природой используется ряд критериев, среди которых критерий Лапласа, критерий Вальда, критерий Сэвиджа, критерий Гурвица.

Критерий Вальда (принципа наибольшей осторожности) основывается на выборе наилучшей из наихудших стратегий Aj.

Если в матрице Р результат aij представляет потери игрока А, то при выборе его оптимальной стратегии используется минимаксный критерий

Z = min max aij

1≤i≤m 1≤ j≤n

Если в матрице Р результат aij представляет выигрыш (полезность) игрока, то при выборе его оптимальной стратегии используется максиминный критерий

Z = max min aij

1≤i≤m 1≤ j≤n

Критерий Сэвиджа использует матрицу рисков R ={rij }, i =1,m ,

j =1,n . Оптимальной считается та стратегия, для которой минимизируется максимальный риск, т.е. достигается значение S:

S = min max rij

1≤i≤m 1≤ j≤n

Критерий Гурвица. При любом выборе стратегии наихудший для игрока А вариант реализуется с вероятностью α , а наилучший с вероятностью 1−α , где α - показатель пессимизма (0 ≤α ≤1). Если aij

– выигрыш (полезность) игрока, то оптимальной стратегией считается та, для которой достигается значение G:

89

G = max(α min aij +(1		−α)max aij )
1≤i≤m	1≤ j≤n	1≤ j≤n

Если aij – потери игрока (затраты), то

G = min(α max aij +(1		−α)min aij )
1≤i≤m	1≤ j≤n	1≤ j≤n

Критерий Лапласа. Все состояния природы Пj, j =1,n , считаются равновероятными q j = 1n . Оптимальной по этому критерию стратегией является та, для которой достигается значение L:

L = max(1 ∑n aij )

1≤i≤m n j=1

Пример 6.6. Используя критерий Вальда, Сэвиджа, Гурвица, Лапласа определить оптимальную стратегию игрока А в игре с пр и- родой, заданной платежной матрицей (матрицей выигрышей) Р:

10		5	2
	0	10	3
P =				.
	−10	0	20

Решение. 1) Используем критерий Вальда. Для этого необходимо в каждой строке матрицы найти наименьший элемент, а затем выбрать ту строку j, которой будет соответствовать наибольший из найденных элементов:

Z1 = min(10, 5, 2) = 2 ; Z2 = min(0, 10, 3) = 0 ;

Z3 = min(−10, 0, 20) = −10;

Z = max(2, 0, −10) = 2 .

Данному значению Z соответствует первая строка. Таким образом, по критерию Вальда оптимальной является первая стратегия

А1.

2) Используем критерий Сэвиджа. Для этого для данной матрицы Р построим матрицу рисков R. Максимальные элементы в каждом столбце соответственно равны 10, 10, 20. Тогда матрица рисков выглядит следующим образом:

10 −10		10 −5	20 −2		0		5	18
	10 −0	10 −10 20 −3				10	0	17
R =					=				.
		10 −0	20 −20			20	10	0
10 −(−10)

Найдем для каждой строки матрицы R наибольший элемент, а затем среди них выберем минимальный:

S1 = max(0, 5, 18) =18 ; S2 = max(10, 0, 17) =17 ; S3 = max(20, 10, 0) = 20 ;

S = min(18, 17, 20) =17 .

90

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

гия А2.

3) Используем критерий Гурвица. Пусть α =0,3, тогда

G1 = 0,3 2 +0,7 10 = 7,6 ;

G2 = 0,3 0 +0,7 10 = 7,0 ;

G3 = 0,3 (−10) +0,7 20 =11,0 ;

G = max(7,6;7,0;11,0) =11,0 .

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

4) Используем критерий Лапласа. Так как n=3, то

L1 = 13 (10 +5 +2) = 173 ;

L2 = 13 (0 +10 +3) = 133 ; L3 = 13 (−10 +0 +20) = 103 ; L = max(173 ;133 ;103 ) = 173 .

Данному значению L соответствует первая строка. Следовательно, по критерию Лапласа первая стратегия является оптимальной.

Ответ.Критерий Вальда рекомендует стратегию А1; Критерий Сэвиджа рекомендует стратегию А2; Критерий Гурвица рекомендует стратегию А3; Критерий Лапласа рекомендует стратегию А1.

Задачи для самостоятельного решения.

№101-104. Найти оптимальную стратегию игрока, используя критерии оптимальности Вальда, Гурвица, Сэвиджа, Лапласа (коэффициент пессимизма равен 0,5).

			2 3		4 5							1 4 5			9
				5 4	1	2				102. Р =			3 8	4	3
101. Р =							.									.
				7 2	8 1								4 6 6		2
		8		15	12	11				18			25	21	21
											30		22	24	25
				12	14	15
103.	Р =	10							.	104. Р =	16		28	23	24		.
			6	8	13	14
										25			30	25	22
			5	10	15	12
											28		27	20	19

91