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

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

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

Прямая задача может быть записана следующим образом:

(1)

(2)

(3)

Переменные двойственной задачи y_i называют объективно обусловленными оценками, или двойственными оценками. Модель двойственной задачи имеет вид:

(4)

(5)

(6)

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

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

1) Целевая функция исходной задачи (1) формулируется на максимум, а целевая функция двойственной задачи (4) – на минимум. В задаче на максимум все неравенства в функциональных ограничениях имеют вид , а в задаче на минимум – вид .

2) Матрица ,

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

.

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

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

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

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

Первая теорема двойственности утверждает:

1. Если прямая и двойственная задачи имеют оптимальные решения, то значения целевых функций в их оптимальных планах совпадают: max f( ) = min g( ) .

2. Если прямая задача имеет допустимые решения, а ее целевая функция не ограничена сверху, то двойственная задача не имеет допустимых планов.

3. Если двойственная задача имеет допустимые решения, а целевая функция не ограничена снизу, то прямая задача не имеет допустимых решений.

4. Обе из рассматриваемых задач не имеют допустимых решений.

Вторая теорема двойственности утверждает правила дополняющей нежесткости. Пусть = (x_l,x₂,...,x_n) – допустимое решение прямой задачи (1)-(3), а = (y₁, y₂,...,y_m) – допустимое решение двойственной задачи (4)-(6). Для того чтобы они были оптимальными решениями соответствующих взаимодвойственных задач (1)-(3) и (4)-(6), необходимо и достаточно, чтобы выполнялись следующие соотношения:

, (7)

. (8)

Условия (7) и (8) позволяют по данным оптимального решения одной из взаимодвойственных задач найти оптимальное решение другой задачи.