next up previous
Next: ビッグM法の問題が有限の最適解を持たないとき Up: ビッグM法による最適化の結果ともとの問題の解の関係 Previous: ビッグM法による最適化の結果ともとの問題の解の関係

ビッグM法により有限の最適解が求められたとき

ビッグM法で有限の最適解 $ [\vec{x}^{\ast T},\vec{\xi}^{\ast T}]^T$が 得られているものとする。 このとき, $ \vec{\xi}^{\ast T}$が零ベクトルなら, $ \vec{x}^{\ast}$は問題(5)の最適解である。 一方, $ \vec{\xi}^{\ast}$が零ベクトルでないときには, 問題(5)の 制約条件を満たす領域は存在しない。

(証明)まず最初に, $ \vec{\xi}^{\ast}= \vec{0}$の場合を考える。 制約条件を満たす任意の点$ \vec{x}$に対し, $ [\vec{x}^T,\vec{0}^T]^T$は(43)の制約条件を満たす。 一方, $ [\vec{x}^{\ast T},\vec{0}^T]^T$は(43)の最小解だから,

$\displaystyle \vec{c}_2^T \begin{bmatrix}\vec{x}^{\ast}\\ \vec{0} \end{bmatrix} \leq \vec{c}_2^T \begin{bmatrix}\vec{x}\\ \vec{0} \end{bmatrix}$ (44)

である。 すなわち, $ \vec{x}^{\ast}$は(5)の最小解である。

次に, $ \vec{\xi}^{\ast} \neq {\vec0}$の場合を考える。 このとき, (5)の制約条件を満たす点は存在しないことを 背理法によって示す。まず最初に, $ [\vec{x}^{\ast T},\vec{\xi}^{\ast T}]^T$の候補は 実行可能基底解全体の集合であって, これは実行可能基底行列の集合から決まる有限集合ことに注意する。 この集合は(43)の制約条件のみから決定され, $ M$には依存しない。

さて, 制約条件を満たす点$ \vec{x}$が存在すれば, $ [\vec{x}^T,\vec{0}^T]^T$は(43)の制約条件を満たすから,

$\displaystyle \vec {c}_2^T \begin{bmatrix}\vec {x}^{\ast}\\ \vec {\xi}^{\ast} \end{bmatrix} \leq \vec {c}_2^T \begin{bmatrix}\vec {x}\\ \vec {0} \end{bmatrix}$ (45)

でなければならない。 一方, (45)の左辺は $ M$を大きくすれば$ + \infty$に発散する( $ \vec{\xi}^{\ast}$は有限で 零でないことに注意)。これは矛盾である。 したがって, 制約条件を満たす点$ \vec{x}$が存在しないことがいえる。


next up previous
Next: ビッグM法の問題が有限の最適解を持たないとき Up: ビッグM法による最適化の結果ともとの問題の解の関係 Previous: ビッグM法による最適化の結果ともとの問題の解の関係
Shigeru HANBA
平成16年3月19日