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

実行可能領域は、3 本の直線 $x+y=6$、$x+3y=10$、$2x+y=8$ の「上側」と第 1 象限の共通部分で、右上に広がる非有界な凸多角形領域である。目的関数の係数 $3,2$ はともに正で $x,y\ge 0$ なので $z\ge 0$ であり、最小値は存在し、実行可能領域の頂点のどれかでとられる。

頂点を求める。
- $x=0$ 上: 制約は $y\ge 6$、$y\ge \frac{10}{3}$、$y\ge 8$ なので $y\ge 8$。頂点 $(0,8)$。
- $2x+y=8$ と $x+y=6$ の交点: 辺々引いて $x=2$、$y=4$。$x+3y=14\ge 10$ を満たすので頂点 $(2,4)$。
- $x+y=6$ と $x+3y=10$ の交点: 辺々引いて $2y=4$ より $y=2$、$x=4$。$2x+y=10\ge 8$ を満たすので頂点 $(4,2)$。
- $y=0$ 上: 制約は $x\ge 6$、$x\ge 10$、$x\ge 4$ なので $x\ge 10$。頂点 $(10,0)$。

各頂点での目的関数の値は
$$z(0,8)=16,z(2,4)=6+8=14,z(4,2)=12+4=16,z(10,0)=30$$
よって最小値は $14$ で、それをとるのは $(2,4)$ だけである（目的関数の勾配 $(3,2)$ はどの制約の法線 $(1,1),(1,3),(2,1)$ とも平行でないので、辺全体で最小になることはない）。

したがって最適解は $(x,y)=(2,4)$。

実行可能領域は下に凸な非有界領域で、頂点を求める。
- $x+y=6$ と $x+3y=10$: $(4,2)$。$2x+y=10\ge 8$ を満たす。$z=16$。
- $x+y=6$ と $2x+y=8$: $(2,4)$。$x+3y=14\ge 10$ を満たす。$z=14$。
- $x+3y=10$ と $2x+y=8$: $(2.8,2.4)$。$x+y=5.2<6$ で実行不可能。
- $y$ 軸上: $x=0$ なら $y\ge 8$ で頂点は $(0,8)$、$z=16$。
- $x$ 軸上: $y=0$ なら $x\ge 10$ で頂点は $(10,0)$、$z=30$。
実行可能領域は頂点 $(0,8),(2,4),(4,2),(10,0)$ をこの順に結ぶ折れ線の上側（非有界）で、$3x+2y$ は $x,y$ について増加（係数が正）なので領域は下向きに非有界でも $z$ は下に有界であり、最小値は頂点で達成される。$z$ の値は $16,14,16,30$ だから最小は $(2,4)$ で $z=14$。
検算: 辺 $(0,8)\to (2,4)$ 上では $z=16-x$ で減少、辺 $(2,4)\to (4,2)$ 上では $z=12+x$ で増加。$z$ の勾配 $(3,2)$ はどの制約の法線 $(1,1),(2,1)$ とも平行でないので最適解は唯一。双対確認: $3={\lambda }_1+2{\lambda }_3$、$2={\lambda }_1+{\lambda }_3$ より ${\lambda }_3=1,{\lambda }_1=1\ge 0$ で、双対目的値 $6\cdot 1+8\cdot 1=14$ と一致。