Матричные игры

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

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Владимирский государственный университет

имени Александра Григорьевича и Николая Григорьевича Столетовых»

Кафедра УИТЭС

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

по дисциплине «Исследование операций и методы оптимизации»

Выполнил: ст. гр. ПИ-111

Кокоулин Н.Ю.

Проверил:

асс. Авдеева Е.С.

Владимир

2013

Содержание

уравнение линейный программирование матричный равновесие

Задача 1. Равновесная ситуация

Задача 2. Игра 2*n

Задача 3. Игра n*2

Задача 4. Решение конечных игр методом итераций

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

Задача 6. Критерий Лапласа

Задача 7. Критерий Гурвица

Задача 8. Критерий ожидаемого значения

Задача 9. Критерий Cэвиджа

Задача 1. Равновесная ситуация

Задание:

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

	В1	В2
А1	3	4
А2	-13	0
А3	0	10
А4	-12	8
А5	11	-3

Решение:

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

min(A1) = 3

Аналогично для других строк находим, что:

min(A2) = -13

min(A3) = 0

min(A4) = -12

min (A5) = -3

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

max(B1) = 11

Аналогично для второго столбца находим, что:

max(B2) = 10

3) Находим верхнюю и нижнюю цену игры. Нижней ценой игры будет являться значение б = maximinjaij. В нашем случае б = 3. Для нахождения верхней цены игры найдем значение в = minimaxjbij = 10

	В1	В2	min(Ai)
А1	3	4	3 > б
А2	-13	0	-13
А3	0	10	0
А4	-12	8	-12
А5	11	-3	-3
max(Bj)	11	10 > в

4) Для поиска седловой точки сравним верхнюю и нижнюю цены игры. Так как нижняя цена игры, равная 3, не равна верхней цены игры, равной 10, можно сделать вывод о том, что седловая точка в данной ситуации отсутствует.

Ответ:

В этой задаче отсутствует ситуация равновесия, т. к. нижняя цена игры б = 3 не равна верхней цене игры в = 10.

Задача 2. Игра 2*n

Задание:

Дана игра 2*n с соответствующей платежной матрицей. Найти оптимальные стратегии игроков А и В и цену игры.

	В1	В2	В3	В4	В5	В6
А1	-7	-1	1	0	-1	-4
А2	-6	3	-8	7	-1	2

Решение:

1. Проанализируем игру на наличие седловой точки.

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

Нижняя цена игры, равная -7, и верхняя цена игры, равная -6, не совпадают. Следовательно, точка равновесия отсутствует, и решение следует искать в смешанных стратегиях.

	В1	В2	В3	В4	В5	В6	min
А1	-7	-1	1	0	-1	-4	-7
А2	-6	3	-8	7	-1	2	-8
max	-6	3	1	7	-1	2

2. Составим систему уравнений, определяющих средний выигрыш игрока А:

3. На плоскости (щ,p) последовательно строим все прямые.

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

Наивысшей точкой нижней огибающей является точка, в которой пересекаются прямые.

Составим и решим систему уравнений:

 <=>

Оптимальная смешанная стратегия игрока А:

5. Подставим полученное значение p0 в одно из уравнений:

Таким образом, цена игры х:

6. Найдем оптимальную смешанную стратегию игрока B.

1) Так как 0<p0=0.2<1, то:

Таким образом, из 6 стратегий игрока B выделяем только стратегии B1 и B3, которым соответствуют прямые (1) и (3), определяющие наивысшую точку нижней огибающей.

2) Составим и решим систему уравнений, определяющих средний проигрыш игрока В:

<=>

3) Оптимальная смешанная стратегия игрока B:

Ответ:

Оптимальная смешанная стратегия игрока А: .

Оптимальная смешанная стратегия игрока B: .

Цена игры: х = -6.2.

Задача 3. Игра n*2

Задание:

Дана игра с соответствующей платежной матрицей. Найти оптимальные стратегии игроков A и B и цену игры.

	В1	В2
А1	8	2
А2	-1	2
А3	7	5
А4	-3	7
А5	8	-3
А6	6	2

Решение:

1. Проверим игру на наличие седловой точки:

	В1	В2	min
