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

41

Прямая

 (

исходная

) 

задача

: 

Найти

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

переменные

х

1

,

х

2

,

х

3

, 

минимизирующие

функцию

min 

L

 (

x

)=

х

1

+

х

2

+

х

3

, 

при

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

: 

х

1

+3

х

2

+

х

3



1; 

2

х

1

+

х

2

+3

х

3



1; 

3

х

1

+

х

2

+

х

3



1; 

x

i



0, 

3

,

1



i

. 

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

задача

: 

Найти

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

переменные

у

1

,

у

2

,

у

3

, 

максимизирующие

функцию

max 

L

 (

x

)=y

1

+y

2

+y

3

, 

при

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

: 

y

1

+2y

2

+3y

3



1; 

3y

1

+y

2

+y

3



1; 

y

1

+3y

2

+y

3



1; 

y

j



0, 

3

,

1



j

. 

Данные

задачи

решаются

, 

например

, 

симплекс

 – 

методом

. 

Поскольку

в

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

задаче

ограничения

имеют

вид

  “



“, 

то

эту

задачу

решать

проще

  (

не

нужно

вводить

искусственные

переменные

). 

Оптимальное

решение

исходной

задачи

можно

будет

непосредственно

получить

из

данных

симплекс

 – 

таблицы

для

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

решения

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

задачи

.  

Начальная

симплекс

 – 

таблица

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

задачи

имеет

вид

БП

у

1

у

2

у

3

у

4

у

5

у

6

Решен

ие

у

4

 1 2 3 1 0 0  1 

у

5

3 1 1 0 1 0  1 

у

6

 1 3 1 0 0 1  1 

L

-1 -1 -1  0  0  0 

0 

ведущий

столбец

Последующие

симплекс

-

таблицы

приведены

ниже

: 

БП

у

1

у

2

у

3

у

4

у

5

у

6

Решение

у

4

 0 

3

2

1

3

2

2

1 

3

1



0 

3

2

у

1

 1 

3

1

3

1

0 

3

1

0 

3

1

у

6

 0 

3

2

2

3

2

0 

3

1



1 

3

2

L

0 

3

2



3

2



0 

3

1

0 

3

1

ведущий

столбец

БП

у

1

у

2

у

3

у

4

у

5

у

6

Решение

у

4

 0  0 

4

9

1 

8

1



8

5



4

1

у

1

 1  0 

4

1

0 

8

3

8

1



4

1

у

2

 0  1 

4

1

0 

8

1



8

3

4

1

L

0 0 

2

1



0 

4

1

4

1

2

1

ведущий

столбец

И

, 

наконец

, 

получаем

симплекс

-

таблицу

, 

которая

соответствует

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

решению

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

задачи

: 

ведущая

строка

ведущая

строка

ведущая

строка

42

БП

у

1

у

2

у

3

у

4

у

5

у

6

Решение

у

3

 0 0 1 

9

4

18

1



18

5



9

1

у

1

 1 0 0 

9

1



18

7

18

1



9

2

у

2

 0 1 0 

9

1



9

1



9

4



9

2

L

0 0 0 

9

2

9

2

9

1

9

5

Оптимальное

решение

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

задачи

линейного

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

следующее

: 

у

1

=

2
9

; 

у

2

=

2
9

; 

у

3

=

1
9

;   max L (y)= 

9

5

. 

Находим

оптимальную

смешанную

стратегию

игрока

В

в

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

с

формулами

 (2.37) 

и

 (2.38): 

5

9

1

1

9

1

9

2

5

2

3

1















j

j

y

v

;  

5

1

5

9

9

1

;

5

2

5

9

9

2

;

5

2

5

9

9

2

3

3

2

2

1

1































v

y

q

v

y

q

v

y

q

. 

Следовательно

, 

5

1

;

5

2

;

5

2



B

S

. 

Оптимальное

решение

исходной

задачи

находим

, 

используя

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

оценки

, 

из

симплекс

-

таблицы

для

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

решения

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

задачи

: 

коэффициент

при

начальной

базисной

переменной

в

оптимальном

уравнении

прямой

задачи

равен

разности

между

правой

и

левой

частями

ограничения

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

задачи

, 

ассоциированного

с

данной

начальной

переменной

. 

Получаем

  x

1

=

9

2

;  x

2

=

9

2

; x

3

=

9

1

;   max L (x)= 

9

5

. 

Отсюда

определим

вероятности

применения

своих

стратегий

игроком

А

:  

5

1

5

9

9

1

;

5

2

5

9

9

2

;

5

2

5

9

9

2

3

3

2

2

1

1































v

x

p

v

x

p

v

x

p

. 

Следовательно

: 

5

1

;

5

2

;

5

2



A

S

. 

Таким

образом

