何をする手法か?
シンプレックス法は、1947年にジョージ・ダンツィグによって開発された、線形計画問題を解くための基本的なアルゴリズムである。実行可能領域の頂点を系統的に探索し、線形制約の下で目的関数が最大化または最小化される最適解を見つける。
手法の背後にある直感
この方法は、線形制約によって定義される実行可能領域の角点(頂点)から開始し、目的関数値を改善する隣接する頂点へ移動する。隣接する頂点にいかなる改善も提供しない頂点に達するまで継続し、最適性を保証する。このアルゴリズムは、線形計画問題の最適解が制約多面体の頂点にあるという幾何学的性質を利用する。
歴史学
ジョージ・ダンツィグは1947年にシンプレックス法を導入し、オペレーションズ・リサーチに革命をもたらし、数十年にわたり線形計画法の標準アルゴリズムとなった。KleeとMinty(1972)は最悪ケースの指数関数的な計算量を示したが、経験的にはこの方法は高速であった。1980年代には内点法が代替として開発されたが、シンプレックス法はその堅牢性と現代的な実装の洗練さから、多くの実用的なアプリケーションで支配的であり続けた。
使うべき場面
実行可能領域が有界で目的関数が線形である線形計画問題を解く際にシンプレックス法を適用する。特に、数百または数千の変数と制約を持つ問題に効果的である。非線形または非有界な問題には使用を避ける。非常に大規模な問題には内点法が好まれる場合がある。
限界と注意点
- 指数関数的な最悪ケース時間計算量(ただし、実際には稀)
- 非常に退化的な問題に対しては性能が低い場合がある
- 非常に大規模な問題に対しては内点法よりも競争力がない
- 標準形への変換と明示的な制約処理が必要
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 線形計画問題に対して有限時間で最適解を見つけることを保証する
- 注意深い実装と退化処理により、実際には効率的である
- 広く実装されており、成熟した最適化ライブラリによってサポートされている
- より高度な最適化アルゴリズムを理解するための基礎
応用
- 生産計画:需要制約を満たしながらコストを最小化するために生産量を最適化する
- 輸送と物流:倉庫と配送センター間の最適な輸送ルートと数量を決定する
- ポートフォリオ最適化:リスクと予算の制約の下でリターンを最大化するために資産間で資本を配分する
- リソース配分:組織の出力を最大化するために、労働力や材料などの限られたリソースを配分する
- 混合問題:品質仕様を満たし、コストを最小化するために、原材料を最適な割合で混合する
- 人員配置:需要を満たしながら人件費を最小化するために、シフトに従業員を割り当てる
使い方
使い方
線形計画問題をスラック変数を用いて標準形に変換し、初期実行可能基底解(実行可能であれば通常は原点)を特定する。
シンプレックス表を用いてピボット操作を実行する:負の縮約費用を持つ投入変数を選択し、最小比率テストで離脱変数を選定し、基底を更新する。
縮約費用を用いて最適性条件をチェックする。最大化問題の場合、すべての縮約費用が非負であれば現在の解は最適である。そうでなければピボットステップに戻る。
よくある落とし穴
- 退化的な基底に遭遇した場合の循環(サイクリング)の適切な処理に失敗する(Blandの規則または摂動法を使用)
- ピボット選択の誤りや表の更新における算術誤差による数値的不安定性
- アルゴリズム開始前に非有界性または実行不可能性をチェックしない
よくある質問
なぜシンプレックス法は「シンプレックス」と呼ばれるのか?
「シンプレックス」という用語は、任意の次元における多面体の最も単純な形式を指す。このアルゴリズムは、制約によって定義される多面体の辺と頂点を移動することによって機能する。
シンプレックス法と内点法の違いは何ですか?
シンプレックス法は実行可能領域の境界上の頂点に留まるのに対し、内点法は内部を通過する。内点法は最悪ケースの計算量では優れているが、シンプレックス法は中規模の問題では実用上しばしば高速である。
実行不可能性または非有界性をどのように扱いますか?
二段階シンプレックス法を使用する:第一段階で補助問題を解いて実行可能基底解を見つけるか、実行不可能性を決定する。第二段階で元の問題に標準シンプレックス法を適用する。
退化とは何ですか、そしてなぜそれが重要ですか?
退化は、実行可能基底解が複数の基底表現を持つ場合に発生し、循環を引き起こす可能性がある。Blandの規則(インデックス順に変数を選択)または摂動法を使用して処理する。