《运筹学网络计划》课件

1、运筹学网络计划PPT课件运筹学网络计划PPT课件7.1 绘制网络图 Draw network plot7.1 绘制网络图22 九月 2022网络还是进行计划工作的有效工具凡事“预则立”！21 九月 2022网络还是进行计划工作的有效工具凡事“预则22 九月 2022横道图时间3月4月5月6月开题报告英文翻译文献查阅论文撰写论文答辩优点：直观、易懂、便于检查缺点：不能反映相互之间联系和影响，无法找出关键工作。21 九月 2022横道图时间3月4月5月6月开题报告英文翻22 九月 2022 用网络图编制的计划称为网络计划，网络计划技术由计划协调技术（Program Evaluation and R

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

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

4、公司的小凯利(J.E.Kelley)共同研制的一种方法。它主要研究大型工程的费用与工期的相互关系。7.1 绘制网络图 Draw network plot21 九月 2022 网络计划主要应用于新产品22 九月 2022【例7.1】（华罗庚：统筹方法平话及补充）某家庭有夫妇两人安排家务，要求从上午11：30开始到下午2：00结束去上班，做下例3件事：工序 工时 代号洗衣 3小时 A烧饭 1小时 B吃饭 0.5小时 C 怎样安排，使完成时间最短？A,3B,1C,0.54.5A,3B,1C,0.53.5A1,2A2,1C,0.5B,12.57.1 绘制网络图 Draw network plot21

5、九月 2022【例7.1】（华罗庚：统筹方法平话及补充22 九月 2022 工序 或称为作业、活动，指任何消耗时间或资源的活动，如新产品设计中的初步设计、技术设计、工装制造等。根据需要，工序可以划分得粗一些，也可以划分得细一些。 事件 标志工序的开始或结束，本身不消耗时间或资源，或相对作业讲，消耗量可以小得忽略不计。某个事件的实现，标志着在它前面各顶作业（紧前工序）的结束，又标志着在它之后的各项作业（紧后工序）的开始。如机械造业中，只有完成铸锻件毛坯后才能开始机加工；各种零部件都完成后，才能进行总装等。 虚工序 虚设的工序。用来表达相邻工序之间的衔接关系，不需要时间和资源。7.1 绘制网络图

6、Draw network plot21 九月 2022 工序 或称为作业、活动，指任何消耗时22 九月 2022虚工序21AB 不正确312BAC 正确21 九月 2022虚工序21AB 不正确31222 九月 2022虚工序 不正确 正确ACADBABACDBACDE21 九月 2022虚工序 不正确 22 九月 2022 网络图 由工序、事件及标有完成各道工序所需时间所构成的连通有向图。路 从起点沿箭头方向到终点的有向路。紧前工序 紧接某项工序的先行工序紧后工序 紧接某项工序的后续工序箭示网络图 用箭条表示工序的计划网络图。本章讲的就是箭示图节点网络图 用节点表示工序的计划网络图前道工序

7、某工序之前的所有工序7.1 绘制网络图 Draw network plot后续工序 某工序之后的所有工序21 九月 2022 网络图 由工序、事件及标有完成各道工22 九月 20222天3天5天4天1天2天3天6天12ABCDEFGH在下图中，A是D、E的紧前工序，D、E是A的紧后工序，F是A的后续工序但不是A的紧后工序；A是D、E、F的前道工序但不是 F 的紧前工序。注意紧前工序、紧后工序、前道工序和后续工序之间的关系。7.1 绘制网络图 Draw network plot21 九月 20222天3天5天4天1天2天3天622 九月 2022表7-1 工序明细表 序号代号工序名称紧前工序时间

8、(天)序号代号工序名称紧前工序时间(天)1A基础工程405E装修工程C252B构件安装A506F地面工程D203C屋面工程B307G设备安装B504D专业工程B208H试运转E、F、G20ABCDGEFH4050302050252020图71（a）箭线图7.1 绘制网络图 Draw network plot【例7.1】某项目由8道工序组成，工序明细表见表7-1所示。分别用箭线法和节点法绘制该项目的项目网络图。 21 九月 2022表7-1 工序明细表 序号代号工序名称紧22 九月 2022表7-1 工序明细表 序号代号工序名称紧前工序时间(天)序号代号工序名称紧前工序时间(天)1A基础工程40

9、5E装修工程C252B构件安装A506F地面工程D203C屋面工程B307G设备安装B504D专业工程B208H试运转E、F、G20A4050302050252020BCDGEFH图71（b）节点图7.1 绘制网络图 Draw network plot21 九月 2022表7-1 工序明细表 序号代号工序名称紧22 九月 2022abc1.当工序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

