Каждой задаче линейного программирования соответствует так называемая двойственная задача. В ней по сравнению с исходной задачей строки переходят в столбцы, неравенства меняют знак, вместо максимума ищется минимум (или наоборот, вместо минимума - максимум). Задача, двойственная к двойственной - эта сама исходная задача
Сравним исходную задачу (слева) и двойственную к ней (справа):
45 Х1 + 80 Х2 → max , 400 W1 + 450 W2 → min ,
5 Х1 + 20 Х2 ≤ 400 , 5 W1 + 10 W2 ≥ 45,
10 Х1 + 15 Х2 ≤ 450 , 20 W1 + 15 W2 ≥ 80,
Х1 ≥ 0 , W1 ≥ 0,
Х2 ≥ 0 . W2 ≥ 0.
Почему двойственная задача столь важна? Можно доказать, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной). При этом оптимальные значения W1 и W2 показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W1 и W2 называют "объективно обусловленными оценками" сырья и рабочей силы.
Из всех задач оптимизации задачи линейного программирования выделяются тем, что в них ограничения - системы линейных неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны.
