Тырсин А.Н. - Системный анализ. Модели и методы (без обложки)

6.Определяем ординату точки c пересечения линий (b11 b12) и (b21 b22). Она равна .

7.Определим абсциссу точки пересечения c. Она равна p2, а p1 = 1 – p2. Выпишем решение и представим оптимальную стратегию игры:

p1 = 0,375, p2 = 0,625, = 0,55,

S	0		A1	A2
					.
			0,375
				0,625

Вывод. При установке новой системы ЭВМ, если неизвестны условия решения задач заказчика, на работу ЭВМ A1 должно приходиться 37,5% времени, а на работу ЭВМ A2 62,5%. При этом выигрыш составит 55% по сравнению с предыдущей системой ЭВМ.

6.3.4. Свойства решений матричных игр
Определение 6.1. Систему
W (A,B,G) ,	(6.2)

где A = {A1, A2, ... , Am} – множество стратегий игрока 1; B = {B1, B2, ... , Bn}

– множество стратегий игрока 2; G – платежная матрица вида (6.1), назовем конечной матричной игрой m n.

Определение 6.2. Пусть задана матричная игра (6.2). Назовем функцию K(Ai , Bj ) aij функцией выигрыша игрока 1, (Ai , Bj ) A B .

Определение 6.3. Стратегия A1 игрока 1 доминирует (строго доминирует) над стратегией A2, если

K(A1, B) K(A2, B) (K(A1, B) > K(A2, B)), B B.

Стратегия B1 игрока 2 доминирует (строго доминирует) над стратегией B2, если

K(A, B1) K(A, B2) (K(A, B1) < K(A, B2)), A A.

При этом стратегии A2 и B2 называются доминируемыми (строго доминируемыми).

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

Свойства решений конечных матричных игр.

Приведем свойства матричных игр. Более подробно данный вопрос изложен в учебниках по матричным играм, например в [20].

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

101

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

2 . Ни одна строго доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии.

3 . Пусть W (A,B,G) – конечная матричная игра, W (A \ A ,B,G)

–подыгра игры W, а A – чистая стратегия игрока 1 в игре W, доминируемая некоторой стратегией A , спектр которой не содержит A . Тогда всякое решение (p0, q0, ) игры W является решением игры W.

4 . Пусть W (A,B,G) – конечная матричная игра, W (A,B \ B ,G)

–подыгра игры W, а B – чистая стратегия игрока 2 в игре W, доминируемая некоторой стратегией B , спектр которой не содержит B . Тогда всякое решение (p0, q0, ) игры W является решением W.

5 . Если для чистой стратегии A игрока 1 выполнены условия свойства 3 , а для чистой стратегии B игрока 2 выполнены условия свойства 4 , то всякое решение игры W (A \ A ,B \ B ,G) является

решением игры W (A,B,G) .
6 . Тройка (p0, q0, )				является решением игры W (A,B,G) тогда и
только	тогда,	когда		(p0, q0, c + d)			является	решением			игры
W (A,B,cG dE) ,			где	E –	единичная		матрица,	c > 0,		d –	любое
вещественное число.
7 .	Для	того,	чтобы		p0 ( p0 , p0		, ... , p0 )	была		оптимальной
					1	2	m
смешанной стратегией матричной игры с матрицей G и ценой игры ,
необходимо и достаточно выполнение неравенств
m
aij pi0 , (j = 1, , n).											(6.3)
i 1
Аналогично для игрока 2: для того,						чтобы q0 (q0			, q0	, ... , q0 )	была
								1	2	n

оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение неравенств

n
aij q0j	, (i = 1, , m).	(6.4)

j 1

Из свойства 7 вытекает: чтобы установить, является ли предполагаемые (p0, q0) и решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (6.3) и (6.4). С другой стороны, найдя неотрицательные решения неравенств (6.3) и (6.4) совместно со следующими уравнениями

m		n
pi0	1,	q0j	1,	(6.5)
i 1		j 1

получим решение матричной игры.

