Приведение матричной игры к ЗЛП

Теория решения матричных игр возникла ранее линейного программирования и долгое время развивалась независимо от него. Математическое соответствие между матричными играми и линейным программированием было установлено одним из его основоположников Дж. Б. Данцигом в 1951 г. Он показал, что матричная игра может быть сведена к паре двойственных задач линейного программирования. Решение одной из них дает оптимальную стратегию игрока А, решение другой – оптимальную стратегию игрока В.

Задача линейного программирования (ЗЛП) состоит в максимизации (минимизации) линейной функции, называемой целевой, при линейных ограничениях. Поиск оптимальных стратегий игрока А (максимизация его среднего выигрыша) и игрокаВ(минимизация его среднего проигрыша) составляют ЗЛП.

Платежную прямоугольную матрицу игры размерностью m ´ n можно представить в следующем виде: .

Оптимальные смешанные стратегии (максиминная и минимаксная) характеризуются векторами вероятностей:

для игрока Аp^* = (p₁^*, p₂^*, …, p_m^*);

для игрока В q^* = (q₁^*, q₂^*, …, q_n^*).

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

Для всех n чистых стратегий игрока В получается система неравенств: где ; . (1)

В теории игр доказывается, что оптимальные смешанные стратегии в матричной игре ½a_ij½_{m ´ n} с ценой v остаются оптимальными при линейном преобразовании элементов матрицы½ba_ij +c½_{m ´ n}, но цена игры становится bv+c. Отсюда следует, что элементы исходной матрицы всегда можно сделать положительными, добавив ко всем элементам и цене игры подходящую величину с.

Систему неравенств (1), элементы которой приведены к положительным значениям, можно преобразовать, разделив обе части каждого неравенства на положительную величину v и обозначая p₁^* / v = х₁, p₂^* / v = х₂, …, p_m^* / v = х_m.

После преобразования получается:

(2)

из следует , где .

Игрок А максимизирует свой средний выигрыш при максимуме цены игры v и минимуме 1 / v, то есть минимизируемой целевой функцией будет

f(x)= . (3)

Минимум целевой функции ищется при ограничениях, вытекающих из системы неравенств (2) и неотрицательности искомых значений хi.

ЗЛП для определения оптимальной смешанной стратегии игрока В является двойственной по отношению к рассмотренной ЗЛП для игрока А.

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

(4)

где и .

Система (4) преобразуется делением неравенств на положительную величину v, и при обозначениях q₁*/v = y₁, q₂*/v = y₂, …, q_n*/v = y_n получается:

(5)

, , где .

Игрок В стремится к минимизации своего среднего проигрыша, что достигается при минимуме цены игры v и, следовательно, максимуме обратной величины 1/v, поэтому в качестве максимизируемой целевой функции берется

h(у)= . (6)

Максимум целевой функции ищется при ограничениях, вытекающих из системы неравенств (5) и неотрицательности искомых значенийу_j.