Исследование операций. Линейное, динамическое программирование


Исследование операций - часть 156


/p>

 

Отбрасывая столбцы B2, В4, В5, получаем игру 3×2 (таблица 27.3).

Наконец, в таблице 27.3 строка А3

дублирует А1, поэтому ее можно отбросить. Окончательно получим игру 2×2 (таблица 27.4).

 

Таблица 27.3

             Bj

 

Ai

 

B1

 

B3

A1

A2

A3

4

3

4

2

6

2

 

Таблица 27.4

             Bj

 

Ai

 

B1

 

B3

A1

A2

4

3

2

6

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

В руководствах по теории игр обычно останавливаются на решении простейших игр 2×2, 2×п и т×2,

которое допускает геометрическую интерпретацию, но мы этого делать не будем — сразу возьмем «быка за рога» и покажем, как можно решить любую игру т×п.

Пусть имеется игра т×п без седловой точки с матрицей (аij) (см. таблицу 27.5).

Таблица 27.5

      Ai

 

Bj

 

B1

 

B2

 

 

Bn

A1

A2

Am

a11

a21

am1

a12

a22

am2

a1n

a2n

amn

 

Допустим, что все выигрыши аij положительны (этого всегда можно добиться, прибавляя ко всем членам матрицы достаточно большое число М; от этого цена игры увеличится на М, а решение

 не изменится). Если все aij положительны, то конечно, и цена игры, т. е. средний выигрыш при оптимальной стратегии, тоже положителен: v > 0.

Мы хотим найти решение игры, т. е. две оптимальные смешанные стратегии

 

      (27.1)

 

дающие каждой стороне максимально возможный для нее средний выигрыш (минимальный проигрыш).

Найдем сначала

 Мы знаем, что если один из игроков (в данном случае это А) применяет свою оптимальную стратегию, то другой (В) не может улучшить свое положение, отступая от своей.


Начало  Назад  Вперед



Книжный магазин