next up previous
Next: もとの問題の最適解の抽出 Up: シンプレックス法 Previous: シンプレックス法


実行可能基底行列が得られている場合

実行可能基底行列$ \vec{B}$がすでに得られ, 制約条件 $ \vec{A} \vec{x} = \vec{b} $が (13)の形に書き直されているものとする。ここで,

$\displaystyle \bar{\vec{b}}=\vec{B}^{-1}\vec{b}, \quad \bar{\vec{A}}_N=\vec{B}^{-1}\vec{N}$ (14)

と定義し, (13)を

$\displaystyle \vec{x}_B=\bar{\vec{b}}-\bar{\vec{A}}_N \vec{x}_N$ (15)

のように書き直す。 (15)を(11)に代入し,

$\displaystyle z_B=\vec{c}_B^T \bar{\vec{b}}, \quad \bar{\vec{c}}_N^T=\vec{c}_N^T-\vec{c}_{B}^T \bar{\vec{A}}_N$ (16)

とおくと,

$\displaystyle z=z_B+\bar{\vec{c}}_N^T \vec{x}_N$ (17)

なる表現が得られる。

ここで, 行列 $ \bar{\vec{A}}_N$の第$ i$列ベクトルを $ \bar{\vec{a}}_i$と書くことにする。 すなわち,

$\displaystyle \bar{\vec{A}}_N=[\bar{\vec{a}}_1,\ldots,\bar{\vec{a}}_{n-m}]$ (18)

と書く。 (15)と(17)をまとめると, 問題(SP)と等価な

\begin{displaymath}\begin{split}{\rm (BF)} \quad &\min \{z=z_B+\bar{\vec{c}}_N^T...
..., \vec{x}_B \geq \vec{0}, \vec{x}_N \geq \vec{0} \} \end{split}\end{displaymath} (19)

という問題が得られる。 問題(BF)を実行可能基底行列$ \vec{B}$に対する基底形式表現と呼ぶ。

さて, 基底解(12)は(BF)の制約条件を満たしているので, 最適とは限らない解である。そこで, 基底解(12)を変 更して目的関数$ z$をより小さくすることを考える。 このために, (15)と(17)を見比べると, 以下のことがわかる。

以上のような考え方からシンプレックス法のアルゴリズムが得られる iv)

\fbox{シンプレックス法}

(初期化)
実行可能基底行列$ \vec{B}$が与えられているものとする。 $ \vec{B}$を使って基底形式表現(19)を求める。
(ステップ1)
$ \{\bar{c}_{N,1},\ldots,\bar{c}_{N,n-m}\}$の中で最小のものを $ \bar{c}_{N,s}$とするv) $ \bar{c}_{N,s}\geq 0$であれば

$\displaystyle \vec{x}_{B}^{\ast}=\vec{B}^{-1}\vec{b}, \quad \vec{x}_N^{\ast}=\vec{0}$ (20)

が最適解なので終了する。 $ \bar{c}_{N,s}<0$であれば ステップ2に進む。
(ステップ2)
非基底行列$ \vec{N}$の第$ s$ $ \vec{a}_{j_{s}}$を取り, 線形方程式

$\displaystyle \vec{B}\bar{\vec{a}}_{s}=\vec{a}_{j_{s}}$ (21)

を解いてベクトル $ \bar{\vec{a}}_{s}$を求める。 $ \bar{\vec{a}}_{s} \leq \vec{0}$なら終了(無限解が存在する)。 そうでないときは, $ \bar{\theta}=\min\{\bar{b}_i/\bar{a}_{s;i}: \bar{a}_{s;i}>0, 1 \leq i \leq m \}$ とする。ある$ r$に対して $ \bar{\theta}=\bar{b}_r/\bar{a}_{s;r}$となっているので, このような添字$ r$を選ぶvi)
(ステップ3)
添字$ r$$ s$を用いて 基底行列を

$\displaystyle \vec{B}=[\vec{a}_{i_1},\ldots,\vec{a}_{i_{r-1}}, \vec{a}_{i_{r}},\vec{a}_{i_{r+1}},\ldots,\vec{a}_{i_{m}}]$ (22)