А1	8	2	2
А2	-1	2	-1
А3	7	5	5 > б
А4	-3	7	-3
А5	8	-3	-3
А6	6	2	2
max	8	7 > в

Так как нижняя цена игры б = 5 не равна верхней цене игры в = 7, то седловая точка отсутствует. Следовательно, решение игры будем искать в смешанных стратегиях.

2. Запишем систему уравнений, определяющую средний проигрыш игрока B:

3. На плоскости (щ, q) строим прямые

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

5. Решим систему уравнений, состоящую из уравнений (3) и (4):

<=>

Найдем цену игры х.

6. Найдем смешанную стратегию игрока А.

Так как , то:

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

<=>

Оптимальная смешанная стратегия игрока А:

.

Ответ:

Оптимальная смешанная стратегия игрока А: .

Оптимальная смешанная стратегия игрока B: .

Цена игры х = .

Задача 4. Решение конечных игр методом итераций

Задание:

Дана игра с соответствующей платежной матрицей. Необходимо найти цену игры и оптимальные смешанные стратегии. Число итераций n = 7.

	В1	В2	В3
А1	1	2	-1
А2	-4	-2	-1
А3	3	4	-4
А4	5	-5	8

Решение:

1. Проверим игру на наличие седловой точки:

	В1	В2	В3	min
А1	1	2	-1	-1 > б
А2	-4	-2	-1	-4
А3	3	4	-4	-4
А4	5	-5	8	-5
max	5	4 > в	8

Так как нижняя цена игры б = (-1) не равна верхней цене игры в = 4, то седловая точка отсутствует. Следовательно, решение игры будем искать в смешанных стратегиях. Воспользуемся итерационным методом с числом итераций n = 7.

2. Для решения построим таблицу, которая будет заполняться последовательно.

Таблица 1. Выигрыш игрока А

n	i	B1	B2	B3	j	A1	A2	A3	A4	хmin	хmax	х(n)
1	1	1	2	-1	3	-1	-1	-4	8	-1	8	3,5
2	4	6	-3	7	2	1	-3	0	3	-1,5	1,5	0
3	4	11	-8	15	2	3	-5	4	-2	-2,67	1,33	0,67
4	3	14	-4	11	2	5	-7	8	-7	-1	2	0,5
5	3	17	0	7	2	7	-9	12	-12	0	2,4	1,2
6	3	20	4	3	3	6	-10	8	-4	0,5	1,33	0,92
7	3	23	8	-1	3	5	-11	4	4	-0,14	0,71	0,57

Пусть игру начнет игрок А, он выберет максиминную стратегию, то есть стратегию А1. Игрок B выбирает такую стратегию, чтобы выигрыш игрока А был минимален, то есть B3. Игрок А выбирает стратегию так, чтобы его выигрыш при стратегии B3 был максимален, то есть А4.

Минимальный средний выигрыш игрока А: .

Максимальный средний выигрыш игрока А: .

Среднее арифметическое минимального и максимального выигрышей игрока А: .

Накопленный выигрыш игрока А при стратегиях А1 и А4 равен:

(1 2 -1) + (5 -5 8) = (6 -3 7).

Игрок B выбирает стратегию так, чтобы накопленный выигрыш игрока А был минимален, то есть B2. При этом накопленный выигрыш игрока А при стратегии B2 будет равен:

.

Игрок А выбирает стратегию так, чтобы его выигрыш был максимален, то есть А4.

Накопленный выигрыш игрока А на третьем этапе:

(6 -3 7) + (5 -5 8) = (11 -8 15).

Игрок B выбирает стратегию так, чтобы выигрыш игрока А был минимален, то есть B2. При этом накопленный выигрыш игрока А:

.

Игрок А выбирает стратегию так, чтобы его выигрыш был максимален, то есть А3.

Накопленный выигрыш игрока А на четвертом этапе:
(11 -8 15) + (3 4 -4) = (14 -4 11).

Игрок В выбирает стратегию так, чтобы выигрыш игрока А был минимален, то есть B2. При этом накопленный выигрыш игрока А:

.

Игрок А выбирает стратегию так, чтобы его выигрыш был максимален, то есть А3.

Накопленный выигрыш игрока А на пятом этапе:

(14 -4 11) + (3 4 -4) = (17 0 7).

