Исследование операций

Автор: Пользователь скрыл имя, 08 Января 2015 в 19:25, курсовая работа

Краткое описание

Сетевая игра: имеются n точек. Некоторые пары этих точек со-
еденены стрелками. Оба игрока одновременно выбирают по точке.
Если они выбирают одну и ту же точку, или разные, но не соединн-
ные между собой стрелкой, то платж равен нулю. Если они выби-
рают связанную пару точек, то игрок, выбравший острие стрелки,
получает от своего противника +1 балл. Решить сетевую игру.

Скачать в ZIP (214.34 Кб) Сколько стоит заказать работу?

Файлы: 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

Информация о работе Исследование операций