Расчётно-графическая работа №3 по дисциплине «Методы оптимизации и теория принятия решений»

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

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

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

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

МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

ЭЛЕМЕНТЫ ТЕОРИИ МАТРИЧНЫХ ИГР

ПРИНЦИПЫ ПРИНЯТИЯ РЕШЕНИЙ

Студент: Дата сдачи работы:

6 апреля 2005 г.

Группа АМ-210

Вариант 48

Преподаватель:

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

Содержание

Цель выполнения задания 3

Исходные данные, представленные в виде таблиц 4

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

1.1. Дискретная задача поиска оптимальной траектории 5

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

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

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

2.3. Решение игры путём сведения к задаче линейного программирования 11

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

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

3.1.1 Решение многокритериальной задачи методом уступок 12

3.1.2. Решение многокритериальной задачи методом обобщённого критерия (свёртки, Гермейера) 13

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

3.2.1. Игра с «природой» 14

Цель выполнения задания

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

Получение навыков работы с пакетами программ оптимизации.

Исходные данные, представленные в виде таблиц

Тип задачи	Условие задачи	Метод решения
Дискретная задача о выборе оптимальной траектории		Метод динамического программирования
Матричная игра		Определение существования седловой точки Графическое решение (с предварительным упрощением игры) Решение как задачи ЛП
Многокритериальная задача		Метод уступок Метод свёртки Определение Парето-оптимальных решений (графическая иллюстрация)
Принятие решений в условиях неопределённости

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

1.1. Дискретная задача поиска оптимальной траектории

Самолёт, находящийся в точке S0 и имеющий скорость V0 и высоту H0, должен быть поднят на заданную высоту Hкон, а скорость его доведена до значения Vкон. Известен расход горючего, необходимый для подъёма с любой высоты H1 на высоту H2 при постоянной скорости V, и расход горючего, необходимый для изменения скорости от V1 до V2 (V2 > V1) при неизменной высоте H. Найти оптимальный режим набора высоты и скорости, при котором общий расход горючего будет минимальным.

Предположим, что весь процесс набора высоты и скорости можно разделить на ряд последовательных шагов (этапов) и за каждый шаг самолёт увеличивает только высоту или только скорость. Изобразим состояние самолёта точкой на плоскости VOH, где абсцисса отвечает скорости V, а ордината – высоте H. Процесс перемещения точки S из начального состояния S0 в конечное Sкон изобразится тогда на плоскости VOH некоторой ступенчатой ломаной линией. Эта траектория и будет характеризовать управление набором высоты и скорости.

Из всех траекторий нужно выбрать такую, на которой выбранный критерий – расход горючего Q будет минимальным.

Для решения задачи методом динамического программирования разделим высоту Hкон – H0 на 3 равных части, скорость Vкон – V0 на 3 равных части.

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

Суммарное число шагов процесса по переводу самолёта из S0 в Sкон равно m = 3 + 3 = 6.

С каждым шагом связан определенный расход горючего. Запишем на каждом из отрезков соответствующую величину расхода горючего (в условных единицах). Тогда условия задачи представлены на рис. 1.

Рис. 1.

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

В концевую точку Sкон можно переместиться только из двух соседних (B1 и B2), причин из каждой только одним способом (рис. 2), а поэтому выбора оптимального управления на последнем шаге нет — оно единственное. Если на предпоследнем шаге мы находились в B1, то перемещение в происходит по горизонтали и тратится 11 у. е. т. (условных единиц топлива); если же находились в В2, то движемся по вертикали и тратим 10 единиц. Эти минимальные величины ходов обводим кружками и ставим у точек В1 и В2.

Рис. 2.

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

Переходим к планированию предпоследнего шага. Для этого рассмотрим пункты, из которых можно попасть в В1 и В2 за один шаг. Такими точками являются C1, С2 и С3. Для каждой из них необходимо найти оптимальный путь в Sкон и соответствующий ему расход горючего. В частности, для C1 выбора нет, нужно двигаться по горизонтали и тратить 11 + 10 = 21 у. е. т. Этот оптимальный путь пометим стрелкой. Для точки С2 выбор есть: из нее можно идти в Sкон через В1 или через В2. В первом случае израсходуется 11 + 11 = 22 единиц, во втором – 10 + 10 = 20 единиц. Итак, оптимальный путь из C2 в Sкон лежит через B2.

