線形計画における双対性
線形計画法（LP）は、要件が線形関係で表される数学モデルで最良の結果を得るための手法です。これは最適化に使用される手法で、線形制約のセットに従って線形目的関数を最小化または最大化することを目指します。線形計画の重要な側面は双対性の概念であり、最適化関数の動作に対する深い洞察を提供します。
双対性の基本
線形計画では、すべての最適化問題に対応する双対問題があります。元の問題を「一次問題」と呼ぶ場合、その対応物は「双対問題」として知られています。双対性は強力な洞察を提供します - 一方の問題の最適解を他方の解を調べることで見つけることができます。
線形計画における双対性について主に2つの結果があります：
- 弱い双対性: 双対性の目的関数の値は、どの実行可能解においても元の問題の目的関数の値以上です。
- 強い双対性: もし一次問題と双対性が共に最適解を持つ場合、一次の目的関数の最適値は双対性のそれと等しい。
一次問題と双対問題
一次問題
最大化: c1x1 + c2x2 + ... + cnxn
対象: a11x1 + a12x2 + ... + a1nxn ≤ b1
a21x1 + a22x2 + ... + a2nxn ≤ b2
,
am1x1 + am2x2 + ... + amnxn ≤ bm
x1, x2, ..., xn ≥ 0
双対問題
最小化: b1y1 + b2y2 + ... + bmym
対象: a11y1 + a21y2 + ... + am1ym ≥ c1
a12y1 + a22y2 + ... + am2ym ≥ c2
,
a1ny1 + a2ny2 + ... + amnym ≥ cn
y1, y2, ..., ym ≥ 0
解釈と経済的意味
一次問題では、資源制約によって課せられた条件を満たしながら得られる最大の利益（または利益）を決定することを目的としています。各決定変数は可能な活動または戦略を表し、制約はこれらの活動に必要な資源の限界を表しています。
一方、双対問題は、総利益の所望の水準を達成または超えるために必要な最小コストを追求します。ここでは、決定変数はシャドウプライス、つまり一次最適化問題の各制約を最小化する価格として解釈できます。双対性は一種の均衡価格システムを提供します。
幾何学的解釈
より簡単に視覚化するために2次元空間を考えます。一次と双対の問題の両方で、解は実行可能領域の頂点（コーナー）にあります。対応する一次と双対の不等式は幾何学的領域を定義し、それらの交点が一次と双対の問題の双方の最適解を保持する可能性があります。
補完的怠惰の原理
一次と双対の定式化を結び付ける重要な要素は補完的緩和の概念です。これは、一次とその双対が共に最適解を持つ場合に保持されるべき条件から成ります。一次と双対の制約のペアごとに補完的緩和条件が満たされなければなりません：
もし xj > 0 ならば、jth 双対条件は厳密です; もし i番目のバイナリ制約が緩和されるならば、ith 基本変数はゼロです。
したがって、元の問題の制約が緩和される場合、その双対の対応変数は最適性においてゼロ価でなければなりません。
双対性の例
サンプル基礎問題
最大化 z = 2x1 + 3x2
対象:
x1 + 2x2 ≤ 10
2x1 + x2 ≤ 8
x1, x2 ≥ 0
互換性のある双対問題
最小化 w = 10y1 + 8y2
対象:
y1 + 2y2 ≥ 2
2y1 + y2 ≥ 3
y1, y2 ≥ 0
応用と意義
双対性の概念は理論的なだけでなく、重要な実践的な意味も持ちます。それにより、より単純な問題の解から他の問題の解を導き出すことが可能になります。双対性は、経済学、工学、軍事科学、運輸などの様々な分野で使用されています。
例えば、経済学では、双対問題は価格の最適化と資源配分についての情報を提供します。双対解は追加資源にどれだけの価値を置くべきかを示し、意思決定者にとって貴重な価格情報を提供します。
結論
線形計画における双対性は、異なる最適化アプローチの間のギャップを埋め、複雑な問題を解決する上での深い理解と効率を可能にします。学術的な関心のためであれ、実用的な解決のためであれ、線形計画技術を最大限に活用するためには、双対性の概念を理解することが重要です。
コメント