10、绘制网络图 Draw network plot21 九月 2022abc1.当工序a完工后b和c可以开工22 九月 20227.1 绘制网络图 Draw network plotacbd acbd (e)(f)ee图726. 网络图只有一个发点（项目的开始点）一个收点（项目的结束点）。如图72（e）所示，则应合成图72（f）所示的一个始点及一个终点。5. 用弧(i，j)表示一道工序，事件i是工序的开始，事件j是工序的完成，规定i j。见下图 ABCDGEFH405030205025202021 九月 20227.1 绘制网络图acbd 22 九月 2022绘制网络图的步骤1、分解任务，列出活动

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

12、四 1 2 4 3 5 6 721 九月 2022结点编号分级编号法零二一二三三四 22 九月 20227.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 plot21 九月 20227.1.3 工序时间的

13、估计均方差为三点估22 九月 2022【例7.2】根据某项目作业明细表72的资料，绘制项目网络图 工序紧前工序工序时间(天)工序紧前工序工序时间(天)a6ga,b10b 9he,f12ca13id,h8dc5ji17ec16kd,h,g20fa,b12lg25表72【解】计划网络图如下：7.1 绘制网络图 Draw network plot21 九月 2022【例7.2】根据某项目作业明细表72的工序紧前工序工序时间(天)工序紧前工序工序时间(天)a 6ga,b10b 9he,f12ca13id,h8dc5ji17ec16kd,h,g20fa,b12lg25a,61b,9c,13d,5e,16

14、f,12h,12g,10i,8k,20j,17l,25图73(a)箭线网络图1235467108911工序紧前工序工序时间(天)工序紧前工序工序时间(天)a 22 九月 2022a6b9 c13 f12d5i8 e16 g10 h12 j17 k20 l25s0t0图73(b)节点网络图工序紧前工序工序时间(天)工序紧前工序工序时间(天)a 6ga,b10b 9he,f12ca13id,h8dc5ji17ec16kd,h,g20fa,b 12lg257.1 绘制网络图 Draw network plot21 九月 2022ab c fdi e g h j k l【例7.3】根据下表作业明细表资

15、料，绘制计划网络图工序紧前工序工序的三种时间工序紧前工序工序的三种时间ambamba679fc182426b5810ge,303542c111214hd,202630da,b,c151719if141722ea91012jf283438a,7.171b,7.83c,12.17d,17e,10.17f,23.33h,25.67g,35.33i,17.33j,33.67图74工序abcdefghij期望值7.177.8312.171710.1723.3335.3325.6717.3333.67方差0.250.690.250.440.251.7842.781.782.78【例7.3】根据下表作业明细

16、表资料，绘制计划网络图工序紧前工22 九月 20223.计划网络图的编制规则及其方法4.掌握 虚工序的用法5.编制网络图可以从左到右又可以从右到左或两边向中间画图6.网络图初稿完成后对照工序明细表验证紧前紧后工序关系是否正确作业：教材P169 T 27.1 绘制网络图 Draw network plot1.本节的主要概念 网络计划、计划网络图、甘特图、PERT、CPM、 结点图、箭示图、工序、事件、紧前工序、紧后工序2.区分紧前工序、紧后工序、前道工序和后续工序之间的关系7.三种时间估计公式， 工序的期望时间和方差下一讲：网络参数 21 九月 20223.计划网络图的编制规则及其方法作业：教7

17、.2 网络参数 Network Parameter7.2 网络参数22 九月 2022（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 Parameter7.2.1时间参数公式及其含义21 九月 2022（1）工序(i,j)的最早开始时间（Ea22 九月 2022(4) 工序(i,j)的最迟必须结

18、束时间(Latest finish time for an activity) TLF(i,j)。计算公式为 (3) 工序(i,j)的最迟必须开始时间（latest start time for an activity）TLS(i,j)。是指为了不影响紧后工序如期开工，工序最迟必须开工的时间，计算公式为 7.2 网络参数 Network Parameter21 九月 2022(4) 工序(i,j)的最迟必须结束时间22 九月 2022(6)工序的单时差或自由时间(Free for an activity) F(i，j)。在不影响紧后工序的最早开始时间的条件下，工序(i,j) 的开始时间可以推迟