102

Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (6.3), (6.4) и линейных уравнений (6.5). Однако это требует большого объема вычислений, которое растет с увеличением числа чистых стратегий игроков. Например для платежной матрицы 3 3 имеем систему из 6 неравенств и 2 уравнений. Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства

max min aij = min max aij .
i	j	j	i

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

Замечание 6.1. Отметим, что исключение доминируемых (не строго) стратегий может привести к потере некоторых решений. Если же исключаются только строго доминируемые стратегии, то множество решений игры не изменится.

Пример 6.5. Пусть W (A,B,G) , где A = {1, 2, 3, 4}; B = {1, 2, 3, 4}, а

платежная матрица G задана следующим образом:

						1		2	3		4
			1			2C		C	2C		3C
			2			3C 3C 2 C					2C
G													, С > 0.
			3			2C 2C C					C
			4			C		C	C		C 2
Решение. Прежде всего заметим, что по свойству 6 достаточно
решить игру W 1 (A,B,G1 ) ,
								1	2	3	4
						1		2	1	2	3
			1			2		3	3 2	1	2
	1
где G					G 3			2	2	1	1	.
			C
						4		1	1	1
											1 2

Элементы 4-й строки матрицы G1 меньше или равны соответствующих элементов 3-й строки и поэтому 3-я стратегия игрока 1 доминирует над 4-й. Кроме того, элементы 1-го столбца матрицы G1 больше или равны соответствующих элементов 2-го столбца, Следовательно, 2-я стратегия игрока 2 доминирует над его 1-й стратегией.

103

Далее,		из	свойства 5 следует, что			всякое решение игры
W 2 (A \ {4},B \ {1},G1 ) является решением игры						W1. В матричной форме
игру W2 можно представить матрицей
		2	3	4
1		1	2	3
G 2 2
		3 2	1	2	.
3		2	1	1

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

получим,	что всякое решение игры W 3 (A \ {4,2},B \ {1,4},G2 ) является
решением игры W2, а значит и игры W1. Игра W3 определяется матрицей
		2	3
G3	1	1	2
				.
		2	1
	3

Матрица G3 не имеет седловой точки, а игра W3 не имеет решения в чистых стратегиях, т.е. оптимальные стратегии игроков являются смешанными. Эти стратегии (в данном случае) легко найти из анализа структуры матрицы G3. Поскольку матрица G3 симметрична, можно предположить, что игроки в оптимальной стратегии используют свои чистые стратегии с равными вероятностями.

Действительно, если игрок 1 выбирает с равными вероятностями стратегии 1 и 3, то при применении любой из двух чистых стратегий игроком 2 математическое ожидание выигрыша игрока 1 будет равным либо 12 1 12 2 32 , либо 12 2 12 1 32 .

Аналогично, если игрок 2 использует свои чистые стратегии 2 и 3 с равными вероятностями, то математическое ожидание его проигрыша будет равно 3/2. Следовательно, указанные стратегии являются оптимальными в игре W3, а величины 3/2 – значением игры W3. Из предыдущего следует, что эти стратегии оптимальны и в W1.

			0				1								1
Таким образом, стратегия	p									; 0;							; 0 является оптимальной
							2								2
	0						1				1
стратегией игрока 1, стратегия q				0;						;				; 0			– оптимальной стратегией
							2				2
игрока 2 в игре W1, а значение игры W1 равно 3/2. В силу свойства 4
		0	; q		0	;		3C
решением игры W будет тройка p												.
								2

104

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

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

Итак, пусть дана матричная игра с матрицей G {aij } порядка m n.

Согласно

свойству

7

оптимальные

смешанные

стратегии

p ( p1,

p2 , ... , pm ) , q (q1, q2 , ... , qn ) игроков 1

и 2 и цена игры должны

удовлетворять соотношениям

m

aij pi , ( j 1, n),

i

1

m

(6.6)

pi 1,

i 1

p

i

0,

(i 1, m),

n

aij q j , (i 1, m),

j 1

n

(6.7)

q j 1,

j 1

q

j

0, ( j 1, n).

