2.8. Двойственность в линейном программировании Прямая и двойственная задача.

Каждой ЗЛП можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой. Дадим определение двлйственной задачи по отношению к общей ЗЛП, состоящей в нахождении максимального значения функции

Z=C₁x₁+C₂x₂+...+C_nx_n (2.67)

при условиях

, (2.68)

x_j0 (2.69)

О п р е д е л е н и е 1. Задача, состоящая в нахождении минимального значения функции

Z^*=b₁y₁+b₂y₂+...+b_ny_n (2.70)

при условиях

(2.71)

y_i 0 (2.72)

называется двойственной по отношению к задаче (2.67)—(2.69).

Задачи (2.67)—(2.69) и (2.70)—(2.72) образуют пару задач, называемую двойственной парой.

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

1. Целевая функция исходной задачи (2.67)—(2.69) задается на максимум, а целевая функция двойственной (2.70)—(2.72) — на минимум.

2. Матрица

,

составленная из коэффициентов при неизвестных в системе ограничений (2.68) исходной задачи, и аналогичная матрица

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

3. Число переменных в двойственной задаче равно числу соотношений в системе (2.70) исходной задачи, а число ограничений в системе (2.71) двойственной задачи— числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (2.70) двойственной задачи являются свободные члены в системе (2.68) исходной задачи, а правыми частями в соотношениях системы (2.71) двойственной задачи — коэффициенты при неизвестных в целевой функции (2.67) исходной задачи.

5. Если переменная х_j исходной задачи может принимать только лишь положительные значения, то j-е условие в системе (2.71) двойственной задачи является неравенством вида «». Если же переменная х_j может принимать как положительные, так и отрицательные значения, то j -е соотношение в системе (2.71) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (2.68) исходной задачи и переменными двойственной задачи. Если i-е соотношение в системе (2.68) исходной задачи является неравенством, то i-я переменная двойственной задачи y_i 0. В противоположном случае переменная y_i может принимать как положительные, так и отрицательные значения.