运筹学网络计划（专业应用）

1、第六章 网络计划引例：沏茶1324烧水（10）备茶（3）沏茶（2）洗碗（2） 以网络图的形式制定计划，求得计划的最优方案。并据以组织和计划生产，达到预定目标的一种科学的管理方法。1沐风书苑r设：有一项工程，分为若干道工序；已知各工序 间的先后关系，以及各工序所需时间t。 问：（1）工程完工期T=？ （2）工程的关键工序有哪些？问题的一般提法关键工序：主矛盾工序，不能延期完工 路 线： 从始点到终点的一条路关键路线：由关键工序组成的路线，是所有路线中时间 最长的路线。关键工序的延误将导致整个项目完 成时间延误相关概念：1324烧水（10）备茶（3）沏茶（2）洗碗（2）2沐风书苑r 两种方法的原理

2、基本一致，都是用网络表示工程项目，以确定关键路线；这两种方法的主要区别是：CPM方法对工程中各工序完工时间的估计是确定的，而PERT方法对时间估计是概率型的； PERT方法主要注重计划中的时间问题，CPM方法在把费用概念引人计划控制过程中，不仅注重时间问题，而且还考虑工程的费用和成本问题，考虑工程时间的均衡问题求解方法： 关键路径法(Critical Path Methd，简称CPM方法) 计划评审技术(Program Evaluation and Review Technique ，简称PERT法）3沐风书苑r2.解法关键路径法（CPM）分为三步：绘制工程网络图标号法求工期T标号法求关键路线

3、4沐风书苑r准备工作:将整个工程分解为若干工序确定各工序的前后顺序（紧前、紧后）确定工序完成时间三点估计法：最乐观时间a、最可能时间m、最悲观时间b 一点估计法p1355沐风书苑r2）图的结构（1）绘制工程网络图弧(箭线)： 表示工序；为工序的起点、终点结点：表示相邻工序的时间分界点，称事项相邻弧：表示工序前后衔接关系，称紧 前(后)工序；权：工序的完成时间1）顺序：按工序先后从左至右；1324烧水（10）备茶（3）沏茶（2）洗碗（2）只有当事项的所有紧前工序完成后，事项的紧后工序才能开始。连接箭尾的结点称为该工序的紧前事项连接箭头的结点称为该工序的紧后事项。6沐风书苑r缺口：多个始点或多个终

4、点的现象。 （应当只有一个始点和终点）回路：方向一致的闭合链。3）绘图要求：图中不得有缺口、回路和多重边。多重边的处理：（1）绘制工程网络图（续）一项工作只能用唯一的实箭线和唯一的双号表示。处理方法：增加虚工序。12ab12a2bb 虚工序7沐风书苑r3）绘图要求：（1）绘制工程网络图（续）要尽量避免弧的交叉：12345678910111213141234567891011121314编号由左到右，不能重复(每条弧上起点的编号数小于终点的编号数)P135方法：箭杆删除法 给起点一个编号数1，设想将该点为起点的弧都去掉，从而又有新的起点，依次给新的起点编号，反复这样做直到终点已经编号为止。8沐风

5、书苑r例1： 某工厂进行技术改造，需要拆掉旧厂房、建造新厂房和安排设备。这项改建工程可以分解为7道工序，其相关资料如下表： 工序代号工序名称紧前工序工序时间（周）A拆迁/2B工程设计/3C土建工程设计B2.5D采购设备B6E厂房土建C、A20F设备安装D、E4G设备调试F29沐风书苑r工序代号工序名称紧前工序工序时间（周）A拆迁/2B工程设计/3C土建工程设计B2.5D采购设备B6E厂房土建C、A20F设备安装D、E4G设备调试F2A（2）B (3)C (2.5)D (6)E (20)F (4)G (2)解：12345610沐风书苑r工序ABCDEFGHIJKLMN紧前工序_DEAFGBHBH

6、IJGCIKL所需天数103127354436347CBAD2E3F4G5H6IJIKLIMN17891011用箭秆删除法标号（保证箭尾号大于箭头号)11沐风书苑r例2：绘制工程网络图工序代号紧前工序工序时间（周）A/2B/3C/2DA3EA4工序代号紧前工序工序时间（周）FB7GB6HD 、 E4IB 、 C10JG、I3续左表解：1A (2)D (3)C (2)2E (4)3F(7)B (0)G(6)46E (0)5I (10)7J (3)H (4)8B (3)12沐风书苑r两种情况需要引入虚工序：两个工序A、B有相同的始点和终点（两个或两个以上的工序有相同的紧前工序，又同时作为另外一工序