19、的时间。计算公式为 (5) 工序(i,j)的总时差或松弛时间(Slack for an activity) S(i,j)。是工序(i,j)的最迟开始(结束)时间与最早开始(结束)时间之差，计算公式为 7.2 网络参数 Network Parameter21 九月 2022(6)工序的单时差或自由时间(Free 22 九月 2022【例7.4】以网络图73为例。（1）在图上计算各工序的最早开始和最迟开始时间。（2）用表格计算工序的6个时间参数。（3）指出项目的关键工序和关键路线。（4）求项目的完工时间。7.2 网络参数 Network Parameter图75a,6111b,9c,13d,5e,

20、16f,12h,12g,10i,8k,20j,17l,2500066991919351919474747475572725552474752524742353719623231400【解】(1)最早开始和最迟开始时间见图7521 九月 2022【例7.4】以网络图73为例。7.2 22 九月 2022（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)1

21、61935193500是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 网络参数 Network Parameter21 九月 2022（2）表格形式见表7-5 表7-5工序 22 九月 2022a,6111b,9c,13d,5e,16f,12h,12g,10i,8k,20j,17l,2500066991919351919474747475572725552474

22、752524742353719623231400(3)关键工序：a、c、e、h、i、j 关键路线： 11(4)工程的完工时间为72天7.2 网络参数 Network Parameter21 九月 2022a,6111b,9c22 九月 2022工序时间是随机变量时，项目的完工期也是随机变量设Xk为关键工序 k 所需时间的随机变量，则 Xk 相互独立，工序的期望时间及方差为工程完工期的期望值及方差为设关键工序数为n，工程的完工期是一随机变量7.2.3项目完工的概率7.2 网络参数 Network Parameter21 九月 2022工序时间是随机变量时，项目的完工期也是随22 九月 2022则

