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

Теория решения матричных игр возникла ранее линейного программирования и долгое время развивалась независимо от него. Математическое соответствие между матричными играми и линейным программированием было установлено одним из его основоположников Дж. Б. Данцигом в 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.

Дата добавления: 2014-01-03