网络流问题求解及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基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

Python将博客内容html导出为Markdown格式

《Python将博客内容html导出为Markdown格式》Python将博客内容html导出为Markdown格式,通过博客url地址抓取文章,分析并提取出文章标题和内容,将内容构建成html,再转... 目录一、为什么要搞?二、准备如何搞?三、说搞咱就搞!抓取文章提取内容构建html转存markdown

Python获取中国节假日数据记录入JSON文件

《Python获取中国节假日数据记录入JSON文件》项目系统内置的日历应用为了提升用户体验,特别设置了在调休日期显示“休”的UI图标功能,那么问题是这些调休数据从哪里来呢?我尝试一种更为智能的方法:P... 目录节假日数据获取存入jsON文件节假日数据读取封装完整代码项目系统内置的日历应用为了提升用户体验,

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Python Websockets库的使用指南

《PythonWebsockets库的使用指南》pythonwebsockets库是一个用于创建WebSocket服务器和客户端的Python库,它提供了一种简单的方式来实现实时通信,支持异步和同步... 目录一、WebSocket 简介二、python 的 websockets 库安装三、完整代码示例1.

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当