単体法

【たんたいほう (simplex method)】

概要

1947年, ダンツィク(G.B. Dantzig) によって提案された,線形計画問題を解くための手法.理論的には有限回反復での収束性しか示されていないが,実用的には高速に最適解が得られることが知られている.また, 実用の際には, 単体法を改良した改訂単体法が良く用いられる.

詳説

　ダンツイック（G. B. Dantzig）によって提案された単体法（simplex method）（シンプレックス法）は, カーマーカー法の出現する1984年までは線形計画問題を解くもっとも有効な解法とされていた. 単体法は問題の構造を巧妙に利用しており, いまでも, 線形計画, 整数計画, 組合せ最適化の多くの分野で使われている[2, 3, 4]. 以下, 次のような基準形と呼ばれる線形計画問題を考えることにする.

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{(P)} \quad \begin{array}{lll} & \mbox{max.} & {\displaystyle \sum_{j=1}^{n}c_j x_j} \\ & \mbox{s. t.} & {\displaystyle \sum_{j=1}^{n}a_{ij} x_j} \leq b_i \; \; (i=1,2,\ldots,m), x_1,x_2,\ldots ,x_n \geq 0. \end{array}}

ここで, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c_j \,(j=1,2,\ldots,n), \, b_i \, (i=1,2,\ldots,m),\, a_{ij} \, (i=1,2,\ldots,m, j=1,2,\ldots,n)} は実数, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{x}=(x_1,x_2,\ldots,x_m)} は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\,} 個の変数からなる構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\,} 次元ベクトルである. すべての線形計問題は, 簡単な変換によって基準形に帰着できる. 問題（P）の制約条件を満たす構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{x}} を実行可能解（feasible solution）, その集まりを実行可能多面体（feasible polyhedron）と呼ぶ. 実行可能解のなかで目的関数を最大にするものを最適解（optimal solution）と呼ぶ.

　ここで, 問題（P）にスラック変数と呼ばれる非負の変数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_{n+i} \, (i=1,\ldots,m)} を導入する

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{array}{ll} \mbox{max.} & c_1 x_1+\cdots+ c_nx_n \\ \mbox{s. t.} & a_{i1} x_1 +\cdots+a_{in} x_n + x_{n+i} = b_i \; \; (i=1, 2, \ldots, m), \\ & x_1 \geq 0,\ldots,x_{n+m}\geq 0. \end{array}}

さらに, 目的関数を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle z=c_0+\sum_{j=1}^n c_j x_j \ (c_0=0)} と書き, 制約式左辺のスラック変数以外の項を移行すると, 上の問題は以下のようになる.

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{array}{ll} \mbox{max.} & z \\ \mbox{s. t.} & x_{n+i}= b_i-a_{i1}x_{1}-\cdots-a_{in}x_{n} \quad (i=1, 2, \ldots, m), \\ & z=c_0+c_1 x_1+\cdots+c_n x_n, \\ & x_1 \geq 0,\ldots, x_{n+m} \geq 0. \end{array}}

制約式の左辺の変数を基底変数, 右辺の変数を非基底変数と呼ぶ. ここで, 非基底変数の添字を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N(1)=1,\ldots,N(n)=n} , 基底変数の添字を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B(1)=n+1,\ldots,B(m)=n+m} とおき, 各変数の係数の添字も対応するものにする.　非基底変数の値を任意に固定すると基底変数の値は一意に定まるが,　特に非基底変数をすべて構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0\,} に固定して得られる解を基底解（basic solution）と呼ぶ. また, 上の等式系を辞書と呼ぶ. 係数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b_i \, (i=1,\ldots,m)} が非負のとき, 基底解は実行可能解であるが, このような辞書を実行可能辞書と呼ぶ. 線形計画問題の実行可能な基底解は実行可能多面体の頂点に対応する [3]. 単体法は目的関数の値を最大化する実行可能な基底解を求めるものであり, 辞書を等価な辞書へと繰り返し変換することによって実現される.

単体法

入力：実行可能な辞書

ステップ１（最適性判定）

(1) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c_{N(s)}>0\,} となる添字構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s (1\le s \le n)} を1つ選ぶ.

(2) もし, そのような添字がなければ, 現在の基底解は最適となり, 終了する.

ステップ２（有界性判定）

(1) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle \frac{b_r}{a_{rN(s)}}=\min\{\frac{b_i}{a_{iN(s)}} : a_{iN(s)}>0, 1 \le i \le m \}} を計算し, 行番号構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r\,} を求める（この操作は現在の基底解から実行可能性を保ったまま非基底変数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_{N(s)}\,} だけをできる限り増加させる）.

(2) そのような番号構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r\,} がなければ（つまり, 変数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_{N(s)}\,} を限りなく増加させることができる）, 問題は非有界となり, 終了する.

(3) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r\,} が存在する場合, ステップ３へ.

ステップ３（（構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r, s\,} ）を中心とするピボット演算を行う）

（1）辞書の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r\,} 番目の式について構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_{N(s)}\,} の表現式を求める.

（2）求めた構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_{N(s)}\,} の式を辞書の他の行 (構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\not = r\,} ) に代入する.

（3）添字構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N(s)\,} と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B(r)\,} を交換し, ステップ１へ.

実行可能解をもつ問題に対して単体法が有限回で終了すれば, その問題は最適解をもつか, または非有界である. しかし, 辞書の右辺に構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0\,} の定数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b_i\,} を少なくとも1つ含むとき, 辞書は退化しており, 単体法は有限回で終わるとは限らない. このとき, ピボット演算を施しても, 基底解が変化しないことになり, 目的関数値も変化しない. 有限回収束を保証するための手段として, Blandのピボット選択規則 [1] が提案されており, これを用いると単体法は必ず有限回で収束する.

　先の説明で述べたように, 単体法の入力として実行可能な辞書が必要とされる. 現在の辞書が実行可能でない場合, 単体法を用いて実行可能な辞書を求めることができる. そのために, 新しい変数（人工変数）構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_a\,} を用いて補助問題

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{array}{ll} \mbox{max.} & -x_a \\ \mbox{s. t.} & x_{n+i}= b_i-a_{i1}x_{1}-\cdots-a_{in}x_{n}+x_a \; \; (i=1, 2, \ldots, m), \\ & x_1 \geq 0,\ldots, x_{n+m} \geq 0, \; x_a \geq 0, \end{array}}

を作る. 元問題が実行可能であることと補助問題の最適目的関数値が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0\,} であることは等価なので, 補助問題を解くことにより, 元問題の実行可能解の有無を判定できる.

　一般に, 基準形の線形計画問題を解く際には, 2段階単体法と呼ばれるものを用いる. 第1段階では, 補助問題を解き, 実行可能解の有無を判定し, 実行可能解が存在する場合は実行可能辞書を求める. 第2段階では, 求めた実行可能辞書を初期の辞書として, もう一度単体法を使い, 元問題を解く.

---

参考文献

[1] R. G. Bland, "New finite pivot ruless for the simplex method", Mathematics of Operations Research 2（1977）, 103-107.

[2] V. Chvátal, Linear Programming, W. H. Freeman and Company, 1983.

[3] G. B. Dantzig, Linear Programming and Extensions, Princeton Univesity Press, 1963.

[4] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.