Колобашкина-Част-1

						a1														8		8
y1																																;
			a			a			a
																	( 8) ( 5) ( 1) 14
					1	2					3
						a2														5		5
y2																																		;
				a		a			a
																		( 8) ( 5) ( 1) 14
					1	2					3
						a3														1									1
y																																	.
				a		a			a
3																		( 8) ( 5) ( 1) 14
					1	2					3
Ответ:x*		T			1 11							2						y*	T	8			5 1													27
																,																			,			.
											14											14 14
					14 14															14																14

1.7.3. Метод обратной матрицы

Данный метод позволяет находить решение игровых задач размерности n×n, содержащих только активные стратегии. Поэтому перед началом решения необходимо убедиться в отсутствии седловой точки и исключить заведомо невыгодные стратегии. Модель игры в данном случае будет идентична модели, рассмотрен-

ной в п. 1.7.2:

В1	В2	...	Вn
a	a	...	a
11	12		1n
A a21	a22	...	a2n
	...	...	...
...
	an2	...
an1			ann

Определим оптимальные стратегии игроков

A1 A2

...

An

x T (x1,x2 ,...,xn ), y T (y1, y2 ,..., yn )

и цену игры .

Для определения оптимальной стратегии x* игрока А составим систему уравнений в предположении, что А применяет свою оптимальную смешанную стратегию, а В свои чистые стратегии, аналогично тому, как это было сделано в п. 1.7.2.

51

a11x1 a21x2 ... an1xn ;

a x a x ... a x ;

12 1 22 2 n2 n (1.7.8)

. . . . . . . . . . . . . . .

a1nx1 a2nx2 ... annxn .

n

xi 1– условие нормировки.

i 1

Запишем систему (1.7.8) в векторно-матричной форме [7]:

x TА (1)	,	(1.7.9)
1 n

где (1)1 n - вектор размерности 1 n, состоящий из одних единиц.

Умножим обе части равенства (1.7.9) справа на А-1:

x TАА-1

(1)

1 n

А-1.

Откуда следует:

x T

(1)

1 n

А-1.

Введем в рассмотрение новый вектор вида:

~ T

x T

-1

x

(1)1 n А

.

n

Поскольку xi

1,

i 1

n

~

n

xi

1

xi

.

(1.7.10)

i 1

i 1

С помощью соотношения (1.7.10) определяем цену игры :

1

.

(1.7.11)

n

~

xi

i 1

Тогда вектор оптимальной стратегии x T стороны А будет:

T

~ T

~ T

x

x

x

,

i 1,...,n.

(1.7.12)

n

~

xi

i 1

52

Далее определяем оптимальную стратегию y* игрока В. Для этого составим соответствующую систему уравнений:

	а11y1 а12 y2				... а1n yn		ν ;
			a22 y2		... a2n yn		ν ;
	a21y1								(1.7.13)
	. . . . . . . . . . . . .
	a	y a		y	... a	y	ν.
	n1	1	n2	2	nn	n
	n
	yi		1 условие нормировки.
	i 1
Запишем систему (1.7.13) в векторно-матричной форме:
			Аy		(1)n 1		,		(1.7.14)
где (1)n 1 – вектор	размерности n 1, состоящий из одних единиц.
Умножим обе части уравнения (1.7.14) слева на А-1:
откуда получим		А-1Аy А-1 (1)n 1						,

y А-1 (1)n 1.

Введем в рассмотрение вектор вида:

y

y

А-1

(1)n 1.

(1.7.15)

Из соотношения (1.7.15) имеем:

yj

n

~

n

1

yj

,

(1.7.16)

j 1

j 1

n

поскольку yi

1.

i 1

Из условий (1.7.15) – (1.7.16) определяем вектор оптимальной стратегии y T стороны В:

	T	~ T		~ T
				y
y		y			,	i 1,...,n,	(1.7.17)
				n
				~
				yj

j1

атакже значение цены игры, которое, естественно, должно совпасть со значением, рассчитанным по формуле (1.7.11):

53

																															1								.																		(1.7.18)
																														n
																															y j
																														j	1
			1.15.																																									,																			:
																									1						3	4
																									2						2	1 .
																									2						1	6
			.																													-1.
																			:
	det(A)		1		2		1							3				2	1						4					2		2									1 11 3 10												4 (				2)						27
					1		6											2	6											2		1
																																:
											2			1								2			1									2							2
											1			6								2			6									2							1			11									10				2
												3		4							1				4										1						3
		adj(	)																																									14									2				5 .
												1		6							2				6										2						1
																																												5									7				4
										3				4							1				4									1							3
										2				1							2				1									2							2
																																												11									14				5
			adj( )																11						14							5												27									27				27
		-1												1					10						2							7														10							2							7			.
			det(A)											27																														27									27				27
																			2						5							4
																																												2									5				4
																																												27									27				27
																									11							14												5
																									27							27												27
~	T		-1																						10							2												7									1				11						2
x		(1)1 n					1							1					1																																														.
																									27							27												27									27				27						27
																									2							5												4
																									27							27												27
																									54

