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

 

Цель работы: Изучение теоретических и практических приёмов составления игровых моделей для задач линейного программирования.

 

Если игровая модель всегда сводится к паре моделей задач линейного программирования, то обратное утверждение неверно. Рассмотрим перевод задачи линейного программирования к игровой модели.

В общем случае целевая функция z=∑ c_i * x_i

Заменой переменных (c_i * x_i) / z= p_i целевая функция приводится к виду 1=∑ p_i, это основное условие перехода к игровой модели. Так как p_i ≥ 0, то должно быть выполнено требование (c_i * x_i) / z ≥ 0 и z ≠ 0 ввиду невозможности деления на нуль. При x_i ≥ 0, что обычно ставится одним из условий задач линейного программирования, основным требованием является sign(c_i) * sign(z) ≥ 0. Если условие не выполняется, то можно построить неполную модель игры, принимая отрицательные p_i равными нулю и тем самым полагая равными нулю соответствующие исходные переменные. Неполная модель дает верхнюю оценку целевой функции. Далее будем считать, что требование неотрицательности коэффициентов в целевой функции выполнено. Рассмотрим отдельно задачи на min и max.

Пусть целевая функция min z=∑ c_i * x_i

В ограничения вида

подставим x_i =(p_i * z) / c_i, левые и правые части ограничений разделим на z и нормируем ограничения поделив каждое на b_i (по условию b_i положительно определённые коэффициенты). Ограничения с b_j =0 из системы исключаем в дополнительные условия, которым должно удовлетворять конечное решение. Очевидно, что нормировка правой части ограничений может быть выполнена и в начале. В результате получим игровую модель

, ∑ p_i =1.

Учитывая, что в исходной задаче z → min, то η → max, так что здесь реализуется максиминный критерий для игрока А.

Аналогично для линейной модели на max z=∑ c_i * x_i с ограничениями вида

подстановка и нормировка приводят к следующей игровой модели

, ∑ q_i =1.

Учитывая, что в исходной задаче z → max, то η → min, так что здесь реализуется минимаксный критерий для игрока B.

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

После решения игры (например, методом итераций) определяем решение исходной задачи линейного программирования с помощью восстановления цепочки замены переменных.

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

найти max z= 2 x₁ +3 x₂

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

, .

Сравнивая вид неравенств в ограничениях с игровыми моделями выше, видим, что модель игры нужно строить как минимаксную для игрока B.

Разделим целевую функцию на z и положим ее равной единице, т.е.

1=q₁ + q₂, откуда x₁=(1/2) q₁ z, x₂=(1/3) q₂ z и подстановка в ограничения после нормировки и деления на z даёт следующую игровую модель

, соответствующая матрица игры A=

На рисунке 9.1 приведено графическое решение игровой модели.

 

Рис 9.1. Графическое решение задачи

 

Экстремальная точка определяется первым и вторым уравнением. С учетом условия нормировки вероятностей имеем три уравнения для трех переменных. Их решение дает q₁ = 4/19 q₂ = 15/19, ν = 3/38, обратная подстановка приводит к исходным данным: x₁ = 4/3, x₂ = 10/3, z = 38/3, что совпадает с ранее найденным решением.

Заметим, что результирующая матрица игры состоит всего из двух первых строк.

Рассмотрим теперь двойственную задачу. Модель для нее:

min z=6y₁+8y₂+y₃+2y₄

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

, .

После нормировки

,

т.е. имеем maxmin и модель для игрока A.

Из z y₁=1/6p₁z, y₂=1/8p₂z, y₃=p₃z, y₄=1/2p₄z и подстановка в ограничения после деления на z дает следующие соотношения

.

Соответствующая матрица игры совпадает с ранее найденной.

 

Модель с положительными и отрицательными коэффициентами в целевой функции

 

Оценка решения

 

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

Рассмотрим модель с положительными и отрицательными коэффициентами в целевой функции.

Пусть задана линейная модель в виде:

Min z = 5x₁-2x₃,

ограничения , .

По виду ограничений соответствующая игровая модель - minmax для игрока B, поэтому вид экстремума нужно изменить. Так как min z = max(-z), то получим целевую функцию в виде max z = -5x₁+2x₃. Первый коэффициент отрицательный, поэтому адекватную линейной модели игровую модель построить нельзя. Полагая q₁=0, и, следовательно, x₁=0, получим q₂=0, q₄=0, x₂=0,x₄=0 соответствующая игровая модель

и матрица игры A= .

Минимальный проигрыш соответствует нижнему элементу матрицы, решение получено в чистых стратегиях: q₃ = 1, ν = 1/10, max(-z)=10, x₁ =0, x₃=1/2 q₃ * 10 = 5, z = -10.

Подставим найденное решение в исходную систему ограничений:

-x2 + 2*5 ≤ 2, 5 +x4 ≤ 5. Отсюда x₄ =0, x₂ = 8.

Решив задачу симплекс-методом, получим X = (0, 8, 5, 0, 0, 0, 7), min z = -10.

В общем случае нужно помнить, что мы получаем оценку решения, но, заметьте, насколько прост метод.