Для точки С3 путь в Sкон единственный — по вертикали, ему соответствует расход в 10 + 12 == 22 единицы горючего; эту величину обводим кружком при С3, а стрелкой укажем оптимальное движение (рис. 3).

Рис. 3.

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

На рис. 4 приведён окончательный результат. Оптимальная траектория отмечена стрелками оранжевого цвета. Число 58 означает минимальный расход горючего, отвечающий этой траектории.

Рис. 4.

Ответ (в терминах исходной задачи):

Таблица 1. Оптимальное управление процессом.

Шаг	Действие
1	Увеличить скорость до V0+DV
2	Увеличить скорость до V0+2DV
3	Увеличить высоту до H0+DH
4	Увеличить скорость до V0+3DV
5	Увеличить высоту до H0+2DH
6	Увеличить высоту до H0+3DH

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

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

Платёжная матрица:

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

Таблица 1. Платёжная матрица (матрица игры)

	B1	B2	B3	Минимумы строк ()
A1	7	11	6	6
A2	10	5	9	5
A3	9	6	8	6
Максимумы столбцов ()	10	11	9

Нижняя цена игры (максимум из минимумов строк) (максимин) – 6. α= 6.

Верхняя цена игры (минимум из максимумов столбцов) (минимакс) – 9. β= 9.

Нижняя цена не совпадает с верхней. Игра не содержит седловой точки.

Максимину α соответствуют две различные стратегия игрока A: A1 (7–11–6)
и A3 (9–6–8)

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

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

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

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

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

Предварительно упростим игру. Сравнивая почленно столбцы В1 и B3, видим, что все элементы столбца В1 больше соответствующих элементов столбца B3. Значит, стратегия В1 для игрока B – заведомо невыгодная доминирующая стратегия. Вычёркиваем её и приводим матрицу к виду:

.

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

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

Таким образом игра 3 * 2 сведена к игре 2 * 2. Приводи матрицу к виду:

.

Рис. 5

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

P1= 5/15 = 1/3.

P2 = 10/15 = 2/3.

Отрезок NK определяет цену игры. Цена игры V = 7,6824.

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

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

Доля Q1 стратегии A1 в оптимальной смешанной стратегии SA* = (Q1,Q2) равна отношению длины отрезка OA2 к сумме длин отрезков OA1 и OA2 на оси I – I.

.

Оптимальную стратегию SA* можно найти другим способом, если поменять местами игроков A и B, а вместо минимума верхней границы выигрыша рассмотреть максимум нижней границы.

Тогда по рис. 6 определяем значения вероятностей Q1 и Q2 стратегий A1 и A2 в оптимальной смешанной стратегии игрока A.

Q1 = 33.37/75 = 0,445.

Q2= 41.63/75 = 0,555.

Рис. 6

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

X = (0,445; 0,555; 0); Y = (0; 0,333; 0,667); V = 7,6824.

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

Игрок B применяет стратегию B2 с вероятностью 0,333, а стратегию B3 – с вероятностью 0,667. Его проигрыш в среднем составит 7,6824 ед.

2.3. Решение игры путём сведения к задаче линейного программирования

	B1	B2	B3
A1	7	11	6
A2	10	5	9
A3	9	6	8

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

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

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

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

t1*	0,087719
t2*	0,035088
t3*	0
Z*	0,122807

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

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

p1=t1*v’=0,

p2=t2*v’=0,

p3=t3*v’=0.

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

u1*	0,052632
u2*	0
u3*	0,070175
W*	0,122807

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

p1=u1*v’=0,

p2=u2*v’=0,

p3=u3*v’=0,571429.

Ответ:

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

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

Цена игры V = 8,142857.

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

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

3.1.1 Решение многокритериальной задачи методом уступок

Расположим критерии по их значимости (наиболее важный считается первым): критерий t более значим, чем критерий z.

Отыщем оптимальное значение целевой функции t(x):

Оптимальное решение

= 18*0-14*10.67 = –149.38 (при =192.06)

Уступка 10%

Сделаем уступку по первому показателю эффективности на 10%, т. е. ухудшим величину до значения = k1*:

=0,9 * –149.38 = –134,442.

В задаче появляется дополнительное ограничение: –134,442.

Отыщем оптимальное значение целевой функции z(x):

решение 1

= 193,0896 (при = –134,442)

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

Уступка 15%

