Для решения прямой задачи линейного программирования, можно воспользоваться решением двойственной задачи. Под двойственной задачей понимается вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Интерес в определении оптимального решения прямой задачи с помощью решения двойственной к ней задачи вызван тем, что вычисления при решении двойственной задачи менее сложные. Прибегая к такому решению, покупатель может найти такой набор цен ресурсов, имеющихся у производителей, при котором затраты на приобретение этих ресурсов будут минимальны, а производитель получит при этом прибыль не менее той, какую бы он получил при производстве и сбыте готовой продукции. Рассмотрим на примере.
Нам дана функция: L= -2*X1+4*X2+14*X3+2*X4→ min
при этом ограничения: -2*X1-X2+ X3+2*X4=6-X1+2*X2+4*X3-5*X4=30XJ ≥0
Решим исходную задачу, решая двойственную. Учтем несимметричный характер пары двойственных задач (II тип).
Введем матрицы С=-2 4 14 2, В=630, А=-2-11 2 -124 -5
Тогда двойственная задача примет вид:
S= 6*y1+30*y2→max
Система ограничений:-2*y1-y2≤ -2-y1+2*y2≤4y1+4*y2≤142*y1-5*y2≤2
Тогда график функции будет выглядеть так:
Область допустимых решений — ABCD.
Мы получаем следующий вывод: максимальное значение S равно 102, при этом максимальный план равен Y=23.
Вернемся к исходной задаче.
Теперь система ограничений исходной задачи примет вид:
-2*X1-X2+ X3+2*X4=6-X1+2*X2+4*X3-5*X4=30X1=0X4=0
В итоге, мы получаем: минимальное значение L равно 102, при этом минимальный план равен X=0170.
Теория линейного программирования позволяет не только получать оптимальные планы с пoмощью эффективных вычислительных процедур, нo и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.