네트워크 flow 문제를 풀어본다
문제는 정의는 아래와 같음
Commodities
Pencils, Pens
Nodes
Detroit, Denver, Boston, New York, Seattle
Arc capacity
Detroit -> Boston : 100
Detroit -> New York : 80
Detroit -> Seattle : 120
Denver -> Boston : 120
Denver -> New York : 120
Denver -> Seattle : 120
Cost
Demand
정리하면,
두개의 상품(Comodities)을 총 5개의 도시(Nodes)에서 이송할꺼임
도시간에 상품을 이송하는데 최대량이 있음(Arc capacity)
운송 단위당 드는 비용(Cost)이 있음
요구되는 양을 맞춰야 함(Demand) -> 생산지는 양수로 수요지는 음수로 표기
import gurobipy as gp
from gurobipy import GRB
# Commidities & Nodes
commodities = ["Pencils", "Pens"]
nodes = ["Detroit", "Denver", "Boston", "New York", "Seattle"]
# Multidict class를 이용하여 arcs capacity 선언
arcs, capacity = gp.multidict(
{
("Detroit", "Boston"): 100,
("Detroit", "New York"): 80,
("Detroit", "Seattle"): 120,
("Denver", "Boston"): 120,
("Denver", "New York"): 120,
("Denver", "Seattle"): 120,
}
)
# Cost
cost = {
("Pencils", "Detroit", "Boston"): 10,
("Pencils", "Detroit", "New York"): 20,
("Pencils", "Detroit", "Seattle"): 60,
("Pencils", "Denver", "Boston"): 40,
("Pencils", "Denver", "New York"): 40,
("Pencils", "Denver", "Seattle"): 30,
("Pens", "Detroit", "Boston"): 20,
("Pens", "Detroit", "New York"): 20,
("Pens", "Detroit", "Seattle"): 80,
("Pens", "Denver", "Boston"): 60,
("Pens", "Denver", "New York"): 70,
("Pens", "Denver", "Seattle"): 30,
}
# Demand for pairs of commodity-city
inflow = {
("Pencils", "Detroit"): 50,
("Pencils", "Denver"): 60,
("Pencils", "Boston"): -50,
("Pencils", "New York"): -50,
("Pencils", "Seattle"): -10,
("Pens", "Detroit"): 60,
("Pens", "Denver"): 40,
("Pens", "Boston"): -40,
("Pens", "New York"): -30,
("Pens", "Seattle"): -30,
}
model = gp.Model("netflow")
flow = model.addVars(commodities, arcs, obj=cost, name="flow")
model.addConstrs((flow.sum("*", i, j) <= capacity[i, j] for i, j in arcs), "cap")
model.addConstrs(
(flow.sum(h, "*", j) + inflow[h, j] == flow.sum(h, j, "*") for h in commodities for j in nodes),
"nodes",
)
model.optimize()
.addVars()
를 이용해서 변수 선언.
flow = model.addVars(commodities, arcs, obj=cost, name="flow")
의 경우, flow 라는 이름을 가지면서 cost를 coefficient로 가지게 됨.
ex) flow['Pencils', 'Detroit', Boston'] 이런식..
model.addConstrs((flow.sum("*", i, j) <= capacity[i, j] for i, j in arcs), "cap")
flow
에서 i
-> j
로 가는 모든 Commodity(*
)의 합은 i
-> j
arc의 capacity보다 작아야 함을 의미
model.addConstrs((flow.sum(h, "*", j) + inflow[h, j] == flow.sum(h, j, "*") for h in commodities for j in nodes), "nodes")
flow
에서 각 Commodity(h
) 당 j
로 부터 향하는 다른 Node(*
)의 합 + 해당 노드에서 commodity의 수요 == flow
에서 각 Commodity(h
) 당 j
로 부터 향하는 다른 Node(*
)의 합
즉 수요 제약을 만족해야함 의미
ex) Boston을 향하는 모든 pencils의 합 + Boston의 pencils의 수요 == 0 (Boston에서 나가는게 없으니)
model.optimize()
print()
if model.status == GRB.OPTIMAL:
solution = model.getAttr("x", flow)
for h in commodities:
print(h)
for i, j in arcs:
if solution[h, i, j] > 0:
print(" ", i, j, solution[h, i, j])
최적화하고 정답을 출력하면 아래와 같은 결과를 얻는다
Optimize a model with 16 rows, 12 columns and 36 nonzeros
Model fingerprint: 0xc43e5943
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+01, 8e+01]
Bounds range [0e+00, 0e+00]
RHS range [1e+01, 1e+02]
Presolve removed 16 rows and 12 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Iteration Objective Primal Inf. Dual Inf. Time
0 5.5000000e+03 0.000000e+00 2.000000e+01 0s
Extra one simplex iteration after uncrush
1 5.5000000e+03 0.000000e+00 0.000000e+00 0s
Solved in 1 iterations and 0.00 seconds
Optimal objective 5.500000000e+03
Pencils
Detroit Boston 50.0
Denver New York 50.0
Denver Seattle 10.0
Pens
Detroit Boston 30.0
Detroit New York 30.0
Denver Boston 10.0
Denver Seattle 30.0