Задача 6. В трех пунктах производства имеется одинаковая продукция в объеме 150, 250, 200 т. Эта продукция должна быть доставлена потребителям в количестве 100, 180, 160, 160 т. Стоимость перевозок единицы продукции от каждого поставщика к каждому потребителю заданы матрицей:

6		12	15	4
		11	5	3
12
	9	17	14	10

Составить оптимальный план перевозок, при котором суммарные затраты на них минимальны.

Тема 4. Динамическое программирование

Динамическое программирование – это математический метод поиска оптимального управления, специально приспособленный к многошаговым процессам. Рассмотрим пример такого процесса.

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

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

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

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

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

37

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

В решении задач методом динамического программирования будут использоваться следующие обозначения:

N – число шагов.

xk =(x1k , x2k ,....,xnk ) – вектор, описывающий состояние системы на k-м шаге. x0 – начальное состояние, т.е. состояние на 1-м шаге.

xN – конечное состояние, т.е. состояние на последнем шаге. Xk – область допустимых состояний на k-ом шаге.

u =(u1k ,u2k ,...,umk ) – вектор УВ на k-ом шаге, обеспечивающий переход сис-

темы из состояния xk-1 в состояние xk.

Uk – область допустимых УВ на k-ом шаге.

Wk – величина выигрыша, полученного в результате реализации k-го шага. S – общий выигрыш за N шагов.

u * =(u1* ,u2* ,...,uN* ) – вектор оптимальной стратегии управления или ОУВ за N

шагов.

Sk+1( xk ) – максимальный выигрыш, получаемый при переходе из любого состояния xk в конечное состояние x0 при оптимальной стратегии управления на-

чиная с (k+1)-го шага.

S1( x0 ) – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния x0 в конечное xN при реализации оптимальной стратегии управления u * . Очевидно, что S = S1( x0 ), если x0 – фиксировано.

Метод динамического программирования опирается на условие отсутствия последействия и условие аддитивности целевой функции.

Условие отсутствия последействия. Состояние xk , в которое перешла сис-

тема за один k-й шаг, зависит от состояния xk −1 и выбранного УВ uk и не зависит

от того, каким образом система пришла в состояние xk −1 , то есть xk = fk (xk−1, uk ). Аналогично, величина выигрыша Wk зависит от состояния xk −1 и выбранно-

го УВ uk , то есть Wk =Wk (xk−1, uk ).

Условие аддитивности целевой функции. Общий выигрыш за N шагов вы-

числяется по формуле:

N

S = ∑Wk ( xk −1 , u k )

k =1

Определение. Оптимальной стратегией управления u * называется совокупность УВ u1* ,u2* ,...,uN* , то есть u * = (u1* ,u2* ,...,uN* ) , в результате реализации которых

система за N шагов переходит из начального состояния x0 в конечное xN и при этом общий выигрыш S принимает наибольшее значение.

38

Условие отсутствия последействия позволяет сформулировать принцип оптимальности Беллмана.

Принцип оптимальности. Каково бы ни было допустимое состояние системы xi−1 X i−1 перед очередным i-м шагом, надо выбрать допустимое УВ ui Ui

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

В качестве примера постановки задачи оптимального управления продолжим рассмотрение задачи управления финансированием группы предприятий. Пусть в начале i-го года группе предприятий Π1 , Π2 ,...,Πm выделяются соответ-

ственно средства: u1i ,u2i ,...,umi .Совокупность этих значений можно считать управлением на i-м шаге, то есть ui =(u1i ,u2i ,...,umi ). Управление u процессом в целом представляет собой совокупность всех шаговых управлений, то есть

u = (u1 , u2 ,...,uN ) .

Управление может быть хорошим или плохим, эффективным или неэффективным. Эффективность управления u оценивается показателем S. Возникает вопрос: как выбрать шаговые управления u1 , u2 ,...,uN , чтобы величина S обрати-

лась в максимум?

Поставленная задача является задачей оптимального управления, а управление, при котором показатель S достигает максимума, называется оптимальным. Оптимальное управление u * многошаговым процессом состоит из сово-

купности оптимальных шаговых управлений: u * = (u1* ,u2* ,...,uN* ) .

Таким образом, перед нами стоит задача: определить оптимальное управление на каждом шаге ui* (i = 1, 2, ... N) и, значит, оптимальное управление всем

процессом u * .

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

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

Пример. Задача о распределении кредита.

Производственное объединение выделяет 3-м входящим в него предприятиям кредит в 80 тыс. руб. для расширения производства. Для каждого предпри-

ятия известны возможные приросты gi (xi ), зависящие от размера выделяемого кредита, при этом g i (0 )= 0, i = 1,3 . Остальная информация дана в таблице дан-

ных № 8 (табл. 2.1.20).

39

Таблица 2.1.20

Таблица данных №8

	Прирост выпуска продукции
Выделяемые
средства	Предпр. №1	Предпр. №2	Предпр. №3
	g1	g 2	g 3
20	10	12	11
40	31	26	36
60	42	36	45
80	62	54	60

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

Решение:

