Исследование операций / ИСО Учебник

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

Логика применения каждого из статистических критериев основывается на 2-х шаговой процедуре:

•на первом шаге для каждой Si стратегии оценивается наиболее вероятный выигрыш;

•на втором шаге выбирается стратегия, которая обеспечивает наибольший выигрыш.

Опираясь на платежную матрицу (табл.4.1.2 (5)) рассмотрим применение четырех однозначных статистических критерия.

Критерий Вальда. (критерий глубокого пессимизма).

Этот критерий является наиболее осторожным, поскольку он основывается на выборе наилучшей стратегии из наихудших возможностей состояний природы Aj. Тогда оценка лучшего гарантированного выигрыша равна:

П = max min П , (S* – выбранная стратегия, соответствующая П*)

i j ij i

Критерий Лапласа.

Этот критерий ориентируется на среднюю оценку ожидаемого выигрыша для каждой стратегии при гипотезе, при состоянии природы Aj. Тогда оценка выигрыша равна:

				1	n
		= max			∑Пij , (			, выбранная стратегия, соответствующая		).
	П						Si		П
		i	n j =1

Критерий крайнего оптимизма.

Этот критерий основывается на выборе наилучшей стратегии при наиболее благоприятных состояниях «природы». Тогда оценка выигрыша равна:

~	~	~
П = max max Пij , ( Si – выбранная стратегия, соответствующая		П)
i	j

Критерий Гурвица:

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

15

				~
			, где
П′= max α max Пij + (1-α)min Пij				0 ≤α≤1., ( Si – выбранная стратегия,
i	j
	j

соответствующая ~ )

П

Критерий Гурвица есть некий баланс между крайним оптимизмом и крайним пессимизмом, установленный путем взвешивания обоих подходов в поведении игрока с соответствующими весами α и (1−α). При α =1 мы имеем критерий крайнего оптимизма; при α =0 имеем критерий Вальда.

Критерий Сэвиджа.

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

Для оценки потерь игрока при выборе не лучшей стратегии Si для состояния «природы» Аj строится матрица сожаления (потерь) С= (Сij);

Cij = max Пij - Пij, для каждого j = 1n .

i

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

С= min max Cij, (Si выбранная стратегия, соответствующая C )

i j

Рассмотрим пример пусть предприятие имеет 4 стратегии выпуска продукции. Точное число клиентов неизвестно, но возможно оценить 4 варианта объема спроса на продукцию. Платежная матрица игры описывает объем получаемой прибыли предприятия от реализации продукции по каждой из стратегий в зависимости от вариантов прогноза спроса (табл. 4.2.2 (6)).

Таблица 4.2.2

		Платежная матрица прибыли предприятия
Страте-					Состояние спроса
гия	A1	A2	A3	A4	max	min	1	Средняя
пред-					j	j	∑n∑Пi	оценка,
					Пij	Пij
приятия							1/n	при
								α =0,3
S1	50	100	180	250	250	50	145	110

16

S2	80	70	80	230	230	70	115	118
S3	210	180	120	210	210	120	180	147
S4	300	220	190	150	300	150	215	205
max Пij	300	220	190	250
i

Решение приведенного примера включает несколько этапов.

Этап 1. Для каждой стратегии S1, S2, S3, S4 рассчитываем оценки получаемой прибыли и заносим значения в дополнительные столбцы матрицы табл. 4.2.2 (6):

а) максимальная оценка прибыли для каждой стратегии =max Пij

j

б) минимальная оценка для каждой стратегии =min Пij

j

в) средняя оценка прибыли для каждой стратегии = 1 ∑4 Пij .

4 j=1

г)

средняя

оценка

прибыли

по

Гурвичу

при

(α =0,3 )α max j Πij + (1−α) min j Πij

Этап 2. Применяем критерии для оценки выигрыша.

а)

по

критерию

Вальда

объем,

получаемой

прибыли

П* =max{50;70;120;150}=150 , что соответствует стратегии S4;

j

б)

по

критерию

Лапласа

объем,

получаемой прибыли

=

П

max{145;115;180;215}=215 , что соответствует стратегии S4;

j

в)

по

критерию

крайнего

оптимизма

объем

получаемой

прибыли

П=max{250;230;210;300}=300 , что соответствует стратегии S4;

~

j

г)

по критерию

Гурвица (при

α =0,3 )

объем,

получаемой

прибыли

П′=max{110,118,147,205}, что соответствует стратегии S4.

j

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

Этап 3. Для применения критерия выбора Сэвиджа строим матрицу ущерба C будет иметь вид:

250		120	10	0
	220	150	110	20
						,
C =	90	40	70	40
	0	0	0	100

а оценка потерь прибыли по критерию Сэвиджа будет равна:

17

С = min{250,220,90,100}=90, что соответствует стратегии S3.

Как мы видим выбор стратегии по критерию Сэвиджа (S3) не совпадает с выбором по другим критериям (S4). Окончательный выбор из S3 и S4 остается за игроком.

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

18

из матрицы П1 (чис-

из матрицы П2 (чис-

Тема 4.3 Антагонистические игры. Матричные игры двух лиц с нулевой суммой.

Лекция 4.3.1 Антагонистические игры двух лиц с нулевой суммой в матричном виде в чистых стратегиях.

Данный тип игр достаточно хорошо и полно разработан. Если игра представлена в нормальной форме то выбор стратегий может быть описан для каждого игрока платежными матрицами:

для игрока 1: П1={Пij1}, i =1, m; j =1, n для игрока 2: П2={Пij2 },i =1, m; j =1, n

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

а) первый игрок выбирает вектор строку Пi (i=1, m тую i-ую стратегию)

б) второй игрок выбирает вектор столбец П2j ( j =1, n)

