运筹学网络计划.ppt

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

1、Chapter 7 网络计划Network Programming,7.1 绘制网络图 Draw network plot7.2网络参数 Network Parameter7.3 网络的优化 Optimization of Network,运 筹 学 Operations Research,7.1 绘制网络图 Draw network plot,2023/7/2,网络还是进行计划工作的有效工具,凡事“预则立”！,2023/7/2,横道图,优点：直观、易懂、便于检查缺点：不能反映相互之间联系和影响，无法找出关键工作。,2023/7/2,用网络图编制的计划称为网络计划，网络计划技术由计划协调技术（

2、Program Evaluation and Review Technique 简写为PERT）与关键路径法（Critical Path Method 简写为CPM）组成。,项目网络图的基本概念,PERT主要针对完成工作的时间不能确定而是一个随机变量时的计划编制方法，活动的完成时间通常用三点估计法，注重计划的评价和审查。,7.1 绘制网络图 Draw network plot,CPM以经验数据确定工作时间，看作是确定的数值，主要研究项目的费用与工期的相互关系。通常将这两种方法融为一体，统称为网络计划、网络计划技术(PERT/CPM)。,2023/7/2,网络计划主要应用于新产品研制与开发、大型

3、工程项目的计划编制与计划的优化，是项目管理和项目安排领域目前比较科学的一种计划编制方法，比甘特图（Cantt chart）或称横道图(bar chart)计划方法有许多优点。网络计划有利于对计划进行控制、管理、调整和优化，更清晰地了解工作之间的相互联系和相互制约的逻辑关系，掌握关键工作和计划的全盘情况。,PERT最早应用于美国海军北极星导弹的研制系统，由于该导弹的系统非常庞大复杂,为找到一种有效的管理技术,设计了PERT这种方法,并使北极星导弹的研制周期缩短了一年半时间。,CPM是与PERT十分相似但又是独立发展的另一种技术，是1957年美国杜邦公司的沃克（）和兰德公司的小凯利()共同研制的一

4、种方法。它主要研究大型工程的费用与工期的相互关系。,7.1 绘制网络图 Draw network plot,2023/7/2,【例7.1】（华罗庚：统筹方法平话及补充）某家庭有夫妇两人安排家务，要求从上午11：30开始到下午2：00结束去上班，做下例3件事：,工序 工时 代号洗衣 3小时 A烧饭 1小时 B吃饭 0.5小时 C,怎样安排，使完成时间最短？,4.5,3.5,7.1 绘制网络图 Draw network plot,2023/7/2,工序 或称为作业、活动，指任何消耗时间或资源的活动，如新产品设计中的初步设计、技术设计、工装制造等。根据需要，工序可以划分得粗一些，也可以划分得细一些。

5、,事件 标志工序的开始或结束，本身不消耗时间或资源，或相对作业讲，消耗量可以小得忽略不计。某个事件的实现，标志着在它前面各顶作业（紧前工序）的结束，又标志着在它之后的各项作业（紧后工序）的开始。如机械造业中，只有完成铸锻件毛坯后才能开始机加工；各种零部件都完成后，才能进行总装等。,虚工序 虚设的工序。用来表达相邻工序之间的衔接关系，不需要时间和资源。,7.1 绘制网络图 Draw network plot,2023/7/2,虚工序,不正确,3,1,2,B,A,C,正确,2023/7/2,虚工序,不正确,正确,A,B,A,C,D,E,2023/7/2,网络图 由工序、事件及标有完成各道工序所需时

6、间所构成的连通有向图。,路 从起点沿箭头方向到终点的有向路。,紧前工序 紧接某项工序的先行工序,紧后工序 紧接某项工序的后续工序,箭示网络图 用箭条表示工序的计划网络图。本章讲的就是箭示图,节点网络图 用节点表示工序的计划网络图,前道工序 某工序之前的所有工序,7.1 绘制网络图 Draw network plot,后续工序 某工序之后的所有工序,2023/7/2,在下图中，A是D、E的紧前工序，D、E是A的紧后工序，F是A的后续工序但不是A的紧后工序；A是D、E、F的前道工序但不是 F 的紧前工序。,注意紧前工序、紧后工序、前道工序和后续工序之间的关系。,7.1 绘制网络图 Draw net

