線形計画法の標準形への変換メモ

線形計画法の問題は，すべて標準形へ変換することができる．それについてのメモ．

用語

線形計画問題：いくつかの変数が線形の等式と不等式をすべてみたすという条件のもとで，線形の関数を最適化 (最大化あるいは最小化) するような変数の値をすべて求める問題
目的関数 (objective function) ：最適化する（したい）関数
制約条件 (constraint)：満たすべき等式あるいは不等式

例：以下の最適化問題の場合

$$ \begin{array}{ll} \text{最小化: } & x_1 + x_2 \\ \text{制約条件: } & x_1 \geq 0, x_2 \geq 0 \\ \end{array} $$

目的関数：$x_1 + x_2$
制約条件：$x_1 \geq 0, x_2 \geq 0$

となる．

線形計画法の標準形

線形計画法の標準形は，以下であらわされる．変数の数 $n$ と制約条件式の数 $m\$ として

$$ \begin{array}{ll} \text{最小化 } & c_1x_1 + c_2x_2 + \cdots + c_nx_n \\ \text{制約条件 } & a{11}x_1 + a{12}x_2 \cdots + a{1n}x_n = b_1 & \vdots \\ & a{m1}x_1 + a{m2}x_2 + \cdots + a{mn}x_n = b_m \\ & (x_1, x_2, \cdots , x_n)^{T} \geq (0, 0, \cdots , 0)^{T} \\ \end{array} $$

標準形の線形計画問題の特徴

線形の目的関数を最小化する
全ての変数に$0$ 以上という非負条件(nonnegative constraint) がつく．
その他の制約が(不等式ではなく) 線形の等式であらわす．

標準形にすることのメリット

様々な形で表現できる線形計画法の問題を標準形1つに統一できる．
解を求めるシンプレックス法などのアルゴリズムでは標準形へ変換してから解くという操作をしている．

標準形への変換例

基本的は以下3つの変換を行う．

目的関数を最小化問題へ変換
不等式制約をスラック変数を導入して等式制約へ変換
非負制約のない変数（自由変数）を新しい非負変数の差へ変換

モデル化した線形計画問題が

\begin{eqnarray} \begin{array}{ll} \text{最大化} & x_1 + x_2\\ \text{制約条件} & 2x_1 + 3x2 \leq 12\\ & −x_1 + x_2 \geq −2\\ & x_2 \geq 0\\ \end{array} \end{eqnarray}

となっていたとする．

目的関数を最小化問題へ変換

目的関数を最大化している場合，それに$−1$ を乗じた$−(x_1 + x_2)$ を最小化する問題に変換する．

不等式制約をスラック変数を導入して等式制約へ変換

1つ目の不等式： $2x_1 + 3x_2 \leq 12$は，$12 − 2x_1 − 3x_2 \geq 0$ と変形して，この左辺の式を新しい変数$s_1$ に等しいとおくことにより，等式条件と変数の非負条件に変換できる．

$$ 2x_1 + 3x_2 + s_1= 12, s_1 \geq 0 $$

2つ目の不等式： $−x_1 + x_2 \geq −2$は，$−x_1 + x_2 + 2 \geq 0$ と変形して，この左辺の式を新しいスラック変数$s_2$ に等しいとおくことにより，等式条件と変数の非負条件に変換できる．

$$ −x_1 + x_2 − s_2 = −2, s_2 \geq 0$ $$

自由変数を新しい非負変数の差へ変換

$x_1$ は非負制約のない自由変数であるので，このままだと標準形の線形計画問題にならない．自由変数$x_1$ が正の値も負の値も取れるので，それを2つの非負変数$u_1^{+}$ と$u_1^{+}$ の差であらわして，

$$ x_1 = u_1^{+} − u_1^{-}, u_1^{+} \geq 0, u_1^{-} \geq 0 $$

とする．これを目的関数と制約条件の式の$x_1$へ代入して消去する．

以上をまとめると，標準形は以下になる．

$$ \begin{array}{ll} \text{最小化} & −(u_1^{+} - u_1^{-}) − x_2\\ \text{制約条件}& 2(u_1^{+} - u_1^{-}) + 3x_2 + s_1 = 12\\ & −(u_1^{+} - u_1^{-}) + x_2 − s_2 = −2\\ & u_1 \geq 0, u_2 \geq 0, x_2 \geq 0, x_3 \geq 0, x_4 \geq 0, s_1 \geq 0, s_2 \geq 0 \\ \end{array} $$

同値変換

2つの線形計画問題は，一方を解くことより他方も解くことができ，その逆も成り立つとき，同値であるという．線形計画問題は，次のような変換を加えても，得られる線形計画問題と同値である．

目的関数に正の実数を乗ずる，あるいは実数を加える．
最大化問題の目的関数に$−1$ を乗じて，最小化問題とする．逆に，最小化問題の目的関数に$−1$ を乗じて，最大化問題とする．
等式制約の両辺に$0$ でない同じ実数を乗ずる，あるいは同じ実数または式を加える．
不等式制約の両辺に同じ正の実数を乗ずる，あるいは同じ実数または式を加える．
不等式制約の両辺に$−1$ を乗じて不等号の向きを逆にする．
不等式制約$\vec{a}^T\vec{x} \leq b$ を$\vec{a}^T\vec{x} + u = b, u \geq 0$ に置き換える，あるいは不等式制約$\vec{a}^T\vec{x} \geq b$ を$\vec{a}^T\vec{x} − u = b, u \geq 0 $に置き換える．このときの変数$u$ をスラック変数という．
等式制約$\vec{a}^T\vec{x} = b$ を２つの不等式制約$\vec{a}^T\vec{x} \leq b, \vec{a}^T\vec{x} \geq b$に置き換える，あるいはその逆を行う．
自由変数$x$に対して，2つの非負変数を使って$x = u − v$ とし，それをすべての$x$に代入して$x$ を消去し，非負制約$u \geq 0, v \geq 0$ を加える．逆に，$u − v$ という形でのみ現れる2つの非負変数$u, v$ に対して，自由変数$x$ を使って$u − v = x$ を代入して$u$ と$v$ を消去する．
目的関数あるいは制約式の一部に現れる線形関数$\vec{a}^T\vec{x}$ を新しい変数$t$ で置き換え，制約条件に$\vec{a}^T\vec{x} − t = 0$ を加える．
等式制約からひとつの変数を他の変数で表し，それをすべての式に代入することにより変数をひとつ消去する．