シンプレックス法

シンプレックス法（単体法）とは

シンプレックス法は、線形計画問題を解くためのアルゴリズムで、1947年にジョージ・ダンツィークによって提案されました。線形計画問題とは、与えられた制約条件の下で、ある目的関数を最大化または最小化する問題です。シンプレックス法は、この問題を解くための最も広く使用されている方法の一つです。

基本的な考え方

シンプレックス法は、実行可能解（多面体の頂点）の一つから出発し、目的関数の値を改善する方向に移動を繰り返すことで最適解を見つけ出します。具体的には、以下のステップで構成されます。

1. 線形計画問題の標準形への変換: 与えられた線形計画問題を、シンプレックス法で扱いやすい形（標準形）に変換します。この際、スラック変数や人工変数が導入されることがあります。
2. シンプレックス表の作成: 標準形に変換された問題を、シンプレックス表と呼ばれる表形式に整理します。この表には、目的関数と制約条件の係数、および定数項が記載されます。
3. 初期基底解の選択: シンプレックス表から、初期の基底変数（解を構成する変数）を選択します。目的関数も必ず基底変数に含めます。
4. 最適性の判定: 現在の基底解が最適であるかどうかを判定します。最適であればアルゴリズムを終了します。そうでなければ、次のステップに進みます。
5. 基底変数の更新: 現在の基底解を改善するために、基底変数と非基底変数を入れ替えます。この時、目的関数の値を最も改善する変数が選択されます（ピボット列の決定）。
6. 基底から追い出す変数の決定: 新たに基底変数として追加する変数に対応して、基底から追い出す変数を決定します（ピボット行の決定）。
7. 解の更新: ピボット演算を行い、新しい基底解を求めます。この際、ガウスの消去法などが用いられます。
8. ステップ4に戻る: ステップ4からステップ7の操作を、最適解が見つかるまで繰り返します。

アルゴリズムの特徴

実用上の高速性: 多くの線形計画問題に対して、実用上高速に最適解を求めることができます。
反復回数: 変数の数や制約式の数の大きな方のオーダー回数程度の反復で、ほとんどの場合最適解に到達します。
ピボット規則への依存性: シンプレックス法の性能は、どのピボット規則を用いるかによって左右されます。ピボット規則とは、基底変数と非基底変数をどのように入れ替えるかのルールです。
巡回問題: 一部のピボット規則では、同じ基底解を繰り返し通過してしまう（巡回）という問題が発生する可能性があります。この問題は、例えば、最小添字規則などの特定のピボット規則を用いることで回避できます。

ピボット規則

最小添字規則: ブランドが提案したピボット規則で、有限回のピボットで終了することが保証されています。
ダンツィークのピボット規則: ダンツィークが提案した規則ですが、問題の規模に対して指数時間かかる例があることが知られています。
多項式時間アルゴリズムの未解決性: 線形計画問題を多項式時間で解くピボット規則は、現在も未解決問題です。

単体法の名前の由来

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

シンプレックス法の応用

シンプレックス法は、様々な分野で応用されています。

経営科学: 生産計画、輸送計画、在庫管理など
経済学: 資源配分、価格決定など
工学: 最適設計、制御システムなど

参考文献

William H. Press, William T. Vetterling, Saul A. Teukolsky, Brian P. Flannery, 丹慶 勝市（翻訳）, 佐藤 俊郎（翻訳）, 奥村 晴彦（翻訳）『ニューメリカルレシピ・イン・シー 日本語版―C言語による数値計算のレシピ』技術評論社、1993年。
水野 眞治, 『シンプレックス法の巡回とその回避』, http://www.me.titech.ac.jp/~mizu_lab/text/PDF-LP/LP3A-simplex.pdf
松井 知己, 『Bland の最小添字規則の有限性 -単体法の非巡回ピヴォット規則- 』, http://tomomi.my.coocan.jp/text/bland7.pdf

外部リンク

ASCII.jpデジタル用語辞典『シンプレックス法』 - コトバンク
世界大百科事典『線形計画法』 - コトバンク
ブリタニカ国際大百科事典 小項目事典『ダンツィーク』 - コトバンク

もう一度検索