Тесты Верно (В) или неверно (Н)? Если в игре 2xn icon

Тесты Верно (В) или неверно (Н)? Если в игре 2xn




Скачати 193.89 Kb.
НазваТесты Верно (В) или неверно (Н)? Если в игре 2xn
Дата11.09.2012
Розмір193.89 Kb.
ТипТесты

Тесты

Верно (В) или неверно (Н)?

1. Если в игре 2xn нет оптимального решения в чистых стратегиях, то оптимальное решение в смешанных стратегиях содержит две активные стратегии.

2. В игре mx2 число активных стратегий в оптимальной стратегии каждого из игроков может быть равно или единице, или двум.

3. Оптимальное решение в игре двух лиц с нулевой суммой всегда является седловой точкой независимо от того, смешанные или чистые стратегии используют игроки.

4. Если максимальная цена матричной игры отрицательна, то конечный результат игры будет убыточным для игрока А.

5. Прибавление одного и того же числа ко всем элементам платежной матрицы не влияет на цену игры.

6. Умножение всех элементов платежной матрицы на одно и тоже пеложительное число не изменяет оптимальных стратегий игрокрв.

7. Цена матричной игры изменится, если из платежной матрицы исключить строки и столбцы, соответствующие дублирующим и доминирующим стратегиям.


^ Ответы: (1 - В; 2 - В; 3 - В; 4 - В; 5 - Н; 6 - В; 7 - Н).


Задачи:

Решить следующие матричные игры:


1.

8

1

7

3

0

-7


2.

-4

-8

-7

-3

-5

-9

-8

-4


3.

5

1

3

7

8

2


4.

6

13

19

25

19

15

16

18

19

25

19

18

16

12

13

15


5.

3

3

4

5

5

4

3

3




6.

0.4

0.5

1

1

0.5

0.3


7.

1

2

3

4

3

0


8.

11

8

12

1

-7

-1

-8

2


9.

10

-4

6

14

0

0

10

4

4

12


10.

2

-6

10

-14

18

-4

8

-12

16

-20


11.

3

7

-1

11

-5

6

2

10

-4

14


12.

9

-5

7

1

-3

-10

4

-8

-6

2


13.

24

0

18

21

9

18

9

3


14.

7

9

0

6

0

10


15.

-1

8

7

6

3

1

9

0

1

2

5

7


16.

1

3

5

7

9

11



17.

2

10

4

8

6

6

8

4

10

2


18.

-3

-9

-15

-21

-27

-33



19.

1

3

5

7

9

11


20.

-1

5

-3

1

0

-3

-3

0

1

-3

5

-1



21.

11

3

9

7

10

5

7

11

8

9



22.

2

2

3

-1

4

3

2

6


23.

4

8

4

6

6

4

-2

12


24.

1

3

1

4

2

1

-1

5


25.

2

4

-2

8

3

6

5

-5


26.

1

2

5

6

-7

9

-4

-3

2

1


27.

5

9

5

7

7

5

-1

13


28.

3

8

12

6

10

14


29.

0

8

2

6

4

4

6

2

8

0



30.

-2

10

-6

2

0

-6

-6

0

2

-6

10

-2



^ 2.8. Решение игр mхn. Эквивалентные задачи линейного программирования

Пусть имеется матричная игра mxn без седловой точки с матрицей выигрышей ||aij||. Допустим, что все выигрыши aij положительны (этого всегда можно добиться, прибавляя ко всем элементам матрицы достаточно большое число С; от этого, как уже отмечалось, цена игры увеличится на М, а оптимальное решение SA и SB не изменится).

Если все aij положительны, то и цена игры v при оптимальной стратегии тоже положительна.

В соответствии с основной теоремой матричных игр, если платежная матрица не имеет седловой точки, то имеется пара оптимальных смешанных стратегий SA=||p1, p2, ..., pm|| и SB=||q1, q2, ..., qn||, применение которой характеризует игроком получение цены игры v.

