最小费用最大流.ppt
《最小费用最大流.ppt》由会员分享,可在线阅读,更多相关《最小费用最大流.ppt(37页珍藏版)》请在三一文库上搜索。
1、,6.5 最小费用最大流问题,6.5.1 最小费用最大流问题的数学模型,设网络D=(V,A,W),每条弧,除了容量,以,外,,还给出单位流量的费用,(简记为,)。,这样,D就成为一个带费用的网络,记为D=(V,A,W,C),其中,C称为费用函数。,设X为D上的一个可行流,称,(6.5.1),为可行流X的费用。,最小费用最大流问题,即要求一个最大流X,使总,运输费用,(6.5.2),达到最小值,,则有最小费用最大流问题的数学模型,(6.5.3),6.5.2 最小费用最大流问题的算法,寻求最大流的方法,最小 费用,最小费用最大流,从某个可行流出发, 找到关于这个可行流 的一条增广链,沿着 该增广链
2、调整X,对 新的可行流试图寻求 关于它的增广链,如 此反复直至最大流,设想:,当沿着一条关于可行流X的增广链,以,调整X,,得到新的可行流,且有,这里第三个等式只是因为对,之外的,来说,即费用均一样。,记,称,是沿增广链,当可行流增加单位流值时费,用的增量,,简称为增广链,的单位费用增量。,可以证明,,若X是流量为f(X)的所有可行流中费,用最小者,,而,是关于X的所有增广链中费用最小的,增广链,,则沿,去调整X,,得到的可行流,就是流量,为,的所有可行流中的最小费用流,,这样,,当,是最大流时,,即为最小费用最大流。,注意到,故X=0必是流量为 0的最小费用,流。,这样,,总可以从X=0开始
3、。,一般地,,若X是流量,f(X)的最小费用流,,为了寻求关于X的最小费用增,广链,,构造一个赋权有向图D(X),,它的顶点是原网,络D的顶点,,而把D中的每一条弧,变成两个,相反方向的弧,和,定义D(X),中弧的,权,在D(X)中长度为,的弧可以略去。,故在网络D中寻找关于 X的最小费用增广链就,等价于在赋权有向图D(X)中,,寻找从,到,的最短,路。,算法步骤:,Step1:,确定初始可行流,令,Step2:,记,为经过k次调整得到的最小费用流,,构造,Step3:,求,中,到,的最短路,若,不存在,则,是最小费用最大流,算法,终止;,否则,转Step4;,Step4:,在D中找对应的增广
4、链,按式(6.4.4)调,整流量,得可行流,令,转,Step2。,例6.5.1,求图6.5.1的最小费用最大流,弧旁的数字,为,图6.5.1,解:,取,见图6.4.7(a),,图6.5.1(a),构造,因没有负权弧,,故可用Dijkstra算法求得最短路为,见图6.5.1(b)。,图6.5.1(b),增广链,调整后,如图6.5.1(c)。,图6.5.1(c),构造,得到,如图6.5.1(d)。,图6.5.1(d),调整得,如图6.5.1(e)。,图6.5.1(e),构造,如图6.5.1(f)。,图6.5.1(f),显然,,与,关联的弧指向,不存在,到,的最短路。,故图6.5.1(e)所示的,为
5、最小费用,最大流。,费用,流值,三、最小费用最大流,例6.8.3,用LINGO软件求解例6.5.1。,解:,程序如下:,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; endsets min=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); fo
6、r(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; enddata end,运行结果:,Global optimal solution found at iteration: 0 Objective value: 12.00000 Variable Value Reduced Cost D( 1) 3.000000 0.000000 D( 2) 0.000000 0.000000,D( 3) 0.000000 0.000000 D( 4) 0.000000 0.000000 D( 5) -3.0000
7、00 0.000000 C( 1, 2) 1.000000 0.000000 C( 1, 3) 3.000000 0.000000 C( 2, 3) 2.000000 0.000000 C( 2, 4) 5.000000 0.000000 C( 3, 4) 1.000000 0.000000 C( 3, 5) 1.000000 0.000000 C( 4, 5) 3.000000 0.000000 U( 1, 2) 2.000000 0.000000 U( 1, 3) 1.000000 0.000000 U( 2, 3) 3.000000 0.000000 U( 2, 4) 6.000000
8、0.000000 U( 3, 4) 2.000000 0.000000,U( 3, 5) 3.000000 0.000000 U( 4, 5) 4.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3) 1.000000 0.000000 F( 2, 3) 2.000000 0.000000 F( 2, 4) 0.000000 5.000000 F( 3, 4) 0.000000 3.000000 F( 3, 5) 3.000000 0.000000 F( 4, 5) 0.000000 0.000000,结果说明,最小费用为12,此时,流值为3。
9、,例6.8.6,用MATLAB软件求解例6.5.1。,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,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最小 费用 最大
链接地址:https://www.31doc.com/p-3391169.html