7、work plot,2023/7/2,表7-1 工序明细表,A,B,C,D,G,E,F,H,40,50,30,20,50,25,20,20,图71（a）箭线图,7.1 绘制网络图 Draw network plot,【例7.1】某项目由8道工序组成，工序明细表见表7-1所示。分别用箭线法和节点法绘制该项目的项目网络图。,2023/7/2,表7-1 工序明细表,A,40,50,30,20,50,25,20,20,B,C,D,G,E,F,H,图71（b）节点图,7.1 绘制网络图 Draw network plot,2023/7/2,a,b,c,1.当工序a完工后b和c可以开工,3.工序c在工序a

8、完工后就可以开工，但工序d必须在a和b都完工后才能开工,a,c,b,d,2.当工序a和b完工后c和d可以开工,4.事件i、j之间有多道工序时，添加虚工序,(a),(c),(d),a,b,c,7.1.2 绘制网络图,7.1 绘制网络图 Draw network plot,2023/7/2,7.1 绘制网络图 Draw network plot,6.网络图只有一个发点（项目的开始点）一个收点（项目的结束点）。如图72（e）所示，则应合成图72（f）所示的一个始点及一个终点。,5.用弧(i，j)表示一道工序，事件i是工序的开始，事件j是工序的完成，规定i j。见下图,A,B,C,D,G,E,F,H,

9、40,50,30,20,50,25,20,20,2023/7/2,绘制网络图的步骤,1、分解任务，列出活动关系表2、做网络图3、结点编号,2023/7/2,分解任务，列出活动关系表,确定各活动的相互关系 紧前活动：只有活动A完成，才能开始活动B，则称A为B的紧前活动；紧后活动：B为A的紧后活动；平行活动；若活动开始进行时，活动C也可以同时进行，则称A和C为平行活动。确定每项活动的活动时间,2023/7/2,作网络图,按时间顺序从左到右地排列起始点在图的最左边，终点在图的最右边。,2023/7/2,结点编号分级编号法,零,二,一,二,三,三,四,1,2,4,3,5,6,7,2023/7/2,7.

10、1.3 工序时间的估计,均方差为,三点估计法是事先估计出工序的三种可能完成时间，其期望值就作为工序时间的估计值。三种时间是：(1)完成工序（i，j）的最短时间，称为乐观时间，记为aij(2)完成工序（i，j）的正常时间，称为最可能时间,记为mij(3)完成工序（i，j）的最长时间，称为悲观时间，记为bij三种时间发生的概率分别为1/6、4/6、1/6，则工序（i，j）完成时间的期望值和方差为：,7.1 绘制网络图 Draw network plot,2023/7/2,【例7.2】根据某项目作业明细表72的资料，绘制项目网络图,表72,【解】计划网络图如下：,7.1 绘制网络图 Draw net

11、work plot,a,6,1,b,9,c,13,d,5,e,16,f,12,h,12,g,10,i,8,k,20,j,17,l,25,图73(a)箭线网络图,1,2,3,5,4,6,7,10,8,9,11,2023/7/2,图73(b)节点网络图,7.1 绘制网络图 Draw network plot,【例7.3】根据下表作业明细表资料，绘制计划网络图,图74,2023/7/2,3.计划网络图的编制规则及其方法4.掌握 虚工序的用法5.编制网络图可以从左到右又可以从右到左或两边向中间画图6.网络图初稿完成后对照工序明细表验证紧前紧后工序关系是否正确,作业：教材P169 T 2,7.1 绘制网

12、络图 Draw network plot,1.本节的主要概念 网络计划、计划网络图、甘特图、PERT、CPM、结点图、箭示图、工序、事件、紧前工序、紧后工序2.区分紧前工序、紧后工序、前道工序和后续工序之间的关系,7.三种时间估计公式，工序的期望时间和方差,下一讲：网络参数,7.2 网络参数 Network Parameter,2023/7/2,（1）工序(i,j)的最早开始时间（Earliest start time for an activity）TES(i,j)。是指紧前工序的最早可能完工时间的最大值，计算公式为,（2）工序(i,j)的最早完工时间（Earliest finish tim