7、的紧前工序）四个工序A、B、X、Y有如下关系： A是X的紧前工序，A和B同时又是Y的紧前工序P134 图6.2P134 图6.1123456ABXYA 虚工序13沐风书苑r工序ABCDEFGH紧前工序-AA、BBD、ED、CG、F工序时间(天)24936242练习：123467895A (2)B (4)C (9)D (3)E (6)G (4)F (2)H (2)14沐风书苑r（2）用标号法求工期T1）标出各事项的最早开始时间 ， -给始点 标 ；10jEjj-给任意点 标 , Ej=Max以 为箭头的各箭之 “箭尾 +箭长tij”0263136162) 终点 的 中的T即完工期。nT1A (2

8、)D (3)C (2)2E (4)3F(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)315沐风书苑r0028336123313136121616（3）求关键路（用标号法）1）标出各事项的最晚开始时间 ，iLii - 给任意点 标 , Li=Min以 为箭尾的各箭之 “箭头 - 箭长tij”nT - 给终点 标 ； 1A (2)D (3)C (2)2E (4)3F(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)16沐风书苑r2）计算各工序 的总时差 R(i,j)= 的 -tij - 的 。ijji3）关键路径：由R(i,j)=

9、 0的关键工序组成的由 至 的路。n1（3）求关键路（用标号法）（不影响总工期条件下，任务可以延迟的最大幅度）00283361233131361216161A (2)D (3)C (2)2E (4)3F(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)一个工序的总时差为0意味着该工序在不影响工期前提下机动时间为0，及工序的最早开始时间也是最迟开始时间，其开始和结束时间没有一点机动的余地注：关键工序头尾皆有=（反之未必成立）17沐风书苑r工序ABCDEFGH紧前工序-AA、BBD、ED、CG、F工序时间(天)24936242练习：123467895A (2)B (

10、4)C (9)D (3)E (6)G (4)F (2)H (2)00472248111110137111515171718沐风书苑r1 计算最早开始时间(ES)与最早完工(EF)时间 从网络起点开始, 用下列公式计算最早开始时间(tES)和最早完工时间(tEF):最早开始时间 = (紧前活动的)最早结束时间的最大值 =开始结点的最早时间tES (i, j) = maxk tEF (k, i)=ETi最早完工时间 = 最早开始时间 + 活动持续时间 tEF(i, j) = tES (i, j) + t (i, j)工序时间参数的计算：19沐风书苑r2 计算最晚开始时间与最晚结束时间 从最后活动开

11、始依次按下式计算每个活动最晚结束时间 tLF 和最晚开始时间tLS 最晚结束时间= (紧后活动的) 最晚开始时间的最小值 =完成结点的最晚时间 tLF (i, j) = mink tLS (j, k)=LTj 最晚开始时间 = 最晚结束时间活动持续时间tLS (i, j) = tLF (i, j) - t (i, j)工序时间参数的计算(续):20沐风书苑r3 总时差 总时差: 不影响总工期条件下，任务可以延迟的最大幅度，用R (i, j)表示: 总时差 = 最晚开始时间 最早开始时间 = 最晚结束时间 最早结束时间 R (i, j) = tLS (i, j) - tES (i, j) = t

12、LF (i, j) - tEF (i, j)p144工序时间参数的计算(续):21沐风书苑r作业:工序代号工序紧前工序工序时间A系统提出和研究问题无4B研究选点问题A7C准备调研方案A10D收集资料工作安排B8E挑选、实地训练工作人员B、C12F准备收集资料用表格C7G实地调查D、E、F5H分析准备调查报告G4I任务结束H022沐风书苑r工序代号工序紧前工序工序时间A系统提出和研究问题无4B研究选点问题A7C准备调研方案A10D收集资料工作安排B8E挑选、实地训练工作人员B、C12F准备收集资料用表格C7G实地调查D、E、F5H分析准备调查报告G4I任务结束H0关键路线逻辑关系图网络结构图 A

13、4(0,1)(4,1)(11,2)(14,2)(14,4)(26,5)(31,6)(35,7)B 7C10E12D 8F 7G5H412467853041126141431353531261414140423沐风书苑r课堂练习 P150习题6.1160234756891011121314abcdefghijklmnopq142030211071225510601015257f b 工序紧前工序工序时间工序紧前工序工序时间工序紧前工序工序时间a /60gb,c7mj,k5ba14he,f12ni,l15ca20if60on2da30jd,g10pm7ea21kh25qo,p5fa10lj,k10

