角の点を調べれば答えが出る
線形計画法とは、直線の式で書ける制約条件の中で、目的関数をいちばん大きく、または小さくする決め方を探す方法です。変数が2つなら、図形の「角の点」だけを調べれば、最適な答えが見つかります。
無数にある計画を、数個の点に絞れます。
このレッスンのゴール
メモ
変数が2つの問題を、実行可能領域の頂点を調べて解くことができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 線形 | 式が、変数に数をかけて足しただけであること | 200x + 300y |
| 境界線 | 制約の式の「≤」を「=」にした直線 | |
| 実行可能領域 | 全部の制約を守る点の集まり | |
| 頂点 | 実行可能領域の角の点 | |
| 最適解 | 目的関数がいちばんよい点 |
学生が入力するセルは、このプレビューでは空白です。
制約の境目は直線になる
小麦粉の制約「x + 2y ≤ 8」の境目は、「x + 2y = 8」という直線です。これが境界線です。
直線は、2つの点がわかれば引けます。y = 0 のときの x と、x = 0 のときの y を調べると、軸との交点が出ます。
2本の境界線が軸と交わる点
| 境界線 | y = 0 のとき | x = 0 のとき |
|---|---|---|
| 小麦粉 x + 2y = 8 | x = 8 | y = 4 |
| オーブン 30x + 20y = 180 | x = 6 | y = 9 |
学生が入力するセルは、このプレビューでは空白です。
実行可能領域は、角のある図形
全部の制約を守る点の集まりが、実行可能領域です。線形の制約なら、この領域は直線で囲まれた図形になります。
パン屋の領域は、4つの角を持つ図形です。この角の点を頂点と呼びます。頂点は、(0, 0)、(6, 0)、(5, 1.5)、(0, 4) の4つです。
4つの頂点と、その利益
| 頂点（x, y） | 何が起きているか | 利益 |
|---|---|---|
| (0, 0) | 何も作らない | 0円 |
| (6, 0) | 食パンだけ。オーブンを使い切る | 1200円 |
| (0, 4) | ロールパンだけ。小麦粉を使い切る | 1200円 |
| (5, 1.5) | 小麦粉もオーブンも使い切る | 1450円 |
学生が入力するセルは、このプレビューでは空白です。
3つの頂点の利益を計算する
docker exec jupyter python3 -c "print(200 * 5 + 300 * 1.5, 200 * 6, 300 * 4)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
最適な点は、頂点にある
利益が1200円になる点を全部つなぐと、直線になります。利益を1450円に上げると、この直線は平らなまま右上へずれます。
直線が領域から出る直前に触れる点が、最適解です。それは、領域の角になります。
利益の直線を動かす
| 利益 | 直線が領域に触れる点 | 言えること |
|---|---|---|
| 1200円 | (6, 0) と (0, 4) とその間の点 | まだ上げられる |
| 1450円 | (5, 1.5) だけ | ここが限界 |
| 1500円 | 触れる点がない | 実行可能な計画はない |
学生が入力するセルは、このプレビューでは空白です。
2本の境界線の交点を求める
パン屋の頂点 (5, 1.5) は、小麦粉とオーブンの境界線の交点です。オーブンの式を10で割ると、「3x + 2y = 18」です。
小麦粉の式「x + 2y = 8」を引くと、「2x = 10」で x = 5 です。y は、(8 − 5) ÷ 2 で 1.5 です。
交点が両方の式に合うか確かめる
docker exec jupyter python3 -c "x = 5; y = 1.5; print(x + 2 * y, 30 * x + 20 * y)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
頂点ごとの利益を比べる
# 4つの頂点で、利益を比べます。
corners = [[0, 0], [6, 0], [5, 1.5], [0, 4]]
profit_x = 200
profit_y = 300
for c in corners:
print(c, profit_x * c[0] + profit_y * c[1])
# profit_x を 500 に変えると、いちばん大きい頂点が変わります。
よくある間違い
注意
多くの人は、最適な点は領域の真ん中にあると考えます。目的関数が直線の式なら、利益は右上へ行くほど増えるので、真ん中より端がよくなります。最適解は、いつでも頂点の上にあります。
さらに挑戦: 利益が変わると
上のコードの食パンの利益を、200円から500円に変えて実行してください。いちばん大きい頂点は、(5, 1.5) から (6, 0) に移ります。
利益の比が変わると、最適な頂点が別の角に移ります。移り変わる境目の値を、数を変えて探してください。