9758

		b1=1			b2=1		b3=1		b4=1
a1=1				2		10		9	7
		1- - - - - -			- - - - - - - - - - - -		- - - - - -
a2=1			|	15		4	|	14	8
					1
a3=1			|	13		14	|	16	11
					0
a4=1			|	4		15	|	13	19
		0- - - - - -			- - - - - - - - - - - -		- - - - - - 1
		V1			V2		V3		V4
1). ai bi			– закрытая транспортная задача (ТЗ)
2). m + n-1=7
3). ui + vj = Cij
u1 + v1=2			u1 = 0
u1 + v4=7			u2= -6
u2 + v2=4			u3 = 4
u3 + v2=14			u4 = 2
u3 + v4=11			v1 = 2
u4 + v1 =4			v2 = 10
u4 + v3=13			v3 = 11
u1 =0			v4 = 7
4). ij= Cij – (ui + vj)
12	= 10 – (0 +10) = 10 – 10 = 0
13	= 9 – (0 + 11) = 9 – 11 = -2					<0
21	= 15 – (-6 +2) = 15 + 4 = 19					>0
23	= 14 – (-6 + 11) = 14 – 5 = 9					>0
24 = 8 – (-6 + 7) = 8 – 1 = 7						>0
31	= 13 – ( 4 + 2) = 13 – 6 = 7					>0
33	= 16 – (4 + 11) = 16 – 15 = 1					>0
42	= 15 – (2 + 10) = 15 – 12 = 3					>0
44	= 19 – (2 + 7) = 19 – 9 = 10					>0
Составляем цикл для					13:

141

U1

U2

U3

U4

		b1=1		b2=1	b3=1	b4=1
	a1=1	2		10	9	7
					1
	a2=1	15		4	14	8
				1
	a3=1	13		14	16	11
				0
	a4=1	4		15	13	19
		1
u1 + v3=9		u1 = 0
u1 + v4=7		u2= -6
u2 + v1=15		u3= 4
u3 + v2=4		u4 = -17
u3 + v2=14		v1 = 21
u3+ v4=11		v2 = 10
u4 + v1=4		v3 = 9
u1 =0		v4 = 7
11	= 2 – (0 + 21) = 2 – 21 = - 19			< 0
12	= 10 – (0 + 10) = 10 – 10 = 0			= 0
23 = 14 – (-6 + 9) = 14 – 3 = 11				> 0
24 = 8 – (-6 + 7) = 8 – 1 = 7				> 0
31	= 13 – (4 + 21) = 13 – 25 = -12			< 0
33	= 16 – (4 + 9) = 16 – 13 = 3			> 0
42	= 15 – (-17 + 10) = 15 + 7 = 22			> 0
43	= 13 – (-17 + 9) = 13 + 8 = 23			> 0
44	= 19 – (-17 + 7) = 19 +10 = 29			> 0
Берём наибольшее отрицательное				по модулю для составления цикла

	b1=1		b2=1	b3=1	b4=1
a1=1		2	10	9	7
	0			1
a2=1		15	4	14	8
			1
a3=1		13	14	16	11
					1
a4=1		4	15	13	19
	1
			142

Найденный план является оптимальным: x13=1 x22=1 x34=1 x41=1

L(x) = 9+4+11+4=28 y.e.

3.2.2. Задачи для раздела 2. Элементы теории матричных игр.

Задача 1. Определить нижнюю и верхнюю цену игры, заданной платежной матрицей

	3	2	1
P	1	1	1	.
	2	0	4

Имеет ли игра седловую точку?

Решение. Найдем по каждой строчке платежной матрицы минимальное число i min ai1,ai2 ,ai3 – это гарантированный выигрыш игрока А, при вы-

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

ij имеет максимальное значение – max 1, 2 , 3 – это нижняя цена игры.

Для игрока В выберем по каждому столбцу максимальное число

j max a1 j ,a2 j ,a3 j – это гарантированный проигрыш игрока В при выборе им стратегии B j . Найдем минимальное из этих чисел min 1, 2 , 3 – это верхняя цена игры. Занесем полученные данные в таблицу.

		B1	B2	B3
A		3	-2	1	1	min 3, 2,1 2
1
A		1	-1	1	2	min 1, 1,1 1
2
A		2	0	4	3	min 2,0, 4 0
3
	1	max 3,1, 2 3	2 max 2, 1, 0 0	3 max 1,1, 4 4	max 2, 1, 0 0
					min 3, 0, 4 0

