Оптимальные стратегии для игроков. Решение графических игр заданными платежными матрицами, страница 5


элементы которой удовлетворяют условию aij > 0, i = 1, 2, …, m, j = 1, 2, …, n эквивалентно решению следующей пары двойственных друг другу стандартных задач линейного программирования (задача ЛП имеет систему ограничений, состоит лишь из одних неравенств, называется стандартной).Найти:

                                           (1)

Найти:

                                               (2)

Точнее говоря, если– оптимальное решение задачи (1), а  – оптимальное решение задачи (2), то

 – цена игры с матрицей А,

– оптимальная стратегия игрока А, – оптимальная стратегия игрока В.

Наоборот, если  и – оптимальные стратегии соответственно игроков А и В и `g – цена игры, то – оптимальное решение задачи (1), а – оптимальное решение задачи (2).

Замечание. Матрица с любыми элементами может быть приведена к матрице с положительными элементами аффинным преобразованием

где l = 1, m > max{½aij½: aij £ 0}. При этом оптимальные стратегии оста-ются прежними Р = Р¢, q = q¢, а цена игры увеличивается на прибавленную константу m    .

Пример 25. Найти решение игры платежной матрицы

А =

Вj

Аi

В1

В2

В3

А1

1

4

4

А2

6

1

6

А3

5

5

2

используя симплекс –  метод.

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

2. Предварительно приведем матрицу А к матрице с положительными элементами, прибавив к каждому ее элементу число, большее максимального модуля отрицательных элементов матрицы А.

В качестве такого прибавляемого числа можно взять, например, число 3 (поскольку 3 > max{½– 2½, ½– 1½}). В результате получим матрицу

А*=

Вj

Аi

В1

В2

В3

А1

1

4

4

А2

6

1

6

А3

5

5

2

3. По теореме 17 решение игры с матрицей А* эквивалентно решению следующей пары стандартных взаимно двойственных задач линейного программирования:

– Задача Z: найти  min Z(Х) = x1 + x2+ x3, при условиях

x1 + 6x2 + 5x3 ³ 1,

4x1 + x2 + 5x3 ³ 1,

4x1 + 6x2 + 2x3 ³ 1,

xi ³ 0,  i = 1, 2, 3.

– Задача F: найти  max F(У) = y1 + y2+ y3, при условиях

y1 + 4y2 + 4y3 £ 1,

6y1 + y2 + 6y3 £ 1,

5y1 + 5y2 + 2y3 £ 1,

xi ³ 0,  i = 1, 2, 3.

4. Решим задачу Z, используя симплекс-метод, получаем оптимальное решение данной задачи  при .

5. По теореме 17 цена g¢ игры с матрицей А* будет равна

, а оптимальная стратегия игрока А

.

6. Цена игры `g для игры с матрицей А , а оптимальная стратегия игрока А останется без изменения .

Замечание. Для нахождения оптимальной стратегии  игрока В мы могли бы аналогичным способом решить двойственную задачу F линейного программирования. Но можно пойти другим путем.

7. Поскольку игрок А, применяя смешанную оптимальную стратегию , выбирает свои чистые стратегии, А1, А2, А3 являются активными. Тогда по утверждению 1) теоремы (об активных стратегиях) пусть`g – цена игры,  и – оптимальные стратегии соответственно игроков А и В.

Тогда: 1) для любой активной стратегии Аk (k Î {1, 2, …, m} игрока А выполняется равенство M(Ak, q0) = `g,

2) для любой активной стратеги В(ℓ Î {1, 2, …, n} игрока В выполняется равенство M(Р0, В) = `g,  M(Ai, q0) = `g,  i = 1, 2, 3.

Используя выражения для M(Ai, q0) по формулам , матрицу игры А и значение цены игры , запишем систему

M(Ai, q0) = `g, i = 1, 2, 3 в развернутом виде:

Сложим первое и третье уравнения, получим , откуда . Подставим найденное значение  в первое и второе уравнения:

  Откуда  

Вычитая из второго уравнения системы (*) ее первое уравнение, будем иметь , откуда .

Подставив это значение  во второе уравнение системы (*), найдем: .Таким образом, оптимальная смешанная стратегия игрока В .

Итак, найдено чистое решение игры с матрицей А:

, , .

2.  Сведение пары двойственных задач линейного программирования к матричной игре.