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

Chapter7网络计划NetworkProgramming7.1绘制网络图

Drawnetworkplot7.2网络参数

NetworkParameter7.3网络的优化

OptimizationofNetwork

运筹学

Operations

Research

2/1/20257.1绘制网络图Drawnetworkplot2/1/2025用网络图编制的计划称为网络计划，网络计划技术由计划协调技术（ProgramEvaluationandReviewTechnique简写为PERT）与关键路径法（CriticalPathMethod简写为CPM）组成。7.1.1项目网络图的基本概念PERT主要针对完成工作的时间不能确定而是一个随机变量时的计划编制方法，活动的完成时间通常用三点估计法，注重计划的评价和审查。7.1绘制网络图DrawnetworkplotCPM以经验数据确定工作时间，看作是确定的数值，主要研究项目的费用与工期的相互关系。通常将这两种方法融为一体，统称为网络计划、网络计划技术(PERT/CPM)。2/1/2025【例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绘制网络图Drawnetworkplot2/1/2025工序或称为作业、活动，指任何消耗时间或资源的活动，如新产品设计中的初步设计、技术设计、工装制造等。根据需要，工序可以划分得粗一些，也可以划分得细一些。事件标志工序的开始或结束，本身不消耗时间或资源，或相对作业讲，消耗量可以小得忽略不计。某个事件的实现，标志着在它前面各顶作业（紧前工序）的结束，又标志着在它之后的各项作业（紧后工序）的开始。如机械造业中，只有完成铸锻件毛坯后才能开始机加工；各种零部件都完成后，才能进行总装等。虚工序虚设的工序。用来表达相邻工序之间的衔接关系，不需要时间和资源。7.1绘制网络图Drawnetworkplot2/1/2025网络图由工序、事件及标有完成各道工序所需时间所构成的连通有向图。路

从起点沿箭头方向到终点的有向路。紧前工序紧接某项工序的先行工序紧后工序紧接某项工序的后续工序箭示网络图用箭条表示工序的计划网络图。本章讲的就是箭示图节点网络图用节点表示工序的计划网络图前道工序某工序之前的所有工序7.1绘制网络图Drawnetworkplot后续工序某工序之后的所有工序2/1/2025①②③④⑤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绘制网络图Drawnetworkplot2/1/2025表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所示。分别用箭线法和节点法绘制该项目的项目网络图。2/1/2025表7-1工序明细表序号代号工序名称紧前工序时间(天)序号代号工序名称紧前工序时间(天)1A基础工程405E装修工程C252B构件安装A506F地面工程D203C屋面工程B307G设备安装B504D专业工程B208H试运转E、F、G20A4050302050252020BCDGEFH图7－1（b）节点图7.1绘制网络图Drawnetworkplot2/1/2025abc1.当工序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绘制网络图Drawnetworkplot2/1/20257.1绘制网络图Drawnetworkplotacbd○○○○○○…○acbd○○…○○(e)(f)ee图7－26.网络图只有一个发点（项目的开始点）一个收点（项目的结束点）。如图7－2（e）所示，则应合成图7－2（f）所示的一个始点及一个终点。5.用弧(i，j)表示一道工序，事件i是工序的开始，事件j是工序的完成，规定i<j。见下图①②③④⑤⑥⑦ABCDGEFH40503020502520202/1/20257.1.3工序时间的估计均方差为三点估计法是事先估计出工序的三种可能完成时间，其期望值就作为工序时间的估计值。三种时间是：(1)完成工序（i，j）的最短时间，称为乐观时间，记为aij(2)完成工序（i，j）的正常时间，称为最可能时间,记为mij(3)完成工序（i，j）的最长时间，称为悲观时间，记为bij三种时间发生的概率分别为1/6、4/6、1/6，则工序（i，j）完成时间的期望值和方差为：7.1绘制网络图Drawnetworkplot2/1/2025【例7.2】根据某项目作业明细表7－2的资料，绘制项目网络图工序紧前工序工序时间(天)工序紧前工序工序时间(天)a6ga,b10b－9he,f12ca13id,h8dc5ji17ec16kd,h,g20fa,b12lg25表7－2【解】计划网络图如下：7.1绘制网络图Drawnetworkplot2/1/2025工序紧前工序工序时间(天)工序紧前工序工序时间(天)a－6ga,b10b－9he,f12ca13id,h8dc5ji17ec16kd,h,g20fa,b12lg25a,61b,9c,13d,5e,16f,12h,12g,10i,8k,20j,17l,25图7－3(a)箭线网络图12354671089112/1/2025a6b9c13f12d5i8e16g10h12j17k20l25s0t0图7－3(b)节点网络图工序紧前工序工序时间(天)工序紧前工序工序时间(天)a－6ga,b10b－9he,f12ca13id,h8dc5ji17ec16kd,h,g20fa,b12lg257.1绘制网络图Drawnetworkplot2/1/2025【例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.782/1/20253.计划网络图的编制规则及其方法4.掌握虚工序的用法5.编制网络图可以从左到右又可以从右到左或两边向中间画图6.网络图初稿完成后对照工序明细表验证紧前紧后工序关系是否正确作业：教材P169T27.1绘制网络图Drawnetworkplot1.本节的主要概念网络计划、计划网络图、甘特图、PERT、CPM、结点图、箭示图、工序、事件、紧前工序、紧后工序2.区分紧前工序、紧后工序、前道工序和后续工序之间的关系7.三种时间估计公式，工序的期望时间和方差下一讲：网络参数2/1/20257.2网络参数

