运筹学第三版第9章.ppt

《运筹学第三版第9章.ppt》由会员分享，可在线阅读，更多相关《运筹学第三版第9章.ppt（50页珍藏版）》请在三一办公上搜索。

1、第9章 网络计划,网络计划是一种使用网络分析的方法编制大型工程进度计划的技术，它对于工程计划人员和工程管理人员统筹组织各项活动、全面掌控工程进度、按期高效完成工程任务能起到重要作用，因而，在现代管理中得到了广泛的应用。网络计划技术主要包括网络图的绘制、时间参数的计算、关键路线的确定以及网络优化等，本章介绍这些内容。,9.1 网络图,网络计划分析中的网络图实质上是一种有时序的有向赋权图，表示一项工程从开始到完工的整个计划，反映了工程计划中活动的组成及相互关系，可以看做工序流程图。,9.1网络图,基本术语（1）工序（活动）：对于一项工程，根据技术和管理上的需要，将工程划分为按一定时序执行又相对独立

2、的一系列工作，这些工作称为工序（也称为活动）。在网络图中，工序用带标号的箭头表示，例如工序a表示为“”。,9.1 网络图,（2）紧前工序、紧后工序：工序b必须在工序a完工以后才能开始，则称工序a是工序b 的紧前工序，工序b称为工序a的紧后工序。（3）事项（结点）：表示一道或者多道工序的开工或完工的时间点叫做事项。事项本身不消耗时间和资源，只是标志某项工序的开始或结束。在网络图中，事项用带有标号的圆圈结点表示（为了包含尽可能多的信息，有时也用其他格式表示结点，例如表格型结点）。引入结点后，工序可以用结点组合表示，例如若工序a连接结点和，即，则工序a可以表示为（2,3）。,9.1 网络图,（4）路

3、线：网络图中的路线是指从始点事项到终点事项的由一系列工序连贯组成的一条路。在把一项工程分解为若干工序后，根据工序资料，可以列出工序一览表，就可以绘制网络图，进而进行相关分析了。,9.1 网络图,2.绘制网络图的规则（1）工序必须用具有唯一意义的结点组合表示，任何两道或多道工序的表示不能用同一结点组合。（2）网络图从左往右画，而且始点和终点只能各有一个。,9.1 网络图,（3）为了不违反上述规定，在必要时引入虚工序。虚工序不占用时间等资源，只是用来表达相邻工序间的衔接关系以及把始点和终点各自合并为一个等其他需要。在网络图上，虚工序用虚线表示。,9.1 网络图,（4）为了方便以后确定关键路线，规定

4、当某道工序有几个紧前工序平行作业时，选择其中工序时间最长的紧前工序与该工序实线连接，而与其他紧前工序通过虚工序用虚线连接。,9.1 网络图,另外，绘制网络图时要注意如下两点：不能有缺口，即除了起点和终点外，各道工序都必须前后衔接，否则从图上看不能经某工序到达终点。不能有循环，否则从图上看某道工序永远也完不成。最后需要说明的是，本章介绍的网络图是箭线式网络图，还有结点式网络图，感兴趣的读者可以参看有关文献。,10,例题 西部小山购物中心的改扩建工程,11,(1)画网络图 用结点表示活动（事项）,12,用弧表示活动（工序）,9.1 网络图,1）关键路线从起点到终点最长的路线称为关键路线；关键路线上

5、的工序称为关键工序；关键路线的路长就是整个工程的完工期；关键路线在网络图上可以用粗线、双线或红线等标注。,9.1 网络图,当网络图比较简单时，可以用全枚举法、破圈法找出关键路线。对大型工程的网络图，可以通过时间参数的计算来求得关键路线。,9.1 网络图,2）时间参数及其计算对每一项活动（工序）,设活动时间t 最早开始时间 ES 最早完成时间 EF=ES+t一项活动的ES等于它的所有紧前活动的EF的最大值。,16,最晚完成时间 LF:保证整个工期不变。最晚开始时间 LS:LS=LFt一项活动的LF等于它的所有紧后活动的LS的最小值。关键活动:ES=LS(EF=LF)松弛(时差):LSES 在不影

