学习运筹学—网络计划培训讲学

Chapter 7 网络计划 Network Programming,7.1 绘制网络图 Draw network plot 7.2网络参数 Network Parameter 7.3 网络的优化 Optimization of Network,运 筹 学 Operations Research,7.1 绘制网络图 Draw network plot,用网络图编制的计划称为网络计划，网络计划技术由计划协调技术（Program Evaluation and Review Technique 简写为PERT）与关键路径法（Critical Path Method 简写为CPM）组成。,7.1.1项目网络图的基本概念,PERT主要针对完成工作的时间不能确定而是一个随机变量时的计划编制方法，活动的完成时间通常用三点估计法，注重计划的评价和审查。,7.1 绘制网络图 Draw network plot,CPM以经验数据确定工作时间，看作是确定的数值，主要研究项目的费用与工期的相互关系。通常将这两种方法融为一体，统称为网络计划、网络计划技术(PERT/CPM)。,【例7.1】（华罗庚：统筹方法平话及补充）某家庭有夫妇两人安排家务，要求从上午11：30开始到下午2：00结束去上班，做下例3件事：,工序 工时 代号 洗衣 3小时 A 烧饭 1小时 B 吃饭 0.5小时 C,怎样安排，使完成时间最短？,4.5,3.5,7.1 绘制网络图 Draw network plot,工序 或称为作业、活动，指任何消耗时间或资源的活动，如新产品设计中的初步设计、技术设计、工装制造等。根据需要，工序可以划分得粗一些，也可以划分得细一些。,事件 标志工序的开始或结束，本身不消耗时间或资源，或相对作业讲，消耗量可以小得忽略不计。某个事件的实现，标志着在它前面各顶作业（紧前工序）的结束，又标志着在它之后的各项作业（紧后工序）的开始。如机械造业中，只有完成铸锻件毛坯后才能开始机加工；各种零部件都完成后，才能进行总装等。,虚工序 虚设的工序。用来表达相邻工序之间的衔接关系，不需要时间和资源。,7.1 绘制网络图 Draw network plot,网络图 由工序、事件及标有完成各道工序所需时间所构成的连通有向图。,路 从起点沿箭头方向到终点的有向路。,紧前工序 紧接某项工序的先行工序,紧后工序 紧接某项工序的后续工序,箭示网络图 用箭条表示工序的计划网络图。本章讲的就是箭示图,节点网络图 用节点表示工序的计划网络图,前道工序 某工序之前的所有工序,7.1 绘制网络图 Draw network plot,后续工序 某工序之后的所有工序,在下图中，A是D、E的紧前工序，D、E是A的紧后工序，F是A的后续工序但不是A的紧后工序；A是D、E、F的前道工序但不是 F 的紧前工序。,注意紧前工序、紧后工序、前道工序和后续工序之间的关系。,7.1 绘制网络图 Draw network plot,表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所示。分别用箭线法和节点法绘制该项目的项目网络图。,表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,a,b,c,1.当工序a完工后b和c可以开工,3.工序c在工序a完工后就可以开工，但工序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,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,40,50,30,20,50,25,20,20,7.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,【例7.2】根据某项目作业明细表72的资料，绘制项目网络图,表72,【解】计划网络图如下：,7.1 绘制网络图 Draw network 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,图73(b)节点网络图,7.1 绘制网络图 Draw network plot,【例7.3】根据下表作业明细表资料，绘制计划网络图,图74,3.计划网络图的编制规则及其方法 4.掌握 虚工序的用法 5.编制网络图可以从左到右又可以从右到左或两边向中间画图 6.网络图初稿完成后对照工序明细表验证紧前紧后工序关系是否正确,作业：教材P169 T 2,7.1 绘制网络图 Draw network plot,1.本节的主要概念 网络计划、计划网络图、甘特图、PERT、CPM、 结点图、箭示图、工序、事件、紧前工序、紧后工序 2.区分紧前工序、紧后工序、前道工序和后续工序之间的关系,7.三种时间估计公式， 工序的期望时间和方差,下一讲：网络参数,7.2 网络参数 Network Parameter,（1）工序(i,j)的最早开始时间（Earliest start time for an activity）TES(i,j)。是指紧前工序的最早可能完工时间的最大值，计算公式为,（2）工序(i,j)的最早完工时间（Earliest finish time for an activity）TEF(i,j)。计算公式为,7.2 网络参数 Network Parameter,7.2.1时间参数公式及其含义,(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,(6)工序的单时差或自由时间(Free for an activity) F(i，j)。在不影响紧后工序的最早开始时间的条件下，工序(i,j) 的开始时间可以推迟的时间。计算公式为,(5) 工序(i,j)的总时差或松弛时间(Slack for an activity) S(i,j)。是工序(i,j)的最迟开始(结束)时间与最早开始(结束)时间之差，计算公式为,7.2 网络参数 Network Parameter,【例7.4】以网络图73为例。 （1）在图上计算各工序的最早开始和最迟开始时间。 （2）用表格计算工序的6个时间参数。 （3）指出项目的关键工序和关键路线。 （4）求项目的完工时间。,7.2 网络参数 Network 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,（2）表格形式见表7-5,表7-5,7.2 网络参数 Network Parameter,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,(4)工程的完工时间为72天,7.2 网络参数 Network Parameter,工序时间是随机变量时，项目的完工期也是随机变量,设Xk为关键工序 k 所需时间的随机变量，则 Xk 相互独立，工序的期望时间及方差为,工程完工期的期望值及方差为,设关键工序数为n，工程的完工期是一随机变量,7.2.3项目完工的概率,7.2 网络参数 Network Parameter,则由李雅普诺夫中心极限定理知(式中n为关键工序数）,即当n很大时Zn近似服从N（0，1）分布，则有,近似服从,即,7.2 网络参数 Network Parameter,设给定一个时间X0，则工程完工时间不超过X0的概率为,要使工程完工的概率为p0，至少需要多少时间X0,查正态分布表求出X，由,得,7.2 网络参数 Network Parameter,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所示的资料： （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,(2) 关键工序是c、f 和j，由表7-4及式(7.12)知，项目完工期的期望值、方差、标准差分别为 12.17+23.33+33.6769.17 20.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,1.本节介绍了网络参数的计算，共有8个公式，现综合如下：,工序(i , j)的最早可能开工时间,工序(i , j)的最迟必须开工时间,工序(i , j)的最早可能完工时间,工序(i , j)的最迟必须完工时间,工序(i , j)的总时差,工序的单时差 工序的完工期可推迟多少，以致不影响下