Этап c № = i – это выделение кредита предприятиям i, i+1,…n (n=3). Управленческое воздействие (ui) – величина кредита i-ому предприятию.

Этап III. Кредит только третьему предприятию (табл. 2.1.21). f3(x3) – максимальный прирост при выделении кредита в размере х3.

f3(x3) = max {g 3 (u 3 )}

u3 ≤ x3

Таблица 2.1.21

Расчетная таблица № 1

	x3	0	20	40	60	80	f3(x3)
u3
0		0	-	-	-	-	0
20		0	11	-	-	-	11
40		0	11	36	-	-	36
60		0	11	36	45	-	45
80		0	11	36	45	60	60

Этап II. Кредит в размере х2 выделяется второму и третьему предприятиям.

f2(x2) = max {g 2 (u 2 )+ f 3 (x 2

− u 2 )}

u 2 ≤ x2

u

= 0, f

(x

)=

g

(0 )+ f

(20 )= 0 + 11 = 11

Пусть

х2

= 20

2

2

2

2

3

u 2 = 20 , f 2 (x 2 )

= g 2

(20 )+ f 3 (0 )= 12 + 0 = 12

u

2 = 0, f 2 (x 2 )= g 2 (0 )+ f 3 (40 )= 0 + 36 = 36

Пусть

х2

= 40

= 20 ,

f 2 (x 2 )= g 2

(20 )+ f 3 (20 )= 12 + 11 = 23

u

2

= 40 , f 2 (x 2 )= g 2

(40 )+ f 3 (0 )= 26 + 0 = 26

u 2

40

Аналогично при х2 = 60 и х2 = 80, заполняем расчетную таблицу № 2 (табл. 2.1.22).

			Расчетная таблица № 2				Таблица 2.1.22
	x2	0	20	40	60	80	f3(x3)
u2
0		0+0=0	-	-	-	-	0
20		0+11=11	12+0=12	-	-	-	12
40		0+36=36	12+11=23	26+0=26	-	-	36
60		0+45=45	12+36=48	26+11=37	36+0=36	-	48
80		0+60=60	12+45=57	26+36=62	36+11=47	54+0=54	62

Данные для функции g 2 (u 2 ) берем из таблицы данных, а для f 3 (x 2 − u 2 )

из таблицы № 1.

Этап I. Кредит, в размере х1, выделяется первому, второму и третьему пред-

приятиям.

Расчеты проводим по формуле:

f1

(x1 ) = max {g1 (u1 )+

f 2 (x1 − u1 )}

x1 ≤u1

Пусть х1

=

20

u

1

= 0, f

1

(x

1

)

= g

1

(0 )+

f

2

(20 ) = 0 + 12 = 12

u1 = 20 , f1 (x1 ) = g 1 (20 )+ f 2 (0 ) = 10 + 0 = 10

Пусть х1

u

1 = 0 , f1 (x1 )

= g 1 (0 )+ f 2 (40 ) = 0 + 36 = 36

=

40

= 20 ,

f1 (x1 ) = g 1 (20 )+ f 2 (20 ) = 10 + 12

= 22

u

1

= 40 , f1 (x1 ) = g 1 (40 )+ f1 (0 ) = 31 + 0 = 31

u1

Аналогично при х2 = 60 и х2

= 80 заполняем расчетную таблицу № 3

(табл. 2.1.23).

Расчетная таблица № 3

Таблица 2.1.23

x2

0

20

40

60

80

f3(x3)

u2

0

0+0=0

-

-

-

-

0

20

0+12=12

10+0=10

-

-

-

12

40

0+36=36

10+12=22

31+0=31

-

-

36

60

0+48=48

10+36=46

31+12=43

42+0=42

-

48

80

0+62=62

10+48=58

31+36=67

42+12=54

62+0=62

67

Данные для функции g1 (u1 ) берем из таблицы данных, а для

f 2 (x1 − u1 ) −

из таблицы № 2.

41

Максимальный прирост выпуска продукции в 67 тыс. руб. получен на III этапе как 31+36, т.е. 31 тыс. руб. соответствует выделению 40 тыс. руб. первому предприятию (см. таблицу данных). Из II этапа 36 тыс. руб. получены как 0+36, т.е. прирост 0 тыс. руб. соответствует выделению 0 тыс. руб. второму предприятию. На I этапе прирост 36 тыс. руб. получен при выделении 40 тыс. руб. третьему предприятию.

Таким образом, кредит в размере 80 тыс. руб. целесообразно выделить первому и третьему предприятиям (по 40 тыс. руб.), при этом прирост продукции будет максимальным и составит 67 тыс. руб.

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

Вопросы для самоконтроля

1.Для решения, каких задач предназначен метод динамического программирования?

2.В чем заключена суть метода динамического программирования?

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

4.Опишите математическую модель для задачи о загрузке транспортного средства. Приведите основное рекуррентное соотношение для ее решения.

5.Сформулируйте принцип оптимальности Беллмана.

Задачи

