next up previous
Next: 内点法 Up: ビッグM法による最適化の結果ともとの問題の解の関係 Previous: ビッグM法により有限の最適解が求められたとき

ビッグM法の問題が有限の最適解を持たないとき

問題(43)が有限の最適解を持たないときには, 問題(5)も有限の最適解を持たない。

(証明)ビッグM法が有限の最適解を持たないと判定された段階 における基底変数ベクトルを $ \vec{x}_B$, 非基底変数ベクトルを $ \vec{x}_N$とする。 非基底変数ベクトルの第$ i$成分を動かすことで目的関数が任意に小さくできるものとする。 すなわち, $ \vec {e}_i$を第$ i$単位ベクトルとしたとき, $ \vec{x}_B$ $ \vec{x}_N$をそれぞれ

\begin{displaymath}\begin{array}{lrcr} \vec {x}_B: &\vec {B}^{-1}\vec {b} &\righ...
...{x}_N: & \vec {0} & \rightarrow &\theta\vec {e}_i\\ \end{array}\end{displaymath} (46)

とすると目的関数が減少し, かつ$ \theta$は任意の正の値を取りうる。 このとき, 解は $ \Delta\vec {x}_B = -\vec {B}^{-1}\vec {N}\vec {e}_i$, $ \Delta\vec {x}_N = \vec {e}_i$ なる方向に動く。 また, $ \theta$が正の任意の値を取っても制約条件 $ \vec {x}\geq 0$は つねに満たされることから, $ \Delta\vec {x}_B \geq \vec {0}$である。 また, $ \Delta\vec {x}_B$, $ \Delta\vec {x}_N$$ M$に依存しない。 さらに,

$\displaystyle \vec {B} \Delta\vec {x}_B + \vec {N} \Delta\vec {x}_N = \vec {0}$ (47)

である。

さて, $ \Delta\vec {x}_B$, $ \Delta\vec {x}_N$を並べ換えて もとの変数$ \vec{x}$と人為変数 $ \vec{\xi}$に対応させると, 解が動く方向のベクトル $ \Delta \vec {x}$ $ \Delta \vec {\xi}$が得られる。 このとき, (47)より,

$\displaystyle \vec {A}_2 \begin{bmatrix}\Delta\vec {x}\\ \Delta\vec {\xi} \end{...
...trix} \begin{bmatrix}\Delta\vec {x}\\ \Delta\vec {\xi} \end{bmatrix} = \vec {0}$ (48)

である。

先の議論により, $ \Delta \vec {x} \geq \vec {0}$, $ \Delta \vec {\xi} \geq \vec {0}$であるが, 実は, 目的関数が任意に小さい値を取りうることから, $ \Delta \vec {\xi} = \vec {0}$となることがいえる。 これはなぜかというと, 問題(43)の解を

$\displaystyle \begin{bmatrix}\vec {x}\\ \vec {\xi} \end{bmatrix} + \theta \begin{bmatrix}\Delta\vec {x}\\ \Delta\vec {\xi} \end{bmatrix}$ (49)

に変更すると目的関数は $ \theta (\vec {c}^T\Delta\vec {x}+M \vec {1}^T\Delta\vec {\xi})$ だけ変動し, この変動が負であることから $ \vec {c}^T\Delta\vec {x}+M \vec {1}^T\Delta\vec {\xi} < 0$ でなければならないのだが, $ M$が十分大きく $ \Delta\vec {\xi} \neq \vec {0}$のときには これは負の値を取りえないからである。 ゆえに $ \Delta\vec {\xi} = 0$である。 ここから, $ \vec {c}^T \Delta x <0$が導かれる。

ここで, 問題(5)が有限の最適解を持つと仮定して矛盾を導こう。 $ \vec{x}^{\ast}$が問題(5)の有限の最適解であるとする。 さて, $ \Delta \vec {x} \geq \vec {0}$であり, 一方(48)より, $ \vec {A}\Delta \vec {x} = \vec {0}$となるから, $ \Delta \vec {x}$の方向に解を動かしても問題(5)の制約条件が 脅かされることはない。 よって, 正のパラメータ$ \theta$に対し, $ \vec {x}^{\ast} + \theta \Delta \vec {x}$も解である。 一方, $ \vec {c}^T \Delta \vec {x} < 0$より, $ \vec {x}^{\ast} + \theta \Delta \vec {x}$は最適解 $ \vec{x}^{\ast}$より 目的関数値を小さくする解である。 これは $ \vec{x}^{\ast}$が最適であることに矛盾する。 以上により, 問題(5)が有限の最適解を持たないことが示された。


next up previous
Next: 内点法 Up: ビッグM法による最適化の結果ともとの問題の解の関係 Previous: ビッグM法により有限の最適解が求められたとき
Shigeru HANBA
平成16年3月19日