网络流问题的应用与推广
2021-10-14
| 2023-8-6
0  |  阅读时长 0 分钟
type
status
date
slug
summary
tags
category
icon
password
Property
流在生活中十分常见，例如交通系统中的人流、车流、物流，供水管网中的水流，金融系统中的现金流，网络中的信息流。网络流优化问题是基本的网络优化问题，应用非常广泛，遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等领域。
网络流优化问题最重要的指标是每条边的成本和容量限制，既要考虑成本最低（最短路径问题），又要满足容量限制（最大流问题），由此产生了网络最大流问题、最小费用流问题和最小费用最大流问题。
不论在实际工作中，还是在数模竞赛中，网络最大流问题、最小费用流问题和最小费用最大流问题都有很多延伸和推广的应用。
本文选择多源多汇物流转运问题、多商品流问题案例，详细介绍网络流问题的分析方法和解决方案，并使用线性规划方法建模和编程。

网络最大流问题的应用与推广

指定流量的可行流

网络最大流的算法如果不是计算最大流，而是要计算指定流量 v 的可行流，可以用如下图所示的增广路（相当于辅助线）方法处理。
（1）在容量网络 G 上增加一个顶点 t’ 和一条边 (t,t’)，构建一个新的容量网络 G’，令边 (t,t’) 的容量为 v；
（2）对于容量网络 G‘，计算从源点 s 到汇点 t’ 的最大流 ，显然 ；
（3）若 ，则容量网络 G 不存在满足流量 v 的可行流；若，则从最大流 的路径中去掉边 (t,t’) 即得到容量网络 G 满足流量 v 的可行流。
notion image
另一种思路是，设置源点 s /汇点 t 的流量为 v，再按最小费用流即可。这种方法不仅得到了流量 v 的可行流，而且是最小费用流，但该方法的计算量较大。

多源点多汇点的最大流

之前讨论的网络流优化问题，都是单源点、单汇点的网络。对于多源点单汇点、单源点多汇点、多源点多汇点的容量网络的最大流问题，可以通过如下图所示的增加一个超级源点和/或超级汇点的方法处理。
（1）在容量网络 G 上增加一个超级源点 s 和一个超级源点 t；从超级源点 s 向网络 G 中的每个源点连一条容量为 +∞ 的边，从网络 G 中的每个汇点向超级汇点 t 连一条容量为 +∞ 的边。于是得到了一个新的容量网络 G’。
2）对于容量网络 G‘，计算从超级源点 s 到超级汇点 t 的最大流 ，即为多源多汇容量网络 G 的最大流。
notion image
使用 NetworkX 工具包，也有另一种特殊方法可以解决多源多汇最大流问题。
NetworkX 中求解费用最小流问题的函数 min_cost_flow()、min_cost_flow_cost() 是求解费用最小流问题的函数，并不是设定供应点、需求点，而是通过设置顶点属性 ‘demand’ 确定供应点、需求点及各顶点的净流量，因而允许网络中存在多个供应点、需求点。
min_cost_flow(G, demand=‘demand’, capacity=‘capacity’, weight=‘weight’)
min_cost_flow_cost(G, demand=‘demand’, capacity=‘capacity’, weight=‘weight’)
因此，对于指定流量的多源多汇网络可行流问题，只要在每个源点、汇点的顶点属性 ‘demand’ 设置对应的供应量、需求量，再按最小费用流即可。这种方法不仅得到了流量 v 的可行流，而且是最小费用流。类似地，对于多源多汇网络的最大流问题，可以参考之前案例：运输费用”的方法，v 从 1 逐渐递增，计算所有流量下的最小费用流，直到达到网络容量的极限，即得到容量网络的最大费用流。该方法不需要构造新的容量网络，编程实现简单，而且可以获得最大流量的最小费用流，但计算量很大。

带顶点容量约束的最大流

标准形式的网络流优化问题，只有边的容量约束，没有顶点的容量约束。在实际问题中，顶点所表示的工厂、仓库、销售点，都存在最大储存量，因而带有顶点的容量约束。
对于顶点容量约束的网络流问题，可以通过如下图所示的将每个带约束的顶点 N 分拆为两个顶点（入顶点 Nin 和出顶点 Nout）的方法处理：
（1）将指向顶点 N 的边，改为指向入顶点 Nin；
（2）将顶点 N 所指向的边，改为出顶点 Nout 所指向的边；
（3）增加一条从入顶点 Nin 指向出顶点 Nout 的边，边的容量为顶点 N 的容量，单位费用为 0。
于是得到了一个新的容量网络 G’。由此，原有网络 G 的顶点 N 的容量限制，转化为网络 G’ 的边 (Nin,Nout) 的容量限制。带顶点约束的容量网络 G 的最大流问题，转化为新的标准形式的容量网络 G’ 的最大流问题。
notion image

