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

方針 実行可能領域は $x_i\ge 0$ と $x_1+x_2+x_3+x_4=6$ から各 $x_i\le 6$ となり有界で、空でない。したがって最大値は存在し、実行可能領域の端点、すなわち実行可能な基底解で達成される。そこで基底解をすべて求め、実行可能なものの $z$ を比べる。

等式制約は $2$ 本、変数は $4$ 個なので、$4$ 個から $2$ 個を基底変数に選び、残り $2$ 個（非基底変数）を $0$ とおいて連立 1 次方程式を解く。選び方は ${}_4{\mathrm{C}}_2=6$ 通りである。

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

(2) 基底 $\{x_1,x_3\}$（$x_2=x_4=0$）: $x_1+x_3=6,x_1+3x_3=10$。引いて $2x_3=4$ より $x_3=2$、$x_1=4$。実行可能で、$z=4+8=12$。

(3) 基底 $\{x_1,x_4\}$（$x_2=x_3=0$）: 第 2 式より $x_1=10$、第 1 式より $x_4=6-10=-4<0$。実行不可能。

(4) 基底 $\{x_2,x_3\}$（$x_1=x_4=0$）: $x_2+x_3=6,2x_2+3x_3=10$。第 1 式を 2 倍して引くと $x_3=-2<0$。実行不可能。

(5) 基底 $\{x_2,x_4\}$（$x_1=x_3=0$）: 第 2 式より $x_2=5$、第 1 式より $x_4=6-5=1$。実行可能で、$z=3\cdot 5=15$。

(6) 基底 $\{x_3,x_4\}$（$x_1=x_2=0$）: 第 2 式より $x_3=\frac{10}{3}$、第 1 式より $x_4=6-\frac{10}{3}=\frac{8}{3}$。実行可能で、$z=4\cdot \frac{10}{3}=\frac{40}{3}$。

比較 実行可能な基底解での $z$ の値は $14,12,15,\frac{40}{3}(\fallingdotseq 13.3)$ である。最大は $15$ で、これを与える端点は (5) の $1$ 個だけである。最適解の集合は最適な端点の凸包なので、最適解はただ 1 つに定まる。

よって最適解は $(x_1,x_2,x_3,x_4)=(0,5,0,1)$（最大値 $z=15$）である。

制約を $A\mathbf{x}=\mathbf{b}$ の形に書くと、$A=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 2& 3& 0\end{array}\right)$、$\mathbf{b}=(6,10{)}^T$ である。基底に選ぶ 2 列の組 ${}_4{C}_2=6$ 通りについて基底解を求める。

• $\{1,2\}$: $x_1+x_2=6,x_1+2x_2=10$ より $x_2=4,x_1=2$。解は $(2,4,0,0)$ で実行可能。$z=2+12=14$。
• $\{1,3\}$: $x_1+x_3=6,x_1+3x_3=10$ より $x_3=2,x_1=4$。解は $(4,0,2,0)$ で実行可能。$z=4+8=12$。
• $\{1,4\}$: $x_1=10$ より $x_4=6-10=-4<0$。実行不能。
• $\{2,3\}$: $x_2+x_3=6,2x_2+3x_3=10$ より $x_3=-2<0$。実行不能。
• $\{2,4\}$: $2x_2=10$ より $x_2=5$、$x_4=6-5=1$。解は $(0,5,0,1)$ で実行可能。$z=15$。
• $\{3,4\}$: $3x_3=10$ より $x_3=10/3$、$x_4=6-10/3=8/3$。解は $(0,0,10/3,8/3)$ で実行可能。$z=40/3$。

実行可能領域は有界（$x_i\ge 0$ かつ和が 6）なので最適解は基底解の中にある。実行可能な基底解の目的関数値は $14,12,15,40/3$ で、最大は $15$ である。

検算として $(0,5,0,1)$ を代入する。$0+5+0+1=6$、$0+10+0=10$ で制約を満たす。$z=0+15+0=15$ となり一致する。

よって最適解は $(x_1,x_2,x_3,x_4)=(0,5,0,1)$、最大値は $15$ である。