No.453

製品Aを作る量を $a$, 製品Bを作る量を $b$ とすると, 問題は

$$\frac{3}{4}a + \frac{2}{7}b \leq C \\ \frac{1}{4}a + \frac{5}{7}b \leq D \\ a \geq 0, b \geq 0$$

という制約下で

$$S = 1000a+2000b$$

を最大化する問題である.

線形計画法の最も単純な問題であり, 不等式を $ab$ 平面上にプロットすれば計算できる.

$$\frac{3}{4}a + \frac{2}{7}b = C \\ \frac{1}{4}a + \frac{5}{7}b = D$$

の交点の位置 $(x, y)$ で場合分けする.

交点が第1象限にある場合:

$1000a + 2000b = S$ が交点を通る場合が最も稼げる. よって, $S = 1000x + 2000y$ である.

交点が第2象限にある場合:

製品Aしか作らなくていい. よって, $S = 4D \times 1000$ である.

交点が第4象限にある場合:

製品Bしか作らなくていい. よって, $S = (7/2)C \times 2000$ である.