《管理运筹学》07-网络规划.ppt

《《管理运筹学》07-网络规划.ppt》由会员分享，可在线阅读，更多相关《《管理运筹学》07-网络规划.ppt（48页珍藏版）》请在三一办公上搜索。

1、第七章网络规划,第七章网络规划,第一节：现实中的网络规划问题第二节：图的基本概念 第三节：树 第四节：最大流问题 第五节：最短路径问题 第六节：最小费用最大流问题第七节：网络计划技术第八节：网络规划的应用,7.7网络计划技术,当系统决策之后，面临的问题就是制定计划和组织实施。网络计划技术就是在制定计划和组织实施过程中采用的一种科学方法。本节主要对目前管理中常用的网络计划方法做一系统的介绍。网络计划技术利用网络图对计划任务的进度、费用及其组成部分之间的相互关系进行计划、检查和控制，以使系统协调运转的科学方法。由于这种方法的主要特点是统筹安排，为了突出这一特点，我国把各种不同的网络计划方法统称为统

2、筹法。,一、系统管理的网络计划技术,（一）甘特图法该方法是科学管理的奠基人泰勒的学生、美国福兰克兵工厂顾问甘特于 20 世纪40 年代开发的一种计划与管理技术。它以时间为横坐标，以工序为纵坐标，以线条的长短表示一项工作或作业的开始和完成时刻以及工作的进展情况。由于它以条形图进行系统计划与管理，故又称横道图、条形图等，图7-28即是一份简化的现场准备作业的条形图。,甘特图,平整场地 建休息室 建材料库 设备安装 材料进场 施工,一、系统管理的网络计划技术,（二）关键线路法关键线路法（Critical Path Method，CPM）是美国杜邦公司为建造新工厂从事计划与管理的研究而提出的，并在 1

3、958 年的建厂工作中发挥了很大作用，使工程工期提前两个月，初步显示出其优越性。而后，杜邦公司不仅把 CPM 法应用于大型工程，而且也应用于小型工程和维修工程，都同样收到了良好的效果。美国加泰迪克公司在 47项工程中使用 CPM 法，平均节约时间 22%，节约资金 15%，其效果是显著的。,一、系统管理的网络计划技术,（三）计划评审技术计划评审技术（Program Evaluation and Review Teacnique，PERT，也称计划协调技术）是由美国海军特种计划局和洛克希德公司、汉米尔顿公司于 1958 年 1 月联合开发的一种新的计划管理方法。它的首次应用使美国“北极星”导弹潜

4、艇工程的工期由原计划的十年缩短为八年。由于它的成功，自 1962 年起美国政府规定一切新开发的工程项目必须采用这种方法。我国的很多大型开发性工程也都应用了这种方法，收到了良好的效果。,一、系统管理的网络计划技术,（四）决策关键线路法任何一项工作都可用多种方案进行计划和管理，因此需要在多种方案的比较中进行决策。然而 CPM 和 PERT 二种方法虽然先进，但却只能考虑完成任务的一种方案，对不同方案必须画出不同的网络图，不仅增大绘制网络图的工作量，而且，在比较和分析时也不能一目了然。为了克服这种局限性，又开发了决策关键线路法（Decision CriticalPath Method，DCPM）。,

5、一、系统管理的网络计划技术,（五）图解评审技术上述各种方法中各工序均属确定型工序，但实践中存在随机工序，如检验工序后的返修工序，这类工序应用上述各种方法很难解决，图解评审技术（Graphical evaluationand Review Technique，GERT）是一种广义网络计划法，是解决这类问题的一种方法。,二、网络计划技术应用的程序,（一）、网络计划技术应用的一般程序,二、网络计划技术应用的程序,（一）、网络计划技术应用的一般程序,（二）、网络图的绘制,1、网络图的组成,任务,工作,线路,起点开始沿箭线方向连续通过一系列箭线和节点最后到达终点所经过的路线,指一项有目的、有开始和结束标

6、志的许多相互关联且有不同指标要求的工作所组成,为完成某项任务在工艺和组织管理上相互独立的活动（子任务）,紧前工作,紧后工作,（二）、网络图的绘制,2、网络图的绘制,（1）任务的分解和分析,（二）、网络图的绘制,2、网络图的绘制,（2）画网络图,单代号网络图,（二）、网络图的绘制,2、网络图的绘制,（2）画网络图,双代号网络图,双代号（AOA）网络图（activityonarrow network）是用有向箭线及其两端的两个节点编号表示工作的网络图。在双代号网络图中，每一项工作都用一根有向箭线和箭线两端的两个节点来表示，每个节点都编以号码，箭线两端的两个节点的号码即代表该箭线所表示的工作,三、双