Задача 1. Предприниматель, торгующий сельхозпродуктами, имеет на складе овощи: картофель стоимостью 5 тыс. руб. за тонну, капусту стоимостью 10 тыс. руб. за тонну, морковь стоимостью 2 тыс. руб. за тонну и свеклу стоимостью 4 тыс. руб. за тонну. При продаже с каждой тонны картофеля, капусты, моркови и свеклы он имеет прибыль 350, 500, 100, 250 руб. соответственно. Сколько тонн каждого вида овощей необходимо продать на рынке, чтобы получить максимальную прибыль? Общая стоимость овощей должна быть равна 16 тыс. руб. Решить задачу методом динамического программирования.

Задача 2. В начале планового периода из 5 лет имеется оборудование, возраст которого 2 года (максимальный возраст оборудования равен 5 годам). Для каждого возраста оборудования t известны: стоимости произведенной на оборудовании продукции r(t) и затраты v(t) на эксплуатацию оборудования. Известны также остаточная стоимость оборудования S = 4 руб. и цена нового оборудования P = 13 руб.

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

t	0	1	2	3	4	5
r(t)	26	26	25	24	23	21
v(t)	15	16	16	16	17	19

42

Задача 3. Самолет грузоподъемностью W = 5 т. следует загрузить 3 видами неделимых предметов. Каждый предмет i имеет wi – вес и ci – стоимость. Необходимо разместить в самолете груз максимальной стоимости.

i	wi	ci
1	2	65
2	3	80
3	1	30

Задача 4. На реконструкцию 4 предприятий выделяется кредит 400 тыс. руб. с дискретностью 80 тыс. руб. В зависимости от суммы инвестиций известен прирост выпуска продукции на каждом предприятии. Причем на каждое предприятие можно осуществить одну инвестицию.

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

	х		Прирост выпуска продукции тыс. руб. от данной инвестиции
						Предприятия
			1		2		3	4
80		30		28			27	35
160		57		62			73	67
240		120		122			125	130
320		150		146			152	144
400		180		175			178	180

Задача 5. В трех районах города предприниматель планирует строительство одинаковых минимаркетов. Известны места, в которых их можно построить. Подсчитаны затраты на их строительство и эксплуатацию.

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

	Магазины		Места строительства
		1	2	3	4
	1	5	9	16	21
	2	6	11	17	20
	3	4	8	15	19

Тема 5. Теория игр. Матричные игры, методы их решения. Элементы теории игр. Классификация игр

Под конфликтом понимается любое столкновение несовпадающих интересов. В каждом конфликте выделяются следующие элементы:

•Кто в игре участвует.

•Каковы возможные исходы этого конфликта.

•Кто в этих исходах заинтересован.

•В чем эта заинтересованность состоит. Математической моделью конфликта является игра.

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

43

Участники конфликта называются игроками.

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

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

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

По характеру взаимодействия игры делятся на:

1.Бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;

2.Коалиционные (кооперативные) – могут образовываться в коалиции.

Вкооперативных играх коалиции наперед определены.

По характеру выигрышей игры делятся на: игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) и игры с ненулевой суммой.

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

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

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

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

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

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

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

44

Матричные игры. Методы их решения Решение матричных игр в чистых стратегиях

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

Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счет игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=1,m), 2 – свою j-ю стратегию (j = 1,n ), после чего игрок 1 получает выигрыш аij за счет игрока 2 (если аij< 0, то это значит, что игрок 1 платит второму сумму | аij |). На этом игра заканчивается.

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

a	a	L a	L a
11	12	1 j	1n
LLLLLLLLLLLL
А = ai1	ai2	L aij	L ain ,
LLLLLLLLLLLL
	am2	L amj
am1			L amn

то проведение каждой партии матричной игры с матрицей А сводится к выбору первым игроком i-й строки, а вторым игроком j-го столбца и получению игроком 1 (за счет игрока 2) выигрыша аij.

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

выигрыша в зависимости от применяемых стратегий игрока 2 min аij, (i = 1,m), т.е.

j

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

max min аij = ai j			o	= α	(1)
i	j	o

Определение. Число α, определенное по формуле (1), называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.

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

этому для игрока 2 отыскивается max аij, т.е. определяется max выигрыш игрока

i

1 при условии, что игрок 2 применит свою j-ю чистую стратегию; затем игрок 2

45

отыскивает такую свою j = j1 стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

min max aij = ai		j = β	(2)
j i	1	1

Определение. Число β, определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счет своих стратегий может себе гарантировать игрок 1.

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

Определение. Если в игре с матрицей А α = β, то говорят, что эта игра имеет

седловую точку в чистых стратегиях и чистую цену игры:

υ = α = β

Седловая точка – это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство α = β. В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:

aijo ≤ aio jo ≤ aio j ,

(3))

где i, j – любые чистые стратегии соответственно игроков 1 и 2; (iо,jо) – стратегии, образующие седловую точку.

Таким образом, исходя из (3), седловой элемент aio jo является минимальным

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

ными чистыми стратегиями соответственно игроков 1 и 2.

Пример решения игры с седловой точкой

							min aij
							j
			1	−3	− 2
							−3
			0	5	4		0			max min aij = 2
A =
			2	3	2		2			i j
max a
	ij	=	2	5	4
