《运筹学》课程电子教案（PPT课件讲稿）第九章 网络计划

第九章网络计划 9.1基本概念 是用网络分析的方法编制的计划 癱杜邦公司—关键路线法CPM确定型 美国海军武器局一计划评审技术PERT 网络图(有向赋权图)的构成 结点,也称事项,一道工序的开始或结束 癱工序(弧),相对独立的活动,消耗资源 癱虚工序,只表示衔接关系,不消耗资源 工序时间(权),完成工序的时间消耗 OR3

OR3 1 第九章 网络计划 9.1基本概念 ～是用网络分析的方法编制的计划 杜邦公司—关键路线法CPM 确定型 美国海军武器局—计划评审技术PERT 网络图（有向赋权图）的构成 结点，也称事项，一道工序的开始或结束 工序（弧），相对独立的活动，消耗资源 虚工序，只表示衔接关系，不消耗资源 工序时间（权），完成工序的时间消耗

92.网络规贝 癱1、避免循环、不留缺口 2、 对应:一道工序用两个事项表示 3、从左向右依次展开 例 序 ABCDEF G H 紧前工序 AB|BC、D 工序时间466759748 C.6 G.7 A,4 1.8 D,7 9 B6 E5 H, 4 OR3

OR3 2 9.2.网络规则  1、避免循环、不留缺口  2、一一对应：一道工序用两个事项表示  3 、从左向右依次展开 例： 工 序 A B C D E F G H I 紧前工序 -- -- A B B C、D C、D E、F G 工序时间 4 6 6 7 5 9 7 4 8        A,4 B,6 C,6 D,7 E,5 G,7 F,9 H,4 I,8