7、代号网络图的绘制,1.双代号网络图的组成,由工作、节点（事件）和线路三部分组成。,节点,线路,3,5,2,3,6,4,虚工作,关键线路,2.双代号网络图的绘制,（1）双代号网络图各种逻辑关系的正确表示方法,该工作必须在哪些工作之前进行？该工作必须在哪些工作之后进行？该工作可以与哪些工作平行进行？,虚工作一般起联系、区分和断开三个作用,详见P231的表7-8,2.双代号网络图的绘制,（2）双代号网络图的绘制规则,必须正确表达已定的工作间的逻辑关系。,网络图中，严禁出现循环回路。,严禁出现双向箭头箭线和无箭头连线。,严禁出现没有箭头节点的箭线或没有箭尾节点的箭线,当某节点有多条外向箭线或有多条内向

8、箭线时，可采用母线法绘图，允许多条箭线经一条共用母线引出或引入节点,应尽量避免箭线交叉，当箭线交叉不可避免时，可采用过桥法或指向法。,只能有一个起点节点；在不分期完成任务的网络图中，应只有和一个终点节点；其他所有节点均为中间节点。,任意两个节点之间只能有一条唯一的箭线，不得有两个或两个以上的箭线从同一节点出发且同时指向同一节点。,详见P234、5的图,2.双代号网络图的绘制,（3）双代号网络图的节点编号,箭尾节点的号编码应小于箭头节点的号码。,在一个网络图中，所有的节点不能出现重复的编号。,（4）双代号网络图的绘制步骤,分解任务，划分施工工作，制定完成任务的全部工作结构分解表。,确定全部工作的

9、逻辑关系，绘制工作逻辑关系表（矩阵表）,确定每一工作的持续时间，制定最终的工程分析表,根据工程分析表绘制并修改网络图。,2.双代号网络图的绘制,（5）双代号网络图的绘制方法,绘制没有紧前工作的工作箭线，使他们具有相同的开始节点，以保证网络图只有一个起点节点。依次绘制其他工作箭线。当各项工作箭线都绘制出来以后，应合并那些没有紧后工作的工作箭线的箭头节点，以保证网络图只有一个终点节点。,无紧前工作的工作（即双代号网络图开始的第一项工作），其开始节点位置号为零；有紧前工作的工作，其开始节点位置号等于其紧前工作的开始节点位置号的最大值加1；有紧后工作的工作，其结束节点位置号等于其紧后工作的开始节点位置

10、号的最小值；无紧后工作的工作（即双代号网络图开始的最后一项工作），其结束节点位置号等于网络图中各工作的结束节点位置号的最大值加1。,节点编号：,第7章 网络规划,21,例7-9 已知某任务的工作构成及其逻辑关系如表7-6所示，试绘制双代号网络图。,解：用矩阵表确定紧后（前）工作,确定各工作的开始节点位置号和结束节点位置号,第7章 网络规划,22,第7章 网络规划,23,例7-10 已知某项目的工作构成及其逻辑关系如表7-9所示，试绘制双代号网络图。,根据工序之间的关系初步绘制如图7-47。,简化为图7-48。,四、双代号网络图的时间参数计算,（一）、时间参数的概念,1、工作持续时间,（1）定额

11、计算法（确定型）：,Di j工作ij的持续时间Qi j工作ij的工程量S产量定额（m3/工日、m2/工日、T/工日、m3/台班）R工人数（机械台班数）H时间定额(H1S),四、双代号网络图的时间参数计算,（一）、时间参数的概念,1、工作持续时间,（2）三时估算法：,Di j工作ij的持续时间 a工作ij的乐观持续时间估计值(Optimistic time)b工作ij的悲观持续时间估计值(Pessimistic time)；m工作ij的最可能持续时间估计值(Most Likely time)。,四、双代号网络图的时间参数计算,（一）、时间参数的概念,2、工期,（1）计算工期：根据网络计划的时间参

12、数计算出来的工期，用Tc表示。（2）要求工期：任务委托人提出的所要求的工期，用Tr表示。（3）计划工期：在要求工期和计算工期的基础上综合考虑需要和可能而确定的工期，用Tp表示。,3、工作最早时间,最早开始时间：是指在紧前工作的约束条件下，本工作可能开始的最早时刻，用ESi-j 表示。最早完成时间：是指在紧前工作的约束条件下，本工作可能完成的最早时刻，用EFi-j 表示。,四、双代号网络图的时间参数计算,（一）、时间参数的概念,4、工作最迟时间,最迟开始时间：是指在不影响整个任务按期完成的前提下，本工作最迟必须开始的时刻，用LSi-j 表示。最迟完成时间：是指在不影响整个任务按期完成的前提下，本