NetworkParameter2/1/2025（1）工序(i,j)的最早开始时间（Earlieststarttimeforanactivity）TES(i,j)。是指紧前工序的最早可能完工时间的最大值，计算公式为（2）工序(i,j)的最早完工时间（Earliestfinishtimeforanactivity）TEF(i,j)。计算公式为7.2网络参数NetworkParameter7.2.1时间参数公式及其含义2/1/2025(4)工序(i,j)的最迟必须结束时间(Latestfinishtimeforan

activity)TLF(i,j)。计算公式为(3)工序(i,j)的最迟必须开始时间（lateststarttimeforanactivity）TLS(i,j)。是指为了不影响紧后工序如期开工，工序最迟必须开工的时间，计算公式为7.2网络参数NetworkParameter2/1/2025(6)工序的单时差或自由时间(Freeforanactivity)F(i，j)。在不影响紧后工序的最早开始时间的条件下，工序(i,j)的开始时间可以推迟的时间。计算公式为(5)工序(i,j)的总时差或松弛时间(Slackforanactivity)S(i,j)。是工序(i,j)的最迟开始(结束)时间与最早开始(结束)时间之差，计算公式为7.2网络参数NetworkParameter2/1/2025【例7.4】以网络图7－3为例。（1）在图上计算各工序的最早开始和最迟开始时间。（2）用表格计算工序的6个时间参数。（3）指出项目的关键工序和关键路线。（4）求项目的完工时间。7.2网络参数NetworkParameter图7－5a,6111①②③④⑤⑥⑧⑦⑨⑩b,9c,13d,5e,16f,12h,12g,10i,8k,20j,17l,2500066991919351919474747475572725552474752524742353719623231400【解】(1)最早开始和最迟开始时间见图7－52/1/2025（2）表格形式见表7-5表7-5工序(i,j)tijTES(i,j)TEF(i,j)TLS(i,j)TLF(i,j)S(i,j)F(i,j)关键工序a(1,2)6060600是b(1,3)9091423140c(2,4)1361961900是d(4,7)5192442472323e(4,5)161935193500是f(3,5)1292123351414g(3,8)1091937472828h(5,6)123547354700是i(7,10)84755475500是j(10,11)175572557200是k(9,11)204767527255l(8,11)251944477228287.2网络参数NetworkParameter2/1/2025a,6111①②③④⑤⑥⑧⑦⑨⑩b,9c,13d,5e,16f,12h,12g,10i,8k,20j,17l,2500066991919351919474747475572725552474752524742353719623231400(3)关键工序：a、c、e、h、i、j

