--PAGE_BREAK--2.Матричные игры
Матричной игрой называется конечная игра двух игроков с нулевой
суммой, в которой задается выигрыш игрока 1 в виде матрицы, строка матрицы
соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы
находится выигрыш игрока 1, соответствующий применяемым стратегиям.
Пусть играют 2 игрока P1 и P2. Матрица
элементы aij – выигрыш игрока P1, если P1 – выбирает i строку, а P2 – выбирает j столбец, называется платежной матрицей игры.
Пусть игрок P1 выбирает i строку с вероятностью xi, P2 выбирает j столбец с
вероятностью yj, тогда и будут называться соответственно смешанными стратегиями 1-ого и 2-ого игроков.
Замечание: так как компонентами смешанных стратегий X и Y являются
вероятности, то и . Если среди компонентов смешанной стратегии X только одна 1, остальные 0, то стратегия называется чистой.
— i-ая чистая стратегия. Любую смешанную стратегию можно представить в виде выпуклой комбинации чистых стратегий, т.е.
Пример. Представить смешанную стратегию в виде выпуклой
комбинации чистых стратегий.
Решение.
Платежной функцией (X ,Y ) первого игрока называется математическое
ожидание его выигрыша, т.е.
(X ,Y )=
Решением матричной игры называют пару смешанных стратегий и
число v называемое ценой игры, удовлетворяющих следующим условиям:
1)
Если P1 придерживается своей оптимальной стратегии X*, то какую бы
чистую стратегию не принимал второй игрок P2, P1 получит выигрыш не меньше чем цена игры v.
2)
Если P2 придерживается своей оптимальной стратегии Y*, то какую бы чистую стратегию не применял второй игрок P1, то P2 проиграет не более чем цена игры v.
Теорема
1. Если игрок P1 придерживается своей оптимальной стратегии X*,
а P2 придерживается своей оптимальной стратегии Y*, то.
Теорема
2. Любая матричная игра имеет решение в смешанных стратегиях.
3.Решение матричной игры в чистых стратегиях
Рассмотрим матричную игру с игроками P1 и P2 и платежной матрицей
1) Перед игроком P1 стоит задача выбора чистой стратегии, в результате применения которой он получит максимально возможный гарантированный
выигрыш. Если игрок P1 выбрал стратегию , то его выигрышем может быть один из выигрышей , расположенный в i-ой строке платежной
матрицы, в зависимости от выбранной стратегии игроком P2. Предполагая поведение игрока P1 крайне осмысленным, необходимо считать, что игрок P2 сыграет наилучшим для себя образом и на выбор игроком P1 стратегии Xiвыберет ту стратегию Yj, при которой выигрыш игрока P1 окажется минимальным.
Обозначим минимальный среди выигрышей через αi:
, (αi –показатель эффективности стратегии Xi).
Продолжая действовать разумно, игрок P1 должен выбрать ту стратегию,
которая максимизирует показатель эффективности, т.е. для которой число αi максимально.
Обозначим:
Число α называется нижней ценой игры в чистых стратегиях, а стратегия
Xi0, которая максимизирует показатель эффективности αi называется максиминной стратегией игрока P1.
Таким образом, если игрок P1 в игре будет следовать максиминной стратегии, то ему при любой игре противника P2 гарантирован выигрыш в чистых стратегиях, не меньший α.
2) Рассмотрим игру с точки зрения игрока P2, который стремиться минимизировать выигрыш игрока P1. Если P2 выберет стратегию , то выигрышем игрока P1 может быть один из выигрышей . Но так как игрок P2 предполагает, что игрок P1 играет наилучшим для себя образом, то выигрышем игрока P1 будет максимальное из этих чисел, обозначим βj:
(βj –показатель неэффективности стратегии Yj).
Таким образом, для любой стратегии Yj игрока P2 наибольший его проигрыш равен βj. В интересах игрока P2 выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел βj обозначим β:
Число β называется верхней ценой игры в чистых стратегиях, а стратегия Yj0, которая максимизирует показатель неэффективности βj называется минимаксной стратегией игрока P2.
Теорема
3. Для элементов платежной матрицы имеют место неравенства:
и, следовательно, нижняя цена игры не больше ее верхней цены в чистых стратегиях:.
Пример. Найти решение игры, заданной платежной матрицей.
Решение:
Решим игру. Пусть – оптимальная стратегия первого игрока, – оптимальная стратегия второго игрока, v – цена игры.
Рассмотрим матрицу
min
max(-1,-2,4)=4=
max 6 7 4 10
min(6,7,5,10)=5=
— нижняя цена игры.
— верхняя цена игры.
— максиминная стратегия, — минимаксная стратегия
Если то элемент называется седловым элементом матрицы
A=
Теорема
4. (о разрешимости матричной игры в чистых стратегиях) Если платежная матрица A имеет седловой элемент , то матричная игра имеет решение в чистых стратегиях, при этом оптимальной стратегий первого игрока является X
i
чистая стратегия, а для второго – Yj0 чистая стратегия, а цена игры v = .
Пример. Найти решение игры, заданной платежной матрицей A=
Решение:
Решим игру. Пусть -оптимальная стратегия первого игрока, — оптимальная стратегия второго игрока, v– цена игры.
Рассмотримматрицу
min
max 2 3
v==2 цена игры v = 2, существует седловой элемент =, тогда решение в чистых стратегиях имеет вид:
оптимальная стратегия первого игрока:
оптимальная стратегия второго игрока:
Ответ: оптимальные стратегии игроков ; , цена игры v =2 .
продолжение
--PAGE_BREAK--4.Принцип доминирования
Рассмотрим игру с платежной матрицей
A=.
Если , то говорят, что j-ая строка доминируется i-ой строкой, при этом i-ая строка называется доминирующей для первого игрока P1; j-ая строка – доминируемой строкой для P1.
Если , то говорят, что i-ый столбец доминируется j-ым столбцом, при этом j-ый столбец называется доминирующим для второго игрока P2; i-ый столбец – доминируемый для P2. Доминируемую для игрока P1 строку и доминируемый для P2 столбец можно вычеркнуть (удалить).
Пример. Упростить платежную матрицу A=, используя принцип доминирования.
Решение.
1 способ: , т.к. — доминирующая строка, -
доминируемая строка (1)
2 способ:, (1)
5.Решение матричной игры 2×2 в смешанных стратегиях
Решить игру с платежной матрицей
Платежная функция
Решить игру с платежной матрицей
Положим . Тогда
. Тогда
Если — оптимальная стратегия первого игрока, то по определению
решения матричной игры
Если игра с нулевой суммой, то (-цена игры).
Решая систему, получим .
Аналогично для второго игрока:
Тогда
Тогда
Если — оптимальная стратегия второго игрока.
Если игра с нулевой суммой, то (-цена игры).
Решая систему, получим .
Пример. Найти решение игры заданной платежной матрицей A= .
Решение:
Решим игру. Пусть — оптимальная стратегия первого игрока, — оптимальная стратегия второго игрока,-цена игры. Тогда оптимальные стратегии игроков и цену игры можно найти, решив системы:
Ответ:оптимальные стратегии игроков , цена игры .
продолжение
--PAGE_BREAK--Геометрическое решение игры 1.Решение игр с платежной матрицей 2×n
Решить игру с платежной матрицей A=
Алгоритм:
1) Через концы горизонтального отрезка [0;1] провести два перпендикуляра к нему: левый и правый. Каждой точке отрезка [0;1] будем ставить некоторую смешанную стратегию (x;1− x).
2) На левом перпендикуляре от точки 0 отложить элементы . На правом перпендикуляре от точки 1 отложить элементы .
Замечание. Масштабы на левом и правом перпендикулярах должны быть
одинаковы, не обязательно совпадающие с масштабом горизонтального отрезка [0;1].
3) Соединить отрезками элементы .
4) Выделить нижнюю огибающую всех построенных отрезков, и найти максимальную точку (точки). Пусть точка является пересечением отрезков и . Тогда оптимальную стратегию можно найти при помощи матрицы .
Решить игру с платежной матрицей A= графически.
Решение:
1. Через концы горизонтального отрезка [0;1] проведем 2 перпендикуляра к нему. Каждой точке отрезка [0;1] будем ставить смешанную стратегию (x; 1− x).
2. На левом перпендикуляре от точки 0 отложить элементы 2, 3, 11. На правом перпендикуляре от точки 1 отложить элементы 7, 5, 2.
3. Соединить отрезками элементы 2 и 7, 3 и 5, 11 и 2.
4. Выделим нижнюю огибающую всех построенных отрезков, и найдем
максимальную точку. Точка является пересечением отрезков [3;5] и [11;2]. Тогда оптимальную стратегию можно найти при помощи матрицы .
Решим игру с платежной матрицей .
Оптимальные стратегии игроков и цену игры можно найти, решив системы:
Ответ:оптимальные стратегии игроков оптимальные стратегии игроков , цена игры
продолжение
--PAGE_BREAK--2.Решение игр с платежной матрицей m×2
Решить игру с платежной матрицей A=.
Алгоритм:
1) Через концы горизонтального отрезка [0;1] провести два перпендикуляра к нему: левый и правый. Каждой точке отрезка [0;1] будем ставить некоторую смешанную стратегию (y;1− y).
2) На левом перпендикуляре от точки 0 отложить элементы . На правом перпендикуляре от точки 1 отложить элементы .
3) Соединить отрезками элементы .
4) Выделить верхнюю огибающую всех построенных отрезков, и найти минимальную точку (точки). Пусть точка является пересечением отрезков Тогда оптимальную стратегию можно найти при помощи матрицы .
Пример. Решить игру с платежной матрицей A=.
Решение:
Решим графическим методом.
1. Через концы горизонтального отрезка [0;1] проведем 2 перпендикуляра к нему. Каждой точке отрезка [0;1] будем ставить смешанную стратегию (y; 1− y).
2. На левом перпендикуляре от точки 0 отложить элементы 6, 4, 2, 1. На правом перпендикуляре от точки 1 отложить элементы 5, 6, 7, 8.
3. Соединить отрезками элементы 6 и 5, 4 и 6, 2 и 7, 1 и 8.
4. Выделим верхнюю огибающую всех построенных отрезков, и найдем минимальную точку. Точка является пересечением отрезков [6;5] и [1;8]. Тогда оптимальную стратегию можно найти при помощи матрицы .
Решим игру с платежной матрицей
Ответ:оптимальные стратегии игроков оптимальные стратегии игроков , цена игры
Практическая Часть
1. Решить Систему
1.1 По формулам Крамера
Решение.
1)Составим определитель из коэффициентов стоящих при неизвестных в системе.
2)Тогда по теореме Крамера:
3)Проверка:
Ответ:
1.2 Методом Гаусса
Решение.
1)Составим расширенную матрицу системы:
2)Преобразим расширенную матрицу к ступенчатому виду:
3)Расширенная приведена к расширенному виду. Получили следующую систему уравнений:
Ответ:
4. Решить транспортную задачу, заданную таблицей. Спланировать перевозки так, чтобы общая их стоимость была минимальной.
Пункт отправления
В1
В2
В3
B4
В5
Запасы,аi (тонн)
А1
14
8
17
5
3
120
А2
21
10
7
11
6
180
А3
3
5
8
4
9
230
Потребности, bj (тонн)
70
120
105
125
110
530
продолжение
--PAGE_BREAK--