In [14]:
#容量制約付き施設配置問題
from gurobipy import *
def make_data():
I,d = multidict({1:80, 2:270, 3:250, 4:160, 5:180}) # demand
J,M,f = multidict({1:[500,1000], 2:[500,1000], 3:[500,1000]}) # capacity, fixed costs
c = {(1,1):4, (1,2):6, (1,3):9, # transportation costs
(2,1):5, (2,2):4, (2,3):7,
(3,1):6, (3,2):3, (3,3):4,
(4,1):8, (4,2):5, (4,3):3,
(5,1):10, (5,2):8, (5,3):4,
}
return I,J,d,M,f,c
In [15]:
#multidictを三つ一気にやると、keyの先のリストから一つずつ辞書の先にくっつく
make_data()
Out[15]:
In [39]:
#変数の名前はつけないと結果の解釈ができない
def flp(I,J,d,M,f,c):
model = Model("flp")
x, y = {} ,{}
for j in J:
y[j] = model.addVar(vtype = "B", name = "facility(%s)" %j)
for i in I:
x[i,j] = model.addVar(vtype = "C", name = "transport(%s, %s)" %(i,j))
model.update()
for i in I:
model.addConstr(quicksum(x[i,j] for j in J) == d[i])
for j in J:
model.addConstr(quicksum(x[i,j] for i in I) <= M[j]* y[j])
for (i,j) in x:
model.addConstr(x[i,j] <= d[i] * y[j])
model.setObjective(quicksum(f[j]*y[j] for j in J) + quicksum(c[i,j]* x[i,j] for i in I for j in J))
model.__data = x,y
return model
In [40]:
if __name__ == "__main__":
I,J,d,c,f,M = make_data()
model = flp(I,J,d,c,f,M)
model.optimize()
In [41]:
for v in model.getVars():
print v.VarName ,v.X
In [53]:
#k-median problem
def kmedian(I, J, c, k):
model = Model("k-median")
x ,y = {} ,{}
for j in J:
y[j] = model.addVar(vtype= "B", name = "facility(%s)" %j)
for i in I:
x[i,j] = model.addVar(vtype="B" ,name = "satisfaction(%s, %s)" %(i,j))
model.update()
for i in I:
model.addConstr(quicksum(x[i,j] for j in J) == 1)
for j in J:
model.addConstr(x[i, j] <= y[j])
model.addConstr(quicksum(y[j] for j in J) == k)
model.setObjective(quicksum(c[i,j] *x[i,j] for i in I for j in J))
model.__data = x, y
return model
In [54]:
def make_data2():
I = [1,2,3,4,5]
J = [1,2,3]
c = c = {(1,1):4, (1,2):6, (1,3):9,
(2,1):5, (2,2):4, (2,3):7,
(3,1):6, (3,2):3, (3,3):4,
(4,1):8, (4,2):5, (4,3):3,
(5,1):10, (5,2):8, (5,3):4,}
k = 2
return I,J,c,k
In [55]:
if __name__ == "__main__":
I,J,c,k = make_data2()
model = kmedian( I,J,c,k)
model.optimize()
In [56]:
for v in model.getVars():
print v.VarName, v.X
#1、2さんは施設1に
#3、4、5さんは施設3に
#施設2は開設されなかった
In [57]:
#k-center problem
def kcenter(I, J, c, k):
model = Model("k-center")
z = model.addVar(vtype = "C", name = "max_distance" )
x, y = {}, {}
for j in J:
y[j] = model.addVar(vtype= "B", name = "facility(%s)" %j)
for i in I:
x[i,j] = model.addVar(vtype="B" ,name = "satisfaction(%s, %s)" %(i,j))
model.update()
for i in I:
model.addConstr(quicksum(x[i,j] for j in J) == 1)
for j in J:
model.addConstr(x[i, j] <= y[j])
model.addConstr(c[i,j] * x[i,j] <= z)
model.addConstr(quicksum(y[j] for j in J) == k)
model.setObjective(z)
model.__data = x, y
return model
In [58]:
if __name__ == "__main__":
I,J,c,k = make_data2()
model = kcenter( I,J,c,k)
model.optimize()
In [59]:
for v in model.getVars():
print v.VarName, v.X
#この場合はk-median problemと解は同じ
In [ ]: