Методы оптимизации и теория принятия решений

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

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

по дисциплине

“Методы оптимизации и теория принятия решений”

Вариант №46

Работа выполнена

Студентом факультета АВТ

Группы АМ-210

Работа проверена:

Новосибирск

2005

Реферат

Расчетно-графическая работа представлена на 16 страницах, содержит 3 рисунка и 3 таблицы. Графики, приведенные в расчетно-графической работе, выполнены с использованием программы Advanced Grapher версии 2.08 и CorelDraw! 11. Оформление сделано при помощи пакета Microsoft Word XP. Расчеты для задач выполнены с использованием пакета MS Excel XP.

Keywords: дискретная задача, метод динамического программирования, матричнкая игра, принцип минимакса, седловая точка, графическое решение, метод свёртки, метод «уступок», игра с «природой», критерий Вальда, критерий Гурвица, критерий Севиджа, критерий Лапласа, критерий максимума среднего выигрыша.

Содержание

1. Метод динамического программирования.. 5

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

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

2.2. Графическое решение игры.. 7

2.3. Решение игры как задачи ЛП.. 9

3. Принципы принятия решений.. 10

3.1. Принятие решений при векторном критерии оптимальности (многокритериальная задача) 10

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

3.1.2. Метод свёртки. 11

3.2. Принятие решений в условиях неопределённости (игры с природой) 12

3.2.1. Критерий Вальда. 12

3.2.2. Критерий Сэвиджа. 12

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

3.2.4. Критерий Лапласа. 13

4. Ответы на вопросы... 14

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

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

Метод динамического программирования:

 

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

Многокритериальная задача:

1.  Метод динамического программирования

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

Расстояние между узлами по вертикали обозначим n1, а по горизонтали - n2. Следовательно n1 = 3 и n2 = 3. Значит в процессе будет n1+n2 шагов, т. е. шесть.

12

Sk

S0

Рис.1. Исходная задача

Начнём поиск оптимальной стратегии с конечной точки Sk. В неё можно попасть двумя путями – из точки A1 или из точки A2.

A1 11 Sk

Рис.2.Пример поиска оптимальной стратегии

Так как затраты на передвижение из точки A1 меньше, чем из точки A2, то в кружок возле точки A1 ставим 1 (и 13 соответственно в кружок возле точки A2) и переходим к следующему шагу. Все шаги аналогичны первому, поэтому для пояснений приведём только иллюстрации и конечный вариант.

C1

 

31

23

35

41

48

59

54

48

38

13

40

32

21

11

26

E2

E1

C4

D3

D2

D1

C3

B3

A2

C2

12

B2

B1

A1

Итак, выше приведена финальная матрица, зелёными стрелками показан оптимальный маршрут. Приведём ответ в терминах исходной задачи:

1. Увеличить высоту до,

2. Увеличить высоту до ,

3. Увеличить высоту до ,

4. Увеличить скорость до ,

5. Увеличить скорость до ,

6. Увеличить скорость до .

.

Оптимальному управлению процессом соответствует минимальный расход горючего Q, отвечающий этой траектории. Q = 11+10+11+8+8+11=59.

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

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

Игра задана матрицей: .

Применим минимаксный и максиминный критерии для нахождения нижней и верхней цены игры.

Минимальные значения в строках: {7,6,6}, .

Максимальные значения в столбцах: {8,13,14}, .

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

Максимину α соответствует стратегия игрока A: A1 (7–10–12)

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

Минимаксу бета соответствует стратегия игрока B: B1 (7–6–8).

Если игрок B будет придерживаться этой стратегии, то гарантировано, что он проиграет не больше β.

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

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

Для графического решения матричной игры рекомендуется упростить её хотя бы до вида 2xn, mx2 или 2x2. Находя доминирующие и дублирующие стратегии, мы удаляем некоторые строки и столбцы из матрицы игры.

.

Над стратегией доминируют стратегии и , поэтому её можно смело удалить. Больше упростить матрицу нельзя. Теперь можно решить матричную игру графически.

