运筹学基础-网络计划(2012修正)

第七章计划评审方法和关键线路法网络计划技术计划评审技术（ProgramEvaluationandReviewTechnique，PERT)

是一种组织生产和进行计划管理的科学方法，也称统筹法。它是综合运用计划评审技术和关键路线法的一种较为先进和计划管理方法。关键路线法（Criticalpathmethod,简写CPM)是对计划项目进行核算、评价，然后选定最优计划方案的一种技术。

是在计划项目的各项错综复杂的工作中，抓住其中的关键路线进行计划安排的一种方法。第一节PERT网络图及其绘制规则网络图又叫箭头图或统筹图，它是计划项目的各个组成部分内在逻辑关系的综合反映，是进行计划和计算的基础，即网络计划技术的基础是网络图。一、网络图的分类

箭线式网络图以箭线代表作业(活动)，以结点代表作业的开始和完成。需要引进虚作业(以虚线表示)，其特点是布图明朗，应用广泛。

结点式网络图以结点代表作业(活动)，以箭线表示各之间的待后承接关系。不需要引进虚作业，但其特点是线条纵横交错，不一目了然，应用不广泛。箭线式网络图例135791113151719212325272931ABDEFGHCIJKLMNOPQ箭线代表作业结点代表作业的开始和完成结点（事件）式网络图例始BACDEFGHIJKMNOLPQx结点代表作业箭线代表作业的衔接二、箭线式网络图的构成箭线式网络图是由作业、事件（结点）和线路三个部分组成。1.作业指任何消耗人力、物力或时间等资源的相对独立的作业过程，又称作业或工序。作业在网络图中的表示在网络图中作业用箭线“→”表示，从箭尾到箭头表示一项作业的开始到终结的过程。在箭线的左（上）侧写上作业的名称，右（下）侧写上该作业所占用的时间。与某项作业前面直接相连的作业称为紧前作业，其后直接相连的后继作业为紧后作业。

虚作业：虚作业是为了表达相邻工序之间的逻辑关系而虚设的作业。不消耗时间、费用和资源，一般用虚箭线表示。026机器解体82天机器部分维修总装试车5天1天2.事件（结点）事件（也叫结点），是相邻作业的分界点，标志着作业的开始或结束。事件（结点）在网络图中的表示一般用圆圈“Ο”来表示，每个结点编上顺序号；箭尾结点表示作业的开始，箭头结点表示作业的完成。结点既不消耗人力、物力，也不占用时间。一项规划只有一个总开始结点称为最初结点，和一个总结束结点称为最终结点。处在网络中间的结点具有两重性，对前面的作业它是终点、对后面的作业它是始点1539b711achijkefd3.线路线路是指从最初事件开始，顺着箭线的方向，由各项作业连贯组成的，到达最终事件的一条路。从最初事件到最终事件可以有不同的路。1539b711achijkefd563765(65)13115730908630(4)131179(3)1311753010(2)171166125(1)1511712路长：线路的总长度称为路程长，也是线路总作业时间如图所示：从起点①连续到终点⑪的各条线路是路长最长的线路称为关键线路关键路线

在所有的线路中，总作业时间最长的线路就是关键路线。或叫主要矛盾线。关键线路决定整个网络计划的完工时间。

关键路线，也可由所有各条线路的路长中最长的一条线路所决定。

网络分析的主要任务是找出工程中的关键路线，因为它决定着完工期。如果这条线路上工作进度有耽误，则整个工程的工期就要向后推迟；相反，如果能采取积极措施缩短这条线路的完工时间，工期就可能提前。1539b711achijkefd563765关键路线三、绘制网络图的规则和注意事项方向的规定网络图是有方向的，工序应按工艺流程顺序或工作的逻辑关系从左向右排列。作业表示的规定一条箭线和它的相关结点只能代表一项作业，不能代表多项作业两个结点之间只能有一条箭线相连正确的画法13可引入虚作业。132不正确的画法虚作业是为了表达相邻作业之间的逻辑关系而虚设的作业。它不消耗时间、费用和资源，一般用虚箭线表示。虚作业的引进原因(1)虚作业

两个事件之间的工作过程只能代表一项作业，当两个或两个以上的作业具有同一个始点和终点时，需要引入虚作业，予以区别。026机器解体82天机器部分维修总装试车5天3天4电器部分维修虚作业3天虚作业的引进原因(2)是为了正确表示各个作业之间的先后承接关系，有时必须引入虚作业。如一个工程各个作业之间的先后关系如表：1539b711achijkefd各项作业之间的关系和表达方式作业a结束后可以开始b和cabc作业c在a和b均结束后才能开始abc

a、b两项均结束后可以开始c和dacdb