13、e for an activity）TEF(i,j)。计算公式为,7.2 网络参数 Network Parameter,时间参数公式及其含义,2023/7/2,(4)工序(i,j)的最迟必须结束时间(Latest finish time for an activity)TLF(i,j)。计算公式为,(3)工序(i,j)的最迟必须开始时间（latest start time for an activity）TLS(i,j)。是指为了不影响紧后工序如期开工，工序最迟必须开工的时间，计算公式为,7.2 网络参数 Network Parameter,2023/7/2,(6)工序的单时差或自由时间(Fr

14、ee for an activity)F(i，j)。在不影响紧后工序的最早开始时间的条件下，工序(i,j)的开始时间可以推迟的时间。计算公式为,(5)工序(i,j)的总时差或松弛时间(Slack for an activity)S(i,j)。是工序(i,j)的最迟开始(结束)时间与最早开始(结束)时间之差，计算公式为,7.2 网络参数 Network Parameter,2023/7/2,【例7.4】以网络图73为例。（1）在图上计算各工序的最早开始和最迟开始时间。（2）用表格计算工序的6个时间参数。（3）指出项目的关键工序和关键路线。（4）求项目的完工时间。,7.2 网络参数 Network

15、 Parameter,图75,a,6,1,11,b,9,c,13,d,5,e,16,f,12,h,12,g,10,i,8,k,20,j,17,l,25,0,0,0,6,6,9,9,19,19,35,19,19,47,47,47,47,55,72,72,55,52,47,47,52,52,47,42,35,37,19,6,23,23,14,0,0,【解】(1)最早开始和最迟开始时间见图75,2023/7/2,（2）表格形式见表7-5,表7-5,7.2 网络参数 Network Parameter,2023/7/2,a,6,1,11,b,9,c,13,d,5,e,16,f,12,h,12,g,10

16、,i,8,k,20,j,17,l,25,0,0,0,6,6,9,9,19,19,35,19,19,47,47,47,47,55,72,72,55,52,47,47,52,52,47,42,35,37,19,6,23,23,14,0,0,(4)工程的完工时间为72天,7.2 网络参数 Network Parameter,2023/7/2,工序时间是随机变量时，项目的完工期也是随机变量,设Xk为关键工序 k 所需时间的随机变量，则 Xk 相互独立，工序的期望时间及方差为,工程完工期的期望值及方差为,设关键工序数为n，工程的完工期是一随机变量,项目完工的概率,7.2 网络参数 Network Par

