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)と等価な


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

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

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

シンプレックス法

(初期化)
実行可能基底行列$ \vec{B}$が与えられているものとする。 $ \vec{B}$を使って基底形式表現(19)を求める。
(ステップ1)
$ \{\bar{c}_{N,1},\ldots,\bar{c}_{N,n-m}\}$の中で最小のものを $ \bar{c}_{N,s}$とする。条件を満たすものが複数あるときには, どれを選んでもよい。 $ \bar{c}_{N,s}\geq 0$であれば終了。 この場合には,

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

が最適解である。 $ \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}}$ (20)

を解いてベクトル $ \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$を選ぶ(条件を満たす添字が複数ある場合は, どれを選んでもよい)。
(ステップ3)
ステップ1とステップ2で得られた添字$ 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}}]$ (21)

から

$\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}}]$ (22)

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

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

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

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

また, 各ステップでベクトル $ \bar{\vec{c}}_N$を求めるためには $ \vec{c}_B^T\vec{B}^{-1}\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}$のすべての成分を計算しても 正しい結果は得られるが, これは計算量の観点からは無駄である。


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