から

$\displaystyle \vec{B}^{\prime}=[\vec{a}_{i_1},\ldots,\vec{a}_{i_{r-1}}, \vec{a}_{j_{s}},\vec{a}_{i_{r+1}},\ldots,\vec{a}_{i_{m}}]$ (23)

に変更し, 新しい基底変数と非基底変数から 対応する $ \bar{\vec{c}}_N$を求めてステップ1に戻る。

なお, (14)の第1式の $ \bar{\vec{b}}$を求めるときには, 逆行列は使わず, 線形方程式

$\displaystyle \vec{B}\bar{\vec{b}}=\vec{b}$ (24)

を解く。一般に, 逆行列の数値計算は計算量が多くかつ誤差の影響を受けやすいので, 数値解析の分野では逆行列の計算は可能な限り回避される。

各ステップでベクトル $ \bar{\vec{c}}_N$を求めるためには $ \vec{c}_B^T\vec{B}^{-1}\vec{N}$を計算する必要があるが, これを求めるためには まず線形方程式 $ \vec{B}^T \vec{c}_{N0}=\vec{c}_B$を解いて ベクトル $ \vec{c}_{N0}$を求め, 続いて $ \vec{c}_{N0}$に行列$ \vec{N}$の転置を左から掛ける, という手順で計算をおこなう。

$\displaystyle (\vec{c}_B^T\vec{B}^{-1}\vec{N})^T=\vec{N}^T(\vec{B}^T)^{-1}\vec{c}_B
$

だから, このようにしても正しい結果が得られることがわかる。 $ \bar{\vec{A}}_N=\vec{B}^{-1}\vec{N}$のすべての成分を計算しても 正しい結果は得られるが, これは計算量の観点からは無駄である。

ここで, シンプレックス法のステップ2で更新された基底解と ステップ3の基底行列に対応する基底解が一致することを見よう。

記法の簡単のため, 基底行列$ \vec{B}$の最後の列ベクトルと 非基底行列$ \vec{N}$の最後の列ベクトルが入れ換えられるという状況を考える。 入れ換えられる列ベクトルを明示するために, $ \vec{B}$$ \vec{N}$の最後の列ベクトルをそれぞれ $ \vec{\beta}$, $ \vec{\nu}$とし,

