《建筑系统工程学》工程系统分析讲义4

1、第四章 网络模型4-1 网络模型及其特征4-2 图论基础4-3 最短路模型4-4 最大流模型4-5 最小费用流模型4-6 最小树模型4-1 网络模型及其特征 网络模型的构成及其分类 网络模型的特征4-1 网络模型及其特征一、网络模型的构成及其分类1.网络模型的构成（1）节点 系统的组成要素（2）弧 要素间的关系（3）流量 要素间关系的量化a,b,ca,b4-1 网络模型及其特征一、网络模型的构成及其分类1.网络模型的构成2.网络模型的分类（1）以物质为流量4-1 网络模型及其特征一、网络模型的构成及其分类1.网络模型的构成2.网络模型的分类（1）以物质为流量（2）以信息为流量4-1 网络模型及

2、其特征一、网络模型的构成及其分类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为

3、弧的集合，则图G可以表示为：G=N，E1234e1e2e3e4e5e6G=N，EN=n1，n2，n3，n4E=e1，e2，e3，e4 ，e5，e64-2 图论基础一、图的有关概念1.图2.自环首尾均在一个节点的弧如 e21234e1e2e3e4e5e64-2 图论基础一、图的有关概念1.图2.自环3.关联与邻接1234e1e2e3e4e5e6(1)节点与弧相互关联4-2 图论基础一、图的有关概念1.图2.自环3.关联与邻接1234e1e2e3e4e5e6(1)节点与弧相互关联(2)弧与弧相互关联4-2 图论基础一、图的有关概念1.图2.自环3.关联与邻接1234e1e2e3e4e5e6(1)节

4、点与弧相互关联(2)弧与弧相互关联(3)节点的邻接前导节点后续节点4-2 图论基础一、图的有关概念1.图2.自环3.关联与邻接4.链的有关概念1234e1e2e3e4e5e6对于任一节点序列n1, n2, ,nk+1, ei为ni-1, ni构成的弧，则弧的系列e1, e2, ,ek构成一条链。 n1为链的始点， nk+1为链的终点，弧的数目k称为链的长度。（1）链例如，节点序列2,3,4构成的链234e3e5234e3e6e3234e44-2 图论基础一、图的有关概念1.图2.自环3.关联与邻接4.链的有关概念1234e1e2e3e4e5e6（1）链（2）路全部由同向弧组成的链例如，节点序列

5、2,3,4构成的路234e3e5234e3e64-2 图论基础一、图的有关概念1.图2.自环3.关联与邻接4.链的有关概念1234e1e2e3e4e5e6（1）链（2）路（3）圈始点和终点为同一节点的链（闭合链）例如，节点序列2,3,4构成的圈e5234e3234e3e6e44-2 图论基础一、图的有关概念1.图2.自环3.关联与邻接4.链的有关概念1234e1e2e3e4e5e6（1）链（2）路（3）圈（4）回路始点和终点为同一节点的路全部由同向弧组成的圈例如，节点序列2,3,4构成的圈e5234e34-2 图论基础一、图的有关概念二、连通图与树1.连通图与不连通图1234e1e2e3e4e

6、5e6（1）连通图：图中任意两节点间至少存在一条链（2）不连通图：图中至少有两节点间不存在链12345674-2 图论基础一、图的有关概念二、连通图与树1.连通图与不连通图2.子图1234e1e2e3e4e5e6（1）由节点子集生成的子图：包括该节点子集及两个端点都在该节点子集上的所有弧。例如，由节点2,3,4生成的子图234e2e3e4e5e64-2 图论基础一、图的有关概念二、连通图与树1.连通图与不连通图2.子图1234e1e2e3e4e5e6（2）由弧子集生成的子图：包括该弧子集及该弧子集的所有端点。例如，由弧e2,e3,e4生成的子图e2234e3e44-2 图论基础一、图的有关概念

7、二、连通图与树1.连通图与不连通图2.子图3.树1234e1e2e3e4e5e6无圈的连通图或子图234e3e44-2 图论基础一、图的有关概念二、连通图与树1.连通图与不连通图2.子图3.树4.有向图与无向图(1)有向图：规定了弧的方向的图（至少包含一条箭线）(2)无向图：未规定弧的方向的图（不包含任何箭线）4-3 最短路模型一、问题的提出通过网络各边所需要的时间、距离或费用等为已知时，欲找出从始点s至终点t的最少时间、最短路径或最小费用等的路径问题。 设备更新问题 编制生产计划问题 物资输送问题 新产品试制规划问题 旅行线路选择问题4-3 最短路模型二、最短路模型的算法1.基本思路Dijk

