シンプレックスアルゴリズム
シンプレックスアルゴリズムは、線形計画問題を解くための数値最適化手法である。制約条件で定義される多面体の頂点を反復的に移動しながら目的関数の最適値を探索し、実用的な速度で最適解を求める。ジョージ・ダンツィーグによって1947年に考案され、現在も産業や経済分野で広く利用されている。
背景メモ
- シンプレックス法は、線形計画問題（限られたリソースで目的を最大化・最小化する問題）を解くための代表的アルゴリズム。1947年にジョージ・ダンツィーグが開発。
- 線形計画問題とは、変数間の一次式で表せる制約のもとで、やはり一次式の目的関数を最適化する問題。輸送コスト最小化や工場の生産計画など、実務上の最適化に幅広く使われる。
- シンプレックス法の核心は、制約条件が作る多面体（実行可能領域）の頂点を、目的関数の値が改善される方向へ次々と辿っていく反復計算。頂点の数は組合せ爆発しうるが、実用上は非常に高速に解を見つける。
- 理論的には最悪ケースで指数時間かかるが、実務では圧倒的に使われてきた。1980年代以降は内点法も台頭したが、シンプレックス法は今も主要な解法の一つ。
- 線形計画問題の標準形と、それを解くための「タブロー」と呼ばれる表の操作（ピボット操作）を理解することが、アルゴリズムを追う前提になる。