6、响总工期的条件下,活动可延迟开始(结束)的最大时间。,17,0 5,0 6,5 6,5 8,5 9,6 10,10 24,9 21,24 26,24 26,10 24,12 24,8 12,6 10,7 10,5 6,0 5,6 12,18,19,20,3）工序时间的三时估计法 活动时间不确定的项目安排,不确定活动时间的估计 乐观的估计时间 a 最可能的估计时间 m 悲观的估计时间 b假设估计时间服从分布 期望时间 方差,21,例2 道特公司新产品可行性研究项目,22,23,总时间T是一个随机变量,可以假设TN(,2),其中=tA+tE+tH+tI+tJ=17 2=1.78+0.11+0.69

7、+0.03+0.11=2.72=1.652,标准正态分布的分布函数,24,25,设TN(,2),9.2 网络的优化,实际的工程规划、管理中，不仅要求时间进度，往往需要考虑充分利用资源和降低费用，这就涉及按照不同目标寻求最优工程计划，即网络优化问题。,27,9.2 网络的优化,1.把串行工作改为平行工作或平行交叉工作例3,28,例4 A:挖沟 9天,B:埋管子 6天,29,2.合理分配有限资源,30,31,9.2 网络的优化,3.网络优化模型 对网络优化问题，可以通过建立数学规划模型并求解，而得出最优方案。本节介绍几个数学规划模型，假设赶工时产生的额外费用以及因缩短工期而节省的间接费用都与时间成

8、正比。,9.2 网络的优化,(1)最优工期模型 不考虑费用时，建立数学规划模型，确定最优工期，思想是让网络图中每个结点对应一个出现时间（决策变量），起点的出现时间为0，终点的出现时间就是完工期。令网络图起点编号为1，终点编号为n，所有箭线集合为A，用 表示箭线(i,j)代表工序的完成时间，工程的最早完工期记为。,9.2 网络的优化,在满足给定的工序完成时间约束下的数学规划模型为,9.2 网络的优化,(2)工期不超过 的最低直接费用模型 在已知各工序的最短完成时间、最长完成时间 以及费用斜率（即每减少一天产生的额外费用）的前提下，各工序的完成时间 为多少时，工程的完工期不超过。,9.2 网络的优

9、化,数学规划模型为,37,9.2 网络的优化,例5 两台机器维修,38,总工期是12天。希望10天完成,需要缩短工期2天。设一项活动 正常时间t,费用c 最短时间t,费用c 最大压缩时间M=tt 压缩一天所需费用K=(c c)/M,39,要求10天完成且费用尽可能地少,应如何安排?,40,设 xi:活动i的最早完成时间,yi:活动i的压缩时间。Min 100 yA+150 yB+200 yC+150 yD+250 yEs.t.xA 0+7 yA xB xA+3 yB xC 0+6 yC xD xC+3 yD xE xB+2 yE xE xD+2 yE xE10,yA3,yB1,yC2,yD2,

10、yE1 xi0,yi0 i=A,B,C,D,E最优解 yA*=1,yE*=1,9.2 网络的优化,(3)最小工程费方案模型 在已知各工序的最短完成时间、最长完成时间、费用斜率 以及工期每缩短一天节省的间接费用为 c的前提下，各工序的完成时间 为多少时，工程的总费用最低，完工期 是多少？,9.2 网络的优化,数学规划模型为,9.2 网络的优化,例6 已知某工程的工序数据如下表所示，而且已知工期每缩短一天节省的间接费用为6。,9.2 网络的优化,对该工程项目计划进行网络优化分析：（1）不考虑费用的情况下求出最优工期；（2）工期不超过12天的最低直接费用和方案；（3）求最小工程费用方案。,9.2网络的优化,(1)首先画出网络图如下:,建立如下的线性规划模型,用运筹学软件求得最优工期为,(2)建立如下的数学规划模型,9.2 网络的优化,用运筹学软件求得最优工期，最少的直接费用为8，；，。,(3)建立如下的数学规划模型,9.2 网络的优化,用运筹学软件求得最优工期，最少的直接费用为79，；，。,