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


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


/p>

 

трех столбцах дается накопленный выигрыш за k партий соответственно при стратегиях А1, А2, А3

игрока А (получается прибавлением элементов столбца Вj к тому, что было строкой выше). Из этих значений в таблице 27.7 «надчеркнуто» максимальное; оно определяет выбор стратегии игрока А в следующей партии (строкой ниже). В последних трех столбцах таблицы 27.7 даны:

 — нижняя оценка цены игры, равная минимальному накопленному выигрышу, деленному на числа партий k;

*
 — верхняя оценка цены игры, равная максимальному накопленному выигрышу, деленному на k;

v* — среднее арифметическое между ними (оно служит лучше, чем нижняя и верхняя, приближенной оценкой цены игры).

Как видно, величина v* незначительно колеблется около цены игры v = 5 (цена исходной игры была 0, но мы прибавили к элементам матрицы по 5). Подсчитаем по таблице 27.7 частоты

 стратегий игроков. Получим:

 

 

что не так уж сильно отличается от вероятностей p1, p2, p3, q1, q2, q3, равных, как мы указывали раньше, для первой, второй и третьей стратегий соответственно 1/4 = 0,25, 1/2 = 0,50, 1/4 = 0,25. Такие сравнительно хорошие приближения мы получили уже при 15 итерациях — это обнадеживает! К сожалению, дальше процесс приближений будет идти не так резво. Сходимость метода Брауна — Робинсон, как показывает опыт, очень медленная, Существуют способы, позволяющие как бы «подхлестнуть» еле плетущийся процесс, но мы на них останавливаться не будем.

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

 

* * *

Таким образом, читатель получил некоторое представление о теории антагонистических игр и о методах решения матричных игр.

Скажем несколько критических слов по поводу этой теории и ее практической значимости. В свое время, когда теория игр еще только появилась, на нее возлагались большие надежды в смысле выбора решений для конфликтных ситуаций.


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



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