3. 単体法 #

3.1. 導入 #

単体法 (Simplex method)

単体法とは，ある一つの端点解 (実行可能基底解) \(P_1\) から始めて，目的関数値が改善するよう，ピボット操作によって隣接する端点解 \(P_2,P_3,\ldots\) に次々と移動して，最終的に最適性条件を満足する最適解に到達しようとする手法である．

注釈

単体法は最適解の候補である端点の座標を手当たり次第に求めず，手順を追って次第に最適解に近付いていく方法である．

手当たり次第に求めようとすると，未知数が \(k\) 個あり，非負条件を含めた制約条件としての \(1\) 次不等式が \(n\) 個あれば，\(k\) 次元超平面の交点数は高々 \({}_nC_k\) 個ある．\(n,k\) が小さいときは手当り次第に端点解を求めても良いかもしれないが，問題の規模が大きくなるとそうもいかないことがわかる．

3.2. 準備 #

線形最適化問題は次の標準形にいつでも直せた．

(1)#\[\begin{split}& \mathrm{Minimize\colon}~ f(\vec{x}) = \vec{c}^{\top}\vec{x} \\ & \mathrm{subject~to\colon}~ \\ & A\vec{x} = \vec{b}, \\ &\vec{x} \geq \vec{0}\end{split}\]

ここで基底変数と非基底変数の自由度は次だとする．

制約条件式 \(A\vec{x} = \vec{b}\) の総数 (基底変数 \(\{[\vec{x}_B]_i\}_{i\in I}\) の総数) を \(m=|I|\) とし，全変数 \(\{[\vec{x}]_j\}_{j\in J}\) の総数 (基底変数と非基底変数の総数)を \(n=|J|\) とする．

(2)#\[\begin{split}i \in I &= \{1,\ldots,m\}, \\ j \in J &= \{1,\ldots,n\}\end{split}\]

係数行列 \(A\) は \(\operatorname{rank} A=m\) とし，次のように基底行列 \(B\) と非基底行列 \(N\) に分解しておく．

(3)#\[\begin{split}A = \begin{bmatrix} B_{11} & B_{12} & \cdots & B_{1m} & N_{11} & N_{12} & \cdots & N_{1(n-m)} \\ B_{21} & B_{22} & \cdots & B_{2m} & N_{21} & N_{22} & \cdots & N_{2(n-m)} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ B_{m1} & B_{m2} & \cdots & B_{mm} & N_{m1} & N_{m2} & \cdots & N_{m(n-m)} \end{bmatrix}\end{split}\]

そして上記の標準形は非基底変数のみで次のように書き直すことができた．

(4)#\[\begin{split}& \mathrm{Minimize\colon}~ f(\vec{x}_N) = \vec{\gamma}^{\top}\vec{x}_N + \vec{\pi}^{\top}\vec{b} \\ & \mathrm{subject~to\colon}~ \\ &(\vec{x}_B=) B^{-1}\vec{b} - B^{-1}N\vec{x}_N \geq \vec{0}, \\ &\vec{x}_N \geq \vec{0}\end{split}\]

併せて以下の量を定義した．

(5)#\[\begin{split}\vec{\pi} &= (B^T)^{-1}\vec{c}_B, \\ \vec{\gamma} &= \vec{c}_N - N^{\top}\vec{\pi}\end{split}\]

これらはそれぞれ単体乗数，相対費用係数とよんだ．

このように問題を整理するとき，次の最適性条件が満たされるならば，実行可能解は最適解となった．

(6)#\[\vec{\gamma} \geq \vec{0}\]

3.3. 単体法の手続き #

単体法とは実行可能基底解が最適解ではないとき，次の端点解に至るためのピボット操作を以下の要領で決定する手続きである．

最適解でないということは，\(\vec{\gamma} \geq \vec{0}\) を満たさない成分が少なくとも一つあることを意味する．そのような成分の一つに着目し，第 \(k\) 成分であったとする．

(7)#\[\gamma_k < 0\]

このとき非基底変数の第 \(k\) 成分 \(x_k = [\vec{x}_N]_k\) を基底解である \(0\) 値から正値にずらすと，目的関数値はより改善すると考えられる．ここで次の二点が論点となる．

\(x_k = [\vec{x}_N]_k\) をどれだけずらすか．つまり正値にずらす際の上限値 \(\theta_k\) は何か．
ずらすことでどの他の端点解が次に選ばれるか，つまりピボット操作すべき変数は何か．

それらは次のとおりである．

\(\vec{x}_B = B^{-1}\vec{b} - B^{-1}N\vec{x}_N\) より， \([\vec{x}_N]_i = \delta_{i,k} x_k\) を代入して整理すると次が得られる ¹ ¹\(\delta_{i,k}\) は Kronecker の \(\delta\) である．つまり \(\delta_{i,k}\) は \(i=k\) のときに限り \(1\) で，他は \(0\) の値をとる．．

