2015-03-20
970
Каждой задаче линейного программирования можно сопоставить определенным образом с ней связанную другую задачу, которая называется двойственной по отношению к первой. Первоначальная задача называется исходной. Вместе взятые задачи образуют пару взаимно – двойственных задач. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Совместное рассмотрение таких пар двойственных задач оказывается весьма эффективным средством теоретического исследования проблем линейного программирования и построения различных вычислительных методов. Кроме того, рассмотрение двойственных задач играет большую роль при экономическом анализе результатов расчета.
Правила составления двойственной задачи:
1) если целевая функция исходной задачи формулируется на максимум, то целевая функция двойственной задачи – на минимум (и наоборот), при этом в двойственной задаче на максимум все неравенства в ограничениях имеют вид ≤, а в задаче на минимум – вид ≥;
|
|
|
2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица 
в двойственной задаче получаются друг из друга транспонированием;
3) число переменных в двойственной задаче равно числу ограничений исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной;
4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи – коэффициенты при неизвестных в целевой функции исходной;
5) каждому ограничению одной задачи соответствует переменная другой задачи, номер переменной совпадает с номером ограничения. При этом ограничению, записанному в виде неравенства ≤, соответствует переменная, связанная условием неотрицательности. Если ограничение исходной задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.
