単体法#

読み: たんたいほう
英名: Simplex Method
別名: シンプレックス法

単体法は，元来線形計画問題を解くため 1947 年に Dantzig が提案した解法のことであり，シンプレックス法とも呼ばれている [2, 1]．

線形計画問題に対する単体法は，最適解においては変数が「基底変数」と「非基底変数」の二種類に分割される，という性質に基づいたアルゴリズムである．

具体的には，以下のような標準形を考える．

(90)#\[\begin{split}\begin{aligned} \min & \ c^{\top} {x} \\ s.t. & \ Ax = b \\ & \ x \geq 0 \end{aligned}\end{split}\]

変数集合 \(I\) は基底変数集合 \(B\) 及び非基底変数集合 \(N\) に分割され，係数行列が \(A = ({B}, {N})\) と分割されるとすると，最適解 \(x^*\) はある基底変数集合に対して \(x = (x_B, x_N) = (0, {B}^{-1} {b})\) と表すことができる．単体法ではこの性質を用いて基底変数集合と非基底変数集合の要素を交換することにより最適解を得る．

単体法には主に「主単体法」と「双対単体法」の二種類がある．主単体法は主実行可能性を保持しながら双対実行可能性を満たす解を探索し，双対単体法は双対実行可能性を保持しながら主実行可能性を満たす解を探索する手法である．ここでいう主実行可能とは，変数 \(x\) が実行可能であること，すなわち上記の標準形で表すと \(B^{-1}b \geq 0\) が成立することである．双対実行可能とは，非基底変数に対応する相対費用が実行可能であることであり，\({c}_N - {B}^{-1}{c}_B \geq 0\) が成立することである．

幾何学的には，主単体法については線形計画問題の実行可能領域を多面体とみなしたとき，隣接する端点を辿り最適解を得る方法と言える．

単体法は，発表時には単体表（シンプレックス・タブロー）という表を保持して計算を行う手法だった．しかしながらこの手法では計算機等の記憶容量を多く必要とするため，必要最低限の要素のみを保持し計算を行なう改訂単体法と呼ばれる解法が提案され，線形計画ソルバは一般的にこの手法を採用している．

収束性に関しては，巡回を起こさないようにする対策を施すことにより，単体法は有限回の反復で実行結果を得られるということが知られている．有名な巡回対策として Bland [3] の最小添字規則を用いた基底変数選択などがある．

単体法は数理最適化のアルゴリズムとしては比較的長い歴史をもつため，技術的な工夫も多く考案されている [4]．対策は主に「退化対策」と「高速化」に大別される．退化対策としてよく用いられるのは，主単体法であれば制約式，双対単体法であれば目的関数を摂動する方法である．「高速化」として重要なのは pricing 即ち基底変数と非基底変数の入れ替え候補となる変数の選択である．教科書に乗っている方法としては Dantzig ルールと呼ばれる貪欲的手法があり，これは主単体法ではもっとも相対費用が低い非基底変数を選ぶことになる．この手法では変数のスケールが影響することもあり，いくつかの正規化の方法が主張されている．もっとも有名なのは devex あるいは steepest edge と呼ばれる手法である． Dantzig ルールと比較すると一回の計算量は増すが，全体で見ると計算時間は削減される [5]．

単体法は，線形計画問題を解くアルゴリズムの中で最も利用されているアルゴリズムと言われる．その理由としては，変数の領域変更や制約式の追加などに対して高速に再最適化を実行できるからである．混合整数計画問題に対する分枝限定法でも単体法が用いられ，各ノードで単体法が呼ばれる．このため単体法そのものの計算の頑健性が求められる．