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

Двойственная задача для заданной задачи линейного программирования (ЛП, англ. Linear programming, LP) — это другая задача линейного программирования, которая получается из исходной (прямой) задачи следующим образом:

Каждая переменная в прямой задаче становится ограничением двойственной задачи;
Каждое ограничение в прямой задаче становится переменной в двойственной задаче;
Направление цели обращается – максимум в прямой задаче становится минимумом в двойственной, и наоборот.

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

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

Эти теоремы принадлежат более широкому классу теорем двойственности в оптимизации. Теорема о сильной двойственности является одним из случаев, в котором разрыв двойственности (разрыв между оптимумом прямой задачи и оптимумом двойственной) равен 0.

О геометрическом смысле двойственной задачи можно почитать в книге Юдина и Гольштейна. Там же можно прочитать об экономическом смысле задачи.

Построение двойственной задачи

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

Пусть прямая задача определена как:

Дан набор из n переменных: x 1 , … , x n {displaystyle x_{1},ldots ,x_{n}} .
Для каждой переменной i определено ограничение на знак — она должна быть либо неотрицательной ( x i ⩾ 0 {displaystyle x_{i}geqslant 0} ), либо неположительной ( x i ⩽ 0 {displaystyle x_{i}leqslant 0} ), либо ограничение не задано ( x i ∈ R {displaystyle x_{i}in mathbb {R} } ).
Задана целевая функция: Максимизировать c 1 x 1 + ⋯ + c n x n {displaystyle c_{1}x_{1}+cdots +c_{n}x_{n}}
Задан список из m ограничений. Каждое ограничение j равно: a j 1 x 1 + ⋯ + a j n x n ⪋ b j {displaystyle a_{j1}x_{1}+cdots +a_{jn}x_{n}lesseqqgtr b_{j}} , где символ перед b j {displaystyle b_{j}} может быть одним из трёх — ⩾ {displaystyle geqslant } , ⩽ {displaystyle leqslant } или = {displaystyle =} .

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

Каждое ограничение прямой задачи становится двойственной переменной. Таким образом, получаем m переменных: y 1 , … , y m {displaystyle y_{1},ldots ,y_{m}} .
Знак ограничения каждой двойственной переменной «противоположен» знаку ограничения в прямой задаче. Таким образом, « ⩾ b j {displaystyle geqslant b_{j}} » становится y j ⩽ 0 {displaystyle y_{j}leqslant 0} , « ⩽ b j {displaystyle leqslant b_{j}} » превращается в y j ⩾ 0 {displaystyle y_{j}geqslant 0} , а « = b j {displaystyle =b_{j}} » превращается в y j ∈ R {displaystyle y_{j}in mathbb {R} } .
Целевая функция двойственной задачи равна (минимизировать) b 1 y 1 + ⋯ + b m y m {displaystyle b_{1}y_{1}+cdots +b_{m}y_{m}}
Каждая переменная прямой задачи становится двойственным ограничением. Таким образом, получаем n ограничений. Коэффициент двойственной переменной в двойственных ограничениях равен коэффициенту переменной из ограничения прямой задачи. Таким образом, каждое ограничение i есть: a 1 i y 1 + ⋯ + a m i y m ⪋ c i {displaystyle a_{1i}y_{1}+cdots +a_{mi}y_{m}lesseqqgtr c_{i}} , где символ перед c i {displaystyle c_{i}} аналогичен ограничению на переменную i в прямой задаче. Так, x i ⩽ 0 {displaystyle x_{i}leqslant 0} превращается в « ⩽ c i {displaystyle leqslant c_{i}} », x i ⩾ 0 {displaystyle x_{i}geqslant 0} превращается в « ⩾ c i {displaystyle geqslant c_{i}} », а x i ∈ R {displaystyle x_{i}in mathbb {R} } превращается в « = c i {displaystyle =c_{i}} ».

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

Векторные формулировки

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

Теоремы двойственности

Ниже мы предполагаем, что прямая задача поставлена как «Максимизировать c T x {displaystyle mathbf {c} ^{T}mathbf {x} } при ограничениях [ограничения]», а двойственная задача поставлена как «Минимизировать b T y {displaystyle mathbf {b} ^{T}mathbf {y} } при ограничениях [ограничения]».

Слабая двойственность

