首页 > 编程语言 >图与网络——最小费用最大流Python实现

图与网络——最小费用最大流Python实现

时间:2023-04-23 12:11:55浏览次数:56  
标签:费用 capacity weight Python 最小 网络 ij

最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下,此类问题的研究试图寻找出:流量从A到B,如何选择路径、分配经过路径的流量,可以在流量最大的前提下,达到所用的费用最小的要求。如n辆卡车要运送物品,从A地到B地。由于每条路段都有不同的路费要缴纳,每条路能容纳的车的数量有限制,最小费用最大流问题指如何分配卡车的出发路径可以达到费用最低,物品又能全部送到。

一、最小费用最大流问题

容量网络:图$D=(V,A,C) $

  • \(V\):点集。其中 \(v_s\)为发点,只有发出的弧;\(v_t\)为收点,该点只有进入的弧;其余的点为中间点;
  • \(A\): 弧集。对于每一条弧 \((v_i,v_j) \in A\)
  • \(C\):容量集。每一条弧的容量$c(v_i,v_j)>=0 $(或简记为 \(c_{ij}\)),其中\(C=\{c_{ij}\}\)
  • \(f:\) ${f_{ij}}={f(v_i,v_j)} $:弧 \((v_i,v_j)\)上的流量

可行流:

  • 容量限制条件:$0\leq f_{ij} \leq _{ij} $​
  • 平衡条件:中间点:流出量 = 流入量   $$\sum_{j:\left(v_{i}, v_{j}\right) \in A} f_{i j}-\sum_{k:\left(v_{k}, v_{i}\right) \in A} f_{k i}=0$$
    发点:

\[\sum_{j:\left(v_{s}, v_{j}\right) \in A} f_{s j}=v \]

收点:

\[\sum_{k_{:} (v_{k}, v_{t}) \in A} f_{k t}=v \]

式中:\(v\)称为这个可行流的流量,即发点的净输出量。

可行流的费用:设每条弧单位流量的费用记为\(b_{ij}\),可行流\(f\)费用为

\[b(f) = \sum \limits_{(v_i,v_j)} b_{ij} f_{ij} \]

