Сущность двойственности в ЛП. Запись двойственности задачи

С каждой задачей линейного программирования тесно связана другая задача, называемая двойственной; первоначальная задача называетсяисходной или прямой. Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой. Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой. Однако при определении симплекс–методом оптимального плана одной из задач автоматически находится решение и другой задачи.

Двойственная задача по отношению к исходной составляется согласно следующим правилам:

1) если целевая функция исходной задачи формулируется на максимум, то целевая функция двойственной задачи – на минимум, и наоборот. При этом в задаче на максимум во всех неравенствах в функциональных ограничениях используется знак « », а в задаче на минимум − знак « »;

2) матрицы коэффициентов при неизвестных в системах ограничений прямой и двойственной задач получаются друг из друга транспонированием;

3) число неизвестных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе у двойственной задачи – числу неизвестных в исходной;

4) коэффициенты при неизвестных в целевой функции двойственной задачи являются свободными членами в системе ограничений прямой задачи, а свободные члены в системе ограничений двойственной задачи есть коэффициенты целевой функции прямой задачи;

5) каждому ограничению прямой задачи соответствует неизвестная двойственной: номер неизвестной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства со знаком « », соответствует неизвестная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая неизвестная двойственной задачи может принимать как положительные, так и отрицательные значения;

6) задача, двойственная двойственной, совпадает с исходной;

7) базисным неизвестным прямой задачи линейного программирования соответствуют свободные неизвестные двойственной, и наоборот.

Математические модели пары двойственных задач могут быть симметричными и несимметричными.

В несимметричных двойственных задачах система ограничений исходной задачи задаётся в виде равенств, в двойственной – в виде неравенств, причём в последней неизвестные могут быть и отрицательными.

В симметричных двойственных задачах система ограничений как исходной, так и двойственной задачи, задаётся неравенствами, причём на двойственные неизвестные налагается условие неотрицательности.

Везде далее будем рассматривать только симметричные взаимо-двойственные задачи линейного программирования.

Запишем пару симметричных взаимодвойственных задач линейного программирования в соответствии с перечисленными выше правилами (табл. 9.1).