Двойная линейная программа

Двойного данной линейной программы (LP) является еще одним ЛП , который является производным от оригинала (The первичной ) LP в следующем схематически:

Каждая переменная в первичном LP становится ограничением в двойном LP;
Каждое ограничение в первичном LP становится переменной в двойном LP;
Объективное направление инвертировано - максимум в первичном становится минимумом в дуальном и наоборот.

В слабой двойственности состояние теоремы о том , что объективное значение двойной LP в любом допустимом решении всегда связанно с целью первичной LP в любом возможном решении (верхняя или нижняя граница, в зависимости от того, является ли это максимизация или задача минимизации). Фактически, это ограничивающее свойство выполняется для оптимальных значений двойственных и прямых ЛП.

В сильных двойственностях теорема утверждает , что, кроме того, если изначальные имеет оптимальное решение , то двойственные имеет оптимальное решение слишком, и два оптимум равны . ^[1]

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

Создание двойного LP [ править ]

Учитывая первичный LP, следующий алгоритм может быть использован для построения его двойственного LP. ^[1]^{: 85} Первичный LP определяется:

Набор п переменных: . ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$
Для каждой переменной , знак ограничение - оно должно быть или неотрицательным ( ) или неположительны ( ), или неограниченной ( ). ${\ displaystyle x_ {i}}$ ${\ displaystyle x_ {i} \ geq 0}$ ${\ displaystyle x_ {i} \ leq 0}$ ${\ displaystyle x_ {i} \ in \ mathbb {R}}$
Целевая функция: ${\ displaystyle {\ text {maximize}} ~~~ c_ {1} x_ {1} + \ cdots + c_ {n} x_ {n}}$
Список m ограничений. Каждое ограничение j : где символ перед знаком может быть либо или, либо . ${\ displaystyle a_ {j1} x_ {1} + \ cdots + a_ {jn} x_ {n} \ lesseqqgtr b_ {j}}$ ${\ displaystyle b_ {j}}$ ${\ displaystyle \ geq}$ ${\ displaystyle \ leq}$ ${\ displaystyle =}$

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

Каждое первичное ограничение становится двойной переменной. Таким образом , есть м переменные: . ${\ displaystyle y_ {1}, \ ldots, y_ {m}}$
Знаковое ограничение каждой дуальной переменной «противоположно» знаку его основного ограничения. Итак, « становится, и» «становится, и » становится . ${\ displaystyle \ geq b_ {j}}$ ${\ displaystyle y_ {j} \ leq 0}$ ${\ displaystyle \ leq b_ {j}}$ ${\ displaystyle y_ {j} \ geq 0}$ ${\ displaystyle = b_ {j}}$ ${\ displaystyle y_ {j} \ in \ mathbb {R}}$
Двойная целевая функция: ${\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}$
Каждая основная переменная становится двойным ограничением. Итак, есть n ограничений. Коэффициент двойственной переменной в двойном ограничении - это коэффициент ее первичной переменной в первичном ограничении. Таким образом, каждое ограничение i имеет вид:, где символ перед знаком аналогичен ограничению для переменной i в первичном LP. Так становится " " и становится " " и становится " ". $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ $c_{i}$ $x_{i}\leq 0$ $\leq c_{i}$ $x_{i}\geq 0$ $\geq c_{i}$ $x_{i}\in \mathbb {R}$ $=c_{i}$

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

Векторные формулы [ править ]

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

Первобытный	Двойной	Примечание
Максимизировать c ^Tx при условии A x ≤ b , x ≥ 0	Минимизировать b ^Ty при условии, что A ^Ty ≥ c , y ≥ 0	Это называется «симметричной» двойственной задачей.
Максимизировать c ^Tx при условии A x ≤ b	Минимизировать b ^Ty при условии, что A ^Ty = c , y ≥ 0	Это называется «асимметричной» двойственной задачей.
Максимизировать c ^Tx при условии A x = b , x ≥ 0	Минимизировать b ^Ty при условии, что A ^Ty ≥ c

Теоремы двойственности [ править ]

Ниже предположим, что первичный LP - это «максимизировать c ^Tx с учетом [ограничений]», а двойственный LP - это «минимизировать b ^Ty с учетом [ограничений]».