Теорема о слабой двойственности утверждает, что для каждого допустимого решения x прямой задачи и каждого допустимого решения y двойственной задачи: c T x ⩽ b T y {displaystyle mathbf {c} ^{T}mathbf {x} leqslant mathbf {b} ^{T}mathbf {y} } . Другими словами, значение целевой функции для каждого допустимого решения двойственной задачи является верхней границей целевой функции прямой задачи, а значение целевой функции любого допустимого решения прямой задачи является нижней границей для целевой функции двойственной задачи. Из этого следует, что

max x c T x ⩽ min y b T y {displaystyle max _{mathbf {x} }mathbf {c} ^{T}mathbf {x} leqslant min _{mathbf {y} }mathbf {b} ^{T}mathbf {y} }

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

Теорему о слабой двойственности относительно легко доказать. Предположим, что прямая задача линейного программирования звучит как «Максимизировать c T x {displaystyle mathbf {c} ^{T}mathbf {x} } при ограничениях A x ⩽ b , x ⩾ 0 {displaystyle mathbf {Ax} leqslant mathbf {b} ,mathbf {x} geqslant 0} ». Предположим, что мы создаём линейную комбинацию ограничений с положительными коэффициентами, такую, что коэффициенты при x не меньше c T {displaystyle mathbf {c} ^{T}} . Эта линейная комбинация даёт нам верхнюю грань для целевой функции. Переменные y двойственной задачи являются коэффициентами этой линейной комбинации. Двойственная задача пытается найти такие коэффициенты, которые минимизируют результирующую правую часть. Это даёт задачу линейного программирования «Минимизировать b T y {displaystyle mathbf {b} ^{T}mathbf {y} } при ограничениях A T y ⩾ c , y ⩾ 0 {displaystyle mathbf {A} ^{T}mathbf {y} geqslant mathbf {c} ,mathbf {y} geqslant 0} ». См. «Простой пример» ниже.

Сильная двойственность

Теорема о сильной двойственности утверждает, что границы, определяемые теоремой о слабой двойственности жёсткие, то есть

max x c T x = min y b T y {displaystyle max _{mathbf {x} }mathbf {c} ^{T}mathbf {x} =min _{mathbf {y} }mathbf {b} ^{T}mathbf {y} }

Теорему о сильной двойственности существенно труднее доказать. Обычно доказательство использует теорему о слабой двойственности в качестве леммы.

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

Другое доказательство использует лемму Фаркаша

Теоретическое приложение

Слабая двойственность имеет интересное теоретическое приложение — она показывает, что нахождение отдельного допустимого решения настолько же трудно, насколько нахождение оптимального допустимого решения. Предположим, что мы имеем систему предсказывания, что данная задача линейного программирования находит произвольное допустимое решение (если оно существует). Если задача звучит как «Максимизировать c x {displaystyle mathbf {c} ^{mathbf {x} }} при ограничениях A x ⩽ b , x ⩾ 0 {displaystyle mathbf {Ax} leqslant mathbf {b} ,mathbf {x} geqslant 0} », мы можем построить другую задачу путём комбинирования её с двойственной ей задачей. Комбинированная задача имеет как x, так и y в качестве переменных:

Максимизировать 1

при ограничениях A x ⩽ b , A T y ⩾ c , c T x ⩾ b T y , x ⩾ 0 , y ⩾ 0 {displaystyle mathbf {Ax} leqslant mathbf {b} ,mathbf {A} ^{T}mathbf {y} geqslant mathbf {c} ,mathbf {c} ^{T}mathbf {x} geqslant mathbf {b} ^{T}mathbf {y} ,mathbf {x} geqslant 0,mathbf {y} geqslant 0}

Если комбинированная задача имеет допустимое решение (x,y), то по слабой двойственности c T x = b T y {displaystyle mathbf {c} ^{T}mathbf {x} =mathbf {b} ^{T}mathbf {y} } . Таким образом, x должно быть максимальным решением прямой задачи, а y должно быть минимальным решением двойственной задачи. Если комбинированная задача не имеет допустимого решения, то и прямая задача допустимого решения не имеет.

Примеры

Простой пример

Рассмотрим прямую задачу с двумя переменными и одним ограничением:

Максимизировать 3 x 1 + 4 x 2 {displaystyle 3x_{1}+4x_{2}} При условиях 5 x 1 + 6 x 2 = 7 x 1 ⩾ 0 , x 2 ⩾ 0 {displaystyle {egin{aligned}&5x_{1}+6x_{2}=7&x_{1}geqslant 0,x_{2}geqslant 0end{aligned}}}

