百木园-与人分享,
就是让自己快乐。

Python小白的数学建模课-19.网络流优化问题

  • 流在生活中十分常见,例如交通系统中的人流、车流、物流,供水管网中的水流,金融系统中的现金流,网络中的信息流。网络流优化问题是基本的网络优化问题,应用非常广泛。
  • 网络流优化问题最重要的指标是边的成本和容量限制,既要考虑成本最低,又要满足容量限制,由此产生了网络最大流问题、最小费用流问题、最小费用最大流问题。
  • 本文基于 NetworkX 工具包,通过例程详细介绍网络最大流问题、最小费用流问题、最小费用最大流问题的建模和编程。
  • 『Python小白的数学建模课 @ Youcans』带你从数模小白成为国赛达人。

1. 网络流优化

1.1 网络流

网络流优化问题是基本的网络优化问题,应用非常广泛,遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等领域。

流从源点流出、通过路径输送、流入到汇点,从而将目标从源点输送到汇点。流在生活中十分常见,例如交通系统中的人流、车流、物流,供水管网中的水流,金融系统中的现金流,网络中的信息流。

现实中的任何路径都有最大流量(容量)的限制,在网络中也是如此,并以边的容量(Capacity)表示,一条边的流量不能超过它的容量。

把这些现实问题抽象为网络流问题,其特征是:(1)有向图上的每条边具有容量限制;(2)从源点流出的流量,等于汇点流入的流量;(3)源点和汇点之外的所有中间节点,流出的流量等于流入的流量。

注意在网络流问题中有几组概念容易混淆:

  • 源点/汇点,起点/终点,供应点/需求点:源点是只进不出的点,汇点是只出不进的点。源点/汇点 可以指定为问题的 起点/终点,但本质上源点/汇点是由网络结构特征决定的,而不是被指定的。供应点的供应量和需求点的需求量是固定/确定的,而源点/汇点的目标是发出/接收的流量最大,不是固定值。
  • 容量 与 流量:容量是路径(边、弧)允许的最大流通能力,用 c(i,j) 表示;流量则是路径(边、弧)上的实际流量,用 f(i,j) 表示。

1.2 典型的网络流优化问题

网络流优化问题最重要的指标是每条边的成本和容量限制,既要考虑成本最低(最短路径问题),又要满足容量限制(最大流问题),由此产生了网络最大流问题、最小费用流问题、最小费用最大流问题。

最大流问题(Maximun flow problem):已知每条边的容量,研究如何充分利用网络能力,使从源点到汇点的总流量最大,也即在容量网络中求流量最大的可行流。

最小费用流问题(Minimum cost problem):已知每条边的容量和单位流量的费用,对于给定的源点、汇点流量,研究如何分配流量和路径,使总费用最小,也即在容量费用网络中求成本最低的可行流。

最小费用最大流问题(Minimum cost maximum flow),已知每条边的容量和单位流量的费用,研究网络的流量最大的路径中,费用最小的路径。简单地说,就是满足最大流的路径可能有多条,需要从其中找到成本最低的路径。

Network 工具包求解网络流优化,包括最大流算法、最小割算法、最小费用流算法、最小费用最大流算法、容量缩放最小成本流算法。

2. 网络最大流问题(MFP)

2.1 网络最大流算法

网络最大流问题,是在容量网络 G(V,E) 中求流量 v(f) 达到最大的可行流 f。在最大流问题中,只能有一个源点和一个汇点。

求解网络最大流主要有增广路法和预流推进法两类方法。

增广路方法从一条可行流开始,用 BFS 或 DFS 从源到汇找到一条增广路,沿着该路径修改流量,不断重复这个过程,直到找不到增广路时停止,此时的流就是最大流。增广路方法有多种的实现算法,如 Ford Fulkerson 标号法的算法复杂度为 \\(O(E f)\\)(不稳定),Edmonds Karp 算法的复杂度为 \\(O(V E^2)\\),Dinic 算法的复杂度为 \\(O(V^2 E)\\),ISAP 算法的复杂度也是 \\(O(V^2 E)\\),但其速度是最快的。

预流推进方法也称压入与重标记方法,算法从源点开始向下推流,通过不断地寻找活结点,将流量推向以该点为起点的可推流边(压入过程);如果在该点处找不到可推流边,则将该点的高度加 1,以实现将过大的流向后推进(重标记过程)。最高标号预流推进(HLPP)算法的复杂度为 \\(O(V^2 E)\\),改进的 HLPP 算法的复杂度为 \\(O(V^2 \\sqrt{(E)})\\)

2.2 NetworkX 求解网络最大流问题

Network 工具包提供了多种求解网络最大流问题的算法和函数。其中 maximum_flow()、maximum_flow_value()、minimum_cut()、minimum_cut_value() 是集成了多种算法的通用函数,可以设置算法选项调用对应的算法;其它函数则是具体的算法实现函数。

