シンプレックス法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

シンプレックス法(単体法とも。どちらも和訳：simplex method)は、1947年にG.B. Danzigが提案した、線形計画問題を解くアルゴリズムの中で最も広く使用されている方法である。

この方法は、ある超多面体の頂点(実行可能解)から出発して目的関数の値をなるべく大きく(小さく)するようなところに移動させていく動作を繰り返して最適解を見つけ出す方法である。このアルゴリズムは、実用上は高速だが、Danzig が提唱したもの（ピボット規則）は多項式時間で終了しない問題例があることが知られている。多項式時間で解が得られるピボット規則の存在性は、現在も未解決問題である。単体法という名前は、Danzig が提案した特殊な図解法においては、アルゴリズムの進行に従って単体が下に落ちていくように見えることに由来する。

[編集] アルゴリズム

一般的な流れは以下のとおりである。

線形計画問題を変形する。
1. 与えられた線形計画問題の制約条件式を等式化する。
2. 等式化された問題の目的関数をzとおく。
3. zを最大化(最小化)する線形計画問題にする。
ここまで行った作業を基にシンプレックス表(Simplex Tableau、線形計画問題の係数を表にまとめたもの)を作成する。
式の数だけ基底変数を定める。zは必ず基底変数に選ばなければならない。
初期の基底変数から得られた連立方程式の解が最適かどうかを調べる。最適とみなすことができた場合は終了。終了しなかった場合は以下の作業をおこなう。
基底変数と非基底変数の組合せを変更する。
1. 新たに基底変数にできそうな変数を非基底変数の中から選ぶ。複数存在する場合は、最も効果の高い変数を基底に選ぶ。(ピボット列の決定)
2. 基底から追い出す変数を決める。増加限界(定数項の値から新たに基底に入れる変数の係数を割ったもの)によって変数を決めることが多い。 (ピボット行の決定)
3. 新しい基底変数での連立方程式を解く。具体的にはピボットを中心に掃き出し法などで新たな実行可能解を求める。実行後は4.に戻る。