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

Кафедра вычислительной техники

Расчетно-графическая работа

По дисциплине "Теория принятия решений"

Новосибирск, 2012

Реферат

Отчет ____ с., 1 ч., 2 рис., 13 табл., 2 источника.

МАТРИЧНАЯ ИГРА, СТАТИСТИЧЕСКАЯ ИГРА, ИГРА С ПРИРОДОЙ, ПРИРОДА, СТАТИСТИК, ГРАФИЧЕСКИЙ МЕТОД, СИМПЛЕКС-МЕТОД, СЕДЛОВАЯ ТОЧКА, ЦЕНА ИГРЫ, КРИТЕРИЙ ОПТИМАЛЬНОСТИ.

Объектом исследования являются методы решения матричных и статистических игр.

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

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

В результате получены оптимальные стратегии для рассматриваемых примеров игр.

Содержание

Реферат

Введение

Основная часть

1. Исходные данные

2. Элементы теории матричных игр

2.1 Нахождение седловой точки игры

2.2 Графическое решение матричной игры

2.3 Решение игры симплекс-методом

3. Принятие решений в условиях статистической неопределенности

3.1 Построение задачи

3.2 Критерий Вальда

3.3 Критерий Лапласа

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

3.5 Критерий Гурвица

3.7 Вывод

Список литературы

Введение

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

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

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

Основная часть

1. Исходные данные

Таблица 1 - Исходные данные

Раздел	Исходные данные	Методы решения
Элементы теории матричных игр		Нахождение седловой точки игры. Графическое решение игры. Решение игры симплекс-методом
Принятие решений в условиях статистической неопределенности	Придумать самостоятельно.	Критерий Гурвица. Критерий Вальда. Критерий Сэвиджа. Критерий Лапласа. Критерий максимума среднего выигрыша.

2. Элементы теории матричных игр

2.1 Нахождение седловой точки игры

Таблица 2 - Исходная платежная матрица игры

А\В	B1	B2	B3
A1	5	9	4
A2	8	3	7
A3	7	7	6

Здесь А1, А2, А3 - стратегии игрока А; В1, В2, В3 - стратегии игрока В. Элементы матрицы - выигрыш игрока А и проигрыш игрока В (таблица 2).

Следуя максиминному и минимаксному критериям (таблица 3), найдём нижнюю и верхнюю цену игры.

Таблица 3 - Платежная матрица с выбранными максимальными и минимальными элементами

А\В	B1	B2	B3	min
A1	5	9	4	4	8	3	7	3
A3	7	7	6	6
max	8	9	7

Нижняя цена игры:  

Верхняя цена игры:  

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

                                                        6≤≤7

, следовательно, игра не имеет седловой точки в чистых стратегиях

 

2.2 Графическое решение матричной игры

Ищем доминирующие стратегии. Исходная матрица игры:

Таблица 4 - Исходная платежная матрица игры

А\В	B1	B2	B3
A1	7	6	5
A2	9	6	11
A3	8	11	6

Для игрока А нет доминирующих стратегий. Для игрока В стратегия В₁ доминирует В₃, исключаем В₁ (q₁=0) (таблица 4).

Получаем следующую платежную матрицу (таблица 5):

Таблица 5 - Платежная матрица с исключенной стратегией В₁

А\В	B2	B3
A1	6	5
A2	6	11
A3	11	6

Построим графическое решение игры для игрока В (рис.1).

Рисунок 1 - Графическое решение для игрока В.

В точке оптимума M пересекаются cтратегии А₂ и А₃ (см. рис.1). Исключаем стратегию А₁ (q₁=0).

Платежная матрица после исключений (таблица 6):

Таблица 6 - Платежная матрица с исключенной стратегией А₁

	В2	В3
А2	3	7
А3	7	6

Построим графическое решение для игрока А (рис.2).

матричная игра седловая точка

Для точного расчета вероятностей стратегий воспользуемся формулами для решения матричной игры размера 2х2.

Рассчитываем вероятность стратегий для каждого игрока:

) Для игрока А

Вероятность стратегии А₂

Вероятность стратегии А₃

 

 

Рисунок 2 - графическое решение для игрока А.

 

2) Для игрока В

Вероятность для стратегии В₂

Вероятность для стратегии В₂

Цена игры:

Таким образом, найдено графическое решение игры относительно игрока А (рис.1) и относительно игрока В (рис.2). Как видно, по этим решениям оба игрока должны отдать предпочтение стратегиям 2 и 3, причем для обоих игроков вероятности этих стратегий равны 0,2 и 0,8.

.

Ответ:   

2.3 Решение игры симплекс-методом

Исходная платежная матрица

Построим исходную двойственную задачу ЛП, где p_i и q_i - вероятности стратегий для игроков А и В соответственно.

 

 

Производим замену переменных:

Получаем следующую двойственную задачу ЛП

 

 

