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


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

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

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

を解くことにより最適解の一部 $ \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,...]
$

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

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

$\displaystyle \min \{ x_1+x_2: 1 \leq x_1 \leq 2, 1 \leq x_2 \leq 2, x_1 \geq 0, x_2 \geq 0\}$ (38)

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

図 2: 問題(38)の制約条件を満たす領域
% latex2html id marker 7580
\includegraphics[scale=1]{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, \quad x_3 \geq 0
$

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

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

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

$\displaystyle x_2-x_5=1, x_5 \geq 0,
x_2+x_6=2, x_6 \geq 0
$

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

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

とおくと, この問題は

\begin{displaymath}\begin{split}&\min\{\vec{c}^T \vec{x}: \vec{A} \vec{x}=\vec{b...
...\vec{c}&=\begin{bmatrix}1,1,0,0,0,0 \end{bmatrix}^T \end{split}\end{displaymath} (39)

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

次に, (39)の実行可能基底行列と 実行可能基底解を求めてみよう。基底変数を決めるときには 1から6までの添字の中から4個の添字を選ぶことになるので, 可能な組み合わせの数は $ \begin{pmatrix}
6\\ 4
\end{pmatrix}=15$ 通りである。 一方, 実行可能基底解は図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)$から始めることに対応)。 これに対応する基底行列は $ \vec{B}=[\vec{a}_{1},\vec{a}_{2},\vec{a}_{3},\vec{a}_{5}]$ であり, 非基底行列は $ \vec{N}=[\vec{a}_{4},\vec{a}_{6}]$ である。また, $ \vec{c}_B=[1,1,0,0]^T$, $ \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}$ (40)

が得られる。

もとの問題の解の復元 計算終了時の基底変数ベクトルが $ \vec{x}_B=[x_1,x_2,x_4,x_6]^T$であったことと 最適解が $ \vec{x}_B=\bar{\vec{b}}$, $ \vec{x}_N=\vec{0}$とあらわされることを思い出すと, (40)から, $ 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)$に到達していることがわかる。


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