Игрок В выбирает стратегию B2. При этом накопленный выигрыш игрока А:

.

Игрок А выбирает стратегию А3.

Накопленный выигрыш игрока А на шестом этапе:

(17 0 7) + (3 4 -4) = (20 4 3).

Игрок В выбирает стратегию B3. При этом накопленный выигрыш игрока А:

.

Игрок А выбирает стратегию А3.

Накопленный выигрыш игрока А на седьмом этапе:

(20 4 3) + (3 4 -4) = (23 8 -1).

Игрок В выбирает стратегию B3. При этом накопленный выигрыш игрока А:

.

Игрок А выбирает стратегию А1.

После седьмого шага итерации средний выигрыш игрока А х(7) = 0,57, при этом игрок А использовал стратегию А1 2 раза, Аэ 0 раз, А3 4 раз, А4 2 раза. Игрок В использовал стратегию В1 0 раз, В2 4 раза, В3 3 раза.

Получаем, что оптимальная стратегия игрока А: .

Оптимальная стратегия игрока В: .

Ответ:

Оптимальная стратегия игрока А:.

Оптимальная стратегия игрока В:.

Цена игры х = 0,57.

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

Задание:

Дана игра 3x4 с соответствующей платежной матрицей.

Необходимо найти цену игры и оптимальные стратегии каждого игрока.

	В1	В2	В3	В4
А1	7	6	7	5
А2	6	7	9	8
А3	5	8	4	6

Решение:

1. Проверим игру на наличие седловой точки:

	В1	В2	В3	В4	min
А1	7	6	7	5	5
А2	6	7	9	8	6 > б
А3	5	8	4	6	4
max	7 > в	8	9	8

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

2. Для игрока А имеется следующая задача линейного программирования (ЗЛП): нужно найти максимальное значение х при выполнении следующих условий:

При этом обязательно выполнение условия:

 (2)

3. Для игрока В имеется следующая ЗЛП: нужно найти минимальные значения х при условиях:

(3)

(4)

4. Разделим условия (1)-(4) на х и введем следующие обозначения:

Для игрока А:

(5)

(6)

Аналогично для игрока В:

(7)

(8)

5. ЗЛП для игрока А заключается в следующем: найти значения , при которых функция (6) имеет наименьшее значение и выполняется условие (5). ЗЛП для игрока В имеет следующий вид: найти значения , при которых функция (8) имеет наибольшее значение и выполняется условие (7).

6. Для решения ЗЛП воспользуемся встроенной функцией «Решатель» в программе LibreOffice Calc. Для решения ЗЛП для игрока А введем функцию (6) и выражения (5) для условий ограничения поиска решений (рисунок 1).

Рисунок 1

Затем построим программу «Решатель» (рисунок 2):



Рисунок 2

После выполнения программы «Решатель» получим результаты для игрока А, представленные на рисунке 3:

Рисунок 3

Для игрока В настройка программы «Решатель» представлена на рисунках 4 и 5.

Рисунок 4



Рисунок 5

Результаты игрока В показаны на рисунке 6.

Рисунок 6

Таким образом, получим для игрока А:

Для игрока В:

8. Перейдем к исходным обозначениям и получим:

Цена игры .

Для игрока А:

Оптимальная смешанная стратегия игрока А: .

Для игрока В:



Оптимальная смешанная стратегия игрока В: .

Ответ:

Оптимальная смешанная стратегия игрока А: .

Оптимальная смешанная стратегия игрока В: .

Цена игры.

Задача 6. Критерий Лапласа

Задание:

Дана игра 3 x 3 с природой. Необходимо найти оптимальную стратегию игрока А и его потери.

	Q1	Q2	Q3
A1	7	4	3
A2	3	3	5
A3	7	4	1

Решение:

1. Принцип Лапласа предполагает, что вероятности состояний природы равновероятны, поэтому:

.

	Q1	Q2	Q3
A1	7	4	3
A2	3	3	5
A3	7	4	1
P	1/3	1/3	1/3

2. Ожидаемые выигрыши игрока А при различных его стратегиях равны:

	Q1	Q2	Q3	х(A)
A1	7	4	3	4,67
A2	3	3	5	3,67
A3	7	4	1	4
P	1/3	1/3	1/3