23、由李雅普诺夫中心极限定理知(式中n为关键工序数）即当n很大时Zn近似服从N（0，1）分布，则有近似服从即7.2 网络参数 Network Parameter21 九月 2022则由李雅普诺夫中心极限定理知(式中n为关22 九月 2022设给定一个时间X0，则工程完工时间不超过X0的概率为要使工程完工的概率为p0，至少需要多少时间X0查正态分布表求出X，由得7.2 网络参数 Network Parameter21 九月 2022设给定一个时间X0，则工程完工时间不超过22 九月 2022a,7.171b,7.83c,12.17d,17e,10.17f,23.33h,25.67g,35.33i,1

24、7.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图77【解】(1)工序的最早开始和最迟开始时间见图7726.526.57.2 网络参数 Network Parameter21 九月 2022a,7.171b,7.22 九月 2022 (2) 关键工序是c

25、、f 和j，由表7-4及式(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 Parameter21 九月 2022 (2) 关键工序是c、f 和j，由表22 九月 20221.本节介绍了网络参数的计算，共有8个公式，现综合如下：工序(i , j)的最早可能开工时间 工序(

26、i , j)的最迟必须开工时间工序(i , j)的最早可能完工时间工序(i , j)的最迟必须完工时间工序(i , j)的总时差工序的单时差 工序的完工期可推迟多少，以致不影响下道工序的最早开工时间：7.2 网络参数 Network Parameter21 九月 20221.本节介绍了网络参数的计算，共有8个公22 九月 2022作业：教材P169 T 3，4，5事件j 的最早时间表示以j为开工事件工序最早可能开工时间事件 i 的最迟时间表示以i为完工事件工序最迟必须完工时间下一讲：网络计划的优化与调整 2.三种时间估计公式， 工序的期望时间和方差3.要求工程完工时间不超过X0时，求完工的概率

27、p04.要使工程完工的概率为p0，求至少需要多少时间X07.2 网络参数 Network Parameter21 九月 2022作业：教材P169 T 3，4，5事7.3 网络的优化 Optimization of Network7.3 网络的优化22 九月 20227.3.1 时间成本控制7.3 网络的优化 Optimization of Network正常时间（Normal Time） 正常成本(Normal Cost) 应急时间(Crash Time)应急成本 (Crash Cost)总成本总应急成本总应急收益 总正常成本总应急增加成本总应急收益单位时间工序的应急增加成本(成本斜率) (

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

29、ptimization of Network21 九月 2022【例7.6】项目工序的正常时间、应急时间工序紧前工序时间(天)成本(万元)时间的最大缩量(天)应急增加成本(万元/天)正常应急正常应急A1915528047BA21196290214CB2422243023DB25233860211EB2624182624FC25238810227GD,E2823193954HF232330300IG,H27264055115JI1814172141KI3530253552LJ28253060310MK3026455743NL2520182852总成本506713工序紧前工序时间(天)成本(万元)

30、时间的最大缩量(天)应急增22 九月 2022【解】(1)项目网络图及时间参数见图78。项目的完工期为210天，将表7-6正常成本一列相加得到总成本为506万元 C,24H,23B,21E,26D,25J,18G,28A,19F,25I,27L,2812K,35M,3013N,2511O,0001940404066646689112139210013915718517421018515718014513911284896440845958190图787.3 网络的优化 Optimization of Network21 九月 2022【解】(1)项目网络图及时间参数见图722 九月 2022C

31、,22H,23B,19E,24D,23J,14G,23A,15F,23I,26L,2512K,30M,2613N,2011O,0001534343458565879102128187012814216715818716714216113112810279795634795655150图79（2）项目网络图不变，时间参数见图79，完工期187天，将表7-6应急成本一列相加得到总成本为713万元 7.3 网络的优化 Optimization of Network21 九月 2022C,22H,23B,19E,2422 九月 2022(3)图79中，非关键工序是D、E、G、K和M，可以看出，将工序D

32、、E、G按正常时间施工时，最早开始和最迟开始时间不相等，说明按正常时间施工不影响项目的完工期（187天），见图710(a)。工序K和M按正常时间共要缩短时间6天，见图710(b)。 E,26D,25G,28O,0343460607979545312K,35M,3013J,14L,2513N,2011应急时间路长：59正常时间路长：6512K,30M,2613应急时间路长：56图710(a)(b)7.3 网络的优化 Optimization of Network21 九月 2022(3)图79中，非关键工序是D、E、G22 九月 2022则最优的决策方案是：关键工序A、B、C、F、H、I、J、L

33、、N全部按应急时间施工，总成本等于各工序应急成本之和；工序D、E、G按正常时间施工，成本等于各工序正常成本之和；工序K缩短5天工序M缩短1天，成本等于正常成本加应急时间增加的成本。按项目完工期187天施工的最小成本是654万元，成本分析见表7-7。调整后有两条关键路线，见图711 C,22H,23B,19E,26D,25J,14G,23A,15F,23I,26L,2512K,30M,2913N,2011O,0001534343460566079102128187012814216715818716714215812812810279795634795653150图7117.3 网络的优化 Op

34、timization of Network21 九月 2022则最优的决策方案是：关键工序A、B、C、22 九月 2022(4)考虑缩短关键工序的时间，选择一天应急增加的成本小于等于6的关键工序采取应急措施来缩短时间，这样的工序有C、J、N，工序C缩短2天，工序J缩短4天，工序N缩短2天。对图78进行第一次调整得到图712。得到两条关键路线，工序K和M变为关键工序，项目完工期为202天，缩短了8天。总成本变动额为: 2341228634（万元）C,22H,23B,21E,26D,25J,14G,28A,19F,25I,27L,2812K,35M,3013N,2311O,000194040406

35、6626687110137202013715117917220217915117213713711082876240825756190图7127.3 网络的优化 Optimization of Network21 九月 2022(4)考虑缩短关键工序的时间，选择一天应22 九月 2022检查图712虚线围起来的部分。要缩短工期必须两条关键路线同时缩短时间，上面一条路线工序N还能缩短3天，因此下面一条路线只对工序K缩短3天，对图712调整得到图713。项目的完工期为199天，又缩短了3天，总成本变动额为 3232366（万元） C,22H,23B,21E,26D,25J,14G,28A,19F,

36、25I,27L,2812K,32M,3013N,2011O,0001940404066626687110137199013715117916919917915116913713711082876240825756190图713继续检查发现，缩短任何关键工序都不能降低成本，则总成本最低的项目工期是199天，总成本为 506346466（万元）7.3 网络的优化 Optimization of Network21 九月 2022检查图712虚线围起来的部分。要缩短工22 九月 20227.3.2 资源的合理配置(1) 资源一定，如何组织、安排和调配资源保证项目按期完成。(2) 资源不足时，如何协调内部资源和采取应急措施(加班、雇工、增加设备、改进施工工艺)保证项目按期完成。(3) 资源、时间和成本的整体调整和系统优化 【例7.7】项目各工序的时间和资源如表78所示 （1）绘制项目网络图，按正常时间计算项目完工期，按期完工最多需要多少人。（2）保证按期完工，怎样采取应急措施，使总成本最小又使得总人数最少，对计划进行系统优化分析。7.3 网络的优化 Optimization of Network21