运筹学网络计划.ppt

运筹学网络计划.ppt

《运筹学网络计划.ppt》由会员分享，可在线阅读，更多相关《运筹学网络计划.ppt（58页珍藏版）》请在冰点文库上搜索。

第六章网络计划,引例：

沏茶,以网络图的形式制定计划，求得计划的最优方案。

并据以组织和计划生产，达到预定目标的一种科学的管理方法。

设：

有一项工程，分为若干道工序；已知各工序间的先后关系，以及各工序所需时间t。

问：

（1）工程完工期T=？

（2）工程的关键工序有哪些？

问题的一般提法,关键工序：

主矛盾工序，不能延期完工路线：

从始点到终点的一条路关键路线：

由关键工序组成的路线，是所有路线中时间最长的路线。

关键工序的延误将导致整个项目完成时间延误,相关概念：

两种方法的原理基本一致，都是用网络表示工程项目，以确定关键路线；这两种方法的主要区别是：

CPM方法对工程中各工序完工时间的估计是确定的，而PERT方法对时间估计是概率型的；PERT方法主要注重计划中的时间问题，CPM方法在把费用概念引人计划控制过程中，不仅注重时间问题，而且还考虑工程的费用和成本问题，考虑工程时间的均衡问题,求解方法：

关键路径法（CriticalPathMethd，简称CPM方法）计划评审技术（ProgramEvaluationandReviewTechnique，简称PERT法）,2.解法关键路径法（CPM）,分为三步：

绘制工程网络图标号法求工期T标号法求关键路线,准备工作:

将整个工程分解为若干工序确定各工序的前后顺序（紧前、紧后）确定工序完成时间,p135,2）图的结构,

（1）绘制工程网络图,结点：

表示相邻工序的时间分界点，称事项,相邻弧：

表示工序前后衔接关系，称紧前（后）工序；,权：

工序的完成时间,1）顺序：

按工序先后从左至右；,只有当事项的所有紧前工序完成后，事项的紧后工序才能开始。

连接箭尾的结点称为该工序的紧前事项连接箭头的结点称为该工序的紧后事项。

缺口：

多个始点或多个终点的现象。

（应当只有一个始点和终点）,回路：

方向一致的闭合链。

3）绘图要求：

图中不得有缺口、回路和多重边。

多重边的处理：

（1）绘制工程网络图（续）,一项工作只能用唯一的实箭线和唯一的双号表示。

处理方法：

增加虚工序。

虚工序,3）绘图要求：

（1）绘制工程网络图（续）,要尽量避免弧的交叉：

编号由左到右，不能重复（每条弧上起点的编号数小于终点的编号数）,P135,方法：

箭杆删除法给起点一个编号数1，设想将该点为起点的弧都去掉，从而又有新的起点，依次给新的起点编号，反复这样做直到终点已经编号为止。

例1：

某工厂进行技术改造，需要拆掉旧厂房、建造新厂房和安排设备。

这项改建工程可以分解为7道工序，其相关资料如下表：

A

（2）,B（3）,C（2.5）,D（6）,E（20）,F（4）,G

（2）,解：

1,2,3,4,5,6,C,B,A,D,2,E,3,F,4,G,5,H,6,I,J,I,K,L,I,M,N,1,7,8,9,10,11,用箭秆删除法标号（保证箭尾号大于箭头号）,例2：

绘制工程网络图,续左表,解：

1,A

（2）,D（3）,C

（2）,2,E（4）,3,F（7）,B（0）,G（6）,4,6,E（0）,5,I（10）,7,J（3）,H（4）,8,B（3）,两种情况需要引入虚工序：

两个工序A、B有相同的始点和终点（两个或两个以上的工序有相同的紧前工序，又同时作为另外一工序的紧前工序）,四个工序A、B、X、Y有如下关系：

A是X的紧前工序，A和B同时又是Y的紧前工序,P134图6.2,P134图6.1,虚工序,练习：

A

（2）,B（4）,C（9）,D（3）,E（6）,G（4）,F

（2）,H

（2）,

（2）用标号法求工期T,0,2,6,3,13,6,16,3,0,2,3,6,3,13,6,16,（3）求关键路（用标号法）,（3）求关键路（用标号法）,（不影响总工期条件下，任务可以延迟的最大幅度）,一个工序的总时差为0意味着该工序在不影响工期前提下机动时间为0，及工序的最早开始时间也是最迟开始时间，其开始和结束时间没有一点机动的余地,练习：

0,4,2,4,11,10,7,15,17,1计算最早开始时间（ES）与最早完工（EF）时间从网络起点开始,用下列公式计算最早开始时间（tES）和最早完工时间（tEF）:

最早开始时间=（紧前活动的）最早结束时间的最大值=开始结点的最早时间tES（i,j）=maxktEF（k,i）=ETi最早完工时间=最早开始时间+活动持续时间tEF（i,j）=tES（i,j）+t（i,j）,工序时间参数的计算：

