[Python/数学模型]给大忙人看的速通三——图论优化

文章目录最大流问题旅行商问题最短路径问题最小生成树问题最大流问题输入数据网络的容量矩阵变量每条边的流量约束条件流量不能超过边的容量且满足流量守恒目标函数最大化从源点到汇点的流量输入格式: 第1行包含2个整数n表示农田数量m表示水管数量。 接下来m行每行包含3个整数a, b, c表示从农田a到农田b有一条有向水管其流量限制为c。农田的编号从1到n。 输出格式: 输出一个整数表示从1号农田到n号农田的最大流量。 输入示例 4 5 1 2 10 1 3 5 2 3 5 2 4 20 3 4 5 输出示例 15代码如下# 读入n,mmap(int,input().split())edges[]for_inrange(m):a,b,cmap(int,input().split())edges.append((a,b,c))# 决策变量每条边上的流量xcp.Variable(m)constraints[]# 1. 容量约束fori,(a,b,c)inenumerate(edges):constraints.append(x[i]0)constraints.append(x[i]c)# 2. 中间点流量守恒forkinrange(2,n):# 2 ~ n-1inflow0outflow0fori,(a,b,c)inenumerate(edges):ifbk:inflowx[i]ifak:outflowx[i]constraints.append(inflowoutflow)# 3. 目标最大化源点1的净流出source_out0source_in0fori,(a,b,c)inenumerate(edges):ifa1:source_outx[i]ifb1:source_inx[i]objectivecp.Maximize(source_out-source_in)# 求解probcp.Problem(objective,constraints)prob.solve()# 输出结果print(round(prob.value))旅行商问题输入数据城市之间的距离矩阵变量每条路径是否被选中约束条件每个城市只能访问一次且形成一个闭环目标函数最小化总旅行距离因为旅行商问题的结果是一个闭环因此我们不需要考虑第一个城市是什么指定第一个城市作为出发点就可以了。输入格式 第1行一个整数 n表示城市数量。 接下来的n行每行包含n个整数表示城市之间的距离矩阵。 输出格式 输出一个整数表示总行程的最短距离。 输入示例 5 0 1050 1420 1270 460 1050 0 1200 240 1100 1420 1200 0 1950 1760 1270 240 1950 0 1270 460 1100 1760 1270 0 输出示例 4590代码如下# ---------- 决策变量 ----------# x[i, j] 1 表示从 i 到 jxcp.Variable((n,n),booleanTrue)# MTZ 顺序变量ucp.Variable(n)constraints[]# ---------- 基本约束 ----------# 不允许自己到自己constraints.append(cp.diag(x)0)# 每个城市恰好出发一次foriinrange(n):constraints.append(cp.sum(x[i,:])1)# 每个城市恰好到达一次forjinrange(n):constraints.append(cp.sum(x[:,j])1)# ---------- MTZ 子回路消除 ----------# 固定第0个城市作为起点constraints.append(u[0]0)foriinrange(1,n):constraints.append(u[i]1)constraints.append(u[i]n-1)foriinrange(1,n):forjinrange(1,n):ifi!j:constraints.append(u[i]-u[j]n*x[i,j]n-1)# 如果选定了 i-j此时x[i, j] 1则 u[i] u[j]# ---------- 目标函数 ----------objectivecp.Minimize(cp.sum(cp.multiply(D,x)))最短路径问题输入数据图的邻接矩阵和边权变量每条边是否被选中约束条件形成一条从源点到汇点的路径目标函数最小化路径总权重输入格式: 第1行包含3个整数n表示城市数量m表示道路数量k表示查询数量。 接下来m行每行包含3个整数a, b, t表示城市a和城市b之间有一条双向道路行驶这条道路需要t时间。城市的编号从1到n。 接下来k行每行包含2个整数s, d表示一次查询从城市s出发到达城市d。 输出格式 输出k行每行包含一个整数表示对应查询的最短时间。 如果无法到达目标城市输出-1。 输入示例 4 5 2 1 2 3 1 3 1 2 4 2 3 4 4 2 3 5 1 4 2 4 输出示例 5 2代码如下inputsys.stdin.readlinedefsolve_one_query(n,edges,s,t):# 无向边拆成有向边arcs[]cost[]fora,b,winedges:arcs.append((a,b))cost.append(w)arcs.append((b,a))cost.append(w)mlen(arcs)# 决策变量是否选第i条弧 0或者1xcp.Variable(m,booleanTrue)constraints[]# 流量平衡约束foriinrange(1,n1):outflow0inflow0fore,(u,v)inenumerate(arcs):ifui:outflowx[e]# 这条边被选作路径的起点ifvi:inflowx[e]# 这条边被选为路径的终点ifis:constraints.append(outflow-inflow1)# 起点有后继没有前驱elifit:constraints.append(outflow-inflow-1)# 终点有前驱没有后继else:constraints.append(outflow-inflow0)# 中间的点必定有前驱和后继# 目标函数objectivecp.Minimize(sum(cost[e]*x[e]foreinrange(m)))# 建立问题probcp.Problem(objective,constraints)# 求解prob.solve()returnint(round(prob.value))# 主程序n,m,kmap(int,input().split())edges[]for_inrange(m):a,b,wmap(int,input().split())edges.append((a,b,w))queries[tuple(map(int,input().split()))for_inrange(k)]fors,tinqueries:print(solve_one_query(n,edges,s,t))最小生成树问题输入数据图的邻接矩阵和边权变量每条边是否被选中约束条件选中的边形成一个连接所有节点的树并且这个树内部的所有子集的边数都不能超过子集节点数减一目标函数最小化选中边的总权重输入格式: 第1行包含2个整数n表示城市数量m表示现有道路数量。 接下来m行每行包含3个整数a, b, c表示城市a和城市b之间有一条现有道路升级成本为c。城市的编号从1到n。 输出格式: 输出一个整数表示连接所有城市的最低成本。 输入示例 6 9 1 2 3 1 3 1 1 4 2 2 3 2 2 5 3 3 4 3 3 6 5 4 5 6 5 6 2 输出示例 10代码如下importcvxpyascpimportitertools n,mmap(int,input().split())edge[]cost[]for_inrange(m):a,b,cmap(int,input().split())edge.append((a,b))cost.append(c)xcp.Variable(m,booleanTrue)constraints[]constraints.append(cp.sum(x)n-1)nodeslist(range(1,n1))forrinrange(2,n):# 子集大小 2 到 n-1forSinitertools.combinations(nodes,r):Sset(S)idx[]fore,(u,v)inenumerate(edge):ifuinSandvinS:idx.append(e)ifidx:constraints.append(cp.sum(x[idx])len(S)-1)foriinrange(m):constraints.append(x[i]1)constraints.append(x[i]0)objectivecp.Minimize(cp.sum(cp.multiply(cost,x)))probcp.Problem(objective,constraints)prob.solve()print(int(prob.value));