关键路线：①→②→④→⑤→⑥→⑦→⑩→11(4)工程的完工时间为72天7.2网络参数NetworkParameter2/1/2025工序时间是随机变量时，项目的完工期也是随机变量设Xk为关键工序k所需时间的随机变量，则Xk相互独立，工序的期望时间及方差为工程完工期的期望值及方差为设关键工序数为n，工程的完工期是一随机变量7.2.3项目完工的概率7.2网络参数NetworkParameter2/1/2025则由李雅普诺夫中心极限定理知(式中n为关键工序数）即当n很大时Zn近似服从N（0，1）分布，则有近似服从即7.2网络参数NetworkParameter2/1/2025设给定一个时间X0，则工程完工时间不超过X0的概率为要使工程完工的概率为p0，至少需要多少时间X0查正态分布表求出X，由得7.2网络参数NetworkParameter2/1/2025a,7.171①②③④⑤⑥⑧⑦⑨b,7.83c,12.17d,17e,10.17f,23.33h,25.67g,35.33i,17.33j,33.67【例7.5】对例7.3所示的资料：（1）求工序的最早开始和最迟开始时间。（2）求工程完工期的期望值及其概率。（3）要求完工的概率为0.95,至少需要多少天。00007.177.1712.1712.1712.1735.529.1717.3435.569.1769.1769.1733.8443.551.8435.569.1712.1726.523.6716.518.6700图7－7【解】(1)工序的最早开始和最迟开始时间见图7－726.526.57.2网络参数NetworkParameter2/1/2025(2)关键工序是c、f和j，由表7-4及式(7.12)知，项目完工期的期望值、方差、标准差分别为μ＝12.17+23.33+33.67＝69.17σ2＝0.25+1.78+2.76＝4.79，σ=2.1886（3）X0＝72，(X0－μ)/σ=(72－69.17)/2.1886=1.293（4）已知概率p0=0.98，由式(7.15)，查正态分布表有要使项目完工的概率为0.98，至少需要73.65天7.2网络参数NetworkParameter2/1/20251.本节介绍了网络参数的计算，共有8个公式，现综合如下：①工序(i,j)的最早可能开工时间②工序(i,j)的最迟必须开工时间③工序(i,j)的最早可能完工时间④工序(i,j)的最迟必须完工时间⑤工序(i,j)的总时差⑥工序的单时差工序的完工期可推迟多少，以致不影响下道工序的最早开工时间：7.2网络参数NetworkParameter2/1/2025作业：教材P169T3，4，5⑦事件j的最早时间表示以j为开工事件工序最早可能开工时间⑧事件i的最迟时间表示以i为完工事件工序最迟必须完工时间下一讲：网络计划的优化与调整2.三种时间估计公式，工序的期望时间和方差3.要求工程完工时间不超过X0时，求完工的概率p04.要使工程完工的概率为p0，求至少需要多少时间X07.2网络参数NetworkParameter2/1/20257.3网络的优化

OptimizationofNetwork2/1/20257.3.1时间－成本控制7.3网络的优化

OptimizationofNetwork正常时间（NormalTime）正常成本(NormalCost)应急时间(CrashTime)应急成本(CrashCost)总成本＝总应急成本－总应急收益＝总正常成本＋总应急增加成本－总应急收益单位时间工序的应急增加成本(成本斜率)

＝(应急成本－正常成本)÷（正常时间－应急时间）2/1/2025【例7.6】项目工序的正常时间、应急时间及对应的费用见表7-6。表中正常成本是在正常时间完成工序所需要的成本，应急成本是在采取应急措施时完成工序的成本。每天的应急成本是工序缩短一天额外增加的成本（1）绘制项目网络图，按正常时间计算完成项目的总成本和工期。（2）按应急时间计算完成项目的总成本和工期。（3）按应急时间的项目完工期，调整计划使总成本最低。（4）已知项目缩短1天额外获得奖金5万元，减少间接费用1万元，求总成本最低的项目完工期，也称为最低成本日程。7.3网络的优化

OptimizationofNetwork2/1/2025工序紧前工序时间(天)成本(万元)时间的最大缩量(天)应急增加成本(万元/天)正常应急正常应急A1915528047BA21196290214CB2422243023DB25233860211EB2624182624FC25238810227GD,E2823193954HF232330300－IG,H27264055115JI1814172141KI3530253552LJ28253060310MK3026455743NL2520182852总成本5067132/1/2025【解】(1)项目网络图及时间参数见图7－8。项目的完工期为210天，将表7-6正常成本一列相加得到总成本为506万元①②C,24③H,23④B,21E,26D,25J,18⑤G,28⑥A,19⑦⑧⑨⑩F,25I,27L,2812K,35M,3013N,2511O,0001940404066646689112139210013915718517421018515718014513911284896440845958190图7－87.3网络的优化

OptimizationofNetwork2/1/2025①②C,22③H,23④B,19E,24D,23J,14⑤G,23⑥A,15⑦⑧⑨⑩F,23I,26L,2512K,30M,2613N,2011O,0001534343458565879102128187012814216715818716714216113112810279795634795655150图7－9（2）项目网络图不变，时间参数见图7－9，完工期187天，将表7-6应急成本一列相加得到总成本为713万元7.3网络的优化

OptimizationofNetwork2/1/2025(3)图7－9中，非关键工序是D、E、G、K和M，可以看出，将工序D、E、G按正常时间施工时，最早开始和最迟开始时间不相等，说明按正常时间施工不影响项目的完工期（187天），见图7－10(a)。工序K和M按正常时间共要缩短时间6天，见图7－10(b)。③E,26D,25⑤G,28⑦⑧O,03434606079795453⑨12K,35M,3013J,14⑨⑩L,2513N,2011应急时间路长：59正常时间路长：65⑨12K,30M,2613应急时间路长：56图7－10(a)(b)7.3网络的优化

OptimizationofNetwork2/1/2025则最优的决策方案是：关键工序A、B、C、F、H、I、J、L、N全部按应急时间施工，总成本等于各工序应急成本之和；工序D、E、G按正常时间施工，成本等于各工序正常成本之和；工序K缩短5天工序M缩短1天，成本等于正常成本加应急时间增加的成本。按项目完工期187天施工的最小成本是654万元，成本分析见表7-7。调整后有两条关键路线，见图7－11①②C,22③H,23④B,19E,26D,25J,14⑤G,23⑥A,15⑦⑧⑨⑩F,23I,26L,2512K,30M,2913N,2011O,0001534343460566079102128187012814216715818716714215812812810279795634795653150图7－117.3网络的优化

OptimizationofNetwork2/1/2025(4)考虑缩短关键工序的时间，选择一天应急增加的成本小于等于6的关键工序采取应急措施来缩短时间，这样的工序有C、J、N，工序C缩短2天，工序J缩短4天，工序N缩短2天。对图7－8进行第一次调整得到图7－12。得到两条关键路线，工序K和M变为关键工序，项目完工期为202天，缩短了8天。总成本变动额为:2×3＋4×1＋2×2－8×6＝－34（万元）①②C,22③H,23④B,21E,26D,25J,14⑤G,28⑥A,19⑦⑧⑨⑩F,25I,27L,2812K,35M,3013N,2311O,0001940404066626687110137202013715117917220217915117213713711082876240825756190图7－127.3网络的优化

OptimizationofNetwork2/1/2025检查图7－12虚线围起来的部分。要缩短工期必须两条关键路线同时缩短时间，上面一条路线工序N还能缩短3天，因此下面一条路线只对工序K缩短3天，对图7－12调整得到图7－13。项目的完工期为199天，又缩短了3天，总成本变动额为3×2＋3×2－3×6＝－6（万元）①②C,22③H,23④B,21E,26D,25J,14⑤G,28⑥A,19⑦⑧⑨⑩F,25I,27L,2812K,32M,3013N,2011O,0001940404066626687110137199013715117916919917915116913713711082876240825756190图7－13继续检查发现，缩短任何关键工序都不能降低成本，则总成本最低的项目工期是199天，总成本为506－34－6＝466（万元）7.3网络的优化

OptimizationofNetwork2/1/20257.3.2资源的合理配置(1)资源一定，如何组织、安排和调配资源保证项目按期完成。(2)资源不足时，如何协调内部资源和采取应急措施(加班、雇工、增加设备、改进施工工艺)保证项目按期完成。(3)资源、时间和成本的整体调整和系统优化【例7.7】项目各工序的时间和资源如表7－8所示（1）绘制项目网络图，按正常时间计算项目完工期，按期完工最多需要多少人。（2）保证按期完工，怎样采取应急措施，使总成本最小又使得总人数最少，对计划进行系统优化分析。7.3网络的优化

OptimizationofNetwork2/1/2025工序紧前工序每天需要资源(人)时间(天)成本（万元）时间的最大缩量(天)应急增加成本(万元/天)正常应急正常应急A51083070220BA1286130150210CB20107100130310DA12764050110ED201085080215FC,EE103360600－G7139708644表7－87.3网络的优化

OptimizationofNetwork2/1/2025【解】（1）项目网络图及最早最迟开始时间见图7－14。项目完工期为40天。关键工序是A、D、E和G，非关键工序是B、C、F，总时差都等于9，也是工序B、C、F的全部机动时间。A,10B,8D,7C,10E,10F,3G,13H,0①②③④⑤⑥⑦000101018172728404037271710190图7－14277.3网络的优化

OptimizationofNetwork2/1/2025从图7－15看出，如果非关键工序都按最早时间开始，第11天到第28天是用工高峰期，第19天到第27天为40人，按此计划施工需要40人图7－157.3网络的优化

OptimizationofNetwork2/1/2025将工序B按最早时间开始，工序C、F按最迟时间开始，调整后最多需要32人，见图7-16。图7－167.3网络的优化

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

OptimizationofNetwork2/1/2025TheEndofChapter7作业:教材P170T6，7，8，91.时间优化2.资源优化3.时间与资源同时优化4.费用优化5.网络图与甘特图并用TheEndofChapter7

7.3网络的优化

OptimizationofNetwork2/1/2025第7章部分习题答案2/1/2025习题7.2(1)ABDCEF①②③④⑤⑥G箭线图节点图SBCDGEFA工序ABCDEFG紧前工序－－－ACAF、D、B、E紧后工序D,EGEGGG－2/1/2025习题7.2(2)ABFCDE①②③④⑤⑥⑦M工序ABCDEFGHIJKLM紧前工序－－－BBA,BBD,GC,E,F,HD,GC,EIJ,K,L紧后工序FE,D,F,GI,KH,JI,KIH,JILMMM－⑧⑨⑩KGJHL箭线图I2/1/2025习题7.3A,9B,6C,12D,19E,6①②③④⑤⑥工序ABCDEFG紧前工序-AAB,CCD,ED,E工序时间(天)961219678F,7（1）网络图G,8⑦2/1/2025习题7.3A,9B,6C,12D,19E,6①②③④⑤⑥F,7（2）网络参数G,8⑦0099212140404848414021341590(3)关键路线：①→②→③→④→⑤→⑥→⑦；关键工序：A、C、D、G；完工期：48周。工序ABCDEFG最早开始09921214040最迟开始015921344140总时差060013102/1/2025习题7.4A,8B,5F,17C,7D,12E,8①②③④⑤⑥⑦M,15工序ABCDEFGHIJKLMN紧前工序---A,BBB,CED,GEEHF,JI,K,LF,J,L工序时间(天)8571281716814510231512⑧⑨⑩K,10G,16J,5H,8L,23（1）网络图I,14N,1211122/1/2025习题7.4（2）网络参数00005871313132429374762624737293324171319759000A,8B,5F,17C,7D,12E,8①②③④⑤⑥⑦M,15⑧⑨⑩K,10G,16J,5H,8L,23I,14N,12111247502/1/2025习题7.5A,10.17B,8C,14.83D,9.167E,17.17①②③④⑤⑥F,11.83工序紧前工序工序的三种时间期望值方差ambA－9101210.170.25BA681080.4444CA13151614.830.25DB89119.1670.25EB,C15172017.170.6944FD,E9121411.830.6944（1）（2）关键工序A、C、E、F；关键路线①→②→④→⑤→⑥2/1/2025习题7.5工序紧前工序工序的三种时间期望值方差标准差ambA－9101210.170.250.5BA681080.44440.6667CA13151614.830.250.5DB89119.1670.250.5EB,C15172017.170.69440.8333FD,E9121411.830.69440.8333（4）X0=56,（3）项目完