第5章图与网络模型.ppt

《第5章图与网络模型.ppt》由会员分享，可在线阅读，更多相关《第5章图与网络模型.ppt（94页珍藏版）》请在三一办公上搜索。

1、1,第五章图与网络模型,1图与网络的基本概念2最短路问题3最小生成树问题4最大流问题5车间作业计划6统筹法（网络规划）,图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉，它有200多年历史，大体可划分为三个阶段：第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题为游戏而产生，最有代表性的工作是所谓的Euler七桥问题(1736年)，即一笔画问题。,第二阶段是从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如Hamilton问题，地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如Cayley把树应用于化学领域，Kirchhoff用树去研

2、究电网络等.,第三阶段是二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。,例10-1：哥尼斯堡七桥问题 哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？,A,B,C,D,最后，数学家Euler在1736年巧妙地给出了这个问题的答

3、案，并因此奠定了图论的基础，Euler把A、B、C、D四块陆地分别收缩成四个顶点，把桥表示成连接对应顶点之间的边，问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。,A,C,B,D,有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。,1,2,3,7,6,4,5,假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,1,2,3,7,6,4,5,1,2,3

4、,7,6,4,5,假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,哈密顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而

5、且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。,22,1图与网络的基本概念,图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，下图就是一个表示这种关系的图。,23,1图与网络的基本概念,当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以表示如下，可见图论中的图与几何图、工程图是不一样的。,24,1图与网络的基本概念,如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那

6、么只用两点之间的联线就很难刻画他们之间的关系了，这时我们引入一个带箭头的联线，称为弧。下图就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。,25,1图与网络的基本概念,无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。回路：若路的第一个点和最后一个点相同，则该路为回路。赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中

