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

Министерство образования и науки РФ

Новосибирский государственный технический университет

Кафедра ВТ

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

по дисциплине «МО и ТПР»

Элементы теории игр и принципы принятия решений

Выполнил: Асанов :

Группа: АМ-610

Факультет: АВТ

Вариант: 7 Дата сдачи:

Новосибирск 2009

Реферат

Данная работа выполнена на 22 страницах, содержит 5 рисунков и 12 таблиц. Целью работы является изучение методов решения задач с матричными играми, статистическими играми и векторных критериев оптимальности. Расчеты для задач выполнены с использованием пакетов ПЭР и MathCAD.

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

Содержание

Раздел 1. Элементы теории матричных игр. 4

1.1 Исходные данные. 4

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

1.3 Графическое решение игры.. 5

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

Раздел 2. Принципы принятия решений. 8

2.1 Принятие решений при векторном критерии оптимальности. 8

2.1.1 Исходные данные. 8

2.1.2 Определение Парето-оптимальных решений. 9

2.1.3 Метод уступок. 10

2.1.4 Метод свертки. 12

2.1.5 Сравнение двух методов. 13

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

2.2.1 Исходные данные. 14

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

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

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

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

2.2.6 Критерий максимума среднего выигрыша. 17

2.2.7 Сравнение методов. 17

Заключение. 18

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

Приложения. 20

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

2.1  Исходные данные

Матричная игра:

- стратегии игрока А;

- стратегии игрока В.

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

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

Таблица 1

	B1	B2	B3	αi
A1	8	7	6	6
A2	7	4	5	4
A3	3	8	5	3
βj	8	8	6

Верхняя цена определяется по принципу максимина для игрока A и равна:

Нижняя цена - по принципу минимакса для игрока B и равна:

Здесь элемент обозначает выигрыш игрока A (проигрыш игрока B) при использовании стратегий Ai игроком A и Bj игроком B.

Так как , то игра имеет седловую точку. Это означает, что существует решение игры в чистых стратегиях. Также это означает, что цена игры имеет фиксированное значение: .

2.3  Графическое решение игры

Графическое решение игры возможно в том случае, если её размерность 2*n или 2*m. В нашем случае игра имеет размерность 3*3, поэтому появляется необходимость свести её к 3*2, исключив доминируемую стратегию игрока A – A3:

Таблица 2

	B1	B2	B3
A1	8	7	6
A2	7	4	5

Решим задачу графически относительно игрока A:

Рис. 1. Графическое решение игры относительно игрока A

Очевидно, что решение игры для игрока A расположено в седловой точке (максимум на нижней ломаной - игрок A заинтересован в максимизации своего выигрыша в худших для него условиях).

Для решения задачи относительно игрока B сведем задачу к размерности 2*2, то есть уберем доминируемую для него стратегию:

Таблица 3

	B2	B3
A1	7	6
A2	4	5

Убедимся, что и решение для игрока B также будет находиться в седловой точке:

Рис. 2. Графическое решение игры относительно игрока B

Игрок B заинтересован в минимизации своего проигрыша в худших для него условиях (минимум на верхнем отрезке)

Таким образом, запишем стратегии игроков (решение задачи в чистых стратегиях):

SA* = (1;0;0), SB* = (0;0;1).

Цена игры, определенная по графикам:

Обоим игрокам выгодно придерживаться только одной определенной стратегии.

Ответ: SA* = (1;0;0), SB* = (0;0;1),

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

Для обоих игроков составим задачи линейного программирования (ЛП), причем для игрока A – прямую задачу, а для игрока B – двойственную ей задачу.

В качестве неизвестных введем следующие величины: , где - вероятность использования игроком A стратегии Ai Целевая функция примет вид . Введем систему ограничений:

Получим:

Прямая задача ЛП:

Двойственная задача ЛП:

Решим обе задачи с помощью пакета ПЭР (см. Приложение 1)

Для прямой задачи была найдена оптимальная точка x*=(0.167;0;0)

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

Найдем вероятности:

Для двойственной задачи была найдена оптимальная точка u*=(0; 0; 0.167)

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

