Сведение матричной игры к задаче линейного программирования

Предположим,что цена игры положительна (u > 0).Если это не так,то согласно свойству 6 всегда можно подобрать такое число с, прибавление которого ко всем элементам матрицы выигрышей даёт матрицу с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.

Итак,пусть дана матричная игра с матрицей А порядка mх n. Согласно свойству 7 оптимальные смешанные стратегии х = (х1,..., хm), y = (y1,..., yn) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям.

Разделим все уравнения и неравенства в (1) и (2) на u (это можно сделать,т.к. по предположению u > 0) и введём обозначения:

Тогда (1) и (2) перепишется в виде:

Поскольку первый игрок стремится найти такие значения хi и, следовательно, p_i, чтобы цена игрыu была максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений p_i , при которых

Поскольку второй игрок стремится найти такие значения y_j и,следовательно, q_j, чтобы цена игры u была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений q_j,, при которых

Формулы (3) и (4) выражают двойственные друг другу задачи линейного программирования (ЛП).

Решив эти задачи, получим значения p_{i ,} q_j и u.Тогда смешанные стратегии, т.е. xi и yjполучаются по формулам:

Пример. Найти решение игры, определяемой матрицей.

Решение. При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу

Составим теперь пару взаимно-двойственных задач:

Решим вторую из них

Из оптимальной симплекс-таблицы следует, что 7/2

(q1, q2, q3) = (0;1/2; 1),

а из соотношений двойственности следует, что

(p1, p2, p3) = (1/2; 1; 0).

Следовательно, цена игры с платёжной матрицей А1 равна

а игры с платёжной матрицей А:

При этом оптимальные стратегии игроков имеют вид: