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

実行可能領域は有界な凸多角形であり、線形の目的関数の最大値はその頂点のいずれかでとられる。そこで頂点を求める。

• $x=0,y=0$ の交点: $(0,0)$
• $x=0$ と $x+2y=14$: $(0,7)$（$3\cdot 0+7=7\le 18$, $0-7\le 4$ を満たす）
• $x+2y=14$ と $3x+y=18$: 第 2 式より $y=18-3x$。第 1 式に代入して $x+36-6x=14$ より $x=\frac{22}{5}$, $y=18-\frac{66}{5}=\frac{24}{5}$。$x-y=-\frac{2}{5}\le 4$ を満たす
• $3x+y=18$ と $x-y=4$: 辺々加えて $4x=22$ より $x=\frac{11}{2}$, $y=\frac{3}{2}$。$x+2y=\frac{17}{2}\le 14$ を満たす
• $x-y=4$ と $y=0$: $(4,0)$

なお $x+2y=14$ と $y=0$ の交点 $(14,0)$ や $3x+y=18$ と $y=0$ の交点 $(6,0)$ は $x-y\le 4$ を満たさないので頂点ではない。

各頂点で $z=5x+4y$ を計算すると
$$z(0,0)=0,z(0,7)=28,z\left(\frac{22}{5},\frac{24}{5}\right)=\frac{110}{5}+\frac{96}{5}=\frac{206}{5},$$
$$z\left(\frac{11}{2},\frac{3}{2}\right)=\frac{55}{2}+6=\frac{67}{2},z(4,0)=20$$

最大は $\frac{206}{5}$ で、$(x,y)=\left(\frac{22}{5},\frac{24}{5}\right)$ のときにとる。

（確認）$(5,4)=\frac{7}{5}(1,2)+\frac{6}{5}(3,1)$ と、この頂点で有効な 2 つの制約の係数ベクトルの非負結合で表せるので、この頂点は確かに最適解である。

よって最大値は $\frac{206}{5}$。

実行可能領域は凸多角形で、目的関数は線形なので、最大値は頂点で達成される。頂点を求める。
- $(0,0)$: $z=0$
- $y=0$ と $x-y=4$: $(4,0)$（$3x+y=12\le 18$, $x+2y=4\le 14$ を満たす）: $z=20$
- $x-y=4$ と $3x+y=18$: $4x=22$ より $(\frac{11}{2},\frac{3}{2})$（$x+2y=\frac{17}{2}\le 14$ を満たす）: $z=\frac{55}{2}+6=\frac{67}{2}=33.5$
- $3x+y=18$ と $x+2y=14$: $y=18-3x$ を代入して $x+36-6x=14$ より $x=\frac{22}{5}$, $y=\frac{24}{5}$（$x-y=-\frac{2}{5}\le 4$ を満たす）: $z=22+\frac{96}{5}=\frac{206}{5}=41.2$
- $x+2y=14$ と $x=0$: $(0,7)$（$3x+y=7\le 18$, $x-y=-7\le 4$ を満たす）: $z=28$

最大は $\left(\frac{22}{5},\frac{24}{5}\right)$ での $z=\frac{206}{5}$。

検算: 目的関数の等高線の傾き $-5/4$ は、$3x+y=18$ の傾き $-3$ と $x+2y=14$ の傾き $-1/2$ の間にあるので、その交点が最適である。双対確認として $5=3\lambda +\mu$, $4=\lambda +2\mu$ を解くと $\lambda =\frac{6}{5},\mu =\frac{7}{5}\ge 0$、双対目的 $18\cdot \frac{6}{5}+14\cdot \frac{7}{5}=\frac{108+98}{5}=\frac{206}{5}$ で一致する。