143

Нижняя цена игры 0 равна верхней цене игры 0 . Значит, игра имеет седловую точку. Для игрока А оптимальная стратегия – A3 , для игрока В опти-

мальная стратегия – B2 .

Ответ: 0 , игра имеет седловую точку, оптимальные стратегии ( A3 , B2 ) .

Задача 2. Решить графически игру, заданную платежной матрицей

4		0
	2	0
P	5	2	.
	3
		3

Решение. Дана игра 4 х 2, то есть у игрока А имеется 4 стратегии, а у иг-

рока В – 2. Поэтому, будем решать игру для игрока В. Построим оси: ОХ – на ней будем отмечать вероятности, с которыми игрок использует ту или иную стратегии, и ОУ – на ней будем откладывать цену игры. На расстоянии единица от оси ОУ проведем еще ось параллельную ей (см. рис. 1). Если игрок А

выбирает стратегию A1 , то игрок В, используя свои стратегии с вероятностями q1, q2 , будет проигрывать, в среднем, q1 a11 q2 a12 q1 ( 4) q2 0 . Отметим на оси ОУ a11 4 , а на оси ей параллель-

ной a12 0 и соединим эти точки прямой линией – она показывает, сколько, в

среднем, получает игрок В, если А использует стратегию A1 , а В чередует стра-

тегии B1 и B2 с некоторыми вероятностями q1, q2 . Аналогично отмечаем на оси ОУ точку –2, а на параллельной ей оси – точку 0 и соединяем отрезком.

Получаем линию, показывающую, сколько в среднем, получает игрок В, если А выбрал стратегию A2 . Точно также для A3 и A4 . Для игрока В надо выбрать верхнюю границу, так как он должен рассчитывать, что А выберет ту страте-

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

144

это ломаная A3 KA4 , выделенная толстой линией. Игроку В следует выбрать ту смешанную стратегию, которая соответствует наименьшему проигрышу для В

– точка К. Это точка пересечения прямых, соответствующих стратегиям A3 и

A4 . Выпишем уравнения этих прямых.

Прямая ( A3 A3 ), проходит через точки с координатами (0; 5) и (1; -2).

Уравнение этой прямой запишется в следующем виде:

	x 0		y 5		x	1	y	5	.
	1 0		2 5			7		7

Уравнение прямой ( A4 A4 ), проходящей через точки (0; -3) и (1; 3), запишется в следующем виде:

	x 0		y ( 3)	x	1	y	1	.
	1 0		3 ( 3)		6		2

Точка К – точка пересечения этих прямых, имеет координаты, удовлетворяю-

щие системе:

x 17 y 75 .

x 1 y 16 2

Решаем систему:

			1					5
x				y						1		5		1		1		13		3			3			42		9
			7					7			y				y				y			y								.
	1				1
										7		7		6		2		42		14			14			13		13
x			y
	6				2

Откуда,

x 16 139 12 138 .

Следовательно, цена игры v 139 и оптимальная стратегия для игрока В:

q2 138 , q1 1 138 135 .

145

Для игрока А, стратегии A1 и A2 будут не активными, игроку А не вы-

годно их использовать. Максимально возможный выигрыш, равный цене игры

v 139 , игрок А будет получать, используя стратегии A3 и A4 . Найдем опти-

мальную смешанную стратегию для игрока А из следующей системы, учиты-

вая, что A1 и A2 не активные стратегии, то есть p1 p2 0 :

				4 p 2 p								5 p							3 p			v			9
										2								3		4
						1																13									1 p4
																														p3
																										9
				0 p1 0 p2									2 p3 3 p4									v																	9
																										13				5 1	p4			3 p4
				p		p	2	p			3		p				4		1																		13
					1
						5			9		8 p4								p4				7	; p3 1 p4							1	7				6		.
								13
																						13									13			13
													9																								*					6			7
Ответ: Цена игры v																, оптимальные стратегии игроков																					S A 0, 0,							,			,
													13																													13 13
*	5			8
SB			,		.
	13 13

Замечание. Если игра размера 2 х n, то ее следует решать для игрока А.

Тогда на чертеже следует выбирать нижнюю границу и максимальное значении этой границы.

Задача 3. Упростить матричную игру, платежная матрица которой имеет

вид:

Bj
	B1	B2	B3	B4	B5
Ai
A1	5	9	3	4	5
A2	4	7	7	9	10
A3	4	6	3	3	9
A4	4	8	3	4	5
A5	4	7	7	9	10
				146

