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

Теория игр находится в тесной связи с линейным программированием, так как любую конечную иг­ру двух лиц с нулевой суммой можно представить в виде задачи линейного программи­рования и наоборот. Дж. Данциг [2] отмечает, что когда в 1947 году создатель теории игр Дж. фон Нейман впервые ознакомился с симплекс-методом, он сразу установил эту взаимосвязь и обратил особое внимание на концепцию двойственности в линейном про­граммировании. Этот раздел иллюстрирует решение матричных игр методами линейного программирования.

Оптимальные значения вероятностей xi, i = 1, 2,..., m, игрока А могут быть определе­ны путем решения следующей максиминной задачи.

,

Чтобы сформулировать эту задачу в виде задачи линейного программирования, положим

Отсюда вытекает, что

Следовательно, задача игрока A может быть записана в виде.

Максимизировать z = v

при ограничениях

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

Оптимальные стратегии у1,у2,…, yn игрока В определяются путем решения задачи

,

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

Максимизировать w = v

при ограничениях

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