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

Решение матричной игры со смешанным расширением – это определение оптимальных смешанных стратегий, то есть нахождение таких значений вероятностей выбора чистых стратегий для обоих игроков, при которых они достигают наибольшего выигрыша.

Для матричной игры, платёжная матрица которой показана на рис. 1, . Определим такие значения вероятностей выбора стратегий для игрока 1 и для игрока 2 , при которых игроки достигали бы своего максимально гарантированного выигрыша.

Рис. 1

Если один из игроков придерживается своей оптимальной стратегии, то, по условию задачи, его выигрыш не может быть меньше цены игры v. Поэтому данная задача может быть представлена для игроков в виде следующих систем линейных неравенств:

Для первого игрока:

Чтобы определить значение v, разделим обе части каждого из уравнений на v. Введем обозначения и запишем системы неравенств в следующей форме

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

.

Для игрока 2 необходимо найти минимальную цену игры (v), следовательно величина 1/v должна стремиться к максимуму, т.е.

Все переменные в данных системах линейных неравенств должны быть неотрицательными, а также цена игры v не была бы отрицательной. Цена игры вычисляется на основе коэффициентов выигрышей платёжной матрицы. Поэтому, для гарантии неотрицательности всех переменных, необходимо, чтобы все коэффициенты матрицы были неотрицательными. Этого можно добиться, прибавив перед началом решения задачи к каждому коэффициенту матрицы число , соответствующее модулю наименьшего отрицательного коэффициента матрицы. Тогда в ходе решения задачи будет определена не цена игры, а величина .

Для решения задач линейного программирования используется симплекс-метод. [1, 5].

В результате решения определяются значения целевых функций (для обоих игроков эти значения совпадают), а также значения переменных x_i и y_j .

Величина v* определяется по формуле: v* = 1/z

Значения вероятностей выбора стратегий определяются: для игрока 1: : для игрока 2: .

Для определения цены игры v из величины v* необходимо вычесть число K.

Дата добавления: 2015-07-26; просмотров: 159; Нарушение авторских прав

Мы поможем в написании ваших работ!