13、工作最迟必须完成的时刻，用LFi-j 表示。,5、工作的时差,总时差(TotalFloatTime)：在不影响总工期的前提下，本工作可以利用的机动时间，用TFi-j 表示。自由时差(FreeFloatTime)：在不影响紧后工作最早开始时间的前提下，本工作可以利用的机动时间，用FFi-j 表示。,四、双代号网络图的时间参数计算,（三）、时间参数的计算（图上计算法）,1、按工作计算法计算时间参数,（1）工作的最早开始时间和最早完成时间,没有紧前工作的工作ij（以起点节点为箭尾节点的工作)ESi j=0,有紧前工作的工作ij，当工作ij只有一项紧前工作hi时 ESi jESh iDh i,当工作i

14、j有多项紧前工作时 ESi jMaxESh iDh i,工作ij的最早完成时间应按下式计算：EFi jESi jDi j,四、双代号网络图的时间参数计算,（三）、时间参数的计算（图上计算法）,1、按工作计算法计算时间参数,（2）网络计划工期的计算,网络计划的计算工期当终点节点为n时，箭头指向终点节点的所有工作的最早完成时间的最大值即为网络计划的计算工期Tc，其计算公式为：Tc=MaxEFmn,网络计划的计划工期网络计划的计划工期Tp的确定应按下述规定：当已规定了要求工期Tr时：TpTr 当未规定要求工期时，可令计划工期等于计算工期：TpTc,四、双代号网络图的时间参数计算,（三）、时间参数的计

15、算（图上计算法）,1、按工作计算法计算时间参数,（3）工作的最迟完成时间和最迟开始时间,工作ij的最迟完成时间LFi j应从网络计划的终点节点开始，逆着箭线方向逐项计算，并符合下列规定：,没有紧后工作的工作m n（以终点节点为箭头节点的工作），其最迟必须完成时间LFm n应按网络计划的计划工期Tp确定，即：LFm n=Tp,有紧后工作的工作，当工作ij只有一项紧后工作jk时，其最迟必须完成时间LFi j为：LFi j LFjkDjk,当工作ij有多项紧后工作jk时，其最迟必须完成时间LFi j应为：LFi j=MinLFjkDjk,工作ij的最迟必须开始时间LSi j应按下式计算：LSi j

16、LFi jDi j,四、双代号网络图的时间参数计算,（三）、时间参数的计算（图上计算法）,1、按工作计算法计算时间参数,（4）工作的总时差,根据总时差TFi j的定义 TF i jLSi jESi j TF i jLFi jEFi j,（5）工作的自由时差,FFi jESjkEFi j,FFm nTpEFm n,（6）按工作计算法计算时间参数示例,例7-11 已知某项目的有关资料如下表所示:,0,11,1,1,1,2,3,4,5,6,A,B,C,D,E,F,H,I,5,3,6,2,5,5,3,1,0,2,1,0,0,16,11,16,11,0,0,5,11,5,0,0,5,0,5,0,8,3,

17、1,11,9,8,3,10,5,13,8,1,2,14,11,16,13,2,2,11,11,13,13,0,1,4,1,5,2,1,TP=16,关键路线,四、双代号网络图的时间参数计算,（三）、时间参数的计算（图上计算法）,2、按节点计算法计算时间参数,节点最早时间：是指双代号网络计划中，以该节点为开始节点的各项工作的最早能够开始的时间，用ETi表示。,节点最迟时间：是指双代号网络计划中，以该节点为完成节点的各项工作的最迟必须完成的时间，用LTi表示。,2、按节点计算法计算时间参数,（1）节点最早时间的计算,当起点节点i未规定其最早开始时间时，ETi其值应等于0，即：ETi0,当节点j只有一

18、条内向箭线时，其最早时间ETj为：ETjETiDi j,当节点j有多条内向箭线时，其最早时间ETj为：ETjMaxETiDi j,（2）网络计划工期的计算,TcETn,（3）节点最迟时间的计算,终点节点n的最迟时间LT n应按网络计划的计划工期Tp确定：LTn=Tp,当节点i只有一条外向箭线时，其最迟时间LTi为：LTiLT jDi j,当节点i有多条外向箭线时，其最迟时间LTi为：LTiMinLT jDi j,2、按节点计算法计算时间参数,（4）工作时间参数的计算,ESi jETi,EFi jETiDi j,LFi jLT j,LSi jLT jDi j,TF i jLT jETiDi j,

