- •1. Введение 4
- •1.1. Основные методологические принципы
- •1.2. Основные определения
- •1.3. Этапы моделирования
- •5. Модели с обратной связью, динамическое проектирование.
- •2. О принципах принятия решений
- •2.1. Принятие решений в условиях неопределенности критерия.
- •Самостоятельная работа №1.
- •2.2. Принятие решения в условиях неопределенности состояния окружающей среды
- •Самостоятельная работа №2
- •3. Задачи выпуклого векторного программирования1.
- •3.1. Некоторые сведения выпуклого анализа
- •3.2. Понятие оптимальности по Слейтеру и Парето
- •3.3. Возможные (допустимые) и подходящие направления.
- •3.4. Задача выпуклого векторного программирования с ограничениями типа неравенства. Поиск подходящих направлений.
- •Самостоятельная работа №3.
- •3.4. Теорема Куна–Таккера для задачи выпуклого векторного программирования
- •Самостоятельная работа № 4.
- •4. Некоторые задачи теория игр
- •4.1. Анализ матричных антагонистических игр двух игроков .
- •Самостоятельная работа № 5.
- •4.2. Анализ матричных игр двух игроков с нулевой суммой в смешанных стратегиях.
- •Самостоятельная работа №6
- •4.3. Биматричные неантагонистические игры.
- •Самостоятельная работа № 7.
- •4.4. Взаимосвязь равновесий по Нешу и Парето в играх.
- •Самостоятельная работа № 8.
- •4.5. Динамические игры с полной информацией
- •Самостоятельная работа № 9
- •5. Задачи дискретного программирования.
- •5.1. Методы отсечения для решения задач целочисленного линейного программирования.
- •Самостоятельная работа № 10.
- •5.2. Комбинаторные методы решения задач целочисленного линейного программирования.
- •5.3. Алгоритм Ленд–Дойг.
- •Самостоятельная работа № 11.
- •5.4. Метод ветвей и границ для решения задачи о коммивояжере.
- •Самостоятельная работа № 12.
- •6.Транспортные задачи линейного программирования
- •6.1. Транспортная задача в сетевой постановке
- •Самостоятельная работа 13.
- •6.2. Транспортная задача в матричной постановке.
- •Самостоятельная работа 14.
- •7. Динамическое программирование и потоки в сетях
- •7.1. Задача оптимизации многошаговых процессов, задача о ранце.
- •Самостоятельная работа 15.
- •7.2 .Задача отыскания кратчайшего расстояния в сети между парами вершин
- •Самостоятельная работа 16.
- •7.2. Задача о максимальном потоке в сети.
- •Самостоятельная работа 17.
- •Литература.
Самостоятельная работа №6
Найти решение матричной игры в смешанных стратегиях для следующих матриц:
1. A=, |
2. A=, |
3. A=, |
4. A=, |
5. A=,. |
6. A=, |
7. A=, |
8. A=, |
9. A=, |
10. A=, |
11. A=, |
12. A=, |
13. A=, |
14. A=, |
15. A= |
16. A=, |
17. A=, |
18. A= |
19. A= |
20. A=, |
21. A=, |
22. A=, |
23. A=, |
24. A=, |
25. A=,. |
26. A=, |
27. A=, |
28. A=, |
29. A=, |
30. A=, |
31. A=, |
32. A=, |
4.3. Биматричные неантагонистические игры.
Рассмотрим теперь примеры игр [27], в которых, вообще говоря, выигрыш одного игрока во многих случаях не равен проигрышу второго.
Игра 1. «Выбор автомобиля».
Двое знакомых одновременно выбирают автомобили японских фирм. Первый предпочитает автомобиль марки Хонда, второй — Тойота. Обладание автомобиля любимого типа первый оценивает в а (а > 0) некоторых условных единиц, а второй — в b (b >0) условных единиц. Полезность автомобиля другого типа для обоих равна нулю. Каждый получает дополнительную выгоду (с > 0), если они выберут одинаковые автомобили, поскольку в таком случае используемое ими запасные части будет совместимым.
В этом примере каждый из игроков (мы будем их называть «Игрок 1» и «Игрок 2») имеет две стратегии, которые можно условно назвать «Хонда» и «Тойота». Описанную игру удобно представить в виде таблицы (матрицы) 22. В игре имеется четыре исхода: (Хонда, Хонда), (Хонда, Тойота) (Тойота, Хонда) и (Тойота, Тойота). Каждому исходу соответствует своя клетка таблицы; в этой клетке помещаются соответствующие выигрыши участников.
Таблица для первого игрока
-
Выбор второго игрока
Хонда
Тойота
Выбор первого игрока
Хонда
a+c
A
Тойота
0
0+c
Таблица для второго игрока
-
Выбор второго игрока
Хонда
Тойота
Выбор первого игрока
Хонда
0+c
b
Тойота
0
b+c
Для анализа игр с двумя игроками целесообразно таблицы объединить. В северо-западном углу выигрыш первого игрока, в юго-восточном – второго.
-
Выбор второго игрока
Хонда
Тойота
Выбор
первого
игрока
Хонда
a+c
0+c
a
b
Тойота
0
0
0+c
b+c
Левый верхний угол клетки таблицы отведен для первого игрока, нижний правый для второго. Рассмотрим анализ этой игры для случая, когда a=7,b=8,c=3. В этом случае предыдущая таблица будет иметь вид
-
Выбор второго игрока
Хонда
Тойота
Выбор
первого
игрока
Хонда
3
Тойота
0
0
3
Выбор первого при условии, что второй игрок принял «Хонда» является «Хонда», при условии, что второй игрок принял «Тойота» так же является «Хонда». Максимальные значения критериев в обоих случаях надчеркнуты. Аналогично для второго игрока, максимальные значения для второго игрока подчеркнуты. В клетке («Хонда»,«Тойота») оказались помеченными оба значения выигрышей, поэтому эта клетка будет состоянием равновесия.
В игре, приведенной в следующей таблице нет состояния равновесия, так как в ней нет клетки, в которой одновременно выделены значения обоих критериев.
|
|
Выбор второго игрока | |
|
|
1 |
2 |
Выбор первого игрока |
1 |
5 |
7 |
2 |
2 |
4 |
Игра 2. Пешеход и автомобилист.
В игре участвуют пешеход и автомобилист. Каждый из игроков имеет две стратегии: проявлять осторожность (А) и не проявлять осторожности (В). От выбранных стратегий зависит вероятность дорожно–транспортного происшествия (автомобилист собьет пешехода). Если оба ведут себя неосторожно, то вероятность происшествия равна 1/2, если только один ведет себя неосторожно, то вероятность равна 1/10, а если оба осторожны, то вероятность равна 1/100.
В случае, если произойдет столкновение, то ущерб пешехода составит 1000 у.е., а ущерб автомобилиста — 200 у.е. Кроме того, осторожное поведение на дороге связано для обоих игроков с издержками в 100 у.е.
На примере Игры 2 рассмотрим, каким образом представить в нормальной форме игру, включающую случайность. Для этого нам необходимо задать способ вычисления выигрышей (все остальные элементы нормальной формы здесь уже указаны).
Стандартное предположение теории игр состоит в том, что если выигрыш — случайная величина, то игроки предпочитают действия, которые приносят им наибольший ожидаемый выигрыш. Предполагается, что в описании игры случайные выигрыши даны в таком виде, что можно рассчитать их математическое ожидание и использовать в качестве выигрышей в нормальной форме игры. Таким образом, выигрыши выражены в некоторых условных единицах (вовсе не обязательно денежных) и представляют некоторый абстрактный уровень полезности для игрока при данном сочетании стратегий.
Пусть оба участника игры проявляют осторожность, то есть реализовался исход (А, А). Если произойдет столкновение, то выигрыш пешехода составит (–1100), а выигрыш водителя — (–300). В противном случае выигрыш пешехода составит (–100), а выигрыш водителя — (–100). Ожидаемые выигрыши равны в этом случае:
1/100* (–1100) + 99/100* (–100) = –110 — для пешехода
1/100* (–200)+99/100*(–100)=–102 — для автомобилиста.
Эту информацию вносим в левую верхнюю клетку таблицы.
|
Автомобилист | ||
A |
B | ||
Пеше– ход
|
A |
–102 |
* ^ |
B |
–100* –120 |
–500 ^ |
Из анализа этой игры видно, что состояние равновесия соответствует клетке (A,B), т.е. пешеход должен действовать осторожно, водитель неосторожно.
Замечание.В этой игре цифры взяты произвольно, более того не проанализировано взаимодействие «водитель» – «водитель», поэтому водителям вряд ли следует действовать в соответствии с решением в этой игре.