トップ > 数理計画用語集 > 双対単体法

数理計画用語集

双対単体法

読み:そうついたんたいほう
英名:Dual Simplex Method
関連双対定理

下記のような,標準形線形計画問題における主問題(P)および双対問題(D)を考える.ただし,equation とし,変数equationequation とする.

(P) equation (D) equation

このとき,線形計画問題の最適条件は以下が成り立つことである.

equation

主単体法(一般的に単体法と言われるアルゴリズム)は,(i) と (iii) を満たしながら (ii) を満たそうとするアルゴリズムと言える.双対単体法とは,(ii) と (iii) を満たしながら (i) を満たそうとするアルゴリズムである.これは双対問題(D)に主単体法を適用しているとも解釈できる.

双対単体法は,制約式の追加を行った際に,追加前の情報を用いて効率良く求解が行える.このため,整数計画問題における分枝限定法などでよく使われている.

[参考]
今野浩, 線形計画法, 日科技連, 1987