西南交通大学教师赛课总决赛课件—管理运筹学

寇玮华（[e-mail]）2019年8月13日星期二管理运筹学西南交通大学交通运输学院管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第2页第十章网络的流§10.2网络最大流算法一学习目的（1）如何判断网络流量达到最大？（2）如何增加网络的流量？二学习内容三学习总结相关知识回顾相关概念基础概念核心概念§10.2.2寻找增流链寻找增流链管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第3页第十章网络的流（1）设f为G上一个流，若存在e∈E，f(e)=C(e),称边e为f饱和边；（2）若存在f(e)C(e)，称边e为f不饱和边；（3）若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到u的有向边(v,u)，称边(v,u)为Q的后向边。（一）基本概念一相关概念管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第4页第十章网络的流若f为G上的流，对e∈E(Q)，令：的一条后向边是当的一条前向边是当QeefQeefeCel)()()()(当l(Q)=0时，称Q为f饱和链；当l(Q)0时，称Q为f不饱和链。（二）核心概念（1）饱和链及不饱和链l(e)、l(Q)隐含的意义是什么？饱和链、不饱和链的性质是什么？)(min)(elQeQl令管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第5页(60,50)(120,30)示例v3v1v2x2x1xy2y1y取链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(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为不饱和链。第十章网络的流管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第6页(120,30)(60,50)v3v1v2x2x1xy2y1y（2）增流链一条从源x到汇y的流f不饱和链称为f增流链。增流链与不饱和链的区别是什么？Q=xx2+Q2即为增流链第十章网络的流管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第7页（三）增流链的作用对网络G中存在一条流f的增流链Q，给出调整公式：其它的一条后向边是当的一条前向边是当)()()()()()(ˆefQeQlefQeQlefef利用调整公式可以把不饱和的增流链流量增加成一个新流，即将增流链调整为饱和链。这里把l(Q)称为增流链Q的调整量。第十章网络的流管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第8页1、标号未查视边（u，v）的顶点v，的标号方式为：（u，边的方向，l(v)）标号点的前个顶点v为终点用+表示v为始点用-表示2、进行查视，即顶点v能否长枝条件为：（1）边e=(v,z)为前向边，f(e)C(e)。（2）边e=(v,z)为后向边，f(e)0。4、不断循环直至不能长枝。3、若顶点z能够长枝，对z进行标号。第十章网络的流二寻找增流链v为终点：l(v)=min{l(u),C(u,v)-f(u,v)}v为始点：l(v)=min{l(u),f(u,v)}管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第9页x1示例xyx2x3v1v2v4v3y1y2y3(0,+,+∞)(x,+,8)(x1,+,3)(v1,-,1)(v4,+,1)(y3,+,1)第十章网络的流管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第10页管理运筹学谢谢管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第11页前面知识回顾图G={V,E}网络G={V,E,C,F,X,Y}G={V,E,W}容量约束条件0≤f(e)≤C(e)，任意e∈E；流量守恒条件f+(v)=f-(v)，任意v∈I；流量分配遵从的条件定理流f为G的最大流的充要条件为G中不存在f增流链G={V,E,C,F,W,X,Y}管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第12页5,27,48,37,3985,37,387第十章网络的流4,27,25,36,58,2v4777,28,25,34,26,5v488,34,26,5v48xyxy管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第13页l=4-1=3l=5-3=2l=6-2=4l=5-3=2l=6-2=4l=6-2=4第十章网络的流l(Q1)=min(4)=46,2Q1:V1V26,25,3Q2:V1V2V3l(Q2)=min(4,2)=2l(Q3)=min(4,2,3)=26,2Q3:V1V25,3V34,1V4l(Q3)=min(l(Q2),3)=2l(v2)=4l(v3)=2l(v4)=2l(v3)=2前向边：l(v)=min{l(u),C(u,v)-f(u,v)}后向边：l(v)=min{l(u),f(u,v)}l(v4)=2l(Q3)=min(l(v3),3)=2Q4:6,2V1V25,3V34,1V4V53,1l(Q4)=min(l(v4),1)=1l(v5)=1l(v2)=4管理运筹学——网络的流寇玮华（[e-mail]）2019年8月13日星期二第14页第十章网络的流学习总结（1）要点增流链（2）重点（3）难点调整公式如何寻找增流链判断网络流量状态的依据。网络流量是否增加的前提。l(v)的计算流量如何增加或减少？调整量是多少？为何把链调整量标示在链的终点？理解、掌握最大流算法的关键。