Решение игр (aij)mxn с помощью линейного программирования

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

Для первого игрока математическая модель задачи запи­сывается в виде

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

Математическую модель можно упростить, для этого разделив все (п + 1) ограничений на v. Это возможно при v ≠ 0. При v = 0 рекомендуется прибавить любое положительное число ко всем элементам платежной матрицы, что гарантирует положи­тельность значения модифицированной игры.

Действительное значение игры получается вычитанием из модифицированного значения этого положительного числа. Если v < 0, то надо сме­нить знаки неравенств. Полагая v > 0, систему ограничений можно записать так:

Положим Х_i = x_i/v. Так как v → max, то 1 / v → min.

Получим задачу линейного программирования вида

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

 

Для второго игрока математическая модель записывается в виде

 

 

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

где S () = 1 / v, Y_j = у_j / v.

Задача второго игрока является двойственной по отноше­нию к задаче первого игрока. Можно найти решение одного из игроков, а затем по теоремам двойственности — решение другого.

Применение матричных игр в маркетинговых исследованиях

Торговая фирма разработала несколько вариантов плана продажи товаров на предстоящей ярмарке с учетом меняющей­ся конъюнктуры рынка и спроса покупателей. Получающиеся от их возможных сочетаний показатели дохода представлены в табл. 31.10.

Определить оптимальный план продажи товаров.

Решение. Обозначим: вероятность применения торговой фирмой стратегии П ₁ — x ₁, стратегии П ₂ —x ₂, П ₃ — х ₃; ве­роятность использования стратегии К ₁ — у ₁, стратегии К ₂ — y ₂, К ₃ — у ₃.

Для первого игрока (торговой фирмы) математическая мо­дель задачи имеет вид

при ограничениях, где x_i = Х_iv.

Для второго игрока (конъюнктуры рынка и спроса покупа­телей) математическая модель задачи имеет вид

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

 

Найдем оптимальное решение задачи для второго игрока симплексным методом. При этом последняя таблица имеет вид табл. 31.11.

Из таблицы следует, что _опт = (1/14, 11/196, 5/49), S ()_max = 45/196.

Цена игры v = 1 / S(Y) = 196/45.

Так как у_i = Y_iv, то y ₁ = 14/45, у ₂ = 11/45, у ₃= 20/45.

Оптимальная стратегия второго игрока:

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

Таким образом, торговая фирма на ярмарке должна при­держиваться стратегии _опт = (20/45, 11/45, 14/45), при этом она получит доход не менее v = 196/45 ден. ед.