Из платежной матрицы видно, что стратегия А2 дублирует стратегию А5,

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

нирующей над А4 стратегии А1 всегда обеспечивает выигрыш, не меньший то-

го, который был бы получен при применении стратегии А4. Следовательно,

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

Bj
	B1	B2	B3	B4	B5
Ai
A1	5	9	3	4	5
A2	4	7	7	9	10
A3	4	6	3	3	9

Из этой матрицы видно, что в ней некоторые стратегии игрока В домини-

руют над другими: В3 над В2, В4 и В5. Отбрасывая доминируемые стратегии В2,

В4 и В5, получаем игру 3x2, имеющей платежную матрицу вида:

Bj
Ai	B1	B3
A1	5	3
A2	4	7
A3	4	3

В этой матрице стратегия А3 доминируется как стратегией А1, так и страте-

гией А2. Отбрасывая стратегию А3, окончательно получаем игру 2x2 с платеж-

ной матрицей:

Bj
	B1	B3
Ai
A1	5	3
A2	4	7

147

Эту игру уже упростить нельзя, ее надо решать рассмотренным выше ал-

гебраическим или геометрическим методом.

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

ладает ли игра седловой точкой – это проще, чем сравнивать почленно все строки и все столбцы платежной матрицы.

Алгебраические методы решения матричных игр иногда производить про-

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

Свойство 1. Если ко всем элементам платежной матрицы прибавить (вы-

честь) одно и тоже число С, то оптимальные смешанные стратегии игроков не изменятся, а только цена игры увеличится (уменьшится) на это число С.

Свойство 2. Если каждый элемент платежной матрицы умножить на по-

ложительное число k, то оптимальные смешанные стратегии игроков не изме-

нятся, а цена игры умножится на k.

Отметим, что эти свойства верны и для игр, имеющих седловую точку. Эти два свойства матричных игр применяются в следующих случаях:

1)если матрица игры наряду с положительными имеет и отрицательные элементы, то ко всем ее элементам прибавляют такое число, чтобы исключить отрицательные числа в матрице;

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

Задача 4. Решить матричную игру 2х2 с платежной матрицей вида:

Bj
	B1	B2
Ai
A1	0.5	-0.2
A2	0.1	0.3

148

Умножая все элементы платежной матрицы на 10, а затем прибавляя к ним число 2, получаем игру с платежной матрицей

Bj

	B1	B2
Ai
A1	7	0
A2	3	5

Решая эту игру алгебраическим методом, получаем

p			5 3				2			;		p				7		;
1		7	5 3 0			9							2		9
q			5 0					5	;				q				4			;
1		7	5 3 0			9								2	9
v		7 5 0 3				35					.
	7 5 3 0
						9

В соответствии со свойствами 1 и 2, исходная матричная игра имеет те же

оптимальные смешанные стратегии: S A 92 : 79 и S B 95 : 94 . А для получения ис-

ходной цены игры необходимо из полученной цены игры вычесть 2, а затем

35					17
разделить на 10. Таким образом, получаем цену исходной игры:			2 :10				.
	9				90

Задача 5. (сведение матричной игры к задаче линейного программирова-

ния).

Дана платежная матрица:

Прибавляя ко всем элементам матрицы (Пij) число K= 5, приходим к мат-

рице модифицированной игры

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

149

Воспользовавшись симплекс-методом, находим решение:

Таким образом, цена модифицированной игры

а цена исходной игры ν*=( 1 )* – 5 = 0. При этом

p1* ( 1 )* x ,
		i 1,3.
i	i

т.е. оптимальная смешанная стратегия первого игрока

*		1		1		1	T
s x1			,		,
				2		4
	4

В рассматриваемой игре (Пij)T = (Пij) и s*х2 s*х1 . Нетрудно найти опти-

мальную смешанную стратегию второго игрока, решив соответствующую зада-

чу линейного программирования, и убедиться в том, что она совпадает с опти-

мальной смешанной стратегией первого игрока.

Завершая рассмотрение игр двух участников с нулевой суммой без седло-

вых точек, заметим, что при использовании смешанных стратегий перед каж-

дой партией игры каждым игроком запускается некий механизм (бросание мо-

неты, игральной кости или использование датчика случайных чисел), обеспечи-

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

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

При этом ожидаемые теоретические результаты игры, при неограниченном воз-

растании числа разыгрываемых партий, стремятся к их истинным значениям.

150