シンプレックス法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/07/06 02:57 UTC 版)
|
この記事には複数の問題があります。
|
シンプレックス法（シンプレックスほう、単体法、たんたいほう、英語: simplex method）は、1947年にジョージ・ダンツィーク（ダンツィク）が提案した、線型計画問題を解くアルゴリズムの中で最も広く使用されている方法である。線型計画法の1つ。
シンプレックス法は、実行可能解（超多面体の頂点）の1つから出発して目的関数の値をなるべく大きく（小さく）するようなところに移動させていく動作を繰り返して最適解を見つけ出す方法である。各ステップで必ず目的関数の値は改善される。
このアルゴリズムは、実用上は高速であり、変数の数・条件式の数の大きな方のオーダーの回数だけ反復を繰り返せばほとんど常に最適解に達する。このことは、1982年に スティーヴン・スメイル (Stephen Smale) が証明した。シンプレックス法は、用いるピボット規則により性能が左右される。有限回のピボットで終了することが保証されている規則として、Blandの提案した最小添字規則が知られている[1]。ダンツィクの提案したピボット規則は問題の規模にたいして指数時間かかる問題例があることが知られている。現在のところ、線型計画問題を多項式時間で解くピボット規則の存在性は未解決問題である。
単体法という名前は、ダンツィクが提案した特殊な図解法においては、アルゴリズムの進行に従って単体が下に落ちていくように見えることに由来する。
アルゴリズム
 |
この節の加筆が望まれています。
|
一般的な流れは以下のとおりである。
- 線型計画問題を制限標準型に変形する。
- スラック変数を加え、標準型に変形する。制約条件のうち、不等式を含む物がなくなり、全て等式となる。
- 人工変数を加え、制限標準型に変形する。等式化された問題の目的関数を
最適化問題では極大・極小値をとる解を求める。
| 一般 | |
|---|---|
| 微分可能 |
| 凸最小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) |
|||||
|---|---|---|---|---|---|
| グラフ理論 |
|
||||
| フローネットワーク |
|
| 典拠管理データベース: 国立図書館 |
|---|
 |
この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |
 |
この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。 |
Weblioに収録されているすべての辞書からシンプレックス法を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からシンプレックス法
を検索
- シンプレックス法のページへのリンク
