МО практики

резервов времени операций, из которых наиболее важными являются полный и свободный резервы.

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

Rijn =t*j −(ti +tij ) = t*j −tijр.о.

Свободный резерв времени операции Rijс показывает, насколько можно увеличить продолжительность или отсрочить начало выполнения операции (i, j) , при условии, что начальное и конечное ее события свершаются в ожидаемое время:

Rijс = t j −(ti +tij ) = t j −tijр.о.

Так резервы времени операции (4,6) сетевого графика составляют (Рис.

4.5):

Rn	= t	* −(t		4	+t	46	) =10 −(4 +1) = 5;
46		6
Rc	= t	6	−(t	4	+t	46	) = 5 −(4 +1) = 0;
46

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

Рассчитайте сеть, которая задается матрицей смежности C и матрицей пропускных способностей R.

41

1)				0	1	1	0	0	0						0			10	18	0	0	0
				0	0	0	0	1	1						0			0	0	0	14	1
C=				0 1 0 1 0 0									R=		0 10				0	17 0		0
				0	1	0	0	1	1						0			9	0	0	22	12
				0	0	0	0	0	1						0			0	0	0	0	18
				0	0	0	0	0	0						0			0	0	0	0	0
2)				0	1	1	0	0	0						0			11	33	0	0	0
				0	0	0	1	1	0						0			0	0	14	4	0
C=				0 1 0 1 1 0									R=		0 5				0	15	23	0
				0	0	0	0	0	1						0			9	0	0	0	23
				0	0	0	1	0	1						0			0	0	11	0	22
				0	0	0	0	0	0						0			0	0	0	0	0
3)			0		1	1	1	0	0								0	20	21	22	0	0
			0		0	1	1	1	0								0	0	5	13	14	0
C=			0		0	0	0	12	28				R=				0	0	0	0	12	28
			0		0	1	0	1	1								0	0	12	0	11	10
			0		0	0	0	0	1								0	0	0	0	0	17
			0		0	0	0	0	0								0	0	0	0	0	0

42

5 Практическое занятие №5

Решение задач теории игр, определенных матрицами . 5.1 Общие сведения

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

Игровые схемы можно применять во многих экономических ситуациях. Выигрышем могут при этом выступать величина прибыли, себестоимость, эффективность использования дефицитных ресурсов, производственных фондов, и т.д.

Существенным обстоятельством является то, что методы и рекомендации теории игр разработаны применительно к таким конфликтным ситуациям, которые обладают свойством многократной повторяемости. Если конфликтная ситуация реализуется однократно или ограниченное число раз, то рекомендации теории игр становятся малоэффективными.

Анализ реальной конфликтной ситуации требует ее существенного (иногда радикального) упрощения – учета лишь наиболее существенных для конфликта факторов. В связи с этим, можно рассматривать игру как упрощенную математическую модель конфликтной ситуации, характеризующуюся наличием определенных правил. Эти правила устанавливают:

1.выбор образа действия игроков на каждом этапе игры;

2.информацию, которой обладает каждый игрок при осуществлении таких выборов;

3.плату для каждого игрока после завершения любого этапа игры.

43

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

К числу определяющих характеристик игр можно отнести следующие:

1.имеется n конфликтующих сторон (игроков), принимающих решения, интересы которых не совпадают;

2.сформулированы правила выбора допустимых стратегий, известные игрокам;

3.определен набор возможных конечных состояний игры (например, выигрыш, проигрыш, ничья);

4.всем участникам игры (игрокам) заранее известны платежи, соответствующие каждому возможному конечному состоянию. Конфликтные ситуации, встречающиеся в практике, порождают

различные виды игр. Классификация игр возможна по разным признакам.

А) По количеству игроков. В игре может принимать участие любое конечное число игроков. Если игроков всего двое, или игроки объединяются в две группы, преследующие противоположные цели, то имеет место парная игра. В зависимости от количества стратегий в игре они делятся на конечные и бесконечные.

Б) В зависимости от взаимоотношений участников различают бескоалиционные (участники не имеют права заключать соглашения) и коалиционные игры (иногда используются синонимы – некооперативные и кооперативные игры соответственно).

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

44