Найдем вначале SA. Для этого предположим, что игрок В отказался от своей оптимальной смешанной стратегии SB и применяет только чистые стратегии. В каждом из этих случаев выигрыш игрока А будет не меньше, чем v:

(2.25)


Разделив левую и правую часть каждого из неравенств (2.25) на положительную величину v и введя обозначения

(2.26)

запишем неравенства (2.25) в следующем виде:

(2.27)

где x1, x2, ... xm - неотрицательные переменные.

В силу того, что

p1+p2+...+pm=1,

переменные x1, x2, ... xm удовлетворяют условию

(2.28)

Учитывая,что игрок А стремится максимизировать v, получаем следующую задачу линейного программирования: найти неотрицательные значения переменных x1, x2, ... xm такие, чтобы они удовлетворяли линейным ограничениям - неравенствам (2.27) и обращали в минимум линейную функцию этих переменных:

min L(x)=x1+x2+ ... +xm (2.29)

Из решения задачи линейного программирования находим цену игры v и оптимальную стратегию Sa по формулам:

(2.30)

, (2.31)

Аналогично находим оптимальную стратегию SВ игрока В. Предположим,что игрок А отказался от своей оптимальной стратегии SA и применяет только чистые стратегии. Тогда проигрыш игрока В в каждом из этих случаев будет не больше, чем v:

(2.32)

Разделив левую и правую части каждого их неравенств (32) на положительную величину v и, введя обозначения:

(2.33)

запишем неравенство (2.32) в следующем виде:

(2.34)

где y1, y2, ..., yn - неотрицательные переменные.

В силу того,что

q1+q2+...+qn=1,

переменные y1, y2, ..., yn удовлетворяют условию

(2.35)

Учитывая, что игрок В стремится минимизировать положительную цену v (свой проигрыш), получаем задачу линейного программирования: найти неотрицательные значения переменных y1, y2, ..., yn такие, чтобы они удовлетворяли линейным ограничениям (2.34) и обращали в максимум линейную функцию этих переменных:

max L(y)=y1+y2+ ... +ym (2.36)

Эта задача является двойственной по отношению к задаче, представленной условиями (2.27) и (2.29).

Оптимальная стратегия SB=||q1, q2, ..., qn|| игрока В определяется из решения двойственной задачи линейного программирования по формулам:

, (2.37)

Таким образом, оптимальные стратегии SA=||p1, p2, ..., pm|| и SB=||q1, q2, ..., qn|| матричной игры mxn с платежной матрицей ||aij|| могут быть найдены путем решения пары двойственных задач линейного программирования.


Исходная задача

Двойственная задача

,

;



,

;




При этом

, (2.38)

.


Пример. Найти решение и цену матричной игры, платежная матрица которой имеет вид


Bj


Ai


B1


B2


B3

A1

1

2

3

A2

3

1

1

A3

1

3

1



Решение

1. Так как a=1 не равно b=3, то игра не имеет седловой точки.

2. В данной игре нет дублирующих и доминируемых стратегий.

3. Решаем игру путем решения пары двойственных задач линейного программирования.

Математические модели пары двойственных задач линейного программирования будут выглядеть следующим образом:

Исходная задача

Найти неотрицательные переменные х123, минимизирующие функцию

min L (x)=х1+х2+х3, приограничениях:

х1+3х2+х3³1;

1+х2+3х3³1;

1+х2+х3³1;

xi³0,

Двойственная задача

Найти неотрицательные переменные у123, максимизирующие функцию

max L (x)=y1+y2+y3, при ограничениях:

y1+2y2+3y3£1;

3y1+y2+y3£1;

y1+3y2+y3£1;

yj³0,



Данные задачи решаются, например, симплекс - методом. Поскольку в двойственной задаче ограничения имеют вид “£“, то эту задачу решать проще (не нужно вводить искусственных переменных). Оптимальное решение исходной задачи можно будет непосредственно получить из данных симплекс - таблицы для оптимального решения двойственной задачи.

Начальная симплекс - таблица двойственной задачи имеет вид


