《工程系统分析》教学课件 第4章 网络模型

第四章网络模型,4-1网络模型及其特征4-2图论基础4-3最短路模型4-4最大流模型4-5最小费用流模型4-6最小树模型,4-1网络模型及其特征,网络模型的构成及其分类,网络模型的特征,4-1网络模型及其特征,一、网络模型的构成及其分类,1.网络模型的构成,（1）节点系统的组成要素,（2）弧要素间的关系,（3）流量要素间关系的量化,a,b,c,a,b,4-1网络模型及其特征,一、网络模型的构成及其分类,1.网络模型的构成2.网络模型的分类,（1）以物质为流量,4-1网络模型及其特征,一、网络模型的构成及其分类,1.网络模型的构成2.网络模型的分类,（1）以物质为流量（2）以信息为流量,4-1网络模型及其特征,一、网络模型的构成及其分类,1.网络模型的构成2.网络模型的分类,（1）以物质为流量（2）以信息为流量（3）以能量为流量,4-1网络模型及其特征,一、网络模型的构成及其分类,1.网络模型的构成2.网络模型的分类,（1）以物质为流量（2）以信息为流量（3）以能量为流量（4）以时间、距离、费用等为流量,4-1网络模型及其特征,一、网络模型的构成及其分类二、网络模型的特征,1.能够直观地反映系统元素及其相互关系2.以不同的流量表述不同的系统问题3.特定流量具有特定的算法4.简单直观，易于掌握,4-2图论基础,图的有关概念,连通图与树,4-2图论基础,一、图的有关概念,1.图,节点与弧的集合。设N为节点的集合，E为弧的集合，则图G可以表示为：G=N，E,G=N，EN=n1，n2，n3，n4E=e1，e2，e3，e4，e5，e6,4-2图论基础,一、图的有关概念,1.图2.自环,首尾均在一个节点的弧如e2,4-2图论基础,一、图的有关概念,1.图2.自环3.关联与邻接,(1)节点与弧相互关联,4-2图论基础,一、图的有关概念,1.图2.自环3.关联与邻接,(1)节点与弧相互关联(2)弧与弧相互关联,4-2图论基础,一、图的有关概念,1.图2.自环3.关联与邻接,(1)节点与弧相互关联(2)弧与弧相互关联(3)节点的邻接,前导节点,后续节点,4-2图论基础,一、图的有关概念,1.图2.自环3.关联与邻接4.链的有关概念,对于任一节点序列n1,n2,nk+1,ei为ni-1,ni构成的弧，则弧的系列e1,e2,ek构成一条链。n1为链的始点，nk+1为链的终点，弧的数目k称为链的长度。,（1）链,例如，节点序列2,3,4构成的链,4-2图论基础,一、图的有关概念,1.图2.自环3.关联与邻接4.链的有关概念,（1）链（2）路,全部由同向弧组成的链,例如，节点序列2,3,4构成的路,4-2图论基础,一、图的有关概念,1.图2.自环3.关联与邻接4.链的有关概念,（1）链（2）路（3）圈,始点和终点为同一节点的链（闭合链）,例如，节点序列2,3,4构成的圈,4-2图论基础,一、图的有关概念,1.图2.自环3.关联与邻接4.链的有关概念,（1）链（2）路（3）圈（4）回路,始点和终点为同一节点的路全部由同向弧组成的圈,例如，节点序列2,3,4构成的圈,4-2图论基础,一、图的有关概念二、连通图与树,1.连通图与不连通图,（1）连通图：图中任意两节点间至少存在一条链,（2）不连通图：图中至少有两节点间不存在链,4-2图论基础,一、图的有关概念二、连通图与树,1.连通图与不连通图2.子图,（1）由节点子集生成的子图：包括该节点子集及两个端点都在该节点子集上的所有弧。,例如，由节点2,3,4生成的子图,4-2图论基础,一、图的有关概念二、连通图与树,1.连通图与不连通图2.子图,（2）由弧子集生成的子图：包括该弧子集及该弧子集的所有端点。,例如，由弧e2,e3,e4生成的子图,4-2图论基础,一、图的有关概念二、连通图与树,1.连通图与不连通图2.子图3.树,无圈的连通图或子图,4-2图论基础,一、图的有关概念二、连通图与树,1.连通图与不连通图2.子图3.树4.有向图与无向图,(1)有向图：规定了弧的方向的图（至少包含一条箭线）(2)无向图：未规定弧的方向的图（不包含任何箭线）,4-3最短路模型,一、问题的提出,通过网络各边所需要的时间、距离或费用等为已知时，欲找出从始点s至终点t的最少时间、最短路径或最小费用等的路径问题。,设备更新问题编制生产计划问题物资输送问题新产品试制规划问题旅行线路选择问题,4-3最短路模型,二、最短路模型的算法,1.基本思路,Dijkstra算法：假定1234是14的最短路，则123一定是13的最短路，234一定是24的最短路,4-3最短路模型,二、最短路模型的算法,1.基本思路2.有关符号,b(i,j),b(i,j),b(i,j),s始点,t终点,b(i,j)节点i至节点j的直达距离,T(j)s至j的最短路长度,P(j)s至j为最短路时,j的前导节点号,k最新标记的节点号,P(j),4-3最短路模型,二、最短路模型的算法,3.算法步骤,开始,对s标记,k=s,T(s)=0,其余T(j),k有未标记未计算的后续节点?,N,T(k)+b(k,j)T(j)?,j,T(j),b(k,j),T(k),4-3最短路模型,二、最短路模型的算法,3.算法步骤,t标记否?,结束,中止,2,4-3最短路模型,二、最短路模型的算法,4.计算示例,4-3最短路模型,二、最短路模型的算法,4.计算示例,s,1,2,对S标记,k=s,T(s)=0,其余T(j),T(s)+b(s,1)=0+2=2T(1),T(1)=2,P(1)=sT(s)+b(s,2)=0+3=3T(2),T(2)=3,P(2)=sT(s)+b(s,3)=0+5=5T(3),T(3)=5,P(3)=sminT(j)=2,x=1k=1,对节点1及s1标记,T(1)+b(1,3)=2+2=4T(3),T(3)=4,P(3)=1T(1)+b(1,5)=2+7=9T(5),T(5)=9,P(5)=1minT(j)=3,x=2k=2,对节点2及s2标记,4-3最短路模型,二、最短路模型的算法,4.计算示例,T(2)+b(2,4)=3+5=8T(4),T(4)=8,P(4)=2,minT(j)=4,x=3k=3,对节点3及13标记,T(3)+b(3,4)=4+3=7T(4),T(4)=7,P(4)=3T(3)+b(3,5)=4+5=9=T(5)minT(j)=7,x=4k=4,对节点4及34标记,T(4)+b(4,5)=7+1=8T(5),T(5)=8,P(5)=4T(4)+b(4,t)=7+7=14T(t),T(t)=14,P(t)=4minT(j)=8,x=5k=5,对节点5及45标记,T(5)+b(5,t)=8+5=13T(t),T(t)=13,P(t)=5minT(j)=13,x=tk=t,对节点t及5t标记,3,4,5,t,4-3最短路模型,三、最短路问题构模举例,例1设备更新问题,某建筑公司在第一年开始购买一台新的施工设备，用了一段时间后进行更新。现在，希望找到五年内的一种最好的更新策略，使得施工机具的购置费用和维修费之和为最小。施工机具的购置费和维修费分别如下表所示：,第一至第五年施工机具购置费,12345,1.11.11.21.21.3,4-3最短路模型,三、最短路问题构模举例,例1设备更新问题,某建筑公司在第一年开始购买一台新的施工设备，用了一段时间后进行更新。现在，希望找到五年内的一种最好的更新策略，使得施工机具的购置费用和维修费之和为最小。施工机具的购置费和维修费分别如下表所示：,维修费与机具使用年限的关系,010.5,120.6,230.8,341.1,451.8,4-3最短路模型,三、最短路问题构模举例,例1设备更新问题,某建筑公司在第一年开始购买一台新的施工设备，用了一段时间后进行更新。现在，希望找到五年内的一种最好的更新策略，使得施工机具的购置费用和维修费之和为最小。施工机具的购置费和维修费分别如下表所示：,1,2.2,3.0,4.1,5.9,2.2,3.0,4.1,2.3,3.1,2.3,4-3最短路模型,三、最短路问题构模举例,例1设备更新问题,4-3最短路模型,三、最短路问题构模举例,例1设备更新问题,1,6,3,4,5,0,1.6,2.2,3.0,4.1,5.9,5.7,5.3,2,4-3最短路模型,三、最短路问题构模举例,例2施工方案选择问题,某建设工程还有四个项目没完成，根据需要希望该工程尽早投入使用。已知这四个项目在正常施工、采取一般措施施工和采取紧急措施施工情况下需要的时间和费用如下表：,时间（月）,项目1234,施工方式正常一般措施紧急措施,542,32,53,21,4-3最短路模型,三、最短路问题构模举例,例2施工方案选择问题,某建设工程还有四个项目没完成，根据需要希望该工程尽早投入使用。已知这四个项目在正常施工、采取一般措施施工和采取紧急措施施工情况下需要的时间和费用如下表：,费用（万元）,123,23,34,12,已知这四个项目必须按顺序施工，为完成这四项工程的全部追加投资为10万元，问在投资允许范围内，如何安排施工，使全部工程尽早投入使用？,4-3最短路模型,三、最短路问题构模举例,例2施工方案选择问题,s,10,3,3,5,5,5,2,2,2,0,0,0,最优施工方案即为从s至t的最短路径,x-节点序号y-剩余的赶工费用T-项目持续时间,4-4最大流模型,一、最大流的有关概念,1.容量网络,(1)流,将目标从一个地点送至另一个地点的活动网络上各条弧的一组负载量,(2)容量,每条弧流的最大通过能力c(x,y),(3)流量,通过弧的流的单位数量f(x,y),(4)最大流,网络中允许通过的最大流量,4-4最大流模型,一、最大流的有关概念,2.可行流,(1)容量限制条件,0f(x,y)C(x,y)(x,y)E,(2)中间节点平衡条件,f(x,y)-f(y,x)=0(ys,t),(3)发点平衡条件,满足下列条件的流称为可行流,f(s,y)-f(y,s)=v,y,(4)收点平衡条件,f(t,y)-f(y,t)=-v,s,t,4-4最大流模型,一、最大流的有关概念,3.弧的分类,(1)N-流不能有任何增加或减少的弧的集合,(2)I-流可以增加的弧的集合最大增量i(x,y)=c(x,y)-f(x,y),(3)R-流可以减少的弧的集合最大减量r(x,y)=f(x,y),4-4最大流模型,一、最大流的有关概念,4.增值链,(1)从st全部由前向弧组成的路P,定义前向弧为st方向，I；后向弧为ts方向，R,4-4最大流模型,一、最大流的有关概念,4.增值链,(1)从st全部由前向弧组成的路P(2)从st全部由后向弧组成的路P,定义前向弧为st方向，I；后向弧为ts方向，R,4-4最大流模型,一、最大流的有关概念,4.增值链,(1)从st全部由前向弧组成的路P(2)从st全部由后向弧组成的路P(3)从st即有前向弧又有后向弧组成的链P,定义前向弧为st方向，I；后向弧为ts方向，R,4-4最大流模型,二、最大流的算法,1.基本思路,寻找st的增值链,是否有？,4-4最大流模型,二、最大流的算法,2.确定增值链的方法,开始,有已标记未检查节点?,X有相邻未标记节点?,对s标记,2,1,结束,t标记?,结束,4-4最大流模型,二、最大流的算法,3.最大流的标号算法,4-4最大流模型,二、最大流的算法,3.最大流的标号算法,4-4最大流模型,二、最大流的算法,3.最大流的标号算法,(-,),(s+,13),(1+,5),(4+,5),5,(5,(5),(5,4-4最大流模型,二、最大流的算法,3.最大流的标号算法,(-,),(s+,8),(1+,6),(3+,4),5+4=9,9,(4,(4),4-4最大流模型,二、最大流的算法,3.最大流的标号算法,(-,),(s+,4),(1+,2),(3+,2),(4+,2),9+2=11,11,6),(2,7,4-4最大流模型,二、最大流的算法,3.最大流的标号算法,(-,),(s+,2),(s+,9),(2+,5),(5+,5),11+5=16,(5,(5),(5,4-4最大流模型,二、最大流的算法,3.最大流的标号算法,(-,),(s+,2),(s+,4),(2+,4),(3+,4),16+4=20,(5+,4),9,(4,(4),9,(-,),(s+,2),最大流=20,4-4最大流模型,三、多收点与多发点的修正,S,t,S1发量,S2发量,t1收量,t2收量,t3收量,4-4最大流模型,四、最大流量最小截量定理,在任一个网络D中,从s至t的最大流流量等于分离s、t的最小截集的容量。,最小截面=20,4-4最大流模型,四、最大流量最小截量定理,例：某高速公路的线路如下图，现拟建立足够数量的收费站，以使从s至t的每辆汽车至少必须通过一个收费站。建立收费站的费用如图所示，求最小费用解。,4-4最大流模型,四、最大流量最小截量定理,例：某高速公路的线路如下图，现拟建立足够数量的收费站，以使从s至t的每辆汽车至少必须通过一个收费站。建立收费站的费用如图所示，求最小费用解。,(2,(2),(2,(2,4),(2),(2,4,4),(6),(6,(6,(1,(1,7),7),4,4,5),(3,(3,最小费用=14，在1-4，2-4，2-5间建收费站。,4-5最小费用流模型,一、问题的提出,在最大可能运送的情况下，如何使运费最省？设a(x,y)-沿弧(x,y)运送单位流量的费用（正整数）v-从st运送的数量,S.b.,4-5最小费用流模型,二、最小费用流算法,1.算法原理,逐次找全程单位运费为0，1，2，的路径。,2.算法步骤,开始,v0=?,执行最大流算法,所有f(x,y)=0,p(x)=0标记S,v0=0,v0=v0+,结束,Y,注意：弧的分类作如下规定I:f(x,y)0|p(y)-p(x)|=a(x,y),4-5最小费用流模型,二、最小费用流算法,3.算法举例,求图示网络v=7和最大流时的最小费用,000000,迭代0：所有弧N,s,s,无,101111,迭代1：P(2)-p(s)=1I,2,s,2(s,2),未标记节点p(x)=p(x)+1(xs,2),未标记节点p(x)=p(x)+1(xs),202122,s,2(s,2),迭代2：未标记节点p(x)=p(x)+1(xs,2),4-5最小费用流模型,二、最小费用流算法,迭代3：P(1)-P(2)=2I,303133,1,未标记节点p(x)=p(x)+1(xs,1,2),s,2,1(s,2)(2,1),4-5最小费用流模型,二、最小费用流算法,303133,1,s,2,1(s