シンプレックス法 - 線形計画問題を解く古典的アルゴリズム

問題の定式化と構成要素

典型的な問題は行列形式で、最大化 c^T x、制約 Ax ≤ b、x ≥ 0 と書かれるか、スラック変数を導入した等式形式で表される。主な要素は、目的関数の係数、制約行列、右辺の値、そして基底変数と非基底変数である。可行基底は多面体の頂点に対応し、基本実行可能解はすべての制約と非負条件を満たす。

アルゴリズムの流れ

1. 初期の基本実行可能解を見つけるか、非実行可能性を判定する（Phase I）。そのために補助目的関数や補助変数を導入することが多い。
2. 次に、現在の基本実行可能解を繰り返し改善する（Phase II）。進入変数と離脱変数を選び、ピボット操作を行って新しい基底を作る。
3. これを、目的関数をこれ以上改善できる進入変数がなくなり最適性が確認されるまで、または非有界性が判明するまで続ける。

幾何学的な見方とピボット操作

幾何学的には、各ピボットは可行多面体の辺に沿って隣接する頂点へ移動する操作であり、目的関数値が減少しない、または増加しないように進む。どの隣接頂点を選ぶかは、最大係数規則や Bland の規則のようなピボット選択規則によって決まり、循環や計算効率に影響する。Bland の規則は慎重なタイブレークによって循環を防ぎ、他の規則は実用上の速度を重視して設計されている。

歴史、計算量、変種

ジョージ・ダンツィグは1947年にこのアルゴリズムを広く普及させ、レオニード・カントロヴィチらの先行する理論研究を発展させた。シンプレックス法は実用上きわめて有効だが、最悪計算時間は指数的であり、悪意ある例では多数のピボットを必要とする。それでも、現実の問題では通常すばやく動作する。後に導入された内点法は多項式時間の保証を持ち、相補的な代替手法となっている。改訂シンプレックス法、双対シンプレックス法、ネットワーク・シンプレックス法は、実務でよく使われる変種である。

応用と注目点

シンプレックス法は、オペレーションズ・リサーチ、物流、金融、製造、そして線形最適化を必要とするあらゆる分野で広く使われている。実務上の効率の高さ、幾何学的な理解のしやすさ、さらに整数計画のヒューリスティクスや感度分析のような変種へ拡張できることが、この手法が最適化ソフトウェアと教育の両方で中心的な役割を保ち続けている理由である。より詳しい技術的内容や実装については、参考文献や最適化ライブラリを参照するとよい。