Слабая двойственность [ править ]

Теорема слабой двойственности утверждает, что для каждого допустимого решения x прямого и каждого допустимого решения y двойственного: c ^Tx ≤ b ^Ty . Другими словами, объективная ценность в каждом допустимом решении дуального - это верхняя граница объективной ценности первичного, а объективная ценность в каждом возможном решении первичного - нижняя граница объективной ценности двойственного. Из этого следует:

макс _x c ^Tx ≤ min _y b ^Ty

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

Слабую теорему двойственности доказать относительно просто. Предположим, что первичный LP - это «Максимизировать c ^Tx при условии A x ≤ b , x ≥ 0». Предположим , мы создаем линейную комбинацию ограничений, с положительными коэффициентами, такие , что коэффициенты х в ограничениях являются по меньшей мере , с ^Т . Эта линейная комбинация дает нам верхнюю границу цели. Переменные y двойственной ЛП являются коэффициентами этой линейной комбинации. Двойственный LP пытается найти такие коэффициенты, которые минимизируют результирующую верхнюю границу. Это дает LP "Minimize b ^Ty при условииA ^Ty ≥ c , y ≥ 0 ". ^[1]^{: 81–83} См. Крошечный пример ниже.

Сильная двойственность [ править ]

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

макс _x c ^Tx = min _y b ^Ty

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

Одно доказательство использует симплексный алгоритм и полагается на доказательство того, что с подходящим правилом поворота оно дает правильное решение. Доказательство устанавливает, что после того, как симплекс-алгоритм завершает работу с решением прямой LP, можно читать из окончательной таблицы решение двойственной LP. Итак, запуская симплексный алгоритм, мы получаем решения как для прямого, так и для двойственного решения одновременно. ^[1]^{: 87–89}

Другое доказательство использует лемму Фаркаша . ^[1]^{: 94}

Теоретические последствия [ править ]

1. Теорема слабой двойственности подразумевает, что найти единственное допустимое решение так же сложно, как найти оптимальное допустимое решение. Предположим, у нас есть оракул, который по LP находит произвольное допустимое решение (если оно существует). Учитывая LP «Максимизировать c ^Tx при условии A x ≤ b , x ≥ 0», мы можем построить другой LP, объединив этот LP с двойственным. Комбинированный LP имеет как переменные x, так и y :

Увеличить 1

при условии A x ≤ b , A ^Ty ≥ c , c ^Tx ≥ b ^Ty , x ≥ 0, y ≥ 0

Если комбинированная ЛП имеет допустимое решение ( x , y ), то по слабой двойственности c ^Tx = b ^Ty . Таким образом, x должен быть максимальным решением прямой LP, а y должен быть минимальным решением двойственной LP. Если комбинированный LP не имеет допустимого решения, то и первичный LP также не имеет допустимого решения.

2. Сильная теорема двойственности обеспечивает «хорошую характеристику» оптимального значения LP, поскольку позволяет нам легко доказать, что некоторое значение t является оптимальным для некоторого LP. Доказательство проводится в два этапа: ^[2]^{: 260–261.}

Покажите возможное решение первичной LP со значением t ; это доказывает, что оптимум не меньше t .
Покажите возможное решение двойного LP со значением t ; это доказывает, что оптимум не превышает t .

Примеры [ править ]

Маленький пример [ править ]

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

