領域の中の最大・最小は頂点で決まる！直線を平行移動して探す

領域の中で $x+3y$ のような式の最大値を探すとき、その式を $k$ と置くところから始めます。

$$x+3y=k$$

$k$ を決めるごとに $1$ 本の直線が決まります。$k$ を変えると、傾きを保ったまま直線が平行に動く。

求めたいのは、この直線が領域と共有点をもつ範囲での $k$ の端です。直線を動かして、領域から離れる寸前で止めた位置が答えになります。

橙の直線が平行に動いています。領域から完全に離れる直前が、$k$ がいちばん大きくなる位置。

その位置で直線が触れているのは頂点 $(0,4)$ です。ここで $k=0+12=12$ になります。

なぜ頂点で決まるのか

領域の内部の点をとったとします。その点を通る直線は、まだどちらへも動かせる。まわりに領域が残っているので、$k$ をもう少し増やせます。

辺の上の点でも同じです。直線の傾きが辺と違うなら、辺に沿って端へ寄せることで $k$ を増やせる。

動かせなくなるのは、まわりに領域が残っていない場所、つまり頂点です。だから最大と最小は頂点で起こります。

目的の式が一次で、領域が多角形であれば、端の値は必ず頂点でとります。この一文が、この種の問題を解くときの土台になります。

例：四角形の領域で最大と最小

連立不等式 $x\ge 0$、$y\ge 0$、$x+y\le 4$、$2x+y\le 6$ の表す領域で、$x+3y$ の最大値と最小値を求めます。

まず領域の頂点を出します。境界どうしの交点を求める作業です。

$3$ 番目の交点は連立して出します。$2x+y=6$ から $x+y=4$ を引くと $x=2$、代入して $y=2$ です。

出た交点が本当に領域の頂点かを確かめます。$(3,0)$ なら $x+y=3\le 4$ で他の条件も満たしている。境界どうしの交点でも、別の条件から外れていれば頂点になりません。

$4$ つの頂点で $x+3y$ を計算します。

最大値は $12$ で $(0,4)$ のとき、最小値は $0$ で $(0,0)$ のときです。

全部の頂点で計算する

直線を動かす図を描かなくても、頂点をすべて洗い出して代入すれば答えが出ます。多角形なら頂点は有限個なので、必ず終わる。

図から読む方法は速いのですが、傾きの比較を間違えると別の頂点を選んでしまいます。頂点が $4$ つ $5$ つなら、計算するほうが確実です。

図を描く手間は省けません。どの境界とどの境界が交わって頂点になるかは、図がないと見えないためです。

傾きが境界と一致すると辺全体が答えになる

同じ領域で、今度は $x+y$ の最大値を求めます。頂点で計算します。

$(0,0)$ で $0$、$(3,0)$ で $3$、$(2,2)$ で $4$、$(0,4)$ で $4$。最大値 $4$ が $2$ つの頂点で同時に起きました。

これは目的の式 $x+y=k$ の傾きが、境界 $x+y=4$ と同じだからです。直線を動かすと、辺にぴったり重なって止まる。

太い橙の線が最大値をとる場所です。$2$ つの頂点だけでなく、そのあいだの辺の上のどの点でも $x+y=4$ になります。

答えを書くときは「最大値 $4$、そのとき $x+y=4$ かつ $0\le x\le 2$」のように、とる場所まで示します。頂点を $1$ つだけ挙げると、答えが足りません。

頂点で計算する方法なら、この場合も見落としません。同じ最大値が $2$ 頂点で出たら、そのあいだの辺全体が答えだと分かります。

領域が閉じていないとき

領域が無限に広がっていると、最大値や最小値が存在しないことがあります。

$x\ge 0$、$y\ge 0$、$x+y\ge 2$ の領域で $x+2y$ を考えます。この領域は右上へ無限に広がっている。

$x$ や $y$ をいくらでも大きくとれるので、$x+2y$ に上限はありません。最大値は存在しない。

最小値のほうは決まります。頂点は $(2,0)$ と $(0,2)$ で、それぞれ $2$ と $4$。最小値は $2$ で $(2,0)$ のときです。

領域が閉じていない問題では、動かす向きに領域の端があるかを先に見ます。端がなければ、その側の答えは存在しません。

目的の式の傾きで動かす向きが変わる

$x+3y=k$ では、$k$ を大きくすると直線は上へ動きました。目的の式が変われば、動く向きも変わります。

$-x+y=k$ なら、$k$ を大きくすると直線は左上へ。$x-2y=k$ なら右下へ寄せることになります。

どちらの向きで $k$ が増えるかは、$k$ を $2$ つ選んで直線を $2$ 本描けば分かります。$k=0$ と $k=3$ の位置を比べる、といった確かめ方です。

図から読むときは、この向きをとり違えると最大と最小が入れ替わります。頂点で計算する方法には、この危険がありません。

目的の式が一次でない場合

$x^2+y^2$ のような式では、頂点で決まるとは限りません。この式は原点からの距離の $2$ 乗なので、等しい値をとる点が同心円になります。

$x\ge 0$、$y\ge 0$、$x+y\ge 2$ の領域で $x^2+y^2$ の最小値を求めます。

原点を中心とする円を大きくしていき、領域と最初に触れる位置を探します。触れるのは、原点から直線 $x+y=2$ へ下ろした垂線の足。

触れる点は $(1,1)$ で、頂点ではありません。辺の途中です。

このとき $x^2+y^2=2$ が最小値。頂点 $(2,0)$ と $(0,2)$ ではどちらも $4$ で、$(1,1)$ のほうが小さくなっています。

頂点で決まるのは目的の式が一次のときだけ。二次の式が出てきたら、等高線がどんな図形になるかを描いて、領域と触れる場所を探します。

例：文章題として出る形

製品 A と B を作ります。A を $1$ 個作るのに材料 P が $2$ キログラム、材料 Q が $1$ キログラム。B を $1$ 個作るのに P が $1$ キログラム、Q が $2$ キログラム。

P は $8$ キログラム、Q は $7$ キログラムまで使えます。A の利益は $1$ 個 $3$ 万円、B は $4$ 万円。利益を最大にする作り方を求めます。

A を $x$ 個、B を $y$ 個として、条件を不等式にします。

$$2x+y\le 8,x+2y\le 7,x\ge 0,y\ge 0$$

目的は $3x+4y$ の最大化です。頂点を求めます。

$2x+y=8$ と $x+2y=7$ を連立します。$1$ 本目を $2$ 倍して $2$ 本目を引くと $3x=9$、$x=3$、$y=2$ です。

最大は $(3,2)$ で $17$ 万円。A を $3$ 個、B を $2$ 個作る計画です。

個数は整数でなければならないので、答えが整数の頂点で出たのは幸運でした。頂点が整数にならない問題では、その近くの整数の点をいくつか調べます。

答えの書き方

最大値や最小値だけでなく、それをとる $x$ と $y$ も書きます。「$x=0$、$y=4$ のとき最大値 $12$」の形です。

辺全体でとる場合は、その辺を範囲つきで示します。頂点を $1$ つだけ書くと、他の場所を落としたことになる。

存在しない場合は「最大値はない」と書きます。空欄にすると、計算していないのか存在しないのかが伝わりません。

よくある誤り

参考文献