c在a结束后即可进行、d必须在a、b两项均结束后才能开始。acdb

不允许出现缺口与回路编号的规定编号应从始事件开始，按照时序依次从小到大对事件编号，直到终事件。编号时不允许箭头编号小于箭尾编号。事件的编号原则箭尾事件(i)小于箭头事件(j)；一般采用非连续编号，即可空留出几个号，跳着编，将来有变化时，不致打乱全局。132132网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。尽量避免箭线之间的交叉1234569781011

为了方便计算和美观清晰，PERT网络图中通过调整布局，尽量避免箭线之间的交叉。调整前1234569781011调整后四、箭线式网络图的绘制1.任务的分解就是把一个计划项目的总任务分解成一定数量的分任务，并确定它们之间的先后承接关系分解任务的原则工作的性质不同或由不同单位执行的工作应分开；同一单位进行的工作，时间先后不衔接的要分开；如产品设计与工装设计，铸造、锻、机械加工、装配要分开如技术设计与工作图设计，材料采购与外协件采购要分开占用时间不消耗资源，但影响工程完工日期的工作应作为分任务；如油漆后的干燥，热处理后的冷却，方案的审批等分解任务的要求编制计划要熟悉业务，了解工程项目的各个组成部分，深入调查。例：下表是某一工程的作业明细表任务经过分解以后，可以列出作业明细表。某一工程的作业时细表2.画网络图(以前图为例)第一步：先画出无紧前作业的A、B，给网络始点编号为①

第二步：用一条斜线“\”消去已画入网络图的作业A、B，

在A后面，画出紧前作业为A的作业E；在B后面，画出紧前作业为B的作业D；给新增的事件编号为③、⑤，在A与B后面，画出紧前作业为A、B的作业C；画作业C时要引进虚作业，为新增的事件编号为⑦。

第三步：用一条斜线“\\”消去已画入网络图的作业C

将F画在紧前作业C之后；为新增的事件编号为⑨。

第四步：用一条斜线“\\\”消去已画入网络图的作业D、E、F

将G画在紧前作业E、F之后；将H画在紧前作业D、F之后，引入虚作业第五步：再用一条斜线“\”消去已画入网络图的作业G、H

以此类推，最后得出网络图某工程的网络图

1AB3ED5C79F13GH1511I1719J21又例f1357911abcde练习：练习1：练习2：答案F175311ACDEB答案F15311ACDB7E9第二节网络时间的计算

网络时间的计算有三种计算方法：图上计算法、表格计算法和EXCEL计算法。图上计算法要用的有关符号作业最早开始符号。在长方形符号中标以作业最早开始时间值，该符号放在箭线的上方，靠近前事件i的右上角。作业最迟完成符号。在三角形符号中标以作业最迟完成时间值，该符号放在箭线的好方，靠近后事件j的左好角。ESi,j19101379LFi,j一、图上计算法（一）作业时间作业时间就是在一定的生产技术条件下，完成一项作业或一道工序所需的时间，符号Ti,j就是表示i→j这项作业的作业时间。三种可能估计：最乐观时间：在最理想的情况下完成工序所需时间a；最悲观时间：在最不利的情况下完成工序所需时间b；最可能时间：在正常情况下完成工序所需时间m。加权平均就是工序时间t确定作业时间的方法：

(1)单一时间估计法：就是在估计各项作业的时间时，只确定一个时间值。

