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

初期辞書 スラック変数 $s_1,s_2,s_3$ を加えると、
$$\begin{array}{rl}{s}_1& =4-x_1-x_2\\ s_2& =6-2x_1-x_2\\ s_3& =3-x_2\\ z& =0+3x_1+2x_2\end{array}$$
非基底変数 $x_1=x_2=0$ とした基底解 $(s_1,s_2,s_3)=(4,6,3)$ はすべて $0$ 以上なので実行可能で、$z=0$ である。

1回目のピボット $z$ の行で係数が正なのは $x_1$ (3) と $x_2$ (2) で、最大の $x_1$ を入る変数にする。$x_2=0$ のまま $x_1$ を増やすとき、各基底変数が $0$ 以上である限界を調べる（最小比テスト）。
- $s_1=4-x_1\geqq 0$ より $x_1\leqq 4$
- $s_2=6-2x_1\geqq 0$ より $x_1\leqq 3$
- $s_3=3$ は $x_1$ を含まないので制限なし

最小は $3$ なので $s_2$ が出る変数。$s_2$ の式を $x_1$ について解くと $x_1=3-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2$。これを他の式に代入して、
$$\begin{array}{rl}{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\\ s_3& =3-x_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\end{array}$$
基底解は $(x_1,s_1,s_3)=(3,1,3)$、$z=9$。

2回目のピボット $z$ の行で係数が正なのは $x_2$ $\left(\frac{1}{2}\right)$ だけなので、$x_2$ を入る変数にする。$s_2=0$ のまま $x_2$ を増やすときの限界は
- $x_1=3-\frac{1}{2}{x}_2\geqq 0$ より $x_2\leqq 6$
- $s_1=1-\frac{1}{2}{x}_2\geqq 0$ より $x_2\leqq 2$
- $s_3=3-x_2\geqq 0$ より $x_2\leqq 3$

最小は $2$ なので $s_1$ が出る変数。$s_1$ の式から $x_2=2-2s_1+s_2$。これを代入して、
$$\begin{array}{rl}{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\\ s_3& =3-(2-2s_1+s_2)=1+2s_1-s_2\\ z& =9+\frac{1}{2}(2-2s_1+s_2)-\frac{3}{2}{s}_2=10-s_1-s_2\end{array}$$

最適性の判定 $z$ の行の非基底変数 $s_1,s_2$ の係数はどちらも $-1<0$ である。$s_1,s_2\geqq 0$ なので $z\leqq 10$ がつねに成り立ち、$s_1=s_2=0$ のとき $z=10$ となる。よってこの辞書は最適で、最適解は $x_1=2,x_2=2$（このとき $s_3=1$）、最適値は $z=10$ である。

（確認：$2+2=4\leqq 4$、$2\cdot 2+2=6\leqq 6$、$2\leqq 3$ を満たし、$3\cdot 2+2\cdot 2=10$。）

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

スラック変数を加えて初期辞書を作る。
$s_1=4-x_1-x_2$, $s_2=6-2x_1-x_2$, $s_3=3-x_2$, $z=3x_1+2x_2$。

1回目: 目的関数の係数が正で最大のものは $x_1$ (係数3)。比 $4/1=4$, $6/2=3$ より $s_2$ が出る変数になる。
$x_1=3-\frac{1}{2}{x}_2-\frac{1}{2}{s}_2$。
これを代入すると $s_1=1-\frac{1}{2}{x}_2+\frac{1}{2}{s}_2$, $s_3=3-x_2$, $z=9+\frac{1}{2}{x}_2-\frac{3}{2}{s}_2$。

2回目: 係数が正なのは $x_2$ (係数 1/2) のみ。$x_2$ の上限は $s_1$ から $2$、$s_3$ から $3$。よって $s_1$ が出る。
$x_2=2+s_2-2s_1$。
これを代入すると $x_1=3-\frac{1}{2}(2+s_2-2s_1)-\frac{1}{2}{s}_2=2+s_1-s_2$, $s_3=1-s_2+2s_1$, $z=9+\frac{1}{2}(2+s_2-2s_1)-\frac{3}{2}{s}_2=10-s_1-s_2$。

目的関数の係数がすべて負なので最適。$s_1=s_2=0$ のとき $x_1=2$, $x_2=2$, $z=10$。

検算: $x_1+x_2=4\leqq 4$, $2x_1+x_2=6\leqq 6$, $x_2=2\leqq 3$ を満たす。$z=3\cdot 2+2\cdot 2=10$。双対解 $y_1=1,y_2=1,y_3=0$ は $y_1+2y_2=3$, $y_1+y_2+y_3=2$ を満たし、双対目的値 $4+6=10$ で一致する。