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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Прямая	Двойственная	Примечания
Максимизировать $\mathbf {c} ^{T}\mathbf {x}$ при ограничениях $\mathbf {A} \mathbf {x} \leqslant \mathbf {b} ,\mathbf {x} \geqslant 0$	Минимизировать $\mathbf {b} ^{T}\mathbf {y}$ при ограничениях $\mathbf {A} ^{T}\mathbf {y} \geqslant \mathbf {c} ,\mathbf {y} \geqslant 0$	Такая задача называется «симметричной» двойственной задачей
Максимизировать $\mathbf {c} ^{T}\mathbf {x}$ при ограничениях $\mathbf {Ax} \leqslant \mathbf {b}$	Минимизировать $\mathbf {b} ^{T}\mathbf {y}$ при ограничениях $\mathbf {A} ^{T}\mathbf {y} =\mathbf {c} ,\mathbf {y} \geqslant 0$	Такая задача называется «асимметричной» двойственной задачей
Максимизировать $\mathbf {c} ^{T}\mathbf {x}$ при ограничениях $\mathbf {Ax} =\mathbf {b} ,\mathbf {x} \geqslant 0$	Минимизировать $\mathbf {b} ^{T}\mathbf {y}$ при ограничениях $\mathbf {A} ^{T}\mathbf {y} \geqslant \mathbf {c}$

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

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

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

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

$\max _{\mathbf {x} }\mathbf {c} ^{T}\mathbf {x} \leqslant \min _{\mathbf {y} }\mathbf {b} ^{T}\mathbf {y}$

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

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

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

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

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

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

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

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

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

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

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

при ограничениях $\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), то по слабой двойственности $\mathbf {c} ^{T}\mathbf {x} =\mathbf {b} ^{T}\mathbf {y}$. Таким образом, x должно быть максимальным решением прямой задачи, а y должно быть минимальным решением двойственной задачи. Если комбинированная задача не имеет допустимого решения, то и прямая задача допустимого решения не имеет.

Примеры

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

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

Максимизировать $3x_{1}+4x_{2}$

При условиях

${\begin{aligned}&5x_{1}+6x_{2}=7\\&x_{1}\geqslant 0,x_{2}\geqslant 0\end{aligned}}$

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

Минимизировать $7y_{1}$

При условиях

${\begin{aligned}&&5y_{1}\geqslant 3\\&&6y_{1}\geqslant 4\\&&y_{1}\in \mathbb {R} \end{aligned}}$

Легко видеть, что максимум прямой задачи достигается, когда переменная x₁ минимизируется до её нижней границы (0), а переменная x₂ максимизируется до её верхней границы, заданной ограничением (7/6). Максимум равен $4\cdot 7/6=14/3$.

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

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

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

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

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

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

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

$S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$ (максимизировать доход от выращивания пшеницы и ячменя)

при ограничениях:

$x_{1}+x_{2}\leqslant L$ (фермер не может использовать больше земли, чем у него есть)

$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leqslant F$ (фермер не может использовать больше удобрений, чем есть в наличии)

$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leqslant P$ (фермер не может использовать больше пестицидов, чем у него есть)

$x_{1},x_{2}\geqslant 0$ (нельзя вырастить отрицательную величину зерна).

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

Минимизировать

$L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$ (минимизировать полную стоимость производства продукции как «целевая функция»)

при ограничениях:

$y_{L}+F_{1}\cdot y_{F}+P_{1}\cdot y_{P}\geqslant S_{1}$ (фермер должен получить не менее S₁ за единицу пшеницы)

$y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geqslant S_{2}$ (фермер должен получить не менее S₂ за единицу ячменя)

$y_{L},y_{F},y_{P}\geqslant 0$ (цены не могут быть отрицательными).

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

Минимизировать: ${\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}$

при условиях: ${\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geqslant {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geqslant 0.$

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

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

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

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

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

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

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

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

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

Максимизировать: $2x_{1}-x_{2}$
При условиях:	$x_{1}-x_{2}\leqslant 1$
	$-x_{1}+x_{2}\leqslant -2$
	$x_{1},x_{2}\geqslant 0.$

Приложения

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

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

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

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

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

Минимизировать $\sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}$

при условиях

$\sum _{i=1}^{m}a_{ij}x_{i}+e_{j}t_{j}\geqslant g_{j},1\leqslant j\leqslant n$

$f_{i}x_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\geqslant h_{i},1\leqslant i\leqslant m$

$x_{i}\geqslant 0,\,t_{j}\geqslant 0,1\leqslant i\leqslant m,1\leqslant j\leqslant n$

Мы имеем $m+n$ условий и все переменные неотрицательны. Нам нужно определить $m+n$ двойственных переменных: y_j и s_i. Мы получаем:

Минимизировать $\sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}$

при условиях

$\sum _{i=1}^{m}a_{ij}x_{i}\cdot y_{j}+e_{j}t_{j}\cdot y_{j}\geqslant g_{j}\cdot y_{j},1\leqslant j\leqslant n$

$f_{i}x_{i}\cdot s_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\cdot s_{i}\geqslant h_{i}\cdot s_{i},1\leqslant i\leqslant m$

$x_{i}\geqslant 0,\,t_{j}\geqslant 0,1\leqslant i\leqslant m,1\leqslant j\leqslant n$

$y_{j}\geqslant 0,\,s_{i}\geqslant 0,1\leqslant j\leqslant n,1\leqslant i\leqslant m$

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

Максимизировать $\sum _{j=1}^{n}g_{j}y_{j}+\sum _{i=1}^{m}h_{i}s_{i}$

при ограничениях

$\sum _{j=1}^{n}a_{ij}y_{j}+f_{i}s_{i}\leqslant c_{i},1\leqslant i\leqslant m$

$e_{j}y_{j}+\sum _{i=1}^{m}b_{ij}s_{i}\leqslant d_{j},1\leqslant j\leqslant n$

$y_{j}\geqslant 0,\,s_{i}\geqslant 0,1\leqslant j\leqslant n,1\leqslant i\leqslant m$

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

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

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

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