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

標準形と初期辞書

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

第 1 回のピボット

$z$ の式で係数が正の非基底変数は $x_1$（係数 $3$）と $x_2$（係数 $2$）なので、まだ最適ではない。係数が最大の $x_1$ を入る変数にする。

$x_2=0$ のまま $x_1$ を増やすとき、各基底変数が負にならない限界を調べる（最小比テスト）：
- $s_1=4-x_1\geqq 0$ より $x_1\leqq 4/1=4$
- $s_2=6-2x_1\geqq 0$ より $x_1\leqq 6/2=3$

最小は $3$ なので、出る変数は $s_2$ である。$s_2$ の式を $x_1$ について解くと
$$x_1=3-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2$$
これを他の式に代入する：
$$s_1=4-\left(3-\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=3\left(3-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2\right)+2x_2=9+\frac{1}{2}{x}_2-\frac{3}{2}{s}_2$$
基底解は $(x_1,x_2,s_1,s_2)=(3,0,1,0)$、$z=9$。

第 2 回のピボット

$z$ の式で $x_2$ の係数 $\frac{1}{2}$ が正なので、まだ改善できる。入る変数は $x_2$。

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

最小は $2$ なので、出る変数は $s_1$。$s_1$ の式を $x_2$ について解くと
$$x_2=2-2s_1+s_2$$
代入して
$$x_1=3-\frac{1}{2}(2-2s_1+s_2)-\frac{1}{2}{s}_2=2+s_1-s_2$$
$$z=9+\frac{1}{2}(2-2s_1+s_2)-\frac{3}{2}{s}_2=10-s_1-s_2$$

最適性の判定

$z=10-s_1-s_2$ で、非基底変数 $s_1,s_2$ の係数はどちらも負である。$s_1,s_2\geqq 0$ なので $z\leqq 10$ が常に成り立ち、$s_1=s_2=0$ のとき $z=10$ となる。よってこの基底解が最適で、
$$x_1=2,x_2=2,z=10$$
（確認：$2+2=4\leqq 4$, $2\cdot 2+2=6\leqq 6$, $3\cdot 2+2\cdot 2=10$。）

答え：$(x_1,x_2,z)=(2,2,10)$

スラック変数を導入して $x_1+x_2+s_1=4$、$2x_1+x_2+s_2=6$ とする。初期基底は $(s_1,s_2)$ で、$x_1=x_2=0$、$s_1=4$、$s_2=6$、$z=0$。

反復1: 目的関数の係数は $x_1$ が 3、$x_2$ が 2 なので、最大の $x_1$ が入る。比 $4/1=4$、$6/2=3$ の最小は第2行なので、$s_2$ が出る。第2行を 2 で割ると $x_1+\frac{1}{2}{x}_2+\frac{1}{2}{s}_2=3$。第1行から引くと $\frac{1}{2}{x}_2+s_1-\frac{1}{2}{s}_2=1$。目的関数は $z=3x_1+2x_2=3(3-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2)+2x_2=9+\frac{1}{2}{x}_2-\frac{3}{2}{s}_2$。

反復2: $x_2$ の係数 $\frac{1}{2}>0$ なので $x_2$ が入る。比は第1行 $1/(1/2)=2$、第2行 $3/(1/2)=6$ で、最小は第1行なので $s_1$ が出る。第1行を 2 倍して $x_2+2s_1-s_2=2$。第2行は $x_1=3-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2=3-1-s_1+\frac{1}{2}{s}_2-\frac{1}{2}{s}_2=2-s_1$ となる。目的関数は $z=9+\frac{1}{2}(2-2s_1+s_2)-\frac{3}{2}{s}_2=10-s_1-s_2$。

非基底変数 $s_1,s_2$ の係数がともに負なので最適。$x_1=2$、$x_2=2$、$z=10$。

検算: $x_1+x_2=4\leqq 4$、$2x_1+x_2=6\leqq 6$ で実行可能。$z=3\cdot 2+2\cdot 2=10$。双対解 $y=(1,1)$ で $y_1+2y_2=3$、$y_1+y_2=2$ が成り立ち、双対目的関数 $4+6=10$ で一致する。