双対線形計画法

双対性定理には経済学的な解釈がある。^{[ 2 ] [ 3 ]}主問題である線形計画問題を古典的な「資源配分」問題として解釈すると、その双対問題である線形計画問題は「資源評価」問題として解釈できる。

製品の生産を計画している工場を考えてみましょう。${\displaystyle 1,\ldots ,n}$原材料を使用して製造${\displaystyle 1,\ldots ,m}$1単位の製品を生産するには${\displaystyle i}$工場は${\displaystyle A_{ji}\geq 0}$原材料の単位${\displaystyle j}$。 させて${\displaystyle x}$工場の生産スケジュール（生産）${\displaystyle x_{i}}$商品の単位${\displaystyle i}$）、 させて${\displaystyle c\geq 0}$市場価格（財の単位）${\displaystyle i}$販売可能${\displaystyle c_{i}}$)、そして${\displaystyle b\geq 0}$工場が利用できる原材料の量（工場は${\displaystyle b_{j}}$原材料の単位${\displaystyle j}$制約条件は、${\displaystyle x\geq 0}$（負の財は生産できない）、そして工場は原材料の量によって許されるだけの財しか生産できない、つまり、${\displaystyle Ax\leq b}$工場は総収益を最大化したいと考えている。${\displaystyle c^{\top }x}$。

したがって、制約付き収益最大化問題が主問題である。

最大化する${\displaystyle c^{\top }x}$ 対象${\displaystyle Ax\leq b,x\geq 0}$

次に、原材料の在庫すべてを購入したいと考えている別の工場について考えてみましょう。${\displaystyle b}$前の工場から。価格ベクトルを提供します${\displaystyle y}$（原材料の単位）${\displaystyle i}$のために$\displaystyle y_{i}}$) 申し出が受け入れられるためには、以下の条件を満たす必要があります。${\displaystyle A^{T}y\geq c}$そうでなければ、最初の工場は、特定の製品を生産することで、その製品の製造に使用した原材料を販売するよりも多くの現金を得ることができるからです。また、$y ≥ 0$最初の工場はマイナスの価格で材料を販売しないため、2番目の工場は量を最小限に抑えたいと考えている。${\displaystyle b^{\top }y}$それは、最初の工場の原材料在庫全体を支払うことを意味します。すると、2番目の工場の最適化問題は、次の双対線形計画問題になります。

最小化する ${\displaystyle b^{\top }y}$対象${\displaystyle A^{\top }y\geq c,y\geq 0}$

双対性定理は、2 つの LP 問題間の双対性ギャップが非負であることを述べています。言い換えれば、この双対 LP の最適解は、少なくとも主 LP の最適解と同じ大きさであり、つまり、最適オファーは${\displaystyle b^{\top }y}$第二工場の収益は常に第一工場の最適収益を下回らない${\displaystyle c^{\top }x}$最初の工場が原材料の全在庫を1品あたりで買い取るという申し出を受けた場合、${\displaystyle y}$、したがって${\displaystyle A^{\top }y\geq c,y\geq 0}$それならば、その提案を受け入れるべきだ。完成品を生産するのと同等以上の収益が得られるだろう。

強双対性定理はさらに、双対性ギャップがゼロであることを述べている。強双対性により、双対解は$\displaystyle y^{*}}$経済学的に言えば、生産マトリックスを持つ工場が調達する原材料の「均衡価格」（シャドウプライスを参照）である。${\displaystyle A}$原材料在庫${\displaystyle b}$完成品の市場価格を考慮すると、原材料として受け入れられるだろう${\displaystyle c}$。 （ご了承ください$\displaystyle y^{*}}$一意ではない可能性があるため、均衡価格は完全に決定されない可能性があります。${\displaystyle A}$、${\displaystyle b}$、 そして${\displaystyle c}$）

その理由を理解するために、原材料価格が$y ≥ 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}

弱双対性定理によれば、主問題の各実行可能解xと双対問題の 各実行可能解yに対して、 c ^T x ≤ b ^T yが成り立ちます。言い換えれば、双対問題の各実行可能解における目的値は主問題の目的値の上限であり、主問題の各実行可能解における目的値は双対問題の目的値の下限です。以下は、主問題 LP「制約条件A x ≤ b、x ≥ 0 の下でc ^T xを最大化する」の証明です。

• c ^T x
• = x ^T c [これは2つのベクトルのスカラー積にすぎないため]
• ≤ 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であり、 y ≥ 0 であるため]

弱い双対性は以下を意味する：

max _x c ^T x ≤ min _y b ^T y

特に、主問題が（上から）非有界である場合、双対問題には実行可能な解がなく、双対問題が（下から）非有界である場合、主問題には実行可能な解がない。

強双対性定理は、2つの問題のうち一方に最適解が存在する場合、もう一方にも最適解が存在し、弱双対性定理によって与えられる境界はタイトである、すなわち、

max _x c ^T x = min _y b ^T y

強双対性定理は証明がより難しく、証明では通常、弱双対性定理が補助的な役割を果たします。

