即首先给出一个初始流,这样的流是存在的,例如零流。如果存在关于它的可增广轨 那么调整该轨上每条弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广 轨,则用同样的方法使流的值增大,继续这个过程,直到网络中不存在关于新得到流的 可增广轨为止,则该流就是所求的最大流 这种方法分为以下两个过程 A.标号过程:通过标号过程寻找一条可增广轨。 B增流过程:沿着可增广轨增加网络的流量。 这两个过程的步骤分述如下。 (A)标号过程 (i)给发点标号为(s,∞) (ⅱi)若顶点x已经标号,则对x的所有未标号的邻接顶点y按以下规则标号: ①若(x,y)∈A,且J0,令,=mmn{/m,o,},则给y标号为(x,o,),若 fx=0,则不给y标号。 (ⅲi)不断地重复步骤(ⅱ)直到收点t被标号,或不再有顶点可以标号为止。当t 被标号时,表明存在一条从s到t的可增广轨,则转向增流过程(B)。如若【点不能被 标号,且不存在其它可以标号的顶点时,表明不存在从s到t的可增广轨,算法结束, 此时所获得的流就是最大流。 (B)增流过程 (i)令=t (i)若l的标号为(v,,),则∫mn=∫m+;若l的标号为(v,o,),则 fm=f-5 (ⅲi)若u=s,把全部标号去掉,并回到标号过程(A)。否则,令=v,并回 到增流过程(ⅱ) 求网络N=(s,t,V,A,U/)中的最大流x的算法的程序设计具体步骤如下: 对每个节点j,其标号包括两部分信息 (pred(i), max io) 该节点在可能的增广路中的前一个节点pred(j),以及沿该可能的增广路到该节点为止 可以增广的最大流量maxf() STEP0置初始可行流x(如零流):对节点t标号,即令maxf()=任意正值(如 STEP1若maxf()>0,继续下一步;否则停止,已经得到最大流,结束。 STEP2取消所有节点j∈V的标号,即令maxf()=0 pred(j)=0;令LST={S},对节点S标号,即令maxf(s)=充分大的正值。 STEP3如果LIST≠Φ且maxf(t)=0,继续下一步;否则:(3a)如果t已经有 标号(即maxf(ω)>0),则找到了一条增广路,沿该增广路对流x进行增广(增广的 流量为maxf(t),增广路可以根据pred回溯方便地得到),转 STEPI。 (3b)如果t没有标号(即LIST=Φ且maxf(t)=0),转 STEPI
-64- 即首先给出一个初始流，这样的流是存在的，例如零流。如果存在关于它的可增广轨， 那么调整该轨上每条弧上的流量，就可以得到新的流。对于新的流，如果仍存在可增广 轨，则用同样的方法使流的值增大，继续这个过程，直到网络中不存在关于新得到流的 可增广轨为止，则该流就是所求的最大流。 这种方法分为以下两个过程： A.标号过程：通过标号过程寻找一条可增广轨。 B.增流过程：沿着可增广轨增加网络的流量。 这两个过程的步骤分述如下。 （A）标号过程： （i）给发点标号为 ( ,) + s 。 （ii）若顶点 x 已经标号，则对 x 的所有未标号的邻接顶点 y 按以下规则标号： ① 若 (x, y) A ，且 xy uxy f 时，令 min{ , } y xy xy x = u − f ， 则给顶点 y 标号为 ( , ) y x + ，若 xy uxy f = ，则不给顶点 y 标号。 ② ( y, x) A ，且 f yx 0 ，令 min{ , } y yx x = f ，则给 y 标号为 ( , ) y x − ，若 f yx = 0 ，则不给 y 标号。 （iii）不断地重复步骤（ii）直到收点 t 被标号，或不再有顶点可以标号为止。当 t 被标号时，表明存在一条从 s 到 t 的可增广轨，则转向增流过程（B）。如若 t 点不能被 标号，且不存在其它可以标号的顶点时，表明不存在从 s 到 t 的可增广轨，算法结束， 此时所获得的流就是最大流。 （B）增流过程 （i）令 u = t 。 （ii）若 u 的标号为 t (v , + ），则 vu vu t f = f + ；若 u 的标号为 ( , ) t v − ，则 uv uv t f = f − 。 （iii）若 u = s ，把全部标号去掉，并回到标号过程（A）。否则，令 u = v ，并回 到增流过程（ii）。 求网络 N = (s,t,V, A,U) 中的最大流 x 的算法的程序设计具体步骤如下： 对每个节点 j ，其标号包括两部分信息 (pred( j),max f(j)) 该节点在可能的增广路中的前一个节点 pred( j) ，以及沿该可能的增广路到该节点为止 可以增广的最大流量 max f( j)。 STEP0 置初始可行流 x （如零流）；对节点 t 标号，即令 max f(t) =任意正值（如 1）。 STEP1 若 max f( j) 0 ，继续下一步；否则停止，已经得到最大流，结束。 STEP2 取消所有节点 j V 的标号，即令 max f( j) = 0 ， pred( j) = 0 ；令 LIST={ s }，对节点 s 标号，即令 max f(s) = 充分大的正值。 STEP3 如果 LIST 且 max f(t) = 0 ，继续下一步；否则：（3a）如果 t 已经有 标号（即 max f(t) 0 ），则找到了一条增广路，沿该增广路对流 x 进行增广（增广的 流量为 max f(t) ，增广路可以根据 pred 回溯方便地得到），转 STEP1。 （3b）如果 t 没有标号（即 LIST= 且 max f(t) = 0 ），转 STEP1
STEP4从LST中移走一个节点i;寻找从节点i出发的所有可能的增广弧:(4a) 对非饱和前向弧(i,j),若节点j没有标号(即pred()=0),对j进行标号,即令 max f()=min(max f(D), u, -x, ) pred()=i 并将j加入LST中 4b)对非空后向弧(,),若节点j没有标号(即pred()=0),对j进行标号, 即令 max f()=mn(max fO), x,, pred() 并将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(4,3)=1;f(4,5)=0; n=leng th(u)i 1ist=[]; max f=zeros(l: n)i maxf(n)=li while maxf(n)>0 maxf=zeros(l, n)ipred=zeros(l, n) list=l;record=list maxf(1)=M; while (isempty(list))&(maxf(n)==0) f1ag=1ist(1);1ist(1)=[] indexl=(find(u(flag,: )x=0))i labell=index (find(u(flag, index1 f(flag, index 1)*=0)) labell=setdiff(labell, record) list=union(list labell pred(labell(find(pred(labell)==0)))=flag axf(labell)=min(maxf(flag),u(flag, labell) -f(flag, label1))i record=union(record, labell)i label2=find(f(:, flag)v=0)i label2=labe 12
-65- STEP4 从 LIST 中移走一个节点 i ；寻找从节点 i 出发的所有可能的增广弧：（4a） 对非饱和前向弧 (i, j) ，若节点 j 没有标号（即 pred( j) = 0 ），对 j 进行标号，即令 max f( ) min{max f( ), } ij ij j = i u − x ， pred( j) = i ， 并将 j 加入 LIST 中。 （4b）对非空后向弧 ( j,i) ，若节点 j 没有标号（即 pred( j) = 0 ），对 j 进行标号， 即令 max f( ) min{max f( ), }ij j = i x ， 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=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, labe 12)i pred(label2(find(pred(labe12)==0)))=-flagi maxf(label2 )=min(maxf(flag), f(label2, flag))i record=union(re cord, label2) end if maxf(n)>0 pred(v2)i if v1>0 f(vl, v2)=f(vl, v2)+maxf(n) vl=abs(v1) f(v2,v1)=f(v2, v1)-maxf(n)i end v2=v1 l=pred (v2) end end end §8最小费用流及其求法 最小费用流 上面我们介绍了一个网络上最短路以及最大流的算法,但是还没有考虑到网络上流 的费用问题,在许多实际问题中,费用的因素很重要。例如,在运输问题中,人们总是 希望在完成运输任务的同时,寻求一个使总的运输费用最小的运输方案。这就是下面要 介绍的最小费用流问题。 在运输网络N=(s,yV,A,U)中,设c是定义在A上的非负函数,它表示通过弧 ,j)单位流的费用。所谓最小费用流问题就是从发点到收点怎样以最小费用输送一已 知量为v(f)的总流量 最小费用流问题可以用如下的线性规划问题描述: min vO, i=s St ∑G-∑f={-v),i=t, j(,∈A(j,∈A 0.i≠S,t 0≤f≤4n,V(,)∈A 显然,如果v(∫)=最大流ν(~mx),则本问题就是最小费用最大流问题。如果 v()>(/m),则本问题无解 82求最小费用流的一种方法一迭代法 这里所介绍的求最小费用流的方法叫做迭代法。这个方法是由 Busacker和 Gowan 在1961年提出的。其主要步骤如下
-66- 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 §8 最小费用流及其求法 8.1 最小费用流 上面我们介绍了一个网络上最短路以及最大流的算法，但是还没有考虑到网络上流 的费用问题，在许多实际问题中，费用的因素很重要。例如，在运输问题中，人们总是 希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案。这就是下面要 介绍的最小费用流问题。 在运输网络 N = (s,t,V, A,U) 中，设 ij c 是定义在 A 上的非负函数，它表示通过弧 (i, j) 单位流的费用。所谓最小费用流问题就是从发点到收点怎样以最小费用输送一已 知量为 v( f ) 的总流量。 最小费用流问题可以用如下的线性规划问题描述： i j A ij ij c f ( , ) min s.t. − = = − = j j i A ji j i j A ij i s t v f i t v f i s f f :( , ) :( , ) 0, , ( ), ( ), ， 0 f ij uij , (i, j) A. 显然，如果 v( f ) = 最大流 ( ) max v f ，则本问题就是最小费用最大流问题。如果 ( ) ( ) max v f v f ，则本问题无解。 8.2 求最小费用流的一种方法—迭代法 这里所介绍的求最小费用流的方法叫做迭代法。这个方法是由 Busacker 和 Gowan 在 1961 年提出的。其主要步骤如下：
(i)求出从发点到收点的最小费用通路(S,t)。 (i)对该通路山(s,1)分配最大可能的流量: f∫ (i,j)=(s) 并让通路上的所有边的容量相应减少∫。这时,对于通路上的饱和边,其单位流费用 相应改为∞。 (i)作该通路山(s,1)上所有边(i,j)的反向边(j,1)。令 C.=-C (iv)在这样构成的新网络中,重复上述步骤(i),(i),(i),直到从发点到收点的全 部流量等于v(f)为止(或者再也找不到从s到t的最小费用道路)。 习题五 1.一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要将它们运过河去, 但由于船小,他一次只能运三者之一过河。显然,不管是狼和山羊,还是山羊和卷心菜, 都不能在无人监视的情况下留在一起。问摆渡人应怎样把它们运过河去? 2.北京(Pe)、东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)各城市之间的 航线距离如下表 M P 21 57 78 70 68 Pa 21 57 36 51 61 78 51 13 由上述交通网络的数据确定最小生成树 3.某台机器可连续工作4年,也可于每年末卖掉,换一台新的。已知于各年初购 置一台新机器的价格及不同役龄机器年末的的处理价如下表所示。又新机器第一年运行 及维修费为0.3万元,使用1-3年后机器每年的运行及维修费用分别为0.8,1.5,20万 元。试确定该机器的最优更新策略,使4年内用于更换、购买及运行维修的总费用为最 省 第三年第四年 年初购置价 2.5 2.6 2.8 3.1 使用了j年的机器处理价 1.3 4.某产品从仓库运往市场销售。已知各仓库的可供量、各市场需求量及从i仓库 至j市场的路径的运输能力如下表所示(表中数字0代表无路可通),试求从仓库可运 往市场的最大流量,各市场需求能否满足? 个库 可供量 30 10 0 B 20 100 需求量 20
-67- (i)求出从发点到收点的最小费用通路 (s,t)。 (ii)对该通路 (s,t) 分配最大可能的流量： min { } ( , ) ( , ) ij i j s t f u = 并让通路上的所有边的容量相应减少 f 。这时，对于通路上的饱和边，其单位流费用 相应改为 。 (iii)作该通路 (s,t) 上所有边 (i, j) 的反向边 ( j,i) 。令 u f ji = ， ji ij c = −c (iv)在这样构成的新网络中，重复上述步骤(i)，(ii)，(iii)，直到从发点到收点的全 部流量等于 v( f ) 为止（或者再也找不到从 s 到 t 的最小费用道路）。 习 题 五 1. 一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要将它们运过河去， 但由于船小，他一次只能运三者之一过河。显然，不管是狼和山羊，还是山羊和卷心菜， 都不能在无人监视的情况下留在一起。问摆渡人应怎样把它们运过河去？ 2. 北京（Pe）、东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)各城市之间的 航线距离如下表： L M N Pa Pe T L 56 35 21 51 60 M 56 21 57 78 70 N 35 21 36 68 68 Pa 21 57 36 51 61 Pe 51 78 68 51 13 T 60 70 68 61 13 由上述交通网络的数据确定最小生成树。 3. 某台机器可连续工作 4 年，也可于每年末卖掉，换一台新的。已知于各年初购 置一台新机器的价格及不同役龄机器年末的的处理价如下表所示。又新机器第一年运行 及维修费为 0.3 万元，使用 1-3 年后机器每年的运行及维修费用分别为 0.8，1.5，2.0 万 元。试确定该机器的最优更新策略，使 4 年内用于更换、购买及运行维修的总费用为最 省。 j 第一年 第二年 第三年 第四年 年初购置价 使用了 j 年的机器处理价 2.5 2.0 2.6 1.6 2.8 1.3 3.1 1.1 4. 某产品从仓库运往市场销售。已知各仓库的可供量、各市场需求量及从 i 仓库 至 j 市场的路径的运输能力如下表所示（表中数字 0 代表无路可通），试求从仓库可运 往市场的最大流量，各市场需求能否满足？ 仓库 i 市场 j 1 2 3 4 可供量 A B C 30 0 20 10 0 10 0 10 40 40 50 5 20 20 100 需求量 20 20 60 20
5.某单位招收懂俄、英、日、德、法文的翻译各一人,有5人应聘。已知乙懂俄 文,甲、乙、丙、丁懂英文,甲、丙、丁懂日文,乙、戊懂德文,戊懂法文,问这 个人是否都能得到聘书?最多几个得到聘书,招聘后每人从事哪一方面翻译工作? 6.下表给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用最 大流问题,画出网络图并求数值解 地 产量 20 8 销量 4 6 7.求下图所示网络的最小费用最大流,弧旁数字为(cn,2) (2
-68- 5. 某单位招收懂俄、英、日、德、法文的翻译各一人，有 5 人应聘。已知乙懂俄 文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这 5 个人是否都能得到聘书？最多几个得到聘书，招聘后每人从事哪一方面翻译工作？ 6. 下表给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用最 大流问题，画出网络图并求数值解。 产量 销地 1 2 3 产量 A B 20 30 24 22 5 20 8 7 销量 4 5 6 7. 求下图所示网络的最小费用最大流，弧旁数字为 ( , ) ij uij c