i			14243
		min max aij = 2
			j	i

Седловой точкой является пара (iо = 3; jо = 1), при которой υ = α = β = 2. Заметим, что хотя выигрыш в ситуации (3; 3) также равен 2 = α = β, она не

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

46

Пример решения игры в минимаксных стратегиях

						min aij
			10	30		j	10
H	=					→			max min a		= 20
										ij
			40	20		→	20		i j
max aij ↓				↓
i			40	30
			123
min max aij =30
	j		i

Из анализа матрицы выигрышей видно, что α < β, т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию i = 2, то игрок 2, выбрав свою минимаксную j = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию i = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию j = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь, игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д.

Решение матричных игр в смешанных стратегиях

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

Определение. Смешанной стратегией игрока называется полный набор ве-

роятностей применения его чистых стратегий.

Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия x – это набор чисел x = (x1, ..., xm) удовлетворяющих соот-

m

ношениям: xi ≥ 0, (i = 1,m), ∑xi = 1.

i =1

Аналогично, для игрока 2, который имеет n чистых стратегий, смешанная

n

стратегия y – это набор чисел y = (y1, ..., yn), yj ≥ 0, (j = 1,n), ∑y j = 1.

j =1

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

47

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

Определение. Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей:

m n

E (A, x, y) = ∑i=1 ∑j =1aij xi y j = x A yT

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

цена игры α = min max Е (А, х, y).

y x

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

должна быть β = max min Е (А, х, y).

x y

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

2 называются такие наборы хо, уо соответственно, которые удовлетворяют равен-

ству min max Е (А, х, y) = max min Е (А, х, y) = Е (А, хо, уо).

y x x y

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

и 2, если они образуют седловую точку: Е (А, х, уо) ≤ Е (А, хо, уо) ≤ Е (А, хо, у). Оптимальные смешанные стратегии и цена игры называются решением

матричной игры.

Основная теорема матричных игр имеет вид:

Теорема (о минимаксе). Для матричной игры с любой матрицей А величины

α = max min Е(А, х, y) и β = min max Е(А, х, y) существуютиравнымежду собой.

x y y x

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

Обозначим через G (Х, Y, А) игру двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию х Х, игрок 2 – y Υ, после чего игрок 1 получает выигрыш А = А (х, y) за счет игрока 2.

Определение. Стратегия х1 игрока 1 доминирует (строго доминирует) над стратегией х2, если А (х1, y) ≥ А (х2, y) (А (х1, y) > А (х2, y)), y Υ.

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

если А (х, y1) ≤ А (х, y2) (А (х, y1) < А (х, y2)), х Х.

При этом стратегии х2 и y2 называются доминируемыми (строго домини-

руемыми).

48

Пример. Пусть G = (Х, Y, А), где Х = {1, 2, 3, 4}; Y = {1, 2, 3, 4}, а функция выигрыша А задана следующим образом:

1ая

1-ая

2ая A =1-ый игрок -ая3-ьяья

4-ая

стратегия	2C		C	2C	3C
		3C	3C 2	C	2C
стратегия
стратегияатегия		2C	2C	C	C		,
		C	C	C	C 2
стратегия
	14444244443

2ой игрок

2-ой игрок

где С > 0.

Решение:

Прежде всего заметим, что по свойству матричных игр достаточно решить игру G1 = (Х, Y, А), где А1 = C1 А. В матричной форме игра G1 определяется матрицей выигрышей:

					1 2		3	4
			1		2	1	2	3
A	1	=	2		3	3 2 1		2
			3		2	2	1	1
					1	1	1
			4					1 2

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

Далее, используя свойства матричных игр, получаем, что всякое решение игры G2 = (Х \ {4}, Y \ {1}, А1) является решением игры G1. В матричной форме игру G2 можно представить матрицей А2:

		2	3	4
1		1	2	3
A2 = 2		3 2	1
				2
		2	1
3				1

Очевидно, что элементы второй строки не меньше полусуммы соответствующих элементов первой и третьей строк. Кроме того, элементы третьего столбца матрицы А2 не меньше соответствующих элементов второго столбца. Получаем, что всякое решение игры G3 = (Х \ {4,2}, Y \ {1,4}, А2) является решением игры G2, а следовательно и игры G1. Игра G3 определяется матрицей А3:

		2	3
A3 =	1	1	2
	3
		2	1

Матрица А3 не имеет седловой точки, т.к. не выполнено равенство:

maxi minj aij = minj maxi aij ,

49

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

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

	ческое ожидание выигрыша игрока 1 будет равным либо	1	1 +	1	2 =	3	, либо
		2		2		2

21 2 + 21 1 = 23 .

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

Таким образом, стратегия Х = ( 21 , 0, 21 , 0) является оптимальной стратегией иг-

рока 1, стратегия Y = (0, 21 , 21 , 0) – оптимальной стратегией игрока 2 в игре G1, а зна-

чениеигрыG1 равно 23 . Всилусвойства4 решениемигрыG будеттройка(Х, Y, 32C ).

Графический метод решения игр 2×n и m×2

Поясним метод на примерах.

