next up previous
Next: ビッグM法 Up: シンプレックス法 Previous: 実行可能基底行列が得られている場合


もとの問題の最適解の抽出

シンプレックス法終了時に得られている実行可能基底行列を $ \vec{B}^{\ast}$とすると, 線形方程式

$\displaystyle \vec{B}^{\ast}\vec{x}_B^{\ast} = \vec{b}$ (24)

を解くことにより最適解の一部 $ \vec{x}_B^{\ast}$が得られる。残りの変数 $ \vec{x}_N^{\ast}$は零である。 $ \vec{x}_B^{\ast}$ $ \vec{x}_N^{\ast}$からもとの問題の最適解 $ \vec{x}^{\ast}$を構成するためには, どの変数が基底変数に入っていたかを 確認する必要がある。

たとえば, 基底変数が$ x_1$, $ x_3$, $ x_5$であり, $ \vec{x}_B^{\ast}=[10,20,30]$となっている場合には, もとの問題の最適解は

$\displaystyle [10,0,20,0,30,0,...]
$

である(非基底変数はすべて零である)。

$ \blacktriangleright$

例 2   シンプレックス法の挙動を調べるため, 以下のような2変数の簡単な線形計画問題を考える。


問題(26)の制約条件を満たす領域を 図2に示す。

% latex2html id marker 6755
\includegraphics{simplex-example1.eps}

目的関数は$ x_1+x_2$であるが, これは傾き$ -1$の直線上で一定値となる。 そして, この直線が左下にずれるほど目的関数の値は小さくなる。 よって, この問題の最適解は $ x_1=1,x_2=1$であることがわかる。

では, この問題を標準形に書き直そう。 不等式 $ 1 \leq x_1$は, 新しい変数$ x_3$を導入して,

$\displaystyle x_1-x_3=1, x_3 \geq 0
$

と書ける。不等式 $ x_1 \leq 2$は, 新しい変数$ x_4$を導入することで,

$\displaystyle x_1+x_4=2, x_4 \geq 0
$

のようになる。$ x_2$に関する不等式も同様にして

\begin{displaymath}
\begin{split}
x_2-x_5=1, x_5 \geq 0 \\
x_2+x_6=2, x_6 \geq 0
\end{split}\end{displaymath}

という等式に変わる。 さて,

$\displaystyle \vec{x}=[x_1,x_2,x_3,x_4,x_5,x_6]^T
$

とおくと, この問題は

$\displaystyle \min\{\vec{c}^T \vec{x}: \vec{A} \vec{x}=\vec{b}, \vec{x} \geq \v...
...1\\ 2 \end{bmatrix}, \vec{c}=\begin{bmatrix}1\\ 1\\ 0\\ 0\\ 0\\ 0 \end{bmatrix}$ (25)

という線形計画問題に書き直される。これは標準形である。

次に, (27)の実行可能基底行列と 実行可能基底解を求めてみよう。基底変数を決めるときには 1から6までの添字の中から4個の添字を選ぶことになるので, 可能な組み合わせの数は $ \begin{pmatrix}
6 4
\end{pmatrix}=15
$ 通りであるv) 。 一方, 実行可能基底解は図2の 制約条件を満たす領域(正方形)の頂点であり, 頂点の数は4個しかないから, 上記の15種類の添字の選び方のうち実行可能なものは4個しかないと推察される。 この推察は正しく, 実際に計算してみると, 特定の4通りの添字の選び方に対してのみ 実行可能基底解が得られ, それ以外の選び方では, $ \vec{B}$が正則でなくなるか, $ \vec{B}^{-1}\vec{b}$の成分の 中に負のものがあらわれるということがわかる。 表1に実行可能な基底変数ベクトルと, 実行可能基底解に対応する$ x_1$$ x_2$の値を示す。

表 1: 実行可能な基底変数ベクトルと実行可能基底解
$ \vec{x}_B$ $ (x_1,x_2)の値$
$ [x_1,x_2,x_3,x_5]^T$ (2, 2)
$ [x_1,x_2,x_3,x_6]^T$ (2, 1)
$ [x_1,x_2,x_4,x_5]^T$ (1, 2)
$ [x_1,x_2,x_5,x_6]^T$ (1, 1)

1の右の欄の値から, これらが図2の4個の頂点に対応している ことがわかる。

