これなに
某社では、技術書やビジネス書を買うと一定額まで補助してもらえるそうです。(本は自分で所有できます)
買いたい本が複数あって、N回 補助の機会があるとき、どの本を買ったら良いでしょうか？
組合せ最適化で計算してみましょう。
考え方
本を買ったら価値は9割になるとして、目的関数を「0.9×購入金額―自腹額」とします。
また、各機会ごとに合計購入金額が補助額を超えた分が自腹額となります。
この目的関数を最大化してみましょう。
下記は、N＝1のときの目的関数のイメージです。傾きは、左側が0.9で、右側が -0.1(=0.9-1)です。
1冊の本は分割できないので、購入額候補（本の組合せ）は、離散的な点になります。
買いたい本のリスト
リストを表示します。
python
import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars
a = pd.DataFrame([
('吾輩は猫だろう', 981),
('風の三四郎', 726),
('夏との扉', 1024),
('高い城の人', 1335),
('天王星年代記', 865),
('並列都市の科学', 1171),
('星は無慈悲な夜の王', 914),
('火の島かご', 463),
('ロボットは我', 758),
('未来世紀カガワ', 1507),
('ケイコとアベ', 689),
('48億円の身代金', 1412),
('星々の王女様', 826),
('猫とゆりかもめ', 649),
('風と共にとまる', 1083),
], columns=['Title', 'Price'])
a
| Title | Price | |
|---|---|---|
| 0 | 吾輩は猫だろう | 981 |
| 1 | 風の三四郎 | 726 |
| 2 | 夏との扉 | 1024 |
| 3 | 高い城の人 | 1335 |
| 4 | 天王星年代記 | 865 |
| 5 | 並列都市の科学 | 1171 |
| 6 | 星は無慈悲な夜の王 | 914 |
| 7 | 火の島かご | 463 |
| 8 | ロボットは我 | 758 |
| 9 | 未来世紀カガワ | 1507 |
| 10 | ケイコとアベ | 689 |
| 11 | 48億円の身代金 | 1412 |
| 12 | 星々の王女様 | 826 |
| 13 | 猫とゆりかもめ | 649 |
| 14 | 風と共にとまる | 1083 |
Pythonで計算する
回数を4回、1回当たりの補助額を3000円とします。
python
N = 4 # 回数
S = 3000 # 1回当たりの補助額
m = LpProblem(sense=LpMaximize)
for i in range(N):
a[f'Var{i}'] = addbinvars(len(a))
sums = addvars(N) # 購入額
owns = addvars(N) # 自腹額
m += 0.9*lpDot(a.Price,sum(a[f'Var{i}'] for i in range(N))) - lpSum(owns)
for i in range(N):
m += sums[i] == lpDot(a.Price,a[f'Var{i}'])
m += owns[i] >= sums[i] - S
for _,r in a.iterrows():
m += lpSum(r[f'Var{i}'] for i in range(N)) <= 1 # 同じ本は1冊まで
%time m.solve()
print(LpStatus[m.status])
for i in range(N):
a[f'Val{i}'] = a[f'Var{i}'].apply(value)
print(a[a[f'Val{i}']>0.5].iloc[:,:2])
print(f'{i+1} 合計 {value(sums[i])}')
>>>
Wall time: 49.8 s
Optimal
Title Price
9 未来世紀カガワ 1507
10 ケイコとアベ 689
12 星々の王女様 826
1 合計 3022.0
Title Price
1 風の三四郎 726
4 天王星年代記 865
11 48億円の身代金 1412
2 合計 3003.0
Title Price
5 並列都市の科学 1171
8 ロボットは我 758
14 風と共にとまる 1083
3 合計 3012.0
Title Price
0 吾輩は猫だろう 981
6 星は無慈悲な夜の王 914
7 火の島かご 463
13 猫とゆりかもめ 649
4 合計 3007.0
結構、時間がかかりますね。モデル化の工夫の余地があるかもしれません。
1回だけなら、「天王星年代記, 星は無慈悲な夜の王, 火の島かご, ロボットは我」を買うとちょうど3000円ですが、4回買うとすると、ちょうどの組合せはなくなりました。
以上