2计算最晚开始时间与最晚结束时间从最后活动开始依次按下式计算每个活动最晚结束时间tLF和最晚开始时间tLS最晚结束时间=（紧后活动的）最晚开始时间的最小值=完成结点的最晚时间tLF（i,j）=minktLS（j,k）=LTj最晚开始时间=最晚结束时间活动持续时间tLS（i,j）=tLF（i,j）-t（i,j）,工序时间参数的计算（续）:

3总时差总时差:

不影响总工期条件下，任务可以延迟的最大幅度，用R（i,j）表示:

总时差=最晚开始时间最早开始时间=最晚结束时间最早结束时间R（i,j）=tLS（i,j）-tES（i,j）=tLF（i,j）-tEF（i,j）,p144,工序时间参数的计算（续）:

作业:

关键路线,逻辑关系图,网络结构图,A4,（0,1）,（4,1）,（11,2）,（14,2）,（14,4）,（26,5）,（31,6）,（35,7）,B7,C10,E12,D8,F7,G5,H4,1,2,4,6,7,8,5,3,0,4,11,26,14,14,31,35,35,31,26,14,14,14,0,4,课堂练习P150习题6.1,绘制网络图，关键路线，工期，总时差,课堂练习P150习题6.1,练习为筹建某餐馆，需制定计划。

将工程分为14道工序，各工序需时及先后关系如下表。

试求该工程完工期T及关键路径。

（2）求完工期（用标号法）,C

（1）,B（3）,A（10）,D

（2）,2,E（7）,3,F（3）,4,G（5）,5,H（4）,6,I（4）,J（3）,7,I（0）,8,K（6）,L（3）,9,I（0）,M（4）,10,N（7）,11,（3）求关键路（用标号法）,9,完工期T=38（天）；关键路：

D-E-F-G-H-I-K-N。

二、工程完工期的概率分析（计划评审技术PERT）,1、PERT与CPM的区别：

工程工期的概率分析是是时间不确定情况下PERT的主要工作,CPM工序时间是确定的,期望工期TE=关键工序的平均工序时间之和；工期方差=关键工序时间方差之和。

由概率论的中心极限定理总工期,确定平均工序时间的三点估计法：

方法：

首先计算,1、给定时间T*，求工期TT*内完工的概率,例15、已知某工程网络图，以及各工序的时间参数。

求工程在43天内完工的概率。

TE=42.33,关键路线I为:

ACFH；,解：

9,12.83,7.83,8.17,4,10.33,12.17,11,例2某工程可分为11项工作，有关资料如下表：

（1）画出施工网络图，确定关键路线及完工期TE；

（2）估计工程在20周内完工的概率。

期望工期TE=19；关键路：

A-D-J-K。

=0.6293,工程在20周内完工的概率为0.6293。

2、给定概率p，求完工可能性为p的工期,例、上例中，求完工可能性达95%的工期。

再由,压缩工程工期,思路：

1.向关键工序要时间2.在非关键工序挖潜力,赶工期问题中，只有压缩关键工序才能引起总工期缩短。

若网络图中同时有几条关键路线，则几条关键路线必须同时在各自线路上压缩一个关键工序，才能缩短总工期,压缩工期步骤：

一.选择压缩工序二.确定压缩量,问题：

保证质量。

不增加人力，物力尽量缩短工期,一.选择压缩工序的步骤1.构建关键路线网络，赋权为压缩费用率（对不可压缩工序赋权为M,表示压缩费用率很大）2.求此网络最小截3.选择最小截上工序同时进行压缩二.压缩量确定：

1.压缩量t不超过工序上允许压缩限度2.压缩量不超过关键路长与次关键路长之差值（一般限制压缩量不超过非关键工序最小总时差）,即压缩量t由下式确定：

（1）关键路线与工期

（2）工期压缩为18天，应如何选择压缩工序和压缩天数？

（3）工期压缩到17天，通过在

（1）中所选定的压缩工序上压缩3天能否达到目的什么？

例：

下图是某工程施工网络，图中单箭线表示普通工序，箭线上的tij（Cij,dij）中，tij为工序时间，Cij为该工序上每压缩一天所需的费用，dij为可压缩天数。

关键路线：

ACF,ADG,BEG工期TE=20天,

（1）.计算关键路、工期、总时差,10（4,9）,F,D,8（7,7）G,8（3,7）B,5（5,4）A,4（2,3）E,5（1,4）C,7（2,6）,