БП

у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







1




0




у1

1







0




0




у6

0







0




1




L

0







0




0







БП

у1

у2

у3

у4

у5

у6

Решение

у4

0

0




1










у1

1

0




0










у2

0

1




0










L

0


0




0












И, наконец, получаем симплекс - таблицу, которая соответствует оптимальному решению двойственной задачи:


БП

у1

у2

у3

у4

у5

у6

Решение

у4

0

0


1













у1

1

0


0













у2

0

1


0













L

0


0


0














Оптимальное решение двойственной задачи линейного программирования следующее:

у1=; у2=; у3=; max L (y)=

Находим оптимальную смешанную стратегию игрока В в соответствии с формулами (2.37) и (2.38):

;

;

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

Оптимальное решение исходной задачи находим, используя двойственные оценки, из симплекс - таблицы для оптимального решения двойственной задачи:

x1=; x2=; x3=; max L (x)=

Отсюда определим вероятности применения своих активных стратегий игроком А:

;

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

Таким образом, решение игры mxn эквивалентно решению задачи линейного программирования. Нужно заметить, что и наоборот, - для любой задачи линейного программирования может быть построена эквивалентная ей задача теории матричных игр. Эта связь задач тнории матричных игр с задачами линейного программирования оказывается полезной не только для теории игр, но и для линейного программирования. Дело в том, что существуют приближенные численные методы решения матричных игр, которые при большой размерности задачи могут оказаться проще, чем симплекс - метод.

Схожі:

Тесты Верно (В) или неверно (Н)? Если в игре 2xn iconТесты по дисциплине «Исследование операций» Заменяя в линейной модели знаки ограничений \
Условие пропорциональности модели лп не выполняется, если удельный вклад в целевую функцию некоторой переменной зависит от значения...
Тесты Верно (В) или неверно (Н)? Если в игре 2xn iconТесты по дисциплине «Исследование операций» Заменяя в линейной модели знаки ограничений \
Условие пропорциональности модели лп не выполняется, если удельный вклад в целевую функцию некоторой переменной зависит от значения...
Тесты Верно (В) или неверно (Н)? Если в игре 2xn iconБесконечные антагонистические игры
Но как и во всякой антагонистической игре, в бесконечной антагонистической игре принципом оптимального поведения игроков остается...
Тесты Верно (В) или неверно (Н)? Если в игре 2xn iconБесконечные антогонистические игры
Но как и во всякой антогонистической игре, в бесконечной антогонистической игре принципом оптимального поведения игроков остается...
Тесты Верно (В) или неверно (Н)? Если в игре 2xn icon4. бесконечные антагонистические игры общие сведения
Но, как и во всякой антагонистической игре, в бесконечной антагонистической игре принципом оптимального поведения игроков остается...
Тесты Верно (В) или неверно (Н)? Если в игре 2xn icon4. бесконечные антагонистические игры общие сведения
Но, как и во всякой антагонистической игре, в бесконечной антагонистической игре принципом оптимального поведения игроков остается...
Тесты Верно (В) или неверно (Н)? Если в игре 2xn icon4. Бесконечные антогонистические игры Общие сведения
Но как и во всякой антогонистической игре, в бесконечной антогонистической игре принципом оптимального поведения игроков остается...
Тесты Верно (В) или неверно (Н)? Если в игре 2xn icon2 Чистые и смешанные стратегии
Если в игре каждый из противников применяет только одну и ту же стратегию, то про саму игру в этом случае говорят, что она происходит...
Тесты Верно (В) или неверно (Н)? Если в игре 2xn icon2 Чистые и смешанные стратегии
Если в игре каждый из противников применяет только одну и ту же стратегию, то про саму игру в этом случае говорят, что она происходит...
Тесты Верно (В) или неверно (Н)? Если в игре 2xn iconТекстовый редактор microsoft word
Большинство необходимых команд и инструментов легко обнаружить на панелях инструментов Стандартная и Форматирование или в Меню Microsoft...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи