《网络计划运筹学.ppt》由会员分享，可在线阅读，更多相关《网络计划运筹学.ppt（53页珍藏版）》请在三一办公上搜索。
1、1,补充：网络计划技术(统筹法),基本概念确定性网络计划网络图的优化不确定性网络计划,2023/6/23,2,什么是网络计划技术/统筹法 对于任何一项生产制造、科学实验、工程实施、军事作战等项目活动，为了充分利用有限的时间、空间与资源（人力、物力、财力），都必须编制一个科学的工作组织计划来有效地组织、调度与控制该项活动的进程，以实现最佳的效应和效益。而这种为编制科学的组织计划的有效方法统称为统筹方法。,例1 甲、乙两工程师从早上六时起床到上班前有一系列活动要做。对于同样的活动过程，有人忙乱不堪，甚至迟到，有人则又快又好，关键在于一个科学的活动实施计划。,例2 大型工程项目（三峡工程、南水北调工
2、程、人造卫星工程、宇航工程等）有如下活动：产品设计、仿真、试制、中试原材料设备定货、采购、运输、入库厂房、设备施工建筑、安装产品计划、生产、销售、安装、调试、维护 参与单位涉及国家各部门、各行业、事业单位，为高速度、低成本、高质量，并在规定期限内完成该工程项目，其关键在：抓好科学技术 抓好项目管理，组织协调好各单位、各任务、各工序的完成。,例3 三军联合作战演习空军夺取制空权，对敌实施地面攻击，运送空降兵海军舰艇护卫，运送陆军、海军陆战队登陆夺取滩头阵地登陆完成后的巩固阵地与纵深发展电子对抗部队实施情报收集分析与电子对抗参与兵种：海军航空兵、海军陆战队、水面舰艇部队、空军歼击机、攻击机、轰炸机
3、、电子对抗机各团、大队，坦克、炮兵、步兵、防化兵、通讯兵、侦察兵、导弹部队等。需迅速订好科学的作战演习计划，以便对作战演习过程演习过程进行有效的管理与控制。,6,网络计划,作为一个管理者，常常面临着一些复杂、大型的工程项目，这些工程项目涉及到众多部门和单位的大量的独立的工作或活动，如何来编制计划、安排进度并进行有力的控制，这是管理的重要内容。统筹方法是解决这些问题的强有力的工具关键路线法（CPM，Critical Path Method），美国杜邦公司提出，用于协调公司不同部门计划评审法（PERT，Program Evaluation and Review Technique），美国海军武装部
4、提出，用于导弹项目的管理和计划目前统称为PERT/CPM方法统筹方法可以应用在各种不同的项目计划上，特别适用于一些跨部门的工作计划，例如，新产品的研制开发，大型工程项目的建设，大型复杂设备的维修以及新系统的设计与安装等计划,统筹法发展历史CPM：1956年在美杜邦公司化工厂建立过程中由美兰德公司提出。PERT：1958年美海军特种计划局在研制“北极星”导弹核潜艇过程中在哈密尔顿公司及洛克菲勒公司协助下提出了一个“北极星计划”以管理整个工程过程中的8家总承包公司，250家分承包公司，3000家三包公司，9000家厂商，由于使用PERT技术，提高了工作效率使整个工期提前两年完成。GERT/CPM
5、在1966年由美国提出，并在阿波罗登月计划中首次使用成功，在英、阿的马岛之战中，1982年4月，英军三天完成计划网络，2003年美军攻击伊拉克（30万大军用三个月制订计划）,网络计划技术（统筹法）的功能完成工程需做哪些工序，各工序需多长时间完成？总工期预计多长时间？完成工程的各工序采用什么样的逻辑顺序关系？关键工作是什么？如何加快工程的完成。环境发生变化时，该工程的风险分析。,计划网络图（PERT图）,计划网络图 反映一个工程项目中各项作业（工序）的内在逻辑关系的一种有向图称为计划网络图，又称统筹图，工序流线图，PERT图等，以符号G表示。此中“内在逻辑关系”是指由于工程本身的工艺与组织性要求
6、，而对各工序提出的在时间上和空间上所要求的先后处理关系。,10,PERT网络图,PERT网络图的一些基本概念定义1（工序）指任何消耗时间或资源的行动、人、财、物、工时，用表示。紧前工序表示的是在另一项工序开始前，必须完成该工序紧后工序表示的是在一项工序结束后，立即开始的工序定义2（事项或事件）标志工序的开始或结束。不需消耗时间和资源。用表示。定义3（路线）指PERT网络图中，从最初事项到最终事项的由各项工序连贯组成的一条路。路线的时间是路线上各工序时间的总和。其中，各项工序累计时间最长的那条路线，决定完成网络图上所有工序需要的最短时间，称为关键路线。总的持续时间短于关键路线，却长于其他诸路线的
7、路线称为次关键路线。其余路线称为非关键路线。,11,确定型网络图,例：建筑项目管理,12,1，某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如下表所示，请画出其统筹方法的网络图,13,14,例2：我们把例1的进度表作一些扩充，如下表所示，请画出其统筹方法的网络图。,6,f,?是否正确,由于d是f 的紧前工序，所以d的结束应该是f 的开始，所以代表f 的弧的起点应该是，但是，b工序的结束也是，所以b工序也成了f 工序的紧前工序，这和题意不符合。,15,为此引入虚工序。虚工序是实际上并不存在而虚设的工序。仅用来表示相邻工序之间的衔接关系，虚工序不需要人力、物力等资源
8、与时间，在图中用虚线表示。本例中虚工序所需时间为0。,f,6,d38,f10,6,16,在网络图上添上g，h工序就得网络图如图如下：,上图中、两点间有2条弧。但是在计算机上，两点之间不管有多少弧，都认为是一条。因此再增加一个节点和引入虚工序。,17,PERT网络图的绘制,绘制PERT网络图时，一般从左到右，从上到下。事项的编号，箭头处必须大于箭尾处。工序关系的表达方式：（a）工序a结束后才开始b和c（b)c在a和b结束后才开始（c）a和b均结束后才可以开始c和d（d）c在a结束后开始，d在a和b结束后才开始,18,网络时间和关键路线 在绘制出网络图之后，我们可以用网络图求出：(1)完成此工程项
9、目所需的最少时间(2)每个工序的开始时间与结束时间(3)关键路线及其相应的关键工序(4)非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间间可以推迟多久,19,例：某公司装配一条新的生产线，其装配过程中的各个工序与其所需时间以及它们之间的相互衔接关系如下表所示，求：完成此工程所需最少时间，关键路线及相应关键工序，各工序的最早开始时间及结束时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久,20,绘制网络图，如下：,21,首先从网络的始点开始，按顺序计算出每个工序的最早开始时间(ES)和最早结束时间(EF)。我们设一个工序所需时间为t，则对同一个工序来说，
10、有 EFES十t由于工序a最早开始时间ES0，所需时间t60，可知工序a的最早结束时间EF0+60=60。我们在网络的弧a的上面，字母a的右边标上这对数据下图。由于任一工序只有当其所有的紧前工序结束之后才能开始，所以任一工序的最早开始时间应该等于其所有紧前工序最早结束时间中的最后的时间。上述的等量关系我们称之为最早开始时间法则，运用这个法则以及EFESt的关系，我们可以依次算出此网络图中的各弧的最早开始时间与最早完成时间。,最早开始时间和最早结束时间的计算,22,ES,EF,在上图中，例如工序h的最早开始时间应取工序d和e的最早结束时间中的最后时间，即在80与100中取最大者100而其最早结束
11、时间EFESt100十15115故在弧h上标以100，115,最早开始时间和最早结束时间的计算,23,其次，我们从网络图的终点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间(缩写为LF)，显然对同一工序来说，有LS=LF-t。对工序j可知其LF=170，t=35，可计算出LS=170-35=135我们把这两个数据标在网络图弧j的下面t右边的方括号内。由于任一工序必须在其所有的紧后工序开始之前结束，这样我们得到了最晚时间法则：在不影响整个工程最早结束时间的情况下，任一工序的最晚结束时间等于其所有紧后工序的最晚开始时间中的最早时间。运用这个法则和L
12、SLF-t的关系式，我们可以从收点开始计算出每个工序的LF与LS如下图所示,最晚开始时间和最晚结束时间的计算,24,例如在图中，工序b的LF的值是从其紧后工序j的LS值得到，即工序b的LF135，而工序b的LS的值为LF-t=135-4590。故在弧b下面标以90，135。,LS,LF,最晚开始时间和最晚结束时间的计算,25,接着，我们可以计算出每一个工序的时差，我们把在不影响工程最早结束的条件下，工序最早开始(或结束)的时间可以推迟的时间，称为该工序的时差，对每一个工序来说其时差记为TS，有 TSLS-ESLF-EF例如，对工序b来说，其时差 TSLSES906030。这就是说工序b至多可以
13、推迟30天开始，不至于影响整个工程的最早结束时间。我们称工序b是非关键工序。而对工序g来说，其时差TSLSES80800。这也就是说工序g的提前与推迟开始(或结束)都会使整个工程最早结束时间提前与推迟。我们称工序g是关键工序。由所有关键工序组成的线路称为关键线路（关键路径）。最后将各工序的时差，以及其他信息构成工序时间表，如下表所示。,时差的计算,26,27,关键路径,28,用WinQSB来求解关键路线,采用PERT-CPM模块,29,网络图的优化,1，时间资源优化在编制网络图计划安排工程进度时，我们要合理地利用现有资源，并缩短工程周期为了使工程进度与资源利用都得到比较合理安排，我们采取以下的
14、做法：(1)优先安排关键工序所需要的资源。(2)利用非关键工序的时差，错开各工序的开始时间，拉平资源需要量的高峰。(3)要统筹兼顾工程进度的要求和现有资源的限制，往往要经过多次综合平衡，才能得到比较合理的计划方案。,30,下面列举一个拉平资源需要量高峰的实例在前例中，若完成工序d，f，g，h，i的机械加工工人人数为65人，并假定这些工人可以完成这五个工序中的任一个工序，下面我们来寻求一个时间资源优化方案有关d，f，g，h，i工序所需的工人人数及上述工序开始时间，所需时间及时差如下表所示,31,若上述各工序都按最早开始时间安排，那么从第60天至第135天的75天里，所需的机械加工工人的人数如下图
15、所示,从图可见，在第7080天和第100110天这两段时间，需要工人数达到80与81人，远超过了现有工人人数。另一方面在第90100天和第115135天所需工人数仅有42人和26人，远远少于现有工人数这种安排的资源负荷是不均匀的，不妥当的。,32,我们应该优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰经过调整，我们让非关键工序f从第80天开始，工序h从第110天开始找到了时间-资源优化的方案.如下图所示，在不增加工人的情况下保证了工程按期完成,33,2，时间费用优化问题,在编制网络计划时，我们要考虑这样一些时间与费用的问题：在既定的时间前工程
16、完工的前提下，使得所需要的费用最少，或者在不超过工程预算的条件下，使得工程最早完工这些就是时间费用优化要研究和解决的问题加快工程进度的一个关键概念是应急处理。应急完成工序是指通过某些高费用的途径（如加班，雇佣临时工，使用特殊设备或材料等），把工序的完成时间减少到正常水平之下。,应急,正常,34,时间费用的优化问题可以化为线性模型来求解规划问题：若考虑工程项目的成本，包括应急费用，那么问题是在项目工期小于或等于项目管理者期望水平的限制条件下，使得总成本最小化。决策：（1）每项工序的开始时间（2）进行应急处理后每项工序的工期减少量（3）项目的期望完成时间。,35,设xi为工序i的最早完成时间，yi
17、为工序i的应急时间。假定工程开始时间为0，则对于工序1，有x1t1-y1，即x1+y1t1，其中t1为工序1的正常完成时间。对其他紧相邻工序i和j，有xj-xi tj-yj，即xj+yj-xi tj。其中tj为工序j的正常完成时间则线性规划模型为其中si为工序i的成本斜率，Ci为工序i说允许的最大应急时间，T为工程要求的完成时间。,36,举例：,继续前面的例子，下表给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用。该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩
18、短工期而增加的直接费用为最少。,37,38,设此网络图上第i点发生的时间为xi，工序(i，j)提前完工的时间为yij，则,39,40,结果：,我们缩短工序g的10天工期，缩短工序i的10天工期，这样我们可以多付出最少的直接费用6400元，提前20天即在150天里完成整个工程,41,对于该问题我们也可以用PERT图求解。在绘制了计划网络图、计算了工序的时间、找出关键路线之后，由于要求我们在150天里完成工程，缩短了正常工期的20天时间。我们在关键路线上，找出直接费用变动率最低的关键工序，最大限度的缩短其完成时间从前表上可知其关键工序a,d,g,i,j中，工序i的直接费用变动率最低，其次是工序g。
19、已知这两个工序都至多只能缩短10天，这样我们就缩短工序i和g各10天时间，而不需经缩短其他的关键工序和非关键工序就能保证在150天完成整个工程。为缩短这20天的工期付出的最少的直接费用为290 x10350 x106400。这个答案是和线性规划的答案一样的。,2023/6/23,42,工序延续时间估计,经验法与专家法（平均值）：适用于重复性工作，不确定性因素少三点估计法（又称六分法）其中a对工序e延续时间的最乐观时间（在顺利情况下工序e完成的最短可能时间）b对工序e延续时间的最悲观时间（最不顺利下工序e完成的最长可能时间）M对工序e延续时间的最可能时间（在正常情况下工序e完成耗费的时间）,20
20、23/6/23,43,三点估计法 这是由于通常认为工序延续时间,2023/6/23,44,随机性网络时间参数与关键路线,问题与求解例(培训计划制订),2023/6/23,45,解计算各工序的期望与方差(见上表右)绘制计划网络图,2023/6/23,46,解计算各工序的有关时间参数ES、LS、EF、LF、R(i,j),2023/6/23,47,解寻找使R(i,j)=0的关键工序及使R(i)=0的对应途经节点输出关键路线与关键工序计算总工期T的期望和方差 E(T)=Ta+Tb+Tg+Th+Ti=CP=2+3+4+4+2=15（天）结论：1.该计划网络G关键路线CP：a b g h i 2.该计划网
21、络G总工期T的期望CP=E(T)=15天,2023/6/23,48,结论：设n为计划网络G的工序数，CP为大型工程计划网络G的关键路线，T为G的任务总工期。若n1，则有：，其中 与 分别为关键路线CP路长的期望与方差对，G在规定工期T0内完工的概率有 aij工序（i,j）的最乐观时间 bij工序（i,j）的最悲观时间 mij工序（i,j）的最可能时间,总工期的概率特性,2023/6/23,49,在上例中取工期T0分别为15，17，18，20周，求 1.该计划网络按期T0内完工的概率 2.欲使按期完工的概率达到95%或99%，试确定相应的工程任务总工期T。解：1.对 有 现取 T0=15，则 此
22、中CP=15，CP=1.025，已由上例中求得。类似地有,2023/6/23,50,2.欲使按期完工的概率达到95%，则,2023/6/23,51,最关键路线与计划难易系数,定义：若在G中有关键路线CPi，i=1k，此中各关键路线有对应路长的期望与方差，i=1,2k，（此中显然有），若有，则称 为G的最关键路线（即方差最大的关键路线称为最关键路线）若 表执行最关键路线 的对应工期，则有，j=1k，即对任何给定工期T0，执行最关键路线时要在T0内完成的可能性最小，而考虑到只有该（最关键路线）上所有工序全部完成后工程方能完工，因此在G设计时应对 上的工序予以特别关注。,2023/6/23,52,定义：设T为G的工期（随机变量），CP为G的关键路线，CP与 为CP路长的期望与方差，则称 为执行给定工期T0的计划难易系数。例 对于上例的计划网络G，求解给定工期T0分别取13,15,17,18,20（周）时的计划难易系数0。解：,太保守，有潜力可挖,完成可能性很大,完成可能性很大,完成可能性较大,完成可能性小,作业,某购物中心正在计划对其现有的商业购物中心进行改革和扩张。该项目预计能提供一些新的商业空间，通过私人投资，资金已安排到位。该购物中心的业主所需做的就是策划、安排和完成该扩张项目，下表是所需工序一览表，试据此求出关键路线。表：某购物中心工序一览表,53,
