加藤家と佐藤家はともにワイン農家です。生産能力に違いがあります。
どのように生産すれば、全体として最大の利益をあげられるでしょうか。
まず何を決めるのかをはっきりさせます。決めるのは生産量なので、それを変数にします。
変数 x ＝ 赤ワインの生産量（樽）、 y ＝ 白ワインの生産量（樽）
制約
9x + 5y ≦ 50 ← 葡萄（トン）
x + 5y ≦ 10 ← 人手（人）
x ≧ 0, y ≧ 0 ← 生産量は負にならない
目的関数
5x + 10y → 最大
翻訳のこつ。 制約は「使う量 ≦ 持っている量」の形で書きます。 赤 1 樽で葡萄 9 トン、白 1 樽で 5 トンなので、使う量は 9x + 5y。 これが手持ちの 50 トン以下、というわけです。 人手も同じ要領で x + 5y ≦ 10。
目的関数 5x + 10y ＝ C を y について解くと
y ＝ −(1/2)x + C/10
これは傾き −1/2 の直線で、C が大きいほど上（右上）へ平行移動します。 この直線を、実行可能領域からはみ出さない範囲でできるだけ上へ動かす。 すると領域の角（頂点）で止まります。
線形計画法の基本定理。
実行可能領域が空でなく有界なら、最適解は必ず頂点のどれかにある。
だから頂点をすべて調べれば答えが出ます。無限にある点を調べる必要はありません。
| 頂点 | どの制約の交点か | 5x + 10y |
|---|---|---|
| (0, 0) | 原点 | 0 |
| (50/9, 0) ≒ (5.56, 0) | 葡萄の制約と x 軸 | 27.8 |
| (5, 1) | 葡萄の制約と人手の制約 | 35 |
| (0, 2) | 人手の制約と y 軸 | 20 |
最大は (5, 1) の 35 万円。 赤ワインを 5 樽、白ワインを 1 樽つくるのが最適です。
2 本の制約式を連立させます。
9x + 5y ＝ 50 …①
x + 5y ＝ 10 …②
① − ②： 8x ＝ 40 ⟹ x ＝ 5
②に代入： 5 + 5y ＝ 10 ⟹ y ＝ 1
変数が 2 つなら図で解けますが、3 つ以上になると図は描けません。 実務では表計算ソフトのソルバーを使います。
| ソルバーに指定するもの | この問題では |
|---|---|
| 目的セル（最大化） | 5x + 10y を計算するセル |
| 変数セル | x と y のセル |
| 制約条件 | 9x+5y ≦ 50、x+5y ≦ 10、x ≧ 0、y ≧ 0 |
| 解法 | シンプレックス LP |
内部ではシンプレックス法という手順が動いています。 これは「頂点から隣の頂点へ、目的関数が良くなる方向に渡り歩く」方法で、 図解法でやっていることを、変数がいくつあってもできるようにしたものです。