next up previous
Next: ビッグM法による最適化の結果ともとの問題の解の関係 Up: シンプレックス法 Previous: もとの問題の最適解の抽出


ビッグM法

2.3.1節で述べたアルゴリズムを利用して 与えられた線形計画問題を解くためには 実行可能基底行列$ \vec{B}$が必要であった。 ところで, 問題の規模が大きいときには 実行可能基底行列をひとつ求めること自体も容易でないことが多い。 そのような状況に対処するためには, 第2.3.1節のアルゴリズムを 実行可能基底行列が未知の場合にも適用できるように 拡張しておく必要がある。

このような拡張としてよく知られているものに, 2段階法とビッグM法がある。 本節では, これらのうちビッグM法について述べる。

(STD)にビッグM法が適用可能であるためには (STD)の制約条件の右辺にあらわれるベクトル$ \vec{b} $の 各成分が非負でなければならない。そこで, $ \vec{b} $の第$ i$成分$ b_i$が負で, 対応する行列$ \vec{A}$の行ベクトルが $ \vec{\alpha}_i^T$ であるときには, $ b_i$$ -b_i$で置き換え, $ \vec{\alpha}_i^T$ $ -\vec{\alpha}_i^T$ で置き換える。これにより, もとの制約条件と等価で $ \vec{b} \geq \vec{0}$を満たす制約条件が得られる。

次に, 人為変数と呼ばれる新たな変数

$\displaystyle \vec{\xi}=[\xi_{1},\ldots,\xi_{m}]^T$ (41)

を導入し,

$\displaystyle \vec{c}_2=[\vec{c}^T,M \cdot \vec{1}_m^T]^T, \quad \vec{A}_2=[\vec{A},\vec{I}_m]$ (42)

と定義して(ただし$ \vec{1}_m$$ m$次の要素がすべて1のベクトル, $ M$は十分大きい正の定数, $ \vec{I}_m$$ m$次の単位行列), (5)から次のような問題を作る。

$\displaystyle \min \left \{ \vec{c}_2^T \begin{bmatrix}\vec{x} \\ \vec{\xi} \en...
...} \end{bmatrix}=\vec{b}, \vec{x} \geq \vec{0}, \vec{\xi} \geq \vec{0} \right \}$ (43)

もとの問題は $ \vec{b} \geq \vec{0}$となるように書き換えられていたから, $ \vec{x} =\vec{0},\vec{\xi}=\vec{b}$は(43)の制約条件を満たす。 よって, これは実行可能基底解である。 ゆえに, 問題(43)において 基底変数ベクトルとして$ \vec{\xi}$を取ると, 実行可能基底行列が得られるから, ここから出発してシンプレックス法を実行し, 最適解を求めることが可能である。

シンプレックス法の終了条件が満たされ, 繰り返し計算が終了したものとしよう。 このとき問題となるのは, もとの問題の最適解をどのようにして復元するか, ということである。

パラメータ$ M$が十分大きく, かつ 計算終了時に有限の最小値が得られた場合を考える。 この最小値に対応する$ \vec{x}$$ \vec{\xi}$をそれぞれ $ \vec{x}^{\ast}$ $ \vec{\xi}^{\ast}$とする。 このとき, $ \vec{\xi}^{\ast}= \vec{0}$であれば $ \vec{x}=\vec{x}^{\ast}$が問題(5)の最適解であることが言え, $ \vec{\xi}^{\ast}\neq \vec{0}$であれば 問題(5)は解を持たないということが言える。 ただし, パラメータ$ M$を どの程度取れば十分であるかについての基準はない。 よって, 計算終了時に $ \vec{\xi}^{\ast}\neq \vec{0}$ となったときには, $ M$を大きく取り直して シンプレックス法を再度実行する必要がある。

なお, 計算終了時の結果からもとの問題の最適解 $ \vec{x}^{\ast}$を 構成する手順は第2.3.2節と同一である。


next up previous
Next: ビッグM法による最適化の結果ともとの問題の解の関係 Up: シンプレックス法 Previous: もとの問題の最適解の抽出
Shigeru HANBA
平成16年3月19日