《运筹学11-清华大学课件》、在线看

第十一章网络计划章节大纲工程计划网络图的绘制网络时间的计算关键路线与网络优化一、工程计划网络问题（关键路径法）问题的一般提法设：有一项工程，分为若干道工序；已知各工序间的先后关系，以及各工序所需时间t。问：（1）工程完工期T=？（2）工程的关键工序有哪些？解法——关键路径法（CPM）绘制工程网络图求完工期（用标号法）求关键路（用标号法）1.1

网络计划图·

网络计划图的基本思想是：首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路；通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。·网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法（CPM）和计划评审技术（PERT）的网络计划图没有本质的区别，它们

的结构和术语是一样的。仅前者的时间参数是确定型的，而后者的时间参数是不确定型的。1.1

网络计划图工

序·

在网络计划图中，用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用（i-j）两个代号及箭线表示一项工作。在箭线上标记必须的信息，如下图：箭尾事项箭头事项工序之间的关系紧前工序：紧排在本工作之前的工作；且开始或完成后，才能开始本工作。紧后工序：紧排在本工作之后的工作；本工作开始或结束后，才能开始或结束的工作。虚工序：不占用时间和不消耗人力，资金等的虚设的工作。虚工序只表示相邻工序之间的逻辑关系。网络图的要求相邻节点只能是一个工序的相关事项；网络图中不能有缺口和回路应改正为TS123AB4C123456ABCDE绘制工程网络图顺序：按工序先后从左至右；图中弧（箭线）：表示工序；顶点（结点）：表示相邻工序的时间分界点，称事项，用

i表示。相邻弧：表示工序前后衔接关系，称紧前（后）工序；要求：图中不得有缺口、回路和多重边。缺口：多个始点或多个终点的现象。（应当只有一个始点和终点）处理方法：增加虚工序。多重边：两点间有多于一条的边。AB处理方法：增加虚工序。AA’B例1

为筹建某餐馆，需制定计划。将工程分为14道工序，各工序需时及先后关系如下表。试求该工程完工期T及关键路径。回路：方向一致的闭合链。工序内容紧前工序所需天数A购买炉灶及材料——10B购买室内设备——3C招集工人——1D选择开业地点——2E申请许可得到执照D7F修理门窗、粉刷墙壁E3G砌炉灶、水池A、F5H接通上下水道G4I安装室内设备B、H4J做好室内装饰B、H3K购进米面及副食品I、J6L张贴开业广告G3M人员训练C、I4N开业前操作试验K、L7工序ABCDEFGHIJKLMN紧前工序____DEAFGBHBHIJGCIKL所需天数1031273544363471CBAD2E3F4G5H6IJ7I’8KL9I’’M10N11网络计划图的时间参数计算网络图中工作的时间参数。它们是：工作持续时间(D)；工作最早开始时间（ES）；工作最早完成时间（EF）；工作最迟开始时间（LS）；工作最迟完成时间（LF）；工作总时差（TF）；工作自由时差（FF）。·工作持续时间(D)——作业时间Ti-j⑴单时估计法（定额法）每项工作只估计或规定一个确定的持续时间值的方法。一般具有工作的工作量，劳动定额资料以及投入人力的多少等，计算各工作的持续时间；工作持续时间Q—工作的工作量。以时间单位表示,如小时;或以体积，重量，长度等单位表示；R—可投入人力和设备的数量；S—每人或每台设备每工作班能完成的工作量；n—每天正常工作班数。或具有类似工作的持续时间的历史统计资料时，可以根据这些资料，采用分析对比的方法确定所需工作的持续时间。⑵三时估计法在不具备有关工作的持续时间的历史资料时，在较难估计出工作持续时间时，可对工作进行估计三个时间值，然后计算其平均值。这三个时间值是：乐观时间。在一切都顺利时，完成工作需要的最少时间，记作a。最可能时间。在正常条件下，完成工作所需要时间。记作m。悲观时间。在不顺利条件下，完成工作需要最多时间，记作b。·

显然上述三种时间发生都具有一定的概率，根据经验，这些时间的概率分布认为是正态分布。一般情况下，通过专家估计法，给出三时估计的数据。可以认为：工作进行时出现最顺利和最不顺利的情况比较少。较多是出现正常的情况。按平均意义可用以下公式计算工作持续时间值：工作最早开始时间ES和工作最早完成时间EF工作的最早开始时间ES是紧前工序最早结束时间。ES=TE（i）EF=ES+tij工作最迟开始时间LS与工作最迟完成时间LF工作的最迟完成时间LF是工作在不影响工期下最迟结束时间。LF=TL（j）

LS=LF-TL(j)最后一项工作的最迟完成时间LF等于其最早完成时间EF工序(i,j)的时间参数x

y事件最早可能发生时间Tei事件最迟必须发生时间Tl网络时间的图示法1.节点时间（事件时间）TE（j）=Max(TE(i)+tij)ji箭尾事项箭头事项A（D）tijc