ある証明では、シンプレックス法を用い、適切なピボット規則を用いることで正しい解が得られるという証明に基づいている。この証明では、シンプレックス法が主問題LPの解を導き出した後、最終タブローから双対問題LPの解を読み取ることができることが示されている。したがって、シンプレックス法を実行することで、主問題と双対問題の両方の解を同時に得ることができる。^{[ 1 ]： 87-89}

別の証明ではファルカス補題を用いる。^{[ 1 ] : 94}

1. 弱双対性定理は、単一の実行可能解を見つけることが、最適な実行可能解を見つけることと同じくらい難しいことを示唆しています。LPが与えられたときに、任意の実行可能解（存在する場合）を見つけるオラクルがあると仮定します。LP「A x ≤ b、x ≥ 0 の制約 の下でc ^T xを最大化する」が与えられた場合、この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. 強双対性定理は、ある値tがある線形計画問題の最適値であることを容易に証明できるという意味で、線形計画問題の最適値の「優れた特徴付け」を提供する。証明は2つのステップで進む。^{[ 4 ]： 260-261}

• 主問題LPの実行可能な解を値tで示します。これにより、最適値が少なくともtであることが証明されます。
• 双対線形計画問題の実行可能な解を値tで示します。これにより、最適値が最大でtであることが証明されます。

2つの変数と1つの制約を持つ主問題線形計画問題を考えてみましょう。

${\displaystyle {\begin{aligned}{\text{最大化}}&3x_{1}+4x_{2}\\{\text{制約条件}}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}}$

上記の手順を適用すると、変数1つと制約2つを持つ以下の双対線形計画問題が得られます。

${\displaystyle {\begin{aligned}{\text{最小化}}&7y_{1}\\{\text{制約条件}}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}}$

制約条件 (7/6) の下で、 x ₁を下限 (0) まで最小化し、x ₂を上限まで最大化したときに、主問題の LP の最大値が得られることは容易にわかります。最大値は 4 ⋅ 7/6 = 14/3 です。    

同様に、双対LPの最小値は、制約の下でy1をその下限値まで最小化したときに達成されます。_最初の制約は下限値を3/5とし、2番目の制約はより厳しい下限値を4/6とするため、実際の下限値は4/6となり、最小値は7 ⋅ 4/6 = 14/3となります。  

強双対性定理によれば、主問題の最大値は双対問題の最小値に等しい。

この例を用いて、弱双対性定理の証明を説明します。主問題である線形計画問題において、目的関数の上限値を求めたいとします。$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}}$$、 それで$7y_1 ≥ 3x_1 + 4x_2$したがって、双対線形計画問題の目的は、主線形計画問題の目的の上限となる。

一定のLの土地、Fの肥料、Pの農薬の供給を受けて小麦と大麦を栽培する農家を考えてみましょう。小麦1単位、土地1単位、${\displaystyle F_{1}}$肥料の単位と${\displaystyle P_{1}}$単位の農薬を使用しなければなりません。同様に、1単位の大麦を栽培するには、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と設定されると仮定します。計画委員会の役割は、設定された量の投入物を調達する総コストを最小限に抑えつつ、農家に対して各作物（産出物）の単価の下限（小麦の場合はS1 、大麦の場合は_S2 ）_を提供することです。これは、次の線形計画問題に対応します。

行列形式で表すと次のようになります。

最小化:${\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.}$

主問題は物理量に関するものです。すべての投入要素が限られた量しか利用できず、すべての産出物の単価が既知であると仮定した場合、総収入を最大化するために、どの量の産出物を生産すべきでしょうか？ 副次問題は経済価値に関するものです。すべての産出物の単価に最低保証価格が設定され、すべての投入要素の入手可能量が既知であると仮定した場合、総支出を最小化するために、どの投入要素の単価設定方式を設定すべきでしょうか？

主空間の各変数には、出力タイプによってインデックス付けされた双対空間で満たすべき不等式が対応します。主空間の各不等式には、入力タイプによってインデックス付けされた双対空間の変数が対応します。

主空間における不等式を制約する係数は、双対空間における目的関数（この例では入力量）を計算するために使用されます。主空間における目的関数を計算するために使用される係数は、双対空間における不等式（この例では出力単価）を制約します。

主問題と双対問題はどちらも同じ行列を使用する。主問題空間では、この行列は、一定量の産出物を生産するために必要な投入物の物理量の消費量を表す。双対問題空間では、この行列は、一定量の投入物の単価から産出物に関連付けられた経済的価値の創出を表す。

各不等式は等式とスラック変数に置き換えることができるため、各主変数は双対スラック変数に対応し、各双対変数は主スラック変数に対応する。この関係により、相補的スラック性について議論することができる。

線形計画問題は、非有界または実行不可能な場合もある。双対性理論によれば、次のようになる。

• 主問題が非有界であれば、双対問題は実行不可能である。
• 双対が非有界である場合、主問題は実行不可能である。

しかし、双対問題と主問題の両方が実行不可能となる可能性もある。以下に例を示す。