Г) По виду функции выигрыша игры делятся на матричные, биматричные и др. В матричных играх (при двух участниках) выигрыши первого игрока задаются матрицей, в биматричных – выигрыши каждого игрока задаются своей матрицей.

Д) По количеству ходов игры делятся на одноходовые (выигрыш распределяется после одного хода каждого игрока) и многоходовые (выигрыш распределяется после нескольких ходов).

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

В дальнейшем мы ограничимся рассмотрением парных матричных игр с нулевой суммой. Задание стратегий двух игроков в парной игре такого типа полностью определяет ее исход, т.е. выигрыш одного или проигрыш другого. Как уже отмечалось, результаты конечной парной игры с нулевой суммой можно задавать матрицей, строки и столбцы которой соответствуют различным стратегиям 1-го и 2-го игроков соответственно, а ее элементы - выигрышам одной стороны (равные проигрышам другой). Эта матрица называется платежной матрицей или матрицей игры.

4.2 Матричные игры с нулевой суммой

Рассмотрим парную игру с нулевой суммой. Пусть игрок I имеет m стратегий (1, 2,…,m), а игрок II - n стратегий (1, 2,…, n). Такая игра называется матричной игрой размерности m×n .

Предположим, игрок I выбрал одну из своих возможных стратегий i

(i =1, m ), а игрок II, не зная результата выбора игрока I, - стратегию j (i =1, n ).

Выигрыши игрока I W1 (i, j) и игрока II W2 (i, j) в результате выбора стратегий удовлетворяют соотношению W1 (i, j) +W1 (i, j) =0 ; таким образом, если ввести обозначение W1 (i, j) =aij , то W2 (i, j) = −aij .

45

Элементы аij для каждой пары стратегий (i, j) считаются известными и записываются в платежную матрицу (табл. 5.1), строки которой соответствуют стратегиям игрока I, а столбцы - стратегиям игрока II. Каждый положительный элемент aij матрицы определяет величину выигрыша игрока I и,

соответственно, проигрыша игрока II при применении ими соответствующих стратегий. Естественно, целью игрока I является максимизация своего выигрыша, тогда как игрока II - минимизация своего проигрыша.

Таблица 5.1Платежная матрица парной игры с нулевой суммой

II	1	2	…	n
I
1	a	a	…	a1n
	11	12
2	a21	a22	…	a2n
…	…	…	…	…
m	am1	am2	…	amn

5.5Решение парных матричных игр с нулевой суммой. Принцип

минимакса

Используя платежную матрицу парной игры с нулевой суммой (табл. 5.1),

определим наилучшую стратегию игрока I среди стратегий i ( i = 1,m ) и

наилучшую стратегию игрока II среди стратегий j (j=1, n ).

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

Проанализируем стратегии игрока I. Игрок I, выбирая стратегию i , должен рассчитывать, что игрок II ответит на нее той из своих стратегий j , для которой выигрыш игрока I будет минимальным. Найдем минимальное число aij в каждой строке матрицы и, обозначив его αi (i =1, m) , запишем в добавочный столбец платежной матрицы (см. табл. 5.2):

46

