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

(4) где , . (5)

По условию y1 + y2 + … +yn = 1. Разделим обе части этого равенства на v.

.

Оптимальная стратегия (y1, y2, ., yn) игрока В должна минимизировать величину v, следовательно, функция

(6)

должна принимать максимальное значение.

Получена задача линейного программирования: найти максимум целевой функции (6) при ограничениях (4), причем на переменные наложено условие неотрицательности (5).

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

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

.

a = max (2, 3,1) = 3, b = min (4, 5, 6,5) = 4, a ¹ b, .

Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий.

Для определения оптимальной стратегии игрока А имеем следующую задачу линейного программирования:

,

, .

Для нахождения оптимальной стратегии игрока В имеем следующую задачу линейного программирования:

,

, .

Оптимальные решения пары двойственных задач имеют вид

, , .

Учитывая соотношения между xi и ti, yj и sj, а также равенство

,

можно найти оптимальные стратегии игроков и цену игры:

(1/2, 1/2, 0), (3/4, 0, 0, 1/4), v=7/2.

Похожие статьи:

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

Сведение матричной игры к задаче линейного программирования
Теория игр находится в тесной связи с линейным программированием, так как каждая конечная игра двух лиц с нулевой суммой может быть представлена как задача линейного программирования и решена симплексным методом и, наоборот, каждая задача линейного программирования может быть представлена как конеч ...

Виды домашних заданий по математике в начальных классах
Существует очень много видов домашних работ.д.омашние задания могут быть общие, индивидуальные и групповые, когда группа учащихся выполняют какое-то задание, являющиеся частью общего классного задания. Например, групповое домашнее задание, при сборе числового материала одна группа узнает цены учебн ...