(8)#\[\vec{x}_B = B^{-1}\vec{b} - x_k B^{-1}\vec{N}_k = \vec{\beta} - x_k\vec{\nu}\]

ここで \(\vec{N}_k\) は非基底行列 \(N\) の第 \(k\) 列目でできるベクトルである．

(9)#\[\begin{split}\vec{N}_k = \begin{bmatrix} N_{1k} \\ \vdots \\ N_{mk} \end{bmatrix}\end{split}\]

また便宜のために，\(\vec{\beta} = B^{-1}\vec{b}\) および \(\vec{\nu} = B^{-1}\vec{N}_k\) を定めた．

さて \(x_k\) は \(\vec{x}_B\geq \vec{0}\) を満たして正値にずらさなければならない．すると (8) より，正値にずらす際の上限値 \(\theta_k\) が得られる．

(10)#\[x_k \leq \theta_k = \min_{i\in\{1,\ldots,m\}} \frac{\beta_i}{\nu_i} ~~ (\nu_i>0)\]

ここで \(\vec{\beta}\) と \(\vec{\nu}\) の第 \(i\) 成分をそれぞれ \(\beta_i\) および \(\nu_i\) と書いた．

注釈

\(\nu_i>0\) なる \(i\) が一つもないとき，\(x_k\) は問題の制約条件に違反することなく，幾らでも大きくして，目的関数値を改善することができる．これはつまり問題が非有界であることを意味する．

以上によって求められた \(\theta_k\) まで，\(x_k\) を増やしたとすると， \(\vec{x}_B = \vec{\beta} - \theta_k\vec{\nu}\) となるが， \(J_k = \operatorname*{argmin}_i(\beta_i/\nu_i)\) の元 \(j\) についての成分は \(0\) となる．

(11)#\[[\vec{x}_B]_j = \beta_j - \theta_k\nu_j = 0\]

つまり \(J_k\) のある一つの元 \(j\) で定まる基底変数 \(x_j = [\vec{x}_B]_j\) と，非基底変数 \(x_k = [\vec{x}_N]_k\) とをピボット操作の対象とすればよい．

以上の手続きを (有界である場合に) 最適解が得られるまで繰り返す手法が単体法である．

注釈

手続きの中で逆行列 \(B^{-1}\) が要求されている箇所があるが，必ずしも直接に求める必要はない．逆行列は計算コストが高く，できることならこれを避けたいものである．今の場合は，例えば \(\vec{\pi} = (B^{\top})^{-1}\vec{c}_B\) については， \(B^{\top}\vec{\pi} = \vec{c}_B\) というように一次方程式に戻して評価すればよい．

逆行列の話題以外にも，この種の数値計算のテクニックをいろいろと使うわけであるが，ここでは割愛している．

3.4. まとめ #

まとめると単体法の手続きは次のとおりである．

初期解として実行可能基底解 \((\vec{x}_B,\vec{x}_N) = (\vec{\beta},\vec{0})\) を選ぶ．ここで \(\vec{\beta} = B^{-1}\vec{b}\) と置いた．
単体乗数 \(\vec{\pi} = (B^{\top})^{-1}\vec{c}_B\) を計算する．
最適性条件 \(\vec{\gamma} \geq \vec{0}\) を評価する．満たされているならば，最適解が得られたため，手続きを終える．そうでないならば，条件を破っているある一つの成分 \(k\) を選び，これに対応する非基底変数 \(x_k = [\vec{x}_N]_k\) に着目する．
\(\vec{\nu} = B^{-1}\vec{N}_k\) を計算する．
\(\vec{\nu}\) の各成分が正でなければ，非有界であるため，手続きを終了する．そうでなければ，\(J_k = \operatorname*{argmin}_i(\beta_i/\nu_i)\) の元 \(j\) を一つ選ぶ．
\(x_k \to \theta_k = \min_{i\in\{1,\ldots,m\}} (\beta_i / \nu_i)\) と更新する．
基底変数を \(\vec{x}_B \to \vec{\beta} - \theta_k\vec{\nu}\) と更新する．
\(x_k\) と \(x_j = [\vec{x}_B]_j\) についてピボット操作する．手続き 2 へ．

上記の手続きが終了するとき，最適解が得られるか，または非有界と判定されるかの何れかの結果となる．

単体法

目次

3. 単体法#

3.1. 導入#

3.2. 準備#

3.3. 単体法の手続き#

3.4. まとめ#

3. 単体法 #

3.1. 導入 #

3.2. 準備 #

3.3. 単体法の手続き #

3.4. まとめ #