Возьмём участок оси абсцисс длиной единица. Левый конец участка (x = 0) будет изображать стратегию B1, правый конец участка (x = 1) – стратегию B2; все промежуточные точки участка будут изображать смешанные стратегии игрока B, причём вероятность P1 стратегии B1 будет равна расстоянию от точки N до правого конца участка, а вероятность P2 стратегии B2 – до левого конца. Проведём через точки B1 и B2 два перпендикуляра к оси абсцисс: ось I – I и ось II –II. На оси I – I будем откладывать выигрыш при стратегии B1, а на оси II –II – выигрыш при стратегии B2.

На рисунке ниже построены 3 прямые, соответствующие стратегиям игрока A. Жирной линией изображена верхняя граница выигрыша игрока A. В точке пересекаются стратегии A3 и A1 – эти стратегии представляют собой активные стратегии для игрока A.

O

Рис.3.Графическое решение

По рисунку определяем значения вероятностей P1 и P2 стратегий B1 и B2 в оптимальной смешанной стратегии SB* = (P1,P2) игрока B.

P1= 0,2

P2 = 0,8

Цена игры V определяется высотой перпендикуляра, опущенного из точки пересечения прямых на ось B1-B2 = 7,59.

Геометрическая интерпретация даёт возможность наглядно изобразить нижнюю цену игры α и верхнюю β. (α= 7, β= 8).

Можно дать геометрическую интерпретацию оптимальных стратегий противника A.

Доля Q1 стратегии A1 в оптимальной смешанной стратегии SA* = (Q1,Q2,Q3) равна 0,05, доля Q2 стратегии A2 равна 0,75, Доля Q3 стратегии A3 равна 0,2,

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

X = (0,05; 0,75; 0,2); V = 7,59

Игрок A применяет стратегию A1 с вероятностью 0,05, стратегию A2 – с вероятностью 0,75, стратегию A3 – с вероятностью 0,2. При этом его выигрыш в среднем составит 7,6824 ед.

2.3.  Решение игры как задачи ЛП

Матрица не содержит седловой точки, поэтому решение игры представлено в смешанных стратегиях: X = (x1, x2, …, xm)

Для определения оптимальной стратегии игрока A имеем следующую задачу линейного программирования: найти min Z = t1 + t2 + t3 при ограничениях

Двойственная задача для определения оптимальной стратегии игрока B формулируется так: найти max W = u1 + u2 + u3 при ограничениях

Решение задачи для игрока A в Excel даёт:

t1	0
t2	0
t3	0,111111
z	0,111111

Цена игры v’ = 1/Z* = 9.

Вероятности p1, p2, p3, с которыми игрок A должен применять свои стратегии A1, A2, A3:

p1=t1*v’=0,

p2=t2*v’=0,

p3=t3*v’=1.

Решение задачи для игрока B в Excel даёт:

t1	0
t2	0
t3	0,111111
Z	0,111111

Вероятности p1, p2, p3, с которыми игрок B должен применять свои стратегии B1, B2, B3:

p1=u1*v’=0

p2=u2*v’=0

p3=u3*v’=1.

Ответ:

Оптимальная стратегия игрока A: X = (0, 0, 1).

Оптимальная стратегия игрока B: Y = (0, 0, 1).

Цена игры V = 9.

3.  Принципы принятия решений

3.1.  Принятие решений при векторном критерии оптимальности (многокритериальная задача)

3.1.1.  Метод уступок

Таблица 1. Решение исходной задачи

	184	-161	0.35	0
	260.78	133.7	0	1
	126	144	0.61	0.96
	42	48	1	0.68
	96	-84	0.75	0.25

Сначала будет правильным выбрать наиболее важный критерий, допустим это будет t. Найдём оптимум функции t*=-161. Весовой коэффициент k1 выберем как 10% от t* и ухудшим t* на это значение - t**=-161+16.1=-177.1. Также введём дополнительное ограничение: . Решив полученную задачу ЛП, получим:

Таблица 2. Решение новой задачи уступками

Имя	x1	x2			ЦФ
	12,81818	5,090909			260,9091
	14	16
Ограничения
	1	2	23	<=	23
	4	-3	36	<=	36
	-2	-1	-30,7273	<=	-6
	-16	14	-133,818	<=	162,1336