続いて, 基底変数ベクトルを $ \vec{x}_B=[x_1,x_2,x_3,x_5]^T$ とした場合のシンプレックス法の動作を見よう。 シンプレックス法は制約条件を満たす領域の頂点をたどって 最適解を探す方法なのだから, 点 $ (x_1,x_2)=(2,2)$から出発した場合, 2回の繰り返し計算で最適点 $ (x_1,x_2)=(1,1)$に到達できるはずである。

ループ第1回目 $ \vec{x}_B=[x_1,x_2,x_3,x_5]^T$, $ \vec{x}_N=[x_4,x_6]^T$ から出発する(点 $ (x_1,x_2)=(2,2)$から始めることに対応)。 これに対応する基底行列は

$\displaystyle \vec{B}=[\vec{a}_{1},\vec{a}_{2},\vec{a}_{3},\vec{a}_{5}]=
\begin...
...trix}
1& 0& - 1& 0\\
1& 0& 0& 0\\
0& 1& 0& - 1\\
0& 1& 0& 0\\
\end{bmatrix}$

であり, 非基底行列は

$\displaystyle \vec{N}=[\vec{a}_{4},\vec{a}_{6}]=
\begin{bmatrix}
0& 0 \\
1& 0 \\
0& 0 \\
0& 1 \\
\end{bmatrix}$

である。また,

$\displaystyle \vec{c}_B=[1,1,0,0]^T, \quad \vec{c}_N=[0,0]^T
$

となる。ここから, $ z_{B}=4$,

$\displaystyle \bar{\vec{b}}=\begin{bmatrix}2 2 1 1\end{bmatrix},
\bar{\v...
...\
0& 1\\
\end{bmatrix},
\bar{\vec{c}}_{N}=\begin{bmatrix}-1 -1\end{bmatrix}$

が得られる。

ループ第2回目 ループ第1回目の終了時の状態を継承して, $ \vec{x}_B=[x_1,x_2,x_4,x_5]^T$, $ \vec{x}_N=[x_3,x_6]^T$ から出発する。表1から, これが点 $ (x_1,x_2)=(1,2)$に対応することがわかる。 先と同様の計算により, $ z_{B}=3$,

$\displaystyle \bar{\vec{b}}=\begin{bmatrix}1 2 1 1\end{bmatrix},
\bar{\v...
...\\
0& 1\\
\end{bmatrix},
\bar{\vec{c}}_{N}=\begin{bmatrix}1 -1\end{bmatrix}$

が得られる。

ループ第3回目 ループ第2回目の終了時の状態を継承して, $ \vec{x}_B=[x_1,x_2,x_4,x_6]^T$, $ \vec{x}_N=[x_3,x_5]^T$ から出発する。表1から, これが点 $ (x_1,x_2)=(1,1)$に対応することがわかる。 この点で目的関数は最小となるから, アルゴリズムはこの段階で終了するはずである。これを確認しよう。 先と同様の計算により, $ z_{B}=2$,

$\displaystyle \bar{\vec{b}}=\begin{bmatrix}1 1 1 1\end{bmatrix}, \bar{\ve...
...& 0 0& 1 \end{bmatrix}, \bar{\vec{c}}_{N}=\begin{bmatrix}0 0\end{bmatrix}$ (26)

が得られる。

もとの問題の解の復元 計算終了時の基底変数ベクトルが $ \vec{x}_B=[x_1,x_2,x_4,x_6]^T$であったことと 最適解が $ \vec{x}_B=\bar{\vec{b}}$, $ \vec{x}_N=\vec{0}$とあらわされることを思い出すと, (28)から, $ x_1=1$, $ x_2=1$, $ x_3=0$, $ x_4=1$, $ x_5=0$, $ x_6=1$が最適解となる。 よって, $ x_1=1$, $ x_2=1$が目的関数を最小とする点であることがわかる。

以上の説明から, シンプレックス法のアルゴリズムが, 点 $ (x_1,x_2)=(2,2)$から出発し, $ (x_1,x_2)=(1,2)$という頂点を経由して 最適点 $ (x_1,x_2)=(1,1)$に到達していることがわかる。

$ \blacktriangleleft$


next up previous
Next: ビッグM法 Up: シンプレックス法 Previous: 実行可能基底行列が得られている場合
Shigeru HANBA
平成15年11月16日