next up previous
Next: シンプレックス法 Up: 原理 Previous: 線形計画問題

標準形と基準形

線形計画問題の一般形は, 異なる向きの不等号や 制約条件が付いた変数と制約条件のない変数が混在しているために, 数学的に取り扱いにくい。そこで, ふつうは, 問題を標準的な形に変換してから解く。

標準的な形としてよく用いられるのは, 標準形と呼ばれるものと, 基準形と呼ばれるものである。 以下でこれらについて説明する。

以下では, 特に断らない限り, $ \vec{A}$$ m$$ n$列の実行列, $ \vec{b} $$ m$次元のベクトル, $ \vec{c}$, $ \vec{x}$$ n$次元のベクトルとする。 また, $ \vec{A}$$ m$$ n$列の実行列であることを $ \vec{A} \in {\mathbb{R}}^{m \times n}$という記法であらわし, $ \vec{x}$$ n$次元の実ベクトルであるということを $ \vec{x} \in {\mathbb{R}}^{n}$という記法であらわす。 さらに, 行列$ \vec{A}$の第$ i$番目の列ベクトルを$ \vec{a}_i$などと書き, ベクトル$ \vec{b} $, $ \vec{c}$などの第$ i$要素をそれぞれ$ b_i$, $ c_i$などと書く。 また, $ \vec{x}$$ \vec{w}$がともに$ n$次のベクトルであるとき, $ \vec{x}\geq \vec{w}$という記法によって, ベクトル$ \vec{x}$の各成分がベクトル$ \vec{w}$の対応する成分以上である, すなわち $ x_i \geq w_i$ $ (i=1,\ldots,n)$となっているということをあらわす。 零ベクトルあるいは零行列をあらわすのには記号$ \vec{0}$を使う。 次元を明示する必要があるときには$ \vec{0}_n$, $ \vec{0}_{m \times n}$などのように書く。

線形計画問題の標準形とは, 以下のような形式の問題である。

\framebox[\textwidth]{{\bf 標準形: }
$\min \{ z=\vec {c}^T \vec {x}: \vec {A} \vec {x} = \vec {b} ,\vec {x} \geq \vec {0}\}$}
この式の読み方は, 「制約条件 $ \vec{A} \vec{x} = \vec{b} $, $ \vec{x} \geq \vec{0}$ のもとで目的関数 $ z=\vec{c}^T \vec{x}$を最小化せよ」である。なお, min は minimize(最小化する)の略である。

一方, 線形計画問題の基準形とは, 次のような問題である。

\framebox[\textwidth]{{\bf 基準形: }
$\min \{ z=\vec {c}^T \vec {x}: \vec {A}\vec {x} \geq \vec {b} ,\vec {x} \geq \vec {0}\}$}

続いて, 線形計画問題の一般形を標準形に変換する手順について説明する。 このためには, 以下に述べるような一連の手順を実行すればよい。

  1. 不等式制約 $ a_{i,1}x_1+\cdots+a_{i,n} x_n \geq b_i$: 新たな変数 $ y_i \in {\mathbb{R}}$を導入し, 制約条件を $ a_{i,1}x_1+\cdots+a_{i,n} x_n -y_i\geq b_i$, $ y_i \geq 0$と書き直す。
  2. 不等式制約 $ a_{i,1}x_1+\cdots+a_{i,n} x_n \leq b_i$: 新たな変数 $ y_i \in {\mathbb{R}}$を導入し, 制約条件を $ a_{i,1}x_1+\cdots+a_{i,n} x_n +y_i\geq b_i$, $ y_i \geq 0$と書き直す。
  3. 符号制約なしの変数$ x_i$: 新たに2個の正の変数$ x_{i-}$, $ x_{i+}$を導入し, $ x_i=x_{i+}-x_{i-}$, $ x_{i+}\geq 0$, $ x_{i-}\geq 0$ と書き直す。また, $ x_i=x_{i+}-x_{i-}$を制約条件や目的関数の式に代入する。
  4. 正でない変数 $ x_i \leq 0$: $ x_i^{\prime}=-x_i$ と変数を置き直す。また, $ x_i=-x_i^{\prime}$を制約条件や目的関数の式に代入する。
  5. $ \vec{c}^T \vec{x}$を最大化する問題(最大化問題): $ \vec{c}^{\prime}=-\vec{c}$と定義して, 新たな目的関数 $ (\vec{c}^{\prime})^T \vec{x}$を最小化する。
上記の手続きのうち, 1, 2, 3では変数の数が それぞれ1個ずつ増えることを注意しておく。

上記と同様の手順によって, 線形計画問題の一般形を基準形に変換することもできる (制約条件や変数の数は増加する)。 なお, 上記とは別の方法を使うと, 等式制約条件や制約条件なしの変数を書き換える際に, 制約条件や変数の数を減らせることが知られている[6]。


next up previous
Next: シンプレックス法 Up: 原理 Previous: 線形計画問題
Shigeru HANBA
平成16年3月19日