网络流问题求解及Gurobi+Python代码(最大流/最小成本网络流/多商品网络流)

2024-02-08 05:04

本文主要是介绍网络流问题求解及Gurobi+Python代码(最大流/最小成本网络流/多商品网络流),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.最大流问题

1.1 问题描述

1.2 Ford-Fulkerson算法

1.3 Gurobi测试 

2.最小成本网络流问题

2.1 问题描述  

2.2 供应链规划案例

3.多商品网络流问题

3.1 问题描述及模型

3.2 Gurobi测试


Gurobi求解代码:GitHub - bujibujibiuwang/Network-Flow-Problem: 网络流问题

1.最大流问题

1.1 问题描述

最大流问题(Maximum flow problem MFP)描述为一个有向图,包含源节点(source)和汇点(sink),以及连接这些节点的有向边,每条边都有一个容量,表示通过该边的最大流量。问题优化目标是寻找最大流量传输。如下图所示,该网络的最大流为23。

求解最大流问题的方法:

  • Ford-Fulkerson 算法 
  • 求解器

1.2 Ford-Fulkerson算法

  • 定义1

  • 定义2

算法步骤如下:

下面是一个简单例子

1.3 Gurobi测试 

 最大流问题有两个约束:流平衡约束和容量约束,模型描述如下:

在一个简单的例子上使用gurobi求解最大流问题,结果如下图,最大流为20

模型核心代码如下: 

maxflow = gp.Model()
flow = maxflow.addVars(edges.keys(), vtype=GRB.CONTINUOUS)
maxflow.setObjective(flow.sum('*', 't'), GRB.MAXIMIZE)
maxflow.addConstrs(flow[i, j] <= edges[i, j] for i, j in edges.keys())
maxflow.addConstrs(flow.sum('*', i) - flow.sum(i, '*') == 0 for i in points.keys() if i != 's' and i != 't')
maxflow.optimize()

2.最小成本网络流问题

2.1 问题描述  

运输问题,分配问题,转运问题,最短路径,最大流等都属于最小成本网络流问题(Minimum-cost network flow problem MCNFP),在该问题中,有一个有向图表示网络,其中包含一些节点和边,每条边都有一个容量和一个单位费用。网络中有供应点,需求点,中转点等,最小成本网络流问题的目标是找到一种流量分配方案,使得满足需求的同时,总运输成本最小。

2.2 供应链规划案例

参考gurobi官方资源Supply Network Design 1

 供应链网络设计问题可以转化为最小成本网络流问题,具体而言,有6个客户点,4个仓库中心,2个工厂,每个客户点都有已知的需求,客户的需求可以通过仓库或者工厂提供,每个仓库有最大容量限制,每个工厂有最大供应量,已知将产品从工厂运输到仓库、从仓库运输到客户、或从工厂直接运输到客户的成本,要求找到确定满足客户需求的最佳运输方式,同时最大限度地降低运输成本。模型如下:

模型核心代码如下:

"""
(1)决策变量和目标函数
"""
cost_flow = gp.Model()
flow = cost_flow.addVars(list(edges), vtype=GRB.CONTINUOUS, name='x')
cost_flow.setObjective(flow.prod(edges), GRB.MINIMIZE)
"""
(2)约束条件
"""
# factory constraints
cost_flow.addConstrs(flow.sum(i, '*') <= factories[i] for i in factories.keys())
# depots constraints
cost_flow.addConstrs(flow.sum(i, '*') <= depots[i] for i in depots.keys())
# customers constraints
cost_flow.addConstrs(flow.sum('*', i) == customers[i] for i in customers.keys())
# flow constraints
cost_flow.addConstrs(flow.sum('*', i) == flow.sum(i, '*') for i in depots.keys())

求解结果如下: 

Optimal objective  1.985000000e+05

3.多商品网络流问题

3.1 问题描述及模型

多商品流动问题(Multi-commodity flow problem MCFP)是不同源节点和汇节点之间存在多种商品(流动需求)的网络流动问题。模型如下:

3.2 Gurobi测试

 参考multi-commodity-flow