тую j-ую стратегию).
Нулевая сумма игры, означает, что
П1ij + Пij2 = 0 ,	(4.3.1)
следовательно
П1ij = -Пij2 ,	(4.3.2)

т.е. платежная матрица игрока 2 равна платежной матрице игрока 2 умноженной на (-1). Следовательно, в игре выбор чистых стратегий игроков можно заменить выбором стратегий по одной матрице П:

Пij = П1ij = -Пij2 , где Пij =	П11	.....Πij .....П1n	, где Пij = Пij1 = −Пij	2 , (4.3.3)
	Πi1	.....Πij ......Πin
	Пm1....Πmj ....Пmn

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

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

19

данным игроком стратегия становится известной противнику, который затем выбирает свою оптимальную стратегию. Пусть игрок 1 считает, что какую бы строку он не выбрал, игрок 2 выберет столбец, максимизирующий выигрыш и тем самым минимизирующий выигрыш игрока 1. Тогда можно исключить из платежной матрицы все элементы, оставив в каждой строке только по одному элементу, соответствующему минимальному платежу. Оптимальная стратегия игрока 1, которая обеспечить ему наибольший из возможных выигрышей вне зависимости от стратегии противника (гарантированный выигрыш), будет состоять в выборе строки с самым высоким значением из таких минимальных платежей. Таким образом, игрок 1 выбирает i-ю стратегию, которая является решением задачи для игрока 1:

П1*=max min	(4.3.4)
j i
П1* - (нижняя цена игры);

i - cтратегия 1 игрока , соответствующая максимальному значению минимумов по строкам (П1* ), называется максиминной стратегией.

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

платежа. Таким образом, игрок 2	выбирает j-ю стратегию, которая является
решением задачи для игрока 2:
П2*=	min max Пij		(4.3.5)
	j	i

П2* - верхняя цена игры;

j* cтратегия игрока 2, соответствующая минимальному значению максимумов столбцов (П2*), называется минимаксной стратегией.

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

Пij ≥ max min Пij	(4.3.6)
i j

20

Если игрок 2 избирает минимаксную стратегию, то его проигрыш будет не больше минимаксного значения, т.е.

Пij ≤ min max Пij	(4.3.7)
j i

Если

max min Пij = max min Пij = П* ,		(4.3.8)
i j	j i

то игроки получают свои гарантированные платежи. В этом случае их стратегии оказываются совместимыми, а платежная матрица имеет седловую точку на пересечении i*-й строки и j*-го столбца, т.е. элемент П*ij является од-

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

называются вполне определенными играми.

Рассмотрим пример вполне определенной игры 2-х лиц с нулевой суммой с платежной матрицей П:

П=	2		1	4		(4.3.9)
		-1	0	6

В данном пример игры, в которой игрок 1 располагает двумя стратегиями. А игрок 2 – тремя. Игрок 1 рассчитывает, что если он выберет первую строку, то противник может выбрать второй столбец, так что выигрыш будет равен 1. Если же он выберет вторую строку, то противник может взять первый столбец, так что выигрыш будет равен -1. Эти два числа есть не что иное, как минимумы строк, показанные в табл. 4.2.1.

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

21

второй стратегии, при которой его проигрыш не превосходит 1. следовательно, в этой игре существуют совместимые выборы, т.е.

V= max min Пij= min max Пij =1		(4.3.10)
i j	j i

И, следовательно, существует седловая точка матрицы,, являющаяся ценой игры (V) для игроков. Седловая точка соответствует положению равновесия, если один из игроков использует стратегию, соответствующую седловой точке, то другому выгоднее всего избрать свою стратегию, также отвечающую седловой точке. Так, если в данном примере игрок 1 использует первую стратегию, то для игрока 2 оптимальной будет вторая стратегия, а если игрок 2 применяет вторую стратегию, то для игрока 1 оптимальной будет первая стратегия. Разумно ожидать, что в игре такого типа оба партнера изберут стратегию седловой точки. Однако не все игры двух участников с нулевой суммой является вполне определенными. В общем случае

max min Пij ≤min max Пij		(4.3.11)
i j	j i

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

Так примером не вполне определенной игры может служить игра двух лиц с платанной матрицей П

	6	- 2	3		(4.3.12)
П =
	- 4	5	4

Если игроки следуют изложенным ранее правилам, то получим, что седловая точка отсутствует:

max min Пij =− 2 4 =max min Пij

(4.3.13)

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

22

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

23

Лекции 4.3.2 Антагонистические игры двух лиц с нулевой суммой в смешанных стратегиях.

Как было рассмотрено в предшествующей лекции игра двух лиц с нулевой суммой не всегда имеет решение в чистых стратегиях.

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

зать с помощью вектора (вектора-строки) вероятностей
Р1={pi }( р11 , р12 ,.........р1m ),	(4.3.14)

где р1i - вероятность выбрать i-ю стратегию, (i=1,2,……..,m). Например, век-

тор ( 14 , 12 ,0,......., 14 ) соответствует смешанной стратегии, при которой игрок 1

выбирает строку 1 с вероятностью 14 и строку 2 с вероятностью 14 , а строку m с вероятностью 14 . Так как числа, входящие в вектор р1, является вероят-

ностями, то они должны быть неотрицательными, а их сумма должна равняться единице, т.е.

m
∑р1i =1, р1i ≥ 0, i =1, 2,....., m.	(4.3.15)

i=1

Эти условия можно записать и в векторных обозначениях

р11'= 1, р1 ≥0,

(4.3.16)

где 1 = (1,1,…….,1), т.е. это вектор-строка с элементами, равными еди-

нице.

Точно так же игрок 2 выбирает вектор (вектор-столбец) вероятностей

P1={pi }(р12 , р22 ,....., рn2 ) ',

(4.3. 17)

24