(2)三种时间估计法：就是在估计各项作业的作业时间时，先估计出三个时间值，然后再求出完成该作业的作业时间。例、求作业的期望时间和方差各项作业的三个估计时间如下表，求各作业的期望时间和方差。作业(i,j)代号估计完成时间（a-m-d)/T(1)(2)(3)(1,2)A3-5-7(1,3)B8-9-16(1,4)C8-11-14(3,4)D2-4-6(2,5)E3-4-5(4,6)F8-16-18(5,6)G18-20-28(5,8)H26-33-52(5,7)I18-25-32(7,8)J12-15-18(6,8)K11-21-25计算：作业(i,j)代号估计完成时间（a-m-b)/T期望完成时间（d）方差(1,2)A3-5-750.44(1,3)B8-9-16101.78(1,4)C8-11-14111.00(3,4)D2-4-640.44(2,5)E3-4-540.11(4,6)F8-16-18152.78(5,6)G18-20-28212.78(5,8)H26-33-523518.78(5,7)I18-25-32255.44(7,8)J12-15-18151.00(6,8)K11-21-25205.44（二）作业时间参数计算其值等于从初始点起到本作业的最长路线上各作业时间之和。从最初作业开始，自左向右，顺着箭线方向逐个计算。1.作业最早可能开工时间ESi,j截取下面部分讨论在箭线式网络图中，要计算的作业时间有两个，即作业的最早开始时间、最迟完成时间。43EF479113551315CDGH65作业最早开始时间计算如下：已知：ES3,7=3，ES5,7=3，T3,7=4，T5,7=3，T7,9=4。求ES7,9=？ES9,11=？ES11,13=？ES11,15=？ES7,9=max{ES3,7+T3,7，ES5,7+T5,7｝=max{3+4，3+3}=7ES9,11=ES7,9+T7,9=7+4=11ES7,9=？43EF479113531315CDGH6533ES9,11=？ES11,13=？ES11,15=？711ES11,13=

ES11,15=ES9,11+T9,11=11+3=141414

2.作业最迟必须完工时间LFi,j指作业最迟必须完工的时刻，否则将会影响后续作业按时开工，以至推迟整个工程的完工时间。最终作业的最迟完成时间应等于总完工时间从终点开始，从右向左，逆箭线方向逐个计算。截取下面部分讨论43EF479113531315CDGH65事件最迟完成时间计算如下：已知：LF11,13=20，LF11,13=20，T7,9=4，T9,11=3，T11,13=6，T11,15=5。求LF9,11=？，LF7,9=？LF9,11=min{LF11,13-T11,13，LF11,15-T11,15}

=min{20-6,20-5}=14LF7,9=LF9,11-T9,11=14-3=11LF9,11=？LF7,9=？43EF479113531315CDGH652020LF3,7=？LF5,7=？1411LF3,7=LF5,7=LF7,9-T7,9=11-4=777作业时间的完整计算作业的最早开始时间是顺着箭线的方向，逐个计算；作业的最迟完成时间是逆着箭线的方向，逐个计算；00CF4300AB23

1I6GH2J57E5D1

3

5

7

9

11131517192100223337101010101723完工时间28282317171515101010733330关键线路28（三）时差与关键路线

一个工作或一个工程有多大时差，就表明了有多大的机动时间可以利用。时差越大，则时间的潜力也越大。即可以将工作的资源暂时调出去支援关键性线路。计算和利用时差是网络分析中一个重要问题，它为计划进度的安排提供了可供选择和协调的可能性，也是确定关键线路的依据。时差又称机动时间或宽裕时间，是指在不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。1、作业时差作业的总时差Ri,j作业的自由时差Fi,j在不影响工程最早结束时间的条件下，工序最早开始时间可以推迟的时间，称为该工序的总时差。(即工序的完工期可以推迟的时间)即：

工序总时差=最迟完成时间－作业时间－最早开始时间工序总时差越大，表明该工序在整个网络中的机动时间越大，可以在一定范围内将该工序的人力、物力资源利用到关键工序上去，以达到缩短工程结束时间的目的。在不影响紧后作业最早开始时间的条件下,作业最早开工时间可以推迟的时间，称为该工序的单时差。Ri,j=

LFi,j－Ti,j－ESi,jFi,j＝min｛

ESj,k｝－Ti,j－ESi,i(1)作业的总时差Ri,j计算公式为：Ri,j=LFi,j－Ti,j－ESi,j作业E（3～13）的总时差为：R3,13=15－5－2＝8R13,17=17－2－10＝5R7,9=7－4－3＝0总时差为0的作业为关键作业作业E（13～17）的总时差为：作业E（7～9）的总时差为：00CF4300AB23

1I6GH2J57E5D1

3

5

7

9

11131517192100223337101010101723完工时间28282317171515101010733330(2)作业的自由时差Fi,j计算公式为：Fi,j=

ESj,k

－Ti,j－ESi,j作业E（3～13）的自由时差为：F3,13=ES13,17－T3,j3－ES3,13＝10－5－2＝3注：自由时差并不是每个作业有，自由时差的形成是由于作业的始点和终点中，四个时间ESi、LFi

、Esj、LFj

是由不同线路上的作业决定的。00CF4300AB23

1I6GH2J57E5D1

3

5

7

9

11131517192100223337101010101723完工时间28282317171515101010733330作业E（5～15）的自由时差为：F5,15＝10－1－3＝6F7,9＝7－4－3＝03、线段时差两个关键事件之间的一个作业、或两个关键事件之间的几个作业连续相接的连线，称为线段。R总=max(Ri,j、Rj,k、…、Rl,q)R1,17=max(R1,3、R3,13、R13,17)=max(1、8、5)=8R1,15=max(R1,5、R5,15)=max(0、6)=600CF4300AB23

1I6GH2J57E5D1

3

5

7

9

11131517192100223337101010101723完工时间282823171715151010107333304、线路时差线路是指从始点出发，经过连续相接的作业，直到终点的一条连线。线路1-3-13-17-19-21的线路时差为8线路时差为0的线路，称为关键线路。是从始点出发，由各个关键作业连续相接，直到终点的线路。注：关键线路的时差等于0，非关键线路时差通常不计算。线路1-5-7-9-11-15-17-19-21时差为0，即为关键线路。00CF4300AB23

1I6GH2J57E5D1

3

5

7

9

11131517192100223337101010101723282317171515101010733330小结：各时间的计算及标注方法tLF(i,j)t(i,j)tES(i,j)ijR(i,j)【例1】下表是某一工程的作业明细表某一工程的作业时细表［解］（1）画出PERT网络图1324567

2A4.7D7.2E4B4C2F6.2G4H4.3I

000267.29.29.213.217.517.517.517.513.59.513.29.29.27.20（2）计算作业时间和时差7.57.57.54.52.10000Ri,j=LFi,j－Ti,j－ESi,jFi,j=ESj,k

－Ti,j－ESi,i(0)(0)(7.5)(4.5)(2.1)(0)(0)(0)(0)关键路线ESLF13245672A4.7D7.2E4B4C2F6.2G4H4.3I练习序号工作名称工作代号工作持续时间紧后工作1产品设计与工艺设计A60B、C、D、E2外购配件B45L3锻件准备C10F4工装制造1D20G、H5铸件E40H6机械加工1F18L7工装制造2G30K8机械加工2H15L9机械加工3K25L10装配与调试L35

1）画出PERT网络图2）计算作业时间和时差画出PERT网络图12467835a60b45c10d20e40f18g30h15k25l350

12467835a60b45c10d20e40f18g30h15k25l3500606060607080110801001351701701351351351351171201201108060ESLFRi,j=LFi,j－Ti,j－ESi,j030474700020200Fi,j=ESj,k

－Ti,j－ESi,i(0)(30)(0)(47)(0)(0)(0)(0)(20)(0)二、表格计算形式三、EXCEL计算形式-同图论中最短线路问题 第三节网络计划的优化绘制网络图、计算网络时间和确定关键路线,得到一个初始的计划方案。但通常还要对初始计划方案进行调整和完善。根据计划的要求，综合地考虑进度、资源利用和降低费用等目标，即进行网络优化，确定最优的计划方案。网络计划的优化包括时间优化－缩短工程时间改进工艺和技术装备，压缩关键工序的作业时间；合理组织平行作业、交叉作业，平行作业指两道以上相互独立的工序同时进行，交叉作业指将紧前工序完成的部分任务分期分批地转入下道工序。利用时差，合理调配资源等途径实现。时间—资源优化优先保证关键路线上关键工序对资源的需求量。向非关键工序要资源，利用时差调整非关键工序的开工时间，以达到与其它工序在占用资源的时间上错开，拉平资源需要量的高峰。时间—成本优化在时间进度优化中，重点在于如何缩短工期，工期的缩短与费用是密切相关的。网络计划的优化中，应考虑不同的完工时间所对应的工程费用，找到工程费用最低的完工时间(最低成本日程)。【例2】如例1中列出的各项作业必须在15小时内结束1324567244.77.2246.244.3000267.29.29.213.217.517.517.517.513.59.513.29.29.27.207.57.57.54.52.100001.9Min{2.5，3，2.1}=2.111.115.415.415.415.411.12.1*3=6.3元Min{0.4，1，4.5}=0.41.68.88.810.7

1515.015.015.010.78.88.80.4*4=1.6元共计7.9元表格计算形式作业(i,j)作业(i,j)作业时间最短时间最大可调整的时间单位时间增加花费用作业开始时间作业缩短时间作业完成时间(1,2)A22000.00.02(2,5)B44002.00.06(5,7)C44006.00.010(1,4)D4.73.51.220.00.05(1,3)E7.24.2350.00.07(3,4)F21147.20.49(4,7)G6.242.22.58.80.015(4,6)H41338.82.111(6,7)J4.32.81.5610.70.015练习：12467835a60b45c10d20e40f18g30h15k25l3500606060607080110801001351701701351351351351171201201108060030474700020200各项作业必须在140小时内结束

(4-6)=Min{30，10，20}=103*10=30元2.5*10=25元12467835a60b45c10d20e40f18g30h15k25l35006060606070801108010013517017013513513513511712012011080600304747000202002015100115150150115115115115100100Min{10，10，10}=10(6-7)=Min{30，10，20}=10107090901051401401051051051057090905*10=50元4*10=40元共计145元301027270001009070时间—资源优化

013256478ABCDHEFGIJK6人3天7人4天5人3天6人5天8人6天4人7天7人4天9