Файл: Теория_игр_УП_ЭК_ЭлРесурс.pdf

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 31.07.2021

Просмотров: 711

Скачиваний: 2

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
background image

 

36

Другой

 

вариант

 

игры

 

2x2

 

получается

если

 

использовать

 

стратегии

 

А

2

 

и

 

А

6

В

 

этом

 

случае

 

платежная

 

матрица

 

имеет

 

вид

 

B

j

 

 
A

i

 

 

B

1

 

 

B

2

 

A

2

 4 2 

A

6

 1,5 3 

 

Тогда

 

7

3

2

1

3

4

1

3

2

1

2

1

1

p

7

4

2

p

;  

7

2

2

1

3

4

2

3

2

1

1

q

7

5

2

q

;     

7

18

2

1

3

4

1

2

3

4

2

1

2

1

v

Ответ

7

4

,

0

,

0

,

0

,

7

3

,

0

A

S

;   

7

5

,

7

2

B

S

;  

7

18

v

Естественно

что

 

цена

 

игры

 

для

 

обоих

 

вариантов

 

одинакова

В

 

заключение

 

наметим

 

общую

 

схему

 

решения

 

матричных

 

игр

 

2xn

 

и

 

mx2

1. 

Определяется

 

наличие

 

седловой

 

точки

т

.

е

возможность

 

решения

 

игры

 

в

 

чистых

 

стратегиях

Если

 

нижняя

 

цена

 

игры

 

 

не

 

равна

 

верхней

 

цене

 

игры

 

то

 

осуществляется

 

поиск

 

решения

 

в

 

смешанных

 

стратегиях

2. 

Производится

 

упрощение

 

матричной

 

игры

 

путем

 

исключения

 

дублирующих

 

и

 

доминируемых

 

стратегий

Если

 

упрощенная

 

игра

 

имеет

 

размерность

 

не

 

2x2

то

 

переходим

 

к

 

этапу

 3. 

3. 

Строится

 

графическое

 

изображение

 

игры

 

и

 

определяется

 

две

 

активные

 

стратегии

 

игрока

имевшего

 

в

 

исходной

 

задаче

 

число

 

стратегий

 

больше

 

двух

4. 

Решается

 

матричная

 

игра

 

2x2

 

ТЕСТЫ

 