Применив вышеизложенный рецепт построения двойственной задачи, получим задачу с одной переменной и двумя ограничениями:

Минимизировать 7 y 1 {displaystyle 7y_{1}} При условиях

5 y 1 ⩾ 3 6 y 1 ⩾ 4 y 1 ∈ R {displaystyle {egin{aligned}&&5y_{1}geqslant 3&&6y_{1}geqslant 4&&y_{1}in mathbb {R} end{aligned}}}

Легко видеть, что максимум прямой задачи достигается, когда переменная x1 минимизируется до её нижней границы (0), а переменная x2 максимизируется до её верхней границы, заданной ограничением (7/6). Максимум равен 4 ⋅ 7 / 6 = 14 / 3 {displaystyle 4cdot 7/6=14/3} .

Аналогично, минимум двойственной задачи достигается, когда y1 минимизируется до его нижнего значения при ограничениях: первое ограничение даёт значение 3/5, в то время как второе даёт более строгую границу 4/6, так что фактический минимум равен 4/6 и минимум целевой функции равен 7 ⋅ 4 / 6 = 14 / 3 {displaystyle 7cdot 4/6=14/3} .

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

Мы используем этот пример для иллюстрации доказательства теоремы о слабой двойственности. Предположим, что в прямой задаче линейного программирования мы хотим получить верхнюю границу целевой функции 3 x 1 + 4 x 2 {displaystyle 3x_{1}+4x_{2}} . Мы можем использовать ограничение, умноженное на некоторый коэффициент, скажем, y 1 {displaystyle y_{1}} . Для любого y 1 {displaystyle y_{1}} мы имеем: y 1 ⋅ ( 5 x 1 + 6 x 2 ) = 7 y 1 {displaystyle y_{1}cdot (5x_{1}+6x_{2})=7y_{1}} . Теперь, если y 1 ⋅ 5 x 1 ⩾ 3 x 1 {displaystyle y_{1}cdot 5x_{1}geqslant 3x_{1}} и y 1 ⋅ 6 x 2 ⩾ 4 x 2 {displaystyle y_{1}cdot 6x_{2}geqslant 4x_{2}} , то y 1 ⋅ ( 5 x 1 + 6 x 2 ) ⩾ 3 x 1 + 4 x 2 {displaystyle y_{1}cdot (5x_{1}+6x_{2})geqslant 3x_{1}+4x_{2}} , так что 7 y 1 ⩾ 3 x 1 + 4 x 2 {displaystyle 7y_{1}geqslant 3x_{1}+4x_{2}} . Следовательно, целевая функция двойственной задачи является верхней границей целевой функции прямой задачи.

Пример фермера

Рассмотрим фермера, который может выращивать пшеницу и ячмень на площади L, используя удобрения F и пестициды P. Чтобы вырастить одну единицу пшеницы на единице площади, нужно использовать F 1 {displaystyle F_{1}} единиц удобрений и P 1 {displaystyle P_{1}} единиц пестицидов.

Прямой задачей будет решение фермера, сколько пшеницы ( x 1 {displaystyle x_{1}} ) и ячменя ( x 2 {displaystyle x_{2}} ) выращивать, если их продажные цены равны S 1 {displaystyle S_{1}} и S 2 {displaystyle S_{2}} за единицу.

Максимизировать: S 1 ⋅ x 1 + S 2 ⋅ x 2 {displaystyle S_{1}cdot x_{1}+S_{2}cdot x_{2}} (максимизировать доход от выращивания пшеницы и ячменя) при ограничениях: x 1 + x 2 ⩽ L {displaystyle x_{1}+x_{2}leqslant L} (фермер не может использовать больше земли, чем у него есть) F 1 ⋅ x 1 + F 2 ⋅ x 2 ⩽ F {displaystyle F_{1}cdot x_{1}+F_{2}cdot x_{2}leqslant F} (фермер не может использовать больше удобрений, чем есть в наличии) P 1 ⋅ x 1 + P 2 ⋅ x 2 ⩽ P {displaystyle P_{1}cdot x_{1}+P_{2}cdot x_{2}leqslant P} (фермер не может использовать больше пестицидов, чем у него есть) x 1 , x 2 ⩾ 0 {displaystyle x_{1},x_{2}geqslant 0} (нельзя вырастить отрицательную величину зерна).

