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

Концепция математической оптимизации

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

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

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

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

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

Форма двойной LP

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

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

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

Минимизировать b ^T y при условии A ^T y ≥ c , y ≥ 0

Этот LP называется дуалом оригинального LP.

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

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

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

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

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

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

Минимизировать b ^T y при условии A ^T y ≥ c , y ≥ 0

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

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

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

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

Построение двойной LP

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

• Набор из n переменных: . ${\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 =}$

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

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

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

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

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

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

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

Слабая дуальность

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

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

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

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

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

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

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

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

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

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

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

Теоретические выводы

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

Увеличить 1

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

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

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

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

Примеры

Маленький пример

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

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

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

${\displaystyle {\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. ${\displaystyle 3x_{1}+4x_{2}}$ ${\displaystyle y_{1}}$ ${\displaystyle y_{1}}$ ${\displaystyle y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}}$ ${\displaystyle y_{1}\cdot 5x_{1}\geq 3x_{1}}$ ${\displaystyle y_{1}\cdot 6x_{2}\geq 4x_{2}}$ ${\displaystyle y_{1}\cdot (5x_{1}+6x_{2})\geq 3x_{1}+4x_{2}}$ ${\displaystyle 7y_{1}\geq 3x_{1}+4x_{2}}$

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

Графическое решение примера фермера — после затенения областей, нарушающих условия, вершина оставшейся допустимой области с пунктирной линией, наиболее удаленной от начала координат, дает оптимальную комбинацию (ее расположение на линиях земли и пестицидов подразумевает, что доход ограничен землей и пестицидами, а не удобрениями)

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

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

В матричной форме это принимает вид:

Увеличить: ${\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}$

при условии: ${\displaystyle {\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:

В матричной форме это принимает вид:

Свернуть: ${\displaystyle {\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}}$

при условии: ${\displaystyle {\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 также может быть неограниченным или невыполнимым. Теория двойственности говорит нам, что:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подставим приведенные выше результаты расчета в модель структурного равновесия, получив ${\displaystyle {\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}

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

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

У нас есть m  +  n условий и все переменные неотрицательны. Определим m  +  n дуальных переменных: y _j и s _i . Получаем:

Так как это задача минимизации, мы хотели бы получить двойственную программу, которая является нижней границей основной. Другими словами, мы хотели бы, чтобы сумма всех правых частей ограничений была максимальной при условии, что для каждой основной переменной сумма ее коэффициентов не превышает ее коэффициента в линейной функции. Например, x ₁ появляется в n  + 1 ограничении. Если мы просуммируем коэффициенты ее ограничений, то получим a _1,1 y ₁  +  a _1,2 y ₂  + ... +  a _1,;;n;; y _n  +  f ₁ s ₁ . Эта сумма должна быть не больше c ₁ . В результате мы получаем:

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

Смотрите также

• Выпуклая двойственность
• Двойственность
• Двойственность (оптимизация)
• Полуопределенное программирование
• Релаксация (приближение)

Ссылки

1. Гертнер, Бернд; Матушек, Иржи (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, получено 2022-12-23
3. Дорфман, Роберт (1987). Линейное программирование и экономический анализ. Пол А. Самуэльсон, Роберт М. Солоу. Нью-Йорк: Dover Publications. ISBN 0-486-65491-5. OCLC  16577541.
4. Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1, МР  0859549
5. фон Нейман, Дж. (1945). «Модель общего экономического равновесия». Обзор экономических исследований . 13 : 1–9.:
6. Кемени, Дж. Г.; Моргенштерн, О.; Томпсон, Г. Л. (1956). «Обобщение модели фон Неймана для расширяющейся экономики». Эконометрика . 24 : 115–135.
7. Ли, У (2019). Общее равновесие и структурная динамика: перспективы новой структурной экономики (на китайском языке). Пекин: Economic Science Press. С. 122–125. ISBN 978-7-5218-0422-5.
8. "Модель общего равновесия и двойная линейная программа". Проект CRAN - R. Получено 2023-06-26 . Подробная документация по модели общего равновесия и двойной линейной программе в R.
9. AA Ahmadi (2016). "Лекция 6: линейное программирование и сопоставление" (PDF) . Принстонский университет .