最小费用流问题的应用与推广

运输问题

有出发地（供应点、供应量）和目的地（需求点、需求量），没有转运点，没有路段（边）的容量限制，目标是总运输成本最小或总利润最大。

指派问题

出发地（供应点、供应量=1）是人，目的地（需求点、需求量=1）是任务，没有转运点，没有路段（边）的容量限制，目标是总指派成本最小或总利润最大。

转运问题

有出发地（供应点、供应量）和目的地（需求点、需求量），有转运点，没有路段（边）的容量限制（或带有容量限制），目标是总流量费用最小或总利润最大。

最大流问题

最大流问题是特殊的最小费用流问题：有供应点、需求点、转运点，有路段（边）的容量限制，没有供应量和需求量的限制，目标是通过网络到目的地的总流量最大。

最短路问题

有供应点（供应量=1）、需求点（需求量=1）、转运点，没有路段（边）的容量限制，目标是通过网络到目的地的总距离最短。

案例：多源多汇的物流转运问题

问题描述

如图所示，某公司的工厂（供应点）位于F1、F2，仓库（中转点）位于W1、W2，零售商（需求点）位于R1、R2、R3、R4。从工厂生产的产品先送到仓库，再由仓库发到零售商。图中给出了各供应点和需求点的流量、每条发货线路的最大流量、单位流量的运输成本，要求在产销平衡的条件下，找出总运输费用最小的运输方案。
notion image

问题分析

这是一个运输路径规划问题，也是一个多源点、多汇点的最小费用流问题。
对于多源多汇的最小费用流问题，构造一个费用网络 G，网络 G 的各条边没有容量限制，单位流量的运输成本为边的权值 w。F1、F2 是网络 G 的源点（供应点），R1~R4 是汇点（需求点），W1、W2 是中间节点。F1、F2 的供应量与 R1~R4 的需求量是平衡的。因此可以用 NetworkX 的 maximum_flow() 函数求出最小费用流。
该问题也是一个典型的线性规划问题，可以用线性规划方法求解。
式中：f(i,j) 表示路段 (i,j) 的流量，w(i,j) 表示路段 (i,j) 的单位流量运输成本，S 表示源点（供应点），T 表示汇点（需求点）。
对于上式描述的线性规划问题，可以用 PuLP工具包求解，编程步骤如下：
（1） 导入 PuLP库函数； （2） 定义一个线性规划问题； （3）定义决策变量，决策变量的上下限：
（4）定义目标函数：
（5）定义约束条件：
注意，f11+f12<=600, f21+f22<=400，意味着允许存在产销不平衡的情况。
（6）求解规划问题，输出优化结果
notion image
 
 
 

案例：多商品流问题

多商品流问题（Multi-Commodity Flow Prolem）是多种商品（物流、人流、数据流等）在具有容量限制的网络中从供应点流到需求点的网络流问题，通常是 NP 问题。多商品流问题的优化目标是以最小的成本实现商品在网络中的流通，约束条件主要是每条边的容量。
多商品流路径优化问题具有广泛的实际应用，如交通运输、物流网络、电信网络以及产销系统。一些实际问题带有特殊要求，如在电信网络中要考虑时间延迟和可靠性问题，在零担货运中需要考虑配货拼车，有时需要综合考虑运输的时间和成本。

问题描述

将城市 v0 生产的商品 A、B 通过铁路网分别运送到 城市 v6、v5，商品 A、B 的需求量分别为 6.0、5.0 单位。铁路网的结构如图所示，每条线路（边）上的数值表示该线路的容量和单位运费。求完成商品运输任务的最小费用的运输方案。
notion image

问题分析

