線形計画法(x+yの最大)

方針

解答

⓪ 発想 — どう考え始めるか。 $4$ つの不等式が表す領域(多角形)をまず図示する。$x\ge 0,y\ge 0$ で第$1$象限、$x+2y\le 8$ と $3x+y\le 9$ で上と右を切る。

$x+y=k$ とおくと傾き $-1$ の直線。$k$ を大きくすると右上へ平行移動する。領域と共有点をもつ最大の $k$ を探す。

$1$ 次式の最大は、ふつう領域の頂点で起こる。頂点(境界線の交点)の座標を求め、$x+y$ を比べる。$x+2y=8$ と $3x+y=9$ の交点 $(2,3)$ で最大 $5$。

① 領域の頂点を求める。 境界は $x=0,y=0,x+2y=8,3x+y=9$。頂点は境界の交点:

• $(0,0)$、$(3,0)$($3x+y=9$ と $y=0$)、$(0,4)$($x+2y=8$ と $x=0$)。
• $x+2y=8$ と $3x+y=9$ の交点:$y=9-3x$ を代入し $x+2(9-3x)=8$、$-5x=-10$、$x=2,y=3$。よって $(2,3)$。

② 頂点で $x+y$ を比べる。

• $(0,0)\to 0$、$(3,0)\to 3$、$(0,4)\to 4$、$(2,3)\to 5$。

最大は $(2,3)$ で $x+y=5$。

まとめ:線形計画法は「領域を図示 → 頂点で $1$ 次式を比べる」。$x+y=k$ の直線を右上へ動かし、最後に接する頂点 $(2,3)$ が最大 $5$ を与える。$2$ つの傾いた境界の交点が最大点になるのが典型。

発展 — 一歩先へ。 線形計画法「$1$ 次式を$1$次不等式の領域で最大化」は、最適解が必ず頂点(または辺)でとる。目的関数の等高線を平行移動し、領域から離れる直前の頂点が答え。生産計画・栄養問題など応用が広く、変数が増えるとシンプレックス法という系統的な解法になる。

別解

別解 — 目的関数の等高線が「最後に触れる頂点」を追う(視覚で捉えるルート)。 $x+y=k$ の直線(傾き $-1$)を、$k$ を小さい値から大きくしながら領域の上を滑らせる。領域から離れる直前に触れている頂点が最大を与える。

領域の頂点は $(0,0),(3,0),(0,4)$、そして $x+2y=8$ と $3x+y=9$ の交点 $(2,3)$。

各頂点で $x+y$: $(0,0)\to 0$、$(3,0)\to 3$、$(0,4)\to 4$、$(2,3)\to 5$。最大は $(2,3)$ の $5$。

直線 $x+y=k$ の傾き $-1$ は、境界 $x+2y=8$(傾き $-\frac{1}{2}$)と $3x+y=9$(傾き $-3$)の“中間”の傾き。だから最大はこの $2$ 辺が出会う頂点 $(2,3)$ で起こる、と傾きの比較からも予測できる。頂点を全部調べる(本解)のと同じ $5$ だが、「目的関数の傾きが $2$ 辺の傾きの間にある頂点が最適」と読むと、どの頂点かを先読みできる。線形計画法の核心だ。