在一个简单的例子上测试,2种商品,5个城市,模型核心代码如下:

"""
(1)变量和目标
"""
multi_commodity = gp.Model()
flow = multi_commodity.addVars(list(cost), vtype=GRB.CONTINUOUS)
multi_commodity.setObjective(flow.prod(cost), GRB.MINIMIZE)
"""
(2)约束条件
"""
# 容量约束
multi_commodity.addConstrs(flow.sum('*', u, v) <= edges[(u, v)] for u, v in edges.keys())
# 流平衡约束
multi_commodity.addConstrs(flow.sum(h, '*', v) + inflow[h, v] == flow.sum(h, v, '*')for h in commodities for v in points.keys())

求解结果如下:

Optimal objective  5.500000000e+03

这篇关于网络流问题求解及Gurobi+Python代码(最大流/最小成本网络流/多商品网络流)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/689976

相关文章

Python中pywin32 常用窗口操作的实现

《Python中pywin32常用窗口操作的实现》本文主要介绍了Python中pywin32常用窗口操作的实现,pywin32主要的作用是供Python开发者快速调用WindowsAPI的一个... 目录获取窗口句柄获取最前端窗口句柄获取指定坐标处的窗口根据窗口的完整标题匹配获取句柄根据窗口的类别匹配获取句

利用Python打造一个Excel记账模板

《利用Python打造一个Excel记账模板》这篇文章主要为大家详细介绍了如何使用Python打造一个超实用的Excel记账模板,可以帮助大家高效管理财务,迈向财富自由之路,感兴趣的小伙伴快跟随小编一... 目录设置预算百分比超支标红预警记账模板功能介绍基础记账预算管理可视化分析摸鱼时间理财法碎片时间利用财

MyBatis模糊查询报错:ParserException: not supported.pos 问题解决

《MyBatis模糊查询报错:ParserException:notsupported.pos问题解决》本文主要介绍了MyBatis模糊查询报错:ParserException:notsuppo... 目录问题描述问题根源错误SQL解析逻辑深层原因分析三种解决方案方案一:使用CONCAT函数(推荐)方案二:

Python中的Walrus运算符分析示例详解

《Python中的Walrus运算符分析示例详解》Python中的Walrus运算符(:=)是Python3.8引入的一个新特性,允许在表达式中同时赋值和返回值,它的核心作用是减少重复计算,提升代码简... 目录1. 在循环中避免重复计算2. 在条件判断中同时赋值变量3. 在列表推导式或字典推导式中简化逻辑

python处理带有时区的日期和时间数据

《python处理带有时区的日期和时间数据》这篇文章主要为大家详细介绍了如何在Python中使用pytz库处理时区信息,包括获取当前UTC时间,转换为特定时区等,有需要的小伙伴可以参考一下... 目录时区基本信息python datetime使用timezonepandas处理时区数据知识延展时区基本信息

Python位移操作和位运算的实现示例

《Python位移操作和位运算的实现示例》本文主要介绍了Python位移操作和位运算的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 位移操作1.1 左移操作 (<<)1.2 右移操作 (>>)注意事项:2. 位运算2.1

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

使用Python和Pyecharts创建交互式地图

《使用Python和Pyecharts创建交互式地图》在数据可视化领域,创建交互式地图是一种强大的方式,可以使受众能够以引人入胜且信息丰富的方式探索地理数据,下面我们看看如何使用Python和Pyec... 目录简介Pyecharts 简介创建上海地图代码说明运行结果总结简介在数据可视化领域,创建交互式地

Redis 热 key 和大 key 问题小结

《Redis热key和大key问题小结》:本文主要介绍Redis热key和大key问题小结,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、什么是 Redis 热 key?热 key(Hot Key)定义: 热 key 常见表现:热 key 的风险:二、

利用python实现对excel文件进行加密

《利用python实现对excel文件进行加密》由于文件内容的私密性,需要对Excel文件进行加密,保护文件以免给第三方看到,本文将以Python语言为例,和大家讲讲如何对Excel文件进行加密,感兴... 目录前言方法一:使用pywin32库(仅限Windows)方法二:使用msoffcrypto-too