(1.7.12),

(x1, x2, x3) , :

				x T							1					11			2				.
										14						14			14
																								(1.7.11):
				1						1						11					2		1	27
																										.
				n						27						27			27					14
				xi
				i 1
			(1.7.15)							~
														y * :
				11						14									5					8
				27						27									27				1	27
				10						2									7					5
y	-1	(1)																					1				.
			n 1	27						27									27					27
																							1
				2						5									4					1
				27						27									27					27

(1.7.17), ( y1 , y2 , y3 ) , :

			y *T				8			5			1	.
					14				14			14
. x *T		1 11 2							, y *T			8				5		1		,	27	.
																					14
	14		14		14							14				14		14

		!	n n .
	2	1	1
1.	2	2	0 .
	0	1	2

	: x *T		6		1 10			; y *	9		2			6	;		14	.
		17		17		17			17		17		17			17
								55

	4			3		1
2. А				1
	4					2 .
				3
	2					3
Ответ: x*		T		1		1		13			;	y*	Т		4		1			4		;		23	.
						9		18								9	9		9					9
				6

1.8. Методы решения матричных игр m×n

1.8.1.Решение игр размерности m×n методами линейного программирования

Решение любой матричной игры m n сводится к задаче линейного программированиях [1, 5].

Рассмотрим игру m n с m стратегиями А1, А2,…,Аm игрока А и

n стратегиями В1, В2,…,Вn		игрока В,				которая задается матрицей
		В1	В2 ...			Вn
	a11		a12 ...			a1n			A1
A	a	21	a	22	...	a			A
							2n		2
	... ... ...					...		...
			am2 ...						Am
	am1					amn

Требуется найти решение игры, т.е. оптимальные смешанные

стратегии игроков А и В x Т (x ,...,x	m	),	y Т (y ,..., y ) и цену
1			1	n

игры .

Сначала найдем оптимальную стратегию (x1,...,xm ) игрока А. Эта стратегия должна обеспечить выигрыш, не меньший цены игры, при любом поведении второго игрока и выигрыш, равный цене игры, при его оптимальном поведении. Цена игры нам неизвестна, поэтому зададим ее в виде некоторого положительного числа . Для того чтобы выполнялось условие > 0 достаточно, чтобы все элементы матрицы были неотрицательные. Этого всегда можно добиться, если воспользоваться аффинным правилом, определяющим допустимые преобразования матрицы игры и её цену.

56

. ,

cik

aik

,

i 1,..., m ; k 1,..., n,

> 0, , - (, ),

.

, -

,

, . , > 0 .

(x1 ,..., xm ) , . -

			,			-
		,		,	,	-
		:
a11 x1	a21 x2	...	am1 xm	;
...
a1n x1	a2n x2	...	amn xm	;	(1.8.1)

m

xi 1.

i 1
			(1.8.1)	-
			:
	xi	zi	(i 1,..., m).	(1.8.2)

(1.8.1) :

a11 z1 a21 z2 ... am1 zm 1;

...

a1n z1 a2n z2 ... amn zm 1;

(1.8.3)

1 z1 ... zm .

57

( ) -

	1
;	,				,
(1.8.3).
	,
						.
						z1 , z2 ,..., zm
,
	m			1,	k 1,..., n,	(1.8.4)
		aik zi
	i 1
				L		:
				m
		L		zi	min.	(1.8.5)
			i	1

, x (x1 ,..., xm ) - .

(y1,, yn) -

		.
,		,	,
,	,	,	-

1/ .

		,
	,	-
,	,	.
		-

:

a11w1 a12 w2 ... a1n wn 1;

	...		(1.8.6)
		am1w1 am2 w2 ... amn wn	1,
wj	y j	; wj	,

:

58

	w ...	w		1	,		(1.8.7)
			n
	1
					yj, j = 1,	, n.
						,	-
,
(1.8.7).
	,
							.
w1 , , wn	,
	n
	aik wk 1,			i 1,..., m ,			(1.8.8)
	k 1
					L .
	n
	L	wk			max .		(1.8.9)
	k	1

-

.

,	,			-
m n				-
.
			m n	-
.
1.16.				-
	0	1	1
C	0	1	0 .
	1	0	1

.

I. - , , , .

= 1, -

59

1 2 0

A 1 0 1 .

2 1 0

II. x (x1 ,..., xm ) .

1.

(1.8.4)(1.8.5):

m

zi min,

	i 1	zi	0, k 1,..., n; i 1,..., m .
	m

aik z i 1, i 1

L z1 z2 z3 min, z1 z2 2z3 1;

2z1 z3 1;

(1 )

z2 1.

2. :

					m
min(L)		max(	L)	max[0	(	zi )].
					i	1
				(1 )
			.
min(L)	max(	L)	max[0 (z1		z2	z3 )].
z1	z2	2z3	z4	1;
2z1 z3		z5	1;			(2 )

z2 z6 1.

3. (2) z4, z5, z6. .

(2) (1):

max( L) max[0 (z1 z2 z3 )];

60