8、stra算法：假定12 34是14的最短路，则12 3一定是13的最短路， 2 34一定是24的最短路12344-3 最短路模型二、最短路模型的算法1.基本思路2.有关符号ijijijb(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 最新标记的节点号sjT(j)P(j)4-3 最短路模型二、最短路模型的算法3.算法步骤开始对s标记,k=s,T(s)=0,其余T(j)k有未标记未计算的后续节点?T(j)=T(k)+b(k,j)P(j)=kYN1NY选择这样一个节点jT(k)+b(k

9、,j)T(j)?skjT(j)b(k,j)T(k)4-3 最短路模型二、最短路模型的算法3.算法步骤开始对s标记,k=s,T(s)=0,其余T(j)k有未标记未计算的后续节点?T(j)=T(k)+b(k,j)P(j)=kYN1NY选择这样一个节点jT(k)+b(k,j)T(j)?1所有未标记节点T(j) ?t标记否?结束中止无最短路Y选择未标记节点中minT(j)对应的节点x,对x及弧P(x) x进行标记,令k=xN2N找到最短路Y24-3 最短路模型二、最短路模型的算法4.计算示例s1223352575245315t74-3 最短路模型二、最短路模型的算法4.计算示例s12233525752

10、45315t7s12对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=1 k=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=2 k=2, 对节点2及s2标记4-3 最短路模型二、最短路模型的算法4.计算示例

11、s1223352575245315t7s12T(2)+b(2,4)=3+5=8T(4), T(4)=8, P(4)=2minT(j)=4, x=3 k=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=4 k=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=5 k=5, 对节点5及45标记T(5)+b(5,t)=8+5=13T(

12、t), T(t)=13,P(t)=5minT(j)=13, x=t k=t, 对节点t及5t标记345t4-3 最短路模型三、最短路问题构模举例例1 设备更新问题 某建筑公司在第一年开始购买一台新的施工设备，用了一段时间后进行更新。现在，希望找到五年内的一种最好的更新策略，使得施工机具的购置费用和维修费之和为最小。施工机具的购置费和维修费分别如下表所示：第一至第五年施工机具购置费年费用(万元)1 2 3 4 51.1 1.1 1.2 1.2 1.34-3 最短路模型三、最短路问题构模举例例1 设备更新问题 某建筑公司在第一年开始购买一台新的施工设备，用了一段时间后进行更新。现在，希望找到五年内

13、的一种最好的更新策略，使得施工机具的购置费用和维修费之和为最小。施工机具的购置费和维修费分别如下表所示：第一至第五年施工机具购置费年费用(万元)1 2 3 4 51.1 1.1 1.2 1.2 1.3维修费与机具使用年限的关系使用年限费用(万元)010.5120.6230.8341.1451.84-3 最短路模型三、最短路问题构模举例例1 设备更新问题 某建筑公司在第一年开始购买一台新的施工设备，用了一段时间后进行更新。现在，希望找到五年内的一种最好的更新策略，使得施工机具的购置费用和维修费之和为最小。施工机具的购置费和维修费分别如下表所示：第一至第五年施工机具购置费年费用(万元)1 2 3

14、4 51.1 1.1 1.2 1.2 1.3维修费与机具使用年限的关系使用年限费用(万元)010.5120.6230.8341.1451.811.621.631.751.862.23.04.15.92.23.04.12.31.743.12.34-3 最短路模型三、最短路问题构模举例例1 设备更新问题11.621.631.741.751.862.23.04.15.92.23.04.13.12.34-3 最短路模型三、最短路问题构模举例例1 设备更新问题11.621.631.741.751.862.23.04.15.92.23.04.13.12.31634501.62.23.04.15.95.75

15、.324-3 最短路模型三、最短路问题构模举例例2 施工方案选择问题 某建设工程还有四个项目没完成，根据需要希望该工程尽早投入使用。已知这四个项目在正常施工、采取一般措施施工和采取紧急措施施工情况下需要的时间和费用如下表：时间（月）项 目1 2 3 4 施工方式正常一般措施紧急措施5423253214-3 最短路模型三、最短路问题构模举例例2 施工方案选择问题 某建设工程还有四个项目没完成，根据需要希望该工程尽早投入使用。已知这四个项目在正常施工、采取一般措施施工和采取紧急措施施工情况下需要的时间和费用如下表：时间（月）项 目1 2 3 4 施工方式正常一般措施紧急措施542325321费用（

16、万元）123233412项 目1 2 3 4 施工方式正常一般措施紧急措施 已知这四个项目必须按顺序施工，为完成这四项工程的全部追加投资为10万元，问在投资允许范围内，如何安排施工，使全部工程尽早投入使用？4-3 最短路模型三、最短路问题构模举例例2 施工方案选择问题s,101,952,843,724,735,6236,5237,428, 459,33510,23511,13512,3213,21214,11215,012t0000最优施工方案即为从s至t的最短路径x-节点序号y-剩余的赶工费用T-项目持续时间xi,yixj,yjT工序2工序1工序3工序44-4 最大流模型一、最大流的有关概念

17、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)=vyf (x,y)f (y,x)(4) 收点平衡条件f (t,y)-f (y,t)= -vsf (y,s)f (s,y)t

