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

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

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

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

Теорема сильной двойственности утверждает, что, более того, если простое число имеет оптимальное решение, то и двойственное решение тоже имеет оптимальное решение, и два оптимума равны . ^[1]

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

Форма двойной пластинки

Предположим, у нас есть линейная программа:

Максимизировать c ^Тx при условии A x ≤ b , x ≥ 0.

Нам хотелось бы построить верхнюю границу решения. Таким образом, мы создаем линейную комбинацию ограничений с положительными коэффициентами, такую, что коэффициенты x в ограничениях равны по крайней мере c. ^Т. Эта линейная комбинация дает нам верхнюю границу цели. Переменные y двойственной ЛП являются коэффициентами этой линейной комбинации. Двойной ЛП пытается найти такие коэффициенты, которые минимизируют полученную верхнюю границу. Это дает следующий LP: ^[1]^: 81–83

Минимизировать б ^Тy подлежит А ^Ту ≥ с , у ≥ 0

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

Интерпретация

Теорема двойственности имеет экономическую интерпретацию. ^[2]^[3] Если мы интерпретируем первичную ЛП как классическую проблему « распределения ресурсов », то ее двойственную ЛП можно интерпретировать как задачу «оценки ресурсов».

Рассмотрим фабрику, которая планирует производство товаров. Позволять $x$ быть его производственным графиком (сделать $x_{i}$ количество добра $i$ ), позволять $c\geq 0$ быть списком рыночных цен (единицы товара $i$ могу продать за $c_{i}$ ). Ограничения, которые он имеет, $x\geq 0$ (он не может производить отрицательные товары) и сырьевые ограничения. Позволять $b$ быть сырьем, которое у него есть в наличии, и пусть $A\geq 0$ – матрица материальных затрат (производство одной единицы товара $i$ требует $A_{ji}$ единицы сырья $j$ ).

Тогда ограниченная максимизация дохода является основной ЛП:

Максимизировать c ^Тx при условии A x ≤ b , x ≥ 0.

Теперь рассмотрим другую фабрику, у которой нет сырья и которая желает закупить весь запас сырья на предыдущей фабрике. Он предлагает ценовой вектор $y$ (единица сырья $i$ для $y_{i}$ ). Для того, чтобы предложение было принято, должно быть так, что $A^{T}y\geq c$ , поскольку в противном случае фабрика могла бы заработать больше денег, производя определенный продукт, чем продавая сырье, используемое для производства товара. Это также должно быть $y\geq 0$ , поскольку завод не будет продавать сырье по отрицательной цене. Тогда задача оптимизации второй фабрики — это двойной ЛП:

Минимизировать б ^Тy подлежит А ^Ту ≥ с , у ≥ 0

Теорема двойственности утверждает, что разрыв двойственности между двумя задачами ЛП равен как минимум нулю. С экономической точки зрения это означает, что если первой фабрике будет предложено купить весь запас сырья по цене за единицу продукции y , такой, что A ^Тy ≥ c , y ≥ 0, то предложение следует принять. Оно будет получать по крайней мере столько же дохода, сколько могло бы получить от производства готовой продукции.

Теорема сильной двойственности далее утверждает, что разрыв двойственности равен нулю. При сильной двойственности двойное решение $y^{*}$ с экономической точки зрения, это «равновесная цена» (см. теневую цену ) на сырье, которое завод с производственной матрицей $A$ и запасы сырья $b$ принял бы за сырье, учитывая рыночную цену готовой продукции $c$ . (Обратите внимание, что $y^{*}$ не может быть уникальным, поэтому равновесная цена не может полностью определяться $A$ , $b$ , и $c$ .)

Чтобы понять, почему, подумайте, растут ли цены на сырье. $y\geq 0$ таковы, что $(A^{T}y)_{i}<c_{i}$ для некоторых $i$ , то завод закупит больше сырья, чтобы производить больше товаров. $i$ , так как цены «слишком низкие». И наоборот, если цены на сырье удовлетворяют $A^{T}y\geq c,y\geq 0$ , но не минимизирует $b^{T}y$ , то фабрика будет зарабатывать больше денег, продавая сырье, чем производя товары, поскольку цены «слишком высоки». По равновесной цене $y^{*}$ фабрика не может увеличить свою прибыль за счет покупки или продажи сырья.

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

Построение двойного ЛП

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

Набор из n переменных: $x_{1},\ldots ,x_{n}$ .
Для каждой переменной $x_{i}$ , ограничение знака – оно должно быть либо неотрицательным ( $x_{i}\geq 0$ ), или неположительный ( $x_{i}\leq 0$ ), или неограниченный ( $x_{i}\in \mathbb {R}$ ).
Целевая функция: ${\text{maximize}}~~~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}$ может быть одним из $\geq$ или $\leq$ или $=$ .

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