, 

решение

игры

mxn

сводится

к

решению

задачи

линейного

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

. 

Нужно

заметить

, 

что

и

наоборот

 – 

для

любой

задачи

линейного

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

может

быть

построена

эквивалентная

ей

задача

теории

матричных

игр

. 

Эта

связь

задач

теории

матричных

игр

с

задачами

линейного

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

оказывается

полезной

не

только

для

теории

игр

, 

но

и

для

линейного

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

. 

Дело

в

том

, 

что

существуют

приближенные

численные

методы

решения

матричных

игр

, 

которые

при

большой

размерности

задачи

могут

оказаться

проще

, 

чем

симплекс

 – 

метод

.

43

ТЕСТЫ

(

В

 – 

Верно

, 

Н

 – 

Неверно

) 

1.

Если

все

элементы

платежной

матрицы

в

матричной

игре

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

, 

то

и

цена

игры

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

. 

2.

Любую

матричную

игру

можно

свести

к

паре

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

задач

линейного

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

. 

3.

В

прямой

задаче

линейного

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

, 

к

которой

сводится

матричная

игра

, 

целевая

функция

подлежит

максимизации

. 

4.

В

обратной

задаче

линейного

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

, 

к

которой

сводится

матричная

игра

, 

ограничения

получаются

со

знаком

 «



». 

5.

Цена

матричной

игры

, 

получаемая

из

решения

прямой

и

обратной

задач

может

быть

различна

. 

(

Ответы

:

 1 - 

В

; 2 - 

В

; 3 - 

Н

; 4 - 

В

, 5 - 

Н

). 

ЗАДАЧИ

Решить

следующие

матричные

игры

: 

1. 2 4 6 2. -7 4 2 3. -5 6 4   

  6 2 2   0 2 1    2 4 3   

 2 6 2  6 -5 

-1

 8 -3 1  

4. 1 3 2 5. 2 1 0 6. 4 6 1   

  3 1 3  1 2 1  4 4 1  

 2 3 1  0 1 2  1 1 6  

7. -4 -6 -1 8.  -2 -5  2  9. 5  7  1   

 -4 

-4 

-1 

 -1 

1 

-5   5 5 1 

 -1 

-1 

-6 

 -2 

-1 

-2   2 2 6 

1

0. 

2 6 4  1

1.

3 6 9  1

2.

0 1 2  

 6 

2 

6 

 9 

3 

3 

 2 

0 

0 

 4 

6 

2 

 3 

9 

3 

 0 

2 

1 

2.9. 

Приближенный

метод

решения

матричных

игр

 mxn 

Рассмотрим

приближенный

метод

решения

матричных

игр

 – 

метод

Брауна

-

Робинсон

  (

метод

итераций

). 

Идея

его

заключается

в

следующем

. 

Разыгрывается

эксперимент

, 

в

котором

игроки

А

и

В

поочередно

применяют

друг

против

друга

свои

чистые

стратегии

. 

Каждый

из

игроков

стремится

увеличить

свой

выигрыш

, 

предполагая

, 

что

будущее

будет

походить

на

прошлое

; 

при

этом

считается

, 

что

ни

один

из

них

не

знает

своей

оптимальной

стратегии

. 

Такой

принцип

приводит

к

некоторой

последовательности

партий

игры

, 

для

каждой

из

которых

можно

подсчитать

приближенные

оптимальные

стратегии

каждого

из

игроков

, 

а

также

верхнюю

и

нижнюю

цены

игры

. 

44

Вместо

того

, 

чтобы

вычислять

каждый

раз

средний

выигрыш

, 

можно

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

суммарным

за

все

предыдущие

ходы

выигрышем

и

выбирать

ту

свою

стратегию

, 

при

которой

этот

накопленный

выигрыш

максимален

. 

Доказано

, 

что

такой

метод

сходится

: 

при

увеличении

числа

партий

средний

выигрыш

на

одну

партию

будет

стремиться

к

цене

игры

, 

а

частоты

применения

стратегий

 – 

к

их

вероятностям

в

оптимальных

смешанных

стратегиях

игроков

. 

Объясним

этот

метод

на

примере

игры

3x3

, 

платежная

матрица

которой

приведена

ниже

. 

Игра

начинается

с

произвольно

выбранной

стратегии

игрока

А

, – 

например

стратегии

А

1

  (

выбранные

стратегии

обозначаются

звездочкой

). 

Платежные

элементы

этой

строки

переписываются

под

платежной

матрицей

. 

Игрок

В

, 

предполагая

, 

что

будущее

будет

походить

на

прошлое

, 

выберет

стратегию

В

1

, 

при

которой

его

проигрыш

минимален

. 

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

этой

стратегии

проигрыш

обозначен

звездочкой

. 

