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

方針. 実行可能領域が空でなく有界な線形計画問題では、最適解は実行可能領域の端点（実行可能な基底解）に現れる。そこで基底解をすべて求め、実行可能なものの中で $z$ を比べる。

最適解が存在すること. $x_1+x_2+x_3=6$ かつ $x_1,x_2,x_3\geqq 0$ より各 $x_i$ は $0\leqq x_i\leqq 6$ を満たすので、実行可能領域は有界である。また下で見るように実行可能な点がある。よって最大値が存在し、実行可能な基底解のどれかで達成される。

基底解の列挙. 等式制約は 2 本、変数は 3 個なので、変数を 1 個だけ $0$ とおき、残り 2 個（基底変数）を連立方程式から求める。選び方は 3 通りある。

(1) $x_3=0$（基底変数 $x_1,x_2$）:
$$x_1+x_2=6,x_1+2x_2=10$$
下の式から上の式を引いて $x_2=4$、よって $x_1=2$。$(x_1,x_2,x_3)=(2,4,0)$ はすべて $0$ 以上なので実行可能。$z=3\cdot 2+4\cdot 4+2\cdot 0=22$。

(2) $x_2=0$（基底変数 $x_1,x_3$）:
$$x_1+x_3=6,x_1+3x_3=10$$
引いて $2x_3=4$ より $x_3=2$、よって $x_1=4$。$(4,0,2)$ は実行可能。$z=3\cdot 4+0+2\cdot 2=16$。

(3) $x_1=0$（基底変数 $x_2,x_3$）:
$$x_2+x_3=6,2x_2+3x_3=10$$
上の式を 2 倍して引くと $x_3=10-12=-2$、よって $x_2=8$。$x_3=-2<0$ なので $(0,8,-2)$ は実行可能でない（比較の対象から外す）。

なお、どの場合も係数行列の行列式は $1,2,1$ で $0$ でないので、解はただ 1 つに定まり、基底解はこの 3 個で尽きている。

比較. 実行可能な基底解は $(2,4,0)$（$z=22$）と $(4,0,2)$（$z=16$）の 2 つで、大きいのは $22$ である。

したがって、$z$ の最大値は $22$ で、そのとき $(x_1,x_2,x_3)=(2,4,0)$。答えは $(22,2,4,0)$。

制約は2本の等式、変数は3個なので、基底解は2変数を基底に選び残り1変数を0とした解である。

(1) $x_3=0$ のとき、$x_1+x_2=6$、$x_1+2x_2=10$ より $x_2=4$、$x_1=2$。非負なので実行可能で、$z=6+16+0=22$。

(2) $x_2=0$ のとき、$x_1+x_3=6$、$x_1+3x_3=10$ より $x_3=2$、$x_1=4$。実行可能で、$z=12+0+4=16$。

(3) $x_1=0$ のとき、$x_2+x_3=6$、$2x_2+3x_3=10$ より $x_3=10-12=-2$、$x_2=8$。$x_3<0$ なので実行不可能。

実行可能領域は有界（$x_i\geqq 0$ かつ和が6）で、最大値は実行可能基底解のいずれかで達成される。よって最大は (1) の $z=22$。

検算：$(2,4,0)$ は $2+4+0=6$、$2+8+0=10$ を満たす。$z=3\cdot 2+4\cdot 4=22$。

別の確認：パラメータ表示は $x_2=4-2t$、$x_1=2+t$、$x_3=t$ ($0\le t\le 2$)。$z=3(2+t)+4(4-2t)+2t=22-3t$ なので、$t=0$ で最大 22。