Для двойственной задачи предположим, что y единиц цены для каждой из этих видов продукта (входы) представлены группой планирования. Задачей группы планирования является минимизация полной стоимости производство продукции при заданных величинах потребления ресурсов с определением стоимости единицы ресурса (выход). Это соответствует следующей задаче линейного программирования:

Минимизировать L ⋅ y L + F ⋅ y F + P ⋅ y P {displaystyle Lcdot y_{L}+Fcdot y_{F}+Pcdot y_{P}} (минимизировать полную стоимость производства продукции как «целевая функция») при ограничениях: y L + F 1 ⋅ y F + P 1 ⋅ y P ⩾ S 1 {displaystyle y_{L}+F_{1}cdot y_{F}+P_{1}cdot y_{P}geqslant S_{1}} (фермер должен получить не менее S1 за единицу пшеницы) y L + F 2 ⋅ y F + P 2 ⋅ y P ⩾ S 2 {displaystyle y_{L}+F_{2}cdot y_{F}+P_{2}cdot y_{P}geqslant S_{2}} (фермер должен получить не менее S2 за единицу ячменя) y L , y F , y P ⩾ 0 {displaystyle y_{L},y_{F},y_{P}geqslant 0} (цены не могут быть отрицательными).

В матричной форме:

Минимизировать: [ L F P ] [ y L y F y P ] {displaystyle {egin{bmatrix}L&F&Pend{bmatrix}}{egin{bmatrix}y_{L}y_{F}y_{P}end{bmatrix}}} при условиях: [ 1 F 1 P 1 1 F 2 P 2 ] [ y L y F y P ] ⩾ [ S 1 S 2 ] , [ y L y F y P ] ⩾ 0. {displaystyle {egin{bmatrix}1&F_{1}&P_{1}1&F_{2}&P_{2}end{bmatrix}}{egin{bmatrix}y_{L}y_{F}y_{P}end{bmatrix}}geqslant {egin{bmatrix}S_{1}S_{2}end{bmatrix}},,{egin{bmatrix}y_{L}y_{F}y_{P}end{bmatrix}}geqslant 0.}

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

Каждой переменной в пространстве прямой задачи соответствует неравенство в пространстве двойственной задачи. Каждому неравенству в пространстве прямой задачи соответствует переменная в пространстве двойственной задачи.

Коэффициенты, которые ограничивают неравенства в пространстве прямой задачи, используются для вычисления целевой функции в двойственном пространстве. Коэффициенты, используемые для вычисления целевой функции, в пространстве прямой задачи ограничивают неравенства в пространстве двойственной задачи.

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

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

Недопустимая задача

Задача линейного программирования может также быть неограниченной или недопустимой. Теория двойственности говорит нам, что:

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

Однако может быть, что обе задачи, как двойственная, так и прямая, недопустимы. Вот пример:

Приложения

Теорема о максимальном потоке и минимальном разрезе является специальным случаем теоремы о сильной двойственности — максимизация потока является прямой задачей линейного программирования, а минимизация разреза является двойственной задачей линейного программирования. См. теорему Форда — Фалкерсона.

Другие теоремы, связанные с графами, могут быть доказаны с помощью теоремы о сильной двойственности, в частности, теорема Кёнига.

Теорема о минимаксе для игр с нулевой суммой может быть доказана с помощью теоремы о сильной двойственности.

Альтернативный алгоритм

Иногда можно найти более интуитивный способ получить двойственную задачу без применения матрицы задачи. Рассмотрим следующую задачу линейного программирования:

Минимизировать ∑ i = 1 m c i x i + ∑ j = 1 n d j t j {displaystyle sum _{i=1}^{m}c_{i}x_{i}+sum _{j=1}^{n}d_{j}t_{j}} при условиях ∑ i = 1 m a i j x i + e j t j ⩾ g j , 1 ⩽ j ⩽ n {displaystyle sum _{i=1}^{m}a_{ij}x_{i}+e_{j}t_{j}geqslant g_{j},1leqslant jleqslant n} f i x i + ∑ j = 1 n b i j t j ⩾ h i , 1 ⩽ i ⩽ m {displaystyle f_{i}x_{i}+sum _{j=1}^{n}b_{ij}t_{j}geqslant h_{i},1leqslant ileqslant m} x i ⩾ 0 , t j ⩾ 0 , 1 ⩽ i ⩽ m , 1 ⩽ j ⩽ n {displaystyle x_{i}geqslant 0,,t_{j}geqslant 0,1leqslant ileqslant m,1leqslant jleqslant n}

