close

Вход

Забыли?

вход по аккаунту

?

4x4 3k+2

код для вставкиСкачать
МИНИСТЕРСТВО
ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Московский государственный институт электроники и математики
(Технический университет)
Кафедра исследования операций
Курсовая работа
по дисциплине:
«Теория игр и исследование операций.
Матричные игры.»
Выполнил:
студент М-71
Потапова Надежда Васильевна
Проверила:
Сёмина Елена Александровна
Москва 2007 г.
Задание
Каждый из двух игроков имеет по 4 фишки. Каждый игрок независимо от
другого распределяет свои фишки по
позициям. Выигрыш игрока
складывается из выигрышей, полученных им на каждой позиции. Если на
позиции количество размещённых игроками фишек оказалось одинаковым,
то выигрыш каждого игрока нуль. Игрок, разместивший на позиции большее
количество фишек, выигрывает эту позицию и все фишки противника,
расположенные на ней. Стоимость позиции и стоимость 1 фишки – 1
единица.
Для параметра =3k+2,
, построить матрицу антагонистической игры и
найти её решение, то есть определить
тройку
, где
множество оптимальных смешанных стратегий игрока 1, а
-
множество оптимальных смешанных стратегий игрока 2.
Решение
Решаем задачу в общем виде для . Рассмотрим способы распределения
четырех фишек по позициям. Существует пять способов размещения 4
фишек на какой-либо позиции:
1. 4+0
2. 2+2+0
3. 3+1+1+0
4. 2+1+1+0
5. 1+1+1+1+1
Сгруппируем стратегии игроков в матрице A так, чтобы они образовывали
группы, которые удовлетворяют разбиению матрицы A на блоки, описанные
в Теореме 7 (на стр. 8 Методических указаний к курсовой работе).
Теорема 7.
Пусть
где
 A1 1

A
A   21
...

A
 m1
A1 2
A2 2
...
Am2
...
...
...
...
A1s 

A2 s 
... 

Am s 

– блоки
Пусть в блоке
сумма элементов в каждой строке одинакова, и в каждом
столбце тоже. Обозначим через:
- среднее арифметическое всех элементов блока
,
- сумму элементов в строке блока
,
- сумму элементов в столбце блока
(очевидно, что
Пусть матрица
Пусть
- оптимальные стратегии игрока 1 и
игрока 2 в игре
. Тогда
,
- оптимальные
стратегии игрока 1 и игрока 2 в игре
Доказательство теоремы:
Пусть
– цена игры
функция выигрыша.
Пусть – цена игры
и
.
.
- ее
- оптимальные стратегии игроков в игре
.
.
Таким образом,
Осталось доказать, что
(для
равна цене игры
.
Предположим, что
Вычислим
. Цена игры
.
и
- оптимальные стратегии. Докажем для
доказательство аналогично).
Докажем, что
игрока 1 в
Рассмотрим
(множество смешанных стратегий
.
.
Заметим, что: 1)
,
,
смешанных стратегий игрока 1 в игре
(множество
).
2)
Аналогично
- оптимальные стратегии игроков в игре
.
Теорема доказана.
-матрица, так как каждый из игроков может разложить свои фишки
одним из пяти способов.
Вероятностный смысл элемента
:
математическое
ожидание выигрыша игрока 1, выбравшего стратегию, соответствующую iому разбиению, тогда когда игрок 2 выбрал стратегию под номером .
Рассмотрим игрока 1. Зафиксируем способ разбиения на группы:
, где – количество позиций с i-фишками.
Очевидно, что
,то есть
.
- все возможные способы разложить 4 фишек по позициям.
Рассмотрим случайную величину
- выигрыш игрока 1 на -ой позиции.
-
случайное событие, заключающееся в том, что в результате эксперимента на
-ой позиции окажется -фишек,
, игрока 1 .
- случайное событие,
заключающееся в том, что в результате эксперимента на -ой позиции
окажется
-фишек, j
игрока 2.
– вероятность того, что на фиксированной позиции при
применении игроком 1 чистой стратегии будет занята
определяется аналогично.
фишками.
Нас интересует величина:
,
.
Рассчитаем матрицу
Замечание. Матрица B будет кососимметрическая.
4,4
0
0,41
4,0
1
0,0
0
4,3
4
0,31
4,1
2
0,11
4,0
1
0,0
0
4,2
3
0,21
4,0
1
0,0
0
4,2
3
0,21
4,1
2
0,11
b11  l   1  (l 1) 1 (l 1)  1   0
l
l
l
l
4,0
1
0,0
0
4,1
2
0,11
4,0
1
0,0
0
3,2
3
3,0
1
1,22
1,0
1
0,2
-1
0,0
0
3,2
3
3,0
1
1,2
-2
1,0
1
0,2
-1
0,0
0
3,1
3
3,0
1
1,0
1
1,1
0
0,11
0,0
0
2,2
0
2,1
2
2,0
1
0,1
-1
0,21
0,0
0
2,1
2
0,11
2,0
1
0,0
0
2,1
2
1,1
0
0,11
2,0
1
1,0
1
0,0
0

 0
 l 6

 l
