Решение матричной игры

Назначение сервиса. С помощью сервиса в онлайн режиме можно:
  • определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии, найти минимаксную стратегию игроков;
  • записать математическую модель пары двойственных задач линейного программирования, решить матричную игру методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Инструкция. Выберите размерность матрицы, нажмите Далее. В новом диалоговом окне выберите метод решения матричной игры. Пример заполнения. Результаты вычислений оформляются в отчете формата Word (см. пример оформления).
Размерность платежной матрицы x
Скопируйте из Excel или Word данные. Нажмите Далее.

Игра – это математическая модель реальной конфликтной ситуации. Конфликтная ситуация двух игроков называется парной игрой. Парную игру с нулевой суммой удобно исследовать, если она описана в виде матрицы. Такая игра называется матричной; матрица, составленная из чисел aij, называется платежной.
0-1-2
104
210
Математической моделью антагонистической игры является матричная игра с матрицей A, в которой ходы (стратегии) игрока A расположены по строкам, а ходы (стратегии) игрока B расположены по столбцам. В самой матрице записаны выигрыши игрока A при соответствующих ходах игроков A и B (отрицательный выигрыш – это проигрыш).

Алгоритм решения матричной игры

В таблице представлены варианты решения игры, заданной платежной матрицей А.
Наличие седловой точки Отсутствие седловой точки
Тип стратегии Смешанная стратегия
Метод решения Решение найдено 1. Через систему уравнений.
2. Графический метод.
3. Использование симплекс-метода.

Описание алгоритма:

  1. На основании анализа платёжной матрицы следует определить, существуют ли в ней доминируемые стратегии, и исключить их.
  2. Найти верхнюю и нижнюю цены игры и определить, имеет ли данная игра седловую точку (нижняя цена игры должна быть равна верхней цене игры).
  3. Если седловая точка существует, то оптимальными стратегиями игроков, являющимися решением игры, будут их чистые стратегии, соответствующие седловой точке. Цена игры равна верхней и нижней цены игры, которые равны между собой.
  4. Если игра не имеет седловой точки, то решение игры следует искать в смешанных стратегиях. Для определения оптимальных смешанных стратегий в играх m × n следует использовать симплекс-метод, предварительно переформулировав игровую задачу в задачу линейного программирования.

Представим алгоритм решения матричной игры графически.

Алгоритм решения матричной игры
Рисунок - Схема решения матричной игры.

Методы решения матричной игры в смешанных стратегиях

Итак, если седловая точка отсутствует, решение игры проводят в смешанных стратегиях и решают следующими методами:
  1. Решение игры через систему уравнений.
    Если задана квадратная матрица nxn (n=m), то вектор вероятностей можно найти, решив систему уравнений. Этот метод используется не всегда и применим только в отдельных случаях (если матрица 2x2, то решение игры получается практически всегда). Если в решении получаются отрицательные вероятности, то данную систему решают симплекс-методом.
  2. Решение игры графическим методом.
    В случаях, когда n=2 или m=2, матричную игру можно решить графически.
  3. Решение матричной игры симплекс-методом.
    В этом случае матричная игра сводится к задаче линейного программирования.
загрузка...