这是一个多商品流问题，具有 1 个供应点 V0 和 2个需求点 V5、V6。
对于多源多汇的多商品流最小费用流问题，构造一个费用网络 G，网络 G 的各条边具有容量限制，单位流量的运输成本为边的权值 w。源点（供应点）为流量净输出，汇点（需求点）为流量净输入；中间节点不带存储，每种商品的净流量都为 0。所有线路的商品总流量不超过边的容量限制。
该问题也是一个典型的线性规划问题，可以用如下模型描述：
式中：M 表示商品品种，S 表示源点（供应点），T 表示汇点（需求点），w(i,j) 表示路段 (i,j) 的单位流量运输成本，f(i,j,m) 表示商品 m 在路段 (i,j) 的流量，
NetworkX 工具包中没有多商品流问题的解决方法，在 Python 其它图与网络工具包也没有找到多商品流问题的函数。网络流问题本质上是线性规划问题，对于上式描述的线性规划问题，可以用 PuLP工具包求解。
多商品流的目标是各种商品从供应点运送到需求点的总费用最小。定义各商品 m 在各路段 (i,j) 的流量 f(i,j,m) 为决策变量，则目标函数为商品 m 在各路段 (i,j) 的运输费用之和 。多商品流的模型主要包含流守恒约束和容量限制。
本案例的问题中，不同商品 A、B 是从同一供应点发出，运送到不同需求点。但本案例的数学模型和例程，并不限定从不同商品从同一供应点发出，也就是说可以适用于多源多汇的多商品流问题。另外，如果如果不同商品在各条边的运费单价不同，只要相应修改例程的目标函数即可处理。

程序说明

  1. 图的输入：稀疏有向图，使用 nx.DiGraph() 定义有向图，使用G.add_weighted_edges_from() 函数以列表向图中添加多条赋权边，每个赋权边以元组 (node1,node2,{‘capacity’:c1, ‘weight’:w1}) 定义属性 ‘capacity’ 和 ‘weight’。注意必须以关键字 ‘capacity’ 表示容量，以 ‘weight’ 表示单位流量的成本。
  1. supplyA、supplyB 表示商品 A、B 的供应量，来自题目要求。注意网络的最大流量必须大于等于各种商品的总供应量或总需求量，否则将没有可行解。
  1. 绘制网络图，以边的标签显示边的容量 ‘capacity’ 和单位流量的成本 ‘weight’ 。
  1. 用 PuLP 求解多商品流线性规划问题：
（1） 定义一个线性规划问题 MCFproblem。 （2）定义决策变量 fA、fB ，并设置决策变量类型和上下限：
  • fA、fB 都是一维数组，表示商品 A、B 在网络 G2 各条边的实际流量。根据题意将决策变量设为连续变量，如果问题要求整车配货等条件，可以相应地设为整数变量。
  • fA、fB 的下限为 0，上限应为各条边的容量。但由于 pulp.LpVariable.dicts 函数中定义上限 upBound 为实数类型，不能是数组，无法对每个决策变量设定不同的上限值。
  • 因此，在定义决策变量 fA、fB 时，将上限设为所有边的容量的最大值 maxCapacity。每条边的具体容量约束，则作为约束条件处理。
  • G2.edges() 表示遍历网络 G2 的边，因此 fA、fB 是 A、B 在所有边 edges 的流量：
（3）定义目标函数：
目标函数是 A、B 在所有边 edges 的总运费，即流量 fA、fB 与单位流量成本 ‘weight’的乘积的总和。
需要说明的是：（1）通过 edgeWeight = nx.get_edge_attributes(G2, ‘weight’) 将所有边的属性 ‘weight’ 转换为字典类型，就可以用 for edge in G2.edges 遍历操作。（2）如果不同商品在各条边的运费单价不同，只要将目标函数修改即可。
（4）定义约束条件：
多商品流的模型主要包含边的容量约束和顶点的流守恒约束和两个方面。
  • 边的容量约束，即每条边上各种商品流量之和不大于边的容量。
  • 顶点的流守恒约束，分为源点（供应点）、汇点（需求点）和中间节点三种情况：
    • 通过 for node in G2.nodes 可以遍历网络的所有顶点。
    • in_degree(node) 计算顶点 node 的入度，入度为 0 的顶点是源点；out_degree(node) 计算顶点 node 的出度，出度为 0 的顶点是汇点。由此可以判断网络的源点、汇点和中间节点；也可以根据题目直接判断各中商品的供应点、需求点进行定义。
    • in_edges(nbunch=node) 返回顶点 node 的所有入边，out_edges(nbunch=node) 返回顶点 node 的所有出边。
    • 源点：对于每种商品，所有输出边的流量之和不大于该顶点该商品的供应量。对于供应量、需求量相等的问题，也可以将该约束条件设为输出流量等于供应量。
    • 汇点：对于每种商品，所有输入边的流量之和等于该顶点该商品的供应量。案例问题有多个需求点，并对应了不同品种的商品，因此需要分别进行设置。
    • 中间节点：对于每种商品，中间节点的总流入量与总流出量相等。
    • 注意，如果供应点、需求点也是流通线路而不是源点、汇点，则不必分作三种情况，都按照中间节点处理，但对每个节点需要设置每种商品的净流量。
（6）求解规划问题，输出优化结果
notion image
 
相关文章 :
数据分析
  • NetworkX
    • 网络流优化问题关键路径法
    目录