単体法

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

概要

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

詳説

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

${\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}}$

ここで, $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)$は実数, ${\boldsymbol {x}}=(x_{1},x_{2},\ldots ,x_{m})$は$n\,$個の変数からなる$n\,$次元ベクトルである. すべての線形計問題は, 簡単な変換によって基準形に帰着できる. 問題（P）の制約条件を満たす${\boldsymbol {x}}$を実行可能解（feasible solution）, その集まりを実行可能多面体（feasible polyhedron）と呼ぶ. 実行可能解のなかで目的関数を最大にするものを最適解（optimal solution）と呼ぶ.

　ここで, 問題（P）にスラック変数と呼ばれる非負の変数$x_{n+i}\,(i=1,\ldots ,m)$を導入する

${\begin{array}{ll}{\mbox{max.}}&c_{1}x_{1}+\cdots +c_{n}x_{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}}$

さらに, 目的関数を $z=c_{0}+\sum _{j=1}^{n}c_{j}x_{j}\ (c_{0}=0)$ と書き, 制約式左辺のスラック変数以外の項を移行すると, 上の問題は以下のようになる.

${\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}}$

制約式の左辺の変数を基底変数, 右辺の変数を非基底変数と呼ぶ. ここで, 非基底変数の添字を$N(1)=1,\ldots ,N(n)=n$, 基底変数の添字を$B(1)=n+1,\ldots ,B(m)=n+m$とおき, 各変数の係数の添字も対応するものにする.　非基底変数の値を任意に固定すると基底変数の値は一意に定まるが,　特に非基底変数をすべて$0\,$に固定して得られる解を基底解（basic solution）と呼ぶ. また, 上の等式系を辞書と呼ぶ. 係数$b_{i}\,(i=1,\ldots ,m)$が非負のとき, 基底解は実行可能解であるが, このような辞書を実行可能辞書と呼ぶ. 線形計画問題の実行可能な基底解は実行可能多面体の頂点に対応する [3]. 単体法は目的関数の値を最大化する実行可能な基底解を求めるものであり, 辞書を等価な辞書へと繰り返し変換することによって実現される.

単体法

入力：実行可能な辞書

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

(1) $c_{N(s)}>0\,$となる添字$s(1\leq s\leq n)$を1つ選ぶ.

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

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

(1) $\textstyle {\frac {b_{r}}{a_{rN(s)}}}=\min\{{\frac {b_{i}}{a_{iN(s)}}}:a_{iN(s)}>0,1\leq i\leq m\}$を計算し, 行番号$r\,$を求める（この操作は現在の基底解から実行可能性を保ったまま非基底変数$x_{N(s)}\,$だけをできる限り増加させる）.

(2) そのような番号$r\,$がなければ（つまり, 変数$x_{N(s)}\,$を限りなく増加させることができる）, 問題は非有界となり, 終了する.

(3) $r\,$が存在する場合, ステップ３へ.

ステップ３（（$r,s\,$）を中心とするピボット演算を行う）

（1）辞書の$r\,$番目の式について$x_{N(s)}\,$の表現式を求める.

（2）求めた$x_{N(s)}\,$の式を辞書の他の行 ($i\not =r\,$) に代入する.

（3）添字$N(s)\,$と$B(r)\,$を交換し, ステップ１へ.

実行可能解をもつ問題に対して単体法が有限回で終了すれば, その問題は最適解をもつか, または非有界である. しかし, 辞書の右辺に$0\,$の定数$b_{i}\,$を少なくとも1つ含むとき, 辞書は退化しており, 単体法は有限回で終わるとは限らない. このとき, ピボット演算を施しても, 基底解が変化しないことになり, 目的関数値も変化しない. 有限回収束を保証するための手段として, Blandのピボット選択規則 [1] が提案されており, これを用いると単体法は必ず有限回で収束する.

　先の説明で述べたように, 単体法の入力として実行可能な辞書が必要とされる. 現在の辞書が実行可能でない場合, 単体法を用いて実行可能な辞書を求めることができる. そのために, 新しい変数（人工変数）$x_{a}\,$を用いて補助問題

${\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}}$

を作る. 元問題が実行可能であることと補助問題の最適目的関数値が$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.