αi = min aij ,i =1, m .					(5.1)
j
Зная числа αi (свои выигрыши при применении i-х стратегий и разумном
ответе игрока II), игрок I должен выбрать такую стратегию, для которой αi
максимально. Обозначив это максимальное значение как α
(т.е. α =maxαi и используя (5.1), получим
	i
α =max min aij					(5.2)
i	j
Таблица 5.2
II	1	2	. . .	n	αi
I
1	a11	a12	. . .	a1n	α1
2	a21	a22	. . .	a2n	α2
. . .	. . .	. . .	. . .	. . .	. . .
m	am1	am2	. . .	amn	αm
β j	β1	β2	. . .	βn

Величина α представляет собой гарантированный выигрыш, который может обеспечить себе игрок I; она называется нижней ценой игры (максимином). Стратегия, обеспечивающая получение нижней цены игры α , называется максиминной стратегией. Если игрок I будет придерживаться своей максиминной (перестраховочной) стратегии, то ему гарантирован выигрыш, не меньший α при любом поведении игрока II.

В свою очередь, второй игрок стремится уменьшить свой проигрыш или, что то же самое, выигрыш игрока I обратить в минимум. В связи с этим, для выбора своей наилучшей стратегии он должен найти максимальное значение выигрыша игрока I в каждом из столбцов и среди этих значений выбрать наименьшее. Обозначим через βj максимальный элемент в каждом столбце j

и запишем эти элементы в дополнительной строке табл. 5.2. Наименьшее

47

значение	среди	βj	обозначим через β ;				эта величина			представляет собой
верхнюю цену игры (минимакс), которая определяется по формуле
β =min max a
	j	i	ij .							(5.3)
Стратегия игрока II, обеспечивающая «выигрыш» β , является его
минимаксной стратегией. Выбор минимаксной стратегии игроком II
гарантирует ему проигрыш не больше β .
В теории игр доказывается, что для нижней и верхней цены игры всегда
справедливо неравенство
max min aij ≤ min max aij , i =						,	j =		,	α ≤ β
					1, m			1, n
i	j		j	i

Игры, для которых нижняя цена равна верхней, т.е. α = β , называются играми с седловой точкой.

Общее значение нижней и верхней цены игры в играх с седловой точкой называется чистой ценой игры γ , а стратегии (i*, j*) , позволяющие достичь этого значения, - оптимальными чистыми стратегиями; элемент aij* =γ является одновременно минимальным в i-й строке и максимальным в j-м столбце. Оптимальные стратегии определяют в игре положение равновесия, поскольку каждому из игроков невыгодно отходить от своей оптимальной стратегии. Чистую цену игры γ в игре с седловой точкой игрок I не может увеличить, а

игрок II - уменьшить. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.

5.5Игры без седловых точек

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

48

меньше α , а второму проигрыш не большеβ . Учитывая, что α < β ,

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

pI = ( p1, p2 ,..., pm ) и qII = (q1, q2 ,..., qn )

где	pi ≥0 , q j ≥0	- вероятности применения соответствующих чистых
стратегий.	Очевидно,	должны выполняться условия нормировки для

вероятностей

m	m
∑pi =1,	∑qi =1,
i=1	j=1

Одна из основных теорем теории игр утверждает, что любая конечная игра двух лиц с нулевой суммой имеет, по крайней мере, одно решение, возможно, в смешанных стратегиях. Из этой теоремы следует, что каждая конечная игра имеет цену. Обозначим ее так же, как чистую цену игры, через γ . Цена игры γ – средний выигрыш, приходящийся на одну партию, – всегда удовлетворяет условию α ≤γ ≤ β , т.е. лежит между нижней (α ) и верхней ( β )

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

Стратегии игроков, входящие в их оптимальные смешанные стратегии, называются активными.

49

(α ≠ β) .

5.5Использование линейной оптимизации при решении

матричных игр

Пусть игра m×n не имеет оптимального решения в чистых стратегиях,

т.е. седловая точка отсутствует

Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое число L, переводящее платежи в область неотрицательных значений - очевидно, при этом цена игры увеличится на L, а решение задачи не изменится). Таким образом, предполагаем, что γ >0.

Будем искать решение игры в смешанных стратегиях

p*I = ( p1, p2 ,..., pm ) ; q*II = (q1,q2 ,...,qn )

Применение игроком I оптимальной смешанной стратегии pI

гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цены игры γ .

Пусть игрок II применяет свою активную чистую j-ю стратегию, а игрок I

– свою оптимальную стратегию pI . Тогда средний выигрыш игрока I будет равен

γ j = a1 j p1 +a2 j p2 +...+aij pi +...+amj pm , j =1,n.

Учитывая, что γ j ( j =1, n) не может быть меньше γ , запишем условия:

a11 p1 +a21 p2

+...+ai1 pi +...+am1 pm

≥γ;

a12 p1 +a22 p2 +...+ai2 pi +...+am2 pm ≥ γ;

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

a p

+a

2 j

p

2

+...+a

ij

p

i

+...+a

mj

p

m

≥γ;

1 j 1

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

a

p

+a

p

+ +a

p

+ +a

p

2n

2

in

i

mn

m

≥ γ.

1n 1

(5.4)

50