(Python)Gurobi求解最大流问题
示例网络，箭头上的数字代表弧允许通过的最大流量
增加两个虚拟节点，节点0和节点7
import gurobipy as gpfrom gurobipy import GRB# Input the information of the networkdict_capacity = {(0, 1): 99999, (1, 2): 70, (1, 3): 100, (1, 4): 90, (2, 6): 80, (3, 4): 40, (3, 5): 70, (4, 5): 40, (4, 6): 100, (5, 6): 90, (6, 7): 99999 }arc, capacity = gp.multidict(dict_capacity)# Construct the modelm = gp.Model("maxflow")# Decision variablesX = m.addVars(arc, name='X')# Add constraintsfor i, j in arc: # The volume of flow cannot exceed the capacity of the arc m.addConstr(X[i, j] <= capacity[i, j]) if i == 0 or j == 7: continue else: # Flow balance constraint m.addConstr(X.sum(i, '*') == X.sum('*', i))# Define the objective functionm.setObjective(X.sum(1, '*'), sense=GRB.MAXIMIZE)# Solve the modelm.optimize()# Output the resultsprint('*' * 60)print("The objective value is：", m.objVal)print('The flow in each arc is:')for i, j in arc: print("Node %d --> Node %d: %d" % (i, j, X[i, j].x))控制台输出结果
Using license file C:\Users\86158\gurobi.licGurobi Optimizer version 9.1.1 build v9.1.1rc0 (win64)Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 20 rows, 11 columns and 42 nonzerosModel fingerprint: 0x43a077e0Coefficient statistics: Matrix range [1e 00, 1e 00] Objective range [1e 00, 1e 00] Bounds range [0e 00, 0e 00] RHS range [4e 01, 1e 05]Presolve removed 17 rows and 5 columnsPresolve time: 0.00sPresolved: 3 rows, 6 columns, 9 nonzerosIteration Objective Primal Inf. Dual Inf. Time 0 2.6000000e 02 3.125000e 01 0.000000e 00 0s 3 2.6000000e 02 0.000000e 00 0.000000e 00 0sSolved in 3 iterations and 0.00 secondsOptimal objective 2.600000000e 02************************************************************The objective value is： 260.0The flow in each arc is:Node 0 --> Node 1: 260Node 1 --> Node 2: 70Node 1 --> Node 3: 100Node 1 --> Node 4: 90Node 2 --> Node 6: 70Node 3 --> Node 4: 40Node 3 --> Node 5: 60Node 4 --> Node 5: 30Node 4 --> Node 6: 100Node 5 --> Node 6: 90Node 6 --> Node 7: 0Process finished with exit code 0 赞 (0)