数学2 線形計画法 問題 1 解説

方針・初手

線形計画法の問題である。与えられた連立不等式が表す領域を図示し、$x+2y=k$ とおいて、$k$ が最大となる点を見つける。直線 $x+2y=k$ の傾きと、領域の境界線の傾きを比較することで最大値をとる頂点を特定できる。

解法1

与えられた不等式

$$x+3y \leqq 15 \quad \cdots \text{①}$$

$$2x+y \leqq 10 \quad \cdots \text{②}$$

$$x \geqq 0 \quad \cdots \text{③}$$

$$y \geqq 0 \quad \cdots \text{④}$$

をすべて満たす $xy$ 平面上の領域を $D$ とする。

直線 $x+3y=15$ と $2x+y=10$ の交点を求めるため、連立方程式

$$\begin{cases} x+3y = 15 \\ 2x+y = 10 \end{cases}$$

を解くと、$x=3, y=4$ となる。

したがって、領域 $D$ は4点 $(0, 0)$, $(5, 0)$, $(3, 4)$, $(0, 5)$ を頂点とする四角形の周および内部である。

ここで、$x+2y=k$ とおくと、これは

$$y = -\frac{1}{2}x + \frac{k}{2}$$

と変形でき、傾き $-\frac{1}{2}$、$y$ 切片 $\frac{k}{2}$ の直線を表す。

領域 $D$ の境界となる直線の傾きについて、①の境界線 $x+3y=15$ の傾きは $-\frac{1}{3}$、②の境界線 $2x+y=10$ の傾きは $-2$ である。

直線 $x+2y=k$ の傾き $-\frac{1}{2}$ は、$-2$ と $-\frac{1}{3}$ の間にある。すなわち

$$-2 < -\frac{1}{2} < -\frac{1}{3}$$

であるから、この直線が領域 $D$ と共有点をもつとき、$y$ 切片 $\frac{k}{2}$ が最大となるのは、直線が点 $(3, 4)$ を通るときである。

このとき、$k$ の値は

$$k = 3 + 2 \cdot 4 = 11$$

となり、これが最大値である。

解法2

領域 $D$ は、4点 $(0, 0)$, $(5, 0)$, $(3, 4)$, $(0, 5)$ を頂点とする凸多角形の周および内部である。

1次式 $x+2y$ の最大値および最小値は、このような有界な閉領域の場合、必ず境界上の頂点のいずれかでとる。

各頂点における $x+2y$ の値を計算すると、以下のようになる。

• $(x, y) = (0, 0)$ のとき、$0 + 2 \cdot 0 = 0$
• $(x, y) = (5, 0)$ のとき、$5 + 2 \cdot 0 = 5$
• $(x, y) = (3, 4)$ のとき、$3 + 2 \cdot 4 = 11$
• $(x, y) = (0, 5)$ のとき、$0 + 2 \cdot 5 = 10$

これらの値のうち、最大のものは $11$ である。

したがって、$x=3, y=4$ のとき最大値 $11$ をとる。

解説

線形計画法の典型問題である。領域を図示し、目的関数を $k$ とおいて直線を図形的に動かす解法（解法1）が基本である。直線の傾きと境界線の傾きの大小関係を比較することで、視覚的にどの頂点で最大（最小）となるか正確に判断できる。

また、凸多角形領域における1次式の最大・最小は頂点でとるという性質を利用する解法（解法2）も、直線の傾きの議論を省略できるため、手早く答えを出すのに有効である。

答え

11