数理最適化（単体法②）

今回は例題を解きながら単体法の解き方の流れを見ていきます。

例題を解いてみる

単体法の概略を知るために、オペレーションズリサーチ学会の入門解説を使って、流れを見ていきたいと思います。

例題

目的関数を最小化する。

$$
u = −x_1 − x_2\\
$$

制約条件

$$
2x_1 + x_2 \leq 6\\
x_1 + 3x_2 \leq 8\\
x_1 \geq 0,    x_2 \geq 0
$$

解いていきます

この制約条件を、標準系に変換します。

$$
2x_1 + x_2 + s_1 = 6\\
x_1 + 3x_2 + s_2 = 8\\
x_i \geq 0    \forall i\\
s_i \geq 0    \forall i
$$

となります。
変数が4個（x1, x2, s1, s2）あります。
この中から、制約条件に含まれる等式の数だけ変数を選びます。
（2個選ぶ）
今回は s1 と s2 を選んでみます。
　　基底変数　：s1、s2
　　非基底変数：x1、x2
これを、基底変数とします。（x1, x2 が非基底変数となる）

すると、以下のようになります。

$$
u = 0\\
x_1 = 0\\
x_2 = 0\\
s_1 = 6\\
s_2 = 8\\
$$

そうすると、この目的関数 u = 0（基底解） も、簡単に求めることができます。
この解は、元の不等式条件をすべて満たします。
よって、「実行可能な基底解」となります。
単体法は、このように求めた実行可能な基底解から開始します。

目的関数 u = −x1 − x2 をみると、x1 と x2 の係数が負となってい ます。
つまり、非基底変数 x1 あるいは x2 の値を増やすと目的関数の値が減少します。
目的関数の最小値を求めるため、出発点から目的関数の値が減少するようにします。
それには、係数が負となっている非基底変数の値を 0 から増加させます。
そのような一つの変数を1つ選びます。
たとえば x1 を選んだ時、 x1 以外の非基底変数を 0 に固定し、x1 の値を 0 から増加させると目的関数の値と基底変数の値は

$$
u = −x_1\\
s_1 = 6 − 2x_1\\
s_2 = 8 − x_1
$$

となります。
x1 の値を 0 から増やしていくと、目的関数 u の値が減少し、基底変数 s1 と s2 の値 も減っていきます。
変数 s1 、s2 共に 0 以上であ るためには
　x1 ≤ 3
を満たす必要があります。
よって、すべての基底変数の値が 0 以上という条件 を満たすためには、
　0 ≤ x1 ≤ 3
でなければなりません。
x1が最大となる x1 = 3 のとき、s1 = 0 となります。
これは、x1 を基底変数とし、s1 を非基底変数（値を0とする変数）とする新 しい実行可能基底解が得られます。
　　基底変数　：x1、s2
　　非基底変数：x2、s1
この新しい基底解を 表す辞書を次の手順で計算します。

1. 基底変数ではなくなる s1 の式を、新しく規定変数となる x1 を示す式に変換します

2. 他の式の x1 を先ほどの「x1を示す式」で置き換えます

3. 目的関数を先ほどの「x1を示す式」で置き換えます

では、順番に見ていきたいと思います。
元の式は、以下です。

$$
u = −x_1 − x_2\\
2x_1 + x_2 + s_1 = 6\\
x_1 + 3x_2 + s_2 = 8\\
$$

これを、「x1を示す式」に変換します。

$$
x_1 = 3 - \dfrac{1}{2}x_2 - \dfrac{1}{2}s_1
$$

他の式の x1 を先ほどの「x1を示す式」で置き換えます。

$$
s_2 = 8 - x_1 - 3x_2\\
= 8 - ( 3 - \dfrac{1}{2}x_2 - \dfrac{1}{2}s_1 ) - 3x_2\\
= 5 - \dfrac{5}{2}x_2 + \dfrac{1}{2}s_1
$$

目的関数の x1 も先ほどの「x1を示す式」で置き換えます。

$$
u = -x_1 - x_2\\
= - ( 3 - \dfrac{1}{2}x_2 - \dfrac{1}{2}s_1 ) -x_2\\
= -3 - \dfrac{1}{2}x_2 + \dfrac{1}{2}s_1
$$

これをまとめると、以下のようになります。

$$
最小化   u = -3 - \dfrac{1}{2}x_2 + \dfrac{1}{2}s_1\\
x_1 = 3 - \dfrac{1}{2}x_2 - \dfrac{1}{2}s_1\\
s_2 = 5 - \dfrac{5}{2}x_2 + \dfrac{1}{2}s_1\\
x_i \geq 0    \forall i\\
s_i \geq 0    \forall i
$$

ちなみに、この中から単体法に必要なものを抜粋すると、以下になります。

$$
u = -3 - \dfrac{1}{2}x_2 + \dfrac{1}{2}s_1\\
x_1 = 3 - \dfrac{1}{2}x_2 - \dfrac{1}{2}s_1\\
s_2 = 5 - \dfrac{5}{2}x_2 + \dfrac{1}{2}s_1
$$

これを、「辞書」と呼びます。
単体法は、この辞書を更新しながら最適解を求めていきます。

ここで、x2、s1 は非基底変数です。
よって、以下のようになります。

$$
u = -3\\
x_1 = 3\\
s_2 = 5\\
$$

つまり、

$$
u = -3\\
x_1 = 3\\
x_2 = 0\\
s_1 = 0\\
s_2 = 5
$$

となります。
同じ手順を繰り返します。

$$
s_2 = 5 - \dfrac{5}{2}x_2 + \dfrac{1}{2}s_1
$$

この x2 を大きくしていくと、x2 = 2 の時、s1 = 0、s2 = 0 となります。
そこで、x2 を基底に入れ、s2 を基底から出すと、新しい実行可能基底解が得られます。
　　基底変数　：x1、x2
　　非基底変数：s1、s2
これを、同じように解いていきます。

$$
u = -3 - \dfrac{1}{2}x_2 + \dfrac{1}{2}s_1\\
x_1 = 3 - \dfrac{1}{2}x_2 - \dfrac{1}{2}s_1\\
s_2 = 5 - \dfrac{5}{2}x_2 + \dfrac{1}{2}s_1\\
$$

これを、「x2を示す式」に変換します。

$$
x_2 = 2 + \dfrac{1}{5}s_1 - \dfrac{2}{5}s_2
$$

他の式の x2 を先ほどの「x2を示す式」で置き換えます。

$$
x_1 = 3 - \dfrac{1}{2}x_2 - \dfrac{1}{2}s_1\\
= 3 - \dfrac{1}{2}(2 + \dfrac{1}{5}s_1 - \dfrac{2}{5}s_2) - \dfrac{1}{2}s_1\\
= 2 - \dfrac{3}{5}s_1 + \dfrac{1}{5}s_2\\
$$

目的関数の x2 も先ほどの「x2を示す式」で置き換えます。

$$
u = -3 - \dfrac{1}{2}x_2 + \dfrac{1}{2}s_1\\
= -3 - \dfrac{1}{2}(2 + \dfrac{1}{5}s_1 - \dfrac{2}{5}s_2) + \dfrac{1}{2}s_1\\
= -4 + \dfrac{2}{5}s_1 + \dfrac{1}{5}s_2\\
$$

これをまとめると、以下のようになります。

$$
u = -4 + \dfrac{2}{5}s_1 + \dfrac{1}{5}s_2\\
x_1 = 2 - \dfrac{3}{5}s_1 + \dfrac{1}{5}s_2\\
x_2 = 2 + \dfrac{1}{5}s_1 - \dfrac{2}{5}s_2\\
x_i \geq 0    \forall i\\
s_i \geq 0    \forall i
$$

ここで、s1、s2  は非基底変数です。
よって、以下のようになります。

$$
u = -4\\
x_1 = 2\\
x_2 = 2\\
$$

つまり、

$$
u = -4\\
x_1 = 2\\
x_2 = 2\\
s_1 = 0\\
s_2 = 0
$$

となります。

目的関数を見てみると、s1 と s2 の係数が正です。

$$
u = -4 + \dfrac{2}{5}s_1 + \dfrac{1}{5}s_2\\
$$

あり，s1 ≥ 0 と s2 ≥ 0 とい う条件から，u の値を −4 より小さくすることはできません。
よって、これが最適解となります。
つまり、x1=2、x2=2 が、元々の課題の最適解ということになります。

最小化を求める問題では、下記条件で探索終了となります。
「実行可能基底解を表す辞書で、目的関数に おける非基底変数の係数がすべて 0 以上」
この時、最適解となります。