Информационные системы менеджмента - Бажин И.И

Глава 4. Стохастические модели управления

251

предполагать, что оба игрока ведут себя разумно с точки зрения своих интере­ сов. Следует помнить, что важнейшее ограничение теории игр - единственность показателя эффективности, определяющего выигрыш. Это может ограничивать применение моделей теории игр, так как во многих реальных экономических за­ дачах имеется более одного показателя эффективности. В то же время исполь­ зование свертки критериев, описанной в главе 3 для многокритериальных задач, помогает эффективно преодолеть эти трудности.

4.6.1. РЕШЕНИЕ ИГР В ЧИСТЫХ СТРАТЕГИЯХ

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

Рассмотрим парную конечную игру. Пусть игрок А располагает личными стратегиями, которые обозначим Ai, А2, . . . , Ат . Пусть у игрока В имеется п личных стратегий, обозначим их Bi, В2, . . . , Вп. В этом случае говорят, что игра имеет размерность m x п. В результате выбора игроками любой пары стратегий

A , H B J (1 = 1,2, . . . , m ; j = 1,2,

n)

однозначно определяется исход игры, то есть выигрыш ац игрока А (положи­ тельный или отрицательный) и проигрыш ( - ац) игрока В. Предположим, что значения ац известны для любой пары стратегий (А|, Bj). Матрица Р = (а^), i = 1, 2 m; j = 1, 2, . . . , п, элементами которой являются выигрыши, соответст­ вующие стратегиям А) и Bj, называется платежной матрицей, или матрицей игры. В общем виде платежная матрица, представленная в форме таблицы,

4 B J	В!	в2	Вп
AI	\
A i	а-и	а-12	a-in
А2	а21	а22	а2 п

выглядит так:

Строки этой таблицы соответствуют стратегиям игрока А, а столбцы - стратегиям игрока В. Составим платежную матрицу для игры, описы­ вающей следующий пример.

			Пример. Бизнесмен (игрок А), пытаясь уйти от
Am	a m i Э т2	З т п	расплаты с кредитором (игрок В), может укрыть­
			ся в одном из двух населенных пунктов (1 или

2). Кредитор (игрок В) разыскивает бизнесмена (игрока А), и если найдет, то по­ лучит от бизнесмена долг в 10 тыс.долл. и неустойку в размере 5 тыс.долл. В противном случае кредитор остается без своих денег. Необходимо построить платежную матрицу игры.

Для составления платежной матрицы следует проанализировать поведение каждого из игроков. Игрок А может укрыться в населенном пункте 1 - обозначим эту стратегию через А1? или в населенном пункте 2 - стратегия А2.

Игрок В может искать бизнесмена в населенном пункте 1 - стратегия В-i, ли­ бо в населенном пункте 2 - стратегия В2. Если игрок А находится в населенном

252	Часть 1. Новые принципы работы