l 6
B
 l
 2l  7

 l
 3l  8

 l
6l
l
0
2
l
l 5
l
2l  8
l

6l
l
2
l
0
l 8
l
2l  16
l
7  2l
l
5l
l
8l
l
0
l 8
l
8  3l 

l
8  2l 

l

16  2l 

l
8l 

l

0 


Так как матрица В кососимметрическая, то
, и
(множества оптимальных стратегий для 1-го и второго игрока совпадают) по
Теореме 3 (на стр. 5 Методических указаний к курсовой работе).
Решение игры с матрицей
не изменится, если рассмотреть
.
6l
6  l 7  2l 8  3l 
 0
 l 6
0
2
5  l 8  2l 

~
В   l 6
2
0
8  l 16  2l 


0
8l 
2l  7 l  5 l  8
3l  8 2l  8 2l  16 l  8
0 
Рассмотрим
. Тогда:
1  3  7
0 1
 1 0
2
0  2

~
В   1  2 0
3
6


3
 3 0 3 0
 7 2  6  3 0 
Используем Теорему 4 (О доминировании) (на стр. 5 Методических
указаний к курсовой работе) и заметим, что:
1) Строка 4 есть линейная комбинация строк 3 и 5 с коэффициентами 1/2,
1/2.
2) Столбец 4 есть линейная комбинация столбцов 3 и 5 с коэффициентами
1/2, 1/2.
Таким образом, получим:
0
 1
~
B*  
 1

7
Ищем
1
0
2
2
1
2
0
6
 7
 2

6 

0 
вектор
-
являющийся
оптимальной
смешанной стратегией игроков 1 и 2, с помощью свойства 3) оптимальных
стратегий (на стр. 5 Методических указаний к курсовой работе), а именно
решаем следующую систему алгебраических неравенств(уравнений)
(5)+(6):
Возвращаемся к системе:
Подставляем полученные результаты в систему:
Получили оптимальную смешанную стратегию 1 и 2
~
игроков для матрицы B * .
~
Возвращаемся к матрице В и ищем вектор
,
являющийся оптимальной смешанной стратегией игроков 1 и 2.
Поиск решения начнем с определения несущественных и существенных
~
компонентов вектора. В матрице B * 2,3,4 компоненты вектора были
существенными (не нулевыми) , можно утверждать, что соответственные
~
компоненты вектора для матрицы В тоже будут существенными на
основании теоремы 5. Значит , 2,3,5 компоненты не равны нулю.
Для
проверим, являются ли компоненты несущественными, используя
следствие к теореме 2. Подставляя вектор
в
матрицу В, видим, что 1 стратегия является несущественной, т.к. при
подстановки вектора в 1 столбец очевидно, что он больше 0,т.е.
всегда. При подстановке в 4 столбец получаем равенство.
То есть теперь мы ищем решение в виде:
Решаем систему линейных неравенств и уравнений:
Рассмотрим
. Тогда:
 0  2  2  9 16
2 0

2

3

8

~ 
В   2 2 0
0
0 


9
3
0
0
0


16 8
0
0
0 
Для
существует решение в чистых стратегиях. Просматриваем все
строки и в них ищем минимальный элемент, а затем проверяем является ли
он максимальным в столбце.
Найдем все оптимальные смешанные стратегии первого (второго) игрока.
. 4,5 компоненты вектора существенные (не
равны 0) на основании теоремы 5.
Подставляя вектор в матрицу В, видим, что 1,2 стратегии являются
несущественной, т.к. при подстановки вектора в 1,2 столбцы ,очевидно, что
они больше 0,т.е.
всегда.
Получаем систему:
Получим решение для матрицы А:
Документ
Категория
Математика
Просмотров
7
Размер файла
3 310 Кб
Теги
4x4_3k
1/--страниц
Пожаловаться на содержимое документа