《小费用最大流》PPT课件.ppt
,6.5 最小费用最大流问题,6.5.1 最小费用最大流问题的数学模型,设网络D=(V,A,W),每条弧,除了容量,以,外，,还给出单位流量的费用,（简记为,）。,这样，D就成为一个带费用的网络，记为D=(V,A,W,C),其中,C称为费用函数。,设X为D上的一个可行流，称,（）,为可行流X的费用。,最小费用最大流问题，即要求一个最大流X，使总,运输费用,（）,达到最小值，,则有最小费用最大流问题的数学模型,（）,6.5.2 最小费用最大流问题的算法,寻求最大流的方法,最小费用,最小费用最大流,从某个可行流出发，找到关于这个可行流的一条增广链，沿着 该增广链调整X，对新的可行流试图寻求关于它的增广链，如此反复直至最大流,设想：,当沿着一条关于可行流X的增广链,以,调整X，,得到新的可行流,且有,这里第三个等式只是因为对,之外的,来说,即费用均一样。,记,称,是沿增广链,当可行流增加单位流值时费,用的增量，,简称为增广链,的单位费用增量。,可以证明，,若X是流量为f(X)的所有可行流中费,用最小者，,而,是关于X的所有增广链中费用最小的,增广链，,则沿,去调整X，,得到的可行流,就是流量,为,的所有可行流中的最小费用流，,这样，,当,是最大流时，,即为最小费用最大流。,注意到,故X=0必是流量为 0的最小费用,流。,这样，,总可以从X=0开始。,一般地，,若X是流量,f(X)的最小费用流，,为了寻求关于X的最小费用增,广链，,构造一个赋权有向图D(X)，,它的顶点是原网,络D的顶点，,而把D中的每一条弧,变成两个,相反方向的弧,和,定义D(X),中弧的,权,在D(X)中长度为,的弧可以略去。,故在网络D中寻找关于 X的最小费用增广链就,等价于在赋权有向图D(X)中，,寻找从,到,的最短,路。,算法步骤：,Step1:,确定初始可行流,令,Step2:,记,为经过k次调整得到的最小费用流，,构造,Step3:,求,中,到,的最短路,若,不存在，则,是最小费用最大流，算法,终止；,否则，转Step4；,Step4:,在D中找对应的增广链,按式（）调,整流量，得可行流,令,转,Step2。,例,求图的最小费用最大流，弧旁的数字,为,图,解:,取,见图（a），,图（a）,构造,因没有负权弧，,故可用Dijkstra算法求得最短路为,见图（b）。,图（b）,增广链,调整后,如图（c）。,图（c）,构造,得到,如图（d）。,图（d）,调整得,如图（e）。,图（e）,构造,如图（f）。,图（f）,显然，,与,关联的弧指向,不存在,到,的最短路。,故图（e）所示的,为最小费用,最大流。,费用,流值,三、最小费用最大流,例,用LINGO软件求解例。,解：,程序如下：,model:sets:nodes/1,2,3,4,5/:d;arcs(nodes,nodes)/1,2 1,3 2,3 2,4 3,4 3,5 4,5/:c,u,f;endsetsmin=sum(arcs:c*f);for(nodes(i)|i#ne#1#and#i#ne#size(nodes):sum(arcs(i,j):f(i,j)-sum(arcs(j,i):f(j,i)=d(i);sum(arcs(i,j)|i#eq#1:f(i,j)=d(1);for(arcs:Bnd(0,f,u);data:u=2 1 3 6 2 3 4;c=1 3 2 5 1 1 3;d=3 0 0 0-3;enddataend,运行结果：,Global optimal solution found at iteration:0 Objective value:12.00000Variable Value Reduced CostD(1)3.000000 0.000000D(2)0.000000 0.000000,D(3)0.000000 0.000000D(4)0.000000 0.000000D(5)-3.000000 0.000000C(1,2)1.000000 0.000000C(1,3)3.000000 0.000000C(2,3)2.000000 0.000000C(2,4)5.000000 0.000000C(3,4)1.000000 0.000000C(3,5)1.000000 0.000000C(4,5)3.000000 0.000000U(1,2)2.000000 0.000000U(1,3)1.000000 0.000000U(2,3)3.000000 0.000000U(2,4)6.000000 0.000000U(3,4)2.000000 0.000000,U(3,5)3.000000 0.000000U(4,5)4.000000 0.000000F(1,2)2.000000 0.000000F(1,3)1.000000 0.000000F(2,3)2.000000 0.000000F(2,4)0.000000 5.000000F(3,4)0.000000 3.000000F(3,5)3.000000 0.000000F(4,5)0.000000 0.000000,结果说明，最小费用为12，此时，流值为3。,例,用MATLAB软件求解例。,MATLAB编程如下：,解：,f=zeros(7,1);f(1)=1;f(2)=1;g=-f;aeq=1,0,-1,-1,0,0,0 0,1,0,1,-1,0,-1 0,0,1,0,1,-1,0;beq=zeros(3,1);lb=zeros(7,1);ub=2 1 6 3 2 4 3;,x,fval,exitflag,output,lambda=linprog(g,aeq,beq,lb,ub);f1=1,3,5,2,1,3,1;aq=1 1 zeros(1,5);aeq1=aq;aeq;beq1=-fval;beq;z,favl1,exitflag,output,lambda=linprog(f1,aeq1,beq1,lb,ub);zfavl1,运行结果如下：,z=2.0000 1.0000 0.0000 2.0000 0.0000 0.0000 3.0000favl1=12.0000,结果说明最大流值为3，最小费用为12。,可以看出，最小费用最大流问题其实就是在最大流问题基础上，再进行一次线性规划问题的计算得出。,最大流为：3+8=7+4=11,最小费用为：34+81+42+71+43+42=55,sets:nodes/s,1,2,3,t/:d;arcs(nodes,nodes)/s,1 s,2 2,1 2,3 1,t 1,3 3,t/:c,u,f;endsetsdata:d=11 0 0 0-11;c=4 1 2 3 1 6 2;u=10 8 5 10 7 2 4;enddatamin=sum(arcs:c*f);for(nodes(i)|i#ne#1#and#i#ne#size(nodes):sum(arcs(i,j):f(i,j)-sum(arcs(j,i):f(j,i)=d(i);sum(arcs(i,j)|i#eq#1:f(i,j)=d(1);for(arcs:bnd(0,f,u);,Global optimal solution found at iteration:2 Objective value:55.00000 Variable Value Reduced Cost D(S)11.00000 0.000000 D(1)0.000000 0.000000 D(2)0.000000 0.000000 D(3)0.000000 0.000000 D(T)-11.00000 0.000000 C(S,1)4.000000 0.000000 C(S,2)1.000000 0.000000 C(2,1)2.000000 0.000000 C(2,3)3.000000 0.000000 C(1,T)1.000000 0.000000 C(1,3)6.000000 0.000000 C(3,T)2.000000 0.000000 U(S,1)10.00000 0.000000 U(S,2)8.000000 0.000000 U(2,1)5.000000 0.000000 U(2,3)10.00000 0.000000 U(1,T)7.000000 0.000000 U(1,3)2.000000 0.000000 U(3,T)4.000000 0.000000 F(S,1)3.000000 0.000000 F(S,2)8.000000-1.000000 F(2,1)4.000000 0.000000 F(2,3)4.000000 0.000000 F(1,T)7.000000-2.000000 F(1,3)0.000000 5.000000 F(3,T)4.000000 0.000000,Row Slack or Surplus Dual Price 1 55.00000-1.000000 2 0.000000-3.000000 3 0.000000-5.000000 4 0.000000-2.000000 5 0.000000-7.000000,6.6 中国邮递员问题,中国邮递员问题：（1962年，管梅谷，中国),某一邮递员负责某街区的邮件投递工作，,要从邮局出发走遍负责的所有街道，,每次都,再回到邮局，,应如何安排投递路线，,他,使所走的总路程最短。,图论语言,给定一个连通图，在每个边,上赋予非负权数,要求一个回路，过每边至少一次，并使回路的,总权数最小。,定义,设 G为连通图，若存在一条回路，经过每条,边一次且仅一次，称这条回路为欧拉回路。具有欧拉,回路的图称为欧拉图。,定理,连通图G是欧拉图当且仅当 G中的点全为偶,点。,证明：,必要性。,设G为欧拉图，,故存在一条回路经过G中所有的边，,这条回路上，,边不重复但顶点可能重复。,对任一点,只要它在回路中出现一次，,必关联两条边。,故,可以,在回路中重复出现，,但点的次必为偶数。,充分性。,设G中的点全为偶点，,如从,出发，,经关联边到,而,为偶点，,故必经关联边到另一点,如此下去，,每条边仅取一次。,由于G的点数有限，,所以沿这条路,必可走回,得到一条回路,若,经过G中所有边，,则,即为欧拉回路。,否,则从G中去掉,后得到子图,则,中每个顶点,的次数仍为偶数，,因G为连通图，,故,与,至少有,一个顶点与,重合，,在,中从,出发，,重复,的,方法，,得到回路,把,和,组合在一起，,如果恰,为G，,则得到欧拉回路。,否则按构造,的方法构造,依此类推。,由于G中边数有限，,故最终可得一条过G中所有,边的回路，,即为欧拉回路。,证毕。,推论,无向连通图G存在欧拉链当且仅当 G中恰,有两个奇点。,证明：,必要性。,无向连通图G存在欧拉链，,则G中必然有一个从,起点u出发，,通过其他中间点，,且过每条边一次且仅一,次，,到达终点v,因为图G中间点都只能是过路的顶点，,离开该点的次数等于到达该点的次数。,因为要求不,能有重复的边，,故而每次到达和离去都选用不同的边。,所以中间顶点必然与偶数条边相关联，,即图G中间点,必然是偶顶点，只有起点 u和终点 v才为奇点。,充分性。,设G中恰有两个奇点 u，v，,在 G中增加一个新边,(u,v)（若u，v之间本来有边，则该边为其重复边），,从而得新图,所以,点全为偶点，,由定理知,存在一条欧拉回路,此时去掉,中的新增加的新边,(u,v),即得G中的一条连接u，v的欧拉链。,证毕。,注1：,上述定理和推论为我们提供了识别一个图能否,一笔画出的较为简单的办法。,如七桥问题，,有四个奇点，,所以不是欧拉图，,故不,不能一笔画出。,即不可能一次连续走过这七座,桥回到原出发点，且每座桥只走一次。,一般地，,若连通多重图G中全为偶点，,则该图能一,笔画成，,且第一个顶点和最后一个顶点相同；,若连通多,重图G有两个奇顶点，,则该图也能一笔画成，,但第一个,点与最后一个点不同。,