Каждое первичное ограничение становится двойной переменной. Итак, существует m переменных: $y_{1},\ldots ,y_{m}$ .
Ограничение знака каждой двойной переменной «противоположно» знаку ее основного ограничения. Так " $\geq b_{j}$ " становится $y_{j}\leq 0$ и " $\leq b_{j}$ " становится $y_{j}\geq 0$ и " $=b_{j}$ " становится $y_{j}\in \mathbb {R}$ .
Двойная целевая функция ${\text{minimize }}~~~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}\leq 0$ становится " $\leq c_{i}$ " и $x_{i}\geq 0$ становится " $\geq c_{i}$ " и $x_{i}\in \mathbb {R}$ становится " $=c_{i}$ ".

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

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

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

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

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

Ниже предположим, что основная ЛП — это «максимизировать c ^Тx с учетом [ограничений]», а двойная ЛП — «минимизировать b ^Тy подлежат [ограничениям]».

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

Теорема о слабой двойственности гласит, что для каждого допустимого решения x простого решения и каждого допустимого решения y двойственного: c ^Тх ≤ б ^Тй . Другими словами, объективное значение в каждом допустимом решении двойственного решения является верхней границей объективного значения простого решения, а объективное значение в каждом допустимом решении простого решения является нижней границей объективного значения двойственного решения. Вот доказательство оригинального LP «Maximize c ^Тx при условии A x ≤ b , x ≥ 0":

с ^Тх
= х ^Тc [поскольку это просто скалярное произведение двух векторов]
≤ х ^Т( А ^Ти ) [поскольку A ^Тy ≥ c в силу двойственных ограничений и x ≥ 0]
= ( х ^ТА ^Т) y [по ассоциативности]
= ( Топор ) ^Тy [свойствами транспонирования]
≤ б ^Тy [поскольку A x ≤ b по основным ограничениям]

Слабая двойственность подразумевает:

Макс _х с ^Тх ≤ мин _у б ^Ти

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

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

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

Макс _х с ^Тх = мин _у б ^Ти

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

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

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

Теоретические последствия

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

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

при условии A x ≤ b , A ^Ту ≥ с , с ^Тх ≥ б ^Ту , х ≥ 0, у ≥ 0

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

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

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

Примеры

Крошечный пример

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

{\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}}

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

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

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

Аналогично, минимум двойственного LP достигается, когда y ₁ минимизируется до нижней границы при следующих ограничениях: первое ограничение дает нижнюю границу 3/5, тогда как второе ограничение дает более строгую нижнюю границу 4/6, поэтому фактическая нижняя граница равна 4/6, а минимальная — 7 ⋅ 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}\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.

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

Свернуть: $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}$	(фермер должен получить шиллинга _{не менее 1} за пшеницу )
	$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.

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

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

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

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

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

Неосуществимая программа

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

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

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

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

Рассмотрение решения задачи линейного программирования как (обобщенного) собственного вектора

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

Собственные уравнения квадратной матрицы имеют вид:

${\begin{matrix}\mathbf {p} ^{T}\mathbf {A} =\rho \mathbf {p} ^{T}\\\mathbf {A} \mathbf {z} =\rho {\mathbf {z} }\\\end{matrix}}$

где $\mathbf {p} ^{T}$ и $\mathbf {z}$ — левый и правый собственные векторы квадратной матрицы $\mathbf {A}$ , соответственно, и $\rho$ является собственным значением.

Приведенные выше собственные уравнения для квадратной матрицы можно распространить на модель общего равновесия фон Неймана: ^[5] ^[6]

${\begin{matrix}\mathbf {p} ^{T}\mathbf {A} \geq \rho \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} \mathbf {z} \leq \rho \mathbf {B} {\mathbf {z} }\\\end{matrix}}$

где экономический смысл $\mathbf {p}$ и $\mathbf {z}$ – равновесные цены различных товаров и равновесные уровни активности различных экономических агентов соответственно.

Модель равновесия фон Неймана может быть расширена до следующей модели структурного равновесия с $\mathbf {A}$ и $\mathbf {B}$ как матричные функции: ^[7]

${\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\geq \rho \mathbf {p} ^{T}\mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\\\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\mathbf {z} \leq \rho \mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} ){\mathbf {z} }\\\end{matrix}}$

где экономический смысл $\mathbf {u}$ Это уровни полезности различных потребителей. Частным случаем приведенной выше модели является

${\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)\geq \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} \leq \mathbf {B} {\mathbf {z} }\end{matrix}}$

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

Если мы определим $\mathbf {A} (u)={\begin{bmatrix}\mathbf {0} &u\\\mathbf {A} &\mathbf {0} \\\end{bmatrix}}$ , $\mathbf {B} ={\begin{bmatrix}\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {b} \\\end{bmatrix}}$ , $\mathbf {p} ={\begin{bmatrix}1\\\mathbf {y} \\\end{bmatrix}}$ , $\mathbf {z} ={\begin{bmatrix}\mathbf {x} \\1\\\end{bmatrix}}$ , то модель структурного равновесия можно записать в виде