14、绘制网络图，关键路线，工期，总时差24沐风书苑r160234756891011121314abcdefghijklmnopq142030211071225510601015257b f 152课堂练习 P150习题6.125沐风书苑r练习 为筹建某餐馆，需制定计划。将工程分为14道工序，各工序需时及先后关系如下表。试求该工程完工期T及关键路径。26沐风书苑r工序内容紧前工序所需天数A购买炉灶及材料10B购买室内设备3C招集工人1D选择开业地点2E申请许可得到执照D7F修理门窗、粉刷墙壁E3G砌炉灶、水池A、F5H接通上下水道G4I安装室内设备B、H4J做好室内装饰B、H3K购进米面及副食品I、

15、J6L张贴开业广告G3M人员训练C、I4N开业前操作试验K、L727沐风书苑r工序ABCDEFGHIJKLMN紧前工序_DEAFGBHBHIJGCIKL所需天数1031273544363471CBAD2E3F4G5H6IJ7I8KL9IM10N1128沐风书苑r（2）求完工期（用标号法）1）标出各事项的最早开始时间 ， -给始点 标 ； -给任意点 标 ,Ej=Max以 为箭头的各箭之 “箭尾 +箭长tij”10jEjj2) 终点 的 中的T即完工期。nT1C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I(0)8K(6)L(3)9I(0)M(4)

16、10N(7)11029121721252531253829沐风书苑r（3）求关键路（用标号法）2）计算各工序 的时差R(i,j)= 的 -tij - 的 。ijji1）标出各事项的最晚开始时间 ， -给终点 标 ； -给任意点 标 ,Li=Min以 为箭尾的各箭之 “箭头 -箭长tij”niLiiT3）关键路径：由R(i,j)= 0的关键工序组成的由 至 的路。n191C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I(0)8K(6)L(3)I(0)M(4)10N(7)1102912172125253125383825342521311712920

17、30沐风书苑r1C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I(0)8K(6)L(3)9I(0)M(4)10N(7)1102912172125253125383825342521311712920完工期T=38（天）；关键路：D-E-F-G-H-I-K-N。由本例可见：关键工序 头尾皆有 = ，但反之未必。 关键工序时间之和=工期T。 31沐风书苑r二、工程完工期的概率分析 （计划评审技术PERT）1、PERT与 CPM的区别：工程工期的概率分析是是时间不确定情况下PERT的主要工作CPM工序时间是确定的32沐风书苑r 期望工期 TE =关键工

18、序的平均工序时间之和； 工期方差 =关键工序时间方差之和。由概率论的中心极限定理总工期确定平均工序时间的三点估计法：标准化33沐风书苑r方法：首先计算1、 给定时间T*，求工期TT*内完工的概率然后查表求。34沐风书苑r例15、已知某工程网络图，以及各工序的时间参数。求工程在43天内完工的概率。工序ambA101315B5810C7810D7911E246F81014G101215H911130.44/1.00/0.25/0.691112.1710.33498.177.8312.83tijABCDEFGH2135764TE=42.33关键路线I为:ACFH；解：912.837.838.1741

19、0.3312.171135沐风书苑r例2 某工程可分为11项工作，有关资料如下表：工作紧前工作工序时间ambABCDEFGHIJK-ABBCCG、HD、EF、I、J1111232111422210.55632424333171415109794（1）画出施工网络图，确定关键路线及完工期TE；（2）估计工程在20周内完工的概率。36沐风书苑r工作紧前工作工序时间ambABCDEFGHIJK-ABBCCG、HD、EF、I、J1111232111422210.556324243331714151097942221067434340.330.330.332.672.002.001.331.331.00

20、1.3300.110.110.117.134.004.001.771.771.001.7701B(2)A(2)C(2)2D(10)E(6)35F(7)4G(4)67H(3)8I(4)J(3)9K(4)19022212561519151211117620期望工期TE=19；关键路：A-D-J-K。37沐风书苑r0.31 0.32 0.33 0.34 0.350.6217 0.6255 0.6293 0.6331 0.6338标准正态分布数值表=0.6293工程在20周内完工的概率为0.6293。192038沐风书苑r2、给定概率p，求完工可能性为p的工期方法：首先查表求，使；再由解出例、上例中，

21、求完工可能性达95%的工期。解：由，查表再由解出39沐风书苑r压缩工程工期思路：1.向关键工序要时间 2.在非关键工序挖潜力 赶工期问题中，只有压缩关键工序才能引起总工期缩短。若网络图中同时有几条关键路线，则几条关键路线必须 同时在各自线路上压缩一个关键工序，才能缩短总工期压缩工期步骤： 一.选择压缩工序 二.确定压缩量问题：保证质量。不增加人力，物力尽量缩短工期40沐风书苑r一.选择压缩工序的步骤 1.构建关键路线网络，赋权为压缩费用率（对不可压缩工序赋权为M,表示压缩费用率很大） 2.求此网络最小截 3.选择最小截上工序同时进行压缩二.压缩量确定： 1.压缩量t不超过工序上允许压缩限度 2