Платежные

элементы

стратегии

В

1

переписываются

справа

от

платежной

матрицы

. 

Игрок

А

, 

также

предполагая

, 

что

будущее

будет

походить

на

прошлое

, 

выбирает

стратегию

А

2

  (

наибольшее

число

обозначено

звездочкой

). 

Платежные

элементы

, 

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

стратегии

А

2

, 

прибавляются

поочередно

к

элементам

предыдущей

строки

, 

записанной

под

матрицей

. 

Далее

выбирается

наименьший

элемент

суммарной

строки

. 

Ему

соответствует

стратегия

В

2

. 

Тогда

к

столбцу

, 

записанному

справа

от

платежной

матрицы

, 

поочередно

прибавляются

платежные

элементы

стратегии

В

2

. 

Этот

процесс

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

до

тех

пор

, 

пока

разрыв

между

нижней

и

верхней

оценками

игры

станет

небольшим

. 

Если

при

выборе

стратегий

на

некотором

шаге

есть

несколько

альтернатив

, 

то

выбирается

любая

из

равноценных

стратегий

. 

В

рассматриваемом

примере

сделано

 20 

шагов

. 

За

эти

двадцать

шагов

игрок

А

применил

свою

первую

стратегию

  (

количество

звездочек

в

суммарных

выигрышах

, 

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

первой

стратегии

) 7 

раз

; 

вторую

– 8 

раз

; 

третью

 – 5 

раз

. 

Игрок

В

применил

стратегию

В

1

восемь

раз

; 

вторую

– 8 

раз

; 

третью

 – 4 

раза

. 

Следовательно

, 

приближенные

оценки

оптимальных

стратегий

, 

полученные

за

 20 

итераций

, 

равны

: 

20

4

;

20

8

;

20

8

;

20

5

;

20

8

;

20

7





B

A

S

S

. 

Эти

оценки

не

так

уж

сильно

отличаются

от

точного

решения

данной

матричной

игры

, 

которое

равно

2

.

0

;

4

.

0

;

4

.

0

;

2

.

0

;

4

.

0

;

4

.

0





B

A

S

S

. 

 B

i 

A

i

B

1

B

2

B

3

  1 2 3 4 5 6 7 8 9 10 

A

1

 1  2  3 * 1 3 5 8* 9* 10 12 14 

17* 20*

A

2

 3  1  1  3* 4* 5 6 9 12* 13* 

14 15 16 

A

3

  1  3  1   1  4 7* 8  9 10 13 16* 17 18 

   11 12 13 14 15 16 17 18 19 20 

1  1*  2  3   21* 22 24* 25 27 29 31 32 33 36*
2  4  3*  4    19 22* 23 26* 27* 28  29  32 35* 36 
3  7  4*  5   19 20 23 24 27 30* 33* 34* 35 36 

45

4 8 7 6* 

5 

9* 9 9            

6 10* 11 12  
7 13 12* 13  
8 16 13* 14  
9 17 16 15*  

10 18 13 18*  
11 19* 20  21   
12 20* 22  24   
13 23 23* 25  
14 24* 25  28   
15 27 26* 29  
16 30 27* 30  
17 31 30* 31  

18 32*  33  32   
19 33*  36  33   
20 36  37 34*  

Приближенную

цену

игры

определяют

как

среднеарифметическое

между

нижней

оценкой

игры



, 

равной

минимально

накопленному

выигрышу



min



игрока

А

, 

деленному

на

число

шагов

 k, 

и

верхней

оценкой

игры



, 

равной

максимальному

суммарному

проигрышу



max



игрока

В

, 

деленному

на

 k: 

k















2

2

max

min











. 

В

рассматриваемом

примере

82

.

1

40

73

20

2

37

36













. 

Точная

цена

игры

v 

= 1,8. 

Разрыв

между



и



отражает

неточность

оценок

относительно

оптимальных

смешанных

стратегий

. 

В

примере

05

.

0

20

36

20

37













составляет

 2,8% 

от

цены

игры

v

=1,8. 

Увеличивая

число

итераций

 k, 

можно

найти

еще

более

точные

оценки

оптимальных

смешанных

стратегий

. 

Преимуществом

итерационного

метода

решения

матричных

игр

является

то

, 

что

объем

вычислений

с

увеличением

размерности

игры

mxn

растет

существенно

медленнее

, 

чем

в

методах

линейного

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

 (

в

частности

, 

в

симплекс

 – 

методе

). 

2.10. 

Качественная

оценка

элементов

платежной

матрицы

Очевидной

трудностью

при

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

теории

игр

является

задание

элементов

платежной

матрицы

с

требуемой

точностью

. 

Вместе

с

тем

эту

задачу

не

нужно

и

переоценивать

. 

Использование

,