Пример 1. Рассмотрим игру, заданную платежной матрицей:

				2
	A		B1	B2	B3
1		1	2	3	11
	A2 7			5	2
								(x1)
																		(x2)
					y
					11			B3
															B′1
																	7
													N		B′2
										М
					3			B2									5
													υ		B′3	2
					2			B1
															A2
					0		A1
																					х
														1-х
											х

Рис. 2.1.6. Графическое решение игры

50

В точках А1 и А2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока 1 при стратегии А1, а на втором – при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет 2 при стратегии В1 игрока 2, 3 при стратегии В2, 11 при стратегии В3. Числам 2, 3, 11 на оси 0х соответствуют точки В1, В2 и В3.

Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии В1 равен 7, при В2 – 5, а при В3 – 2. Эти числа определяют точки В′1, В2′, В3′ на перпендикуляре, восстановленном в точке А2. Соединяя между собой точки В1 и В′1, В2 и В′2, В3 и В′3 получим три прямые, расстояние до которых от оси 0х определяет средний выигрыш при любом сочетании соответствующих стратегий. Например, расстояние от любой точки отрезка В1В′1 до оси 0х определяет средний выигрыш υ1 при любом сочетании стратегий А1 А2 (с частотами х и 1–х) стратегией В1 игрока 2. Это расстояние равно 2х1 + 7(1 − х2) = υ1.

(Вспомните планиметрию и рассмотрите трапецию А1 B1 B′1 A2). Таким образом, ординаты точек, принадлежащих ломанной В1 M Ν В′3 определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке Ν; следовательно этой точке соответствует оптимальная стратегия Х* = (х, 1−х), а ее ордината равна цене игры υ. Координаты точки Ν находим как точку пересечения прямых В2 B′2

и В3 B′3.

