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

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

Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей в нахождении максимального значения функции

F = C₁X₁ + C₂X₂+…+C_nX_n (1)

при условиях

(2)

x_j≥0 (j=1,n) (3)

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

F*=b₁y₁+b₂y₂+…+b_my_m (4.)

при условиях

(5)

y_i≥0 (i=1,m) (6)

называется двойственной задачей по отношению к задаче (1) – (3)..

Задачи (1) – (3) и (4) – (6) образуют пару задач, называемую в линейном программировании двойственной парой.

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

1. Целевая функция исходной задача задается на max, а целевая функция двойственной задачи на min.

2. Матрица:

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

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

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

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

5. Если переменная x_j исходной задачи может принимать лишь положительные значения, то j-тое условие в системе (5) двойственной задачи является неравенством вида «≥». Если же переменная x_j может принимать как положительные так и отрицательные значения, то j-тое соотношение в системе (5) является уравнением.

6. Если i-е соотношение в системе (2) исходной задачи является неравенством, то i-тая переменная двойственной задачи y_i≥0. В противном случае переменная y_i может принимать как положительные так и отрицательные значения.

Двойственные пары задач обычно подразделяются на симметричные и несимметричные.

В симметричной паре двойственной задачи ограничения вида (2) исходной задачи и соотношения (5) двойственной задачи являются неравенствами вида «≤», т.е переменные обеих задач могут принимать только неотрицательные значения.