Сделаем уступку по первому показателю эффективности на 15%, т. е. ухудшим величину до значения = k2*:

=0,85 * –149.38 = –126,973.

В задаче появляется дополнительное ограничение: –126,973.

Отыщем оптимальное значение целевой функции z(x):

решение 2

= 193,6361 (при = –126,973)

Можно заметить, что ценой больших уступок по более значимому критерию t удаётся лишь незначительно улучшить значение по критерию z (улучшение по z на 0,5465 ед. или на 0,28% в результате уступки по t на 7,469 ед. или на 5%).

3.1.2. Решение многокритериальной задачи методом обобщённого критерия (свёртки, Гермейера)

Положительные λ ставятся при тех показателях, которые желательно максимизировать; отрицательные – при тех, которые желательно минимизировать. Абсолютные значения коэффициентов соответствуют степени важности показателей.

Пусть W1 – z, а W2 – t.

Для случая λ1 = +1, λ2 = – 2.

Максимизировать Q = 1 * () – 2 * ().

Полученное решение

= 192 = – 149,333

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

3.2.1. Игра с «природой»

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

Пусть рассматривается эффективность работы различных алгоритмов сортировки (A1, A2, A3, A4) на некоторых заранее неизвестных массивах данных. Массивы данных случайно генерируются программой («природа») с учётом параметров: порядок следования данных, размер массива данных, упорядоченность… Всего выделено четыре состояния, каждое из которых означает определённое сочетание факторов, влияющих на эффективность сортировки.

Условия игры задаются в виде матрицы «выигрышей» игрока A. (примерная интерпретация: меньше выигрыш – больше суммарное время работы алгоритма).

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

	Пj	П1	П2	П3	П4
Ai
A1	1	7	4	0
A2	9	4	8	8
A3	2	4	5	5
A4	1	7	1	1

Максиминный критерий Вальда

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

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

Минимумы строк: 0, 4, 2, 1

Максимум из числа минимумов строк: 4

Выбор стратегии №3

Критерий минимаксного риска Севиджа

Строим матрицу сожалений:

	Пj	П1	П2	П3	П4
Ai
A1	-8	0	-4	-8
A2	0	-3	0	0
A3	-7	-3	-3	-3
A4	-8	0	-7	-7

Минимумы строк: -8, -3, -7, -8

Максимум из числа минимумов строк: -3

Выбор стратегии №2

Критерий пессимизма-оптимизма Гурвица

	Пj	П1	П2	П3	П4	min	max
Ai
A1	1	7	4	0	0	7
A2	9	4	8	8	4	9
A3	2	4	5	5	2	5
A4	1	7	1	1	1	7

	0,1	0,2	0,5	0,8	0,9
1	0,7	1,4	3,5	5,6	6,3
2	4,5	5	6,5	8	8,5
3	2,3	2,6	3,5	4,4	4,7
4	1,6	2,2	4	5,8	6,4

Видим, что соответствует
стратегии №2.

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

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

	Пj	П1	П2	П3	П4
Ai
A1	1	7	4	0	12	3
A2	9	4	8	8	29	7,25 *
A3	2	4	5	5	16	4
A4	1	7	1	1	10	2,5

Выбор стратегии №2

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

Пусть нам известен вектор вероятностей состояний природы. P = (0.1; 0.2; 0.5; 0.2).

	Пj	П1	П2	П3	П4	Мат. ожидание
Ai
A1	1	7	4	0	3,5
A2	9	4	8	8	7,3 *
A3	2	4	5	5	4,5
A4	1	7	1	1	2,2
Вероятность сост. природы	0,1	0,2	0,5	0,2

Выбор стратегии №2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Исследование операций. – М.: Советское радио, 1972.

2. Зайченко, Ю. П. Исследование операций. – Киев: Высшая школа, 1988.

3. Математические основы кибернетики. – М.: Энергоатомиздат, 1987.

4. Кузнецов, Кузубов, Волощенко. Математическое программирование.– М.: Высшая школа, 1980.

Исследование операций и методы оптимизации / составитель – Новосибирск: НГТУ, 1990.

Оптимизация в САПР / составитель – Новосибирск: НГТУ, 1992.

Принятие оптимальных многоцелевых решений [Электронный ресурс]. – Режим доступа: http://www. *****/psu/Faculties/Forest/courses/decision/chap7_a. htm