22、.压缩量不超过关键路长与次关键路长之差值（一般限制压缩量不超过非关键工序最小总时差）,即压缩量t由下式确定：41沐风书苑r3(4,2)J101234567893(4,2)N10(4,9)FDHL 1(3,0)M3(8,2)P1(4,0)8(7,7)GK5(1,4)5(4,4)I8(3,7)B5(5,4)A1(3,0)4(2,3)E5(1,4)C7(2,6)（1）关键路线与工期（2）工期压缩为18天，应如何选择压缩工序和压缩天数？（3）工期压缩到17天，通过在(1)中所选定的压缩工序上压 缩3天能否达到目的什么？ 例：下图是某工程施工网络，图中单箭线表示普通工序，箭线上的tij(Cij, dij

23、)中，tij为工序时间，Cij为该工序上每压缩一天所需的费用，dij为可压缩天数。 42沐风书苑r关键路线：ACF,ADG,BEG 工期TE=20天 (1).计算关键路、工期、总时差工序HLJNPMKI总时差331313111122553(4,2)J101234567893(4,2)N10(4,9)FDHL 1(3,0)M3(8,2)P1(4,0)8(7,7)GK5(1,4)5(4,4)I8(3,7)B5(5,4)A1(3,0)4(2,3)E5(1,4)C7(2,6)0014417202088578191010121243沐风书苑r101347810(4,9)FD8(7,7)G8(3,7)B5

24、(5,4)A4(2,3)E5(1,4)C7(2,6)（2）构建关键路线网络(赋权值为费用率)，确定最小割，选择压缩工序用最大流标号法得最小割为(C, D, E)，所以选择在工序C, D,E上压缩时间根据非关键工序的总时差和压缩工序的限制，确定压缩量 得压缩量为在C,D,E工序上各压缩两天，使总工期压缩至18天44沐风书苑r553(4,2)J101234567893(4,2)N10(4,9)FDHL 1(3,0)M3(8,2)P1(4,0)8(7,7)GK5(1,4)5(4,4)I8(3,7)B5(5,4)A1(3,0)2(2,1)E3(1,2)C5(2,4)001441518188855817

25、881010(3)工期压缩2天后，关键路线已发生变化，所以不能在中选中的压缩工序压缩三天以达到工期成为17天的目的。重复上述步骤，得新的网络，重新确定关键路线和非关键路线的总时差，如图工序HLJNPM总时差3311119945沐风书苑r1013457810(4,9)FD8(7,7)GK5(1,4)5(4,4)I8(3,7)B5(5,4)A2(2,1)E3(1,2)C5(2,4) 继续构建关键路线网路，确定最小割为C,D,E,K，作为压缩工序。确定压缩量根据非关键工序的总时差和压缩工序的限制，确定压缩量 最小时差 ，得压缩量为在C,D,E,K工序上各压缩1天，使总工期压缩至17天46沐风书苑r4

26、7沐风书苑r工程费用分析问题： 编制工程网络计划时，不仅要考虑工期时间，还应到考虑工程造价 对一个工程来说，无论是以考虑工程费用为主，还是以控制时间进度为主，都必须对工程计划进行时间费用分析，从而可综合考虑制定最优的计划。48沐风书苑r费用概念直接费用：指人工、材料、燃料等直接用来完成工程 任务的费用。工序直接费用率：指一道工序缩短单位时间所需增 加的费用间接费用：指管理人员的工资、办公、采购等并非直 接用于完成工程任务的费用。间接费用率p:整个项目的工期每提前单位时间可节 约的费用49沐风书苑r工程的时间费用关系图费用工期时间总费用直接费用曲线(工程的时间费用曲线)间接费用曲线最低成本工期TE总费用曲线由同一工期下的直接费用和间接费用相加得到压缩工期会增加直接费用，但减少了间接费用延长工期会增加间接费用，但可能减少直接费用 因此只有当压缩关键工序时间增加的直接费用小于由此导致工期缩短而节约的间接费用时，这一压缩才进行。50沐风书苑r最低成本工期的确定：确定最低成本工期的步骤：一、绘制网络图，计算工序总时差R (i, j)，确定TE与关键路线，计算相应工程费用。二、在各关键路线上所有可压缩的工序中，各确定一个本线路上费用率最低的工序作为压缩工序，这些压缩工序之集合用I表示.一般可由1）.构建关键路线网络，赋权为压缩费用率（对不可压缩工序赋权为M,表示压缩费用率很大）2）.求此网