发布时间 : 星期一 文章最大流与最小费用流更新完毕开始阅读503b621ca76e58fafab003c3
最大流与最小费用流
§7 最大流问题
7.1 最大流问题的数学描述 7.1.1 网络中的流
定义 在以V为节点集，A为弧集的有向图G?(V,A)上定义如下的权函数：
（i）L:A?R为孤上的权函数，弧(i,j)?A对应的权L(i,j)记为lij，称为孤(i,j)的容量下界（lower bound）；
（ii）U:A?R为弧上的权函数，弧(i,j)?A对应的权U(i,j)记为uij，称为孤(i,j)的容量上界，或直接称为容量（capacity）；
D:V?R为顶点上的权函数，（iii）节点i?V对应的权D(i)记为di，称为顶点i的供需量（supply／demand）；
此时所构成的网络称为流网络，可以记为
N?(V,A,L,U,D)。
由于我们只讨论V,A为有限集合的情况，所以对于弧上的权函数L,U和顶点上的权函数D，可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示，因此L,U,D有时直接称为权向量，或简称权。由于给定有向图G?(V,A)后，我们总是可以在它的弧集合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络。
在流网络中，弧(i,j)的容量下界lij和容量上界uij表示的物理意义分别是：通过该弧发送某种“物质”时，必须发送的最小数量为lij，而发送的最大数量为uij。顶点i?V对应的供需量di则表示该顶点从网络外部获得的“物质”数量（di?0时），或从该顶点发送到网络外部的“物质”数量（di?0时）。下面我们给出严格定义。
定义 对于流网络N?(V,A,L,U,D)，其上的一个流（flow）f是指从N的弧集A到R的一个函数，即对每条弧(i,j)赋予一个实数fij（称为弧(i,j)的流量）。如果流f满足
ijj:(i,j)?A?f?j:(j,i)?A?fji?di,?i?V, （1）
lij?fij?uij,?(i,j)?A， （2）
则称f为可行流（feasible flow）。至少存在一个可行流的流网络称为可行网络（feasible network）．约束（1）称为流量守恒条件（也称流量平衡条件），约束（2）称为容量约束。 可见，当di?0时，表示有di个单位的流量从网络外部流入该项点，因此顶点i称为供应点（supply node）或源（source），有时也形象地称为起始点或发点等；当di?0时，表示有|di|个单位的流量从该顶点流失到网络外部（或说被该项点吸收），因此顶点i称为需求点（demand node）或汇（sink），有时也形象地称为终止点或收点等；当di?0时，顶点i称为转运点（transshipment node）或平衡点、中间点等。此外，根据（1）可知，对于可行网络，必有
?di?Vi?0 （3）
也就是说，所有节点上的供需量之和为0是网络中存在可行流的必要条件。
一般来说，我们总是可以把L?0的流网络转化为L?0的流网络进行研究。所以，除非特别说明，以后我们总是假设L?0（即所有孤(i,j)的容量下界lij?0），并将L?0时的流网络简记为
N?(V,A,U,D)。此时，相应的容量约束（2）为 0?fij?uij,?(i,j)?A。
-51-
定义 在流网络N?(V,A,U,D)中，对于流f，如果 fij?0,?(i,j)?A，
则称f为零流，否则为非零流。如果某条弧(i,j)上的流量等于其容量（fij?uij），则称该弧为饱和弧（saturated arc）；如果某条弧(i,j)上的流量小于其容量（fij?uij），则称该弧为非饱和弧；如果某条弧(i,j)上的流量为 0（fij?0），则称该弧为空弧（void arc）。
7.1.2 最大流问题
考虑如下流网络N?(V,A,U,D)：节点s为网络中唯一的源点，t为唯一的汇点，而其它节点为转运点。如果网络中存在可行流f，此时称流f的流量（或流值，flow value）为ds（根据（3），它自然也等于?dt），通常记为v或v(f)，即
v?v(f)?ds??dt。
对这种单源单汇的网络，如果我们并不给定ds和dt（即流量不给定），则网络一般记为
N?(s,t,V,A,U)。最大流问题（maximum flow problem）就是在N?(s,t,V,A,U)中找到流值最大的
可行流（即最大流）。我们将会看到，最大流问题的许多算法也可以用来求解流量给定的网络中的可行流。也就是说，当我们解决了最大流问题以后，对于在流量给定的网络中寻找可行流的问题，通常也就可以解决了。
因此，用线性规划的方法，最大流问题可以形式地描述如下：
maxv
s.t.
j:(i,j)?A?fij?j:(j,i)?A??v,i?s?fji???v,i?t ， （4）
?0,i?s,t??(i,j)?A. （5）
定义 如果一个矩阵A的任何子方阵的行列式的值都等于0，1或?1，则称A是全幺模的(totally
unimodular TU，又译为全单位模的)，或称A是全幺模矩阵。
定理8（整流定理） 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量均为正整数，则问题的最优解为整数解。
最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。
7.1.3 单源和单汇运输网络
实际问题往往是多源多汇网络，为了计算的规格化，可将多源多汇网络G化成单源单汇网络G'。设X是G的源，Y是G的汇，具体转化方法如下：
（i）在原图G中增加两个新的顶点x和y，令为新图G'中之单源和单汇，则G中所有顶点V成为G'之中间顶点集。
（ii）用一条容量为（iii）用一条容量为
0?fij?uij,?的弧把x连接到X中的每个顶点。 ?的弧把Y中的每个顶点连接到y。
G和G'中的流以一个简单的方式相互对应。若f是G中的流，则由
若a是G的弧?f(a),?f'(a)??f?(v)?f?(v),若a?(x,v)
?f?(v)?f?(v),若a?(v,y)???所定义的函数f'是G'中使得v(f')?v(f)的流，这里f(v)表示流出v的流量，f(v)表示流入v的
流量（在G中）。反之，G'中的流在G的弧集上的限制就是G中具有相同值的流。
7.2 最大流和最小割关系
设N?(s,t,V,A,U)，S?V，s?S，t?V?S，则称(S,S)为网络的一个割，其中S?V?S，
(S,S)为尾在S，头在S的弧集，称
-52-
C(S,S)?为割(S,S)的容量。
(i,j)?Ai?S,j?S?uij
定理9 f是最大流，(S,S)是容量最小的割的充要条件是
v(f)?C(S,S)。
在网络N?(s,t,V,A,U)中，对于轨(s,v2,?,vn?1,t)（此轨为无向的），若vivi?1?A，则称它为前向弧；若vi?1vi?A，则称它为后向弧。
在网络N中，从s到t的轨P上，若对所有的前向弧(i,j)都有fij?uij，对所有的后向弧(i,j)恒
有fij?0，则称这条轨P为从s到t的关于f的可增广轨。
令
?uij?fij,当（i,j)为前向弧?ij??，
f,当（i,j)为后向弧?ij??min{?ij}
则在这条可增广轨上每条前向弧的流都可以增加一个量?，而相应的后向弧的流可减少?，这样就可
使得网络的流量获得增加，同时可以使每条弧的流量不超过它的容量，而且保持为正，也不影响其它弧的流量。总之，网络中f可增广轨的存在是有意义的，因为这意味着f不是最大流。
7.3 最大流的一种算法—标号法
标号法是由Ford和Fulkerson在1957年提出的。用标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。即首先给出一个初始流，这样的流是存在的，例如零流。如果存在关于它的可增广轨，那么调整该轨上每条弧上的流量，就可以得到新的流。对于新的流，如果仍存在可增广轨，则用同样的方法使流的值增大，继续这个过程，直到网络中不存在关于新得到流的可增广轨为止，则该流就是所求的最大流。
这种方法分为以下两个过程：
A.标号过程：通过标号过程寻找一条可增广轨。 B.增流过程：沿着可增广轨增加网络的流量。 这两个过程的步骤分述如下。 （A）标号过程：
（i）给发点标号为(s,?)。
（ii）若顶点x已经标号，则对x的所有未标号的邻接顶点y按以下规则标号： ① 若(x,y)?A，且fxy?uxy时，令?y?min{uxy?fxy,?x}， 则给顶点y标号为(x,?y)，若fxy?uxy，则不给顶点y标号。
?② (y,x)?A，且fyx?0，令?y?min{fyx,?x}，则给y标号为(x,?y)，若fyx?0，则不给
??y标号。
（iii）不断地重复步骤（ii）直到收点t被标号，或不再有顶点可以标号为止。当t被标号时，表明存在一条从s到t的可增广轨，则转向增流过程（B）。如若t点不能被标号，且不存在其它可以标号的顶点时，表明不存在从s到t的可增广轨，算法结束，此时所获得的流就是最大流。
（B）增流过程 （i）令u?t。
（ii）若u的标号为(v?,?t），则fvu?fvu??t；若u的标号为(v?,?t)，则fuv?fuv??t。 （iii）若u?s，把全部标号去掉，并回到标号过程（A）。否则，令u?v，并回到增流过程（ii）。 求网络N?(s,t,V,A,U)中的最大流x的算法的程序设计具体步骤如下： 对每个节点j，其标号包括两部分信息
(pred(j),maxf(j))
该节点在可能的增广路中的前一个节点pred(j)，以及沿该可能的增广路到该节点为止可以增广的最大
-53-
流量maxf(j)。
STEP0 置初始可行流x（如零流）；对节点t标号，即令maxf(t)=任意正值（如1）。 STEP1 若maxf(t)?0，继续下一步；否则停止，已经得到最大流，结束。 STEP2 取消所有节点j?V的标号，即令maxf(j)?0，
pred(j)?0；令LIST={s}，对节点s标号，即令maxf(s)?充分大的正值。 STEP3 如果LIST??且maxf(t)?0，继续下一步；否则：（3a）如果t已经有标号（即
，则找到了一条增广路，沿该增广路对流x进行增广（增广的流量为maxf(t)，增广路maxf(t)?0）
可以根据pred回溯方便地得到），转STEP1。
（3b）如果t没有标号（即LIST=?且maxf(t)?0），转STEP1。
STEP4 从LIST中移走一个节点i；寻找从节点i出发的所有可能的增广弧：（4a）对非饱和前向弧(i,j)，若节点j没有标号（即pred(j)?0），对j进行标号，即令
maxf(j)?min{maxf(i),uij?xij}，pred(j)?i，
并将j加入LIST中。
（4b）对非空后向弧(j,i)，若节点j没有标号（即pred(j)?0），对j进行标号，即令
maxf(j)?min{maxf(i),xij}，pred(j)??i，
并将j加入LIST中。
例14 用Ford-Fulkerson算法计算如下网络中的最大流，每条弧上的两个数字分别表示容量和当前流量。
解 编写程序如下： clc,clear,M=1000;
u(1,2)=1;u(1,3)=1;u(1,4)=2; u(2,3)=1;u(2,5)=2; u(3,5)=1;
u(4,3)=3;u(4,5)=3;
f(1,2)=1;f(1,3)=0;f(1,4)=1; f(2,3)=0;f(2,5)=1; f(3,5)=1;
f(4,3)=1;f(4,5)=0; n=length(u); list=[]; maxf(n)=1;
while maxf(n)>0
maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=M;
while (~isempty(list))&(maxf(n)==0) flag=list(1);list(1)=[];
index1=(find(u(flag,:)~=0));
label1=index1(find(u(flag,index1)... -f(flag,index1)~=0));
label1=setdiff(label1,record); list=union(list,label1); pred(label1)=flag;
maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1));
record=union(record,label1);
-54-