пункте 1, и там его обнаруживает игрок В, то есть осуществляется пара страте­ гий (Ai, B-i), то игрок А платит сумму 15 тыс.долл., то есть ац = - 15. Аналогично получаем а22 = - 15 (А, В2). Очевидно, что стратегия (Ai, B2) и (А2, В^ дают игро­ ку А выигрыш 0 (он не платит кредитору), поэтому а12 = а21 = 0. Таким образом, для описанной игры размера 2x2 получаем платежную матрицу Р в виде

I о - is;

Рассмотрим игру тхп с матрицей Р = (а^), i = 1, 2, . . . , m; j = 1, 2, . . . , п и определим наилучшую среди стратегий Ai, А2 Ат . Выбирая стратегию Ah игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий Bj, для которой выигрыш для игрока А минимален (игрок В стремится "навредить" игроку А).

Обозначим через OCJ наименьший выигрыш игрока А при выборе им страте­ гии А, для всех возможных стратегий игрока В (наименьшее число в i-той строке платежной матрицы), то есть

min ay = a,

j=l,...,n

Среди всех чисел a, (i = 1,2, . . ., m) выберем наибольшее: а = max aj. i=l,...,m

Назовем а нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,

a = max	min ац	(4.20)
i=l,...,m	j=l,...,n

Стратегия, соответствующая максимину, называется максиминной страте­ гией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А, и, вы­ бирая стратегию Bj, он учитывает при этом максимально возможный выигрыш для А. Обозначим через Pj наибольший элемент j-того столбца платежной мат­ рицы

Pj = m a x 3jj i=l,...,m

Среди всех чисел Pj выберем наименьшее р = min Pj и назовем р верхней j=l,-,n

ценой игры или минимаксным выигрышем (минимаксом). Это гарантиро­ ванный проигрыш игрока В. Следовательно,

Р = min	max a,j	(4.21)
j=l,...,n	i=l,...,m

Стратегия, соответствующая минимаксу, называется минимаксной стратегией.

Глава 4. Стохастические модели управления

253

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

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

I О -15J

При выборе стратегии А-, (первая строка матрицы) минимальный выигрыш равен си = min(- 15; 0) = - 15 и соответствует стратегии Bi игрока В. При выборе игроком А стратегии А2 (вторая строка матрицы) минимальный выигрыш равен аг = = min(0; -15) = - 1 5 и достигается при стратегии В2 игрока В.

Гарантируя себе максимальный выигрыш при любой стратегии игрока В, то есть нижнюю цену игры а = max(ai, аг) = шах(-15, -15) = -15 , игрок А может выбирать любую стратегию: Ai или А2, то есть любая его стратегия является максиминной.

Выбирая стратегию Bi (столбец 1), игрок В понимает, что игрок А ответит стратегией А2, чтобы максимизировать свой выигрыш (проигрыш В). Следова­ тельно, максимальный проигрыш игрока В при выборе им стратегии Вч равен Pi = тах(-15, 0) = 0. Аналогично, максимальный проигрыш игрока В (выигрыш А) при выборе им стратегии В2 (столбец 2) равен Рг = тах(0, -15).

Таким образом, при любой стратегии игрока А гарантированный минималь­ ный проигрыш игрока В равен р = min(pi, Рг) = min(0, 0) = 0 - верхней цене иг­ ры. Любая стратегия игрока В является минимаксной.

Дополнив платежную матрицу Р, представленную в табличной форме, стро­

	кой Pj	и столбцом а*, получим следующую таблицу.
	\ B j	Bi	в2	ai	В приведенном примере верхняя и ниж­
					няя цены игры различны.
	Ai	\	0		Если верхняя и нижняя цены игры
	Ai	-15		-15
					совпадают,.то общее значение верхней и
	А2	0	-15	-15	нижней цены игры a = р = v называется
				""^--^a = -15	чистой ценой игры, или ценой игры. Ми­
		0	0		нимаксные стратегии,		соответствующие
	Pi
					цене игры,	являются	оптимальными
					стратегиями,	а их совокупность - опти­

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

254	Часть 1. Новые принципы работы

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

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

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

г0,5	0,6	0,8Л
Р = 0,9	0,7	0,8
^о,7	0,6	о,б;

Все расчеты удобно проводить в таблице, в которой, кроме матрицы Р, вве­ дены столбец а] и строка pj. Анализируя строки матрицы (стратегии игрока А),

		Bi	B2	B3	a j	заполняем столбец а,: ои = 0,5, а2
						= 0,7, аз = 0,6 -		минимальные
	Ai	0,5	0,6	0,8	0,5	числа в строках	1, 2, 3. Аналогич­
						но, р, = 0,9, р2	= 0,7, р3 = 0,8 -
	A2	0,9	0,7	0,8	0,7
						максимальные числа в столбцах 1,
	Аз	0,7	0,6	0,6	0,6	2, 3, соответственно. Нижняя цена
						игры а = max(0,5; 0,7; 0,6) = 0,7
	Pi	0,9	0,7	0,8	a = p = 0,7	(наибольшее число в столбце щ) и
						верхняя цена игры		р = min(0,9;

0,7; 0,8) = 0,7 (наименьшее число в строке PJ). ЭТИ значения равны, т.е. а = р, и достигается это в одной и той же паре стратегий (А2, В2). Следовательно, игра имеет седловую точку (А2, В2), и цена игры v = 0,7.

