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

 

Рассмотрим задачу о производстве продукции из ограниченного количества сырья: производитель производит n видов продукции из m видов сырья в количестве b ₁, b ₂, …, b_m. Известны расходы каждого вида сырья на каждый вид продукции а_ij, i = 1,…, n; j = 1,…, m, а также прибыль от реализации продукции каждого вида с_j, j =1,…, m. Составить план выпуска продукции x ₁, …, x_n, при котором суммарная прибыль от реализации была бы наибольшей.

Математическая модель данной задачи имеет вид:

x_j ³ 0, j = 1,2… n.

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

Составим математическую модель задачи:

Целевая функция: выручка от продажи сырья (или затраты на покупку сырья) стремиться к минимуму.

Параметры управления: у ₁,…, у_m продажная цена товара. Тогда

а ₁₁ у ₁ – стоимость сырья первого вида, которое расходуется на одно изделие первого тип, а ₂₁ у ₂ – стоимость сырья второго вида, которое расходуется на одно изделие первого типа и т.д. тогда

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

.

Рассуждая аналогично для остальных видов продукции, получим систему ограничений

Целевая функция имеет функциональное выражение вида:

.

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

Составим двойственную задачу для задачи из предыдущего параграфа:

.

Система ограничений двойственной задачи имеет транспонированную матрицу по сравнению с прямой задачей. В качестве столбца свободных членов используются коэффициенты целевой функции, а в качестве коэффициентов целевой функции – столбец свободных членов. Знаки неравенств меняются, целевая функция стремится к минимуму. Обратим внимание, что для построения симметричной задачи все неравенства должны быть однотипные, если же в системе ограничений есть противоположное неравенство, то необходимо его умножить на –1.

F=500 у ₁+380 у ₂ à min.

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

Построим опорную прямую:

500 y ₁ + 380 y ₂ = 0 и укажем направление градиента целевой функции

grad F =(500;380).

 

 

На рис. 2.7 отмечена область допустимых неотрицательных решений системы ограничений обратной задачи. Точкой «входа» прямой L в ОДР является точка А – точка пересечения первой и второй прямых. Найдем ее координаты.

 

Решим систему методом Крамера:

 

у ₁= 6 д.е.; у ₂ = 6 д.е. F = 500×6+380×6 = 5280 д.е.

 

Итак, наименьшая цена, за которую первый продавец может продать сырье первого типа – 6 д.е.; сырье второго типа – 6 д.е. При этом он получит 5280 д.е.

Обратим внимание, что при решении прямой задачи в § 2.3 значение целевой функции было такое же. Это является иллюстрацией первой теоремы двойственности:

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

По решению двойственной задачи можно восстановить решение исходной задачи. Для этого используют вторую теорему двойственности:

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

Подставим решение (6; 6) в систему ограничений, так как обе координаты отличны от нуля, то в исходной задаче оба ограничения выполняются как равенства

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

Þ

 

Решим систему методом Крамера:

 

Получили то же оптимальное решение, что и в предыдущем параграфе симплексным методом.