Игры с « природой».
Для того чтобы можно сделать вывод о том какую именно стратегию выбирать игроку, необходимо использовать критерии Вальда, Гурвица, Сэвиджа, Лапласа, Байеса.
1. Критерий Вальда. Рекомендуется применять максиминную стратегию. Она достигается из условия max min αijи совпадает с нижней ценой игры.
i j
Критерий является пессимистическим, считается, что природа будет действовать наихудшим для человека образом, агрессивно, делать все, чтобы помешать нам достигнуть успеха.
Рассмотрим задачу.
Ежедневный спрос на булочки в продовольственном магазине может принимать следующие значения
Если булочка не продана днем, то она м.б. реализована за 15 центов к концу дня. Свежие булочки продаются по 49 центов за штуку. Затраты магазина на одну булочку 25 центов.
Используя игровой подход, определить, какое число булочек надо заказывать ежедневно.
Составим платежную матрицу. Сначала вычислим прибыль (49-25=24) и убыток (15-25=-10).
| 100*24 | 100*24 | 100*24 | 100*24 | 100*24 | |
| 100*24-50*10 | 150*24 | 150*24 | 150*24 | 150*24 | |
| 100*24-100*10 | 150*24-50*10 | 200*24 | 200*24 | 200*24 | |
| 100*24-150*10 | 150*24-100*10 | 200*24-50*10 | 250*24 | 250*24 | |
| 100*24-200*10 | 150*24-150*10 | 200*24-100*10 | 250*24-50*10 | 300*24 |
Платежная матрица примет вид
Вычислим критерий Вальда - максиминный. Он отражает принцип гарантированного результата:
Олицетворяет позицию крайнего пессимизма: надо ориентироваться всегда на худшие условия, зная наверняка, что хуже этого не будет. Этот перестраховочный подход для того, кто очень боится проиграть.
Оптимальной считается стратегия, при которой гарантируется выигрыш в любом случае, не меньший, чем нижняя цена игры с природой:
Н = max minαij
i j
Подсчитать min по строкам и выбрать ту стратегию, при которой минимум строки максимален.
| А1 | |
| А2 | |
| А3 | |
| А4 | |
| А5 |
Критерий Вальда рекомендует выбирать стратегию А1.
2. Критерий Гурвица (оптимизма - пессимизма).Критерий рекомендует при выборе решения не руководствоваться ни крайним пессимизмом (всегда рассчитывай на худшее), ни крайним легкомысленным оптимизмом (авось кривая выведет). Критерий рекомендует стратегию, определяемую по формуле
H = Max {γmin aij + (1- γ)max aij}
i j j
где γ - степень оптимизма - изменяется в диапазоне [0, 1].
Критерий придерживается некоторой промежуточной позиции, учитывающей возможность как наихудшего, так и наилучшего поведения природы. При γ = 1 критерий превращается в критерий Вальда, при γ = 0 - в критерий максимума. На γ оказывает влияние степень ответственности лица, принимающего решение по выбору стратегии. Чем хуже последствия ошибочных решений, больше желания застраховаться, тем γ ближе к единице.
Рассмотрим платежную матрицу.
Параметр Гурвица возьмем равным 0,6.
| min | max | γmin aij + (1- γ)max aij | |
| А1 | 2400*0.6+0.4*2400=2400 | ||
| А2 | 1900*0.6+3600*0.4=2580 | ||
| А3 | 1400*0.6+4800*0.4=2760 | ||
| А4 | 900*0.6+6000*0.4=2940 | ||
| А5 | 400*0.6+7200*0.4=3120 |
Критерий Гурвица рекомендует стратегию А5.
3. Критерий Сэвиджа.Суть критерия состоит в выборе такой стратегии, чтобы не допустить чрезмерно высоких потерь, к которым она может привести. Находится матрица рисков, элементы которой показывают, какой убыток понесет человек (фирма), если для каждого состояния природы он не выберет наилучшей стратегии.
Элементы матрицы рисков находится по формуле (rij):
rij = maxaij - aij
где maxaij - максимальный элемент в столбце исходной матрицы.
Оптимальная стратегия находится из выражения
H = Min {max(max aij - aij)}
Составим матрицу риска, (max aij - aij).
Выберем максимальный элемент в столбце и вычитаем из него остальные элементы столбца, получим max(max aij - aij).
| Мax | ||||||
| А1 | ||||||
| А2 | ||||||
| А3 | ||||||
| А4 | ||||||
| А5 |
Из максимальных значений последнего столбца выбираем минимальную величину, получим Min {max(max aij - aij)}.
Критерий Сэвиджа рекомендует стратегию А4.
4. Критерий Лапласа.Этот критерий основывается на принципе недостаточного обоснования. Поскольку вероятности состояния не известны, необходимая информация для вывода, что эти вероятности различны, отсутствует. Поэтому можно предположить, что они равны. Выбор стратегии осуществляется по формуле
H = Max {1/n·∑ aij}
где 1/n вероятность реализации одного из состояний р = 1/n.
| А1 | (2400+2400+2400+2400+2400)/5=2400 |
| А2 | (1900+3600+3600+3600+3600)/5=3260 |
| А3 | (1400+3100+4800+4800+4800)/5=3780 |
| А4 | (900+2600+4300+6000+6000)/5=3960 |
| А5 | (400+2100+3800+5500+7200)/5=3800 |
Критерий Лапласа рекомендует нам стратегию А4.
Таким образом, рассмотрев одну платежную матрицу, мы получили, что критерии Лапласа и Сэвиджа рекомендует стратегию А4.То есть необходимый заказ булочек составит 250 единиц ежедневно.
5. Критерий Байеса. Принятие решения в условиях риска.
Если в рассмотренных выше критериях, необходимая информация о вероятностях какого-либо состояния отсутствовала, то критерий Байеса действует в условиях не полной информации, т.е. в условиях риска (имеется информация о вероятностях применения стратегий второй стороной). Эти вероятности называются априорными вероятностями.
Выбор стратегии осуществляется по формуле
H = Max {∑pi aij}
Ежедневный спрос на булочки в продовольственном магазине задается следующим распределением вероятностей
| 0,2 | 0,25 | 0,3 | 0,15 | 0,1 |
Поставив значение aij и pi в формулу, получим:
| А1 | 2400*0,2+2400*0,25+2400*0,3+2400*0,15+2400*0,1=2400 |
| А2 | 1900*0,2+3600*0,25+3600*0,3+3600*0,15+3600*0,1=3260 |
| А3 | 1400*0,2+3100*0,25+4800*0,3+4800*0,15+4800*0,1=3695 |
| А4 | 900*0,2+2600*0,25+4300*0,3+6000*0,15+6000*0,1=3620 |
| А5 | 400*0,2+2100*0,25+3800*0,3+5500*0,15+7200*0,1=3290 |
Критерий Байеса рекомендует стратегию А3
В условиях полной неопределенности теория не дает однозначных принципов выбора того или иного критерия.
Оптимальные стратегии, выбранные по различным критериям, различны.
Таким образом, окончательный вывод зависит от предпочтений человека, который принимает решение.
ПРИМЕР №1
Найти оптимальные стратегии 1-го игрока, исходя из различных критериев, в игре с полной неопределенностью относительно второго игрока, заданной платежной матрицей:
а11 а12 а13 а14 5 10 18 25
а21 а22 а23 а24 8 7 8 23
А = а31 а32 а33 а34 ; А = 21 18 12 21
а41 а42 а43 а44 20 22 19 15
Решение.
1. Максиминный критерий Вальда. max min аij
i j
Вычислим минимальные значения по строкам min аij, а далее из них выберем максимальное.
5 10 18 255
А = 8 7 8 23 7
21 18 12 21 12
20 22 19 1515
Таким образом, получаем Н = max min аij = 15 при применении стратегии А4. i j
Ответ: оптимальной стратегией 1-го игрока А является
стратегия А4.
2. Критерий Гурвица.
Параметр Гурвица возьмем равным γ=0,6: γ= min аij+(1-γ) max аij
5 10 18 255 25 5*0,6+0,4*25=13
А = 8 7 8 23 7 23 7*0,6+0,4*23=13,4
21 18 12 21 12 18 12*0,6+0,4*18=14,4
20 22 19 1515 22 15*0,6+0,4*22=17,8
Получаем H = max[0.6 min аij+(1-0.6) max аij]=17.8
i j
Ответ: оптимальной стратегией первого игрока является
стратегия А4.
3. Критерий Сэвиджа (критерий минимаксного риска).
Необходимо построить матрицу рисков.
Для этого:
1) вычислить максимальные значения по столбцам
5 10 18 25
А = 8 7 8 23
21 18 12 21
20 22 19 15
21 22 19 25
2) вычислить матрицу рисков: rij= max аij- аij
21-5 22-10 19-18 25-25 16 12 1 0
rij= 21-8 22-7 19-8 25-23 = 13 15 11 2
21-21 22-18 19-12 25-21 0 4 7 4
21-20 22-22 19-19 25-15 1 0 0 10
3) вычислить максимальные значения по строкам и из них выберем строку с минимальным значением:
16 12 1 0 16
13 15 11 2 15
rij= 0 4 7 4 7
1 0 0 10 10
Получаем H = min max rij = 7 при применении стратегии А3.
i j
Ответ: оптимальной стратегией первого игрока является стратегия А3.
4. Критерий Лапласа. n
Вычислить средние арифметические по строкам [1/n ∑ аij]
5 10 18 25 0.25 (5+10+18+25)=14.5 j=1
A = 8 7 8 23 0.25 (8+7+8+23)=11.5
21 18 12 21 0.25 (21+18+12+21)=18
20 22 19 15 0.25 (20+22+19+15)=19
Получаем H = max [1/n ∑ аij] =19 при применении стратегии А4.
i j=1
Ответ: оптимальной стратегией первого игрока является стратегия А4.
Выбор стратегии в условиях риска (при наличии вероятностной информации).
В1 В2 В3 В4 n
А1 5 10 18 25 H = max∑Pj аij
А2 8 7 8 23 i j=1
А3 21 18 12 21
А4 20 22 19 15
Вероятности стратегий второго игрока.
| В1 | В2 | В3 | В4 |
| 0.2 | 0.15 | 0.35 | 0.3 |
5*0.2+10*0.15+18*0.35+25*0.3=16.30
8*0.2+7*0.15+8*0.35+23*0.3=12.35
21*0.2+18*0.15+12*0.35+21*0.3=17.40
20*0.2+22*0.15+19*0.35+15*0.3=18.45
Получаем Н = 18,45 при применении стратегии А4.
Ответ: оптимальной стратегией первого игрока является стратегия А4.
ПРИМЕР №2
Предприятие имеет возможность самостоятельно планировать объемы выпуска сезонной продукции А1, А2, А3. Не проданная в течении сезона продукция позже реализуется по сниженной цене. Данные о себестоимости продукции, отпускных ценах и объемах реализации в зависимости от уровня спроса приведены в таблице:
| Вид продукции | Себесто-имость | Цена единицы Продукции | Объем реализации При уровне спроса | |||
| В течение сезона | После уценки | Повы-шенном | среднем | Пони- женном | ||
| А1 | d1 | р1 | q1 | a1 | b1 | c1 |
| А2 | d2 | р2 | q2 | a2 | b2 | c2 |
| А3 | d3 | р3 | q3 | а3 | b3 | c3 |
Требуется:
1) придать описанной ситуации игровую схему, указать допустимые стратегии сторон, составить платежную матрицу
2) дать рекомендации об объемах выпуска продукции по видам, обеспечивающих предприятию наивысшую прибыль.
Указание. Для уменьшения размерности платежной матрицы считать, что одновременно на все три вида продукции уровень спроса одинаков: повышенный, средний или пониженный.
| Вид продукции | Себесто-имость | Цена единицы Продукции | Объем реализации При уровне спроса | |||
| В течение сезона | После уценки | Повы-шенном | среднем | Пони- женном | ||
| А1 | 2,6 | 3,4 | 2,8 | |||
| А2 | 3,7 | 4,2 | 3,2 | |||
| А3 | 1,5 | 2,8 | 1,7 |
Решение.
В игре участвуют 2 игрока: А - производитель, В - потребитель.
Игрок А стремится реализовать свою продукцию так, чтобы получить максимальную прибыль. Стратегиями игрока А являются:
А1 - продавать продукцию при повышенном состоянии спроса
А2 - продавать продукцию при среднем состоянии спроса
А3 - продавать продукцию при пониженном состоянии спроса
Игрок В стремится приобрести продукцию с минимальными затратами. Стратегиями игрока В являются:
В1 - покупать продукцию при повышенном состоянии спроса
В2 - покупать продукцию при среднем состоянии спроса
В3 - покупать продукцию при пониженном состоянии спроса
Интересы игроков А и В - противоположны. Определим цену продукции в течение сезона и после уценки:
| Вид продукции | себестоимость | Цена в течение сезона | Цена после уценки |
| А1 | 2,6 | 3,4-2,6=0,2 | 2,8-2,6=0,2 |
| А2 | 3,7 | 4,2-3,7=0,5 | 3,2-3,7= -5 |
| А3 | 1,5 | 2,8-1,5=1,3 | 1,7-1,5=0,2 |
Рассчитаем элементы платежной матрицы
| Предложение | Спрос | ||
| стратегии | Повышенный спрос 14+38+24 | Средний спрос 8+22+13 | Пониженный спрос 5+9+7 |
| Повышенный спрос 14+38+24 | 14*0,8+38*0,5+ 24*1,3=61,4 | 8*0,8+(14-8) *0,2+ 22*0,5+(38-22)*(-5) +13*1,3+(24-13)*0,2 =29,7 | 5*0,8+(14-5)*0,2+ 9*0,5+(38-9)*(-5)+ 7*1,3+(24-7)=8,3 |
| Средний спрос 8+22+13 | 8*0,8+22*0,5+ 13*1,3=34,3 | 8*0,8+22*0,5+ 13*1,3=34,3 | 5*0,8+(8-5)*0,2+ 9*0,5+(22-9)*(-5)+ 7*1,3+(13-7)*0,2 =12,9 |
| Пониженный спрос 5+9+7 | 5*0,8+9*0,5+7*1,3 =17,6 | 5*0,8+9*0,5+ 7*1,3=17,6 | 5*0,8+9*0,5+ 7*1,3=17,6 |
Платежная матрица примет вид
| Стратегии | В1 | В2 | В3 | αi=min аij j |
| А1 | 61.4 | 29.7 | 8.3 | 8.3 |
| А2 | 34.3 | 34.3 | 12.9 | 12.9 |
| А3 | 17.6 | 17.6 | 17.6 | 17.6 |
| βj=max аij i | 61.4 | 34.3 | 17.6 |
α = max αi = 17.6 β = min βj = 17.6
Так как α = β = ν = 17,6, то найдена седловая точка. Значит оптимальное решение: А3; В3
Производитель (игрок А) получит гарантированную прибыль в размере 17,6 ден.ед., если будет реализовывать свою продукцию при пониженном уровне спроса в объеме 5,9 и 7 ед. соответственно продукции А1, А2 и А3
Контрольные вопросы:
1.Дайте определение конфликтной ситуации.
2.Как называется математическая модель конфликтной ситуации?
3.Как называются заинтересованные стороны в теории игр?
4.Какая игра называется антагонистической? Приведите пример.
5.Дайте определение понятию «стратегия».
6.Что понимается под исходом конфликта?
7.Дайте определение понятию «выигрыш».
8.На какие классы делятся игры в зависимости от числа игроков?
9.В чем состоит цель игрока А при выборе стратегии ?
10. В чем состоит суть максиминного принципа оптимальности и как называется выигрыш, полученный в соответствии в этим принципом?
11.Почему максимин α называют нижней ценой игры?
12.В чем состоит цель игрока В при выборе стратегии?
13.Почему минимакс βназывают верхней ценой игры?
14.Почему справедливо неравенство α < β ?
15.Дайте определение цены игры в чистых стратегиях.
16.Какая игра называется игрой в смешанных стратегиях?
17.Как найти оптимальную смешанную стратегию игрока А и цену игры 2 х n геометрически?
18.Что в теории игр понимается под термином «природа»?
19.Приведите примеры в которых решение принимается в условиях неопределенности, связанной с неосознанным принятием различных факторов.
20.Чем отличается выбор оптимальных стратегий игроков в играх с природой от антагонистических игр?
21.Что понимается под риском игрока в игре с природой, и каким образом формируется матрица рисков,
22.Дайте определение критерия Вальда и как по нему определяется выигрыш?
23. Дайте определение критерия Севиджа и как по нему определяется выигрыш?
24. Дайте определение критерия Лапласа и как по нему определяется выигрыш?
25. Дайте определение критерия Байеса и как по нему определяется выигрыш?
26. Какой принцип выбора оптимальной стратегии лежит в основе критерия пессимизма –оптимизма Гурвица относительно выигрышей?