Методы решения игр

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГБОУ ВПО «УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ»

Контрольная работа

по дисциплине «Теория игр»

Выполнил:

Зверев Сергей Владимирович

Группа: ФК-11 Пр

Проверила: Петрова С.Н.

2013



Задача 1

а) Решить игру с природой по критерию Гурвица, б=0,4;

б) Решить игру с природой по критерию Лапласа;

в) Решить игру с природой по критерию Сэвиджа;

г) Решить игру с природой по критерию Вальда.

Решение:

а) Решить игру с природой по критерию Гурвица, б=0,4

1. Для матрицы выигрышей:

К(А1)=0,4•9+0,6•(-3)=1,8

К(А2)=0,4•9+0,6•(2)=4,8

К(А3)=0,4•8+0,6•(1)=3,8

К(А4)=0,4•3+0,6•(1)=1,8

Лучшая стратегия А2

2. Для матрицы потерь:

К(А1)=0,4(-3)+9=4,2

К(А2)=0,4•2+0,6•9=6,2

К(А3)=0,4•1+0,6•8=5,2

К(А4)=0,4•1+0,6•3=2,2

Лучшая стратегия А4.

б) Решить игру с природой по критерию Лапласа.



1) Если А - матрица выигрышей

2) Если А- матрица потерь

10

16

15

6

1) Если А - матрица выигрышей, то оптимальной является стратегия А2

2) Если А- матрица потерь, то оптимальной является стратегия А4

в) Решить игру с природой по критерию Сэвиджа.

Стратегия R - матрица риска. Элементы находятся по формуле

А-матрица выигрышей

А - матрица потерь



1 -3 2

9 8 9

1. Если А-матрица выигрышей

5

7

8

8

Оптимальной является 1 стратегия

2. Если А-матрица потерь

8

7

5

6

Оптимальной является 3 стратегия

г) Решить игру с природой по критерию Вальда (максиминный, минимаксный)

1)Если А - матрица выигрышей, то выбирается



-3

2

1

1

Оптимальной является стратегии А2.

1)Если А - матрица потерь, то выбирается

9

9

8

3

Оптимальной является стратегия А4

Задача 2

Решить игру методом Брауна, выполнить 20 итераций.

Решение.

Найдем наилучшую стратегию первого игрока: минимальное число в каждой строке обозначаем б₁ = -1, б₂ = 0, б₃ = 3. Выбираем максимальное из этих значении б = б₃ = 3 - нижняя цена игры.

Аналогично для второго игрока. Найдем максимальное значения выигрыша по столбцам в₁ = 6, в₂ = 8, в₃ = 9 и минимальное из этих чисел в = = в₁ = 6 верхняя цена игры. Игра не имеет седловой точки.

б = max (-1,0,3) = 3, в = min(6,8,9) = 6; б?в, 3?v?6.

v = 9/2 = 4.5; p* = (0,1/4, 3/4), q* = (1/2, 0,1/2).

Метод фиктивного розыгрыша Брауна-Робинсона.

Игроки многократно разыгрывают игру и пытаются выявить те стратегии, которые дают им больший накопительный выигрыш. Одно разыгрывание игры - партия. Число партий может быть сколько угодно большим. Данный процесс также называется итерационным, поскольку в каждой партии (итерации) игроки используют один и тот же алгоритм выбора наилучшей стратегии.

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

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

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

Оптимальные стратегии игроков определяются частотами выбора их чистых стратегий. Приближенное значение цены игры - результатом v^N на последней итерации.

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

На первом шаге противники выбирают произвольные чистые стратегии i₁и j₁соответственно. Пусть противниками на первых N шагах последовательно выбирались стратегии (i₁,i_2,i_3, i_4,….i_N) и (j₁, j_2, j₃,…j_N) и x_i^N, y_i^N - количеством шагов, на которых первым и вторым игроками выбирались стратегии i₁и j₁ соответственно. Очевидно,



Задача 3

Решить игру симплекс-методом

2 2 3 1

-1 8 6 3

5 7 4 6

3 2 4 0

Решение

Найдем наилучшую стратегию первого игрока: минимальное число в каждой строке обозначим б₁. Получаем: б₁ =1, б₂ =-1, б₃ = 4, б₄ =0. Выбираем максимальное из этих значений б = б₃ = 4 - нижняя цена игры.

Аналогично для второго игрока. Найдем максимальное значение выигрыша по столбцам: в₁ =5, в₂ =8, в₃ =6, в₄ =6 и минимальное из этих чисел в = в₁ =5 - верхняя цена игры.

