运筹学Ch7网络计划

Chapter7网络计划NetworkProgramming7.1绘制网络图Drawnetworkplot7.2网络参数NetworkParameter7.3网络的优化OptimizationofNetwork运筹学OperationsResearch7.1绘制网络图DrawnetworkplotCh7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]32020年1月19日星期日用网络图编制的计划称为网络计划，网络计划技术由计划协调技术（ProgramEvaluationandReviewTechnique简写为PERT）与关键路径法（CriticalPathMethod简写为CPM）组成。7.1.1项目网络图的基本概念PERT主要针对完成工作的时间不能确定而是一个随机变量时的计划编制方法，活动的完成时间通常用三点估计法，注重计划的评价和审查。7.1绘制网络图DrawnetworkplotCPM以经验数据确定工作时间，看作是确定的数值，主要研究项目的费用与工期的相互关系。通常将这两种方法融为一体，统称为网络计划、网络计划技术(PERT/CPM)。Ch7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]42020年1月19日星期日网络计划主要应用于新产品研制与开发、大型工程项目的计划编制与计划的优化，是项目管理和项目安排领域目前比较科学的一种计划编制方法，比甘特图（Canttchart）或称横道图(barchart)计划方法有许多优点。网络计划有利于对计划进行控制、管理、调整和优化，更清晰地了解工作之间的相互联系和相互制约的逻辑关系，掌握关键工作和计划的全盘情况。PERT最早应用于美国海军北极星导弹的研制系统，由于该导弹的系统非常庞大复杂,为找到一种有效的管理技术,设计了PERT这种方法,并使北极星导弹的研制周期缩短了一年半时间。CPM是与PERT十分相似但又是独立发展的另一种技术，是1957年美国杜邦公司的沃克（M.R.walker）和兰德公司的小凯利(J.E.Kelley)共同研制的一种方法。它主要研究大型工程的费用与工期的相互关系。7.1绘制网络图DrawnetworkplotCh7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]52020年1月19日星期日【例7.1】（华罗庚：统筹方法平话及补充）某家庭有夫妇两人安排家务，要求从上午11：30开始到下午2：00结束去上班，做下例3件事：工序工时代号洗衣3小时A烧饭1小时B吃饭0.5小时C怎样安排，使完成时间最短？①②③④A,3B,1C,0.54.5①②③④A,3B,1C,0.53.5④②①③A1,2A2,1C,0.5B,12.57.1绘制网络图DrawnetworkplotCh7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]62020年1月19日星期日工序或称为作业、活动，指任何消耗时间或资源的活动，如新产品设计中的初步设计、技术设计、工装制造等。根据需要，工序可以划分得粗一些，也可以划分得细一些。事件标志工序的开始或结束，本身不消耗时间或资源，或相对作业讲，消耗量可以小得忽略不计。某个事件的实现，标志着在它前面各顶作业（紧前工序）的结束，又标志着在它之后的各项作业（紧后工序）的开始。如机械造业中，只有完成铸锻件毛坯后才能开始机加工；各种零部件都完成后，才能进行总装等。虚工序虚设的工序。用来表达相邻工序之间的衔接关系，不需要时间和资源。7.1绘制网络图DrawnetworkplotCh7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]72020年1月19日星期日网络图由工序、事件及标有完成各道工序所需时间所构成的连通有向图。路从起点沿箭头方向到终点的有向路。紧前工序紧接某项工序的先行工序紧后工序紧接某项工序的后续工序箭示网络图用箭条表示工序的计划网络图。本章讲的就是箭示图节点网络图用节点表示工序的计划网络图前道工序某工序之前的所有工序7.1绘制网络图Drawnetworkplot后续工序某工序之后的所有工序Ch7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]82020年1月19日星期日①②③④⑤2天3天5天4天1天2天3天6天12ABCDEFGH在下图中，A是D、E的紧前工序，D、E是A的紧后工序，F是A的后续工序但不是A的紧后工序；A是D、E、F的前道工序但不是F的紧前工序。注意紧前工序、紧后工序、前道工序和后续工序之间的关系。7.1绘制网络图DrawnetworkplotCh7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]92020年1月19日星期日表7-1工序明细表序号代号工序名称紧前工序时间(天)序号代号工序名称紧前工序时间(天)1A基础工程405E装修工程C252B构件安装A506F地面工程D203C屋面工程B307G设备安装B504D专业工程B208H试运转E、F、G20①②③④⑤⑥⑦ABCDGEFH4050302050252020图7－1（a）箭线图7.1绘制网络图Drawnetworkplot【例7.1】某项目由8道工序组成，工序明细表见表7-1所示。分别用箭线法和节点法绘制该项目的项目网络图。Ch7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]102020年1月19日星期日表7-1工序明细表序号代号工序名称紧前工序时间(天)序号代号工序名称紧前工序时间(天)1A基础工程405E装修工程C252B构件安装A506F地面工程D203C屋面工程B307G设备安装B504D专业工程B208H试运转E、F、G20A4050302050252020BCDGEFH图7－1（b）节点图7.1绘制网络图DrawnetworkplotCh7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]112020年1月19日星期日abc1.当工序a完工后b和c可以开工○○○○3.工序c在工序a完工后就可以开工，但工序d必须在a和b都完工后才能开工acbd○○○○○○2.当工序a和b完工后c和d可以开工4.事件i、j之间有多道工序时，添加虚工序②⑥③(a)abcd○○○○○(b)(c)(d)abc7.1.2绘制网络图7.1绘制网络图DrawnetworkplotCh7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]122020年1月19日星期日7.1绘制网络图Drawnetworkplotacbd○○○○○○…○acbd○○…○○(e)(f)ee图7－26.网络图只有一个发点（项目的开始点）一个收点（项目的结束点）。如图7－2（e）所示，则应合成图7－2（f）所示的一个始点及一个终点。5.用弧(i，j)表示一道工序，事件i是工序的开始，事件j是工序的完成，规定ij。见下图①②③④⑤⑥⑦ABCDGEFH4050302050252020Ch7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]132020年1月19日星期日7.1.3工序时间的估计6ijijijba均方差为三点估计法是事先估计出工序的三种可能完成时间，其期望值就作为工序时间的估计值。三种时间是：(1)完成工序（i，j）的最短时间，称为乐观时间，记为aij(2)完成工序（i，j）的正常时间，称为最可能时间,记为mij(3)完成工序（i，j）的最长时间，称为悲观时间，记为bij三种时间发生的概率分别为1/6、4/6、1/6，则工序（i，j）完成时间的期望值和方差为：64)(ijijijijijbmatEt226)(ijijijijabtD7.1绘制网络图DrawnetworkplotCh7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]142020年1月19日星期日【例7.2】根据某项目作业明细表7－2的资料，绘制项目网络图工序紧前工序工序时间(天)工序紧前工序工序时间(天)a6ga,b10b－9he,f12ca13id,h8dc5ji17ec16kh,g20fa,b12lg25表7－2【解】计划网络图如下：7.1绘制网络图Drawnetworkplot工序紧前工序工序时间(天)工序紧前工序工序时间(天)a－6ga,b10b－9he,f12ca13id,h8dc5ji17ec16kh,g20fa,b12lg25a,61b,9c,13d,5e,16f,12h,12g,10i,8k,20j,17l,25图7－3(a)箭线网络图1235467108911Ch7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]162020年1月19日星期日a6b9c13f12d5i8e16g10h12j17k20l25s0t0图7－3(b)节点网络图工序紧前工序工序时间(天)工序紧前工序工序时间(天)a－6ga,b10b－9he,f12ca13id,h8dc5ji17ec16kh,g20fa,b12lg257.1绘制网络图Drawnetworkplot【例7.3】根据下表作业明细表资料，绘制计划网络图工序紧前工序工序的三种时间工序紧前工序工序的三种时间ambamba－679fc182426b－5810ge,303542c－111214hd,202630da,b,c151719if141722ea91012jf283438a,7.171①②③④⑤⑥⑧⑦⑨b,7.83c,12.17d,17e,10.17f,23.33h,25.67g,35.33i,17.33j,33.67图7－4工序abcdefghij期望值7.177.8312.171710.1723.3335.3325.6717.3333.67方差0.250.690.250.440.251.7842.781.782.78Ch7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]182020年1月19日星期日3.计划网络图的编制规则及其方法4.掌握虚工序的用法5.编制网络图可以从左到右又可以从右到左或两边向中间画图6.网络图初稿完成后对照工序明细表验证紧前紧后工序关系是否正确作业：教材P169T27.1绘制网络图Drawnetworkplot1.本节的主要概念网络计划、计划网络图、甘特图、PERT、CPM、结点图、箭示图、工序、事件、紧前工序、紧后工序2.区分紧前工序、紧后工序、前道工序和后续工序之间的关系7.三种时间估计公式，工序的期望时间和方差下一讲：网络参数7.2网络参数NetworkParameterCh7网络计划NetworkProgramming制作与教学武汉理工大学管理学院熊伟[e-mail]202020年1月19日星期日（1）工序(i,j)的最早开始时间（Earlieststarttimeforanactivity）TES(i,j)。是指紧前工序的最早