Соответствующие два уравнения имеют вид:

	3x + 5(1 − x) =υ		x =		3		, υ =	49	.
		− x) =υ		11				11
	11x + 2(1

Следовательно, Х = ( 113 ; 119 ), при цене игры υ = 4911 . Таким образом, мы можем найти оптимальную стратегию при помощи матрицы:

3	11
5	2

Оптимальные стратегии для игрока 2 можно найти из системы:

	3y + 5(1	− y) =υ	y =		9
		− y) =υ		11
	5y + 2(1

Следовательно, Y = (0; 119 ; 112 ).

(Из рисунка видно, что стратегия B1 не войдет в оптимальную стратегию).

Пример 2. Найти решение игры, заданной матрицей:

		B		2 B	2
	A		1
			6	5
	1		4
1	A2			6
	A		2	7
	3
	A4	1		8

51

x			А4’		8
				А3’		7
	А1
6				А2’
		K				6
	А2		А1’		5

4

ν

А3

2

1

А4	N

B1						y
					B2
		y	1-y

Рис. 2.1.7. Графическое решение игры 4×2

Решение:

Матрица имеет размерность 2×4. Строим прямые, соответствующие стратегиям игрока 1 (рис. 2.1.7). Ломаная А1 K А′4 соответствует верхней границе выигрыша игрока 1, а отрезок Ν Κ – цене игры. Решение игры таково:

Υ = (	3	;	5	);	Х = (	7	; 0; 0;	1	);	υ =	43	.
								8			8
8		8			8

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

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

Итак, пусть дана матричная игра с матрицей А порядка m×n. Тогда оптимальные смешанные стратегии х = (х1, …, хm), y = (y1, …, yn) соответственно игроков 1 и 2 и цена игры υ должны удовлетворять соотношениям:

	m
	∑aij xi ≥υ (j =
					1, n)
	i =1
	m	=1					(1)
	∑xi
i =1
		(i = 1, m)
xi ≥ 0,
							52

		n
		∑aij y j ≤υ	(i = 1, m)
		j =1
		n	(2)
		∑y j =1
	j =1

		≥ 0, (j = 1, n)
	y j

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

	xi	= pi	(i =		) ,
				1,m
	υ

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

	m	m		1
	∑aij pi ≥ 1,	∑pi	=				,
				υ
	i=1	i=1
	n	n		1
	∑aij q j ≤ 1,	∑q j	=				,
					υ
	j =1	j =1

	yi	= qi	( j =			) ,
				1, n
	υ
		pi ≥ 0 ,	(i =					) ,
					1,m
		q j ≥ 0 ,	( j =						) .
							1, n

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

m	m
∑pi → min ,	∑aij pi ≥ 1	(3)
i=1	i=1

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

n	n
∑q j → max ,	∑aij q j ≤ 1	(4)
j =1	j =1

Формулы (3) и (4) выражают двойственные друг другу задачи линейного программирования (ЛП).

Решив эти задачи, получим значения pi (i =1,m) , qj ( j =1, n) и υ. Тогда смешанные стратегии, т.е. xi и yj, получаются по формулам:

	xi =υpi	(i =
			1, m)			(5)
	y j =υq j
		(j = 1, n)

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

	0	1	−1
	0	−1	0
A =
		0
1			−1

Решение:

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

		1	2	0
A1
	=	1	0	1
			1
	2			0

53

Составим теперь пару взаимно двойственных задач:

p1

+p2 +p3

→ min

q1+q2 +q3

→ max

p

+ p +

2 p

≥1,

q

1

+ 2q

2

≤1,

1

2

3

2 p1 +

p3 ≥1,

q1

+ q3 ≤1,

p

≥1,

2q

1

+ q

2

≤1,

3

p

, p

, p

≥ 0

q

1

,q

2

,q

3

≥ 0

1

2

3

Решим вторую из них (табл. 2.1.24).

								Симплекс-таблица № 4							Таблица 2.1.24
		Б.п.		q1	q2		q3	q4	q5	q6	Решение		∑		Отношение
				−1	−1		−1	0	0	0	0		−3
		q4		1	2		0	1	0	0	1		5		—
		q5		1	0		1	0	1	0	1		4		1 1
		q6		2	1		0	0	0	1	1		5		—
		Б.п.		q1	q2		q3	q4	q5	q6	Решение		∑		Отношение
				0	−1		0	0	1	0	1		1
		q4		1	2		0	1	0	0	1		5		1 2
		q3		1	0		1	0	1	0	1		4		—
		q6		2	1		0	0	0	1	1		5		1 1 = 1
		Б.п.		q1	q2		q3	q4	q5	q6	Решение		∑		Отношение
				1 2	0		0	1 2	1	0	3 2		7 2
		q2		1 2	1		0	1 2	0	0	1 2		5 2
		q3		1	0		1	0	1	0	1		4
		q6		3 2	0		0	−1 2	0	1	1 2		5 2
Из оптимальной симплекс-таблицы следует, что оптимальному значе-
нию7		2	соответствует:

(q1, q2, q3) = (0; 21 ; 1),

а из соотношений двойственности следует, что

(p1, p2, p3) = ( 21 ; 1; 0)

Следовательно, цена игры с платежной матрицей А1 равна:

		1				1				2																							1								,
υ1 =			=					=																				=
	p1	+ p2 + p3		1
						+1			3																				q1		+ q2 + q3
					2
а игры с платежной матрицей А:														2										1
			υ = υ −1 =														−1 = −
						1							3										3
При этом оптимальные стратегии игроков имеют вид:
Х = (х1, х2, х3) = (υр1; υр2; υр3) =									2				1			2							2							1			2
															;						1;						0	=				;					; 0
									3				2			3							3							3			3
Y = (y1, y2, y3) = (υq1; υq2; υq3) =									2							2					1		2										1					2
											0;											;					1	=		0;						;
									3							3					2		3										3
																																						3

54

Кооперативные игры

Кооперативной игрой называется игра с ненулевой суммой, в которой игрокам разрешается обсуждать перед игрой свои стратегии и договариваться о совместных действиях, т.е. образовывать коалиции. Обозначим через N множество всех игроков: N ={1, 2, …, n}, а через K – любое его подмножество. Пусть игроки из K договариваются между собой о совместных действиях и, таким образом, образуют одну коалицию. Очевидно, что число таких коалиций, состоящих из r игроков, равно числу сочетаний из n по r, то есть Cnr , а число всевозможных коалиций равно:

n

∑Crn = 2n – 1 r=1

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

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

В случае участия в игре двух лиц, предполагается, что два игрока не могут воздействовать друг на друга, пока не придут к некоторому соглашению. Значит игра определяется как множество А в пространстве переменных х и у, представляющее общие выигрыши. Также заданы два числа Х1,У1, определяющие величины выигрыша, который каждый из игроков может получить, не вступая в коалиции со своим партнером. Обычно предполагают, что множество А – замкнутое, выпуклое и ограниченное сверху. Точка В (Х1,У1) называется точкой угрозы

(рис. 2.1.8).

Переговорное множество

y

Решение Нэша

Y1 В

А

Х1		х

Рис. 2.1.8. Переговорное множество и точка угроза

55

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

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

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

Max (x-x1)(y-y1)

Рассмотрим известную задачу под названием «семейный спор».

Семейная пара – Муж и Жена каждый вечер решают проблему: как им провести вечер. В городе, где они живут, имеется два вида развлечений: Балет и Футбол. Жена предпочитает Балет, Муж – Футбол. Однако супруги так привязаны друг к другу, что посещение любимого развлечения в одиночку доставляет им совсем не такое удовольствие, как присутствие на них вдвоем, т.е. если Жена идет вечером на Балет с Мужем, она получает максимум удовольствия (скажем 4 единицы); Муж недолюбливает Балет, но присутствие на нем с женой скрашивает тягостное времяпрепровождение (Муж получает 1 ед.). Если Жена идет с Мужем на обожаемый им Футбол, Муж получает 4 ед. удовольствия, Жена получает 1 ед. удовольствия. В принципе, Муж может сходить на Футбол, а Жена на Балет в одиночку. Однако отсутствие супруга снижает удовольствие от любимых зрелищ до 2 ед. И наконец, вечер будет проведен совсем без пользы, если Муж отправится на Балет, а Жена − на Футбол, в этом случае они получат по 0 ед.

В итоге, матрица выигрышей описанной игры выглядит следующим образом:

Жена

БалетФутбол

Балет (4,1) (0,0)

Муж Футбол (2,2) (1,4)

Можно показать, что если супруги будут придерживаться различных несогласованных смешанных стратегий, множество возможных выигрышей образует в системе координат h1 , h2 треугольник АВС с вершинами в точках (0,0), (1,4), (4,1)

(рис. 2.1.9).

h2

4		B
			D
3
			N
2
1		T	Е	C
	A	1	2 3 4	h1

Рис. 2.1.9. Решение игры «семейный спор»

56

Линия ВС является множеством Парето-оптимальных решений: вдоль этой линии рост удовольствия, получаемого Женой, возможен только за счет снижения удовольствия Мужа. Точка Т (2,2) является точкой угрозы в этой игре, а «угроза», например, со стороны Жены может быть такой: «Вместо того, чтобы более 2/3 своего свободного времени проводить на Футболе, я буду ходить на Балет (с Мужем или без него − неважно) – ничего не потеряю». Аналогичная «угроза» может прозвучать со стороны Мужа.

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

Решение Нэша представлено точкой N, когда супруги договариваются половину свободного времени проводить вместе на Балете, вторую половину – на Футболе.

Игры с «природой»

Под природой понимается совокупность неопределенных факторов, которые не контролируются управляющим органом, но влияют на качество вырабатываемых решений. Будем считать, что имеется конечное число состояний природы Рj j=1…n. Управляющий орган также имеет конечное число стратегий Ai i=1…m. Информация об игре задается платежной матрицей Вm×n = (bij), которая может быть матрицей выигрышей или проигрышей (она всегда составляется относительно управляющего органа).

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

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

Все состояния природы считаются равновероятными и реализуются с вероятностями 1n . Стратегия Ai оценивается ожидаемым выигрышем или ожидаемым проигрышем:

Mi = 1n	n
	∑bij − математическое ожидание
	j=1

Если В – матрица выигрышей, то выбирается i* стратегия, доставляющая max выигрыш.

Если В – матрица проигрышей, то выбирается i* стратегия, доставляющая min проигрыш.

2. Критерий Вальде

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

αi = min bij j = 1, n

Будет выбрана та стратегия, на которой наименьший гарантированный выигрыш будет наибольшим

i : max αi	= max min bij
i=1,m	i	j

57

Если В – матрица проигрышей (минимаксный критерий):

αi = max bij i =
		1, m
j =1,n
i : min αi	= min max bij
i=1,m	i	j

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

Строится матрица рисков Rm×n = (rij). Если В – матрица выигрышей.

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

βj = max bij

i=1,m

rij = β j − bij (недополученная прибыль)

Если В – матрица проигрышей.

Каждое состояние природы Рj оценивается числом γ j , равным минимальному проигрышу в данном состоянии природы:

γj = min bij

i=1,m

rij = bij − γ j (чрезмерные потери)

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

4. Критерий Гурвица

Пусть В – матрица выигрышей.

Ai оценивается с позиций оптимиста и пессимиста.

Оптимист выбирает max bij , а пессимист −		min b
		j =1,n ij . Гурвиц предложил
j =1,n
стратегию, определяемую по формуле:
max { λ max bij	+ (1 − λ )min bij } ,
j =1,n	j =1,n

где λ – коэффициент оптимизма, изменяется в диапазоне [0,1].

Пример. Возможно строительство четырех типов электростанций: А1 – тепловые, А2 – приплотинные, А3 – бесшлюзовые, А4 – шлюзовые. Имеются четыре состояния природы. Экономическая эффективность различных типов электростанций изменяется в зависимости от состояния природы и задается матрицей В.

5		2	8	4		А
	2	3	4	12		1
						А2
В =	8	5	3	10		А
	1	4	2	8		3
						А
						4

58

Решение:

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

М1	= ¼ (5 + 2	+ 8	+ 4) = 19/4
М2	= ¼ (2 + 3	+ 4	+ 12) = 21/4
М3	= ¼ (8 + 5	+ 3	+ 10) = 26/4
М4	= ¼ (1 + 4	+ 2	+ 8) = 15/4

Max (19/4; 21/4; 26/4; 15/4) = 26/4

По критерию Лапласа выбираем стратегию А3, т.е. строительство бесшлюзовых электростанций.

2. Критерий Вальде Из каждой строчки матрицы выбираем минимальное число:

α i = min bij j = 1, n

α1 = 2 α2 = 2 α3 = 3 α4 = 1

Выбираем из них максимальное − это α 3 = 3 . По критерию Вальде выбира-

ем стратегию А3, т.е. строительство бесшлюзовых электростанций. 3. Критерий Сэвиджа

β1 = 8; β2 = 5; β3 = 8; β4 = 12 .

Строим матрицу рисков:

8 − 5			5 − 2		8 − 8	12	− 4		3		3	0	8
	8	− 2	5	− 3	8 − 4	12	− 12			6	2	4	0
R =	8	− 8	5	− 5	8 − 3	12	− 10		=	0	0	5	2
	8	− 1	5	− 4	8 − 2	12	− 8			7	1	6	4

Из нее выбираем α 1 = 8;α 2 = 6;α 3 = 5;α 4 = 7 . Минимальное число из них α3 = 5 . По критерию Сэвиджа выбираем стратегию А3, т.е. строительство бес-

шлюзовых электростанций. 4. Критерий Гурвица Возьмем λ = 0,5.

Таблица подсчета

Стратегия	Оптимист	Пессимист	Гурвиц
А1	8	2	0,5×8 + 0,5×2 = 5
А2	12	2	0,5×12 + 0,5×2 = 7
А3	10	3	0,5×10 + 0,5×3 = 6,5
А4	8	1	0,5×8 + 0,5×1 = 4,5

Выбираем из последнего столбца максимальное число − это 7. По критерию ГурвицавыбираемстратегиюА2, т.е. строительствоприплотинныхэлектростанций.

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

59

Связь между теорией игр и проблемами микроэкономики

Представим экономику, в которой два субъекта: Игрок 1 и Игрок 2 и два товара (блага): х1 и х2. Любой из игроков имеет свою функцию полезности, заданную на наборе товаров: u1(x1,x2), u2(x1,x2). Предполагается, что эти функции непрерывны и монотонны по любой из переменных и выпуклы. В начале игры имеется а единиц товара х1 и b единиц товара х2. Пусть это начальное количество товара распределено между игроками:

Игрок 1		обладает х1		и х1	количествами товаров.
			1	2
Игрок 2		обладает	х2	и х2	количествами товаров.
			1	2
х1	+ х2	= а , х1 + х2 = b
1	1	2	2

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

Такие игры впервые рассматривал Эджворт. Для наглядного представления экономики с двумя игроками и двумя товарами используется ящик Эджворта.

В ящике Эджворта по горизонтальной оси откладывается количество товара х1, а по вертикали − х2 (рис. 2.1.10). Ящик Эджворта: сплошными линиями обозначены кривые безразличия 1-го игрока, пунктирными – кривые безразличия 2-го игрока).

