これなに
OR学会の機関誌10月号「学生たちのOR」特集から、適当に最適化の問題をピックアップしてPythonで解いてみたいと思います。
準備として、numpy, pulp, ortoolpy が必要です。環境構築は、組合せ最適化を使おうを参考にしてください。
フードデザート問題
論文「長崎市におけるフードデザート問題の分析」の問題を使わせてもらいましょう。
全ての人が通えるように生鮮食料品店を配置し、配置数を最小化します。一般人は5000m以内に、高齢者は1500m以内でないと通えません。
考え方
容量制約なし施設配置問題です。
Pythonで解く
まず、ランダムなデータを作成します。
python
import numpy as np
from pulp import *
from ortoolpy import addvar, addvars
nc, n1, n2 = 4, 2, 2 # 候補点数、一般人地域数、高齢者地域数
np.random.seed(2)
dist1 = np.random.randint(4000, 6000, (nc, n1))
dist1 # 候補点から一般人地域への距離
>>>
array([[5192, 4527],
[4493, 5608],
[5558, 4299],
[4466, 5099]])
python
dist2 = np.random.randint(1000, 2000, (nc, n1))
dist2 # 候補点から高齢者地域への距離
>>>
array([[1360, 1263],
[1674, 1433],
[1607, 1587],
[1725, 1047]])
定式化して解きます。
python
m = LpProblem()
x = addvars(n, cat=LpBinary) # 変数
m += lpSum(x) # 目的関数
for i in range(n1):
m += lpDot(dist1[i] <= 5000, x) >= 1 # 制約
for i in range(n2):
m += lpDot(dist2[i] <= 1500, x) >= 1 # 制約
m.solve()
[int(value(v)) for v in x]
>>>
[1, 1, 0, 0]
以上