Сущность двойственности в ЛП. Запись двойственности задачи
С каждой задачей линейного программирования тесно связана другая задача, называемая двойственной; первоначальная задача называетсяисходной или прямой. Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой. Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой. Однако при определении симплекс–методом оптимального плана одной из задач автоматически находится решение и другой задачи.
Двойственная задача по отношению к исходной составляется согласно следующим правилам:
1) если целевая функция исходной задачи формулируется на максимум, то целевая функция двойственной задачи – на минимум, и наоборот. При этом в задаче на максимум во всех неравенствах в функциональных ограничениях используется знак « », а в задаче на минимум − знак « »;
2) матрицы коэффициентов при неизвестных в системах ограничений прямой и двойственной задач получаются друг из друга транспонированием;
3) число неизвестных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе у двойственной задачи – числу неизвестных в исходной;
4) коэффициенты при неизвестных в целевой функции двойственной задачи являются свободными членами в системе ограничений прямой задачи, а свободные члены в системе ограничений двойственной задачи есть коэффициенты целевой функции прямой задачи;
5) каждому ограничению прямой задачи соответствует неизвестная двойственной: номер неизвестной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства со знаком « », соответствует неизвестная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая неизвестная двойственной задачи может принимать как положительные, так и отрицательные значения;
6) задача, двойственная двойственной, совпадает с исходной;
7) базисным неизвестным прямой задачи линейного программирования соответствуют свободные неизвестные двойственной, и наоборот.
Математические модели пары двойственных задач могут быть симметричными и несимметричными.
В несимметричных двойственных задачах система ограничений исходной задачи задаётся в виде равенств, в двойственной – в виде неравенств, причём в последней неизвестные могут быть и отрицательными.
В симметричных двойственных задачах система ограничений как исходной, так и двойственной задачи, задаётся неравенствами, причём на двойственные неизвестные налагается условие неотрицательности.
Везде далее будем рассматривать только симметричные взаимо-двойственные задачи линейного программирования.
Запишем пару симметричных взаимодвойственных задач линейного программирования в соответствии с перечисленными выше правилами (табл. 9.1).