函数
功能
maximum_flow(flowG,s,t[, capacity,...]) 计算最大流
maximum_flow_value(flowG,s,t[,...]) 计算最大的单一目标流的值
minimum_cut(flowG,s,t[, capacity,flow_func]) 计算最小割的值和节点分区
minimum_cut_value(flowG,s,t[,capacity,...]) 计算最小割的值
edmonds_karp(G,s,t[,capacity,...]) Edmonds-Karp 算法求最大流
shortest_augmenting_path(G,s,t[,...]) SAP算法求最大流
dinitz(G,s,t[,capacity,...]) Dinitz 算法求最大流
preflow_push(G,s,t[,capacity,...]) HLPP 算法求最大流
boykov_kolmogorov(G,s,t[,capacity,...]) Boykov-Kolmogorov 算法求最大流

2.3 maximum_flow() 函数说明

maximum_flow()、maximum_flow_value() 是求解网络最大流问题的通用方法,集成了多种算法可供选择。官网介绍详见:https://networkx.org/documentation/stable/reference/algorithms/flow.html 。

maximum_flow (flowG, _s, _t, capacity=\'capacity\', flow_func=None, *kwargs)
maximum_flow_value (flowG, _s, _t, capacity=\'capacity\', flow_func=None, *kwargs)

主要参数:

  • flowG(NetworkX graph):有向图,边必须带有容量属性 capacity(不能用 \'weight\' )。
  • _s (node):源点。
  • _t (node):汇点。
  • capacity (string):边的容量属性 capacity,缺省视为无限容量。
  • flow_func(function):调用算法的函数名,如:\'edmonds_karp\', \'shortest_augmenting_path\', \'dinitz\', \'preflow_push\', \'boykov_kolmogorov\'。缺省值 \'None\' ,选择 \'preflow_push\'(HLPP 算法)。

返回值:

  • flow_value(integer, float):网络最大流的流量值
  • flow_dict (dict):字典类型,网络最大流的流经路径及各路径的分配流量

注意:如果要选择指定算法,需要写成以下形式 flow_func=nx.algorithms.flow.edmonds_karp,而不是 flow_func=edmonds_karp。也可以写成:

from networkx.algorithms.flow import edmonds_karp
flowValue, flowDict = nx.maximum_flow(G1, \'s\', \'t\', flow_func=edmonds_karp)

2.4 案例:输油管网的最大流量

问题描述:

在输油管网中,通过输油管连接生产石油的油井、储存石油的油库和转运的中间泵站。各站点之间的连接及管路的容量如图(参见 2.6 程序运行结果图)所示,求从油井到油库的最大流量和具体方案。

问题分析:

这是一个网络最大流问题,可以用顶点表示油井、油库和泵站,其中油井为源点 s、油库为汇点 t,用有向边表示输油管,有向边的权 capacity 表示输油管的最大流量(容量)。

用 NetworkX 的 maximum_flow() 函数即可求出从从源点 s 到汇点 t 的最大流量。

程序说明:

  • 图的输入。本例为稀疏有向图,使用 nx.DiGraph() 定义一个有向图。通过 add_edge(\'s\', \'a\', capacity=6) 定义有向边和属性 capacity。注意必须以关键字 \'capacity\' 表示容量,不能用权值 \'weight\' 或其它关键字代替。

  • nx.maximum_flow_value() 返回网络最大流的值,nx.maximum_flow() 可以同时返回网络最大流的值和网络最大流的路径及分配的流量。

  • maxFlowDict 为字典类型,具体格式参加 2.6 程序运行结果。为了得到最大流所流经的边的列表edgeLists,要对 maxFlowDict 进行整理和格式转换。

  • 在网络最大流图中,以边的标签显示了边的容量 c 和流量 f。

  • 2.5 Python 例程

    # mathmodel19_v1.py
    # Demo19 of mathematical modeling algorithm
    # Demo of network flow problem optimization with NetworkX
    # Copyright 2021 YouCans, XUPT
    # Crated:2021-07-15

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

    # 1. 最大流问题 (Maximum Flow Problem,MFP)
    # 创建有向图
    G1 = nx.DiGraph() # 创建一个有向图 DiGraph
    G1.add_edge(\'s\', \'a\', capacity=6) # 添加边的属性 \"capacity\"
    G1.add_edge(\'s\', \'c\', capacity=8)
    G1.add_edge(\'a\', \'b\', capacity=3)
    G1.add_edge(\'a\', \'d\', capacity=3)
    G1.add_edge(\'b\', \'t\', capacity=10)
    G1.add_edge(\'c\', \'d\', capacity=4)
    G1.add_edge(\'c\', \'f\', capacity=4)
    G1.add_edge(\'d\', \'e\', capacity=3)
    G1.add_edge(\'d\', \'g\', capacity=6)
    G1.add_edge(\'e\', \'b\', capacity=7)
    G1.add_edge(\'e\', \'j\', capacity=4)
    G1.add_edge(\'f\', \'h\', capacity=4)
    G1.add_edge(\'g\', \'e\', capacity=7)
    G1.add_edge(\'h\', \'g\', capacity=1)
    G1.add_edge(\'h\', \'i\', capacity=3)
    G1.add_edge(\'i\', \'j\', capacity=3)
    G1.add_edge(\'j\', \'t\', capacity=5)

    # 求网络最大流
    # maxFlowValue = nx.maximum_flow_value(G1, \'s\', \'t\') # 求网络最大流的值
    # maxFlowValue, maxFlowDict = nx.maximum_flow(G1, \'s\', \'t\') # 求网络最大流
    from networkx.algorithms.flow import edmonds_karp # 导入 edmonds_karp 算法函数
    maxFlowValue, maxFlowDict = nx.maximum_flow(G1, \'s\', \'t\', flow_func=edmonds_karp) # 求网络最大流

    # 数据格式转换
    edgeCapacity = nx.get_edge_attributes(G1, \'capacity\')
    edgeLabel = {} # 边的标签
    for i in edgeCapacity.keys(): # 整理边的标签,用于绘图显示
    edgeLabel[i] = f\'c={edgeCapacity[i]:}\' # 边的容量
    edgeLists = [] # 最大流的边的 list
    for i in maxFlowDict.keys():
    for j in maxFlowDict[i].keys():
    edgeLabel[(i, j)] += \',f=\' + str(maxFlowDict[i][j]) # 取出每条边流量信息存入边显示值
    if maxFlowDict[i][j] > 0: # 网络最大流的边(流量>0)
    edgeLists.append((i,j))

    # 输出显示
    print(\"最大流值: \", maxFlowValue)
    print(\"最大流的途径及流量: \", maxFlowDict) # 输出最大流的途径和各路径上的流量
    print(\"最大流的路径:\", edgeLists) # 输出最大流的途径

    # 绘制有向网络图
    fig, ax = plt.subplots(figsize=(8, 6))
    pos = {\'s\': (1, 8), \'a\': (6, 7.5), \'b\': (9, 8), \'c\': (1.5, 6), \'d\': (4, 6), \'e\': (8, 5.5), # 指定顶点绘图位置
    \'f\': (2, 4), \'g\': (5, 4), \'h\': (1, 2), \'i\': (5.5, 2.5), \'j\': (9.5, 2), \'t\': (11, 6)}
    edge_labels = nx.get_edge_attributes(G1, \'capacity\')
    ax.set_title(\"Maximum flow of petroleum network with NetworkX\") # 设置标题
    nx.draw(G1, pos, with_labels=True, node_color=\'c\', node_size=300, font_size=10) # 绘制有向图,显示顶点标签
    nx.draw_networkx_edge_labels(G1, pos, edgeLabel, font_color=\'navy\') # 显示边的标签:\'capacity\' + maxFlow
    nx.draw_networkx_edges(G1, pos, edgelist=edgeLists, edge_color=\'m\') # 设置指定边的颜色、宽度
    plt.axis(\'on\') # Youcans@XUPT
    plt.show()

    2.6 程序运行结果

    最大流值: 14
    最大流的途径及流量: {\'s\': {\'a\': 6, \'c\': 8}, \'a\': {\'b\': 3, \'d\': 3}, \'c\': {\'d\': 4, \'f\': 4}, \'b\': {\'t\': 10}, \'d\': {\'e\': 3, \'g\': 4}, \'t\': {}, \'f\': {\'h\': 4}, \'e\': {\'b\': 7, \'j\': 1}, \'g\': {\'e\': 5}, \'j\': {\'t\': 4}, \'h\': {\'g\': 1, \'i\': 3}, \'i\': {\'j\': 3}}
    最大流的路径: [(\'s\', \'a\'), (\'s\', \'c\'), (\'a\', \'b\'), (\'a\', \'d\'), (\'c\', \'d\'), (\'c\', \'f\'), (\'b\', \'t\'), (\'d\', \'e\'), (\'d\', \'g\'), (\'f\', \'h\'), (\'e\', \'b\'), (\'e\', \'j\'), (\'g\', \'e\'), (\'j\', \'t\'), (\'h\', \'g\'), (\'h\', \'i\'), (\'i\', \'j\')]

    3. 最小费用流问题(MCP)

    3.1 最小费用流问题的算法

    在实际问题中,我们总是希望在完成运输任务的同时,寻求运输费用最低的方案。最小费用流问题,就是要以最小费用从出发点(供应点)将一定的流量输送到接收点(需求点)。在最小流问题中,供应点、需求点的数量可以是一个或多个,但每个供应点的供应量和需求点的需求量是固定的。

    最小费用流问题可以用如下的线性规划问题描述

    \\[\\begin{align*}
    & min\\;Cost=\\sum_{i=1}^m\\sum_{j=1}^m w_{ij} f_{ij}\\\\
    & s.t.:\\;\\begin{cases}
    \\sum_{j=1}^m f_{ij} - \\sum_{j=1}^m f_{ji} = v_i\\\\
    \\sum_{i=1}^m v_{i} = 0\\\\
    0 \\leq f_{ij} \\leq c_{ij} \\;
    \\end{cases}
    \\end{align*}
    \\]

    来源:https://www.cnblogs.com/youcans/p/15181104.html
    图文来源于网络,如有侵权请联系删除。

    未经允许不得转载:百木园 » Python小白的数学建模课-19.网络流优化问题

    相关推荐

    • 暂无文章