Х1	Игрок 2
X2
А1	А2
А0
	Х2
Игрок 1	X1
Рис. 2.1.10. Ящик Эджворта

А0 А1 А2 – договорная кривая. Все точки на этой кривой характеризуют такие состояния, когда не может быть увеличена полезность игрока 1 без снижения полезности другого, т.е. все точки, находящиеся на договорной кривой оптимальной по Парето (рис. 2.1.11).

60

	Игрок 2
	Решение
Контрактное	Нэша
множество
Переговорное
множество	Начальное
	распределение
Игрок 1
Рис. 2.1.11. Решение Нэша

Вопросы для самоконтроля

1.Какие экономические задачи решает теория игр?

2.Дайте определения понятий: игра, игрок, стратегия игрока, выигрыш, платежная матрица.

3.Приведите классификацию игр по различным критериям.

4.Чем однозначно определяются матричные игры?

5.В чем заключается принцип максимина и минимакса?

6.Что такое игра с седловой точкой?

7.Дайте определение понятия «смешанная стратегия».

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

9.В чем заключается графический метод решения игр?

10.Что такое доминирование стратегий?

11.Определите понятие «игра с природой».

12.Сформулируйте следующие критерии оптимальности: Лапласа, Вальде, Сэвиджа, Гурвица.

