最大值为：maxz?f1(c)?14c。 64 习 题 四
1. 用Matlab编程求例5的解。
2. 有四个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表： 工作 C A B D 工人 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 问指派哪个人去完成哪项工作，可使总的消耗时间为最小？试对此问题用动态规划方法求解。
3. 为保证某一设备的正常运转，需备有三种不同的零件E1,E2,E3。若增加备用零件的数量，可提高设备正常运转的可靠性，但增加了费用，而投资额仅为8000元。已知备用零件数与它的可靠性和费用的关系如下表所示。 增加的可靠性 设备的费用（千元） 备件数 E3 E3 E2 E2 E1 E1 0.3 0.2 0.1 1 3 2 0.4 0.5 0.2 2 5 3 0.5 0.9 0.7 3 6 4 现要求在既不超出投资额的限制，又能尽量提高设备运转的可靠性的条件下，问各种零件的备件数量应是多少为好？
4. 某工厂购进100台机器，准备生产I、II两种产品，若生产产品I，每台
机器每年可收入45万元，损坏率为65％；若生产产品II，每台机器每年收入为35万元，损坏率为35％，估计三年后将有新型机器出现，旧的机器将全部淘汰。试问每年应如何安排生产，使在三年内收入最多？
这两个过程的步骤分述如下。 （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)，若
??z?1 z?2 z?3 fyx?0，则不给y标号。
（iii）不断地重复步骤（ii）直到收点t被标号，或不再有顶点可以标号为止。当t被标号时，表明存在一条从s到t的可增广轨，则转向增流过程（B）。如若t点不能被标号，且不存在其它可以标号的顶点时，表明不存在从s到t的可增广轨，算法结束，
-50-
此时所获得的流就是最大流。
（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进行标号，
即令
maxf(j)?min{maxf(i),xij}，pred(j)??i， 并将j加入LIST中。
例14 用Ford-Fulkerson算法计算如下网络中的最大流，每条弧上的两个数字分别表示容量和当前流量。
解 编写程序如下： clc,clear,M=1000;
-51-
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 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 最小费用流及其求法
-52-
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的最小费用道路）。
下面我们编写了用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
-53-
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; 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 -54-