4.6.2. РЕШЕНИЕ ИГР В СМЕШАННЫХ СТРАТЕГИЯХ

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

Смешанной стратегией игрока SA игрока А называется стратегия, в которой игрок применяет чистые стратегии A-i, А2, . . . , А|, . . . , А т с вероятностями pi, р2 PJ, . . . , pm, причем сумма вероятностей равна 1: 2]р, = 1.

Глава 4. Стохастические модели управления

255

Смешанные стратегии игрока А записываются в виде матрицы

SA = ^Al	Аг	'"	Ai	'"	Аг
1	Р2	•••	Pi	•••	Pn

или в виде строки SA = (p-i, p2, ... , Pi, ... , pm)- Аналогично, смешанные стратегии игрока В обозначаются

	SB =	В!	В2	...	В;	...	В„
		qi	Чг	•••	4i	•••	q„
или SB = (qi, q2	Ц\, ••• ,	qm), где сумма вероятностей появления стратегий

равна 1: Zqi = 1

Чистые стратегии можно считать частным случаем смешанных и задавать строкой из нулей и единиц, в которой 1 соответствует чистой стратегии: Ak =(0, 0,

... , 1, ... , 0). Здесь индекс к показывает, что 1 находится на k-том месте в при­ веденной строке стратегий.

На основании принципа минимакса определяется оптимальное решение (или решение игры): это пара оптимальных стратегий S*A ,S*R , в общем случае

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

а < v < р,

где а и р - нижняя и верхняя цены игры.

Справедлива следующая основная теорема теории игр - теорема Неймана.

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

Пусть S*4= (pi*, р2\ ..... Pm) и Sg= (qi*, q2 \ ... , qm*) - пара оптимальных стратегий. Если для чистой стратегии Ак =(0, 0, ... , 1, ... , 0) игрока А существует такая оптимальная смешанная стратегия S^ , в которой элемент рк > 0, то такая

чистая стратегия называется активной (или существенной). В противном слу­ чае стратегия является неактивной (несущественной). Определения активной и неактивной стратегий для игрока В аналогичны.

Справедлива теорема об активных стратегиях: если один из игроков при­

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

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

256	Часть 1. Новые принципы работы

Рассмотрим игру размера 2x2, которая является простейшим случаем ко­ нечной игры. Если такая игра имеет седловую точку, то оптимальное решение - это пара чистых стратегий, соответствующих этой точке.

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

смешанных стратегий S^ = (р/, р2) и Sg = (q/, q2).

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

выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В. Для игры 2x2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) - слу­ чайная величина, математическое ожидание (среднее значение) которой явля­ ется ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равен v и для 1-й, и для 2-й стратегии противника.

Пусть игра задана платежной матрицей

а 1 1	а 1 2
Р =
V я 21	а 2 2 ^
Средний выигрыш игрока А, если он использует оптимальную смешанную
стратегию S^= (Pi , р2), а игрок В - чистую стратегию Bi		(это соответствует
первому столбцу платежной матрицы Р), равен цене игры v:
ацр*1 + a2ip*2 = v.		(4.22)

Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стра­ тегию В2, то есть a12p*i + а22р 2 = v. Учитывая, что р*ч + р*2 = 1, получаем систе­ му уравнений для определения оптимальной стратегии S*x и цены игры v

*	*
аир 1 + а2 1 р2 = v.
a12p*i + а22р*2 = v.		(4.23)
Р*1 + Р*2 = 1
Решая эту систему, получим оптимальную стратегию

1	;	>	Р 2 -	а„ - а12
		а 22 ~ а 12 ~ а 21		а 1 1 + а 22

(4.24)

Ч2 а 21

'21

Глава 4. Стохастические модели управления

257

