シンプレックス法のソースを表示

{{Otheruses|線型計画問題を解くアルゴリズム|非線型最適化問題のNelderとMeadによる滑降シンプレックス法 (downhill simplex method)|ネルダー–ミード法}}
{{複数の問題 |出典の明記=2015年10月 |参照方法=2024年3月 }}
'''シンプレックス法'''（シンプレックスほう、'''単体法'''、たんたいほう、{{Lang-en|simplex method}}）は、[[1947年]]に[[ジョージ・ダンツィーク]]が提案した、[[線型計画問題]]を解く[[アルゴリズム]]の中で最も広く使用されている方法である。[[線型計画法]]の1つ。

シンプレックス法は、実行可能解（超多面体の頂点）の1つから出発して目的関数の値をなるべく大きく（小さく）するようなところに移動させていく動作を繰り返して最適解を見つけ出す方法である。各ステップで必ず目的関数の値は改善される。

このアルゴリズムは、実用上は高速であり、変数の数・条件式の数の大きな方のオーダーの回数だけ反復を繰り返せばほとんど常に最適解に達する。このことは、[[1982年]]に [[スティーヴン・スメイル]] (Stephen Smale) が証明した。シンプレックス法は、用いるピボット規則により性能が左右される。有限回のピボットで終了することが保証されている規則として、Blandの提案した最小添字規則が知られている{{Sfn|今野浩|1987|pp=39-42}}。ダンツィークの提案したピボット規則は問題の規模にたいして指数時間かかる問題例があることが知られている。現在のところ、線型計画問題を多項式時間で解くピボット規則の存在性は未解決問題である。

単体法という名前は、ダンツィークが提案した特殊な図解法においては、アルゴリズムの進行に従って[[単体 (数学)|単体]]が下に落ちていくように見えることに由来する。

== アルゴリズム ==
{{節スタブ}}
一般的な流れは以下のとおりである。
#  線型計画問題を制限標準型に変形する。
## スラック変数を加え、標準型に変形する。制約条件のうち、不等式を含む物がなくなり、全て等式となる。
## 人工変数を加え、制限標準型に変形する。等式化された問題の目的関数を <math>z</math> とおく。<math>z</math> を最大化（最小化）する線型計画問題にする。
#  ここまで行った作業を基にシンプレックス表（Simplex Tableau、線型計画問題の係数を表にまとめたもの）を作成する。
#  式の数だけ[[基底]]変数を定める。目的関数 <math>z</math> は必ず基底変数に選ばなければならない。
#  初期の基底変数から得られた[[連立方程式]]の解が最適かどうかを調べる。最適とみなすことができた場合は終了。終了しなかった場合は以下の作業をおこなう。
#  基底変数と非基底変数の組合せを変更する。
## 新たに基底変数にできそうな変数を非基底変数の中から選ぶ。複数存在する場合は、最も効果の高い変数を基底に選ぶ（[[ピボット]]列の決定）
## 基底から追い出す変数を決める。増加限界（定数項の値から新たに基底に入れる変数の係数を割ったもの）によって変数を決めることが多い。（ピボット行の決定）
## 新しい基底変数での連立方程式を解く。具体的にはピボットを中心に[[ガウスの消去法|掃き出し法]]などで新たな実行可能解を求める。実行後は4.に戻り、同様の処理を繰り返す。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
<!-- 出典は列挙するだけでなく脚注で各文章に紐付けする。また、「参考になりそうな書籍」ではなく、執筆にあたり実際に使用した出典情報を示す。-->
* {{Cite book |和書 |author=今野浩 |author-link=今野浩 |title=線形計画法 |publisher=[[日科技連]] |date=1987-03-01 |isbn=978-4817150141 |ref=harv }}
* {{Cite book |和書 |title=ニューメリカルレシピ・イン・シー 日本語版―C言語による数値計算のレシピ |publisher=[[技術評論社]] |author=William H. Press（著）、William T. Vetterling（著）、Saul A. Teukolsky（著）、Brian P. Flannery（著）、丹慶 勝市（翻訳）、佐藤 俊郎（翻訳）、奥村 晴彦（翻訳）|date=1993-06-01 |isbn=978-4874085608 }}
* {{Cite web |author=水野眞治 |date=2013-02-23 |title=シンプレックス法の巡回とその回避 |url=https://www.nakatalab.iee.e.titech.ac.jp/text/pdf/LP/LP3A-simplex.pdf |archive-url=https://web.archive.org/web/20241122153850/https://www.nakatalab.iee.e.titech.ac.jp/text/pdf/LP/LP3A-simplex.pdf |archive-date=2024-11-22 |accessdate=2025-03-04 |format=pdf |work=学習・研究用テキスト 線形計画法 (3A) }}

== 外部リンク ==
* {{Kotobank|シンプレックス法|2=ASCII.jpデジタル用語辞典}}
* {{Kotobank|線形計画法|2=世界大百科事典}}
* {{Kotobank|ダンツィーク|2=ブリタニカ国際大百科事典 小項目事典}}

{{アルゴリズム}}
{{最適化アルゴリズム}}
{{Normdaten}}
{{Comp-stub}}
{{Math-stub}}

{{DEFAULTSORT:しんふれつくすほう}}
[[Category:線型計画法]]
[[Category:数学に関する記事]]