双対単体法#

読み: そうついたんたいほう
英名: Dual Simplex Method

下記のような，標準形の線形計画問題における主問題 (P) および双対問題 (D) を考える．ただし，\(c \in \mathbb{R}^n, b \in \mathbb{R}^m\) とし，変数 \(x, y\) は \(x \in \mathbb{R}^n, y \in \mathbb{R}^m\) とする．

(73)#\[\begin{split}(P) \begin{array}{ll} \min & c^\top x \\ \mathrm{s.t.} & Ax = b, \ x \ge 0 \end{array}\end{split}\]

(74)#\[\begin{split}(D) \begin{array}{ll} \max & b^\top y \\ \mathrm{s.t.} & A^\top y \le c \end{array}\end{split}\]

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

(75)#\[\begin{split}\begin{array}{ll} \mathrm{(i)} & Ax = b, \ x \ge 0 \\ \mathrm{(ii)} & A^\top y \le c \\ \mathrm{(iii)} & x^\top (c - A^\top y) = 0 \end{array}\end{split}\]

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

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