線形計画法とは

線形計画法とは、一次式(※1)で表される制約条件のもとで、
利益が最大になる条件や最大利益などを求める手法のこと。

一言でいうと、
「いくつかの限られた条件（制約）の中で、一番いい結果（最大の利益や最小のコスト）を出すための組み合わせを見つける方法」。

例：ハンバーガーショップの利益最大化

私がハンバーガーショップの店長だとします。

決定変数（私が決められること）

• ハンバーガーを $x$ 個作る
• チーズバーガーを $y$ 個作る

目的関数（最大化したい目標）

ハンバーガーは1個売れると300円の利益、チーズバーガーは400円の利益が出るとします。
総利益 $Z$ は、「一次式」を使ってこう表せます。

$$Z = 300x + 400y$$

これが「最大利益を求める式」です。

制約条件（限られたルール）

しかし、材料には限りがあります。これも一次式（不等式）で表します。

• ひき肉の限界： $2x + 3y \leqq 120$
• パンズの限界： $x + y \leqq 50$
• 作る数はマイナスにならない： $x \geqq 0$, $y \geqq 0$

このルールをすべて守りながら、「総利益 $Z$ が一番大きくなる $x$ と $y$ の組み合わせはどれか？」を計算するのが線形計画法です。

解いてみる

線形計画法には便利な性質があります。最大値は、制約条件を満たす範囲（実行可能領域）の内側ではなく、必ず領域の「頂点（角）」のどこかで実現するのです。だから範囲の中をしらみつぶしに探す必要はなく、頂点だけを比べれば答えが見つかります。

この例での頂点は次の4つです。

頂点 (x, y)	Z = 300x + 400y
(0, 0)	0円
(50, 0)	15,000円
(30, 20)	17,000円（最大）
(0, 40)	16,000円

答え： ハンバーガーを30個、チーズバーガーを20個作れば、利益は17,000円で最大になる。

(30, 20) はどこから出てくるのか

(0, 0)・(50, 0)・(0, 40) の3点は、どれか一方の制約を軸（x = 0 または y = 0）に当てはめるだけで出てくる単純な点です。しかし (30, 20) だけは性質が違い、「パンズもひき肉も両方ちょうど使い切る」組み合わせを表しています。これは、2本の制約式をどちらも等号にして連立方程式として解くことで求められます。

$$x + y = 50 \quad \text{…①（パンズを使い切る）}$$
$$2x + 3y = 120 \quad \text{…②（ひき肉を使い切る）}$$

①を $x$ について解くと $x = 50 - y$。これを②に代入します。

$$2(50 - y) + 3y = 120$$
$$100 - 2y + 3y = 120$$
$$100 + y = 120$$
$$y = 20$$

$y = 20$ を①に戻すと、$x = 50 - 20 = 30$。よって $(x, y) = (30, 20)$ と求まります。検算として両方の式に代入すると、$30 + 20 = 50$、$2 \times 30 + 3 \times 20 = 120$ とぴったり成り立ちます。

まとめ

線形計画法は、「制約（限られた条件）」を一次式で表し、その中で目的関数（利益やコストなど）を最大・最小にする組み合わせを探す手法です。

今回の例では、ひき肉やパンズという限られた材料の中で、利益が最大になるハンバーガーとチーズバーガーの個数の組み合わせを求めました。答えは「ハンバーガー30個・チーズバーガー20個」で、そのとき利益は17,000円になり、これが理論上の最大値です。

線形計画法は、生産計画・在庫管理・配送ルートの最適化など、
「限られたリソースをどう配分すれば一番得か」を考える場面で幅広く使われているそうです。

※1

一次式は「グラフを描くと直線になるような式」です。
例えば
Y=aX+b
みたいなのが一次式です。
横軸にXを、縦軸にYをとってグラフを描くと、斜めの直線になりますよね。
https://wa3.i-3-i.info/word111359.html

一次式
aや-2bのように
文字が1つだけの項を1次の項といい、
1次の項と数の項の和で表される式を 1次式といいます。

項
2x+3という式で、加法の記号「+」で結ばれた
2xや3を項といいます。また、2xという項で、数の部分2を係数といいます。
https://ic0.tv/class/mathematics/junior-high-school-freshman/002/ichijishikinokeisan/