Новосибирский государственный технический университет
Кафедра вычислительной техники
Расчётно-графическая работа
по дисциплине «Методы оптимизации и теория принятия решений»
ПРИНЯТИЕ РЕШЕНИЙ В РАЗЛИЧНЫХ УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ. ЭЛЕМЕНТЫ ТЕОРИИ ИГР.
Вариант : 45
Группа : АМ-210
Студент :
Преподаватель :
Новосибирск 2005
Реферат
Расчетно-графическая работа представлена на 19 страницах, содержит 1 рисунок и 12 таблиц. Все графики, приведенные в расчетно-графической работе, выполнены с использованием программы Advanced Grapher версии 2.05. Оформление сделано при помощи пакета Microsoft Word XP. Расчеты для задач выполнены с использованием пакета MS Excel.
Ключевые слова: дискретная задача, метод динамического программирования, матричнкая игра, принцип минимакса, седловая точка, графическое решение, метод свёртки, метод «уступок», игра с «природой», критерий Вальда, критерий Гурвица, критерий Севиджа, критерий Лапласа, критерий максимума среднего выигрыша.
Содержание
1. Исходные данные. 4
2. Метод динамического программирования. 5
3. Элементы теории матричных игр. 7
3.1. Нахождение седловой точки игры.. 7
3.2. Графическое решение игры.. 8
3.3. Решение игры как задачи ЛП.. 9
4. Принципы принятия решений. 11
4.1. Принятие решений при векторном критерии оптимальности. 11
4.1.1. Метод уступок. 11
4.1.2. Метод свёртки. 13
4.2. Принятие решений в условиях неопределённости (игры с природой) 14
4.2.1. Критерий Вальда. 14
4.2.2. Критерий Сэвиджа. 15
4.2.3. Критерий Гурвица. 15
4.2.4. Критерий Лапласа. 16
5. Ответы на вопросы.. 17
6. Выводы.. 18
7. Список литературы.. 19
1. Исходные данные
Исходные данные формируются согласно 45 варианту и правилам выбора заданий. Номер варианта обозначается как “ab”. Данные берутся из таблицы в соответствии с “b”, причём каждый элемент матрицы увеличивается на “a”.
C1 B1 A1
Sk
D1 9 C2 11 B211 A2
13
E1 8 D2 9 C3 10 B3
13
E2 D3 C4
8 10 12
S0
Для решения матричной игры платёжная матрица формируется в соответствии с “b”, причём каждый элемент матрицы увеличивается на “a”.
Бикритериальная задача ЛП формируется следующим образом: Z=(10+a)x1+(10+b)x2→max. Ограничения в задаче в соответствии с номером “b”. Плюс ещё один критерий вида: Z=(10+b)x1-(10+a)x2→min.
 |
Z=15x1-14x2→min
Z=14x1+15x2→max
x1+2x2 ≥ 8
6x1-5x2 ≤ 60
2x1+3x2 ≤ 40
x1, x2 ≥0
Условия решения игр с «природой» даны и сформулирован в соответствующем разделе настоящей РГР.
2. Метод динамического программирования
Пусть нужно попасть из точки S0 в точку Sk. Необходимо найти оптимальную траекторию, чтобы затраты на передвижение были как можно меньше.
Расстояние между узлами по вертикали обозначим n1, а по горизонтали - n2. Следовательно n1 = 3 и n2 = 3. Значит в процессе будет n1+n2 шагов, т. е. шесть.
C1 B1 A1
Sk
D1 9 C2 11 B211 A2
13
E1 8 D2 9 C3 10 B3
13
E2 D3 C4
8 10 12
S0
Начнём поиск оптимальной стратегии с конечной точки Sk. В неё можно попасть двумя путями – из точки A1 или из точки A2.
A1 12 Sk
11 13
11 A2
Так как затраты на передвижение из точки A1 меньше, чем из точки A2, то в кружок возле точки A1 ставим 12 (и 13 соответственно в кружок возле точки A2) и переходим к следующему шагу. Все шаги аналогичны первому, поэтому для пояснений приведём только иллюстрации.
B1 A1 Sk
11 12
9 11 B2 13
8 9 A2
12 11 10
9 9 B3
Приведём конечную матрицу с показанной стрелками оптимальной траекторией.
C1 B1 A1
Sk
D1 9 C2 11 B2 11 A2
13
E1 8 D2 9 C3 10 B3
E2 D3
8C4
S0
.
3. Элементы теории матричных игр
3.1. Нахождение седловой точки игры
Находим верхнюю и нижнюю цену игры.
Таблица №1.
A B | B1 | B2 | B3 | Ai |
A1 | 9 | 8 | 7 | 7 |
A2 | 11 | 12 | 13 | 11 |
A3 | 10 | 13 | 8 | 8 |
bi | 11 | 13 | 13 |
Минимальные значения в строках: {7,11,8}, 
.
Максимальные значения в столбцах: {11,13,13}, 
.
Так как 
, т. е. седловая точка существует, то это значит, что игра может быть решена в чистых стратегиях.
3.2. Графическое решение игры
Для того чтобы графически решить заданную игру, необходимо, сначала, уменьшить размерность задачи, упростив ее хотя бы до вида 2xn, mx2 или 2x2.
Как видно из таблицы №1, стратегия B1 является доминирующей для стратегии B2, это означает, что стратегию B2 можно исключить. После этого получим:
Таблица №2
A B | B1 | B3 |
A1 | 9 | 7 |
A2 | 11 | 13 |
A3 | 10 | 8 |
Данная игра является игрой 3x2. Получаем:
Рис.1 Графическое решение матричной игры
Таким образом, игра имеет седловую точку равную 11, то есть она имеет равновесное решение и игрокам не выгодно отступать от него.
3.3. Решение игры как задачи ЛП
Составим для заданной игры прямую и обратную задачи ЛП:
Таблица №3
Прямая задача (для игрока B) | Двойственная задача (для игрока A) |
|
|
Решим полученную линейную задачу в пакете MS Excel XP:
Таблица №4
|
В результате для игрока А выгодно придерживаться всё время одной стратегии a1.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 |