線形計画法のシンプレックス法
ビルドアップ 1
$x_{1} , x_{2} \ge 0$ に関して、次の線形計画問題が与えられたとしよう。 $$ \begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 1 \\ & & x_{1} & & & \le & 3 \\ & & & & x_{2} & \le & 2 \end{matrix} $$ つまり、与えられたすべての制約条件を満たしながら $x_{1} + x_{2}$ を最大化したい。これを方程式形式に変えるためには、スラック変数 $x_{3}, x_{4}, x_{5} \ge 0$ を導入して $$ \begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & + & x_{3} & & & & & = & 1 \\ & & x_{1} & & & & & + & x_{4} & & & = & 3 \\ & & & & x_{2} & & & & & + & x_{5} & = & 2 \end{matrix} $$ のように表せばいい。これをもう一度辞書またはテーブルに表すと、元の $x_{1}$、$x_{2}$ は非基底変数となって右側に残り、$x_{3}$、$x_{4}$、$x_{5}$ は基底変数になって左側に行く。 $$ \begin{matrix} \zeta & = & & 0 & + & x_{1} & + & x_{2} \\ x_{3} & = & & 1 & + & x_{1} & - & x_{2} \\ x_{4} & = & & 3 & - & x_{1} & & \\ x_{5} & = & & 2 & & & - & x_{2} \end{matrix} $$ $$ \mathcal{N} = \left\{ 1, 2 \right\} \\ \mathcal{B} = \left\{ 3, 4, 5 \right\} $$ ここで、$\zeta = \bar{\zeta} + x_{1} + x_{2}$ の $\bar{\zeta}$ は、最適解に対する目的関数の関数の値、つまり現在どのくらい最適化されているかを意味すると見なせる。以下のいくつかの方程式を通して変数置換を行うと、$\zeta$ の右側にある非基底変数の符号を $-$ に統一できるかもしれない。すると、すべての非基底変数に $0$ を代入したとき $$ \zeta = \zeta_{?} - x_{?_{1}} - x_{?_{2}} $$ この形が最大の値になることだ。言い換えれば、これが実行可能基底を得ることだ。非基底変数の符号の中に $+$ があるということは、まだ $\zeta_{?}$ を増やす可能性があることを意味し、すべての符号が $-$ であるということは、これ以上 $\zeta_{?}$ を大きくすることはできないという意味になる。これがまさにシンプレックス・メソッドのアイデアだ。問題を代数的に解いているように見えるが、スラック変数を加えて方程式形式を作った時点で解空間がシンプレックスになるため、シンプレックスという表現を使う。
実践
$$ \begin{matrix} \zeta & = & & 0 & + & x_{1} & + & x_{2} \\ x_{3} & = & & 1 & + & x_{1} & - & x_{2} \\ x_{4} & = & & 3 & - & x_{1} & & \\ x_{5} & = & & 2 & & & - & x_{2} \end{matrix} $$ $$ \mathcal{N} = \left\{ 1, 2 \right\} \\ \mathcal{B} = \left\{ 3, 4, 5 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (0,0,1,3,2) \\ \bar{\zeta} = 0 $$
実際に上の例をシンプレックス・メソッドで解いてみよう。
$\zeta$ の形を見ると $x_{1}$ と $x_{2}$ の両方を増やすことはできるが、制約条件から $x_{4} = 3 - x_{1}$ と $x_{5} = 2 - x_{2}$ を知っているので、今のところ大きな意味はなさそうだ。$x_{3}$ についての条件を参考にすると $$ x_{2} = 1 + x_{1} - x_{3} $$ 新しい辞書は次のようになる。
$$ \begin{matrix} \zeta & = & & 1 & + & 2x_{1} & - & x_{3} \\ x_{2} & = & & 1 & + & x_{1} & - & x_{3} \\ x_{4} & = & & 3 & - & x_{1} & & \\ x_{5} & = & & 1 & - & x_{1} & + & x_{3} \end{matrix} $$ $$ \mathcal{N} = \left\{ 1, 3 \right\} \\ \mathcal{B} = \left\{ 2, 4, 5 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (0,1,0,3,2) \\ \bar{\zeta} = 1 $$
方程式で確認できるように、目的関数の値を元の比較で $1$ だけ増やした。この辞書を修正するプロセスを ピボットステップ2と呼び、非基底から基底に入った$x_{2}$ のような変数を入口変数、基底から非基底に出た $x_{3}$ のような変数を退出変数3と呼ぶ。ここで混乱してはいけないのは、目的関数自体を変えたわけではなく、これからも変えることはないということだ。ビルドアップからずっとそのように、既存の変数は単に他の変数を代表するだけであり、以前には見えなかった定数項が今見えるようになっただけだ。
今の辞書で私たちがやるべきことはかなり明確だ。$x_{1}$ を増やせば、その倍の量だけ目的関数が大きくなりそうだ。同じ理由で $x_{5}$ を入口変数として使うと $$ x_{1} = 1 + x_{3} - x_{5} $$ となり、
$$ \begin{matrix} \zeta & = & & 3 & + & x_{3} & - & 2x_{5} \\ x_{1} & = & & 1 & + & x_{3} & - & x_{5} \\ x_{2} & = & & 2 & & & - & x_{5} \\ x_{4} & = & & 2 & - & x_{3} & + & x_{5} \end{matrix} $$ $$ \mathcal{N} = \left\{ 3, 5 \right\} \\ \mathcal{B} = \left\{ 1, 2, 4 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (1,2,0,2,0) \\ \bar{\zeta} = 3 $$
となる。$\zeta$ の右側に $x_{3}$ がまだ増える余地があるので、$x_{3}$ を入口変数として使ってみると $$ x_{3} = 2 - x_{4} + x_{5} $$ となり、
$$ \begin{matrix} \zeta & = & & 5 & - & x_{4} & - & x_{5} \\ x_{1} & = & & 3 & - & x_{4} & - & \\ x_{2} & = & & 2 & & & - & x_{5} \\ x_{3} & = & & 2 & - & x_{4} & + & x_{5} \end{matrix} $$ $$ \mathcal{N} = \left\{ 4, 5 \right\} \\ \mathcal{B} = \left\{ 1, 2, 3 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (3,2,2,0,0) \\ \bar{\zeta} = 5 $$
となる。これで、$\zeta$ の右側のすべての変数の符号が $-$ であり、どの変数を触っても $\zeta$ が大きくなることはなく、最適化が完了したことがわかる。実際に、最初に与えられた線形計画問題 $$ \begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 1 \\ & & x_{1} & & & \le & 3 \\ & & & & x_{2} & \le & 2 \end{matrix} $$ に $x_{1} = 3$ と $x_{2} = 2$ を代入して再計算してみると、すべての制約条件をよく満たし、目的関数の値も正確に $\zeta = \bar{\zeta} - 0 = 5$ であることが確認できる。