$\displaystyle \vec{B}= \left [ \begin{array}{c\vert c} \vec{B}_0 &\vec{\beta} \...
...c{N}= \left [ \begin{array}{c\vert c} \vec{N}_0 &\vec{\nu} \end{array} \right ]$ (25)

と書く。 また, $ \vec{e}_{n-m}$を第$ n-m$番目の単位ベクトルとする。

ステップ2では, $ \vec{x}_B$$ \vec{x}_N$がそれぞれ $ \vec{x}_B^{\prime}$ $ \vec{x}_N^{\prime}$に変更されたものとする。 すなわち,

\begin{displaymath}\begin{split}\vec{x}_B&=\vec{B}^{-1}\vec{b}, \\ \vec{x}_B^{\p...
...\vec{0},\\ \vec{x}_N^{\prime}&=\theta \vec{e}_{n-m} \end{split}\end{displaymath} (26)

である。 $ \vec{B}$の最後の列ベクトルと $ \vec{N}$の最後の列ベクトルが 入れ換えられることを仮定したから, (26)のように $ \vec{x}_B$を変更すると, $ \vec{x}_B$の最後の要素は零になる。 (25)を使うと, (26)の第2式は

$\displaystyle \vec{x}_B^{\prime}=\vec{B}^{-1}\vec{b} -\theta\vec{B}^{-1}\vec{\nu}\\ $ (27)

と書けることを注意しておく。

ここで, $ \vec{x}_B$ $ \vec{x}_B^{\prime}$の第$ m$要素とそれ以外を分け,

$\displaystyle \vec{x}_B= \left [ \begin{array}{c} \vec{\sigma}_0 \\ \hline \sig...
...rime}= \left [ \begin{array}{c} \vec{\sigma}_2 \\ \hline 0 \end{array} \right ]$ (28)

とおく。 ただし, $ \vec{\sigma}_0$ $ \vec{\sigma}_2$$ m-1$次のベクトル, $ \sigma_1$はスカラーである。

証明すべきことは, 入れ換え後の基底行列

$\displaystyle \left [ \begin{array}{c\vert c} \vec{B}_0 & \vec{\nu} \end{array} \right ]$ (29)

に対応する解

$\displaystyle \vec{x}_B^{\prime\prime}= \left [ \begin{array}{c\vert c} \vec{B}...
...} \end{array} \right ]^{-1} \vec{b}, \quad \vec{x}_N^{\prime\prime}=\vec{0},\\ $ (30)

が添字の並べ換えによって $ \vec{x}_B^{\prime}$, $ \vec{x}_N^{\prime}$と一致すること, すなわち

$\displaystyle \vec{x}_B^{\prime\prime}= \left [ \begin{array}{c} \vec{\sigma}_{2}\\ \hline \theta \end{array} \right ]$ (31)

となることである。

これを示すための準備として, まず行列(29)が正則であることを 背理法によって示しておく。 行列(29)が正則でないと 仮定しよう。 行列$ \vec{B}$は実行可能基底行列であって正則だから, この仮定はベクトル$ \vec{\nu}$が行列$ \vec{B}_0$の列ベクトルの線形結合となることを意味する。 さて, (27)より, $ \vec{B}\vec{x}_B^{\prime}=\vec{b} -\theta\vec{\nu}$ であるが, (28)の第2式を用いると, これは

$\displaystyle \vec{B}_0 \vec{\sigma}_2=\vec{b} -\theta\vec{\nu}$ (32)

と書き直せる。 ところで, $ \vec{\nu}$は行列$ \vec{B}_0$の列ベクトルの線形結合だったから, あるベクトル $ \vec{\sigma}_3$に対し, $ \vec{\nu}=\vec{B}_0 \vec{\sigma}_3$となる。 これを(32)に代入すると,

$\displaystyle \vec{b}=\vec{B}_0 (\vec{\sigma}_2 +\vec{\sigma}_3)$ (33)

となる。 一方, (26)の第1式と(28)の第1式より, $ \vec{B}_0 \vec{\sigma}_0 +\vec{\beta} \sigma_1 =\vec{b}$ であり, これと(33)を合わせると

$\displaystyle \vec{\beta} \sigma_1 =\vec{B}_0 (\vec{\sigma}_2 +\vec{\sigma}_3 -\vec{\sigma}_0)$ (34)

が得られる。 ゆえに, ベクトル $ \vec{\beta}$は行列$ \vec{B}_0$の列ベクトルの線形結合である。 一方, 行列$ \vec{B}$は正則である。 これは矛盾である。 以上によって行列(29)が正則であることが示された。

続いて, (31)を示そう。 このために,

$\displaystyle \vec{x}_B^{\prime\prime}= \left [ \begin{array}{c} \vec{\sigma}_4 \\ \hline \sigma_5 \end{array} \right ]$ (35)

とおく。 このとき, (30)より, $ \vec{B}_0 \vec{\sigma}_4+\vec{\nu}\sigma_5 = \vec{b}$ であり, これを(32)に代入して整理すると,

$\displaystyle \vec{B}_0 \left ( \vec{\sigma}_4- \vec{\sigma}_2\right ) = \vec{\nu} \left ( \theta - \sigma_5 \right )$ (36)

が得られる。 一方, ベクトル$ \vec{\nu}$が行列$ \vec{B}_0$の各列ベクトルの線形結合で 表されないことはすでに示されているから, (36)が成り立つということは, $ \vec{\sigma}_4=\vec{\sigma}_2$, $ \sigma_5=\theta$ を意味する。 以上によってシンプレックス法のステップ2で更新された解が ステップ3の基底解と一致することが示された。


next up previous
Next: もとの問題の最適解の抽出 Up: シンプレックス法 Previous: シンプレックス法
Shigeru HANBA
平成16年3月19日