9.3关键路线法一-CPM 9.3.1时间参数运算什么是关键路线? 1、作业时间t(i,j),经验数据、统计数据 事项最早时间TE()=max{TE()+t(i,j)} 到齐上课,最后到者决定最早开课时间 3、事项最迟时间T(-min{T()-t(,j)} 保证12点吃饭,路最远者决定最迟下课时间 4、工序最早可能开工时间 (i j- TEO = maxTEs(h, i +t(h,i)y 5、工序最早可能完工时间 TEF(j=TES()+t (i, OR3

OR3 3 9.3 关键路线法－－ CPM 9.3.1时间参数运算 什么是关键路线？ 1、作业时间t（i，j），经验数据、统计数据 2、事项最早时间TE(j)＝max{TE(i)+ t（i，j）} 到齐上课，最后到者决定最早开课时间 3、事项最迟时间TL (i)＝min{TL (j)- t（i，j）} 保证12点吃饭，路最远者决定最迟下课时间 4、工序最早可能开工时间 TES(i,j)＝ TE(i) = max{TES(h,i)+ t（h,i ）} 5、工序最早可能完工时间 TEF(i,j)＝TES(i,j)+ t（i，j） h i j

警6、工序最迟必须开工时间 TLS (i,j=tOt (ij=mints(, k -t(i,j y 7、工序最迟必须完工时间 TLF (ij=tLO- TLS (ij+t(i,j) 8、工序总时差:在不影响其紧后工序最迟必 开工时间的前提下,本工序可以推迟的时间 R(ij=TiS(ij-Tes(ij- TLe(- TEF(ij mintis( k) ]-TEF (i, 9、工序单时差:在不影响其紧后工序最早可能 开工时间的前提下,本工序可以推迟的时间 r (ij)= TEs(, k)]-TEF (ij) OR3

OR3 4 . 6、工序最迟必须开工时间 TLS（i,j)＝ TL (j)－ t（i,j)＝ min{TLs(j,k)- t（i，j）} 7、工序最迟必须完工时间 TLF（i,j)＝ TL (j)＝ TLS（i,j)+ t（i,j) 8、工序总时差：在不影响其紧后工序最迟必须 开工时间的前提下，本工序可以推迟的时间 R（i,j）＝ TLS(i,j)－ TES(i,j) ＝ TLF(i,j)－ TEF(i,j) ＝ min{TLS(j,k) } – TEF（i,j） 9、工序单时差：在不影响其紧后工序最早可能 开工时间的前提下，本工序可以推迟的时间 r （i,j）＝ min{TES(j,k) } – TEF（i,j） K k k

9.3.2时间参数图解 t(j·k) ts R (ij) 解上例 计算事项 Q2C6/3 ③G7 200 A4 时间参数000 DZ Fg B6 ⑤一H4 2828 E5 2224 关键路线:由总时差为零的工序构成 B—D—G— OR3

OR3 5 9.3.2时间参数图解 . 解上例： 计算事项    时间参数     TES TLS TEF TLF TES TLS TEF TLS r(i,j) R（i,j） A4 B6 C6 G7 D7 E5 F9 H4 I 8 0 0 4 7 6 13 22 20 28 28 20 24 13 6 关键路线：由总时差为零的工序构成 B D G I t（i,j) t（j,k)

解上例计算工序时间参数 工序 t(i,j)ESEF LS LF R ①② 437 A—B—C—DE ① 466759 00466 606 30 107133 0030 ③④ 136130 1119241311 0 132215242 GH ④⑥7132013200 ⑤⑦4222624282 0020 820284201280 OR3

OR3 6 .  解上例 计算工序时间参数 工序 i j t(i,j) ES EF LS LF R r A   4 0 4 3 7 3 0 B   6 0 6 0 6 0 0 C   6 4 10 7 13 3 3 D   7 6 13 6 13 0 0 E   5 6 11 19 24 13 11 F   9 13 22 15 24 2 0 G   7 13 20 13 20 0 0 H   4 22 26 24 28 2 2 I   8 20 28 20 28 0 0

94计划评审技术一PERT 蜂PERT的产生 关键路线法中,工序时间是确定值,而对研究 性的工序来说,t(i,j)是随机的。1958年美 国海军武器局研制北极星导弹时提出,重点在 于计划的评审。 PERT的时间估计采用三种时间估计法a最 乐观时间,b一最悲观时间,m一最可能时间, 工序期望时间 a+4m+b 方差62 b-a2 OR3

OR3 7 9.4计划评审技术－－PERT  PERT的产生 关键路线法中，工序时间是确定值，而对研究 性的工序来说， t（i，j）是随机的。1958年美 国海军武器局研制北极星导弹时提出，重点在 于计划的评审。  PERT的时间估计 采用三种时间估计法a－最 乐观时间，b－最悲观时间，m－最可能时间， 则 工序期望时间 te ＝ 方差 δe 2＝（ ）2 a+4m+b 6 b－a 6

PERT的计算方法 网络图的绘制与关键路线法相同 参数计算与关键路线法体系不同 工程期望工期TE=Σtk 期望工期方差62=∑6e2 计划工期Tk-—业主要求的工期 预期完工概率:入=查正态分布表 定概率的完工期Tk=TE+λ OR3

OR3 8 PERT的计算方法 网络图的绘制与关键路线法相同 参数计算与关键路线法体系不同 工程期望工期 TE ＝∑ tek 期望工期方差 δ 2＝∑ δek 2 计划工期 TK－－业主要求的工期 预期完工概率：＝ 查正态分布表 一定概率的完工期 TK ＝TE + δ  TK－ TE δ

PERT应用举例 P346例6关键工序:CD—F/G-4 期望工期 10.50+10.17+20.33+5.17+1283=59 612=136+0.25+400+0.25+14.69=20.55 62=136+025+1.00+025+14.69=1755 癖完工概率:λ1=(60-59)÷V2055=0.22 查表得P(1)=587 (60-59)÷√1755=0.244 查表得P(^2 59.5 若要有90%的把握,计划工期应定多长 K T TK=T+8x=59+453×1.29=6484 OR3

OR3 9 PERT应用举例  P346例6 关键工序：C D F/G I J  期望工期： TE＝10.50+10.17+20.33+5.17+12.83＝59 δ1 2＝1.36+0.25+4.00+0.25+14.69＝20.55 δ2 2＝ 1.36+0.25+1.00+0.25+14.69＝17.55  完工概率：1＝（60-59）20.55＝0.22 查表得 P（ 1）＝58.7％ 2＝（60-59）17.55＝0.244 查表得 P（ 2）＝59.5  若要有90％的把握，计划工期应定多长 TK＝ TE + δ ＝59+4.531.29＝64.84

9.5网络优化 癱CPM与PERT主要目标是控制工期 癱网络优化在上述基础上,寻求时间更短、资源 更省、成本更低的方案 9.5.1时间一资源优化(资源的均衡配置) 原则:关键优先、利用时差P331例题4 方法:绘制资源负荷图,排定关键工序,游移非 关键工序 H15天 39人 F18天22人 58 20人 d20天 g30天 k25天 60 80 135 OR3 10

OR3 10 9.5 网络优化 CPM与PERT主要目标是控制工期 网络优化在上述基础上，寻求时间更短、资源 更省、成本更低的方案 9.5.1时间－资源优化 （资源的均衡配置） 原则：关键优先、利用时差 P331例题4 方法：绘制资源负荷图，排定关键工序，游移非 关键工序 60 80 110 135 d20天 g30天 k25天 58人 H15天 39人 42人 26人 F18天 22人