ぷろえんじにあ
TRIZ・ITソフトウェアキーワードリスト TOP
1 解説
G.B.Dantzingによって、1947年に開発された。この方法は、基底変数と非基底変数の初期分割から始められる。それぞれから選ばれた一対の変数を変換するというボット操作を反復して基底解を逐次にたどっていき最終的に最適実行可能基底解を求める方法である。
このアルゴリズムは、実用上は高速。ほとんど常に、変数の数・条件式の数の大きな方のオーダーの回数だけ反復を繰り返せば解ける。そのことは、1982年に Stephen Smale が証明した。しかし、Danzig が提唱したもの（ピボット規則）は多項式時間で終了しない問題例がある。常に多項式時間で解が得られるピボット規則の存在性は、現在も未解決問題である。単体法という名前は、Danzig が提案した特殊な図解法においては、アルゴリズムの進行に従って単体が下に落ちていくように見えることに由来する。
2 所見
特になし