7、间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。,26,2最短路问题,最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。解最短路的Dijkstra算法(双标号法）步骤：1.给出点V1以标号(0,s)2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合3.如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则 vs到vt的距离为lt，而从 vs到vt的最短路径，则可以从kt 反向追踪到起点vs 而得到

8、。如果vt 未标号，则可以断言不存在从 vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。4.对上述弧的集合中的每一条弧，计算 sij=li+cij。在所有的 sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。,最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局等，而且经常被作为一个基本工具，用于解决其它的优化问题.定义 给定一个赋权有向图D=(V,A)，记D中每一条弧 上的权为为。给定D中一个起点 和 终点，设P是D中从 到 的一条路.则定义路P的权是P中所有弧

9、的权之和.记为，即 又若P*是D图中 到 的一条路，且满足 则称P*为从 到 的最短路。,28,最短路问题 网络：规定起点、中间点和终点的赋权图；有向网络：网络中每个边都是有向边；无向网络：网络中每个边都是无向边；混合网络：网络中既有有向边，又有无向边；网络最短路线问题：寻找网络中从起点 v1 到终点 vn 的最短路线。Min L()=lij 为从 v1 到 vn 的通路；lij 其中，lij为从 vi 到 vj 的一步距离。,29,结合例题学习、掌握求最短路的狄克斯拉、海斯和福德三个方法：1、狄克斯拉方法：适用于满足所有权系数大于等于0（lij0）的网络最短路问题，能求出起点 v1 到所有其

10、它点 vj 的最短距离；2、海斯方法：基本思想是在最短路线上任意两点间路线也是最短路线。利用 vi 到 vj 的一步距离求出 vi 到 vj 的两步距离再求出 vi 到 vj 的四步距离经有限次迭代可求出 vi 到 vj 的最短距离；3、福德方法：适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离。,30,2最短路问题,例1 求下图中v1到v6的最短路解：采用Dijkstra算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下：,31,网络最短路线问题：寻找网络中从起点 v1 到终点 vn 的最短路线。标注 vk(lk，k-1)

11、定义：k=1时，l1=0，k-1=s，v1(0，s）min(lij)Min L()=lij 为从 v1 到 vn 的通路；lij 其中，lij为从 vi 到 vj 的一步距离。,最短路问题,32,2最短路问题,例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标

12、号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。,33,2最短路问题,例2最终解得：最短路径v1 v3 v5 v6 v7，每点的标号见下图,（0,s）V1（甲地）,15,17,6,2,4,4,3,10,6,5,(13,3)v2,(22,6)V7（乙地）,V5(14,3),V6(16,5),V3(10,1),V4(18,5),例设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要负购买费。试确定一个5年计划，使总支出最小。若已知设备在各年的购买费，及不同机器役龄时的残值与维修费。,解：把这个问题化为最

13、短路问题。,设bi 表示设备在第i 年年初的购买费,ci 表示设备使用i 年后的维修费,V=v1,v2,v6,点vi表示第i 年年初购进一台新设备,虚设一个点v6表示第5年年底.E=vivj|1ij6.,2最短路问题,35,2最短路问题,例的解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。把所有弧的权数计算如下表：,若每年购置一台新设备，则购置费为：11+11+12+12+13=59，每年的维修费为5元，共59+5*5=84.若在1，2，3年购置一台新设备，则购置费为：11+12+13=36，每年的维修费

14、为（5+6）+（5+6）+5=27，共36+27=63.设备使用一年后就更新则不划算。由表知，设备使用三年后应当更新。,这样上述设备更新问题就变为：在有向赋权图G=(V,E,F)(图解如下)中求v1到v6的最短路问题.,由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5,v1到v6,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6 五条连线后得到,从上图中容易得到v1到v6只有两条路：,v1v3v6（费用22+31）和v1v4v6（费用22+31）.,而这两条路都是v1到v6的最短路.,39,3最小生成树问题,树是

15、图论中的重要概念，所谓树就是一个无圈的连通图。,图中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。,40,3最小生成树问题,给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图中，(b)和(c)都是(a)的生成子图。如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在图中，(c)就是(a)的生成树。最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。,(a),(b),(c),41,3最小生成树问题,求解最小生成树的破圈

16、算法算法的步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。,42,3最小生成树问题,例 用破圈算法求图（a）中的一个最小生成树,43,3最小生成树问题,例、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。,解：此问题实际上是求最小生成树，这在例中已经求得，也即按照图的(f)设计，可使此网络的

17、总的线路长度为最短，为19百米。“管理运筹学软件”有专门的子程序可以解决最小生成树问题。,44,4最大流问题,最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。最大流的数学模型 例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？,v5,45,4最大流问题,我们可以为此例题建立线性规

18、划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：,46,4最大流问题,在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0fij cij。我们把满足守恒条件及流量可行条件的一组网络流 fij称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。我们把

19、例6的数据代入以上线性规划模型，用“管理运筹学软件”，马上得到以下的结果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最优值（最大流量）=10。,47,5车间作业计划模型,一、一台机器、n个零件的排序问题 例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？,48,5车间作业计划模型,例1解：如果我们用Pi表示安排在第i位加工的零件所

20、需的时间，用Tj表示安排在第j位加工的零件在车间里总的停留时间，则有 Tj=P1+P2+Pj-1+Pj=不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为Tj，Tj=可知这六个零件的停留时间为：T1+T2+T3+T4+T5+T6 P1+(P1+P2)+(P1+P2+P3)+(P1+P2+P3+P4)+(P1+P2+P3+P4+P5)+(P1+P2+P3+P4+P5+P6)6 P1+5 P2+4P3+3P4+2P5+

21、P6.那么各个零件平均停留时间为 从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。,49,5车间作业计划模型,二、两台机器、n个零件 例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如表12-5所示。表-1 应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样

22、的。如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图12-1中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和车床、磨床在每个时间段的状况的图形所构成。,50,5车间作业计划模型,图 1 从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法。,51,5车

23、间作业计划模型,寻找例2的最优解：我们在表12-5中找到所列出的最短加工时间是0.25,它是第二道工序磨床加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五位，并在表中划去零件2 所在行。如表12-6中红色线条所示。接着，我们又找到最短加工时间为0.5，这一时间与磨床（第二工序）有关，我们把 磨床加工时间为0.5的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把 表中的零件1所在的行划去。如表12-6中黄色线条所示。下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件5的所需时间，故把零件5排在加工顺序的第一位上，同时把表中的零件5所

24、在的行划去。如表12-6中蓝色线条所示。,表-2,52,同样，下一个最短加工时间为1，这是车床加工零件3的所需时间，故把零件3排在第二位上，同时把零件3所在的行划去。如表12-6中黑色线条所示。这样就得到了最优加工顺序：5，3，4，1，2。一共只需7个小时就能完成全部加工。从例2中我们可以归纳出关于两台机器n个零件的排序问题，使得全部任务总的时间 最短的排序算法。在加工所需时间表上选出最短加工时间tij，这是第i工序加工j零件所需时间，当i=1时，将零件j的顺序尽量靠前，若i=2时，将零件j的顺序尽量靠后。在表上划去零件j的所在行，回到步骤1。,5车间作业计划模型,基本概念杜邦公司关键路线法C

25、PM 确定型美国海军武器局计划评审技术PERT网络图（有向赋权图）的构成结点，也称事项，一道工序的开始或结束工序（弧），相对独立的活动，消耗资源虚工序，只表示衔接关系，不消耗资源工序时间（权），完成工序的时间消耗,6统筹方法,网络规则,1、避免循环、不留缺口2、一一对应：一道工序用两个事项表示3、从左向右依次展开例：,A,4,B,6,D,7,E,5,F,9,H,4,I,8,C,6,G,7,关键路线法 CPM,时间参数运算 什么是关键路线？1、作业时间t（i，j），经验数据、统计数据2、事项最早时间TE(j)maxTE(i)+t（i，j）到齐上课，最后到者决定最早开课时间3、事项最迟时间TL(i

26、)minTL(j)-t（i，j）保证12点吃饭，路最远者决定最迟下课时间4、工序最早可能开工时间 TES(i,j)TE(i)=maxTES(h,i)+t（h,i）5、工序最早可能完工时间 TEF(i,j)TES(i,j)+t（i，j）,6、工序最迟必须开工时间 TLS（i,j)TL(j)t（i,j)minTLs(j,k)-t（i，j）7、工序最迟必须完工时间 TLF（i,j)TL(j)TLS（i,j)+t（i,j)8、工序总时差：在不影响其紧后工序最迟必须开工时间的前提下，本工序可以推迟的时间 R（i,j）TLS(i,j)TES(i,j)TLF(i,j)TEF(i,j)minTLS(j,k)T