（2）构建关键路线网络（赋权值为费用率），确定最小割，选择压缩工序,用最大流标号法得最小割为（C,D,E），所以选择在工序C,D,E上压缩时间,根据非关键工序的总时差和压缩工序的限制，确定压缩量,得压缩量为,在C,D,E工序上各压缩两天，使总工期压缩至18天,3（4,2）J,3（4,2）,N,10（4,9）,F,D,H,L1（3,0）,M3（8,2）,P,1（4,0）,8（7,7）G,K,5（1,4）,5（4,4）,I,8（3,7）B,5（5,4）A,1（3,0）,2（2,1）E,3（1,2）C,5（2,4）,（3）工期压缩2天后，关键路线已发生变化，所以不能在中选中的压缩工序压缩三天以达到工期成为17天的目的。

重复上述步骤，得新的网络，重新确定关键路线和非关键路线的总时差，如图,10（4,9）,F,D,8（7,7）G,K,5（1,4）,5（4,4）,I,8（3,7）B,5（5,4）A,2（2,1）E,3（1,2）C,5（2,4）,继续构建关键路线网路，确定最小割为C,D,E,K，作为压缩工序。

确定压缩量,根据非关键工序的总时差和压缩工序的限制，确定压缩量,最小时差，得压缩量为,在C,D,E,K工序上各压缩1天，使总工期压缩至17天,工程费用分析,问题：

编制工程网络计划时，不仅要考虑工期时间，还应到考虑工程造价对一个工程来说，无论是以考虑工程费用为主，还是以控制时间进度为主，都必须对工程计划进行时间费用分析，从而可综合考虑制定最优的计划。

费用概念,直接费用：

指人工、材料、燃料等直接用来完成工程任务的费用。

工序直接费用率：

指一道工序缩短单位时间所需增加的费用,间接费用：

指管理人员的工资、办公、采购等并非直接用于完成工程任务的费用。

间接费用率p:

整个项目的工期每提前单位时间可节约的费用,工程的时间费用关系图,费用,工期时间,总费用,直接费用曲线（工程的时间费用曲线）,间接费用曲线,最低成本工期,TE,总费用曲线由同一工期下的直接费用和间接费用相加得到,压缩工期会增加直接费用，但减少了间接费用延长工期会增加间接费用，但可能减少直接费用,因此只有当压缩关键工序时间增加的直接费用小于由此导致工期缩短而节约的间接费用时，这一压缩才进行。

最低成本工期的确定：

确定最低成本工期的步骤：

一、绘制网络图，计算工序总时差R（i,j），确定TE与关键路线，计算相应工程费用。

二、在各关键路线上所有可压缩的工序中，各确定一个本线路上费用率最低的工序作为压缩工序，这些压缩工序之集合用I表示.一般可由1）.构建关键路线网络，赋权为压缩费用率（对不可压缩工序赋权为M,表示压缩费用率很大）2）.求此网络最小截3.）选择最小截上工序同时进行压缩,q（i,j）工序（i,j）的费用率（i,j）工序（i,j）的工序时间可缩短下限，即赶进度时间p单位时间的间接费用率,三.计算这些压缩工序上费用率之和，若（q-p）0，则表示压缩工期将引起工程费用上升，若（q-p）0时为止,1.绘制网络图，计算工序总时差R（i,j），确定TE与关键路线，计算相应工程费用,2.在各关键路线上各确定一个本线路上费用率最低的工序作为压缩工序，这些压缩工序之集合用I表示,最低成本工期,是,否,最低成本工期确定步骤,压缩,例：

下图表示由l、m、n、o、p、q、r其道工序组成的网络图及有关时间参数，工程有关费用由下表给出，正常工期TE=60天，是确定赶工期问题中最低成本工期,循环1第一步，建立网路图，如下图所示，确定各工序总时差R（i,j），见表2，关键路线由q和r二道工序组成，工序时间TE=60天。

方案1：

工期为60天（正常工期）的费用：

S1=12800+200*60=24800元,表2,m,第二步，关键路线上只能缩短r工序，则r工序为压缩工序。

第三步，r工序费用率qr=150，（qr-p）=-500。

可进一步压缩。

第四步，确定压缩时间t，显然有在r工序上压缩时间20天，得新工序时间,循环2第一步，建立网路图（图3），确定各工序总时差R（i,j），见表3，有两条关键路线（7）-（10）-（14）和（7）-（12）-（14），完工期为40天,方案2：

工期为40天的工程费用：

S2=12800+150*20+200*40=23800元,表3,7,12,14,11,13,10,10,0,25,40,20,Q（）,20,O（60）,25,P（）,15,20,R（150）,10,l,m,15,10,n,图3,0,15,30,40,20,25,25,第二步，在关键路线网络上确定最小割为o工序（7，12）和r工序（10，14）并将其作为压缩工序；第三步，压缩工序费用率总和为q=q（7，12）+q（10，14）=210此时，（q-p）0，所以不能在压缩工期，任何压缩都将引起总费用上升.最低成本工期为40天，相应费用23800元。