17、ameter,2023/7/2,则由李雅普诺夫中心极限定理知(式中n为关键工序数）,即当n很大时Zn近似服从N（0，1）分布，则有,近似服从,即,7.2 网络参数 Network Parameter,2023/7/2,设给定一个时间X0，则工程完工时间不超过X0的概率为,要使工程完工的概率为p0，至少需要多少时间X0,查正态分布表求出X，由,得,7.2 网络参数 Network Parameter,2023/7/2,a,7.17,1,b,7.83,c,12.17,d,17,e,10.17,f,23.33,h,25.67,g,35.33,i,17.33,j,33.67,【例7.5】对例7.3所示

18、的资料：（1）求工序的最早开始和最迟开始时间。（2）求工程完工期的期望值及其概率。（3）要求完工的概率为0.95,至少需要多少天。,0,0,0,0,7.17,7.17,12.17,12.17,12.17,35.5,29.17,17.34,35.5,69.17,69.17,69.17,33.84,43.5,51.84,35.5,69.17,12.17,26.5,23.67,16.5,18.67,0,0,图77,【解】(1)工序的最早开始和最迟开始时间见图77,26.5,26.5,7.2 网络参数 Network Parameter,2023/7/2,(2)关键工序是c、f 和j，由表7-4及式(

19、7.12)知，项目完工期的期望值、方差、标准差分别为 12.17+23.33+33.6769.1720.25+1.78+2.764.79，=2.1886,（3）X072，(X0)/=(7269.17)/2.1886=1.293,（4）已知概率p0=0.98，由式(7.15)，查正态分布表有,要使项目完工的概率为0.98，至少需要73.65天,7.2 网络参数 Network Parameter,2023/7/2,1.本节介绍了网络参数的计算，共有8个公式，现综合如下：,工序(i,j)的最早可能开工时间,工序(i,j)的最迟必须开工时间,工序(i,j)的最早可能完工时间,工序(i,j)的最迟必须

20、完工时间,工序(i,j)的总时差,工序的单时差 工序的完工期可推迟多少，以致不影响下道工序的最早开工时间：,7.2 网络参数 Network Parameter,2023/7/2,作业：教材P169 T 3，4，5,事件j 的最早时间表示以j为开工事件工序最早可能开工时间,事件 i 的最迟时间表示以i为完工事件工序最迟必须完工时间,下一讲：网络计划的优化与调整,2.三种时间估计公式，工序的期望时间和方差3.要求工程完工时间不超过X0时，求完工的概率p04.要使工程完工的概率为p0，求至少需要多少时间X0,7.2 网络参数 Network Parameter,7.3 网络的优化 Optimiza

21、tion of Network,2023/7/2,7.3.1 时间成本控制,7.3 网络的优化 Optimization of Network,正常时间（Normal Time）,正常成本(Normal Cost),应急时间(Crash Time),应急成本(Crash Cost),总成本总应急成本总应急收益 总正常成本总应急增加成本总应急收益,单位时间工序的应急增加成本(成本斜率)(应急成本正常成本)（正常时间应急时间）,2023/7/2,【例7.6】项目工序的正常时间、应急时间及对应的费用见表7-6。表中正常成本是在正常时间完成工序所需要的成本，应急成本是在采取应急措施时完成工序的成本。每

22、天的应急成本是工序缩短一天额外增加的成本,（1）绘制项目网络图，按正常时间计算完成项目的总成本和工期。（2）按应急时间计算完成项目的总成本和工期。（3）按应急时间的项目完工期，调整计划使总成本最低。（4）已知项目缩短1天额外获得奖金5万元，减少间接费用1万元，求总成本最低的项目完工期，也称为最低成本日程。,7.3 网络的优化 Optimization of Network,2023/7/2,【解】(1)项目网络图及时间参数见图78。项目的完工期为210天，将表7-6正常成本一列相加得到总成本为506万元,C,24,H,23,B,21,E,26,D,25,J,18,G,28,A,19,F,25,

23、I,27,L,28,12,K,35,M,30,13,N,25,11,O,0,0,0,19,40,40,40,66,64,66,89,112,139,210,0,139,157,185,174,210,185,157,180,145,139,112,84,89,64,40,84,59,58,19,0,图78,7.3 网络的优化 Optimization of Network,2023/7/2,C,22,H,23,B,19,E,24,D,23,J,14,G,23,A,15,F,23,I,26,L,25,12,K,30,M,26,13,N,20,11,O,0,0,0,15,34,34,34,58,5

24、6,58,79,102,128,187,0,128,142,167,158,187,167,142,161,131,128,102,79,79,56,34,79,56,55,15,0,图79,（2）项目网络图不变，时间参数见图79，完工期187天，将表7-6应急成本一列相加得到总成本为713万元,7.3 网络的优化 Optimization of Network,2023/7/2,(3)图79中，非关键工序是D、E、G、K和M，可以看出，将工序D、E、G按正常时间施工时，最早开始和最迟开始时间不相等，说明按正常时间施工不影响项目的完工期（187天），见图710(a)。工序K和M按正常时间共要缩

25、短时间6天，见图710(b)。,E,26,D,25,G,28,O,0,34,34,60,60,79,79,54,53,12,K,35,M,30,13,J,14,L,25,13,N,20,11,应急时间路长：59,正常时间路长：65,12,K,30,M,26,13,应急时间路长：56,图710,(a),(b),7.3 网络的优化 Optimization of Network,2023/7/2,则最优的决策方案是：关键工序A、B、C、F、H、I、J、L、N全部按应急时间施工，总成本等于各工序应急成本之和；工序D、E、G按正常时间施工，成本等于各工序正常成本之和；工序K缩短5天工序M缩短1天，成本

26、等于正常成本加应急时间增加的成本。按项目完工期187天施工的最小成本是654万元，成本分析见表7-7。调整后有两条关键路线，见图711,C,22,H,23,B,19,E,26,D,25,J,14,G,23,A,15,F,23,I,26,L,25,12,K,30,M,29,13,N,20,11,O,0,0,0,15,34,34,34,60,56,60,79,102,128,187,0,128,142,167,158,187,167,142,158,128,128,102,79,79,56,34,79,56,53,15,0,图711,7.3 网络的优化 Optimization of Networ

27、k,2023/7/2,(4)考虑缩短关键工序的时间，选择一天应急增加的成本小于等于6的关键工序采取应急措施来缩短时间，这样的工序有C、J、N，工序C缩短2天，工序J缩短4天，工序N缩短2天。对图78进行第一次调整得到图712。得到两条关键路线，工序K和M变为关键工序，项目完工期为202天，缩短了8天。总成本变动额为:2341228634（万元）,C,22,H,23,B,21,E,26,D,25,J,14,G,28,A,19,F,25,I,27,L,28,12,K,35,M,30,13,N,23,11,O,0,0,0,19,40,40,40,66,62,66,87,110,137,202,0,1

28、37,151,179,172,202,179,151,172,137,137,110,82,87,62,40,82,57,56,19,0,图712,7.3 网络的优化 Optimization of Network,2023/7/2,检查图712虚线围起来的部分。要缩短工期必须两条关键路线同时缩短时间，上面一条路线工序N还能缩短3天，因此下面一条路线只对工序K缩短3天，对图712调整得到图713。项目的完工期为199天，又缩短了3天，总成本变动额为 3232366（万元）,C,22,H,23,B,21,E,26,D,25,J,14,G,28,A,19,F,25,I,27,L,28,12,K,3

29、2,M,30,13,N,20,11,O,0,0,0,19,40,40,40,66,62,66,87,110,137,199,0,137,151,179,169,199,179,151,169,137,137,110,82,87,62,40,82,57,56,19,0,图713,继续检查发现，缩短任何关键工序都不能降低成本，则总成本最低的项目工期是199天，总成本为 506346466（万元）,7.3 网络的优化 Optimization of Network,2023/7/2,7.3.2 资源的合理配置,(1)资源一定，如何组织、安排和调配资源保证项目按期完成。(2)资源不足时，如何协调内部资

30、源和采取应急措施(加班、雇工、增加设备、改进施工工艺)保证项目按期完成。(3)资源、时间和成本的整体调整和系统优化,【例7.7】项目各工序的时间和资源如表78所示,（1）绘制项目网络图，按正常时间计算项目完工期，按期完工最多需要多少人。（2）保证按期完工，怎样采取应急措施，使总成本最小又使得总人数最少，对计划进行系统优化分析。,7.3 网络的优化 Optimization of Network,2023/7/2,表78,7.3 网络的优化 Optimization of Network,2023/7/2,【解】（1）项目网络图及最早最迟开始时间见图714。项目完工期为40天。关键工序是A、D、

31、E和G，非关键工序是B、C、F，总时差都等于9，也是工序B、C、F的全部机动时间。,A,10,B,8,D,7,C,10,E,10,F,3,G,13,H,0,0,0,0,10,10,18,17,27,28,40,40,37,27,17,10,19,0,图714,27,7.3 网络的优化 Optimization of Network,2023/7/2,从图715看出，如果非关键工序都按最早时间开始，第11天到第28天是用工高峰期，第19天到第27天为40人，按此计划施工需要40人,图715,7.3 网络的优化 Optimization of Network,2023/7/2,将工序B按最早时间开

32、始，工序C、F按最迟时间开始，调整后最多需要32人，见图7-16。,图716,7.3 网络的优化 Optimization of Network,2023/7/2,（2）由图716，只有1天时间需要32人，对计划整体优化可以从以下几个方案考虑。第一，对工序B或E采取应急措施，缩短工序时间1天，能够使总人数降到27人，由表78知，工序B一天的应急成本比工序E低，因此工序B缩短1天，第17天完工，增加成本10万元。第二，如果项目完工期推迟1天完工的成本比工序B的应急成本低，可以考虑对关键工序E推迟一天开始，即第20天开始，项目完工期为41天。第三，从图716看出,人员并没有均衡利用,在某个时间段内就可以利用富裕的资源到关键工序，缩短关键工序的时间，而在用工高峰期时将缩短的关键工序时间用到其它工序上。第四，均衡利用资源，综合评价与审核。当资源、时间和成本可以相互转化和替代时，制定评价标准，确定多个目标的优先次序，是成本优先、工期优先还是资源优先，综合评价与审核，经过反复调整与优化，得到满意的计划方案后，作出项目施工决策。,7.3 网络的优化 Optimization of Network,