27、EF（i,j）9、工序单时差：在不影响其紧后工序最早可能开工时间的前提下，本工序可以推迟的时间 r（i,j）minTES(j,k)TEF（i,j）,计算关系式,这些时间参数的关系可以用下图表示工作的关系状态。,时间参数图解,.解上例：计算事项 时间参数,.解上例：计算事项 时间参数,TES,TLS,TEF,TLF,TES,TLS,TEF,TLS,r(i,j),R（i,j）,A4,B6,C6,G7,D7,E5,F9,H4,I 8,0,0,4,7,6,13,22,20,28,28,20,24,13,6,关键路线：由总时差为零的工序构成 B D G I,t（i,j),t（j,k),解上例 计算工序时

28、间参数,60,6统筹方法,统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进行分别讨论：一、计划网络图 统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。例3、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表-3所示，请画出其统筹方法网络图。表-3,61,6统筹方法,解:用网络图表示上述的工序进度表 网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，

29、下面标以完成此工序所需的时间（或资源）等数据，即为对此弧所赋的权数,a,b,c,d,e,60,13,8,38,15,图-4,62,6统筹方法,例、把例的工序进度表做一些扩充，如表1-5，请画出其统筹方法的网络图。表-5,63,6统筹方法,解：我们把工序 e 扩充到图5发生了问题，由于是 e 的紧前工序，故的结束应该是 e 的开始，所以代表 e 的弧的起点应该是，由于工序的结束也是，所以工序也成了工序 e 的紧前工序，与题意不符。为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。,1,5,2,6,4,3,a,60,b,15,8,e,

30、10,13,d,c,38,f,图-5,64,6统筹方法,在网络图上添加、工序得网络图-6。在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图-7。,1,2,5,6,7,3,4,a,60,15,b,e,c,13,d,38,8,h,5,10,f,g,16,图-6,65,6统筹方法,在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。,1,2,5,7,8,3,4,a,60,15,b,e,c,13,d,38,8,h,5,10,f,6,16,g,图12-7,66,6统筹方法,二、网络时间与关键路线 在绘制出网络图之后，我们可以由网络图求出：1、完成此工程项目所需的最少时间。2

31、、每个工序的开始时间与结束时间。3、关键路线及其应用的关键工序。4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。例5、某公司装配一条新的生产线，具体过程如表-10,求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。,67,6统筹方法,表-10,68,6统筹方法,解：据表-10,绘制网络图如图-8。图-8 如图-8,-就是一条关键路线，我们要干完所有的工序就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最长的路线就决定了完成整个工程所需的最少时间，这条路

