整数にすると、問題が急に難しくなる
整数計画法とは、変数が整数（1個、2個、…）でなければならない最適化の問題です。本数や人数は小数にできないので、現実の問題の多くは整数計画です。
線形計画より解くのが難しく、答えを四捨五入しても、最適にならないことがあります。
このレッスンのゴール
メモ
整数を求める問題が、なぜ線形計画より難しいかを、例を挙げて言うことができる。
キーワード
| ことば | いみ |
|---|---|
| 整数計画法 | 変数が整数でなければならない最適化 |
| LP緩和 | 整数の条件を外して、線形計画として解くこと |
| ナップサック問題 | 重さの上限の中で、価値の合計を最大にする荷物の選び方 |
| 動的計画法 | 小さな問題の答えを表にためて、大きな問題を解く方法 |
| 組合せ爆発 | 選び方の数が、急に増えること |
学生が入力するセルは、このプレビューでは空白です。
答えを丸めても最適にならない
パン屋の線形計画の答えは、食パン5本、ロールパン1.5袋で、利益は1450円でした。袋は半分に分けられないので、整数に直します。
丸めた計画は、実行可能でないか、最適でないことがあります。表で確かめます。
丸めた計画の結果
| 計画（食パン、ロールパン） | 実行可能か | 利益 |
|---|---|---|
| (5, 2) 1.5を切り上げる | 小麦粉9kgで不可 | なし |
| (5, 1) 1.5を切り捨てる | 実行可能 | 1300円 |
| (4, 2) 食パンを減らす | 実行可能 | 1400円 |
学生が入力するセルは、このプレビューでは空白です。
整数の条件を付けて解く
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-200, -300], A_ub=[[1, 2], [30, 20]], b_ub=[8, 180], integrality=[1, 1]); print(round(-r.fun, 2), r.x)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
ナップサック問題は、荷物の選び方
トラックに積める重さは50kgまでです。荷物は3つあり、重さと価値（千円）が決まっています。価値の合計がいちばん大きくなる選び方を探します。
荷物は、積むか積まないかの2つに1つで、半分だけは積めません。
荷物と選び方
| 選び方 | 重さ | 価値 |
|---|---|---|
| 荷物1（10kg、60）と荷物2（20kg、100） | 30kg | 160 |
| 荷物1と荷物3（30kg、120） | 40kg | 180 |
| 荷物2と荷物3 | 50kg | 220 |
| 3つとも | 60kg | 積めない |
学生が入力するセルは、このプレビューでは空白です。
価値の高い順では、最大にならない
1kgあたりの価値は、荷物1が6、荷物2が5、荷物3が4です。この順に積むと、荷物1と2で30kg、価値は160になります。
荷物3は入りません。しかし最適は、荷物2と3の220です。整数の問題では、貪欲な選び方が最適にならないのです。
整数の条件を外して解く
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-60, -100, -120], A_ub=[[10, 20, 30]], b_ub=[50], bounds=(0, 1)); print(round(-r.fun, 2), r.x)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
整数の条件を付けて解く
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-60, -100, -120], A_ub=[[10, 20, 30]], b_ub=[50], bounds=(0, 1), integrality=[1, 1, 1]); print(round(-r.fun, 2), r.x)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
多くの人は、線形計画の答えを四捨五入すれば、整数の最適解になると考えます。丸めた点は、実行可能でないことも、最適でないこともあります。整数の問題は、整数の条件を付けて解きます。
動的計画法は、小さな答えを表にためる
全部の選び方を試すと、荷物がn個で2のn乗通りです。30個で約10億通りになります。これが組合せ爆発です。
動的計画法は、「積載がwのときの最大の価値」を表にためます。荷物を1つずつ加え、表を更新するだけで、荷物の数 × 積載量の回数で済みます。
積載ごとの最大の価値の表（10kg刻み）
| 荷物を加えたあと | 0kg | 10kg | 20kg | 30kg | 40kg | 50kg |
|---|---|---|---|---|---|---|
| まだ何もない | 0 | 0 | 0 | 0 | 0 | 0 |
| 荷物1（10kg、60） | 0 | 60 | 60 | 60 | 60 | 60 |
| 荷物2（20kg、100） | 0 | 60 | 100 | 160 | 160 | 160 |
| 荷物3（30kg、120） | 0 | 60 | 100 | 160 | 180 | 220 |
学生が入力するセルは、このプレビューでは空白です。
30個の荷物の選び方の数
docker exec jupyter python3 -c "print(2 ** 30, 2 ** 40)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
表を更新して答えを出す
# 動的計画法で、積載50kgの最大の価値を求めます。
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
best = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1):
if best[w - weights[i]] + values[i] > best[w]:
best[w] = best[w - weights[i]] + values[i]
print("最大の価値:", best[capacity])
print("積載40kgのとき:", best[40])
# capacity を 60 に変えて、答えがどうなるか確かめてください。
さらに挑戦: 自分の荷物で
上のコードの重さと価値を、自分の持ち物に変えてください。登山のリュックの重さの上限を決めて、持っていくものを選びます。
荷物を1つ増やすと、表の更新が1回増えるだけです。全部試す方法と、速さを比べて書きましょう。