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

该【西南交通大学教师赛课总决赛课件—管理运筹学 】是由【小屁孩】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【西南交通大学教师赛课总决赛课件—管理运筹学 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。管理运筹学西南交通大学交通运输学院2021/10/10第十章网络的流§(1)如何判断网络流量达到最大?(2)如何增加网络的流量?二学****内容三学****总结相关知识回顾相关概念基础概念核心概念§(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的后向边。(一)基本概念一相关概念2021/10/103第十章网络的流若f为G上的流,对e∈E(Q),令:当l(Q)=0时,称Q为f饱和链;当l(Q)>0时,称Q为f不饱和链。(二)核心概念(1)饱和链及不饱和链l(e)、l(Q)隐含的意义是什么?饱和链、不饱和链的性质是什么?令2021/10/104(180,150)(60,50)(40,20)(120,30)(150,130)(70,70)(70,50)(130,100)(240,230)示例(150,150)v3v1v2(100,100)(120,120)x2x1xy2y1y(200,200)取链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为不饱和链。第十章网络的流2021/10/105(240,230)(130,100)(150,130)(70,70)(150,150)(120,30)(40,20)(60,50)(70,50)v3v1v2(100,100)(120,120)x2x1xy2y1y(180,150)(200,200)(2)增流链一条从源x到汇y的流f不饱和链称为f增流链。增流链与不饱和链的区别是什么?Q=xx2+Q2即为增流链第十章网络的流2021/10/106(三)增流链的作用对网络G中存在一条流f的增流链Q,给出调整公式:利用调整公式可以把不饱和的增流链流量增加成一个新流,即将增流链调整为饱和链。这里把l(Q)称为增流链Q的调整量。第十章网络的流2021/10/1071、标号未查视边(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)}2021/10/108(1,0)x1示例xyx2x3v1v2v4v3y1y2y3(5,0)(4,3)(3,3)(8,6)(8,3)(4,1)(7,5)(8,2)(2,2)(2,1)(7,0)(4,1)(4,2)(2,2)(1,1)(5,3)(3,2)(4,2)(12,4)(8,4)(12,5)(11,3)(11,3)(11,7)(0,+,+∞)(x,+,8)(x1,+,3)(v1,-,1)(v4,+,1)(y3,+,1)第十章网络的流2021/10/109管理运筹学谢谢2021/10/1010