Mathematical optimization concept
与えられた 線形計画法 (LP) の双対 とは 、次の図式的な方法で
元の ( 主 ) LPから導出される別の LP です。
主 LP の各変数は、二重 LP では制約になります。 主 LP の各制約は、二重 LP の変数になります。 客観的な方向は逆転します。つまり、プライマルの最大値はデュアルの最小値になり、その逆も同様です。 弱 双対定理は 、任意の実行可能解における双対LPの目的値は、常に任意の実行可能解における主LPの目的値の境界値（最大化問題か最小化問題かによって上限または下限）となることを述べています。実際、この境界値は、双対LPと主LPの最適値に対して成立します。
強い 双対性定理 によれば、主最適解が存在する場合、双対最適解も存在する。 そして、2つの最適解は等しい 。 [1]
これらの定理は、最適化における双対性定理 のより大きなクラスに属します 。 強い双対性定理は、 双対性ギャップ （主最適値と双対最適値の間のギャップ）が0となる ケースの一つです。
次のような線形計画があるとします。
A x ≤ b 、 x ≥ 0 を条件として c T x を最大化します 。
解の上限を構築したい。そこで、正の係数を持つ制約条件の線形結合を作成し、制約条件における x の係数が少なくとも c T となるようにする。この線形結合によって目的関数の上限が得られる。双対線形結合の変数 y は、この線形結合の係数である。双対線形結合は、得られた上限を 最小化する 係数を見つけようとする。これは以下の線形結合を与える： [1] : 81–83
A T y ≥ c 、 y ≥ 0 を条件として b T y を最小化する
この LP は オリジナル LP のデュアルと呼ばれます。
解釈 双対性定理には経済学的な解釈がある。 [2] [3] 主LPを古典的な「 資源配分 」問題として解釈すると、その双対LPは「資源評価」問題として解釈できる。
原材料 を使って 商品 の生産を計画している工場を考えてみましょう 。商品 を1単位生産するには 、工場は 単位の原材料 を必要とします 。 を 工場の生産スケジュール（ 商品 単位の生産 ）、 を 市場価格（商品1単位の 販売価格 ）、 を 工場が保有する原材料の量（ 原材料 単位を保有 ）とします。制約条件は （負の商品を生産することはできない）、および工場は原材料の量によって許される限りの商品しか生産できない、つまり です 。工場は総収入 を最大化したいと考えています 。 1 , … , n {\displaystyle 1,\ldots ,n} 1 , … , m {\displaystyle 1,\ldots ,m} i {\displaystyle i} A j i ≥ 0 {\displaystyle A_{ji}\geq 0} j {\displaystyle j} x {\displaystyle x} x i {\displaystyle x_{i}} i {\displaystyle i} c ≥ 0 {\displaystyle c\geq 0} i {\displaystyle i} c i {\displaystyle c_{i}} b ≥ 0 {\displaystyle b\geq 0} b j {\displaystyle b_{j}} j {\displaystyle j} x ≥ 0 {\displaystyle x\geq 0} A x ≤ b {\displaystyle Ax\leq b} c ⊤ x {\displaystyle c^{\top }x}
したがって、制約付き収益最大化が主要な LP です。
対象を 最大化する c ⊤ x {\displaystyle c^{\top }x} A x ≤ b , x ≥ 0 {\displaystyle Ax\leq b,x\geq 0}
ここで、前の工場から 原材料の全在庫を購入したい別の工場を考えてみましょう。その工場は （原材料1単位あたり ）の価格ベクトルを提示します 。この提案が受け入れられるためには、 である必要があります。 そうでなければ、最初の工場は、ある製品を生産することで、その製品を生産するために使用した原材料を販売するよりも多くの現金を稼ぐことができるからです。また 、最初の工場は材料をマイナスの価格で販売しないので、 である必要があります。2番目の工場は、最初の工場の原材料の全在庫に対して支払う金額を最小化したいと考えています 。すると、2番目の工場の最適化問題は、次の双対LPになります。 b {\displaystyle b} y {\displaystyle y} i {\displaystyle i} y i {\displaystyle y_{i}} A T y ≥ c {\displaystyle A^{T}y\geq c} y ≥ 0 {\displaystyle y\geq 0} b ⊤ y {\displaystyle b^{\top }y}
対象を 最小限に抑える b ⊤ y {\displaystyle b^{\top }y} A ⊤ y ≥ c , y ≥ 0 {\displaystyle A^{\top }y\geq c,y\geq 0}
双対性定理は、2つのLP問題間の双対性ギャップが非負であることを述べています。言い換えれば、この双対LPの最適解は、 主LPの最適解と 少なくとも 同じ大きさであり、 2番目の工場による最適オファーは常に1番目の工場の最適収益 を下回らないことを意味します 。1番目の工場が、原材料の在庫全体を1品目あたりの価格で購入するというオファーを受け、となる場合、そのオファーを受け入れるべきです。 そうすれば 、完成品を生産した場合と同等以上の収益が得られます。 b ⊤ y {\displaystyle b^{\top }y} c ⊤ x {\displaystyle c^{\top }x} y {\displaystyle y} A ⊤ y ≥ c , y ≥ 0 {\displaystyle A^{\top }y\geq c,y\geq 0}
強い双対性定理はさらに、双対性ギャップがゼロであることを述べています。強い双対性の場合、双対解は、経済的に言えば、完成品の市場価格が与えられた場合、生産マトリックス と原材料在庫 を持つ工場が原材料 として受け入れるであろう 「均衡価格」（ 影の価格 を 参照）です。（は一意ではない可能性があるため、均衡価格は 、 、 によって完全に決定されない可能性があること に 注意 してください 。） y ∗ {\displaystyle y^{*}} A {\displaystyle A} b {\displaystyle b} c {\displaystyle c} y ∗ {\displaystyle y^{*}} A {\displaystyle A} b {\displaystyle b} c {\displaystyle c}
その理由を理解するために、原材料価格が に対して となるような場合を考えてみましょう 。 価格 が「低すぎる」ため 、工場は財 をより多く生産するために、より多くの原材料を購入することになります。逆に、原材料価格が を満たすものの を最小化しない場合 、価格は「高すぎる」ため、工場は財 を生産するよりも原材料を販売する方が利益が大きくなります。均衡価格 では 、工場は原材料の購入や販売によって利益を増やすことはできません。 y ≥ 0 {\displaystyle y\geq 0} ( A T y ) i < c i {\displaystyle (A^{T}y)_{i}<c_{i}} i {\displaystyle i} i {\displaystyle i} A T y ≥ c , y ≥ 0 {\displaystyle A^{T}y\geq c,y\geq 0} b T y {\displaystyle b^{T}y} y ∗ {\displaystyle y^{*}}
双対定理には物理的な解釈もある。 [1] : 86–87
デュアルLPの構築 一般に、主LPが与えられた場合、次のアルゴリズムを使用してその双対LPを構築することができます。 [1] ：85 主LPは次のように定義されます。
n 個 の変数 のセット: 。 x 1 , … , x n {\displaystyle x_{1},\ldots ,x_{n}} 各変数 には 符号 制約 があり、非負 ( )、非正 ( )、または制約なし ( ) のいずれかである必要があります。 x i {\displaystyle x_{i}} x i ≥ 0 {\displaystyle x_{i}\geq 0} x i ≤ 0 {\displaystyle x_{i}\leq 0} x i ∈ R {\displaystyle x_{i}\in \mathbb {R} } 目的関数: maximize c 1 x 1 + ⋯ + c n x n {\displaystyle {\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}} m 個の制約のリスト 。各制約 j は次のようになり ます。 ここで、 の前の記号は、 または またはのいずれかです 。 a j 1 x 1 + ⋯ + a j n x n ⪋ b j {\displaystyle a_{j1}x_{1}+\cdots +a_{jn}x_{n}\lesseqqgtr b_{j}} b j {\displaystyle b_{j}} ≥ {\displaystyle \geq } ≤ {\displaystyle \leq } = {\displaystyle =} デュアル LP は次のように構成されます。
各主制約は双対変数となる。したがって、 変数は m 個存在する。 y 1 , … , y m {\displaystyle y_{1},\ldots ,y_{m}} 各双対変数の符号制約は、その主制約の符号と「反対」です。したがって、「 」は になり 、「 」は になり 、「 」は になります 。 ≥ b j {\displaystyle \geq b_{j}} y j ≤ 0 {\displaystyle y_{j}\leq 0} ≤ b j {\displaystyle \leq b_{j}} y j ≥ 0 {\displaystyle y_{j}\geq 0} = b j {\displaystyle =b_{j}} y j ∈ R {\displaystyle y_{j}\in \mathbb {R} } 双目的関数は minimize b 1 y 1 + ⋯ + b m y m {\displaystyle {\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}} 各主変数は双対制約になります。したがって、 n個の 制約があります。双対変数の双対制約における係数は、その主変数の主制約における係数です。したがって、各制約 i は です。 ここで、 の前の記号は 、主LPにおける変数 i の符号制約と同様です。したがって、 は「 」になり、 は「 」になり、 は「 」になります。 a 1 i y 1 + ⋯ + a m i y m ⪋ c i {\displaystyle a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}} c i {\displaystyle c_{i}} x i ≤ 0 {\displaystyle x_{i}\leq 0} ≤ c i {\displaystyle \leq c_{i}} x i ≥ 0 {\displaystyle x_{i}\geq 0} ≥ c i {\displaystyle \geq c_{i}} x i ∈ R {\displaystyle x_{i}\in \mathbb {R} } = c i {\displaystyle =c_{i}} このアルゴリズムから、双対の双対が主対であることが簡単にわかります。
すべての制約が同じ符号を持つ場合、上記のレシピを行列とベクトルを用いてより簡潔に表現することができます。次の表は、様々な種類のプライマルとデュアルの関係を示しています。
原始的 デュアル 注記 A x ≤ b 、 x ≥ 0 を条件として c T x を最大化する A T y ≥ c 、 y ≥ 0 を条件として b T y を最小化する これは「対称的」双対問題と呼ばれる。 A x ≤ b を条件として c T x を最大化する A T y = c , y ≥ 0 を条件として b T y を最小化する これは「非対称」双対問題と呼ばれる。 A x = b 、 x ≥ 0 を条件として c T x を最大化する A T y ≥ c を条件として b T y を最小化する
双対定理 以下では、主 LP が「 [制約] に従って c T x を 最大化する」であり、双対 LP が「 [制約] に従って b T y を最小化する」であると仮定します。
弱い双対性 弱 双対定理は 、主対の あらゆる実行可能解 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であるため] 弱い双対性は次を意味します。
最大 x c T x ≤ 最小 y b T y
特に、主問題が（上から）無限大である場合、双対問題には実行可能な解がなく、双対問題が（下から）無限大である場合、主問題には実行可能な解がありません。
強い二重性 強い 双対性定理に よれば、2 つの問題のうちの 1 つに最適解がある場合、もう 1 つにも最適解があり、弱い双対性定理によって与えられる境界は厳密です。つまり、
最大 x c T x = 最小 y b T y
強い双対性定理は証明がより困難であり、証明では通常、弱い双対性定理がサブルーチンとして使用されます。
一つの証明は 単体法 を用いており、適切なピボットルールを用いれば正しい解が得られるという証明に基づいています。この証明は、単体法が主LPの解で終了すると、最終テーブルから双対LPの解を読み取ることができることを示しています。つまり、単体法を実行することで、主LPと双対LPの両方の解を同時に得ることができるのです。 [1] : 87–89
別の証明では ファーカスの補題 が用いられる。 [1] : 94
理論的含意 1. 弱双対定理は、 単一の 実行可能解を見つけることは、 最適な 実行可能解を見つけることと同じくらい難しいことを意味します。仮に、あるLPが与えられたときに、任意の実行可能解（もし存在するならば）を見つけるオラクルがあるとします。「 A x ≤ b , x ≥ 0 を条件として c T x を最大化する」というLPが与えられたとします。この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の最適値であることを容易に証明することを可能にする。証明は2つのステップで進行する。 [4] : 260–261
値t を持つ主 LP の実行可能な解を示します 。これにより、最適値は少なくとも t であることが証明されます。 値t を持つデュアル LP の実行可能なソリューションを示します 。これにより、最適値は最大でも t であることが証明されます。
例
小さな例 2 つの変数と 1 つの制約を持つ基本 LP を考えてみましょう。
maximize 3 x 1 + 4 x 2 subject to 5 x 1 + 6 x 2 = 7 x 1 ≥ 0 , x 2 ≥ 0 {\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}}} 上記のレシピを適用すると、1 つの変数と 2 つの制約を持つ次のデュアル LP が生成されます。
minimize 7 y 1 subject to 5 y 1 ≥ 3 6 y 1 ≥ 4 y 1 ∈ R {\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の最大値は、制約条件(7/6)の下で、 x 1 がその下限値(0)に最小化され、 x 2 が その上限値(7/6)に最大化されたときに達成されることが容易に分かります。最大値は4 ⋅ 7/6 = 14/3です。
同様に、制約の下でy 1 が下限に最小化されると、双対 LP の最小値が達成されます 。最初の制約では下限が 3/5 になりますが、2 番目の制約ではより厳しい下限が 4/6 になります。したがって、実際の下限は 4/6 になり、最小値は 7 ⋅ 4/6 = 14/3 になります。
強い双対性定理によれば、主値の最大値は双対値の最小値に等しくなります。
この例を用いて、弱双対定理の証明を説明します。主LPにおいて、目的関数 の上限を求めたいとします 。制約条件 に何らかの係数、例えば を乗じたものを使用できます 。任意の に対して、 が得られます 。ここで、 かつ ならば 、 となるので 、 となります 。したがって、双対LPの目的関数は、主LPの目的関数の上限となります。 3 x 1 + 4 x 2 {\displaystyle 3x_{1}+4x_{2}} y 1 {\displaystyle y_{1}} y 1 {\displaystyle y_{1}} y 1 ⋅ ( 5 x 1 + 6 x 2 ) = 7 y 1 {\displaystyle y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}} y 1 ⋅ 5 x 1 ≥ 3 x 1 {\displaystyle y_{1}\cdot 5x_{1}\geq 3x_{1}} y 1 ⋅ 6 x 2 ≥ 4 x 2 {\displaystyle y_{1}\cdot 6x_{2}\geq 4x_{2}} y 1 ⋅ ( 5 x 1 + 6 x 2 ) ≥ 3 x 1 + 4 x 2 {\displaystyle y_{1}\cdot (5x_{1}+6x_{2})\geq 3x_{1}+4x_{2}} 7 y 1 ≥ 3 x 1 + 4 x 2 {\displaystyle 7y_{1}\geq 3x_{1}+4x_{2}}
農家の例 農家の例に対するグラフィカルな解決法 – 条件に違反する領域を塗りつぶした後、残りの 実現可能な領域 の頂点と原点から最も遠い破線が最適な組み合わせを示します（土地と農薬の線上にあるため、収益は肥料ではなく土地と農薬によって制限されます）。 土地（L） 、 肥料 （F） 、農薬 （P） という一定の条件で小麦と大麦を栽培する農家を考えてみましょう 。小麦1単位を栽培するには、土地1単位、 肥料1単位、 農薬1単位を使用する必要があります。同様に、大麦1単位を栽培するには、土地1単位、 肥料1単位、 農薬1単位を使用する必要があります。 F 1 {\displaystyle F_{1}} P 1 {\displaystyle P_{1}} F 2 {\displaystyle F_{2}} P 2 {\displaystyle P_{2}}
根本的な問題は、売価が と の場合に、農家が小麦 ( ) と大麦 ( ) をどれだけ栽培するかを 決める こと です 。 x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} S 1 {\displaystyle S_{1}} S 2 {\displaystyle S_{2}}
最大化: S 1 ⋅ x 1 + S 2 ⋅ x 2 {\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}} （小麦と大麦の生産による収益を最大化する） 以下を条件とする: x 1 + x 2 ≤ L {\displaystyle x_{1}+x_{2}\leq L} （利用可能な土地以上の土地は使用できません） F 1 ⋅ x 1 + F 2 ⋅ x 2 ≤ F {\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F} （利用可能な肥料以上のものを使用することはできません） P 1 ⋅ x 1 + P 2 ⋅ x 2 ≤ P {\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P} （利用可能な農薬以上の農薬を使用することはできません） x 1 , x 2 ≥ 0 {\displaystyle x_{1},x_{2}\geq 0} (小麦や大麦の量がマイナスになることはありません)。
行列形式では、次のようになります。
最大化: [ S 1 S 2 ] [ x 1 x 2 ] {\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}} 以下を条件とする: [ 1 1 F 1 F 2 P 1 P 2 ] [ x 1 x 2 ] ≤ [ L F P ] , [ x 1 x 2 ] ≥ 0. {\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 1 、大麦については S 2 という、それぞれの作物（産出物）の単価の下限値を設定しながら、設定された投入物の調達にかかる総費用を最小化することである 。これは以下のLPに対応する。
最小化: L ⋅ y L + F ⋅ y F + P ⋅ y P {\displaystyle L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}} （「目的関数」として生産手段の総費用を最小化する） 以下を条件とする: y L + F 1 ⋅ y F + P 1 ⋅ y P ≥ S 1 {\displaystyle y_{L}+F_{1}\cdot y_{F}+P_{1}\cdot y_{P}\geq S_{1}} （農家は 小麦に対して
最低でも S1 を受け取らなければならない） y L + F 2 ⋅ y F + P 2 ⋅ y P ≥ S 2 {\displaystyle y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geq S_{2}} （農家は 大麦に対して S2 以上を受け取らなければならない） y L , y F , y P ≥ 0 {\displaystyle y_{L},y_{F},y_{P}\geq 0} (価格は負の値にはできません)。
行列形式では、次のようになります。
最小化: [ L F P ] [ y L y F y P ] {\displaystyle {\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}} 以下を条件とする: [ 1 F 1 P 1 1 F 2 P 2 ] [ y L y F y P ] ≥ [ S 1 S 2 ] , [ y L y F y P ] ≥ 0. {\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は非有界または実行不可能となることもあります。双対理論によれば、次のようになります。
主項が無限である場合、双対項は実行不可能です。 双対が無限である場合、主は実行不可能です。 しかし、双対性と原始性の両方が実現不可能となる可能性はあります。以下に例を示します。
最大化: 2 x 1 − x 2 {\displaystyle 2x_{1}-x_{2}} 以下を条件とする: x 1 − x 2 ≤ 1 {\displaystyle x_{1}-x_{2}\leq 1} − x 1 + x 2 ≤ − 2 {\displaystyle -x_{1}+x_{2}\leq -2} x 1 , x 2 ≥ 0. {\displaystyle x_{1},x_{2}\geq 0.}
線形計画問題の解を（一般化された）固有ベクトルとして見る 線形計画問題、固有方程式、そしてフォン・ノイマンの一般均衡モデルの間には密接な関連があります。線形計画問題の解は、一般化固有ベクトルとみなすことができます。
正方行列の固有方程式は次のとおりです。
p T A = ρ p T A z = ρ z {\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} =\rho \mathbf {p} ^{T}\\\mathbf {A} \mathbf {z} =\rho {\mathbf {z} }\\\end{matrix}}}
ここで 、 と はそれぞれ正方行列 の左固有ベクトルと右固有ベクトルであり 、 は固有値です。 p T {\displaystyle \mathbf {p} ^{T}} z {\displaystyle \mathbf {z} } A {\displaystyle \mathbf {A} } ρ {\displaystyle \rho }
上記の正方行列の固有方程式はフォン・ノイマンの一般均衡モデルに拡張できる： [5] [6]
p T A ≥ ρ p T B A z ≤ ρ B z {\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}}}
ここで、および の経済的意味は 、それぞれさまざまな財の均衡価格とさまざまな経済主体の均衡活動水準です。 p {\displaystyle \mathbf {p} } z {\displaystyle \mathbf {z} }
フォン・ノイマンの平衡モデルは、行列値関数としておよびを持つ次の構造平衡モデルにさらに拡張することができる： [ 7 ] A {\displaystyle \mathbf {A} } B {\displaystyle \mathbf {B} }
p T A ( p , u , z ) ≥ ρ p T B ( p , u , z ) A ( p , u , z ) z ≤ ρ B ( p , u , z ) z {\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}}}
ここで、の経済的意味は 様々な消費者の効用水準である。上記のモデルの特別なケースは u {\displaystyle \mathbf {u} }
p T A ( u ) ≥ p T B A ( u ) z ≤ B z {\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}}}
この形式の構造均衡モデルと線形計画問題は、多くの場合相互に変換できます。つまり、これら 2 種類の問題の解決策は、多くの場合一貫しています。
、、、 を 定義すると 、 構造平衡モデルは次のように書ける。 A ( u ) = [ 0 u A 0 ] {\displaystyle \mathbf {A} (u)={\begin{bmatrix}\mathbf {0} &u\\\mathbf {A} &\mathbf {0} \\\end{bmatrix}}} B = [ c T 0 0 b ] {\displaystyle \mathbf {B} ={\begin{bmatrix}\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {b} \\\end{bmatrix}}} p = [ 1 y ] {\displaystyle \mathbf {p} ={\begin{bmatrix}1\\\mathbf {y} \\\end{bmatrix}}} z = [ x 1 ] {\displaystyle \mathbf {z} ={\begin{bmatrix}\mathbf {x} \\1\\\end{bmatrix}}}
[ y T A u ] ≥ [ c T y T b ] {\displaystyle {\begin{bmatrix}\mathbf {y} ^{T}\mathbf {A} &u\\\end{bmatrix}}\geq {\begin{bmatrix}\mathbf {c} ^{T}&\mathbf {y} ^{T}\mathbf {b} \\\end{bmatrix}}}
[ u A x ] ≤ [ c T x b ] {\displaystyle {\begin{bmatrix}u\\\mathbf {A} \mathbf {x} \\\end{bmatrix}}\leq {\begin{bmatrix}\mathbf {c} ^{T}\mathbf {x} \\\mathbf {b} \\\end{bmatrix}}}
先ほど述べた小さな例を用いて、構造平衡モデルを説明しましょう。この例では、、およびが存在 し ます 。 A = [ 5 6 ] {\displaystyle \mathbf {A} ={\begin{bmatrix}5&6\end{bmatrix}}} A ( u ) = [ 0 0 u 5 6 0 ] {\displaystyle \mathbf {A} (u)={\begin{bmatrix}0&0&u\\5&6&0\\\end{bmatrix}}} B = [ 3 4 0 0 0 7 ] {\displaystyle \mathbf {B} ={\begin{bmatrix}3&4&0\\0&0&7\\\end{bmatrix}}}
構造平衡モデルを解くと、 [8]が得られる。
p ∗ = ( 1 , 2 / 3 ) T , z ∗ = ( 0 , 7 / 6 , 1 ) T , u ∗ = 14 / 3 {\displaystyle \mathbf {p} ^{*}=(1,2/3)^{T},\quad \mathbf {z} ^{*}=(0,7/6,1)^{T},\quad u^{*}=14/3}
これらは線形計画問題の解と一致しています。
上記の計算結果を構造平衡モデルに代入すると、 p T A ( u ) = ( 10 / 3 , 4 , 14 / 3 ) ≥ ( 3 , 4 , 14 / 3 ) = p T B A ( u ) z = ( 14 / 3 , 7 ) T ≤ ( 14 / 3 , 7 ) T = B z {\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] : sub.8.1
代替アルゴリズム 場合によっては、プログラム行列を見ずに双対計画を求める方が直感的に分かりやすいかもしれません。次の線形計画を考えてみましょう。
最小化 ∑ i = 1 m c i x i + ∑ j = 1 n d j t j {\displaystyle \sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}} 対象となる ∑ i = 1 m a i j x i + e j t j ≥ g j , {\displaystyle \sum _{i=1}^{m}a_{ij}x_{i}+e_{j}t_{j}\geq g_{j},} 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n} f i x i + ∑ j = 1 n b i j t j ≥ h i , {\displaystyle f_{i}x_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\geq h_{i},} 1 ≤ i ≤ m {\displaystyle 1\leq i\leq m} x i ≥ 0 , t j ≥ 0 , {\displaystyle x_{i}\geq 0,\,t_{j}\geq 0,} 1 ≤ i ≤ m , 1 ≤ j ≤ n {\displaystyle 1\leq i\leq m,1\leq j\leq n}
m + n 個の条件があり 、すべての変数は非負です。m + n 個の双対変数 y j と s i を定義します 。 すると 、 次 の よう に なり ます 。
最小化 ∑ i = 1 m c i x i + ∑ j = 1 n d j t j {\displaystyle \sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}} 対象となる ∑ i = 1 m a i j x i ⋅ y j + e j t j ⋅ y j ≥ g j ⋅ y j , {\displaystyle \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 ≤ j ≤ n {\displaystyle 1\leq j\leq n} f i x i ⋅ s i + ∑ j = 1 n b i j t j ⋅ s i ≥ h i ⋅ s i , {\displaystyle 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 ≤ i ≤ m {\displaystyle 1\leq i\leq m} x i ≥ 0 , t j ≥ 0 , {\displaystyle x_{i}\geq 0,\,t_{j}\geq 0,} 1 ≤ i ≤ m , 1 ≤ j ≤ n {\displaystyle 1\leq i\leq m,1\leq j\leq n} y j ≥ 0 , s i ≥ 0 , {\displaystyle y_{j}\geq 0,\,s_{i}\geq 0,} 1 ≤ j ≤ n , 1 ≤ i ≤ m {\displaystyle 1\leq j\leq n,1\leq i\leq m}
これは最小化問題なので、主変数の下限となる双対計画を求めたい。言い換えれば、各主変数の係数の合計が 線形関数の係数を超えないという条件の下で、制約条件の右辺すべての和が最大となるようにしたい。例えば、 x 1 は n + 1個の制約条件に現れる 。その制約条件の係数を合計すると、 a 1,1 y 1 + a 1,2 y 2 + ... + a 1,;;n;; y n + f 1 s 1 となる。この和は最大でも c 1 でなければならない。結果として、以下のようになる。
最大化 ∑ j = 1 n g j y j + ∑ i = 1 m h i s i {\displaystyle \sum _{j=1}^{n}g_{j}y_{j}+\sum _{i=1}^{m}h_{i}s_{i}} 対象となる ∑ j = 1 n a i j y j + f i s i ≤ c i , {\displaystyle \sum _{j=1}^{n}a_{ij}y_{j}+f_{i}s_{i}\leq c_{i},} 1 ≤ i ≤ m {\displaystyle 1\leq i\leq m} e j y j + ∑ i = 1 m b i j s i ≤ d j , {\displaystyle e_{j}y_{j}+\sum _{i=1}^{m}b_{ij}s_{i}\leq d_{j},} 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n} y j ≥ 0 , s i ≥ 0 , {\displaystyle y_{j}\geq 0,\,s_{i}\geq 0,} 1 ≤ j ≤ n , 1 ≤ i ≤ m {\displaystyle 1\leq j\leq n,1\leq i\leq m}
計算手順では、プログラムが標準形であると仮定していることに注意してください。ただし、任意の線形計画法は標準形に変換できるため、これは制限要因ではありません。
参照
参考文献 ^ abcdefg ゲルトナー、ベルント; マトウシェク、イジー (2006)。 線形計画法の理解と使用 。ベルリン：シュプリンガー。 ISBN 3-540-30697-8 。 81～104ページ。 ^ Sakarovitch, Michel (1983), 双対性の補完：双対変数の経済的解釈 、Springer Texts in Electrical Engineering、ニューヨーク、NY：Springer New York、pp. 142– 155、 doi ：10.1007/978-1-4757-4106-3_9、 ISBN 978-0-387-90829-8 、 2022年12月23日 閲覧 ^ ドーフマン、ロバート (1987). 線形計画法と経済分析 . ポール・A・サミュエルソン、ロバート・M・ソロー. ニューヨーク: Dover Publications. ISBN 0-486-65491-5 . OCLC 16577541。 ^ ロヴァシュ、ラズロ ; プラマー医学博士 (1986 年)、 『マッチング理論』 、『離散数学年報』、第 1 巻。 29、北オランダ、 ISBN 0-444-87916-1 、 MR 0859549 ^ フォン・ノイマン、J. (1945). 「一般経済均衡モデル」 『経済研究 』 13 : 1–9 . : ^ Kemeny, JG; Morgenstern, O.; Thompson, GL (1956). 「拡大経済のフォン・ノイマン・モデルの一般化」. Econometrica . 24 : 115–135 . ^ 李、呉（2019）『 一般均衡と構造動学：新構造経済学の展望』 （中国語）北京：経済科学出版社、pp. 122– 125. ISBN 978-7-5218-0422-5 。 ^ 「一般均衡モデルと双対線形計画」。CRAN - Rプロジェクト 。 2023年6月26日 閲覧。R における一般均衡モデルと双対線形計画に関する詳細なドキュメント。 ^ AA Ahmadi (2016). 「講義6：線形計画法とマッチング」 （PDF） . プリンストン大学 . 
