領域における最大・最小問題（線形計画法）

二変数の場合の線形計画法は入試で頻出です。まずは具体例。

• ベクトルの内積を使えば「$ax+by$ を最大化したい $\iff (a,b)$ の方向に進みたい」とみなせます。例えば上記の例題では「領域内でベクトル $(4,5)$ の方向に進みたい」という問題になります。このように考えても答えが $(2,1)$ であることが分かります。→正射影ベクトルの公式の証明と使い方
• 当然ですが，目的関数の係数によっては関数の最大値を達成する点が変わってきます。そのため上記の例題では傾きの議論（※の部分）が必要になります。
• 例えば今回は赤い点が答えでしたが，関数が異なる場合，他の点（紫の点）で最大となることもあります。しかし「領域の端っこ（頂点）」で最大値，最小値を取るというのは（最適値が有界でないなどの例外を除いて）成り立ちます。

• 領域を表す不等式が一次式であり，最大化（最小化）したい関数も一次関数なので最も扱いやすい問題です。このように不等式も目的関数も一次式であるような問題を線形計画法と呼びます。

• 関数 $f(x,y)$ を最大化するのと$-f(x,y)$ を最小化するのは同じなので最大化問題と最小化問題は本質的に同じです。

• 上記の例題の考え方（直線を動かして切片を最大化する）は最大化したい関数 $f(x,y)$ が一次関数であれば，領域が曲がっていても使えます。例えば領域が「円の内部」とか「楕円の内部」などの問題も出題されます。

ここからは完全に余談です。

入試で出題されるのは二変数の線形計画法ですが， 一般に $n$ 変数の線形計画問題も考えられます。これは工学的にも非常に重要な問題です。工学的に重要だからこそ大学入試で出題されやすいのかもしれません。

二変数の線形計画法の場合 $xy$ 平面でものごとを考えることができましたが，$n$ 変数の場合 $n$ 次元空間で考える必要があります。 $n\geqq 4$ の場合はもはや不等式で表される領域を図示することができません。そもそも4次元空間ってなんだよって話ですよね。

しかし，現代のテクノロジーを使えば $n$ 変数の線形計画法も高速に解くことができます。例えば，二変数の場合と同様「最大値（最小値）を取るのは領域の端っこ」であることを利用した単体法という解法があります。他にも内点法や楕円体法などの解法もあり，世の中の多くの問題が線形計画法の形で定式化され，実際に解かれています。

Tag:数学2の教科書に載っている公式の解説一覧

Tag:数学的モデリングまとめ（線形計画法）