Решим двойственную задачу ЛП симплекс методом, для этого все коэффициенты в ограничениях и в целевой функции прямой задачи умножим на - 1.

Таблица 7 - Первая итерация симплекс-метода

И1	x1	x2	x3	W
u1	-5	-8	-7	-1	1/8
u2	-9	-3	-7	-1	1/3
u3	-4	-7	-6	-1	1/7
Z	1	1	1	0

Таблица 8 - Вторая итерация симплекс-метода

И2	x1	u1	x3	W
x2	5/8	-1/8	7/8	-1
u2	-57/8	-3/8	-35/8	-5/8	5/3
u3	3/8	-7/8	1/8	-1/8	1/7
Z	3/8	1/8	1/8	-1/8

Таблица 9 - Третья итерация симплекс-метода

И3	x1	u3	x3	W
x2	4/7	-1/7	6/7	1/7	1/6
u2	-51/7	-3/7	-31/7	-4/7	4/31
u1	-3/7	-8/7	-1/7	1/7	-1
Z	3/7	1/7	1/7	-1/7

Таблица 10 - Четвертая итерация симплекс-метода

И4	x1	u3	u2	W
x2	-26/31	-7/31	6/31	1/31
x3	51/31	3/31	-7/31	4/31
u1	-6/31	-35/31	-1/31	5/31
Z	6/31	1/31	-5/31

Так как исходная задача является задачей минимизации, полученное значение целевой функции нужно умножить на - 1. Тогда искомое значение будет равно .

Исходя из произведенной замены, цена игры равна обратному значению ЦФ.

Вектора решений для двойственной задачи.

 

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

Таким образом, результаты решения графическим и симплекс-методами дали совпадающие результаты. Обоим игрокам следует отдать предпочтение своим стратегиям с номерами 2 и 3, причем с вероятностью 0,2 и 0,8 соответственно.

3. Принятие решений в условиях статистической неопределенности

3.1 Построение задачи

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

Статистиком в игре является предприниматель, имеющий 4 стратегии - различные варианты меню.

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

Природа имеет 4 состояния:

.        Преобладают посетители художественной галереи.

2.      Преобладают работники деловых центров.

.        Преобладают посетители праздничных фуршетов и корпоративных вечеринок.

.        Преобладают дети с близлежащих школ.

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

Таблица 11 - Платежная матрица игры

Состояния природы	Состояние (преобладает аудитория)
Стратегии игрока	Посетители галереи	Работники деловых центров	Посетители торжеств	Дети
А1 - Меню 1	23	7	21	16
А2 - Меню 2	15	13	16	22
А3 - Меню 3	28	24	13	22
А4 - Меню 4	24	16	28	18

Необходимо выбрать преимущественную стратегию, которая обеспечит больший выигрыш в условиях неопределенности (статистической неопределенности)

 

3.2 Критерий Вальда

Данный критерий в случае поиска выигрыша является максиминным, то есть ищем  . Следовательно, по критерию Вальда следует выбрать стратегию А4.

 

3.3 Критерий Лапласа

Считая, что наступление всех состояний природы равновероятно, то есть p₁=p₂=. =p_n=1/n, ищем оптимальную стратегию, то есть такую, что . В соответствии с критерием:

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

 

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

Составим матрицу рисков для исходной матрицы:

Таблица 12 - Матрица рисков игры

Состояния природы	Состояние (преобладает аудитория)
Стратегии игрока	Посетители галереи	Работники деловых центров	Посетители торжеств	Дети
А1 - Меню 1	5	17	6
А2 - Меню 2	13	11	12	0
А3 - Меню 3	0	0	15	0
А4 - Меню 4	4	8	0	4

По критерию выбираем  . По данному критерию выбираем стратегию А4.

 

3.5 Критерий Гурвица

Данный критерий позволяет задать степень пессимистичности/оптимистичности при поиске оптимальной стратегии. Эта степень задается коэффициентом α. Так как вероятность успеха кафе достаточно велика (кушать хочется всем), будем больше оптимистами и примем коэффициент α = 0.7. В соответствии с критерием:

 

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

3.6 Критерий максимального среднего выигрыша.

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

Оптимальной считается стратегия, дающая .

Соответственно:

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

3.7 Вывод

Таблица 13 - оптимальные стратегий по критериям

Критерий	Оптимальная стратегия
Вальда	А4
Лапласа	А3
Сэвиджа	А4
Гурвица	А4
Максимума среднего выигрыша	А3

Таким образом, делаем следующие выводы:

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

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

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

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

Список литературы

1.      Венцель Е.С. Исследование операций. Учебное пособие для студентов вузов. - 2-е изд., пер. - М: Высш. шк, 2001 - 208с.: ил.

2.      Зайченко Ю.П. Исследование операций. Учебное пособие для студентов университетов и технических вузов - Киев: Вища школа, 1975. - 320с.: ил.