32、线称为关键路线。,1,2,3,4,6,7,8,5,a,60,b,45,e,c,h,j,35,i,g,10,30,d,20,40,25,f,18,15,69,6统筹方法,下面我们给出找关键路线的办法 首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间（ES)和最早结束时间（EF)，设一个工序所需的时间为t，这对于同一个工序来说，有 EF=ES+t。,工序a的最早开始时间,工序a的最早完成时间,1,1,a0，60,60,图9,70,6统筹方法,图10 其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF),显然对同一

33、工序有 LS=LF-t,1,2,3,6,7,8,5,a0,60,60,b60,105,45,e60.100,c60,70,h100,115,j135,170,35,i110.135,g80,110,30,d60.80,20,40,25,f70,88,18,4,10,15,71,6统筹方法,运用此法则，可以从首点开始计算出每个工序的LF与LS，如图12-11所示。接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的时差，对每个工序来说其时差记为Ts有 Ts=LS-ES=LF-EF,1,2,3,6,7,8,5,a0,60,6

34、00,60,b60,105,4590,135,e60.100,c60,70,h100,115,j135,170,35135,170,i110.135,g80,110,3080,110,d60.80,2060,80,4080,120,25110,135,f70,88,18117,135,4,10107,117,15120,135,72,6统筹方法,最后将各工序的时差，以及其他信息构成工序时间表如表所示。这样就找到了一条由关键工序a,d,g,i和j依次连接成的从发点到收点的关键路线。,73,三、完成工序所需时间与关键路线 当完成工序所需时间不确定的情况下如何求网络时间和关键路线？例6.长征研究院培

35、训中心负责明年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息，要求绘制出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。解：由表，绘出统筹方法的网络图如图-12所示。,图-12,6统筹方法,74,6统筹方法,75,6统筹方法,由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：1.乐观时间。指所需最少时间，用a表示。2.最可能时间。指正常时间，用m表示。3.悲观时间。指不顺利情况下，最多时间，用b表示。如表-13所示：表-13 单位：周,计划评审技术PERT,PERT的产生 关键路线法中，工序

36、时间是确定值，而对研究性的工序来说，t（i，j）是随机的。1958年美国海军武器局研制北极星导弹时提出，重点在于计划的评审。PERT的时间估计 采用三种时间估计法a最乐观时间，b最悲观时间，m最可能时间，则 工序期望时间 te 方差 e2（）2,a+4m+b,6,ba,6,77,6统筹方法,显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从 分布。我们可以用如下公式计算出完成活动所需的平均时间：以及方差 例如：完成工作g所需平均时间：同时求出方差为,78,6统筹方法,同样可以求出每个活动的完成所需平均时间及方差，如表12-14：表12-14,79,6统

37、筹方法,下面就用平均时间代替完成活动所需时间，并在网络图上标上每个活动最早开始时间和最早结束时间，如图12-14所示。,1,2,3,4,5,8,7,6,同样也可以标上最晚开始时间和最晚完成时间等。,a0,2,g5,9,b2,5,e5,6,d2,4,f6,8,c0,2,i13,15,h9,13,3,2,2,2,1,4,2,4,2,1,2,3,4,5,8,7,6,a0,2,g5,9,b2,5,e5,6,d2,4,f6,8,c0,2,i13,15,h9,13,21,3,110,11,45,9,49,13,23,5,20,2,32,5,213,15,211,13,图12-14,图12-15,80,6统

38、筹方法,从表12-15上我们找到了一条从发点到收点由关键工序a,b,g,h,i组成的关键路线，用双线标出来。则完成培训工作所需的平均时间为各关键路线的时间之和：=2+3+4+4+2=15（周）同时完成时间近似服从一定的概率分布正态分布，则均值为关键路线上各关键活动之均值之和15，方差也为关键路线上各关键活动方差之和1.05。由此我们可以计算出此项培训组织工作不同完工时间的概率，如16周内完工的概率。为求此概率，可以先求u值。式中的T为预定完工时间16，E（T）=15，算得u=0.976。查正态分布函数表可知概率为0.8355。即16周内完工的概率为83.55%.,81,6统筹方法,其正态分布图

39、如图12-16所示：,16,图12-16,82,6统筹方法,四、网络优化 得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划方案。1.时间-资源优化 做法：1）优先安排关键工序所需的资源。2）利用非关键工序的时差，错开各工序的开始时间。3）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。下面列举一个拉平资源需要量最高峰的实例。在例5中，若加工工人为65人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间-资源最优方案。如表-16所示：,83,6统筹方法,表-16,若上述工序都按最早开始时间安排，那么从第6