3.1.2.  Метод свёртки

Введём функцию и рассмотрим случай, когда . При этом в данном случае k1 нужно брать больше нуля, а k2 меньше нуля.

1. , примем k1=2, k2=-2.

,

,

при .

Теперь подставив соответствующие в функции и t, получим оптимальные значения функций.

Z(x1,x2)=184, t(x1,x2)=-161.

Таблица 3. Решение методом свёртки

по критерию t
x1	x2		ОГР1	ОГР2	ОГР3
0	11,5	184	23	-34,5	11,5
		-161
		690

3.2.  Принятие решений в условиях неопределённости (игры с природой)

Возможно производство четырёх типов самолётов – A1, A2, A3, A4. Т. е. реактивных, турбинных, моторных и планеров Предположим, что выделено 4 различных состояния, каждое из которых означает определённое сочетание факторов, влияющих на эффективность самолётов. Состояние природы обозначим через P1, P2, P3 и P4. Экономическая эффективность производства отдельных типов самолётов изменяется в зависимости от состояний природы и задана матрицей.

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

Используем формулу .Т. е. находим максимальное число из минимальных. , . Соответственно выбираем ту стратегию, у которой минимум строки максимален – A3.

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

Составим матрицу рисков .

Применим формулу .

, . Число 22 соответствует оптимальной A3 стратегии по Сэвиджу.

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

Возьмём , что означает перевес в сторону пессимистического прогноза. Здесь применяется формула , где - минимум строки, - её максимум.

	N1	N2	N3	N4
A1	12	66	13	09	09	66	31,8
A2	50	27	33	37	27	50	66,2
A3	35	44	47	50	35	50	71
A4	21	05	25	60	05	60	63

Максимальное значение критерия говорит в пользу критерия A3.

Итак, все три критерия говорят в пользу стратегии A3, которая и выбирается в качестве самой подходящей.

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

Если предположить известным распределение вероятностей для различных состояний природы, например считать эти состояния равновероятными (), то для принятия решения следует найти математические ожидания выигрыша:

,

,

,

.

Максимальное значение имеет M3, значит надо выбрать стратегию A3.

Вывод: По критериям Вальда, Сэвиджа, Гурвица и Лапласа выгоднее строить моторные(!) самолёты.

P. S. Значения, выбранные для задачи, носят случайный характер и не имеют никакой связи с действительностью.

4.  Ответы на вопросы

4.1.  Рекуррентное соотношение (функциональное уравнение), в соответствии с которым ведётся поиск.

Для задач, к которым можно применить метод динамического программирования, должно выполняться основное рекуррентное соотношение

– вектор параметров, описывающих состояние процесса

– оптимальное значение целевой функции для k-шагового процесса (функция состояния)

– вектор переменных управления, подлежащих выбору на k-м шаге

– вектор состояния предыдущего (k-1)-го шага при условиях и

4.2.  На каких этапах решения используется дополнительная информация от лица, принимающего решение?

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

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

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

4.3.  Что такое «игра с природой»?

Задача, в которой неопределённость вызвана отсутствием информации об условиях, в которых осуществляется действие. Условия зависят не от действий другого игрока, а от объективной действительности («природы»).

4.4.  Что известно в задаче?

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

4.5.  Что нужно определить в задаче?

Оптимальную стратегию игрока A.

4.6.  Чем определяется выбор критерия в такого рода задачах?

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

Если принимается очень ответственное решение, и даже минимальный риск недопустим, то следует применять критерий Вальда – гарантированного результата. Наоборот, если определённый риск вполне приемлем и руководство (заказчик) намерено вложить в намечаемую операцию столько средств, чтобы потом не было обидно, что вложено слишком мало, то выбирают критерий Сэвиджа.

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

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

1.  , , “Математическое программирование”, М., Высшая школа, 1980 г., 304 с.

2.  , “Исследование операций”, М., Высшая школа, 2001 г., 208 с.

3.  “Оптимизация в САПР”. Методические указания, № 000, Новосибирск, 1992 г., 28 с.