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

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

Прямая задача:

.

Двойственная задача:

.

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

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

Матрица

,

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

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

Число переменных в двойственной задаче (m) равно числу соотношений (ограничений) в прямой задаче, а число ограничений двойственной задачи (n) – числу переменных в прямой задаче.

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

Если переменная x_j прямой задачи может принимать только положительные значения (x_j ³ 0), то j -е условие двойственной задачи – условие неравенства вида “³“. Если i-е соотношение в прямой задаче – неравенство, то i –я переменная двойственной задачи z _i ³ 0.

n Если прямая задача имеет решение, то и двойственная задача тоже имеет решение, причем max(min) L₁ = min(max) L₂, поэтому для отыскания оптимума достаточно решить одну какую–либо из задач двойственной пары, обычно решают ту, которая проще.

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