尧图网站建设 
沉寂了很久接下来小编要朝着目标努力了。目前初步规划了2期内容用 Python 三类主流求解器Gurobi、COPT、SCIP把网络流问题和铁路运输经典问题两条线一以贯之地讲透。第 1 期讲网络流家族第 2 期沿着铁路运输组织规划流程逐个建模求解。目录1. 问题场景2. 数学建模2.1 集合、参数与决策变量2.2 目标函数与约束条件3. 求解案例4. PythonGurobi求解5. PythonCOPT求解6. PythonSCIP求解参考资料1. 问题场景这个场景你一定不陌生早高峰你要从家赶到公司打卡路网中有几个路口和地标每条路的通行时间不同堵车程度不同。你想知道走哪条路总时间最短把路网抽象一下节点家、若干路口/地标、公司边路口间的路段带通行时间分钟起点家终点公司目标家到公司的总通行时间最小这就是一个最典型的最短路问题在带权有向图上求从起点到终点权值和最小的路径。2. 数学建模2.1 集合、参数与决策变量2.2 目标函数与约束条件3. 求解案例为了让模型落地且便于读者手算验证我们构造一个小型路网。4. PythonGurobi求解fromgurobipyimportGRB,Model,quicksum# # 1. 定义案例数据# N[1,2,3,4,5,6]A[(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,6),(5,4),(5,6)]C{(1,2):6,(1,3):4,(2,3):2,(2,4):2,(3,4):1,(3,5):2,(4,6):7,(5,4):1,(5,6):3}s1t6b{1:1,2:0,3:0,4:0,5:0,6:-1}# # 2. 建模与求解# defbuild_and_solve(N:list,A:list,C:dict,b:dict,s:int,t:int):# ---- 建模 ----modelModel(ShortestPath_Gurobi)# 决策变量 x_{ij} in {0,1}xmodel.addVars(A,vtypeGRB.BINARY,namex)# 目标: min sum c_{ij} * x_{ij}model.setObjective(quicksum(C[i,j]*x[i,j]for(i,j)inA),GRB.MINIMIZE,)# 约束: 流平衡foriinN:out_exprquicksum(x[i,j]for(ii,j)inAifiii)in_exprquicksum(x[j,i]for(j,ii)inAifiii)model.addConstr(out_expr-in_exprb[i],namefflow_balance_{i})# ---- 求解 ----model.optimize()# ---- 结果 ----statusmodel.Statusifmodel.StatusGRB.OPTIMAL:chosen[(i,j)for(i,j)inAifx[i,j].X0.5]totalmodel.ObjVal pathreconstruct_path(chosen,s,t)return{status:OPTIMAL,total_cost:total,path:path,chosen_edges:chosen,}return{status:fstatus{status},total_cost:None,path:None,chosen_edges:None}defreconstruct_path(chosen,s,t):由选中的边集合按出度链还原有序路径。nxt{i:jfor(i,j)inchosen}path[s]curswhilecur!t:curnxt[cur]path.append(cur)returnpath# # 3. 主流程# defmain():resbuild_and_solve(N,A,C,b,s,t)ifres[status]OPTIMAL:print(f求解状态: OPTIMAL)print(f目标值{res[total_cost]})print(f选中边:{res[chosen_edges]})print(f最短路径:{res[path]})else:print(f求解状态:{res[status]}(无可行径路))if__name____main__:main()5. PythonCOPT求解fromcoptpyimportCOPT,Envr# # 1. 定义案例数据# N[1,2,3,4,5,6]A[(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,6),(5,4),(5,6)]C{(1,2):6,(1,3):4,(2,3):2,(2,4):2,(3,4):1,(3,5):2,(4,6):7,(5,4):1,(5,6):3}s1t6b{1:1,2:0,3:0,4:0,5:0,6:-1}# # 2. 建模与求解# defbuild_and_solve(N:list,A:list,C:dict,b:dict,s:int,t:int):# ---- 建模 ----modelEnvr().createModel(ShortestPath_COPT)# 决策变量 x_{ij} in {0,1}xmodel.addVars(A,vtypeCOPT.BINARY,nameprefixx)# 目标: min sum c_{ij} * x_{ij}model.setObjective(sum(C[i,j]*x[i,j]for(i,j)inA),COPT.MINIMIZE)# 约束: 流平衡foriinN:out_exprsum(x[i,j]for(ii,j)inAifiii)in_exprsum(x[j,i]for(j,ii)inAifiii)model.addConstr(out_expr-in_exprb[i],namefflow_balance_{i})# ---- 求解 ----model.solve()# ---- 结果 ----statusmodel.statusifstatusCOPT.OPTIMAL:chosen[(i,j)for(i,j)inAifx[i,j].X0.5]totalfloat(model.getAttr(COPT.Attr.BestObj))pathreconstruct_path(chosen,s,t)return{status:OPTIMAL,total_cost:total,path:path,chosen_edges:chosen}return{status:fstatus{status},total_cost:None,path:None,chosen_edges:None}defreconstruct_path(chosen,s,t):由选中的边集合按出度链还原有序路径。nxt{i:jfor(i,j)inchosen}path[s]curswhilecur!t:curnxt[cur]path.append(cur)returnpath# # 3. 主流程# defmain():resbuild_and_solve(N,A,C,b,s,t)ifres[status]OPTIMAL:print(f求解状态: OPTIMAL)print(f目标值{res[total_cost]})print(f选中边:{res[chosen_edges]})print(f最短路径:{res[path]})else:print(f求解状态:{res[status]}(无可行径路))if__name____main__:main()6. PythonSCIP求解frompyscipoptimportModel,quicksum# # 1. 数据读取# N[1,2,3,4,5,6]A[(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,6),(5,4),(5,6)]C{(1,2):6,(1,3):4,(2,3):2,(2,4):2,(3,4):1,(3,5):2,(4,6):7,(5,4):1,(5,6):3}s1t6b{1:1,2:0,3:0,4:0,5:0,6:-1}# # 2. 建模与求解# defbuild_and_solve(N:list,A:list,C:dict,b:dict,s:int,t:int):# ---- 建模 ----modelModel(ShortestPath_SCIP)# 决策变量 x_{ij} in {0,1}x{}for(i,j)inA:x[i,j]model.addVar(lb0,ub1,vtypeBINARY,namefx_{i}_{j})# 目标: min sum c_{ij} * x_{ij}model.setObjective(quicksum(C[i,j]*x[i,j]for(i,j)inA),minimize)# 约束: 流平衡foriinN:out_exprquicksum(x[i,j]for(ii,j)inAifiii)in_exprquicksum(x[j,i]for(j,ii)inAifiii)model.addCons(out_expr-in_exprb[i],namefflow_balance_{i})# ---- 求解 ----model.setRealParam(limits/time,30)model.optimize()# ---- 结果 ----statusmodel.getStatus()ifstatusoptimal:chosen[(i,j)for(i,j)inAifmodel.getVal(x[i,j])0.5]totalmodel.getObjVal()pathreconstruct_path(chosen,s,t)return{status:OPTIMAL,total_cost:total,path:path,chosen_edges:chosen}return{status:fstatus{status},total_cost:None,path:None,chosen_edges:None}defreconstruct_path(chosen,s,t):由选中的边集合按出度链还原有序路径。nxt{i:jfor(i,j)inchosen}path[s]curswhilecur!t:curnxt[cur]path.append(cur)returnpath# # 3. 主流程# defmain():resbuild_and_solve(N,A,C,b,s,t)ifres[status]OPTIMAL:print(f求解状态: OPTIMAL)print(f目标值{res[total_cost]})print(f选中边:{res[chosen_edges]})print(f最短路径:{res[path]})else:print(f求解状态:{res[status]}(无可行径路))if__name____main__:main()参考资料[1] Ahuja, Ravindra K. et al. “Network Flows: Theory, Algorithms, and Applications.” (1993). 最短路问题求解 | Python+Gurobi-COPT-SCIP
沉寂了很久接下来小编要朝着目标努力了。目前初步规划了2期内容用 Python 三类主流求解器Gurobi、COPT、SCIP把网络流问题和铁路运输经典问题两条线一以贯之地讲透。第 1 期讲网络流家族第 2 期沿着铁路运输组织规划流程逐个建模求解。目录1. 问题场景2. 数学建模2.1 集合、参数与决策变量2.2 目标函数与约束条件3. 求解案例4. PythonGurobi求解5. PythonCOPT求解6. PythonSCIP求解参考资料1. 问题场景这个场景你一定不陌生早高峰你要从家赶到公司打卡路网中有几个路口和地标每条路的通行时间不同堵车程度不同。你想知道走哪条路总时间最短把路网抽象一下节点家、若干路口/地标、公司边路口间的路段带通行时间分钟起点家终点公司目标家到公司的总通行时间最小这就是一个最典型的最短路问题在带权有向图上求从起点到终点权值和最小的路径。2. 数学建模2.1 集合、参数与决策变量2.2 目标函数与约束条件3. 求解案例为了让模型落地且便于读者手算验证我们构造一个小型路网。4. PythonGurobi求解fromgurobipyimportGRB,Model,quicksum# # 1. 定义案例数据# N[1,2,3,4,5,6]A[(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,6),(5,4),(5,6)]C{(1,2):6,(1,3):4,(2,3):2,(2,4):2,(3,4):1,(3,5):2,(4,6):7,(5,4):1,(5,6):3}s1t6b{1:1,2:0,3:0,4:0,5:0,6:-1}# # 2. 建模与求解# defbuild_and_solve(N:list,A:list,C:dict,b:dict,s:int,t:int):# ---- 建模 ----modelModel(ShortestPath_Gurobi)# 决策变量 x_{ij} in {0,1}xmodel.addVars(A,vtypeGRB.BINARY,namex)# 目标: min sum c_{ij} * x_{ij}model.setObjective(quicksum(C[i,j]*x[i,j]for(i,j)inA),GRB.MINIMIZE,)# 约束: 流平衡foriinN:out_exprquicksum(x[i,j]for(ii,j)inAifiii)in_exprquicksum(x[j,i]for(j,ii)inAifiii)model.addConstr(out_expr-in_exprb[i],namefflow_balance_{i})# ---- 求解 ----model.optimize()# ---- 结果 ----statusmodel.Statusifmodel.StatusGRB.OPTIMAL:chosen[(i,j)for(i,j)inAifx[i,j].X0.5]totalmodel.ObjVal pathreconstruct_path(chosen,s,t)return{status:OPTIMAL,total_cost:total,path:path,chosen_edges:chosen,}return{status:fstatus{status},total_cost:None,path:None,chosen_edges:None}defreconstruct_path(chosen,s,t):由选中的边集合按出度链还原有序路径。nxt{i:jfor(i,j)inchosen}path[s]curswhilecur!t:curnxt[cur]path.append(cur)returnpath# # 3. 主流程# defmain():resbuild_and_solve(N,A,C,b,s,t)ifres[status]OPTIMAL:print(f求解状态: OPTIMAL)print(f目标值{res[total_cost]})print(f选中边:{res[chosen_edges]})print(f最短路径:{res[path]})else:print(f求解状态:{res[status]}(无可行径路))if__name____main__:main()5. PythonCOPT求解fromcoptpyimportCOPT,Envr# # 1. 定义案例数据# N[1,2,3,4,5,6]A[(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,6),(5,4),(5,6)]C{(1,2):6,(1,3):4,(2,3):2,(2,4):2,(3,4):1,(3,5):2,(4,6):7,(5,4):1,(5,6):3}s1t6b{1:1,2:0,3:0,4:0,5:0,6:-1}# # 2. 建模与求解# defbuild_and_solve(N:list,A:list,C:dict,b:dict,s:int,t:int):# ---- 建模 ----modelEnvr().createModel(ShortestPath_COPT)# 决策变量 x_{ij} in {0,1}xmodel.addVars(A,vtypeCOPT.BINARY,nameprefixx)# 目标: min sum c_{ij} * x_{ij}model.setObjective(sum(C[i,j]*x[i,j]for(i,j)inA),COPT.MINIMIZE)# 约束: 流平衡foriinN:out_exprsum(x[i,j]for(ii,j)inAifiii)in_exprsum(x[j,i]for(j,ii)inAifiii)model.addConstr(out_expr-in_exprb[i],namefflow_balance_{i})# ---- 求解 ----model.solve()# ---- 结果 ----statusmodel.statusifstatusCOPT.OPTIMAL:chosen[(i,j)for(i,j)inAifx[i,j].X0.5]totalfloat(model.getAttr(COPT.Attr.BestObj))pathreconstruct_path(chosen,s,t)return{status:OPTIMAL,total_cost:total,path:path,chosen_edges:chosen}return{status:fstatus{status},total_cost:None,path:None,chosen_edges:None}defreconstruct_path(chosen,s,t):由选中的边集合按出度链还原有序路径。nxt{i:jfor(i,j)inchosen}path[s]curswhilecur!t:curnxt[cur]path.append(cur)returnpath# # 3. 主流程# defmain():resbuild_and_solve(N,A,C,b,s,t)ifres[status]OPTIMAL:print(f求解状态: OPTIMAL)print(f目标值{res[total_cost]})print(f选中边:{res[chosen_edges]})print(f最短路径:{res[path]})else:print(f求解状态:{res[status]}(无可行径路))if__name____main__:main()6. PythonSCIP求解frompyscipoptimportModel,quicksum# # 1. 数据读取# N[1,2,3,4,5,6]A[(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,6),(5,4),(5,6)]C{(1,2):6,(1,3):4,(2,3):2,(2,4):2,(3,4):1,(3,5):2,(4,6):7,(5,4):1,(5,6):3}s1t6b{1:1,2:0,3:0,4:0,5:0,6:-1}# # 2. 建模与求解# defbuild_and_solve(N:list,A:list,C:dict,b:dict,s:int,t:int):# ---- 建模 ----modelModel(ShortestPath_SCIP)# 决策变量 x_{ij} in {0,1}x{}for(i,j)inA:x[i,j]model.addVar(lb0,ub1,vtypeBINARY,namefx_{i}_{j})# 目标: min sum c_{ij} * x_{ij}model.setObjective(quicksum(C[i,j]*x[i,j]for(i,j)inA),minimize)# 约束: 流平衡foriinN:out_exprquicksum(x[i,j]for(ii,j)inAifiii)in_exprquicksum(x[j,i]for(j,ii)inAifiii)model.addCons(out_expr-in_exprb[i],namefflow_balance_{i})# ---- 求解 ----model.setRealParam(limits/time,30)model.optimize()# ---- 结果 ----statusmodel.getStatus()ifstatusoptimal:chosen[(i,j)for(i,j)inAifmodel.getVal(x[i,j])0.5]totalmodel.getObjVal()pathreconstruct_path(chosen,s,t)return{status:OPTIMAL,total_cost:total,path:path,chosen_edges:chosen}return{status:fstatus{status},total_cost:None,path:None,chosen_edges:None}defreconstruct_path(chosen,s,t):由选中的边集合按出度链还原有序路径。nxt{i:jfor(i,j)inchosen}path[s]curswhilecur!t:curnxt[cur]path.append(cur)returnpath# # 3. 主流程# defmain():resbuild_and_solve(N,A,C,b,s,t)ifres[status]OPTIMAL:print(f求解状态: OPTIMAL)print(f目标值{res[total_cost]})print(f选中边:{res[chosen_edges]})print(f最短路径:{res[path]})else:print(f求解状态:{res[status]}(无可行径路))if__name____main__:main()参考资料[1] Ahuja, Ravindra K. et al. “Network Flows: Theory, Algorithms, and Applications.” (1993).