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

方針 等式制約が $2$ 本、変数が $3$ 個なので、基底解は「$3$ 個の変数のうち $1$ 個を $0$ とし、残り $2$ 個（基底変数）を連立方程式で決めたもの」である。選び方は ${}_3{\mathrm{C}}_2=3$ 通りある。

最適解が基底解に現れる理由 $x_1,x_2,x_3\ge 0$ かつ $x_1+x_2+x_3=6$ より、各変数は $0\le x_i\le 6$ を満たす。よって実行可能領域は有界である。この領域が空でなければ最適解が存在し、線形計画法の基本定理より、最適解は端点、すなわち実行可能な基底解の中にある。したがって、実行可能な基底解の目的関数の値を比べればよい。

係数行列は $A=\left(\begin{array}{ccc}1& 1& 1\\ 1& 2& 3\end{array}\right)$、右辺は $b=\left(\begin{array}{c}6\\ 10\end{array}\right)$ である。

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

(2) 基底変数 $x_1,x_3$（$x_2=0$）
$$x_1+x_3=6,x_1+3x_3=10$$
第 $2$ 式から第 $1$ 式を引くと $2x_3=4$ より $x_3=2$、よって $x_1=4$。$(4,0,2)$ は実行可能。
$$z=2\cdot 4+3\cdot 0+1\cdot 2=10$$

(3) 基底変数 $x_2,x_3$（$x_1=0$）
$$x_2+x_3=6,2x_2+3x_3=10$$
第 $1$ 式を $2$ 倍して第 $2$ 式から引くと $x_3=-2$、よって $x_2=8$。$x_3<0$ なので $(0,8,-2)$ は実行不可能であり、候補から外す。

比較 実行可能な基底解は $(2,4,0)$（$z=16$）と $(4,0,2)$（$z=10$）の $2$ つである。$z$ が大きいのは $(2,4,0)$ なので、最適解は
$$(x_1,x_2,x_3)=(2,4,0)$$
であり、最適値は $16$ である。

制約は等式 2 本、変数は 3 個なので、基底解は 3 個の変数から基底変数を 2 個選び、残りの 1 個を 0 とおいて得られる(最大 $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$ 個)。

(1) $x_3=0$ のとき、$x_1+x_2=6$、$x_1+2x_2=10$ より $x_2=4$、$x_1=2$。$(2,4,0)$ は $x_i\ge 0$ を満たすので実行可能。$z=2\cdot 2+3\cdot 4+0=16$。

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

(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_1+x_2+x_3=6$ と $x_1+2x_2+3x_3=10$ の交線上の線分で、有界である。したがって目的関数の最大値は実行可能基底解のどれかで達成される。実行可能基底解のうち $z$ が最大なのは $(2,4,0)$ で、$z=16$。

検算:$(2,4,0)$ を代入すると、$2+4+0=6$、$2+8+0=10$ で制約を満たす。線分上の方向ベクトル $(2,-4,2)$ に沿った $z$ の変化は $4-12+2=-6<0$ で、$(2,4,0)$ から $(4,0,2)$ へ進むと $z$ が減ることとも一致する。

最適解は $(x_1,x_2,x_3)=(2,4,0)$(最大値 16)。