18、f (y,t)f (t,y)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方向，Rs123ti(s,1)=2i(1,2)=4i(2,3)=5i(3,t)=34-4 最大流模型一、最大流的有关概念4.增值链(1) 从st全部由前向弧组成的路P(2) 从st全部由后向弧组成的路P

19、定义前向弧为st方向，I；后向弧为ts方向，Rs123tr(s,1)=3r(1,2)=2r(2,3)=4r(3,t)=14-4 最大流模型一、最大流的有关概念4.增值链(1) 从st全部由前向弧组成的路P(2) 从st全部由后向弧组成的路P(3) 从st即有前向弧又有后向弧组成的链P定义前向弧为st方向，I；后向弧为ts方向，Rs123tr(s,1)=3i(1,2)=4r(2,3)=4r(3,t)=24-4 最大流模型二、最大流的算法1.基本思路寻找st的增值链是否有？沿该链调整流量Y达到最大流N4-4 最大流模型二、最大流的算法2.确定增值链的方法开始有已标记未检查节点?选择相邻未标记节点y

20、YY选择已标记未检查节点xX有相邻未标记节点?N无增值链Nx为已检查节点对s标记21结 束t标记?找到增值链Y对y及弧(x,y)标记I、R类N2(x,y)类型?12N类结 束4-4 最大流模型二、最大流的算法3.最大流的标号算法开始对s标记为(-, )有已标记未检查节点?X有相邻未标记节点?选择相邻未标记节点y1YYNN选择已标记未检查节点x为最大流中止3=0 x为已检查节点2(x,y)类型?对y标记为(x+,(y)(y)= min (x),c(x,y)-f(x,y)t标记?改变流量(t)= + (t)取消全部标记R类NY1对y标记为(x-,(y)(y)=min(x),f(x,y)22N类I类

21、34-4 最大流模型二、最大流的算法3.最大流的标号算法S113429459t41055543654-4 最大流模型二、最大流的算法3.最大流的标号算法S113429459t4105554365S 1 2 3 4 5 t (-,)(s+,13)(1+,5)(4+,5)5(5(5)(54-4 最大流模型二、最大流的算法3.最大流的标号算法S 1 2 3 4 5 t (-,)(s+,13)(1+,5)(4+,5)5S113429459t4105554365(5(5)(5(-,)(s+,8)(1+,6)(3+,4)5+4=9,9(4(4)4-4 最大流模型二、最大流的算法3.最大流的标号算法S 1

22、2 3 4 5 t (-,)(s+,13)(1+,5)(4+,5)5(-,)(s+,8)(1+,6)(3+,4)5+4=9S113429459t4105554365(5(5)(5,9(4(4)(-,)(s+,4)(1+,2)(3+,2)(4+,2)9+2=11,11,6)(2,74-4 最大流模型二、最大流的算法3.最大流的标号算法S 1 2 3 4 5 t (-,)(s+,13)(1+,5)(4+,5)5(-,)(s+,8)(1+,6)(3+,4)5+4=9(-,)(s+,4)(1+,2)(3+,2)(4+,2)9+2=11S113429459t4105554365(5(5)(5,9(4(4

23、),11,6)(2,7(-,)(s+,2)(s+,9)(2+,5)(5+,5)11+5=16(5(5)(54-4 最大流模型二、最大流的算法3.最大流的标号算法S 1 2 3 4 5 t (-,)(s+,13)(1+,5)(4+,5)5(-,)(s+,8)(1+,6)(3+,4)5+4=9(-,)(s+,4)(1+,2)(3+,2)(4+,2)9+2=11(-,)(s+,2)(s+,9)(2+,5)(5+,5)11+5=16S113429459t4105554365(5(5)(5,9(4(4),11,6)(2,7(5(5)(5(-,)(s+,2)(s+,4)(2+,4)(3+,4)16+4=2

24、0(5+,4),9(4(4),9(-,)(s+,2)最大流=204-4 最大流模型三、多收点与多发点的修正StS1S2t1t2t3S1发量S2发量t1收量t2收量t3收量4-4 最大流模型四、最大流量最小截量定理在任一个网络D中,从s至t的最大流流量等于分离s、t的最小截集的容量。S12345t134959410554652220272321242323最小截面=204-4 最大流模型四、最大流量最小截量定理例：某高速公路的线路如下图，现拟建立足够数量的收费站，以使从s至t的每辆汽车至少必须通过一个收费站。建立收费站的费用如图所示，求最小费用解。s1234567t468252573843764

25、4-4 最大流模型四、最大流量最小截量定理例：某高速公路的线路如下图，现拟建立足够数量的收费站，以使从s至t的每辆汽车至少必须通过一个收费站。建立收费站的费用如图所示，求最小费用解。s1234567t468252573843764(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.算法原理逐

26、次找全程单位运费为0，1，2，的路径。2.算法步骤开始v0=?执行最大流算法所有f(x,y)=0,p(x)=0标记S,v0=0v0= v0 +结束YN未标记节点P(x)=p(x)+1计算总费用=v是否达到最大流其他注意：弧的分类作如下规定I: f(x,y)0 |p(y)-p(x)|=a(x,y)4-5 最小费用流模型二、最小费用流算法3.算法举例求图示网络 v=7和最大流时的最小费用s123t(4,10)(1,8)(2,5)(3,10)(6,2)(1,7)(2,4)迭代 p(s) p(1) p(2) p(3) p(t) 标记节点 标记边 0 0 0 0 0 0(a,b)容量单位运费迭代0：所有

27、弧Nss无 1 0 1 1 1 1迭代1：P(2)-p(s)=1 I2s,2 (s,2)未标记节点 p(x)=p(x)+1 (xs,2)未标记节点 p(x)=p(x)+1 (xs)2 0 2 1 2 2s,2 (s,2) 迭代2：未标记节点 p(x)=p(x)+1 (xs,2)4-5 最小费用流模型二、最小费用流算法3.算法举例求图示网络 v=7和最大流时的最小费用s123t(4,10)(1,8)(2,5)(3,10)(6,2)(1,7)(2,4)迭代 p(s) p(1) p(2) p(3) p(t) 标记节点 标记边 0 0 0 0 0 0(a,b)容量单位运费ss无 1 0 1 1 1 1

28、2s,2 (s,2)2 0 2 1 2 2s,2 (s,2) 迭代3：P(1)-P(2)=2 I 3 0 3 1 3 31未标记节点 p(x)=p(x)+1 (xs,1,2)s,2,1 (s,2) (2,1) 4-5 最小费用流模型二、最小费用流算法3.算法举例求图示网络 v=7和最大流时的最小费用s123t(4,10)(1,8)(2,5)(3,10)(6,2)(1,7)(2,4)迭代 p(s) p(1) p(2) p(3) p(t) 标记节点 标记边 0 0 0 0 0 0(a,b)容量单位运费ss无 1 0 1 1 1 12s,2 (s,2)2 0 2 1 2 2s,2 (s,2) 3 0

29、 3 1 3 31s,2,1 (s,2) (2,1) 4 0 3 1 4 4迭代4：P(t)-P(1)=1 I P(3)-P(2)=3 I3t857=5 v0=5 s,2,3 (s,2) (2,3) 未标记节点 p(x)=p(x)+1 (xs,2,3)4-5 最小费用流模型二、最小费用流算法3.算法举例求图示网络 v=7和最大流时的最小费用s123t(4,10)(1,8)(2,5)(3,10)(6,2)(1,7)(2,4)迭代 p(s) p(1) p(2) p(3) p(t) 标记节点 标记边 0 0 0 0 0 0(a,b)容量单位运费ss无 1 0 1 1 1 12s,2 (s,2)2 0 2 1 2 2s,2 (s,2) 3 0 3 1 3 3s,2,1 (s,2) (2,1) 4 0 3 1 4 43s,2,3 (s,2) (2,3) 迭代5：P(1)-P(s)=4 I1未标记节点 p(x)=p(x)+1 (xs,1,2,3)3t102=2 v0=5+2=7 5 0 4 1 4 5C=54+25=30s,1,2,3 (s,1)(s,2)(2,3)4-5 最小费用流模型二、最小费用流算法3.算法举例求图示网络 v=7和最大流时的最小费用s123t(4,10)(1,8)(2,5)(3,10)(6,2)(1,7)(2,4)迭代 p(s) p(1) p(2) p(