Исследование операций
Курсовая работа, 08 Января 2015, автор: пользователь скрыл имя
Краткое описание
Сетевая игра: имеются n точек. Некоторые пары этих точек со-
еденены стрелками. Оба игрока одновременно выбирают по точке.
Если они выбирают одну и ту же точку, или разные, но не соединн-
ные между собой стрелкой, то платж равен нулю. Если они выби-
рают связанную пару точек, то игрок, выбравший острие стрелки,
получает от своего противника +1 балл. Решить сетевую игру.
Файлы: 1 файл
tigr.pdf
— 216.33 Кб (Скачать)| Page 1 |
операций.
Выполнил: Ярослав Киселев, гр. 1400
Вариант 17.
1
| Page 2 |
2
Вариант 17.
1. Пусть A
c
- прямоугольная игра, имеющая матрицу:
A
c
=
c c c
c 3 4
c 5 1
Показать, что для любого числа c цена этой игры иравна V=c.
2. Сетевая игра: имеются n точек. Некоторые пары этих точек со-
еденены стрелками. Оба игрока одновременно выбирают по точке.
Если они выбирают одну и ту же точку, или разные, но не соединн-
ные между собой стрелкой, то платж равен нулю. Если они выби-
рают связанную пару точек, то игрок, выбравший острие стрелки,
получает от своего противника +1 балл. Решить сетевую игру.
3. Заполните следующие выигрыши в таблице так, чтобы в получив-
шейся игре...
(a) не было ни одного равновесия Нэша.
(b) было одно равновесие Нэша.
(c) было два равновесия Нэша.
(d) было три равновесия Нэша.
(e) было четыре равновесия Нэша.
| Page 3 |
3
1
?
?
2
?
?
0
?
Решение.
1
A
c
=
c c c
c 3 4
c 5 1
Для доказательства этого утверждения мы применим формулу:
V =
|A|
IA
∗
I
T
В этой формуле:
I =
(
1 1 1
)
I
T
=
1
1
1
|A| - определитель матрицы A
c
.
|A| =
∣
∣
∣
∣
∣
∣
c c c
c 3 4
c 5 1
∣
∣
∣
∣
∣
∣
= c(5c − 17) A
∗
= |A|A
−1
A
−1
- матрица, обратная к A
c
.
A
−1
=
1
|A|
−17
4c
c
3c
−c(c − 1) c(c − 4)
2c
c(c − 5) −c(c − 3)
A
∗
=
−17
4c
c
3c
−c(c − 1) c(c − 4)
2c
c(c − 5) −c(c − 3)
| Page 4 |
4
Подставляя все вместе мы получим:
V =
∣
∣
∣
∣
∣
∣
∣
∣
∣
c c c
c 3 4
c 5 1
∣
∣
∣
∣
∣
∣
∣
∣
∣
(
1 1 1
)
−17
4c
c
3c
−c(c − 1) c(c − 4)
2c
c(c − 5) −c(c − 3)
1
1
1
=
c(5c−17)
5c−17
= c
Что и требовалось доказать.
2.
Платжная матрица для данной задачи имеет вид:
A =
0 −1 1 −1
1
0
1 −1
−1 −1 0
1
1
1 −1 0
Проверим, есть ли у этой матрицы седловая точка:
S
2
1
S
2
2
S
2
3
S
2
4
S
1
1
0
-1 1
-1 -1
S
1
2
1
0
1
-1 -1
S
1
3
-1 -1 0
1
-1
S
1
4
1
1
-1 0
-1
1
1
1
1
Седловой точки нет. Это означает, что мы будем искать решение в сме-
шанных стратегиях.
0 −1 1 −1
1
0
1 −1
−1 −1 0
1
1
1 −1 0
1
0
1 −1
−1 −1 0
1
1
1 −1 0
0
1 −1
−1 0
1
1 −1 0
Ищем решение в смешанных стратегиях:
0
1
-1 p
1
-1 0
1
p
2
1
-1 0
p
3
q
1
q
2
q
3
| Page 5 |
5
3
∑
i=1
q
i
= 1 ,
3
∑
i=1
p
i
= 1.
Составим и решим следующие системы уравнений:
− p
2
+p
3
− V = 0
p
1
−p
3
− V = 0
−p
1
+ p
2
− V = 0
p
1
+ p
2
+p
3
= 1
;
+ q
2
−q
3
− V = 0
−q
1
+q
3
− V = 0
q
1
− q
2
− V = 0
q
1
+ q
2
+q
3
= 1
.
Или же в матричной форме:
0 −1 1 −1
1
0 −1 −1
−1 1
0 −1
1
1
1
0
∣
∣
∣
∣
∣
∣
∣
∣
0
0
0
1
;
0
1 −1 −1
−1 0
1 −1
1 −1 0 −1
1
1
1
0
∣
∣
∣
∣
∣
∣
∣
∣
0
0
0
1
Решаем первую систему по методу Крамера:
∆ =
∣
∣
∣
∣
∣
∣
∣
∣
0 −1 1 −1
1
0 −1 −1
−1 1
0 −1
1
1
1
0
∣
∣
∣
∣
∣
∣
∣
∣
= 9 ∆
p
1
=
∣
∣
∣
∣
∣
∣
∣
∣
0 −1 1 −1
0 0 −1 −1
0 1
0 −1
1 1
1
0
∣
∣
∣
∣
∣
∣
∣
∣
= 3
∆
p
2
=
∣
∣
∣
∣
∣
∣
∣
∣
0 0 1 −1
1 0 −1 −1
−1 0 0 −1
1 1 1
0
∣
∣
∣
∣
∣
∣
∣
∣
= 3 ∆
p
3
=
∣
∣
∣
∣
∣
∣
∣
∣
0 −1 0 −1
1
0 0 −1
−1 1 0 −1
1
1 1 0
∣
∣
∣
∣
∣
∣
∣
∣
= 3
∆
V
=
∣
∣
∣
∣
∣
∣
∣
∣
0 −1 1 0
1
0 −1 0
−1 1
0 0
1
1
1 1
∣
∣
∣
∣
∣
∣
∣
∣
= 0
Следовательно V = 0,p
1
=
1
3
,p
2
=
1
3
,p
3
=
1
3
Решим вторую систему:
∆ =
∣
∣
∣
∣
∣
∣
∣
∣
0
1 −1 −1
−1 0
1 −1
1 −1 0 −1
1
1
1
0
∣
∣
∣
∣
∣
∣
∣
∣
= 9 ∆
q
1
=
∣
∣
∣
∣
∣
∣
∣
∣
0 0 −1 −1
−1 0 1 −1
1 0 0 −1
1 1 1
0
∣
∣
∣
∣
∣
∣
∣
∣
= 3
∆
q
2
=
∣
∣
∣
∣
∣
∣
∣
∣
0
1 0 −1
−1 0 0 −1
1 −1 0 −1
1
1 1 0
∣
∣
∣
∣
∣
∣
∣
∣
= 3
| Page 6 |
6
∆
V
=
∣
∣
∣
∣
∣
∣
∣
∣
0
1 −1 0
−1 0
1 0
1 −1 0 0
1
1
1 1
∣
∣
∣
∣
∣
∣
∣
∣
= 0
Следовательно V = 0,q
1
=
1
3
,q
2
=
1
3
,q
3
=
1
3
Имеем: V=0, P
∗
= (0,
1
3
,
1
3
,
1
3
),Q
∗
=
(0,
1
3
,
1
3
,
1
3
). Теперь необходимо проверить, являются ля найденные страте-
гии оптимальными для игроков. Для этого необходимо проверить полу-
ченные результаты на сответствие неравенству: E(P,Q
∗
) ≤ E(P
∗
,Q
∗
) ≤
E(P
∗
,Q). Здесь P
∗
,Q
∗
- оптимальные смешанные стратегии, а E(P
∗
,Q
∗
) =
V - цена игры. Выполним проверку:
1. E(P
∗
,1) = 0 · 0 + 1 ·
1
3
− 1 ·
1
3
+ 1 ·
1
3
=
1
3
> V
2. E(P
∗
,2) = −1 · 0 + 0 ·
1
3
− 1 ·
1
3
+ 1 ·
1
3
= 0 = V
3. E(p
∗
,3) = 1 · 0 + 1 ·
1
3
+ 0 ·
1
3
+ −1 ·
1
3
= 0 = V
4. E(1,Q
∗
) = 0 · 0 − 1 ·
1
3
+ 1 ·
1
3
− 1 ·
1
3
= −
1
3
< V
5. E(2,Q
∗
) = 1 · 0 + 0 ·
1
3
+ 1 ·
1
3
− 1 ·
1
3
= 0 = V
6. E(3,Q
∗
) = 1 · 0 + 1 ·
1
3
− 1 ·
1
3
+ 0 ·
1
3
= 0 = V
Из описанных выше 2-х неравенств и 4-х равенств мы можем сделать
заключение о том, что построенные решения V = 0,q
1
=
1
3
,q
2
=
1
3
,q
3
=
1
3
Имеем: V=0, P
∗
= (0,
1
3
,
1
3
,
1
3
),Q
∗
= (0,
1
3
,
1
3
,
1
3
) являются верными.
3.
1
?
?
2
?
4
0
?
1. Заполним таблицу для случая, когда в получившейсся игре нет ни
| Page 7 |
7
одного равновесия Нэша:
1
7
4
2
3
4
0
5
В данном случае равновесие Нэша отсутствует.
2. Заполним таблицу так, чтобы было ровно одно равновесие Нэша:
1
7
4
2
3
4
0
1
Равновесие Нэша находится во втором столбце первой строки.
3. Заполним таблицу так, чтобы в полученной игре оказалось ровно две
ситуации по Нэшу:
1
1
3
2
5
4
0
1
| Page 8 |
8
В данной игре присутствует ровно два равновесия Нэша, одно из которых
- во втором столбце первой строки, а второе - в первом столбце первой
строки.
4. Теперь заполним таблицу так, чтобы в получившейся игре было ровно
три равновесия по Нэшу:
1
4
1
2
5
4
0
1
Равновесия Нэша - в первой строке, а также В первом столбце второй
строки.
5. Заполним таблицу так, чтобы в получившиейся игре было ровно 4 рав-
новесия Нэша:
1
4
1
2
0
4
0
2