線形計画法の強双対定理

内容

主問題 $\min\ c^\top x$（制約 $Ax \ge b,\ x \ge 0$）と双対問題 $\max\ b^\top y$（制約 $A^\top y \le c,\ y \ge 0$）を考える。どちらか一方に最適解が存在すれば他方にも存在し、最適値は等しい：$c^\top x^* = b^\top y^*$。

なぜ正しいのか?

弱双対性は常に成り立つ：双対問題の任意の実行可能値は主問題の任意の実行可能値の下界となる。買い手の提示額が資源の真の価値を超えないのと同じ構図である。強双対定理は、最適点でこの差がちょうどゼロになることを主張する——双対変数は各制約資源の公正な『シャドープライス』として働き、すべての資源をシャドープライスで評価すると、主問題の最良コストと過不足なく一致する。

この定理を使うトピック

関連する定理

ステップごとの証明

この定理のステップごとの証明はまだありません。