シンプレックス法
ウィキペディア フリーな encyclopedia
この項目では、線型計画問題を解くアルゴリズムについて説明しています。非線型最適化問題のNelderとMeadによる滑降シンプレックス法 (downhill simplex method)については「ネルダー–ミード法」をご覧ください。 |
シンプレックス法(英語: simplex method、単体法)は、1947年にジョージ・ダンツィークが提案した、線型計画問題を解くアルゴリズムの中で最も広く使用されている方法である。線型計画法の1つ。
シンプレックス法は、実行可能解 (超多面体の頂点) の1つから出発して目的関数の値をなるべく大きく (小さく) するようなところに移動させていく動作を繰り返して最適解を見つけ出す方法である。各ステップで必ず目的関数の値は改善される。
このアルゴリズムは、実用上は高速であり、変数の数・条件式の数の大きな方のオーダーの回数だけ反復を繰り返せばほとんど常に最適解に達する。このことは、1982年に スティーヴン・スメイル (Stephen Smale) が証明した。シンプレックス法は、用いるピボット規則により性能が左右される。有限回のピヴォットで終了することが保証されている規則として、Blandの提案した最小添字規則が知られている。Dantzigの提案したピボット規則は問題の規模にたいして指数時間かかる問題例があることが知られている。現在のところ、線型計画問題を多項式時間で解くピボット規則の存在性は未解決問題である。
単体法という名前は、Dantzig が提案した特殊な図解法においては、アルゴリズムの進行に従って単体が下に落ちていくように見えることに由来する。