Мы имеем m + n {displaystyle m+n} условий и все переменные неотрицательны. Нам нужно определить m + n {displaystyle m+n} двойственных переменных: yj и si. Мы получаем:

Минимизировать ∑ i = 1 m c i x i + ∑ j = 1 n d j t j {displaystyle sum _{i=1}^{m}c_{i}x_{i}+sum _{j=1}^{n}d_{j}t_{j}} при условиях ∑ i = 1 m a i j x i ⋅ y j + e j t j ⋅ y j ⩾ g j ⋅ y j , 1 ⩽ j ⩽ n {displaystyle sum _{i=1}^{m}a_{ij}x_{i}cdot y_{j}+e_{j}t_{j}cdot y_{j}geqslant g_{j}cdot y_{j},1leqslant jleqslant n} f i x i ⋅ s i + ∑ j = 1 n b i j t j ⋅ s i ⩾ h i ⋅ s i , 1 ⩽ i ⩽ m {displaystyle f_{i}x_{i}cdot s_{i}+sum _{j=1}^{n}b_{ij}t_{j}cdot s_{i}geqslant h_{i}cdot s_{i},1leqslant ileqslant m} x i ⩾ 0 , t j ⩾ 0 , 1 ⩽ i ⩽ m , 1 ⩽ j ⩽ n {displaystyle x_{i}geqslant 0,,t_{j}geqslant 0,1leqslant ileqslant m,1leqslant jleqslant n} y j ⩾ 0 , s i ⩾ 0 , 1 ⩽ j ⩽ n , 1 ⩽ i ⩽ m {displaystyle y_{j}geqslant 0,,s_{i}geqslant 0,1leqslant jleqslant n,1leqslant ileqslant m}

Поскольку это задача минимизации, нам хотелось бы получить двойственную задачу, которая является нижней границей прямой задачи. Другими словами, нам хотелось бы, чтобы сумма всех правых частей ограничений была максимальной при условиях, что для каждой переменной прямой задачи сумма её коэффициентов не превосходит коэффициента в линейной функции. Например, x1 появляется в n + 1 {displaystyle n+1} ограничениях. Если мы суммируем коэффициенты ограничения, мы получим a 1 , 1 y 1 + a 1 , 2 y 2 + ⋯ + a 1 , n y n + f 1 s 1 {displaystyle a_{1,1}mathbf {y} _{1}+a_{1,2}mathbf {y} _{2}+dots +a_{1,n}mathbf {y} _{n}+f_{1}mathbf {s} _{1}} . Эта сумма должна не превосходить c1. Как результат мы получаем:

Максимизировать ∑ j = 1 n g j y j + ∑ i = 1 m h i s i {displaystyle sum _{j=1}^{n}g_{j}y_{j}+sum _{i=1}^{m}h_{i}s_{i}} при ограничениях ∑ j = 1 n a i j y j + f i s i ⩽ c i , 1 ⩽ i ⩽ m {displaystyle sum _{j=1}^{n}a_{ij}y_{j}+f_{i}s_{i}leqslant c_{i},1leqslant ileqslant m} e j y j + ∑ i = 1 m b i j s i ⩽ d j , 1 ⩽ j ⩽ n {displaystyle e_{j}y_{j}+sum _{i=1}^{m}b_{ij}s_{i}leqslant d_{j},1leqslant jleqslant n} y j ⩾ 0 , s i ⩾ 0 , 1 ⩽ j ⩽ n , 1 ⩽ i ⩽ m {displaystyle y_{j}geqslant 0,,s_{i}geqslant 0,1leqslant jleqslant n,1leqslant ileqslant m}

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

Интерпретации в реальной жизни

Теорема двойственности имеет экономическую интерпретацию. Если мы интерпретируем прямую задачу линейного программирования как классическую задачу «распределения ресурсов», её двойственную задачу можно интерпретировать как задачу «оценки ресурсов». См. статью Теневая цена. Об экономической интерпретации двойственной задачи можно почитать также в книге Лунгу.

Теорема двойственности имеет и физическую интерпретацию.