next up previous
Next: 実行可能基底行列が得られている場合 Up: 原理 Previous: 標準形と基準形

シンプレックス法

本節ではシンプレックス法について簡単に説明する。

標準形で記述された線形計画問題:

$\displaystyle {\rm (STD)} \quad \min \left \{ z=\vec{c}^T \vec{x}: \vec{A}\vec{x} = \vec{b} , \vec{x} \geq \vec{0} \right \}$ (5)

が与えられているものとする。先に注意したように, $ \vec{A} \in {\mathbb{R}}^{m \times n}$, $ \vec{b} \in {\mathbb{R}}^{m}$, $ \vec{c} \in {\mathbb{R}}^{n}$である。また, $ n \geq m$で, 行列$ \vec{A}$は フルランクであると仮定しておく。 さらに, (STD)の制約条件を満たす領域は空でないと仮定する。

シンプレックス法は, まず制約条件を満たす基底解と 呼ばれる解iii) をひとつ見付け, 続いて最適解が得られるまで基底解を改善していく方法である。 標準形の問題が一定の条件を満たすときは, シンプレックス法を用いると有限回の計算で最適解が得られることが保証される。

ではシンプレックス法の説明に入ろう。

行列$ \vec{A}$の列ベクトル $ \vec{a}_1,\ldots,\vec{a}_n$の中から適当な$ m$個の線形独立なベクトル を選び出し, これらを並べて

$\displaystyle \vec{B}=[\vec{a}_{i_1},\ldots,\vec{a}_{i_m}]$ (6)

という行列を作る。 また, 行列$ \vec{A}$の列ベクトルから 行列$ \vec{B}$の列ベクトルを除いた残りを並べて,

$\displaystyle \vec{N}=[\vec{a}_{j_1},\ldots,\vec{a}_{j_{n-m}}]$ (7)

という行列を作る。 行列$ \vec{B}$, $ \vec{N}$はそれぞれ基底行列, 非基底行列と呼ばれる。 さらに, 行列$ \vec{B}$に対応する変数の組 $ x_{i_1},\ldots,x_{i_m}$を集めて

$\displaystyle \vec{x}_B=[x_{i_1},\ldots,x_{i_{m}}]^T$ (8)

なるベクトルを作る。$ \vec{x}_B$を基底変数ベクトルと呼ぶ。 続いて, 行列$ \vec{N}$に対応する変数の組 $ x_{j_1},\ldots,x_{j_{n-m}}$を集めて

$\displaystyle \vec{x}_N=[x_{j_1},\ldots,x_{j_{n-m}}]^T$ (9)

なるベクトルを作る。$ \vec{x}_N$を非基底変数ベクトルと呼ぶ。

ここで, 目的関数に対応するベクトル$ \vec{c}$を基底行列に対応した形に分割し,

$\displaystyle \vec{c}_B=[c_{i_1},\ldots,c_{i_m}],\quad \vec{c}_N=[c_{j_1},\ldots,c_{j_{n-m}}]$ (10)

とおくと, 目的関数 $ z=\vec{c}^T \vec{x}$

$\displaystyle z=\vec{c}_B^T\vec{x}_B+\vec{c}_N^T\vec{x}_N$ (11)

と書き直される。

さて, 変数ベクトル$ \vec{x}$

$\displaystyle \vec{x}_B=\vec{B}^{-1} \vec{b} , \quad \vec{x}_N=\vec{0}$ (12)

となるように選んでみよう。 等式制約条件 $ \vec{A} \vec{x} = \vec{b} $

$\displaystyle \vec{B} \vec{x}_B+\vec{N} \vec{x}_N= \vec{b}$ (13)

と書き直せるから, (12) から決まる$ \vec{x}$は 制約条件 $ \vec{A} \vec{x} = \vec{b} $を満たしている。 (12)で定まる$ \vec{x}$を基底解と呼ぶ。 ただし, この段階では, $ \vec{x} \geq \vec{0}$であることは保証されない。

ところで, $ \vec{B}^{-1}\vec{b} \geq \vec{0}$となる場合には, $ \vec{x}_{B}\geq 0$, $ \vec{x}_N \geq 0$となり, 基底解$ \vec{x}$は符号制約 $ \vec{x} \geq \vec{0}$を満たす。 このとき基底解$ \vec{x}$は問題(STD)のひとつの解になる。 $ \vec{B}^{-1}\vec{b} \geq \vec{0}$のとき, (12)により定まる$ \vec{x}$を実行可能基底解と呼び, 対応する行列$ \vec{B}$を実行可能基底行列と呼ぶ。

以下では, まず実行可能基底行列がひとつ得られている場合に 最適解を構成するためのアルゴリズムについて説明し, 続いて実行可能基底行列が未知の場合への拡張について述べる。




next up previous
Next: 実行可能基底行列が得られている場合 Up: 原理 Previous: 標準形と基準形
Shigeru HANBA
平成16年3月19日