読み方：シンプレックスほう

シンプレックス法【simplex method】単体法

シンプレックス法とは？

複数の制約条件のもとで目的関数を最大化または最小化する「線形計画問題」を解くアルゴリズムの一つ。1947年にアメリカの数学者ジョージ・ダンツィーグ（George B. Dantzig）が考案した手法で、生産計画や物流の最適化などに広く応用されている。

線形計画問題では、制約条件を満たす解の集合が多面体として表現される。シンプレックス法はこの多面体の頂点に着目する。最適解は必ず頂点のいずれかに存在するという数学的性質を利用し、ある頂点を出発点として、隣接する頂点の中で目的関数の値が改善される方向へ順に移動していく。改善できる頂点がなくなった時点で、そこが最適解となる。山の斜面を一歩ずつ高い方へ登り、頂上に達したら止まる動作に例えられる。

計算の各ステップでは、「ピボット操作」と呼ばれる連立一次方程式の変形を繰り返す。手順が明確で機械的に処理できるため、コンピュータによる実装に向いており、変数が数千から数万規模の問題にも対応した高性能なソルバー（解析ソフト）が広く普及している。表計算ソフトの最適化機能にも内部で組み込まれており、利用者が数式を直接扱わなくても最適解を得られる環境が整っている。

理論上の最悪計算量は指数時間であり、問題によっては頂点を大量に経由する可能性がある。しかし、実務で扱う問題の多くでは反復回数が現実的な範囲に収まり、高速に解が得られることが知られている。1980年代以降に登場した「内点法」は多面体の内部を通って最適解に近づく別の手法で、大規模問題では優位な場合もある。両者は問題の性質に応じて使い分けられているが、シンプレックス法は数理最適化の基本的な手法として今日も広く使われている。