Исследование операций - часть 156
/p>
Отбрасывая столбцы B2, В4, В5, получаем игру 3×2 (таблица 27.3).
Наконец, в таблице 27.3 строка А3
дублирует А1, поэтому ее можно отбросить. Окончательно получим игру 2×2 (таблица 27.4).
|
Bj
Ai |
B1 |
B3 |
|
A1 A2 A3 |
4 3 4 |
2 6 2 |
Таблица 27.4
Ai |
B1 |
B3 |
|
A1 A2 |
4 3 |
2 6 |
Эту игру, как ни старайся, уже не упростишь. Приходится решать. Попутно заметим, что, отбрасывая лишние (дублирующие и заведомо невыгодные) стратегии в игре с седловой точкой, мы придем к решению в чистых стратегиях. Но лучше сразу проверить, не обладает ли игра седловой точкой — это проще, чем сравнивать почленно все строки и все столбцы.
В руководствах по теории игр обычно останавливаются на решении простейших игр 2×2, 2×п и т×2,
которое допускает геометрическую интерпретацию, но мы этого делать не будем — сразу возьмем «быка за рога» и покажем, как можно решить любую игру т×п.
Пусть имеется игра т×п без седловой точки с матрицей (аij) (см. таблицу 27.5).
Таблица 27.5
Bj |
B1 |
B2 |
… |
Bn |
|
A1 A2 … Am |
a11 a21 … am1 |
a12 a22 … am2 |
… … … … |
a1n a2n … amn |
Допустим, что все выигрыши аij положительны (этого всегда можно добиться, прибавляя ко всем членам матрицы достаточно большое число М; от этого цена игры увеличится на М, а решение
Мы хотим найти решение игры, т. е. две оптимальные смешанные стратегии
дающие каждой стороне максимально возможный для нее средний выигрыш (минимальный проигрыш).
Найдем сначала