${\begin{bmatrix}\mathbf {y} ^{T}\mathbf {A} &u\\\end{bmatrix}}\geq {\begin{bmatrix}\mathbf {c} ^{T}&\mathbf {y} ^{T}\mathbf {b} \\\end{bmatrix}}$

${\begin{bmatrix}u\\\mathbf {A} \mathbf {x} \\\end{bmatrix}}\leq {\begin{bmatrix}\mathbf {c} ^{T}\mathbf {x} \\\mathbf {b} \\\end{bmatrix}}$

Давайте проиллюстрируем модель структурного равновесия на ранее обсуждавшемся крошечном примере. В этом примере мы имеем $\mathbf {A} ={\begin{bmatrix}5&6\end{bmatrix}}$ , $\mathbf {A} (u)={\begin{bmatrix}0&0&u\\5&6&0\\\end{bmatrix}}$ и $\mathbf {B} ={\begin{bmatrix}3&4&0\\0&0&7\\\end{bmatrix}}$ .

Для решения модели структурного равновесия получаем ^[8]

$\mathbf {p} ^{*}=(1,2/3)^{T},\quad \mathbf {z} ^{*}=(0,7/6,1)^{T},\quad u^{*}=14/3$

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

Подставим приведенные выше результаты расчета в модель структурного равновесия, получив ${\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)=(10/3,4,14/3)\geq (3,4,14/3)=\mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} =(14/3,7)^{T}\leq (14/3,7)^{T}=\mathbf {B} {\mathbf {z} }\end{matrix}}$

Приложения

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

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

Теорему о минимаксе для игр с нулевой суммой можно доказать с помощью теоремы сильной двойственности. ^[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. Если мы суммируем коэффициенты его ограничений, мы получим a _1,1 y ₁ + a _1,2 y ₂ + ... + a _1,;;n;; у _п + ж ₁ 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$

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

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8 . Страницы 81–104.
^ Сакарович, Мишель (1983), «Дополнения к двойственности: экономическая интерпретация двойных переменных» , Springer Texts in Electrical Engineering , Нью-Йорк, Нью-Йорк: Springer New York, стр. 142–155, ISBN 978-0-387-90829-8 , получено 23 декабря 2022 г.
^ Дорфман, Роберт (1987). Линейное программирование и экономический анализ . Пол А. Самуэльсон, Роберт М. Солоу. Нью-Йорк: Dover Publications. ISBN 0-486-65491-5 . OCLC 16577541 .
^ Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549
^ фон Нейман, Дж. (1945). «Модель общего экономического равновесия». Обзор экономических исследований . 13 : 1–9. :
^ Кемени, Дж.Г.; Моргенштерн, О.; Томпсон, Г.Л. (1956). «Обобщение модели фон Неймана расширяющейся экономики». Эконометрика . 24 : 115–135.
^ Ли, Ву (2019). Общее равновесие и структурная динамика: перспективы новой структурной экономики (на китайском языке). Пекин: Издательство экономической науки. стр. 122–125. ISBN 978-7-5218-0422-5 .
^ «Модель общего равновесия и двойная линейная программа» . Проект КРАН-Р . Проверено 26 июня 2023 г. Подробная документация по модели общего равновесия и двойной линейной программе в R.
^ А.А. Ахмади (2016). «Лекция 6: линейное программирование и сопоставление» (PDF) . Принстонский университет .

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

[2] Сакарович, Мишель (1983), «Дополнения к двойственности: экономическая интерпретация двойных переменных» , Springer Texts in Electrical Engineering , Нью-Йорк, Нью-Йорк: Springer New York, стр. 142–155, ISBN 978-0-387-90829-8 , получено 23 декабря 2022 г.

[3] Дорфман, Роберт (1987). Линейное программирование и экономический анализ . Пол А. Самуэльсон, Роберт М. Солоу. Нью-Йорк: Dover Publications. ISBN 0-486-65491-5 . OCLC 16577541 .

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

[5] фон Нейман, Дж. (1945). «Модель общего экономического равновесия». Обзор экономических исследований . 13 : 1–9. :

[6] Кемени, Дж.Г.; Моргенштерн, О.; Томпсон, Г.Л. (1956). «Обобщение модели фон Неймана расширяющейся экономики». Эконометрика . 24 : 115–135.

[7] Ли, Ву (2019). Общее равновесие и структурная динамика: перспективы новой структурной экономики (на китайском языке). Пекин: Издательство экономической науки. стр. 122–125. ISBN 978-7-5218-0422-5 .

[8] «Модель общего равновесия и двойная линейная программа» . Проект КРАН-Р . Проверено 26 июня 2023 г. Подробная документация по модели общего равновесия и двойной линейной программе в R.

[9] А.А. Ахмади (2016). «Лекция 6: линейное программирование и сопоставление» (PDF) . Принстонский университет .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]