Теперь найдем вероятности:

Таким образом, решением будут являться стратегии: SA* = (1;0;0); SB* = (0;0;1)

Ответ: SA* = (1;0;0), SB* = (0;0;1),

Раздел 3.  Принципы принятия решений.

3.1  Принятие решений при векторном критерии оптимальности

3.1.1  Исходные данные

Бикритериальная задача ЛП:

Множество Парето состоит из одной точки. Поэтому, руководствуясь заданием, изменим критерий t. Получим:

3.1.2  Определение Парето-оптимальных решений

Найдем субоптимальные решения по обоим критериям графическим способом:

Рис. 3. Поиск субоптимального решения бикритериальной задачи ЛП

По рис. 3 определим субоптимальные решения по обоим критериям.

По критерию Z - точка A(0; 10.625), Z=180.625

По критерию t – точка B(10.535; 4.04), t=138.695

Отсюда следует, что множество Парето – это отрезок AB.

3.1.3  Метод уступок

Как лицо, принимающее решение (ЛПР), предположим, что критерий является более значимым, чем Z . Для критерия t субоптимальным решением является точка
B(10.535; 4.04), значение критерия в этой точке: t(x*) = t(B) = 138.695.

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

u – уступка по критерию t. Уступка характеризует ту величину более предпочтительного критерия, которой мы готовы пожертвовать в пользу менее значимого. Положим ее равной 10%: u = 0.1t(x*) = 27.739

Запишем новую задачу ЛП:

Решим задачу в пакете ПЭР

Расчеты приведены в Приложении 2.

Получено компромиссное решение по методу уступок в точке xкомпр=(9.3422; 4.7861).

Найдем значения критериев в этой точке: 110.9564 Z(xкомпр)=

Отметим найденное решение на множестве Парето:

Рис. 4. Компромиссное решение бикритериальной задачи методом уступок

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

Ответ: xкомпр=(9.3422; 4.7861) 110.9564 Z(xкомпр)=

3.1.4  Метод свертки

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

Для вычисления значений нормализованных критериев составим таблицу, содержащую значения критериев в разных точках:

Таблица 4

X	t(x)	Z(x)
A(0; 10.625)	-106.255	180.625
B(10.535; 4.04)	138.695	174.03
C(7;0)	119	70
D(2;0)	34	20
E(0;6)	-60	102

Таким образом, , ,

Установим веса критериев (получены от ЛПР): t=; z= и найдем взвешенную сумму:

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

Решим её в пакете ПЭР

Решение приведено в Приложении 3

Найдено компромиссное решение по методу свертки: xкомпр = B=(10.535; 4.04)

Рис. 5. Компромиссное решение бикритериальной задачи методом свертки

Так как исходная задача является линейной и функция свертки тоже линейна, то полученная задача тоже является линейной. А решением линейной задачи всегда являются крайние точки ОДР.

Но так как мы решаем бикритериальную задачу и производим свертку двух критериев, то найденное решение является эффективным, а следовательно оно лежит на множестве Парето. Так как, множество Парето является отрезком (AB), то крайних точек может быть всего две (субоптимальные решения A и B). Поэтому мы и получили решение в крайней точке B множества Парето, которое является субоптимальным решением для критерия t.

Ответ: xкомпр =(10.535; 4.04) t(xкомпр)= 138.695 Z(xкомпр)=174.03

3.1.5  Сравнение двух методов

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

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

3.2.1  Исходные данные

Боевой отряд спецназа отправляется на задание. Командир может укомплектовать отряд одним из 4-х типов войск: пехота, танковые, мотострелковые (бронетранспортеры), воздушный десант.

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

Известна эффективность применения каждого рода войск в этих условиях, выраженная в условных единицах.

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

Таблица 5

	поле	город	лес	горы
пехота	2	7	6	3
танки	8	6	8	8
БТР	3	9	2	1
десант	7	4	7	9

Сформулируем задачу в терминах теории статистических игр:

Имеется четыре состояния «природы» - B1, B2, B3 и B4. У статистика (игрока с «природой») имеется четыре возможных стратегии: A1, A2, A3 и A4. Задана матрица выигрышей:

Таблица 6

	B1	B2	B3	B4
A1	2	7	6	3
A2	8	6	8	8
A3	4	9	2	1
A4	7	4	7	9

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

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

Критерий Вальда (критерий осторожного наблюдателя) предполагает, что «природа» находится в самом невыгодном для статистика состоянии. В этом худшем состоянии выбирают стратегию, дающую гарантированный выигрыш, равный нижней цены игры с «природой»

Таблица 7

	B1	B2	B3	B4
A1	2	7	6	3	2
A2	8	6	8	8	6
A3	4	9	2	1	1
A4	7	4	7	9	4

= 6. По критерию Вальда следует выбрать стратегию A2

Ответ: Командиру следует укомплектовать отряд танковыми войсками.

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

Данный критерий обеспечивает выбор стратегии из условия:

, где - коэффициент пессимизма

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

Таблица 8

	B1	B2	B3	B4
A1	2	7	6	3	2	7	5.5
A2	8	6	8	8	6	8	7.4
A3	4	9	2	1	1	9	6.6
A4	7	4	7	9	4	9	7.5

Отсюда, H = 7.5 и в качестве лучшей по данному критерию выбирается стратегия A4

Ответ: Командиру следует укомплектовать отряд воздушно-десантными силами.

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

Критерий Сэвиджа по другому называют критерием минимальных «сожалений» или минимального риска. Для отыскания лучшей стратегии по данному критерию составим матрицу рисков R. Элемент матрицы rij означает разность между максимальным выигрышем по «природным условиям» и текущим выигрышем по выбранной стратегии.

Таблица 9

	B1	B2	B3	B4
A1	2	7	6	3
A2	8	6	8	8
A3	4	9	2	1
A4	7	4	7	9
	8	9	8	9

Таблица 10

	B1	B2	B3	B4
A1	6	2	2	6	6
A2	0	3	0	1	3
A3	4	0	6	8	8
A4	1	5	1	0	5

Матрица рисков R:

Лучшей выбирается стратегия, для которой величина риска в худших условиях минимальна: . Следовательно, A2 по данному критерию является лучшей стратегией.

Ответ: Командиру следует укомплектовать отряд танковыми войсками.

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

Критерий Лапласа состоит в том, что для неизвестных состояний «природы» всё ее состояния принимают равновероятными. Так как события B1,B2,B3,B4 образуют полную группу событий, то вычислим вероятности каждого из них:

p(B1) = p(B2) = p(B3) = p (B4) = 0.25

Таблица 11

	B1	B2	B3	B4
A1	2	7	6	3	4,5
A2	8	6	8	8	7.5
A3	4	9	2	1	4
A4	7	4	7	9	6,75

Лучшая стратегия по критерию Лапласа выбирается согласно условию:

Следовательно, лучшей является стратегия A2

Ответ: Командиру следует укомплектовать отряд танковыми войсками.

3.2.6  Критерий максимума среднего выигрыша

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

p(B1) = 0.15

p(B2) = 0.5

p(B3) = 0.05

p(B4) = 0.3

Таблица 12

	B1	B2	B3	B4
A1	2	7	6	3	5
A2	8	6	8	8	7
A3	4	9	2	1	5,5
A4	7	4	7	9	6,1

Лучшая стратегия по критерию Лапласа выбирается согласно условию:

Следовательно, лучшей является стратегия A2

Ответ: Командиру следует укомплектовать отряд танковыми войсками.

3.2.7  Сравнение методов

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

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

По критерию Гурвица в случае оптимистичности и реалистичных предположений о состоянии природы – командиру следует применить десант.

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

При использовании метода Лапласа, мы делаем предположение о равновероятности состояний природы. В этом случае командиру следует укомплектовывать отряд танковыми войсками.

.

Заключение

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

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

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

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

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

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

Приложения

Приложение 1. Решение матричной игры симплекс-методом

Приложение 2. Решение бикритериальной задачи методом уступок

Приложение 3. Решение бикритериальной задачи методом свертки