19、FFi jETjETiDi j,例7-13按工作计算法计算时间参数示例,1,2,3,4,5,6,A,B,C,D,E,F,H,I,30,50,20,30,10,8,9,G,10,10,10,20,20,30,J,10,0,20,30,40,50,50,70,120,130,130,120,70,90,70,40,50,70,10,0,7,例7-13按工作计算法计算时间参数示例,0,0,10,10,20,70,30,50,40,40,50,70,50,90,70,70,120,120,130,130,（四）、表上计算法,五、网络图的优化,（一）、工期优化,工期优化也称时间优化，就是当初始网络计划的

20、计算工期大于要求工期时，通过压缩关键线路上工作的持续时间或调整工作关系，以满足工期要求的过程。,压缩关键线路方法,调整工作关系的方法,（二）、资源优化,资源(人力、材料、机具设备、资金等)的优化，就是要解决网络计划实施中的资源供求矛盾或实现资源的均衡利用，以保证工程的顺利完成，并取得良好的技术经济效果。通常，资源优化有两种不同的目标：资源有限，工期最短；工期一定，实现资源的需求均衡。资源有限使工期最短的优化是指在资源供应有限的前提下，保持各个工作的每日资源需求量(强度)是常数，合理地安排资源分配，寻找最短计划工期的过程。,（三）、最优工期,工期-成本优化的目的在于：(1)寻求直接费与间接费总和

21、即成本最低的最优工期TS，以及与此相对应的网络计划中各工作的进度安排。(2)在工期规定(Ti)的条件下，寻求与此相对应的最低成本，以及网络中各工作的进度安排。,优化的思路,缩短工期,缩短关键工作的时间,缩短费用率最小的关键工作的时间,(1)当关键线路只有一条时，首先将这条线。路上费用率ei-j最小的工作的持续时间缩短t。此时，应满足,(3)步骤(1)或步骤(2)的工作应进行多次，以逐步缩短工期，使计划工期满足规定的要求，并计算出相应的直接费总和及各工作的时间参数。,且保持被缩短持续时间的工作i-j仍为关键工作（即其压缩幅度小于或等于工作的总时差）。,(2)如果关键线路有两条以上时，那么每条线路

22、都需要缩短持续时间t，才能使计划工期也相应缩短t。为此，必须找出费用率总和e i-j为最小的工作组合，我们把这种工作组合称为“最小切割”。,优化示例,例7-15 某网络计划中各工作的工期成本数据列于表，给出了各工作的正常持续时间D，加快的持续时间d，及与其相应的直接费用M和，计算后所得的费用率e也列在表中。假定每周的间接费用为1.5万元。试进行工期-成本优化,1,3,2,5,4,6,6，6,30，0,24，12,18，6,30，12,36，0,30，0,12，48,96,0.57,1,3,2,5,4,6,6，6,30，0,24，0,18，6,30，0,36，0,18，0,12，48,84,4-

23、6缩短12天,总费用减少：-1.5X12+0.57X12=-11.16,1-3缩短6天,1,3,2,5,4,6,6，0,24，0,24，0,18，0,30，0,36，0,18，0,12，42,78,4-6与3-5同时缩短2天,总费用减少：-1.5X6+1X6=-3,1,3,2,5,4,6,6，0,24，0,24，0,18，0,36，0,16，0,12，42,76,28，0,总费用减少：-1.5X2+1.15X6=-0.70,7.8网络规划的应用,某公司有一个管道网络如图7-29所示，使用这个网络可以把石油从v1运到v7。由于输油管道长短不一，每段管道除了有不同的流量限制cij外，还有不同的单位

24、流量的费用bij。图中每边上的数值表示（cij，bij）。如果使用这个网络运送石油，怎样运送才能运送最多的石油，并使运送的费用最小？,图7-24.应用问题图示,线性规划法求解,第一步：先求出网络的最大流令（vi，vj）上的流量fij，则最大流的数学模型为：Max F=f12+f14,s.t.(f23+f25)-f12=0(f35+f36)-(f23+f43)=0(f43+f46+f47)-f14=0 f57-(f25+f35)=0 f67-(f36+f46)=0 fij cij fij0,图7-25.应用问题电子表格求解图示（1）,用电子表格求解，可得最大流量为10，如图7-25所示。,线性规划法求解,第二步：在最大流量的所有解中，找出一个最小费用的解。数学模型为：Min z=6f12+3f14+4f25+5f23+4f35+3f36+2f43+3f46+8f47+7f57+4f67,s.t.f12+f14=10(f23+f25)-f12=0(f35+f36)-(f23+f43)=0(f43+f46+f47)-f14=0 f57-(f25+f35)=0 f67-(f36+f46)=0 0-(f47+f57+f67)=-10 fij cij fij0,图7-26.应用问题电子表格求解图示（2）,用电子表格求解，可得最大流量为10，总费用为145。如图7-26所示,