{\begin{aligned}{\text{maximize }}&3x_{1}+4x_{2}\\{\text{subject to }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}

Применение приведенного выше рецепта дает следующий двойной LP с одной переменной и двумя ограничениями:

{\begin{aligned}{\text{minimize }}&7y_{1}\\{\text{subject to }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}

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

Точно так же минимум двойственного LP достигается, когда y ₁ минимизируется до своей нижней границы при ограничениях: первое ограничение дает нижнюю границу 3/5, а второе ограничение дает более строгую нижнюю границу 4/6, поэтому фактическая нижняя граница составляет 4/6, а минимальная - 7 · 4/6 = 14/3.

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

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

Пример фермера [ править ]

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

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

Максимизировать: $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$		(максимизировать выручку от производства пшеницы и ячменя)
при условии:	$x_{1}+x_{2}\leq L$	(нельзя использовать больше земли, чем доступно)
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F$	(нельзя использовать больше удобрений, чем доступно)
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P$	(нельзя использовать больше пестицидов, чем доступно)
	$x_{1},x_{2}\geq 0$	(не может производить отрицательное количество пшеницы или ячменя).

В матричной форме это становится:

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

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

при условии:

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.

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

Свести к минимуму: $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$		(минимизировать общую стоимость средств производства как «целевую функцию»)
при условии:	$y_{L}+F_{1}\cdot y_{F}+P_{1}\cdot y_{P}\geq S_{1}$	(фермер должен получить не менее S ₁ за свою пшеницу)
	$y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geq S_{2}$	(фермер должен получить не менее S ₂ за свой ячмень)
	$y_{L},y_{F},y_{P}\geq 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}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.

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

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

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

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

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

Невыполнимая программа [ править ]

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

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

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

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

Приложения [ править ]

Теорема о максимальном потоке и минимальном разрезе является частным случаем сильной теоремы двойственности: максимизация потока - это прямая ЛП, а минимизация сечения - двойственная ЛП. См. Теорему о максимальном расходе и минимальном отсечении # Формулировка линейной программы .

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

Теорема о минимаксе для игр с нулевой суммой может быть доказана с помощью теоремы сильной двойственности. ^[1]^{: подраздел.8.1}

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

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

Свести к минимуму	$\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}\geq g_{j},$	$1\leq j\leq n$
	$f_{i}x_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\geq h_{i},$	$1\leq i\leq m$
	$x_{i}\geq 0,\,t_{j}\geq 0,$	$1\leq i\leq m,1\leq j\leq 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}\geq g_{j}\cdot y_{j},$	$1\leq j\leq n$
	$f_{i}x_{i}\cdot s_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\cdot s_{i}\geq h_{i}\cdot s_{i},$	$1\leq i\leq m$
	$x_{i}\geq 0,\,t_{j}\geq 0,$	$1\leq i\leq m,1\leq j\leq n$
	$y_{j}\geq 0,\,s_{i}\geq 0,$	$1\leq j\leq n,1\leq i\leq m$

Поскольку это задача минимизации, мы хотели бы получить двойную программу, которая является нижней границей прямого. Другими словами, мы хотели бы, чтобы сумма всех правых частей ограничений была максимальной при условии, что для каждой прямой переменной сумма ее коэффициентов не превышает ее коэффициент в линейной функции. Например, x ₁ появляется в n + 1 ограничениях. Если суммировать коэффициенты ее ограничения мы получаем в _1,1г ₁ + _1,2у ₂ + ... + _{1, ;; п ;;}y _n + f ₁s ₁. Эта сумма должна быть не более 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}\leq c_{i},$	$1\leq i\leq m$
	$e_{j}y_{j}+\sum _{i=1}^{m}b_{ij}s_{i}\leq d_{j},$	$1\leq j\leq n$
	$y_{j}\geq 0,\,s_{i}\geq 0,$	$1\leq j\leq n,1\leq i\leq m$

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

Реальные интерпретации [ править ]

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

Теорема двойственности имеет и физическую интерпретацию. ^[1]^{: 86–87}

Ссылки [ править ]

^ a b c d e f g Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Springer. ISBN 3-540-30697-8. Страницы 81–104.
^ Ловас, Ласло ; Пламмер, доктор медицины (1986), Теория соответствия , Анналы дискретной математики, 29 , Северная Голландия, ISBN 0-444-87916-1, Руководство по ремонту 0859549
Перейти ↑ AA Ahmadi (2016). «Лекция 6: линейное программирование и согласование» (PDF) . Принстонский университет .

[gm06-1] Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Springer. ISBN 3-540-30697-8. Страницы 81–104.

[lp-2] Ловас, Ласло ; Пламмер, доктор медицины (1986), Теория соответствия , Анналы дискретной математики, 29 , Северная Голландия, ISBN 0-444-87916-1, Руководство по ремонту 0859549

[3] Перейти ↑ AA Ahmadi (2016). «Лекция 6: линейное программирование и согласование» (PDF) . Принстонский университет .

[1]