初等数学方法建模
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?xij?uij,?(i,j)?A。
定义 在流网络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
?v,i?s?s.t. ?xij??xji???v,i?t ， （4）
j:(i,j)?Aj:(j,i)?A?0,i?s,t? 0?xij?uij,?(i,j)?A. （5）
36
初等数学方法建模
定义 如果一个矩阵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）用一条容量为
?的弧把x连接到X中的每个顶点。
（iii）用一条容量为?的弧把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)的流。反之，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的弧集，称
C(S,S)?(i,j)?Ai?S,j?S?uij
为割(S,S)的容量。
定理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的可增广轨。
37
初等数学方法建模
令
?uij?fij,当（i,j)为前向弧， ?ij??当（i,j)为后向弧?fij,??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标号。
?in{fyx,?x}，则给y标号为(x?,?y)，若fyx?0，则不给y标② (y,x)?A，且fyx?0，令?y?m号。
（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))
38
初等数学方法建模
该节点在可能的增广路中的前一个节点pred(j)，以及沿该可能的增广路到该节点为止可以增广的最大流量
maxf(j)。
STEP0 置初始可行流x（如零流）；对节点t标号，即令maxf(t)=任意正值（如1）。 STEP1 若maxf(j)?0，继续下一步；否则停止，已经得到最大流，结束。 STEP2 取消所有节点j?V的标号，即令maxf(j)?0，
pred(j)?0；令LIST={s}，对节点s标号，即令maxf(s)?充分大的正值。
STEP3 如果LIST??且maxf(t)?0，继续下一步；否则：（3a）如果t已经有标号（即maxf(t)?0），则找到了一条增广路，沿该增广路对流x进行增广（增广的流量为maxf(t)，增广路可以根据pred回溯方便地得到），转STEP1。
（3b）如果t没有标号（即LIST=?且maxf(t)?0），转STEP1。
STEP4 从LIST中移走一个节点i；寻找从节点i出发的所有可能的增广弧：（4a）对非饱和前向弧，对j进行标号，即令 (i,j)，若节点j没有标号（即pred(j)?0）
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;
39
初等数学方法建模
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=zeros(1:n);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(find(pred(label1)==0)))=flag;
maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1));
record=union(record,label1); label2=find(f(:,flag)~=0); label2=label2';
label2=setdiff(label2,record); list=union(list,label2);
pred(label2(find(pred(label2)==0)))=-flag; maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2); end
if maxf(n)>0 v2=n;
v1=pred(v2); while v2~=1 if v1>0
f(v1,v2)=f(v1,v2)+maxf(n); else
v1=abs(v1);
f(v2,v1)=f(v2,v1)-maxf(n); end v2=v1;
v1=pred(v2); end end end f
40
初等数学方法建模
§8 最小费用流及其求法
8.1 最小费用流
上面我们介绍了一个网络上最短路以及最大流的算法，但是还没有考虑到网络上流的费用问题，在许多实际问题中，费用的因素很重要。例如，在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案。这就是下面要介绍的最小费用流问题。
在运输网络N?(s,t,V,A,U)中，设cij是定义在A上的非负函数，它表示通过弧(i,j)单位流的费用。所谓最小费用流问题就是从发点到收点怎样以最小费用输送一已知量为v(f)的总流量。
最小费用流问题可以用如下的线性规划问题描述：
min(i,j)?A?cijijf
?v(f),i?s?fji???v(f),i?t ，
?0,i?s,t?s.t.
ijj:(i,j)?A?f?j:(j,i)?A? 0?fij?uij,?(i,j)?A.
显然，如果v(f)?最大流v(fmax)，则本问题就是最小费用最大流问题。如果v(f)?v(fmax)，则本问题无解。
8.2 求最小费用流的一种方法—迭代法
这里所介绍的求最小费用流的方法叫做迭代法。这个方法是由Busacker和Gowan在1961年提出的。其主要步骤如下：
(i)求出从发点到收点的最小费用通路?(s,t)。 (ii)对该通路?(s,t)分配最大可能的流量：
f?min{uij}
(i,j)??(s,t)并让通路上的所有边的容量相应减少f。这时，对于通路上的饱和边，其单位流费用相应改为?。
(iii)作该通路?(s,t)上所有边(i,j)的反向边(j,i)。令
uji?f，cji??cij
(iv)在这样构成的新网络中，重复上述步骤(i)，(ii)，(iii)，直到从发点到收点的全部流量等于v(f)为止（或者再也找不到从s到t的最小费用道路）。
41