《{交通运输管理}西南交通大学教师赛课总决赛讲义—管理运筹学》由会员分享，可在线阅读，更多相关《{交通运输管理}西南交通大学教师赛课总决赛讲义—管理运筹学（14页珍藏版）》请在金锄头文库上搜索。
1、管理运筹学,西南交通大学交通运输学院,2020/8/2,第十章 网络的流,10.2 网络最大流算法,一 学习目的,（1）如何判断网络流量达到最大？,（2）如何增加网络的流量？,二 学习内容,三 学习总结,相关知识回顾,相关概念,基础概念,核心概念,10.2.2 寻找增流链,寻找增流链,2020/8/2,2,第十章 网络的流,（1）设f为G上一个流，若存在eE，f(e)=C(e), 称边e为f饱和边； （2）若存在f(e)0，称边e为f正边;若f(e)=0，称边e 为f零边。 （4）设Q=x，u，v，t为f的一条初等链，则： G中u到v的有向边(u, v)，称边(u, v)为Q的前向边； G中v
2、到u的有向边(v, u)，称边(v, u)为Q的后向边。,（一） 基本概念,一 相关概念,2020/8/2,3,第十章 网络的流,若f为G上的流，对eE(Q)，令：,当l(Q)=0时，称Q为f饱和链； 当l(Q)0时，称Q为f不饱和链。,（二） 核心概念,（1）饱和链及不饱和链,l(e)、l(Q)隐含的意义是什么？ 饱和链、不饱和链的性质是什么？,令,2020/8/2,4,取链Q1=xx2v2x1v1，边(x,x2),(x2,v2)和(x1,v1)为Q1的前向边， L(x,x2)=10,L(x2,v2)=30,L(x1,v1)=0；边(v2,x1)为Q1的后向边， L(v2,x1)=50。则L
3、(Q1)=0， Q1为饱和链。,取链Q2=x2v3y2v1y1y，边(x2,v3),(v3,y2),(v1,y1)和(y1,y)为Q2前向边， L(x2,v3)=20，L(v3,y2)=90，L(v1,y1)=10，L(y1,y)=30；边(y2,v1)为 Q2后向边， L(y2,v1)=20。则L(Q2)=10，Q2为不饱和链。,第十章 网络的流,2020/8/2,5,（2）增流链,一条从源x到汇y的流f不饱和链称为f增流链。,增流链与不饱和链的区别是什么？,Q=xx2+Q2即为增流链,第十章 网络的流,2020/8/2,6,（三） 增流链的作用,对网络G中存在一条流f的增流链Q，给出调整公
4、式：,利用调整公式可以把不饱和的增流链流量增加成一个新流，即将增流链调整为饱和链。,这里把l(Q)称为增流链Q的调整量。,第十章 网络的流,2020/8/2,7,1、标号未查视边（u，v）的顶点v，的标号方式为： （u，边的方向，l(v)）,标号点的前个顶点,v为终点用+表示 v为始点用-表示,2、进行查视，即顶点v能否长枝条件为： （1）边e=(v,z)为前向边，f(e)0。,4、不断循环直至不能长枝。,3、若顶点z能够长枝，对z进行标号。,第十章 网络的流,二 寻找增流链,v为终点： l(v)=minl(u),C(u,v)-f(u,v) v为始点： l(v)=minl(u),f(u,v),
5、2020/8/2,8,(0,+,+),(x,+,8),(x1,+,3),(v1,-,1),(v4,+,1),(y3,+,1),第十章 网络的流,2020/8/2,9,管 理 运 筹 学,谢 谢,2020/8/2,10,前面知识回顾,网络,G=V,E,C,F,X,Y,G=V,E,W,容量约束条件 0f(e)C(e)，任意eE； 流量守恒条件 f+(v)=f-(v)，任意vI；,流量分配遵从的条件,G=V,E,C,F,W,X,Y,2020/8/2,11,5,2,7,4,8,3,7,3,9,8,5,3,7,3,8,7,第十章 网络的流,7,7,7,2,8,2,8,8,x,y,x,y,2020/8/2
6、,12,l=4-1=3,l=5-3=2,l=6-2=4,l=5-3=2,l=6-2=4,l=6-2=4,第十章 网络的流,l (Q1) = min(4)=4,l (Q2) = min(4,2)=2,l (Q3) = min(4,2,3)=2,l (Q3) = min(l(Q2),3)=2,l (v2) = 4,l (v3) = 2,l (v4) = 2,l (v3) = 2,前向边： l(v)=minl(u),C(u,v)-f(u,v) 后向边： l(v)=minl(u),f(u,v),l (v4) = 2,l (Q3) = min(l(v3),3)=2,l (Q4) = min(l(v4),1)=1,l (v5) = 1,l (v2) = 4,2020/8/2,13,第十章 网络的流,学习总结,（1）要点,增流链,（2）重点,（3）难点,调整公式,如何寻找增流链,判断网络流量状态的依据。 网络流量是否增加的前提。,l(v)的计算,流量如何增加或减少？调整量是多少？,为何把链调整量标示在链的终点？,理解、掌握最大流算法的关键。,2020/8/2,14,
