- •Системный анализ и принятие решений
- •14.1. Постановка задачи 87
- •Лекция 1. Введение в методологию системного анализа
- •1.1. Предмет и содержание курса. Основные определения
- •1.2. Классификация систем
- •1.3. Сущность системного подхода
- •Лекция 2. Задачи системного анализа
- •2.1. Характеристика задач системного анализа
- •Внедрение результатов анализа.
- •2.2. Основные приемы формализации задач системного анализа
- •2.3. Внедрение результатов анализа
- •2.4. Примеры задач системного анализа
- •Методика по Оптнеру
- •Лекция 3. Основные понятия и определения теории принятия решений
- •3.1. Основные принципы теории принятия решений
- •3.2. Постановка задач принятия оптимальных решений
- •3.3. Этапы принятия решений
- •Лекция 4. Построение (выбор) моделей системы
- •4.1. Классификация видов моделирования систем
- •4.2. Возможности и эффективность моделирования систем на вычислительных машинах
- •Лекция 5. Математическое программирование
- •5.1. Структура оптимизационных задач
- •5.2. Математические постановки задач, приводящие к моделям линейного программирования
- •Лекция 6. Содержательные постановки задач линейного программирования. Методы решения задач линейного программирования
- •6.1. Содержательные постановки задач, приводящие к моделям линейного программирования.
- •6.2. Численные методы математического программирования
- •Лекция 7. Решение задач линейного программирования симплекс-методом
- •Симплекс-таблица
- •Лекция 8. Двойственная задача линейного программирования
- •Лекция 9. Транспортные задачи линейного программирования
- •9.1. Постановка задачи
- •9.2. Методы составления начального опорного плана
- •9.3. Понятие потенциала и цикла
- •9.4. Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения
- •8.5. Усложненные задачи транспортного типа
- •Лекция 10. Дискретное программирование.
- •10.1. Постановка задачи дискретного программирования
- •10.2. Математические модели задач дискретного программирования
- •10.3. Метод ветвей и границ для задачи целочисленного программирования
- •Лекция 11. Нелинейное программирование
- •11.1. Постановка задачи нелинейного программирования
- •11.2.Решение задач нелинейного программирования в системе matlab
- •Лекция 12. Динамическое программирование
- •Лекция 13. Принятие решений в условиях неопределенности. Введение в матричные игры.
- •14.1. Основные понятия теории игр. Введение в матричные игры
- •14.2. Формальное описание матричной антагонистической игры
- •Лекция 14. Решение игр в смешанных стратегиях
- •14.1. Постановка задачи
- •14.2. Основные понятия теории статистических решений
- •15.3. Выбор критерия принятия решения
- •14.3.1. Критерий Лапласа
- •15.3.2. Критерий Вальда
- •14.3.3. Критерий Гурвица
- •14.3.4. Критерий Cэвиджа
14.2. Формальное описание матричной антагонистической игры
Важными и хорошо изученными играми являются парные антагонистические игры.
Тройка
G=<X,Y,A>,
где X,
Y
- множества чистых стратегий 1-го и 2-го
игроков соответственно,
A(x,y)
x
X,
y
Y
– функция выигрыша
первого игрока, или просто функция
выигрыша, называется антагонистической
игрой с нулевой суммой.
Если X и Y конечны, то G называется конечной антагонистической игрой. Пары стратегий вида (x,y) называются ситуациями в игре G. Цель каждого из игроков в игре – получить максимальный выигрыш. Игрок 1, изменяя x X, старается максимизировать A(x,y), а игрок 2 выбирает y Y так, чтобы минимизировать A(x,y), но каждый из игроков в отдельности не контролирует полностью значение A(x,y). Задача теории игр состоит в определении наиболее рационального поведения каждого игрока.
Процесс разыгрывания конечной антагонистической игры состоит в следующем.
1-й игрок выбирает чистую стратегию x X;
Независимо от первого игрока 2-й игрок выбирает чистую стратегию y Y;
Возникает ситуация (x,y), в которой 1-й игрок получает от 2-го игрока выигрыш A(x,y), при этом 2-й игрок столько же проигрывает, т.е. его выигрыш составляет - A(x,y).
Так как число возможных действий каждого из игроков конечно, а содержательная сущность стратегии определяется вне математической модели, можно предполагать, что 1-й игрок имеет m стратегий, т.е. X={1,2,…,m, }, а 2-й игрок имеет n стратегий, т.е. Y={1,2,…,n}. Пусть из своих m стратегий 1-й игрок выберет i-ю стратегию (i=1,…m), а 2-й игрок выберет j-ю стратегию (j=1,…n), тогда значения функции A(x,y) естественно представить в виде матрицы A размерности m×n
где в i-й строке расположены выигрыши 1-го игрока в ситуациях (i,1),…,(i,n), а в j-м столбце – проигрыши 2-го игрока в ситуациях (1,j),…,(m,j).
Примеры матричных игр
Игра в орлянку.
Игроки выбирают ход{орел, решка}. Если ходы совпали, то выиграл первый, иначе второй.
II игрок I игрок |
орел |
решка |
орел |
1 |
– 1 |
решка |
– 1 |
1 |
Прорыв обороны. Первый игрок выбирает систему зенитного вооружения. Второй игрок выбирает самолет. Элементы aij задают вероятность поражения самолета j системой i. Цель второго игрока — прорвать оборону.
|
Самолеты |
||
Зенитки |
0,5 |
0,6 |
0,8 |
0,9 |
0,7 |
0,8 |
|
0,7 |
0,5 |
0,6 |
|
В первом примере все ходы одинаково плохи или хороши. Во втором примере ход (2, 2) в некотором смысле лучший для обеих сторон: если взять самолет 2, то зенитка 2 — лучшая для первого игрока; если взять зенитку 2, то самолет 2 лучший для второго. В матрице есть седловая точка!
Определение. Седловой точкой матрицы (aij) называют пару (i0j0) такую, что
aij0≤ai0jo≤ai0j
Принцип минимакса (осторожности).
Предположим, что противник всеведущ и угадывает все ходы! Первый игрок предполагает, что второй все знает и для хода i первого игрока выберет j(i): aij(i) aij, j = 1,…, n. Обозначим αi=aij(i)=min aij, j=1,…,n; i=1,...,m
Тогда лучшей стратегией для первого игрока является выбор i0 такой, что
α=maxiai=maxi minjaij=αi0
Величину назовем нижней ценой игры в чистых стратегиях.
Второй игрок из соображений осторожности считает, что первый j выберет i(j) так, что aij (j) aij, i, т.е. βj=max aij,j=1,…,m и выбирает j с минимальным j, т.е.
Β=minj maxi aij=βj0
Величину назовем верхней ценой игры в чистых стратегиях.
Пример 1. = –1, = +1,
Пример 2. α=max{0.5, 0.7, 0.5}=0.7;
β=min{0.9, 0.7, 0.8}=0.7.
α=β.
Лемма. Для любой функции f(x,y), xX, yY, справедливо неравенство
в предположении, что эти величины существуют.
Доказательство. Введем обозначения:
Тогда
Теорема.
Необходимым и достаточным условием
равенства верхней и нижней цен игры в
чистых стратегиях является существование
седловой точки в матрице (aij).
Доказательство. Необходимость. Пусть = . По определению
т.е. α≤αi0j0≤β.
Так как = ,
то αij0≤αi0j0≤
αi0j,
,
т.е. является седловой точкой.
Достаточность. Пусть седловая точка (i0j0) существует, т.е.
то αij0≤αi0j0≤ αi0j, .
Тогда
но по лемме верно обратное, т.е.
.
Следовательно
= .
