Игра двух лиц с нулевой суммой как задача линейного программирования

Рассмотрим платежную матрицу игры двух лиц, не имеющую седловых точек,

	B 1	B 2	…	Bn
A 1	U 11	U 12	…	U 1 n
A 2	U 21	U 22	…	U 2 n
…	…	…	…	…
Am	Um 1	Um 2	…	Umn

где платежи U_ij имеют смысл выигрышей игрока A.

Как известно, такая игра имеет решение в области смешанных стратегий. Пусть X=(x ₁ ,x ₂ ,…,x_m) – распределение вероятностей на стратегиях игрока A. Тогда согласно принципу гарантированного результата этот игрок будет выбирать такое поведение (распределение X ^*), которое максимизирует наименьший ожидаемый выигрыш

.

Обозначим через n минимальный ожидаемый выигрыш

.

Отсюда очевидно, что n не больше каждого ожидаемого выигрыша, и так как цель – максимальный выигрыш, то приходим к следующей эквивалентной задаче

L=n→ max

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

,

"х_i³0.

Это обычная линейная задача, оптимальное значение критерия которой L^*=n^* есть цена игры. Ее решение определяет оптимальное поведение игрока А.

Для игрока B линейная модель строится аналогично, но тот же критерий минимизируется, так как n уже имеет смысл максимального проигрыша, а ограничения на вероятности y_j соответствуют строкам платежной матрицы и записываются как неравенства “меньше или равно”.

Резюме

Рассмотренные модели задач объединяет одно свойство: все функции, входящие в модель (целевая и ограничения), являются линейными относительно искомых переменных. Нетрудно видеть, что задача описывается линейной моделью, если справедливы 3 свойства:

· аддитивности (сложение составляющих затрат, прибыли, времени и т.д.);

· пропорциональности (прибыль, расход пропорциональны количеству продкукции, услуг);

· непрерывности переменных.

Несмотря на сходство в главном, приведенные модели отличаются по виду экстремума (max или min) и/или по виду ограничений (равенства, неравенства, знаки неравенств). Возможны также задачи, в которых часть переменных не имеет ограничений по знаку (например, температура в градусах Цельсия, величина дебаланса, отклонение от заданного значения и т.п.). Чтобы абстрагироваться от этих несущественных отличий при использовании методов решения линейных задач, модели приводят к некоторому единому виду. Основными являются две формы представления задач ЛП, которые рассматриваются ниже.