А.И. Орлов       
Основы теории принятия решениий       
Учебное пособие. Москва, 2002.

4. Линейное программирование
    

Двойственная задача. Каждой задаче линейного программирования соответствует так называемая двойственная задача. В ней по сравнению с исходной задачей строки переходят в столбцы, неравенства меняют знак, вместо максимума ищется минимум (или наоборот, вместо минимума - максимум). Задача, двойственная к двойственной - эта сама исходная задача. Сравним исходную задачу (слева) и двойственную к ней (справа):

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 называют "объективно обусловленными оценками" сырья и рабочей силы.

Предыдущая страница | Оглавление | Следующая страница