Применяя теорему об активных стратегиях при отыскании Sg - оптималь­ ной стратегии игрока В, получаем, что при любой чистой стратегии игрока A (Ai или А2) средний проигрыш игрока В равен цене игры v. Это, как и в предыдущем случае, приводит к аналогичной линейной системе уравнений, решение которой дает оптимальную стратегию Sg (q 1, q 2)

q", =	^	^	,	q*2 =	* ± ^	(4.25)
	a i l + a 22 ~ а 12 ~ a 21				a i l + a 22 ~ а 12 ~ Я21

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

р _ f-15	0 | a = _1 5 i p = o.
V О	-\S)

Поэтому ищем решение в смешанных стратегиях. Для игрока А средний выиг­ рыш равен цене игры v (при ВЛ или В2); для игрока В средний проигрыш равен цене игры v (при A-i или А2). Используя полученные формулы для расчета опти­ мальных стратегий, определим

Р*1 = Р*г = q*i = q*2 = -15/(-15 -15) = 0,5; v = (-15)(-15)/(-15 -15) = - 7,5 (тыс.долл.)

Это означает, что оптимальная стратегия каждого игрока состоит в том, что­ бы чередовать свои чистые стратегии случайным образом, выбирая каждый из населенных пунктов с вероятностью 0,5. При этом средний выигрыш равен - 7,5 тысяч долларов.

Рассмотрим еще одну экономическую задачу, сводящуюся к игровой моде­

ли.