最小费用最大流问题就是在网络中求一个最大流\(f\),使流的总输送费用\(b(f)\)最小。
增流网络: 设\(f\)是网络 $D=(V,A,C,F,B) $的一个网络流,按照以下规则构建一个新的网络 \(D_{f}=(V,A^{'},C^{'},B^{'})\),该网络称为伴随\(f\)的增流网络,其中\(V\)为顶点集,\(A\)为弧集,\(C\)为容量集,\(F\)为流量集,\(B\)为费用集。

  • 顶点:网络\(D_{f}\)与\(D\) 的顶点与网络的顶点相同;

  • 弧与权:

    • 在\(D\)中的弧\((v_i,v_j)\)若为零流弧,即\(f_{ij}=0\),则在\(D_{f}\)中构建一条同向的弧,\(c_{ij}^{'}=c_{ij}-f_{ij}\),\(b_{ij}^{'}=b_{ij}\)
    • 在D中的弧\((v_i,v_j)\)若为饱和弧,即 \(f_{ij}=c_{ij}\),则在\(D_{f}\)中构建一条反向的弧\(c_{ij}^{'}=\_{ij}\), \(b_{ij}^{'}=-b_{ij}\)
    • 在D中的弧\((v_i,v_j)\)若为非饱和弧,即\(f_{ij}<c_{ij}\),则在\(D_{f}\)中分别构建一条同向的弧和一条反向的弧,同向的弧 \(c_{ij}^{'}=c_{ij}-f_{ij}\), \(b_{ij}^{'}=b_{ij}\);反向的弧 \(c_{ij}^{'}=f_{ij}\), $b_{ij}^{'}=-b_{ij} $
  • 负回路:在增流网络\(D_{f}\)​中,所有的权(费用)之和小于零的回路称为负回路。

  • 增流圈:在增流网络 \(D_{f}\)​中的负回路对应网络\(D\)中的一个圈,在这个圈中,如果方向与这个负回路方向相同的所有弧都为不饱和弧,方向与负回路方向相反的所有弧都为非零流弧,则这个圈称为增流圈。

最大流问题的线性规划模型:

\[\begin{aligned} & \max v \\ & \text { s.t. }\left\{\begin{array}{l} \sum_{j:\left(v_i, v_j\right) \in A} f_{i j}-\sum_{j:\left(v_j, v_i\right) \in A} f_{j i}= \begin{cases}v, & i=s \\ -v, & i=t \\ 0, & i \neq s, t\end{cases} \\ 0 \leqslant f_{i j}, \forall\left(v_i, v_j\right) \in A \end{array}\right. \end{aligned} \]

最小费用最大流问题的数学模型:

\[\begin{aligned} & \min \sum_{\left(v_i, v_j\right) \in A} b_{i j} f_{ij} \\ & \text { s.t. }\left\{\begin{array}{l} \sum_{j:\left(v_i, v_j\right) \in A} f_{i j}-\sum_{j:\left(v_j, v_i\right) \in A} f_{j i}= \begin{cases}v, & i=s \\ -v, & i=t \\ 0, & i \neq s, t\end{cases} \\ 0 \leqslant f_{i j}, \forall\left(v_i, v_j\right) \in A \\ f是最大可行流 \end{array}\right. \end{aligned} \]

二、最小费用最大流的算法

在这里插入图片描述

2.1 求得最大流量调整流量达到最小费用

利用最大流算法,将网络的流量调整到最大流
构建伴随网络流\(f\)的增流网络\(D_f\)​
在增流网络\(D_f\) 中,查找关于费用的负回路,令\(\theta = \min \{c_{ij}^{'}\}\),(\(c_{ij}^{'}\)为负回路中各弧的容量),若不存在负回路,则说明当前网络流已经是最小费用流,结束算法。
针对负回路对应网络\(D\)中的圈,若该圈是增流圈,则把增流圈方向上与负回路方向一致的所有弧的流量加上\(\theta\),把增流圈方向上与负回路方向相反的所有弧的流量减去\(\theta\);若该圈不是增流圈,则转到步骤3重新寻找负回路。

2.2 寻找最小费用增广链达到最大流量

从网络\(D\)的零流\(f\)开始,构建伴随网络流\(f\)的增流网络\(D_f\)(此处\(D_f\) 中的权只需要费用\(c_{ij}^{'}\)​)
在增流网络\(D_{f}\)中用最短路径算法寻找从源到汇的最短路径,则该最短路径即对应网络\(D\)中的一条最小费用增广链;若找不到从源到汇的最短路,说明已经得到最大流,结束算法
在网络\(D\)中调整流量。前向弧上令\(\theta_{j}=c_{ij}-f_{ij}\),后向弧上令 \(\theta_{j}=f_{ij}\)​ ,调整量 $$ \theta =\min {\theta_j}$$
重复步前面骤,直到在增流网络\(D_{f}\) 中找不到从源到汇的最短路

三、最小费用最大流Pyhton程序

案例:给出下图网络的最小费用最大流(Minimum Cost Maximum Flow,MCMF)。

import numpy as np
import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
import networkx as nx  # 导入 NetworkX 工具包

# 3. 最小费用最大流问题(Minimum Cost Maximum Flow,MCMF)
# 创建有向图
G3 = nx.DiGraph()  # 创建一个有向图 DiGraph
G3.add_edges_from([('s','v1',{'capacity': 13, 'weight': 7}),
                  ('s','v2',{'capacity': 9, 'weight': 9}),
                  ('v1','v3',{'capacity': 6, 'weight': 6}),
                  ('v1','v4',{'capacity': 5, 'weight': 5}),
                  ('v2','v1',{'capacity': 4, 'weight': 4}),
                  ('v2','v3',{'capacity': 5, 'weight': 2}),
                  ('v2','v5',{'capacity': 5, 'weight': 5}),
                  ('v3','v4',{'capacity': 5, 'weight': 2}),
                  ('v3','v5',{'capacity': 4, 'weight': 1}),
                  ('v3','t',{'capacity': 4, 'weight': 4}),
                  ('v4','t', {'capacity': 9, 'weight': 7}),
                  ('v5','t',{'capacity': 9, 'weight': 5})]) # 添加边的属性 'capacity', 'weight'

# 求最小费用最大流
minCostFlow = nx.max_flow_min_cost(G3, 's', 't')  # 求最小费用最大流
minCost = nx.cost_of_flow(G3, minCostFlow)  # 求最小费用的值
maxFlow = sum(minCostFlow['s'][j] for j in minCostFlow['s'].keys())  # 求最大流量的值

# # 数据格式转换
edgeLabel1 = nx.get_edge_attributes(G3,'capacity')  # 整理边的标签,用于绘图显示
edgeLabel2 = nx.get_edge_attributes(G3,'weight')
edgeLabel={}
for i in edgeLabel1.keys():
    edgeLabel[i]=f'({edgeLabel1[i]:},{edgeLabel2[i]:})'  # 边的(容量,成本)
edgeLists = []
for i in minCostFlow.keys():
    for j in minCostFlow[i].keys():
        edgeLabel[(i, j)] += ',f=' + str(minCostFlow[i][j])  # 将边的实际流量添加到 边的标签
        if minCostFlow[i][j]>0:
            edgeLists.append((i,j))

print("最小费用最大流的路径及流量: ", minCostFlow)  # 输出最大流的途径和各路径上的流量
print("最小费用最大流的路径:", edgeLists)  # 输出最小费用最大流的途径
print("最大流量: ", maxFlow)  # 输出最大流量的值
print("最小费用: ", minCost)  # 输出最小费用的值
最小费用最大流的路径及流量:  {'s': {'v1': 11, 'v2': 9}, 'v1': {'v3': 6, 'v4': 5}, 'v2': {'v1': 0, 'v3': 4, 'v5': 5}, 'v3': {'v4': 2, 'v5': 4, 't': 4}, 'v4': {'t': 7}, 'v5': {'t': 9}, 't': {}}
最小费用最大流的路径: [('s', 'v1'), ('s', 'v2'), ('v1', 'v3'), ('v1', 'v4'), ('v2', 'v3'), ('v2', 'v5'), ('v3', 'v4'), ('v3', 'v5'), ('v3', 't'), ('v4', 't'), ('v5', 't')]
最大流量:  20
最小费用:  370

参考文献

  1. 网络流——最大流和最小费用流
  2. 最小费用最大流问题详解
  3. Python小白的数学建模课-19.网络流优化问题

标签:费用,capacity,weight,Python,最小,网络,ij
From: https://www.cnblogs.com/haohai9309/p/17345697.html

相关文章

  • python--多线程:锁 、全局锁、Queue队列以及线程池
    关于如何加锁,获取钥匙,释放锁:lock=threading.Lock():生成锁对象,全局唯一;lock.acquire():获取锁。未获取到会阻塞程序,直到获取到锁才会往下执行;lock.release():释放锁,归回后,其他人也可以调用;【注意事项】:lock.acquire()和lock.release()必须成对出现,否则就有可能造成......
  • 如何在交互式环境中执行Python程序
    相信接触过Python的小伙伴们都知道运行Python脚本程序的方式有多种,目前主要的方式有:交互式环境运行、命令行窗口运行、开发工具上运行等,其中在不同的操作平台上还互不相同。今天,小编讲些Python基础的内容,以Windows下交互式环境为依托,演示Python程序的运行。一般来说,顺利安装Python......
  • 手把手教你使用Python网络爬虫获取菜谱信息
    今日鸡汤一腔热血勤珍重,洒去犹能化碧涛。/1前言/    在放假时,经常想尝试一下自己做饭,下厨房这个网址是个不错的选择。    下厨房是必选的网址之一,主要提供各种美食做法以及烹饪技巧。包含种类很多。    今天教大家去爬取下厨房的菜谱,保存在world文档,方便日后制作自......
  • 手把手教你用Python打造一款批量下载视频并能可视化显示下载进度的下载器
    今日鸡汤桃之夭夭,灼灼其华。/1前言/    平时宅在家的我们最爱做的事莫过于追剧了,但是有时候了,网络原因,可能会让你无网可上。这个时候那些好看的电视剧和电影自然是无法观看了,本期我们要讲的就是怎样下载这些视频。/2项目目标/    通过Python程序对所感兴趣的视频进行批量......
  • 手把手教你使用Python生成图灵智能小伙伴,实现工作助手/闲聊功能
    /1前言/在家闲着,做个小项目,基于Python,实现一个语聊小机器人,分享给大家。项目整体比较简单,官方文档介绍的非常详细,可快速上手。/2 目标/将图灵机器人放到桌面,实现工作助手/陪聊功能。/3 涉及的库/V1.0版本:requests、jsonV2.0版本:requests、json、selenium(实现功能:如图灵返回结果......
  • 一篇文章带你用Python网络爬虫实现网易云音乐歌词抓取
    前几天小编给大家分享了数据可视化分析,在文尾提及了网易云音乐歌词爬取,今天小编给大家分享网易云音乐歌词爬取方法。本文的总体思路如下:找到正确的URL,获取源码;利用bs4解析源码,获取歌曲名和歌曲ID;调用网易云歌曲API,获取歌词;将歌词写入文件,并存入本地。本文的目的是获取网易云......
  • 关于python爬虫解析的问题
    在进行Python爬虫解析时,需要注意以下事项:1、良好的网站使用协议:需要遵守网站的robots.txt文件,以确保你的爬虫程序不会将网站拦截下来。2、编码问题:需要正确设置HTTP头和解析器的编码,以确保爬虫程序能够正确地解析网站的信息。3、数据解析:需要适当地处理HTML文档中的标签,以便从......
  • python变量名规则&大小写敏感
    1.变量名由英文字母、下划线_或数字组成(不能包含空格、%、-、*、/、&、^等),并且第一个字符必须是英文字母或下划线。 2.变量名不能是Python关键字。(关键字指的是Python本身“已经在使用”的名字,Python已经占用了这些名字,所以我们不能用)常见的关键字:True False None(注意......
  • Python time 库常用函数
    time模块中时间表现的格式主要有三种:timestamp时间戳,时间戳表示的是从1970年1月1日00:00:00开始按秒计算的偏移量struct_time时间元组,共有九个元素组。formattime格式化时间,已格式化的结构使时间更具可读性。包括自定义格式和固定格式。使用time库前先用import导......
  • python3-hex
    hex函数,参数可以是一个int整数或一个bytes类型元素,转为0x的十六进制字符串形式withopen(file='J:/新建文本文档.txt',mode='rb')asf:s=f.read()print(type(s),s)result=''foriins:result+=hex(i)print(result)<class'......