40、0天至第135天的75天里，所需的机械加工工人人数如图-17所示。,84,6统筹方法,在图的上半部中，工序代号后的数字是人数，线下面的数字是非关键工序时差长度。图的下半部表示从第60天至135天内的75天里，所需机械加工工人数，这样的图称为资源负荷图。,2,7,4,6,3,5,f(22人）,18,h(39人),15,58人,64人,80人,81人,42人,26人,65人,60 80 100 120 130,d(58人）,i(26人）,g(42人）,30,20,25,图12-17,85,6统筹方法,同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需

41、要量的高峰。经过调整，我们让非关键工序f从第80天开始，工序h从第110天开始。找到了时间-资源优化的方案，如图12-18所示，在不增加工人的情况下保证了工程按期完成。,2,4,6,7,5,3,f(22人）,h(39人）,d(58人）,i(26人）,g(42人）,工人数,65人,60 80 100 120 130,58人,42人,64人,26人,65人,图12-18,86,6统筹方法,2.时间-费用优化 需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间-费用优化要研究和解决的问题。直接费用：为了加快工程进度，需要

42、增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序越短，直接费用越多，间接费用越少。,87,6统筹方法,工序的最快完成时间：指完成时间的最高限度。我们设完成工序j的正常所需时间为Tj;直接费用为cj;完成工序j的最快完成时间为Tj,直接费用为cj。这样我们可以计算出缩短工序j的一天工期所增加的直接费用，用kj表示，称为直接费用变动率。有 时间-费用优化问题可建立两个线性规划模型。模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。设工序（i,j)的提前完工时

43、间为Yij,我们用Tij,Tij分别表示正常完工时间与最快完工的时间，则有工序（i,j)的实际完工时间为：Tij-Yij。我们用Cij,Cij表示用正常完工时间和最快完成时间完成工序所需要的费用，Kij为工序（i,j)的直接费用变动率。得到这个问题的线性规划模型如下：minf=（Kij*Yij)（i,j)S.t.Xj-Xi Tij-Yij,对一切弧（i,j)Yij Tij-Tij,对一切弧（i,j)Xn-X1 T,Xi 0，Yij 0。,88,6统筹方法,例7.例5所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的

44、所需的直接费用和每缩短一天工期所需增加的直接费用，如表12-17所示。表12-17,89,6统筹方法,该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要求在140天完工呢？,1,2,3,4,5,6,7,8,a,b,f,e,c,h,g,i,j,d,图12-19,90,6统筹方法,解：绘出如图12-19所示，根据此网络图建立数学模型。设此网络图上第i点发生的时间为xi，工序提前完工的时间为yij。目标函数minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y6

45、7.s.t.x2-x1 60-y12,x7-x2 45-y27 x3-x210-y23 x4-x220-y24 x5-x240-y25 x7-x318-y37 x6-x430-y46 x5-x40虚拟弧（4，5）x7-x515-y57 x7-x625-y67,91,6统筹方法,x1=0,y120,y2715,y23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y78 0 x8 150 xi 0，yij 0.（对一切可能的ij)运算得到结果：f=6400。,92,6统筹方法,模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费用却会随着完成时间的缩短而减少，设单位

46、时间的间接费用为d,计划期的间接费用与总工期成正比，即为d(xn-x1),那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间的模型为：目标函数min f=d(xn-x1)+s.t.xj-xi Tij-yij，对一切弧（i,j)yijTij-Tij，对一切弧（i,j)xi 0，yij 0。,93,6统筹方法,例8 如果在例7中，每天的间接费用为330元，求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间。解：决策变量的含义同例7。此数学模型的目标函数为：min f=330(x8-x1)+120y27+300 y23+

47、400y24+500y25+230y37+350y46+290y67 此模型的约束条件与例7的约束条件基本相同，只要在例子的约束条件中去掉x8 150就得到了例8模型的约束条件了。计算得到以下结果：f=55700.x1=0,y12=0,y67=10,x2=60,y27=0,y78=0.,94,6统筹方法,x3=125,y23=0,x4=107,y24=0,x5=110,y25=0,x6=110,y37=0,x7=125,y46=0,x8=160,y57=0,也就是说整个工程工期为160天时总费用最少为55700元，各个工序开始时间如解所示，工序 i 要提前10天完工，其余的工序按正常时间完工。,