linprogで線形計画を解く
SciPy の linprog は、線形計画法の問題を Python で解く関数です。係数を3つのリストで渡すと、最適な作り方と、その利益が返ってきます。
手で頂点を調べるより速く、変数が増えても同じ書き方で解けます。
このレッスンのゴール
メモ
SciPy の linprog で線形計画の問題を解き、結果を読むことができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| linprog | SciPy の、線形計画を解く関数 | |
| 係数 | 式の x や y にかかる数 | 200x の 200 |
| 最小化 | 目的関数を小さくする向きで解くこと | |
| 実行不可能 | 制約を全部守る点が1つもないこと | |
| 有界でない | 目的がいくらでもよくなること |
学生が入力するセルは、このプレビューでは空白です。
linprogは最小化しかできない
linprog は、目的関数を小さくする向きでしか解きません。利益を大きくしたいときは、係数に − を付けて、「−200x − 300y」を小さくします。
答えの fun は、− が付いた値です。もとの利益に戻すには、符号を逆にします。
linprogに渡す3つのリスト
| 名前 | 中身 | パン屋の値 |
|---|---|---|
| c | 目的関数の係数（− を付ける） | [-200, -300] |
| A_ub | 制約の左辺の係数 | [[1, 2], [30, 20]] |
| b_ub | 制約の上限 | [8, 180] |
学生が入力するセルは、このプレビューでは空白です。
パン屋の問題を解く
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-200, -300], A_ub=[[1, 2], [30, 20]], b_ub=[8, 180]); print(round(-r.fun, 2), r.x)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
結果の status で、解けたかがわかる
r.success は、解けたときだけ True です。r.status は、理由を数字で教えます。0は解けた、2は実行不可能、3は有界でないという意味です。
制約が矛盾すると2になり、制約が足りなくて目的がいくらでもよくなると3になります。
status の意味
| status | 意味 | 例 |
|---|---|---|
| 0 | 最適解が見つかった | パン屋の問題 |
| 2 | 実行不可能 | 「食パン7本以上」を加えた問題 |
| 3 | 有界でない | x − y ≤ 1 だけを守る問題 |
学生が入力するセルは、このプレビューでは空白です。
実行不可能な問題を解く
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-200, -300], A_ub=[[1, 2], [30, 20], [-1, 0]], b_ub=[8, 180, -7]); print(r.status, r.success)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
有界でない問題を解く
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-1, -1], A_ub=[[1, -1]], b_ub=[1]); print(r.status, r.success)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
多くの人は、利益を大きくしたいのに、係数をそのまま渡します。linprog は小さくする向きなので、損をする計画を選びます。大きくしたい目的は、係数に − を付けて渡し、答えの符号を戻します。
頂点は、全部の組の交点から探せる
linprog の中でも、頂点を探す考え方は同じです。境界線は4本あります（x = 0、y = 0、小麦粉、オーブン）。
2本ずつ選ぶと6組あり、それぞれ1点で交わります。そのうち、全部の制約を守る点だけが、実行可能領域の頂点です。
6組の交点と、実行可能か
| 選んだ2本 | 交点（x, y） | 実行可能か |
|---|---|---|
| x = 0 と y = 0 | (0, 0) | 実行可能 |
| x = 0 と 小麦粉 | (0, 4) | 実行可能 |
| x = 0 と オーブン | (0, 9) | 小麦粉が18kgで不可 |
| y = 0 と 小麦粉 | (8, 0) | オーブンが240分で不可 |
| y = 0 と オーブン | (6, 0) | 実行可能 |
| 小麦粉 と オーブン | (5, 1.5) | 実行可能 |
学生が入力するセルは、このプレビューでは空白です。
2本の直線の交点を求める
# 2本の直線 a1*x + b1*y = c1 と a2*x + b2*y = c2 の交点を求めます。
a1 = 1
b1 = 2
c1 = 8
a2 = 30
b2 = 20
c2 = 180
det = a1 * b2 - a2 * b1
if det == 0:
print("平行なので、交点はありません。")
else:
x = (c1 * b2 - c2 * b1) / det
y = (a1 * c2 - a2 * c1) / det
print("交点:", x, y)
# c2 を 120 に変えて、交点がどう動くか確かめてください。
さらに挑戦: 結果を頂点と比べる
linprog の答え (5, 1.5) と、手で求めた4つの頂点を比べてください。linprog の答えは、4つのうちのどれと同じですか。
次に、小麦粉の上限を8kgから6kgに変えて、もう一度解きます。答えが別の頂点に移るかを確かめましょう。