数学建模——最大流问题（配合例子说明）（一）

一、最大流有关的概念

最大流是应用广泛的一类问题，例如交通运输网络中的人流、车流、物流；供水网络中的水流、金融系统中的资金流；通讯系统中的信息流。上世纪50年代Ford，Fulkerson建立的《网络流理论》是网络应用的基础。

例1

如图1所示网络为输油管道网络，vs为起点，vt为终点，v1,v2,v3,v4为中转站，边上的数字表示该管道的最大输油能力（t/h）。问如何安排各管道的输油量，才能使得从vs到vt的输油量最大。

1、容量网络的定义

设有连通图G=(V,E)，G的每一条边(vi,vj)上有非负数cij称为容量，仅有一个入次为0的点vs称为发点（源），一个出次为0的点vt称为收点（汇），其余点位中间点，这样的网络G称为容量网络，记为G=(V,E,C)。如图1所示。

2、符号设置

• Cij  边(i,j)的容量限制；
• fij  边(i,j)的实际流量；（称f={fij}为网络的一个流。）
• W  网络的总流量；

3、建立模型

3.1 每条边的容量限制

3.2 平衡条件

对中间点u，流入=流出，即

3.3 网络的总流量

称发点流量之和或汇点流量之和为网络总流量（忽略损失）。

4、网络最大流数学模型

5、计算

编写例1的Lingo计算程序，将计算结果填入表1，将数据反映如图1，得到图2.

sets:
dian/vs v1 v2 v3 v4 vt/:;
bian(dian,dian)/vs,v1 vs,v3 vs,v4 v1,v2 v1,v3 v2,v3 v2,vt v3,vt v3,v4 v4,v3 v4,vt/:c,f;
endsets
data:
c=4 3 4 2 1 2 4 2 3 2 3;
enddata
max=w;
w=@sum(bian(i,j)|j#eq#6:f(i,j));
@for(bian(i,j):f(i,j)<c(i,j));
@for(dian(k)|k#ne#1#and#k#ne#6:@sum(bian(i,k):f(i,k))=@sum(bian(k,j):f(k,j)));

表1 流量分布（不唯一）

如图2所示，称形如(vs,v4),(v4,vt),(v4,v3),(v1,v2),(v1,v3)为饱和边;其余的边都是非饱和边。

要增大网络的流量，必须对饱和边扩容！！

二、最小费用流

设G=(V,E,C)为流量网络，边(i,j)除了容量限制cij外，还有因为流量而产生的单位费用dij(dij>0)，记为G=(V,E,C,d)。这时如果不管流量大小，而只把网络流产生的费用当产目标，最优解必定是0，即各条边的实际流量为0时费用最小。研究方法必须改变为保持流量一定的情况下，使得流量产生的总费用最小。当网络流量保持最大而流量费用最小的网络流称为最小费用最大流。

例2

如图3所示网络G=(V,E,c,d)，每条边有两个数字，第一个是容量限制，第二个是流量产生的单位费用。求该网络的最小费用最大流（最大流例1求得为7）。

【符号说明】

• G=(V,E,c,d] 如图3所示网络图；
• Cij  边(i,j)的管道容量限制；
• Dij  边(i,j)的单位费用；
• Xij  边(i,j)的实际流量；
• W   网络G的总流量。

【建立模型】

（1）各条边的流量限制

（2）网络总流量

（3）网络总费用

（4）中间点的流量平衡

【数学模型】