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

シンプレックス法

本節では, 線形計画問題を解くためのシンプレックス法という アルゴリズムについて簡単に説明する。 この部分の説明はおもに文献[3],[4]による。

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

$\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)の制約条件を満たす領域は空でないと仮定する。

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

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

行列$ \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)のひとつの解になっていることがわかる。 (12)から定まる基底解$ \vec{x}$ が問題(STD)の解となるとき, この解を実行可能基底解と呼び, 対応する行列$ \vec{B}$を実行可能基底行列と呼ぶ iii)

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




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