Пример 2. Предприятие выпускает скоропортящуюся продукцию, которую может сразу отправить потребителю (стратегия А-0, отправить на склад для хранения (стратегия А2) или подвергнуть дополнительной обработке (стратегия А3) для длительного хранения.

Потребитель может приобрести продукцию: немедленно (стратегия В-0, в течение небольшого времени (стратегия В2), после длительного периода време­ ни (стратегия В3).

В случае стратегий А2 и Аз предприятие несет дополнительные затраты на хранение и обработку продукции, которые не требуются для А1? однако при стра­ тегии А2 следует учесть возможные убытки из-за порчи продукции, если потре­ битель выберет стратегии В2 или В3.

258	Часть 1. Новые принципы работы

Требуется определить оптимальные пропорции продукции для применения стратегий Ai, A2, А3, руководствуясь минимаксным критерием (гарантированный средний уровень убытка) при матрице затрат, представленной следующей таб­ лицей:

А |	Bi	в2	в3
	\
А,	2	5	8
А2	7	6	10
Аз	12	10	8

Матрица примет вид

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

P = f 7	6 101
U2	Ю 8,

Элементы первого столбца больше соответствующих элементов второго столб­ ца, поэтому его можно отбросить, так как цель игрока В - уменьшить выигрыш игрока А. Игра упростилась

U0 8J

По формулам (4.24) находим

р*2 = (8-10)/(6+8-10-10) = 1/3; р*з = 1 - 1/3 = 2/3; v = 6(1/3) + 10(2/3) = 26/3 = 8,67

Таким образом, оптимальная стратегия производителя продукции в рас­ сматриваемом примере sA = (0; 1/3; 2/3), то есть стратегия А^ не применяется, 1/3 продукции отправляется на склад (стратегия А2), а 2/3 продукции дополни­ тельно обрабатывается (стратегия Аз), при этом цена игры v = 8,67.

4.6.3.ПРИВЕДЕНИЕ МАТРИЧНОЙ ИГРЫ К ЗАДАЧЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Пусть игра т х п задана платежной матрицей Р(ац), i = 1,2, ... , m; j = 1,2,

... , п. Игрок А обладает стратегиями Ai, А2, ... , Ат , игрок В - стратегиями Вч, В2,

Глава 4. Стохастические модели управления

259

... , Вп. Необходимо определить оптимальные стратегии S*A = (pi , р2 , ... , pm ) и

Sg = (q/, q 2 , ... , qm ), где pj, q, - вероятности применения соответствующих чистых стратегий A,, Bj, а суммы соответствующих вероятностей равны 1, т.е.

Pi* + Рг* +...+ Pm* = 1, qi* + Яг* +...+ qm* = 1

Как мы уже знаем, оптимальная стратегия S*v обеспечивает игроку А сред­ ний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и вы­ игрыш, равный цене игры v, при оптимальной стратегии игрока В. Без потери общности можно принять v > 0 (этого можно добиться, сделав все элементы ац > 0). Если игрок А применяет смешанную оптимальную стратегию S^ против любой чистой стратегии Bj игрока В, то он получает средний выигрыш, или ма­ тематическое ожидание выигрыша at = a^p-t + a2jp2 + ... + amj-pm, j = 1, 2, ... , n (т.е. элементы j-ro столбца платежной матрицы почленно умножаются на соот­ ветствующие вероятности стратегий А-ь А2, ... , Ат , и результаты складываются).

Для оптимальной стратегии S^ все средние выигрыши не меньше цены иг­ ры v, поэтому получаем систему неравенств в виде (сравните с системой урав­ нений для игры 2x2)

ацрт + агфг + ... + am ipm >	v,
ai2pi + а22р2 + ••• + am2pm >	v,	(4.26)
amPi + a2np2 + ... + amnpm >	v

Каждое из неравенств системы разделим на v > 0 и введем новые перемен­

ные Xi = p-i/v, x2 = p2/v	xm = pm/v. При этом система неравенств примет вид
	a-iiXi + a2ix2	+ ... + amiXm	>	1,
	a12xi + a22x2	+ ... + am2xm	>	1,	(4.27)

ainiXi + a2nx2 + ... + amnxm > 1,

Цель игрока А - максимизировать свой гарантированный выигрыш, то есть цену игры v. Разделив на v Ф 0 равенство pi + р2 + ... + р т = 1, получаем, что переменные xs (i = 1, 2, ... , m) удовлетворяют условию

Xi + Х2 + ... + Xm = 1/v

Максимизация цены игры v эквивалентна минимизации обратной величины 1/v, поэтому задача может быть сформулирована так: определить значения пере-

260 Часть 1. Новые принципы работы

менных Х| > 0 (i = 1, 2, ... , m) так, чтобы они удовлетворяли линейным ограниче­ ниям (4.27), и при этом линейная функция

F = хп + х2 + ... + х т

(4.28)

обращалась в минимум.

ЭТО задача линейного программирования. Решая задачу (4.27) - (4.28), по­ лучаем оптимальное решение р/, р2 , ... , р т и оптимальную стратегию S^ .

Для определения оптимальной стратегии Sg = (q/, q2 qm ) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, то есть найти max(1/v). Это приводит к следующей задаче линейного программу рования:

Определить значения переменных У] > 0 (yj = q/v, j = 1, 2, ... , п), которые удовлетворяют системе неравенств

аиУ1 +а21У2 + ... + а1пуп < 1,
a2iyi + а22у2 + ... + а2пуп < 1,		(4.29)
amiyi + am2y2 + ...	+ amnyn < 1
и максимизируют линейную функцию
Fi = У1 + у2	+ ... + уп	(4.30)
Решение задачи линейного программирования (4.29) - (4.30)		определяет
оптимальную стратегию S^ = ( q / , q2*	qm )• При этом цена игры
v = 1/maxF! = 1/minF		(4 31)

Заметим, что задачи линейного программирования {4.27) - (4.28) и (4.29) - (4.30) являются взаимно-двойственными (такие задачи описаны в гл.З).

Пример. Предприятие может выпускать три вида продукции (А^ А2 и А3), полу­ чая при этом прибыль, зависящую от спроса, который может быть в одном из четырех состояний (Bi, B2, В3, В4). Дана матрица в виде таблицы, элементы ко­ торой ау характеризуют прибыль, которую получит предприятие при выпуске i-той продукции с j-м состоянием спроса.

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

Задача сводится к игровой модели, в которой игра предприятия А против спроса В задана платежной матрицей в виде представленной ниже таблицы.