3. По критерию Лапласа оптимальной стратегией игрока А является стратегия А2, которая обеспечивает ему наименьшие потери:

.

Ответ:

Оптимальной стратегией игрока А является стратегия А2, при этом потери игрока составляют х = 3,67.

Задача 7. Критерий Гурвица

Задание:

Дана игра 4 x 4 с природой. Необходимо найти оптимальную стратегию игрока А и его доход (б = 0).

	Q1	Q2	Q3	Q4
A1	-4	8	3	0
A2	0	5	1	6
A3	-1	0	5	4
A4	6	1	-1	0

Решение:

1. Найдем максимальные значения по строкам.

	Q1	Q2	Q3	Q4	max aij
A1	-4	8	3	0	8
A2	0	5	1	6	6
A3	-1	0	5	4	5
A4	6	1	-1	0	6

2. Найдем минимальные значения по строкам.

	Q1	Q2	Q3	Q4	max aij	min aij
A1	-4	8	3	0	8	-4
A2	0	5	1	6	6	0
A3	-1	0	5	4	5	-1
A4	6	1	-1	0	6	-1

3. Доход игрока А при стратегии A1: .

При стратегии A2: .

При стратегии A3: .

При стратегии A4: .

	Q1	Q2	Q3	Q4	max aij	min aij	х(Ai)
A1	-4	8	3	0	8	-4	-4
A2	0	5	1	6	6	0	0
A3	-1	0	5	4	5	-1	-1
A4	6	1	-1	0	6	-1	-1

4. Оптимальной стратегией игрока А будет стратегия A2, так как она обеспечивает наибольший доход х = 0.

Ответ: Оптимальной стратегией игрока А является стратегия A2, при этом доход игрока составляет х = 0.

Задача 8. Критерий ожидаемого значения

Задание: Дана игра 3 x 5 с природой. Необходимо найти оптимальную стратегию игрока А и его доход.

	Q1	Q2	Q3	Q4	Q5
A1	7	-3	1	0	6
A2	-1	8	2	-1	-3
A3	5	6	5	5	6

Решение:

1. Так как вероятности состояний природы нам неизвестны, можно воспользоваться прошлым опытом:

	Q1	Q2	Q3	Q4	Q5
A1	7	-3	1	0	6
A2	-1	8	2	-1	-3
A3	5	6	5	5	6
Pj	0,1	0,2	0,3	0,1	0,3

2. Средний доход игрока при i-ой стратегии равен:

	Q1	Q2	Q3	Q4	Q5	х (Ai)
A1	7	-3	1	0	6	2,2
A2	-1	8	2	-1	-3	1,1
A3	5	6	5	5	6	5,5
Pj	0,1	0,2	0,3	0,1	0,3

3. Оптимальной по критерию ожидаемого значения является стратегия A3, так как она дает наибольший доход х = 5,5.

Ответ: оптимальной стратегией игрока является стратегия A3, при этом доход игрока составляет х = 5,5.

Задача 9. Критерий Cэвиджа

Задание:

Дана игра 4 x 3 с природой. Необходимо найти оптимальную стратегию игрока А и его доход.

	Q1	Q2	Q3
A1	2	4	4
A2	5	-3	-2
A3	9	5	3
A4	5	3	-2

Решение:

1. Для построения матрицы «сожалений» определяем максимум по столбцам:

	Q1	Q2	Q3
A1	2	4	4
A2	5	-3	-2
A3	9	5	3
A4	5	3	-2
max aij	9	5	4

2. Строим матрицу «сожалений».

	Q1	Q2	Q3
A1	7	1	0
A2	4	8	6
A3	0	0	1
A4	4	2	6
max aij	9	5	4

3. Определяем максимально возможные «сожаления» игрока А.

	Q1	Q2	Q3	ri
A1	7	1	0	7
A2	4	8	6	8
A3	0	0	1	1
A4	4	2	6	6
max aij	9	5	4

4. Оптимальной является та стратегия игрока А, при которой максимальное значение «сожаления» минимально. Такой стратегией является стратегия А3.

5. Доход игрока А при стратегии А3 равен:

.

Ответ: оптимальной стратегией игрока является стратегия А3, при этом доход игрока А составляет х = 3.

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

...