Задачи

Задача 1. Один из участников игры имеет право загадать одно из чисел: 4, 3, 1, 7, а другой участник одно из чисел: 0, 2, 5, 8, 9. Если результат сложения задуманных чисел будет четным, то второй игрок выплачивает первому получившуюся сумму, а если нечетным, то первый – второму. Записать платежную матрицу данной игры. Найти решение матричной игры.

Задача 2. Предприниматель располагает 3 видами товаров: А1, А2, А3, которые он стремится продать на рынке, где возможна продажа аналогичных товаров − В1, В2, В3 соответственно.

61

Предпринимателю неизвестно, какой вид товаров преимущественно конкурент будет продавать на рынке, а конкуренту не известно, какие товары предпринимателя на этом рынке появятся.

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

Предприниматель		Конкурент
	В1	В2		В3
А1	0,5	0,4		0,9
А2	0,2	0,9		0,1
А3	0,8	0,0		1,0

Задача 3. Банк заинтересован в покупке акций некоторого акционерного общества. Стремясь сделать покупку как можно более выгодной, банк снабжает продавца информацией о реальной стоимости акций, которая может быть как правдивой (А1), так и заведомо ложной (А2).

Продавец может как проверить информацию (В1), так и не проверять (В2). Условия задачи можно представить в виде игровой матрицы, содержащей

данные о величине возможной успешности сделки – приросте стоимости по отношению к вложенным средствам.

Банк	Продавец акций
	В1	В2
А1	0,608	1,000
А2	1,000	0,440

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

Задача 4. Найти оптимальную цену игры.

	3	7	1	1	5	8
	4	9	3	6	2	1
	2	3	1	4	7	20

Задача 5. Найти оптимальную цену игры.

	8	6	4	5	1
	5	4	3	2	3
	6	7	6	3	5
	3	3	2	1	2

62