б = max(1, -1, 4, 0) = 4, в = min(5, 8, 6, 6) = 5 б?в, 4?v?5

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

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

Добавлено 4 дополнительные переменные: s₅ ? 0, s₆ ? 0, s₇?0, s₈? 0.

Шаг 0, выбран ключевой элемент (3,1)
Базис	БП	s1	s2	s3	s4	s5	s6	s7	s8
s5	1	2	2	3	1	1	0	0	0
s6	1	-1	8	6	3	0	1	0	0
s7	1	5	7	4	6	0	0	1	0
s8	1	3	2	4	0	0	0	0	1
ИС	0	1	-1	-1	-1	0	0	0	0

Шаг 1, выбран ключевой элемент (2,3)
Базис	БП	s1	s2	s3	s4	s5	s6	s7	s8
s5	3/5	0	-4/5	7/5	-7/5	1	0	-2/5	0
s6	6/5	0	47/5	34/5	21/5	0	1	1/5	0
s7	1/5	1	7/5	4/5	6/5	0	0	1/5	0
s8	2/5	0	-11/5	8/5	-18/5	0	0	-3/5	1
ИС	1/5	0	2/5	-1/5	1/5	0	0	1/5	0

Шаг 2
Базис	БП	s1	s2	s3	s4	s5	s6	s7	s8
s5	6/17	0	-93/34	0	-77/34	1	-7/34	-15/34	0
s6	3/17	0	47/34	1	21/34	0	5/34	1/34	0
s7	1/17	1	5/17	0	12/17	0	-2/17	3/17	0
s8	2/17	0	-75/17	0	-78/17	0	-4/17	-11/17	1
ИС	4/17	0	23/34	0	11/34	0	1/34	7/34	0

Получен оптимальный план S_опт = (1/17, 0,3/17, 0), Z_max = 4/17.

Для определения оптимальной стратегии игрока А имеет двойственную задачу линейного программирования:

Найдем решение задачи L(T), не прибегая к симплекс-методу, используя соотношения двойственности.



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

Задача 4

игра природа стратегия цена

Решить игру Р графически

Р = 1 -2 > Q = 3 0

4 6 6 8

7 9 9 11

Решение:

В исходной матрице Р присутствуют отрицательные элементы.

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

Решим задачу геометрическим методом, который включает в себя следующие этапы:

1. В декартовой системе координат по оси абсцисс откладывается отрезок, длинна которого равна 1. Левый конец отрезка (точка х=0) соответствует стратегии В₁, правый - стратегии В₂(х=1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (р₁, р₂), где р₁+р₂ =1

2. На левой оси I-I (оси ординат) откладываются выигрыши стратегий В₁. На линии II-II, параллельной оси ординат, из точки 1 откладываются выигрыши стратегий В₂.

Решение игры (3х2) проводим с позиции игрока А, придерживающегося минимаксной стратегии. Стратегия А₃ доминирует над стратегиями А₁ и А₂ (все элементы строки 3 больше или равны значениям 1-ой или 2-й строк), следовательно, исключаем стратегии А₁ и А₂ (1-ю и 2-ю строки матрицы). Чистые стратегии А₁ и А₂ (см.рис.) не выгодны для игрока А, поскольку при любой стратегии игрока В они дают последнему больший выигрыш, чем чистая стратегия А₃. На основании принципа минимакса выделим прямую А₃А₃ и на ней точку А₃ с наименьшей ординатой на оси I-I, то есть при р₁*=1, р₂ * =0 имеем оптимальное решение.

Решение игры проводим с позиции игрока В, придерживающегося максимальной стратегии. Средний выигрыш v₃, соответствующий смешанной стратегии S_B, определяется по формуле математического ожидания v₃ = 9р₁ + 11р₂ и равен ординате точки М₃, которая лежит на отрезке А₃А₃ и имеет абсциссу S_B, (см.рис.). На основании принципа максимина выделим прямую А₃А₃ и на ней точку А₃ с наименьшей ординатой на оси I-I, то есть при р₁*=1, р₂ * =0 имеем оптимальное решение S*_B = (1;0).

Чистая стратегия В₁ является оптимальной для игрока В, а чистая стратегия А₃ - для игрока А. Цена игры для матрицы Q равна v* = 9*1+11*0 = б = в = 9, то есть имеется седловая точка. Поскольку ранее к элементам матрицы было прибавлено число 2, то вычтем это число из цены игры. Цена игры для матрицы Р равна v=v* - 2 = 9 - 2 = 7.

Задача 5

Найти верхнюю и нижнюю цену игр. Проверить игру на наличие седловой точки.

Размещено на Allbest.ru

...