d事件最迟必须发生时间TL：反向求差取小TL（i）TL（n）=TE(n)

Max(+)

Min(-)TL（i）=Min(TL(j)-tij)a

b事件最早可能发生时间TE：顺向求和取大TE(i)TE（1）=0ij开始完成可能必须最早最迟ad-tija+tijdji箭尾事项箭头事项A（D）tija

bc

d2.工序时间ESⅠⅡLSEFⅣⅢLFⅠⅡⅢⅣ工序A3.工作时差：指工作有机动时间。⑴工作总时差TF（i-j）——在不影响工期的前提下，工作所具有的机动时间i箭尾事项事项A（D）tija

jd-tija+tij箭d头a

bc

dLS-ES=LF-EFⅠ

ⅡⅢⅣ工序A总时差为零的工序即关键工序ji箭尾事项头项ad-t箭事ija+tijdA（D）tija

bc

d（2）工作自由时差FF（i-j）——在不影响其紧后工作最早开始的前提下，工序最早可能完工时间所具有机动时间ⅠⅡⅢⅣ工序Aji箭尾事项头项A（D）tija

bc

dad-ti箭ja+tijd

事（3）工作安全时差SF（i-j）——在不影响其紧后工作的最迟开始的前提下，工作所具有机动时间ⅠⅡⅢⅣ工序A（2）求完工期（用标号法）1）标出各事项的最早开始时间，为箭头的各箭之-给始点

1

标

0

；-给任意点

j

标

Ej

,Ej=Max{以j“箭尾 +箭长tij”}2)

终点

n

的

T 中的T即完工期。C(1)B(3)A(10)D(2)F(3)3

45I(4)J(3)78K(6)L(3)9M(4)10N(7)0122E(7)9G(5)1217I’’(02)16H(4)25I’(0)2531253811顺向求和取其大（3）求关键路（用标号法）1）标出各事项的最晚开始时间i2）计算各工序

j

的时差R(i,j)j=

的 -tiji

-

的

。的路。为箭尾的各箭之“箭头 -箭长tij”}-给终点

n

标

； -给任意点T至n3）关键路径：由R(i,j)=0的关键工序组成的由19C(1)B(3)A(10)D(2)F(3)3

45H(4)I(4)J(3)7I’(K(6)L(3)M(4)1022E(7)9G(5)1217I’’(0)216250)253125381138253425

82131171292001Min(25,34)N(7)反向求差取其小，i

标

Li

,Li=Min{以

i工序箭尾节点i所需天数箭头节点jESEFLSLF总时差d-t-a单时差c-t-a自由时差

d-t-babcdA00101212010212222B0032121031921191818C0012534013334332433D002220202000E227992929000F9931212912912000G12125171712171217000H17174212117211721000I21214252521252125000J21213252521242225111K25256313125312531000L17173313117202831111111M25344383825293438990N31317383831383138000ESLSEFLF1791181062345A(

10

)B(

3

)C(

1

)D(

2

)E(

7

)F(

3

)G(

5

)H(

4

)I(

4

)J(

3

)L(

3

)K(

6

)M(

4

)N(

7

)ESLSEFLF完工期T=38（天）；关键路：D-E-F-G-H-I-K-N。由本例可见：关键工序 头尾皆有

=，但反之未必。关键工序时间之和=工期T。2534253425252525课堂习题求下面网络计划图中的关键路径和完工期。要求使用标号法，给出节点的TE和TL，工序的ES、EF、LS、LF以及总时差TF和自由时差FF312546789A(3

)B(4

)C(5

)D(6

)F(2

)H(3

)E(1

)G(4

)I(5

)小结虚工序的网络时间也应计算，以判断其是否为关键工序。（虚工作为无机动时间的关键工作；否则该虚工作即为有机动时间的非关键工作。）关键工序有2条：ADEGI和ADFHI·完工期TE为19天。33011001243689B(4

)C(5

)D(6

)H(3

)E(1)00F(2)59

9G(4

)0

03

39

910

10711

1110

1014

1419

19000000I(5

)0000

00011A(3

)iTE

TLTF

FF二、工序时间不确定的工程计划网络问题（计划评审技术PERT）=关键工序的平均工序时间之和；=关键工序时间方差之和。例2

某工程可分为11项工作，有关资料如下表：工作紧前工作a工序时间mbA-123B-123C-123DA110.517EB2514FB3615GC2310HC129IG、H147JD、E129KF、I、J444画出施工网络图，确定关键路线及完工期TE；估计工程在20周内完工的概率。工作紧前工作a工序时间mbA-12320.330.11B-12320.330.11C-12320.330.11DA110.517102.677.13EB251462.004.00FB361572.004.00GC231041.331.77HC12931.331.77IG、H14741.001.00JD、E12931.331.77KF、I、J444400B(2)C(2)2E(6)3467G(4)H(3)J(3)K(4)199012A(2)22125F(7)5615191581211I(4)11762D(10)0E期望工期T

=19；关键路：A-D-J-K。0.310.320.330.340.350.62170.62550.629