(

В

 – 

Верно

Н

 – 

Неверно

1. 

Если

 

в

 

игре

 

2xn

 

нет

 

оптимального

 

решения

 

в

 

чистых

 

стратегиях

то

 

оптимальное

 

решение

 

в

 

смешанных

 

стратегиях

 

содержит

 

две

 

активные

 

стратегии

 

у

 

каждого

 

из

 

игроков

2. 

В

 

игре

 

mx2

 

число

 

активных

 

стратегий

 

в

 

оптимальной

 

стратегии

 

каждого

 

из

 

игроков

 

может

 

быть

 

равно

 

или

 

единице

или

 

двум

3. 

Оптимальное

 

решение

 

в

 

игре

 

двух

 

лиц

 

с

 

нулевой

 

суммой

 

всегда

 

является

 

устойчивым

 

независимо

 

от

 

того

смешанные

 

или

 

чистые

 

стратегии

 

используют

 

игроки

4. 

Если

 

оптимальная

 

цена

 

матричной

 

игры

 

отрицательна

то

 

конечный

 

результат

 

игры

 

будет

 

убыточным

 

для

 

игрока

 

А

5. 

Прибавление

 

одного

 

и

 

того

 

же

 

числа

 

ко

 

всем

 

элементам

 

платежной

 

матрицы

 

не

 

влияет

 

на

 

цену

 

игры

6. 

Умножение

 

всех

 

элементов

 

платежной

 

матрицы

 

на

 

одно

 

и

 

тоже

 

положительное

 

число

 

не

 

изменяет

 

оптимальных

 

стратегий

 

игроков


background image

 

37

7. 

Цена

 

матричной

 

игры

 

изменится

если

 

из

 

платежной

 

матрицы

 

исключить

 

строки

 

и

 

столбцы

соответствующие

 

дублирующим

 

и

 

доминируемым

 

стратегиям

8. 

Любая

 

матричная

 

игра

 

2xn

 

или

 

mx2

 

может

 

быть

 

сведена

 

к

 

игре

 2

х

2. 

(

Ответы

1-

В

; 2-

В

; 3-

В

; 4-

В

; 5-

Н

; 6-

В

; 7-

Н

; 8-

В

). 

 

ЗАДАЧИ

 

 

Решить

 

следующие

 

матричные

 

игры

1. 

8 1  7  2. -4 -8 -7 -3 3.

5  1  3  

  3 0  7  

-5 -9 -8 -4   7  8  2  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. 6 13 19 25 19 15 16 18 5.

3  3  4  5 

  19 25 19 18 16 12 13 15   5  4  3  3 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

6. 0,

0,5 

1 7. 1 2 3 

8. 11 8 12 1 

  1 

0,5 

0,3 

  4 3 0    -7 -1 -8 2 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

9. 10 -4  6  14  0 

10.

2  -6 10 -14 18  

 

0 10  4  4  12  

 

-4  8 -12 16 -20  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

11. 3  7  -1 11 -5 

12.

9 -5 7  1  -3  

  6 2 10 -4 14 

 

 -10 

4 -8 -6 2  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

13. 

24 0 18 21 

   

14.

7 9 0 

 

   

 9 

18 

9 3 

    6 

10   

  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

15. 

-1 

8 7 6 3 1 

   

    

 9 

0 1 2 5 7 

   

    

 

 

 

 

 

 

 

 

 

 

 

 

 

 

16. 1  3  17.  2  10  18.

-3  -9  19

1 3 

   

  5 7 

 

4 8   -15 

-21 

  5 7 

   

 

9  11  

6  6 

  -27 -33  

9  11  

 

 

 

 

 

 

 

 

 

 

 

 

 

    

  10 

2  

   

    

20. -1  5  21

11 3  22. 2 2  3  -1  23.  4 

  -3 1 

  9 7    4 3 2  6  

4  6 

  0 

-3 

 10 5          

6  4 

  -3 

  7 11          

-2  12 

 1 

-3 

 8 

9  

 

 

      

 5 

-1 

    

 

    

   

 

 

 

 

 

 

 

 

 

 

 

 

 

 


background image

 

38

24. 1  3  25

2 4  -2 8 26

.

1 2 27. 5  9 

 1 

4  3 6 5 -5 

 5 6    5  7 

 2 

       -7 9   7  5 

 -1 5            -4 -3    -1  13 

    

          2  1    

 

 

 

   

 

 

 

 

 

 

 

 

 

 

28. 3  8 12 29

0 8 

30

.

-2 10    

 

 

6 10 14   2  6     -6  2  

 

 

   

 

  4 4 

  0 

-6 

    

   

 

  6 2 

  

-6 

    

   

 

  8 0 

  1 1 

    

 

 

   

 

 

 

 

 

-6   

 

 

   

 

    

  

10 

-2 

    

 

2.8. 

Решение

 

игр

 m

х

n. 

Эквивалентные

 

задачи

 

линейного

 

программирования

 

Пусть

 

имеется

 

матричная

 

игра

 

mxn

 

без

 

седловой

 

точки

 

с

 

матрицей

 

выигрышей

 ||a

ij

||. 

Допустим

что

 

все

 

выигрыши

  a

ij

 

положительны

  (

этого

 

всегда

 

можно

 

добиться

прибавляя

 

ко

 

всем

 

элементам

 

матрицы

 

достаточно

 

большое

 

число

 

С

от

 

этого

как

 

уже

 

отмечалось

цена

 

игры

 

увеличится

 

на

 

C, 

а

 

оптимальные

 

решения

 S

A

 

и

 S

B

 

не

 

изменятся

). 

Если

 

все

  aij 

положительны

то

 

и

 

цена

 

игры

 

 

при

 

оптимальной

 

стратегии

 

тоже

 

положительна

т

.

к

В

 

соответствии

 

с

 

основной

 

теоремой

 

матричных

 

игр

если

 

платежная

 

матрица

 

не

 

имеет

 

седловой

 

точки

то

 

имеется

 

пара

 

оптимальных

 

смешанных

 

стратегий

  S

A

=||p

1

, p

2

, ..., p

m

|| 

и

  S

B

=||q

1

, q

2

, ..., q

n

||, 

применение

 

которой

 

обеспечивает

 

игрокам

 

получение

 

цены

 

игры

 

Найдем

 

вначале

 S

A

Для

 

этого

 

предположим

что

 

игрок

 

В

 

отказался

 

от

 

своей

 

оптимальной

 

смешанной

 

стратегии

  S

B

 

и

 

применяет

 

только

 

чистые

 

стратегии

В

 

каждом

 

из

 

этих

 

случаев

 

выигрыш

 

игрока

 

А

 

будет

 

не

 

меньше

чем

 

:                            



.

...

...

..........

..........

..........

,

...

,

...

2

2

1

1

2

2

22

1

12

1

2

21

1

11

v

p

a

p

a

p

a

v

p

a

p

a

p

a

v

p

a

p

a

p

a

m

mn

n

n

m

m

m

m

 (2.25) 

Разделив

 

левую

 

и

 

правую

 

часть

 

каждого

 

из

 

неравенств

 (2.25) 

на

 

положительную

 

величину

  v 

и

 

введя

 

обозначения

,

...,

;

;

2

2

1

1

v

p

x

v

p

x

v

p

x

m

m

 (2.26) 

запишем

 

неравенства

 (2.25) 

в

 

следующем

 

виде



1

...

...

..........

..........

..........

1

...

1

...

2

2

1

1

2

2

22

1

12

1

2

21

1

11

m

mn

n

n

m

m

m

m

x

a

x

a

x

a

x

a

x

a

x

a

x

a

x

a

x

a

, (2.27) 


background image

 

39

где

 x

1

, x

2

, ... x

m

 – 

неотрицательные

 

переменные

В

 

силу

 

того

что

 

p

1

+p

2

+...+p

m

=1, 

переменные

  x

1

, x

2

, ... x

m

  

удовлетворяют

 

условию

 

x

x

x

v

m

1

2

1

  

...

. (2.28) 

Учитывая

что

 

игрок

 

А

 

стремится

 

максимизировать

 

получаем

 

следующую

 

задачу

 

линейного

 

программирования

найти

 

неотрицательные

 

значения

 

переменных

  x

1

, x

2

, ... x

m

 

такие

чтобы

 

они

 

удовлетворяли

 

линейным

 

ограничениям

 – 

неравенствам

 (2.27) 

и

 

обращали

 

в

 

минимум

 

линейную

 

функцию

 

этих

 

переменных

min 

L

(x)=x

1

+x

2

+ ... +x

m

. (2.29) 

Из

 

решения

 

задачи

 

линейного

 

программирования

 

находим

 

цену

 

игры

 

 

и

 

оптимальную

 

стратегию

 Sa 

по

 

формулам

m

i

i

x

v

1

1

  (2.30) ,          

v

x

x

x

p

i

n

i

i

i

i

1

i

m

1,

.      (2.31) 

Аналогично

 

находим

 

оптимальную

 

стратегию

  S

В

 

игрока

 

В

Предположим

что

 

игрок

 

А

 

отказался

 

от

 

своей

 

оптимальной

 

стратегии

 S

A

 

и

 

применяет

 

только

 

чистые

 

стратегии

Тогда

 

проигрыш

 

игрока

 

В

 

в

 

каждом

 

из

 

этих

 

случаев

 

будет

 

не

 

больше

чем

 



.

...

...

..........

..........

..........

,

...

,

...

2

2

1

1

2

2

22

1

21

1

2

12

1

11

v

q

a

q

a

q

a

v

q

a

q

a

q

a

v

q

a

q

a

q

a

n

mn

m

m

n

n

n

n

. (2.32) 

Разделив

 

левую

 

и

 

правую

 

части

 

каждого

 

их

 

неравенств

 (2.32) 

на

 

положительную

 

величину

 

 

и

 

введя

 

обозначения

v

q

y

v

q

y

v

q

y

n

n

...,

;

;

2

2

1

1

, (2.33) 

запишем

 

неравенство

 (2.32) 

в

 

следующем

 

виде



.

1

...

...

..........

..........

..........

,

1

...

,

1

...

2

2

1

1

2

2

22

1

21

1

2

12

1

11

n

mn

m

m

n

n

n

n

y

a

y

a

y

a

y

a

y

a

y

a

y

a

y

a

y

a

, (2.34) 

где

 y

1

, y

2

, ..., y

n

 – 

неотрицательные

 

переменные

В

 

силу

 

того

что

 q

1

+q

2

+...+q

n

=1, 

переменные

 y

1

, y

2

, ..., y

n

 

удовлетворяют

 

условию

                            

v

y

y

y

n

1

...

2

1

. (2.35) 

Учитывая

что

 

игрок

 

В

 

стремится

 

минимизировать

 

положительную

 

цену

 

v

  (

свой

 

проигрыш

), 

получаем

 

задачу

 

линейного

 

программирования

найти

 

неотрицательные

 

значения

 

переменных

 y

1

, y

2

, ..., y

n

 

такие

чтобы

 

они

 

удовлетворяли

 

линейным

 

ограничениям

 (2.34) 

и

 

обращали

 

в

 

максимум

 

линейную

 

функцию

 

этих

 

переменных

max 

L

(y)=y

1

+y

2

+ ... +y

m

. (2.36) 


background image

 

40

Эта

 

задача

 

является

 

двойственной

 

по

 

отношению

 

к

 

задаче

представленной

 

условиями

 (2.27) 

и

 (2.29). 

Оптимальная

 

стратегия

  S

B

=||q

1

, q

2

, ..., q

n

|| 

игрока

 

В

 

определяется

 

из

 

решения

 

двойственной

 

задачи

 

линейного

 

программирования

 

по

 

формулам

v

y

y

y

q

j

n

j

j

j

j

1

,  

n

j

,

1

. (2.37) 

Таким

 

образом

оптимальные

 

стратегии

 S

A

=||p

1

, p

2

, ..., p

m

|| 

и

 S

B

=||q

1

, q

2

..., q

n

|| 

матричной

 

игры

 

mxn

 

с

 

платежной

 

матрицей

 ||a

ij

|| 

могут

 

быть

 

найдены

 

путем

 

решения

 

пары

 

двойственных

 

задач

 

линейного

 

программирования

Прямая

 (

исходная

задача

 

Двойственная

 

задача

 

 

m

i

i

x

x

L

1

min

m

i

i

ij

x

a

1

1

n

j

,

1

0

i

x

m

i

,

1

n

j

j

y

y

L

1

)

(

max

n

j

j

ij

y

a

1

1

m

i

,

1

0

j

y

n

i

,

1

 

При

 

этом

     

)

(

max

1

)

(

min

1

1

1

1

1

y

L

x

L

y

x

v

n

j

j

m

i

i

, (2.38) 

n

j

v

y

q

m

i

v

x

p

j

j

i

i

,

1

;

;

,

1

;

Пример

.

 

Найти

 

решение

 

и

 

цену

 

матричной

 

игры

платежная

 

матрица

 

которой

 

имеет

 

вид

 

B

j

 

 
A

i

 

 

B

1

 

 

B

2

 

 

B

3

 

A

1

 1 2  3 

A

2

 3 1  1 

A

3

 1 3  1 

Решение

1.  

Так

 

как

 

=1 

не

 

равно

 

=3, 

то

 

игра

 

не

 

имеет

 

седловой

 

точки

.

 

2. 

В

 

данной

 

игре

 

нет

 

дублирующих

 

и

 

доминируемых

 

стратегий

3. 

Решаем

 

игру

 

путем

 

решения

 

пары

 

двойственных

 

задач

 

линейного

 

программирования

 

Математические

 

модели

 

пары

 

двойственных

 

задач

 

линейного

 

программирования

 

будут

 

выглядеть

 

следующим

 

образом