图论与网络
这两个过程的步骤分述如下。 （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)，以及沿该可能的增广路到该节点为止可以增广的最大流量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已经有标号（即maxf(t)?0），则找到了一条增广路，沿该增广路对流x进行增广（增广的流量为maxf(t)，增广路可以根据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进行标号，
-71-
即令
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); label2=find(f(:,flag)~=0); label2=label2';
label2=setdiff(label2,record); list=union(list,label2); pred(label2)=-flag;
maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2); end
if maxf(n)>0
-72-
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)中，设cij是定义在A上的非负函数，它表示通过弧
(i,j)单位流的费用。所谓最小费用流问题就是从发点到收点怎样以最小费用输送一已知量为v(f)的总流量。
最小费用流问题可以用如下的线性规划问题描述：
min(i,j)?A?cijijf
?v(f),i?s?s.t. ?fij??fji???v(f),i?t ，
j:(i,j)?Aj:(j,i)?A?0,i?s,t? 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。这时，对于通路上的饱和边，其单位流费用相应改为?。
-73-
(iii)作该通路?(s,t)上所有边(i,j)的反向边(j,i)。令
uji?f，cji??cij
(iv)在这样构成的新网络中，重复上述步骤(i)，(ii)，(iii)，直到从发点到收点的全部流量等于v(f)为止（或者再也找不到从s到t的最小费用道路）。
下面我们编写了用Floyd算法求最短路的函数floydpath和最小费用最大流函数mincostmaxflow。
最短路函数如下：
function path=floydpath(w); num=length(w);
M=sum(sum(w)).*num;
w=w+((w==0)-eye(num)).*M; p=zeros(num); for k=1:num for i=1:num for j=1:num
if w(i,j)>w(i,k)+w(k,j) w(i,j)=w(i,k)+w(k,j); p(i,j)=k; end end end end
if w(1,num)>=M path=[]; else
path=zeros(num); s=1;t=num;m=p(s,t); while ~isempty(m) if m(1)
s=[s,m(1)];t=[t,t(1)];t(1)=m(1);
m(1)=[];m=[p(s(1),t(1)),m,p(s(end),t(end))]; else
path(s(1),t(1))=1;s(1)=[];m(1)=[];t(1)=[]; end end end
最小费用最大流函数如下：
function flow=mincostmaxflow(rongliang,cost,flowvalue); %第一个参数：容量矩阵；第二个参数：费用矩阵；
%第三个参数：指定容量值（可以不写，表示求最小费用最大流） %前两个参数必须在不通路处置零，且为同维矩阵 %返回值为可行流矩阵
%必须有函数文件floydpath.m M=sum(sum(rongliang));
flow=zeros(size(rongliang));allflow=sum(flow(1,:)); if nargin<3
flowvalue=M;
-74-
end
while allflow w=(flow theta=min(min(path.*(rongliang-flow)+(path.*(rongliang-flow)==0).*M)); theta=min([min(path'.*flow+(path'.*flow==0).*M),theta]); if allflow+theta>flowvalue theta=flowvalue-allflow; end flow=flow+(rongliang>0).*(path-path').*theta; allflow=sum(flow(1,:)); end 对于习题五中的第7题，我们的调用函数如下： clear;clc; cost=[ 0 4 1 0 0; 0 0 0 6 1; 0 2 0 3 0; 0 0 0 0 2; 0 0 0 0 0; ]; rongliang=[ 0 10 8 0 0; 0 0 0 2 7 ; 0 5 0 10 0; 0 0 0 0 4; 0 0 0 0 0; ]; y=mincostmaxflow(rongliang,cost) 习 题 五 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年，也可于每年末卖掉，换一台新的。已知于各年初购 -75- 置一台新机器的价格及不同役龄机器年末的的处理价如下表所示。又新机器第一年运行及维修费为0.3万元，使用1-3年后机器每年的运行及维修费用分别为0.8，1.5，2.0万元。试确定该机器的最优更新策略，使4年内用于更换、购买及运行维修的总费用为最省。 j 第一年 第二年 第三年 第四年 年初购置价 2.5 2.6 2.8 3.1 使用了j年的机器处理价 2.0 1.6 1.3 1.1 4. 某产品从仓库运往市场销售。已知各仓库的可供量、各市场需求量及从i仓库至j市场的路径的运输能力如下表所示（表中数字0代表无路可通），试求从仓库可运往市场的最大流量，各市场需求能否满足？ 仓库i 市场j 1 2 3 4 可供量 30 10 0 40 20 A 0 0 10 50 20 B 20 10 40 5 100 C 需求量 20 20 60 20 5. 某单位招收懂俄、英、日、德、法文的翻译各一人，有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这5个人是否都能得到聘书？最多几个得到聘书，招聘后每人从事哪一方面翻译工作？ 6. 下表给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用最大流问题，画出网络图并求数值解。 1 2 3 产量 销地 产量 20 24 5 8 A 30 22 20 7 B 4 5 6 销量 7. 求下图所示网络的最小费用最大流，弧旁数字为(cij,uij)。 -76-
图与网络
