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

    На этом шаге мы рассмотрим решение матричных игр методами линейного программирования.

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

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


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


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


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


    Отметим последнее условие, что цена игры v может быть как положительной, так и отрицательной. Оптимальные стратегии y1, y2, ...,yn игрока В определяются путем решения задачи


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



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

    На следующем шаге рассмотрим пример решения матричной игры методами линейного программирования.




Предыдущий шаг Содержание Следующий шаг