МИНИСТЕРСТВО
ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Московский Государственный институт электроники и математики
(Технический университет)
Кафедра исследования операций
Курсовая работа
по дисциплине:
«Теория игр и исследование операций.
Матричные игры.»
Выполнила: студентка гр. М-72, ФПМ
Козулина Юлия.
Проверила: канд. физ.-мат. Наук
Москва 2007 г.
Задание.
Каждый из двух игроков имеет по 5 фишек. Каждый игрок независимо от другого распределяет свои фишки по l позициям. Выигрыш игрока складывается из выигрышей, полученных им на каждой позиции. Если на позиции количество размещённых игроками фишек оказалось одинаковым, то выигрыш каждого игрока нуль. Игрок, разместивший на позиции большее количество фишек, выигрывает эту позицию и все фишки противника, расположенные на ней. Стоимость позиции и стоимость 1 фишки – 1 единица.
Для параметра l = 5k + 2, 
построить матрицу антагонистической игры и найти её решение, то есть определить тройку 
, где 
- множество оптимальных смешанных стратегий игрока 1, а 
- множество оптимальных смешанных стратегий игрока 2.
Решение.
Начнём разбор игры с общего случая l.
1) Пронумеруем игроков.
2) Считаем:
· P – множество стратегий игрока 1;
· Q – множество стратегий игрока 2.
3) Матрица игры А будет очень большой размерности, поэтому мы для решения игры 
воспользуемся Теоремой 7 (на стр. 8 Методических указаний к курсовой работе) и найдём матрицу B.
Решения игр и 
связаны по Теореме 7 следующим образом:
ü 
(У игр с данными матрицами одинаковые цены игр);
ü Если 
и 
- оптимальные стратегии игрока 1 и игрока 2 в игре , то
и 
-
Оптимальные стратегии игрока 1 и игрока 2 в игре .
Для применения Теоремы 7 надо правильно группировать стратегии игроков 1 и 2 в матрице А, так чтобы они образовывали группы, удовлетворяющие разбиению матрицы А на блоки, описанные условиями Теоремы 7.
Для этого рассмотрим способы распределения 5 фишек по l позициям.
Их всего 7:
1) 5+0
2) 4+1
3) 3+2
4) 3+1+1
5) 2+2+1
6) 2+1+1+1
7) 1+1+1+1+1
Из данного утверждения видно, что матрица В имеет размерность 7х7.
Вероятностный смысл элементов матрицы В: 
(
) есть математическое ожидание выигрыша игрока 1, выбравшему стратегию из группы с номером i, при условии, что игрок 2 выбрал стратегию из группы с номером j.
Определим правило поиска элемента ():
Рассмотрим игрока 1. Фиксируем способ разбиения 5 фишек на группы.
, и 
.
- все возможные способы разложить 5 фишек по l позициям.
- количество данных способов.
Нас же интересует величина 
(1), где
- выигрыш игрока 1 на позиции i.
Рассмотрим:
- случайное событие, заключающееся в том, что на позиции 1 окажется 
фишек игрока 1 (
).
- случайное событие, заключающееся в том, что на позиции 1 окажется 
фишек игрока 2 (
).
Тогда т. к. и (;) независимые события и все l позиций равноправны., то искомая нами формула (1) имеет вид (2):
(2)
Стоит отметить, что 
, а 
, где (;).
(Отметим, что 
- вероятность того, что на фиксированной позиции при применении игроком 1 чистой стратегии будет занято 
фишек).
Замечание.
Уже начиная с 
матрица В будет иметь размерность 7х7.
А при l<5 матрицу В можно получить путём определённых строк и столбцов из общего вида матрицы В.
Подсчёт матрицы В(7х7).
Напомним способы разбиения:
1) 5+0
2) 4+1
3) 3+2
4) 3+1+1
5) 2+2+1
6) 2+1+1+1
7) 1+1+1+1+1
Замечание 1.
Матрица B будет кососимметрическая.
5,50 0,5-1 5,01 0,00 |
|
5,45 0,4-1 5,12 0,1-1 5,01 0,00 |
|
5,34 0,3-1 5,23 0,2-1 5,01 0,00 |
|
5,34 0,3-1 5,12 0,1-1 5,01 0,00 |
|
5,23 0,2-1 5,12 0,1-1 5,01 0,00 |
|
5,23 0,2-1 5,12 0,1-1 5,01 0,00 |
|
5,12 0,1-1 5,01 0,00 |
|
4,34 1,3-2 0,3-1 4,23 1,2-2 0,2-1 4,01 1,01 0,00 |
|
4,34 1,3-2 0,3-1 4,12 1,10 0,1-1 4,01 1,01 0,00 |
|
4,23 1,2-2 0,2-1 4,12 1,10 0,1-1 4,01 1,01 0,00 |
|
4,23 1,2-2 0,2-1 4,12 1,10 0,1-1 4,01 1,01 0,00 |
|
4,12 1,10 0,1-1 4,01 1,01 0,00 |
|
3,30 2,3-2 0,3-1 3,12 2,12 0,1-1 3,01 2,01 0,00 |
|
3,23 2,20 0,2-1 3,12 2,12 0,1-1 3,01 2,01 0,00 |
|
3,23 2,20 0,2-1 3,12 2,12 0,1-1 3,01 2,01 0,00 |
|
3,12 2,12 0,1-1 3,01 2,01 0,00 |
|
3,23 1,2-2 0,2-1 3,12 1,10 0,1-1 3,01 1,01 0,00 |
|
3,23 1,2-2 0,2-1 3,12 1,10 0,1-1 3,01 1,01 0,00 |
|
3,12 1,10 0,1-1 3,01 1,01 0,00 |
|
2,20 1,2-2 0,2-1 2,12 1,10 0,1-1 2,01 1,01 0,00 |
|
2,20 1,2-2 0,2-1 2,12 1,10 0,1-1 2,01 1,01 0,00 |
|
2,12 1,10 0,1-1 2,01 1,01 0,00 |
|
Умножим матрицу B на l : её решение при этом не изменится.
0 (7-l) (7-l) (8-2l) (8-2l) (9-3l) (10-4l)
(ll) (4-l) (7-2l) (10-3l)
(ll) (10-l) (15-2l) (20-3l)
(2l-8) (l-6) (ll) (10-2l)
(2l-8) (l-4) (l-l) (20-2l)
(3l-9) (2l-7) (2l-15) (l-5) (l-l)
(4l-10) (3l-10) (3l-20) (2l-10) (2l-20) (l-10) 0
Опираясь на общий вид матрицы В можно сделать следующие выводы:
1) Так как матрица В кососимметрическая, то =0 , и 
(множества оптимальных стратегий для 1-го и второго игрока совпадают) по Теореме 3 (на стр. 5 Методических указаний к курсовой работе).
2) При больших l (а именно l>10) матрица В будет иметь следующих схематический вид:
0 
+ 0 3
+ -3 0
+ + + 0 0
+ + + 0 0
+ + + + + 0
+ + + + + + 0
Элементы матрицы возрастают с ростом l при движении по столбцам сверху вниз. Можно сделать вывод о существовании чистой оптимальной стратегии (седловой точки). Элемент 
- максимальный элемент в 7-ой строке и при этом минимальный в 7-ом столбце. Других элементов с подобными свойствами в матрице нет. Более того, из свойства 3) оптимальных стратегий (на стр. 5 Методических указаний к курсовой работе) следует, что других смешанных оптимальных стратегий не существует (из-за вида столбца №7).
Вывод для l>10:
Решение матрицы B:
Решение матрицы A:
******
Решение матричной игры для l = 2.
Так как l мало, то можно выписать матрицу А:
0 0 0 0 | 4 1 1 4 | 3 2 2 3 |
-4 -1 -1 -4 | 0 0 0 0 | 2 1 1 2 |
-3 -2 -2 -3 | -2 -1 -1 -2 | 0 0 0 0 |
; 
;
Элемент 
- максимальный элемент в 1-ой строке и при этом минимальный в 1-ом столбце. Других элементов с подобными свойствами в матрице нет. Более того, из свойства 3) оптимальных стратегий (на стр. 5 Методических указаний к курсовой работе) следует, что других смешанных оптимальных стратегий не существует (из-за вида столбца №1).
Вывод для l=2:
Решение матрицы B:
Решение матрицы A:
Решение матричной игры для l = 7.
Так как l уже достаточно велико, то матрица А будет иметь большую размерность и логично начать решение сразу с матрицы B:
-18
11
0
1
18
Используем Теорему 4 О доминировании ( на стр. 5 Методических указаний к курсовой работе) и заметим, что:
1) Строка 1 доминируется строкой 7 (нестрого).
2) Строка 6 есть линейная комбинация строк 5 и 7 с коэффициентами ½, ½.
3) Столбец 1 доминирует столбец 7 (нестрого).
4) Столбец 6 есть линейная комбинация столбцов 5 и 7 с коэффициентами ½, ½.
Итак, мы вычеркнули 1, 6 строки и 1, 6 столбцы
Замечание.
Так как доминирование нестрогое, то при возврате к матрице B и нахождению её решений у нас могут появиться ненулевые составляющие в векторах смешанных стратегий.
Продолжим решение игры с матрицей:
-11
-
3
1
Ищем вектор 
- являющийся оптимальной смешанной стратегией игроков 1 и 2, с помощью свойства 3) оптимальных стратегий (на стр. 5 Методических указаний к курсовой работе), а именно решаем следующую систему алгебраических неравенств (уравнений):
где 
. И 
.
Но как уже упоминалось в Замечании, при возврате непосредственно к матрице B, у нас в смешанных оптимальных стратегиях могут возникать ненулевые составляющие.
Возвращаемся к матрице В и ищем вектор 
- являющийся оптимальной смешанной стратегией игроков 1 и 2, с помощью свойства 3) оптимальных стратегий (на стр. 5 Методических указаний к курсовой работе), а именно решаем следующую систему алгебраических неравенств (уравнений):
Так как в рассмотренной нами матрице 
2, 3, 4, 5 компоненты векторов 
были ненулевыми (существенными) в общем виде, то можно утверждать, что 3, 4, 5, и 7 компоненты векторов 
также будут существенными (по Теореме 5 (на стр. 6 Методических указаний к курсовой работе) )
Начнём поиск решения с несущественных стратегий, т. е. нулевых компонент вектора, используя Теорему 2 (на стр. 5 Методических указаний к курсовой работе).
Подставляя вектор 
в матрицу В видим, что 1 и 2 стратегии являются несущественными (при подстановке вектора в 1 столбец очевидно, что он больше 0, а во второй столбец: 
>0), т. е. 
и 
всегда.
То есть теперь мы ищем решение в виде: 
Решаем систему линейных неравенств и уравнения:
Вывод для l=7:
Решение матрицы B:
Запишем ответ, используя теорию выпуклых множеств:
Ответ:
Решение матрицы B:
Решение матрицы А:
