最適化・線形計画法の問題

1. 初期辞書を作る

スラック変数 $s_1,s_2\geqq 0$ を加えると、制約は
$$x_1+x_2+s_1=5,2x_1+x_2+s_2=8$$
となる。基底変数を $s_1,s_2$、非基底変数を $x_1,x_2$ として、初期辞書は
$$\begin{array}{rl}{s}_1& =5-x_1-x_2\\ s_2& =8-2x_1-x_2\\ z& =0+4x_1+3x_2\end{array}$$
である。非基底変数を $0$ とおくと、基底解は $(x_1,x_2)=(0,0)$、$z=0$ である。

2. 1 回目のピボット

$z$ の式で係数が正の非基底変数は $x_1$（係数 $4$）と $x_2$（係数 $3$）である。係数が最大の $x_1$ を入る変数とする。

$x_2=0$ のまま $x_1$ を増やすとき、基底変数が負にならない範囲を調べる（最小比テスト）。
- $s_1=5-x_1\geqq 0$ より $x_1\leqq 5$
- $s_2=8-2x_1\geqq 0$ より $x_1\leqq 4$

最小は $4$ なので、$s_2$ が出る変数である。

$s_2$ の式を $x_1$ について解くと
$$x_1=4-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2.$$
これを他の式に代入する。
$$s_1=5-\left(4-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2\right)-x_2=1-\frac{1}{2}{x}_2+\frac{1}{2}{s}_2,$$
$$z=4\left(4-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2\right)+3x_2=16+x_2-2s_2.$$
このとき基底解は $(x_1,x_2)=(4,0)$、$z=16$ である。

3. 2 回目のピボット

$z=16+x_2-2s_2$ で係数が正なのは $x_2$（係数 $1$）だけなので、$x_2$ を入る変数とする。

$s_2=0$ のまま $x_2$ を増やすときの最小比テスト：
- $x_1=4-\frac{1}{2}{x}_2\geqq 0$ より $x_2\leqq 8$
- $s_1=1-\frac{1}{2}{x}_2\geqq 0$ より $x_2\leqq 2$

最小は $2$ なので、$s_1$ が出る変数である。

$s_1$ の式を $x_2$ について解くと
$$x_2=2-2s_1+s_2.$$
これを代入して
$$x_1=4-\frac{1}{2}(2-2s_1+s_2)-\frac{1}{2}{s}_2=3+s_1-s_2,$$
$$z=16+(2-2s_1+s_2)-2s_2=18-2s_1-s_2.$$

4. 最適性の判定

$z=18-2s_1-s_2$ で、非基底変数 $s_1,s_2$ の係数はどちらも負である。$s_1,s_2\geqq 0$ なので $z\leqq 18$ であり、$s_1=s_2=0$ のとき等号が成り立つ。よってこの辞書が最適で、
$$x_1=3,x_2=2,z=18.$$

（確認：$3+2=5\leqq 5$、$2\cdot 3+2=8\leqq 8$ で実行可能であり、$4\cdot 3+3\cdot 2=18$ である。）

答えは $(x_1,x_2,z)=(3,2,18)$。

スラック変数 $s_1,s_2\geqq 0$ を導入し、$x_1+x_2+s_1=5$、$2x_1+x_2+s_2=8$ とする。

初期辞書: $s_1=5-x_1-x_2$、$s_2=8-2x_1-x_2$、$z=4x_1+3x_2$。基底変数は $s_1,s_2$ で、初期解は $(0,0)$、$z=0$。

1回目の反復: 目的関数の係数が最大の非基底変数は $x_1$（係数4）なので、$x_1$ が入る。最小比テストは $s_1$ 行が $5/1=5$、$s_2$ 行が $8/2=4$。最小は4なので $s_2$ が出る。
$x_1=4-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2$ となる。
$s_1=5-(4-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2)-x_2=1-\frac{1}{2}{x}_2+\frac{1}{2}{s}_2$。
$z=4(4-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2)+3x_2=16+x_2-2s_2$。

2回目の反復: 係数が正の非基底変数は $x_2$（係数1）のみなので、$x_2$ が入る。比は $x_1$ 行が $4/(1/2)=8$、$s_1$ 行が $1/(1/2)=2$。最小は2なので $s_1$ が出る。
$x_2=2-2s_1+s_2$。
$x_1=4-\frac{1}{2}(2-2s_1+s_2)-\frac{1}{2}{s}_2=3+s_1-s_2$。
$z=16+(2-2s_1+s_2)-2s_2=18-2s_1-s_2$。

目的関数の係数がすべて負になったので最適である。非基底変数 $s_1=s_2=0$ より $x_1=3$、$x_2=2$、$z=18$。

検算: $x_1+x_2=5\leqq 5$、$2x_1+x_2=8\leqq 8$ で両制約が等号。$z=4\cdot 3+3\cdot 2=18$。実行可能領域の頂点は $(0,0),(4,0),(3,2),(0,5)$ で、$z$ の値はそれぞれ $0,16,18,15$。最大は18で一致する。