Разделим все уравнения и неравенства в (6.6) и (6.7) на (это можно сделать, т.к. по предположению ( > 0) и введем обозначения:

p

i

q j

x

i

(i 1, m) ,

y

j

( j 1, n) .

Тогда (6.6) и (6.7) перепишется в виде:

m

aij xi 1, i 1

n

aij y j 1, j 1

	m	1
	xi			,		xi 0 , (i 1, m) ,
	i 1
	n			1
	y j				,	y j 0, ( j 1, n) .
	j 1

Игрок 1 стремится найти такие значения pi и, следовательно, xi, чтобы цена игры была наибольшей, поэтому решение первой задачи сводится к нахождению таких неотрицательных значений xi (i 1, m) , при которых

105

m	m
xi min , aij xi 1.		(6.8)
i 1	i 1

Игрок 2 стремится найти такие значения qj и, следовательно, yj, чтобы цена игры была наименьшей, поэтому решение второй задачи сводится к нахождению таких неотрицательных значений yj, ( j 1, n) , при которых

n	n
y j max ,	aij y j 1.	(6.9)
j 1	j 1
Формулы (6.8) и (6.9) выражают двойственные друг другу задачи
линейного программирования. Решив их, получим значения xi		(i 1, m) , yj

( j 1, n) и . Тогда смешанные стратегии, т.е. pi и qj найдем по формулам: pi xi (i 1, m) , q j y j ( j 1, n) .

Пример 6.6. Найти решение игры, определяемой матрицей

	0	1	1
G	0	1	0	.
	1	0
			1

Решение. При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу

		1	2	0
		1	0	1
G1					.
		2	1	0

Составим две взаимно-двойственные задачи линейного программирования:

	p1 p2 p3 min,						q1 q2 q3				max,
p1 p2					2 p3 1,	q1 2q2					1,
					p3 1,		q1			+ q3 1,
2 p1
					p3 1,	2q1 q2					1,
	p , p	2	, p	3	0,	q , q		2	, q	3	0.
	1						1

6.4. Принятие решений в условиях риска (Статистические игры)

6.4.1. Риск и его измерение

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

106

спроса на товары, неабсолютная надежность процессов производства, неточность информации, погодные условия и др. [28].

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

– ЛПР, называемый игроком 1. Игрок 2 (природа) сознательно против игрока 1 не действует, а выступает как не имеющий конкретной цели и случайным образом выбирающий очередные «ходы» партнер по игре. Поэтому термин «природа» характеризует некую объективную действительность.

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

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

-выявление объективных и субъективных факторов, влияющих на конкретный вид риска;

-анализ выявленных факторов;

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

-установка допустимого уровня риска;

-анализ отдельных операций по выбранному уровню риска;

-разработка мероприятий по снижению риска.

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

Пример 6.7 [28]. Пусть имеются два инвестиционных проекта. Первый с вероятностью 0,6 обеспечивает прибыль 15 млн. руб., однако с вероятностью 0,4 можно потерять 5,5 млн. руб. Для второго проекта с вероятностью 0,8 можно получить прибыль 10 млн. руб. и с вероятностью 0,2 потерять 6 млн. руб. Какой проект выбрать?

107

Решение. Оба проекта имеют одинаковую среднюю прибыльность,

равную (0,6 15 + 0,4 (–5,5) = 0,8 10 + 0,2 (–6) = 6,8 млн. руб. Однако среднее квадратическое отклонение прибыли равно:

-для 1-го проекта (0,6 (15 – 6,8)2+0,4 (–5,5 – 6,8)2)1/2 = 10,04 млн. руб.,

-для 2-го проекта (0,8 (10 – 6,8)2+0,2 (–6 – 6,8)2)1/2 = 6,4 млн. руб.,

поэтому более предпочтителен второй проект.

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

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

-критерий ожидаемого значения;

-критерий «ожидаемое значение – дисперсия»;

-критерий предельного уровня;

-критерий наиболее вероятного исхода.

Критерий ожидаемого значения максимизирует ожидаемую прибыль (или минимизирует ожидаемые затраты). Использование ожидаемых величин предполагает возможность многократного решения одной и той же задачи, пока не будут получены достаточно точные расчётные формулы. Математически это выглядит так: пусть Х – случайная величина с математическим ожиданием MX и дисперсией DX. Если x1, x2, ..., xn – значения случайной величины X, то среднее арифметическое их значений x (x1 x2 ... xn ) / n имеет дисперсию DX / n . Таким образом, при n

, имеем DX / n 0 и x MX .

Другими словами, при достаточно большом объёме выборки разница между средним арифметическим и математическим ожиданием стремится к нулю (так называемая предельная теорема теории вероятности). Следовательно, использование критерия ожидаемого значения справедливо только в случае, когда одно и тоже решение приходится применять достаточно большое число раз. Справедливо и обратное: ориентация на ожидания будет приводить к неверным результатам для решений, которые приходится принимать небольшое число раз.

Критерий «ожидаемое значение – дисперсия» является модификацией критерия ожидаемого значения. В нем максимизация ожидаемого значения прибыли сочетается с минимизацией её дисперсии.

Критерий предельного уровня не дает оптимального решения,

например, максимизирующего прибыль, или минимизирующего затраты.

108

ЛПР на основании субъективных соображений определяет наиболее приемлемый способ действий.

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

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

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

Пример 6.8. Требуется принять решение о том, когда необходимо проводить профилактический ремонт ПЭВМ, чтобы минимизировать потери из-за неисправности. В случае, если ремонт будет производиться слишком часто, затраты на обслуживание станут большими при малых потерях из-за случайных поломок. Так как невозможно предсказать заранее, когда возникнет неисправность, необходимо найти вероятность того, что ПЭВМ выйдет из строя в период времени t. В этом и состоит элемент «риска». Математически это выглядит так: ПЭВМ ремонтируется индивидуально, если она остановилась из-за поломки. Через T интервалов времени выполняется профилактический ремонт всех n ПЭВМ. Необходимо определить оптимальное значение Т, при котором минимизируются общие затраты на ремонт неисправных ПЭВМ и проведение профилактического ремонта в расчёте на один интервал времени.

Пусть рt – вероятность выхода из строя одной ПЭВМ в момент t, а nt – случайная величина, равная числу всех вышедших из строя ПЭВМ в тот же момент. Пусть далее С1 – затраты на ремонт неисправной ПЭВМ и С2 – затраты на профилактический ремонт одной машины.

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

		T 1
		C1 M (nt ) C2 n
	ОЗ	t 1	,
		T

где M(nt) – математическое ожидание числа вышедших из строя ПЭВМ в момент t. Так как nt имеет биномиальное распределение с параметрами (n, pt), то M(nt) = npt. Таким образом,

109

		T 1
		n(C1 pt C2 )
	ОЗ	t 1	.
		T

Необходимые условия оптимальности T* имеют вид:

ОЗ (T*–1) ОЗ (T*), ОЗ (T*+1) ОЗ (T*).

Следовательно, начиная с малого значения T, вычисляют ОЗ(T), пока не будут удовлетворены необходимые условия оптимальности.

Пусть С1 = 100; С2 = 10; n = 50. Значения pt имеют вид (табл. 6.3):

Таблица 6.3. Результаты расчета

			T	рt	T 1		ОЗ(Т)
					pt
					t 1
		1		0,05	0	500
		2		0,07	0,05	375
			3	0,10	0,12		366,7
		4		0,13	0,22	400
		5		0,18	0,35	450
T* 3,	ОЗ(Т*) 366,7.

Следовательно, профилактический ремонт необходимо делать через T* = 3 интервала времени.

6.4.2. Статистические игры

Методы принятия решений в условиях риска обосновываются в рамках теории статистических решений, или статистических игр. Создателем теории статистических игр считается американский математик и статистик венгерского происхождения А. Вальд (Abraham Wald). Он показал, что в теории принятия решений статистические игры являются основным подходом, если решение принимается в условиях риска [15]. В этом случае предполагаются заданными вероятности состояний

n

«природы»: P( 1 ), P( 2 ), ... , P( n ) , P( j ) 1.

j 1

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

n

ai aij P( j ) , j 1

где aij – элементы матрицы выигрышей A {aij }m n .

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

110