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

数理計画用語集

単体法

読み:たんたいほう
英名:Simplex Method
別名:シンプレックス法
関連線形計画問題

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

単体法は,実行可能領域上のある端点から出発し,隣接する端点を辿っていくことで最適解を得るという方法である.これは,線形計画問題では端点の中に最適解は存在するという事実を利用している.なお,単体法に関しては,単体表(シンプレックス・タブロー)という表を用いた計算方法が存在する.ところで,(もともとの)単体法により求解を行なおうとすると多くの要素について計算を行なう必要がある.これは,計算機等の記憶容量を多く必要とすること,あるいは数値的な誤差が蓄積する危険性が高まることを示唆している.このため,必要最低限の要素のみを保持し計算を行なう改訂単体法と呼ばれる解法が提案されている.

収束性に関しては,巡回(cycling)を起こさないようにする対策を施すことにより,単体法は有限回の反復で実行結果を得られるということが知られている.なお,有名な巡回対策として Bland によるものがある.単体法は多くの問題に対して実用的な反復回数で実行結果を得ることが出来る.しかし,Klee-Minty の問題のように出発する端点によっては最適解を得るために全ての端点を探索する必要がある(指数オーダーの反復を必要とする)ため単体法の適用が不利になるという問題もある.