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

При решении матричной игры в смешанных стратегиях можно использовать метод сведения игры к задаче линейного программирования.

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

Задача 1. (для игрока А)

В результате решения задачи 1 находят её оптимальный план и значение задачи . Затем определяют цену игры v и компоненты смешанной стратегии по формулам

.

Задача 2. (для игрока В)

Пусть – оптимальный план задачи 2 и − её значение. Тогда цена игры v и компоненты смешанной стратегии определяются равенствами

.

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

Пример 6.6. Предприятие может выпускать три вида продукции (А₁, А₂, А₃), получая при этом прибыль, зависящую от спроса. Спрос, в свою очередь, может принимать одно из четырёх состояний П₁, П₂, П₃ и П₄. Прибыль, которую получит предприятие при выпуске продукции А_i и состоянии П_j ( ), составит u_ij ден. ед.

Предполагая состояние спроса полностью неопределённым, определить оптимальные пропорции в выпускаемой продукции, гарантируя при этом среднюю величину прибыли при любом состоянии спроса.

Числовые данные задачи представлены матрицей :

.

Решение. Используя игровой подход, примем за игрока А – руководство предприятия, принимающее решение о пропорциях в выпуске продукции трёх видов. Чистыми стратегиями игрока являются стратегии А_i – выпуск продукции только одного вида А_i ( ). Совокупность обстоятельств, формирующих спрос на продукцию, примем за второго игрока – природу П. Согласно условию природа может реализовать одно из своих состояний П₁, П₂, П₃ и П₄.

Итак, задача имеет характер статистической игры. Элементы а_ij платёжной матрицы характеризуют прибыль предприятия при различных комбинациях (А_i,П_j) ( ).

 

Таблица 68

Пj	П1	П2	П3	П4
Ai
A1
А2
A3

 

Доминируемых строк платёжная матрица не имеет. Доминируемые столбцы (при их наличии) матрицы статистической игры не исключаются, так как природа может реализовать любое из своих состояний. Таким образом, упрощение платёжной матрицы невозможно.

Гарантируемая средняя величина прибыли предприятия (игрока А) будет обеспечена при выборе им максиминной стратегии.

Находим нижнюю и верхнюю чистые цены игры:

Так как , то игра не имеет решения в чистых стратегиях. Найдём её решение в смешанных стратегиях.

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

 

(6.1)

 

Представим эту задачу в канонической форме

 

(6.2)

 

Двойственная к этой задаче имеет вид:

 

(6.3)

 

Установим следующее взаимооднозначное соответствие между переменными задач (6.2) и (6.3)

 

 

Решим задачу (6.3) симплексным методом. Исходная симплексная таблица имеет вид:

 

Таблица 69

СП					bi
БП
y5
y6
y7
g	–1	–1	–1	–1

В качестве разрешающего столбца в таблице 69 примем третий столбец. По минимальному симплексному отношению определяем разрешающим элементом число 6 в разрешающем столбце. С помощью симплексных преобразований переходим к таблице 70.

Таблица 70

СП БП					bi
y5
y6
y3
g

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

В качестве разрешающего выбираем первый столбец, а в качестве разрешающего элемента в нём число 4. После симплексных преобразований получим таблицу 71.

Таблица 71

СП БП					bi
y1
y6
y3
g

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

Таблица 72

СП БП					bi
y1
y6
y3
g

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

Используя соответствие между переменными задачи 2.2 и 2.3 по симплексной таблице 2.4, находим оптимальный план задачи 9.2:

При этом . Цена игры .

Находим компоненты оптимальной смешанной стратегии игрока А.

Полученное решение означает, что средняя величина прибыли при любом состоянии спроса будет гарантирована, если в общем объёме продукции, выпускаемой предприятием, продукция вида А₁ составит 30%, А₂ – 30% и А₃ – 40%.

Лекция 8

Не нашли, что искали? Воспользуйтесь поиском по сайту: