《运筹学第六章网络计划.pptx》由会员分享，可在线阅读，更多相关《运筹学第六章网络计划.pptx（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.问题的一般提法：设有一项工程，可分为若干道工序，已知各工序间的先后关系以及各工序所需时间t。问：（1）工程完工期T？（2）工程的关键工序有哪些？（3）若工序时间T具有随机性，则期望完工期TE=?完工期为某天的可能性多大？（4）费用优化和资源平衡。第1页/共66页2.解法关键路径法（CPM方法）计划评审法（PERT方法）l相同点：l不同点：PERT法：注重于对工程安排的评价与审查。CPM方法：注重于时间、成本和资源的优化；均是用网络表示工程项目，以确定关键路线。第2页/共66页6.1 网络计划图的绘制1.绘图顺序：按工序先后从左至右2.网络图的组成要素 用 表示。i j （1）弧（实箭线）表
2、示工序，（2）顶点（结点）：表示相邻工序时间分界点，称为事项，i用 表示（3）相邻弧：表示工序的前后衔接关系，称为紧前 （或紧后）关系。如 i Akj BA是B的紧前工序，B是A的紧后工序。A第3页/共66页（4）虚工序（虚箭线）为表示工序前后衔接关系的需要而增加的。用 表示。ij3.绘图规则：（1）图中不能有缺口，多重边和回路。123456起点终点（缺口：有几个总开工事项或几个总完工事项）处理方法：在5、6之间加道虚工序A第4页/共66页（多重边：两点之间有多于一条边）处理方法：增加虚工序（回路：工序循环进行，永远不能完成不允许）（）（）（）（）（）第5页/共66页（2）网络图中的事项要从左
3、至右统一编号，每道工序 的箭尾事项号应小于箭头事项号。12 正确21错误（3）尽量避免箭杆交叉。1234567处理方法：先画草图，再整理。1234567第6页/共66页4.绘图准备工作（1）确定目标（以谁为主）时间资源费用（2）工程任务的分解和分析；分析工程由哪些工序组成并列出全部工序及代号清单。（3）确定各工序之间先后顺序及衔接关系；要确定每道工序开工之前有哪些工序必须先期完成。（4）确定各工序时间。要确定每道工序的完成所需时间。第7页/共66页例1（P13例）某工厂进行技术改造的工作表如下：工序代号工序代号工序名称工序名称紧前工序紧前工序工作时间工作时间（周）（周）A拆迁拆迁/2B工程设计
4、工程设计/3C土建工程土建工程设计设计B2.5D采购设备采购设备B6E厂房土建厂房土建C，A20F设备安装设备安装D，E4G设备调试设备调试F2第8页/共66页1A(2)3B(3)2C(2.5)4D(6)E(20)5F(4)6G(2)第9页/共66页6.2 时间参数计算与关键路线确定CPM方法一、求完工期T（标号从前往后）1.标出各事项的最早开始时间tE(i)i20表示第i个事项最早在第20天才开始。（1）给始点 标10（2）给任意事项 标jtE(j)第10页/共66页（3）终点 的 即为完工期T（最快的完工期）n=max以 为箭头（终点）的各箭的箭尾 +箭长 tij j8510L(3)K(6
5、)25173131=max25+6,17+3表示第10个事项最早在第31天开始。之所以取最大，因为在第20天，L工序已完成，但k工序未完成。tE(n)第11页/共66页二、求关键路（关键工序）（标号从后往前）1.标出各事项的最迟开始时间tL(i)（1）给终点 标号nT（2）给任一事项 标号itL(i)tL(i)=mintL(j)-t(i,j)i=min以 为箭尾（起点）的各箭的箭头 -箭长tij（3）给始点 标号00第12页/共66页567K(6)L(3)10484=min10-6,8-3表示第5个事项最晚第4天开始。之所以取最小，保证时间最长的工序K能完工。2.计算各工序 的时差ijR(i,
6、j)=的 -tij-的ji表示这道工序的松弛时间。如ijA(3)2125R(i,j)=25-3-21=1表示A工序最晚结束时间在第25天，最早开工时间在第21天，工时为3天，故有1天的松弛量。第13页/共66页3.关键工序工序时差为0的工序（R(i,j)=0）如：ijA(3)222525-3-22=0表示A工序的开工和结束时间不能延后，否则整个工期延后一关键工序。4.关键路由关键工序组成的由起点到终点的路。第14页/共66页例2 求例1的关键工序及关键路。132456A（2）B（3）E（20）D（6）F（4）G（2）C（2.5）05.5325.529.531.505.5325.529.531.
7、5RA=3.5,RB=0,RC=0,RD=16.5,RE=0,RF=0,RG=0第15页/共66页总工期:T=31.5（周）注：1.关键工序 箭头箭尾均有 =反之不成立。2.关键工序时间之和=完工期T关键路：（不一定唯一）123456 关键工序：B-C-E-F-G第16页/共66页所有时间参数(j)最早完成时间=(i)最早开始时间-t(i,j)(i)最迟完成时间=(j)最迟开始时间-t(i,j)工序(i,j)的总时差=(j)最迟开始时间-t(i,j)-(i)最早开始时间工序(i,j)的自由时差=(j）最早开始时间-(i）最早完成时间第17页/共66页例3（P136）某项课题研究工作分解的作业表
8、如下。根据此表绘制此项科研工作的网络图，计算时间参数，并确定关键路线。工序代号工序代号工序工序紧前工序紧前工序工序时间工序时间A系统提出和研究问题系统提出和研究问题无无4B研究选点问题研究选点问题A7C准备调研方案准备调研方案A10D收集资料工作安排收集资料工作安排B8E挑实地训练工作人员挑实地训练工作人员B，C12F准备收集资料用表格准备收集资料用表格C7G实地调查实地调查D，E，F5H分析准备调查报告分析准备调查报告G4I任务结束任务结束H0第18页/共66页E(12)124536789A(4)B(7)C(10)B(0)C(0)D(8)F(7)G(5)H(4)I(0)04141411263
9、135350414263135351414关键工序：A-C-C-E-G-H-I关键路：12456789第19页/共66页6.3 网络图的调整及优化6.3.1 缩短工程工期问题工期优化所谓工期优化，就是在编制网络计划时，如何加快工程进度，缩短工程的工期。一般可以从以下两个方面进行：（1）压缩关键工序的工序时间对关键工序增加新设备，采用新工艺，新技术等措施；或对工序时间较长的关键工序采用平行作业或交叉作业等措施，以达到提高工效、缩短关键工序时间的目的。（2）在非关键工序上尽量挖掘潜力利用非关键工序的时差进行合理调度，抽调人力、物力支援关键工序，缩短关键工序时间。第20页/共66页6.3.2 工程的
10、时间费用分析工期-成本优化（费用优化）所谓工期成本优化，就是在编制网络计划中，如何使工程的完成既快又省。一.费用构成1.直接费用工资、设备、原材料等（直接与完成工序有关的费用）第21页/共66页CDA(压缩时间)B(正常完成时间)时间直接费用称 为直接（赶工）费用率（表示缩短工序一天，工期增加的直接费用）即直接费用率=平均单位时间的赶工费用第22页/共66页2.间接费用管理费等（不直接参加生产的费用）间接费用AB称单位时间的间接费用为间接费用率。总费用=直接费用+间接费用工期直接费用间接费用总费用费用t*（最小工期时间）时间第23页/共66页二.求最低成本工期方法：1.求出正常工期和关键工序（
11、用CPM方法）2.比较关键工序的直接费用率与间接费用率（1）若直接费用率 间接费用率则正常工期为最低成本工期。（2）若存在直接费用率间接费用率则在关键工序上压缩，先压缩直接费用率最小的方案，并确定该方案可能缩短的时间。t=mint=min,=min压缩工序的正常时间-赶工时间=min所有非关键工序的时差第24页/共66页（3）按照工作的新工时，重新计算网络计划的关键 路线及关键工序。（4）再比较关键工序的直接费用率与间接费用率。不断重复，直到使总费用上升为止。（直接费用率间接费用率）注：若压缩引起出现多于一条新的关键路线时，需同时压缩各关键路线.（因为不同时压，则工期不能缩短，工期=关键工序上
12、工时之和）第25页/共66页例4 设某工程有关资料如表：工序工序 紧前工序紧前工序工序时间工序时间直接费用直接费用率率可压天数可压天数A-3-BA731CA443DC562间接费用率为5求最低成本工期。第26页/共66页解：（1）求工期及关键工序。1324A（3）C（4）B（7）D（5）0731212730工期：T=12,关键工序：A-C-D第27页/共66页（2）因为直接费用率不全5，故应在关键工序上压缩先压缩C（直接费用率最小）压一天能节省费用为5-4=1=3（C的可压天数），=R24=2 故t=2t=2压缩方案：C压缩2天，可减少费用（5-4）*2=2此时网络图为：1324A（3）C（2
13、）B（7）D（5）0531010530关键路有两条：A-BA-C-D工期T=10RA=RB=RC=RD=0第28页/共66页若再各压缩1天 则应压缩B、C（同时压）此时的直接费用率将是3+4=75故最低成本工期为10天。注：（1）有时资料未给可压缩时间，但给了正常工作时间及最短工作时间。则压缩时间=正常工作时间-最短工作时间。（2）当网络图中工作很多，关键路线又不止一条，用观察法来确定缩短工时所需直接费用增加最少的方案比较困难，这时可以使用求网络最大流的标号法来解决。第29页/共66页方法：将问题化为：在全部以关键工序组成的网络上，每边容量使用本工作的直接费用率（若本工作已不能缩短工时，容量应
14、标 ）求网络的最大流，当求出最大流时所得到的最小截，就是增加直接费用最少的方案。1243第30页/共66页12431243工作组合（2，4）（2，3）为费用最低方案。B C第31页/共66页三.求规定工期的最小成本方案间接费用是确定了的，无需考虑，只需考虑直接费用尽量小。方法：1.求出正常工期和关键路线2.在关键工序上压，先压缩直接费用率最小的，压缩天数也应为t=min,.当出现多于一条的关键路线时要同时压，直到满足规定为止。第32页/共66页例5 建筑公司要装水管线的工程，有关资料：工作工作紧前工作紧前工作正常情况正常情况应急情况应急情况时间（天）时间（天）费用（元）费用（元）时间（天）时间
15、（天）费用（元）费用（元）a-11.7240-ba3.2752110ca25.24500157200da18.048017600ed9.05408710fb,c7.7166051800ge,f16.84000145700hg7.2160051775ie,f12.850091298第33页/共66页（1）按正常情况，画出施工网络图，找出关键路，求完工期。（2）现提出这项工程要60天完成，求使总应急费用最小的方案。18246735a(11.7)b(3.2)c(25.2)d(18.0)b(0)f(7.7)e(9.0)g(16.8)h(7.2)i(12.8)011.729.714.936.944.66
16、1.468.668.661.444.635.636.936.911.70正常工期TE=68.6天关键工序a-c-f-g-h解：（1）第34页/共66页（2）将每道工序的直接费用率计算如下：工作工作 abcdefghi可压可压工期工期1.210.2112.72.82.23.8直接直接费用费用率率29.17264.7112017044.4607.1479.55367.89第35页/共66页1）先压f,=2.7;而Rb=22,Rd=3.2,Rc=3.2,Ri=11.2,故=3.2。因此,t=2.7011.729.714.936.941.958.765.965.958.741.932.936.936.
17、911.70工期TE=65.9关键工序：a-c-f-g-h18246735a(11.7)b(3.2)c(25.2)d(18.0)b(0)f(5.0)e(9.0)g(16.8)h(7.2)i(12.8)第36页/共66页2）再压h,=2.2;而Rb=22,Rd=3.2,Rc=3.2,Ri=11.2,故=3.2.因此，t=2.218246735a(11.7)b(3.2)c(25.2)d(18.0)b(0)f(5.0)e(9.0)g(16.8)h(5.0)i(12.8)011.729.714.936.941.958.763.763.758.741.932.936.936.911.70工期TE=63.
18、7关键工序：a-c-f-g-h第37页/共66页3）再压c,=3.7;而Rb=22,Rd=3.2,Re=3.2,Ri=9.0故=3.2.因此，t=3.218246735a(11.7)b(3.2)c(22)d(18.0)b(0)f(5.0)e(9.0)g(16.8)h(5.0)i(12.8)011.729.714.933.738.755.560.560.555.538.729.733.733.711.70工期TE=60.560关键工序：a-d-e-g-h a-c-f-g-h第38页/共66页4）可同时压c,e各0.5天,=0.5;而Rb=18.8,Rc=3.0故=3.0.因此，t=0.51824
19、6735a(11.7)b(3.2)c(21.5)d(18.0)b(0)f(5.0)e(8.5)g(16.8)h(5.0)i(12.8)011.729.714.933.238.255.0606055.038.229.733.233.211.70工期TE=60关键工序：1）a-c-f-g-h 2）a-d-e-g-h第39页/共66页所以，工期60天时总应急最小的方案为：工序abcdefghi工时11.73.221.5188.55.016.85.012.8增加的最小应急费用第40页/共66页6.3.3 工程的时间资源优化（工期资源优化）所谓工期资源优化，就是在有限资源的情况下，如何合理地调配人力、材
20、料、设备、能源等资源，使之既符合客观条件限制，又尽量不误工期（将资源适当调整使资源利用得以平衡）。方法：1.计算工程每单位时间内所需资源量。2.作出初始进度横道表 3.进行资源均衡调整求得新进度。4.评价工程进度计划对资源利用的均衡程度（计算单位时间内资源利用量的方差）。第41页/共66页例6 已知某工程有关资料如表：工序工序紧前工序紧前工序工序时间工序时间所需资源数所需资源数（人（人/天）天）A-49B-23C-26D-24EB38FC27GD，F32HE，G41第42页/共66页（1）绘制工程网络图，求出工期与关键路线。（2）调整网络，使资源尽量平衡（不能延误工期）解：（1）162345A
21、（4）B（2）C（2）D（2）E（3）F（2）G（3）H（4）02247111174240工期为11天关键工序：C-F-G-H第43页/共66页（2）a）画出横道表9 9 9 93 36 68 8 8 4 4 7 7 2 2 2 1 1 1 12411工序ABCDEFGH12345678910人数22222410221111第44页/共66页b)调整调整原则：利用非关键工序的时差Rij=的 -tij-的ji先找出那些具有最大总时差的工序在不拖延整个工程完工期的情况下，尽量往后延。RA=11-4-0=7RB=4-2-0=2RE=7-3-2=3RD=4-2-0=2方案：1）可将A排在8-11周中。
22、2）将B，E整体后移2周：B排在3，4周E排在5、6、7周调整后结果，如下表：第45页/共66页9 9 9 93 36 68 8 8 4 4 7 7 2 2 2 1 1 1 12411工序ABCDEFGH12345678910人数222224102211119 9 9 93 38 8 8 10 10 10 10 10 10 10 10 10 10 10第46页/共66页注：1.若对劳动力有具体的要求，如每周不超过多少，还 可进一步调。2.资源平衡结果不一定唯一，也不一定特别平衡。C）评价：利用方差公式：其中：TE总工期第47页/共66页=10初始横道表中：=44.727第48页/共66页修订后
23、进度计算表中：故修订后资源就更均衡了。第49页/共66页6.3.4 工程完工期的概率分布一.确定平均工序时间t(i,j)的三时估计法设工序最乐观时间为aij设工序最保守时间为bij设工序最可能时间为mij求均值求方差说明（华罗庚）：由实际工作情况表明，工作进行时出现最顺利和最不顺利情况都比较少，更多的是在最可能完成时间内完成。第50页/共66页设工时出现m的可能性两倍于出现a或b的可能性应用加权平均法则平均期望工时：第51页/共66页工时的方差：二.期望工期TE =关键路上工序平均时间之和工期的方差2=关键路上工序方差之和第52页/共66页三.求工程在某天内完工的概率（因为完工期为关键路线上各
24、工序时间之和，由中心极限定理易知）例7 某工程网络图如下：1234567A10-13-15B5-8-10C7-8-10D7-9-15E2-4-6F8-10-14G10-12-15H9-11-13估计工程在40天内完成的概率。第53页/共66页解：（1）计算每一工序平均期望工时t(i,j)并确定关键工序。工序工序ABCDEFGHt(i,j)12.837.838.179.67410.33 12.17111234567A(12.83)B(7.83)C(8.17)D(9.67)E(4)F(10.33)G(12.17)H(11)012.8320.662130.3331.3342.542.530.3331
25、.521.1720.6612.830关键工序：A-B-D-G第54页/共66页（2）计算关键工序的方差。工序工序ABDGt(i,j)12.837.839.6712.17ij20.690.691.770.69 TE=12.83+7.83+9.67+12.17=1.96=1-0.8997=0.1003=42.5第55页/共66页四.求完工可能性达到95%的工期第56页/共66页u天津大学1999年博士生入学试题（15%）某工程可分为14道工序，有关资料如下表：（1）请画出该工程的网络图，按正常时间求出完工期和关键路。（2）如果要求工程在46周完成，求总赶工费用最小的赶工方案。（3）（2）中的问题能
26、否采用LP的方法解决？若能，请建立此问题的LP模型（不解）。第57页/共66页工序工序紧前工序紧前工序正常完成正常完成时间（周）时间（周）最快赶工最快赶工时间时间正常费用正常费用（元）（元）最大赶工最大赶工费用（元）费用（元）A-2118002300BA4232003600CB10762007300DC4341004900EC6426003000FC7521002400GD,H5318002200第58页/共66页工序工序紧前工序紧前工序正常完时正常完时间（周）间（周）最快赶工最快赶工时间时间正常费用正常费用（元）（元）最大赶费最大赶费用（元）用（元）HE7490009600IF，G86430
27、04600JD，H9620002500KI4316001800LI5325003000MK，L2110001500NJ6333004000第59页/共66页解：（1）M（2）K（0）123468910571112A（2）B（4）C（10）F（7）D（4）G（5）E（6）H（7）J（9）I（8）K（4）L（5）N（6）026162229344238464749494747424334292216620完工期TE=49关键路：A-B-C-E-H-G-I-L-M第60页/共66页（2）计算每道工序的直接费用率。工序ABCDEFG可压工期1231222直接费用率500200366.6780020015
28、0200工序HIJKLMN可压工期3231213直接费用率200150166.67200250500 233.33第61页/共66页要压缩9周（在关键工序上压）1）先压I,=2;RD=9,RF=11,RJ=5,RK=1,RN=5,故=1所以t=1F（7）M（2）K（0）123468910571112A（2）B（4）C（10）D（4）G（5）E（6）H（7）J（9）I（7）K（4）L（5）N（6）026162229344138454648484646414234292216620完工期TE=48关键路：A-B-C-E-H-G-I-L-M第62页/共66页2）再压I，=1;RD=9,RF=11,R
29、J=5,RK=1,RN=5,故=1所以t=1F（7）M（2）K（0）123468910571112A（2）B（4）C（10）D（4）G（5）E（6）H（7）J（9）I（6）K（4）L（5）N（6）026162229344038444547474545404134292216620完工期TE=47关键路：A-B-C-E-H-G-I-L-M第63页/共66页3）再压B，=2;RD=9,RF=11,RJ=5,RK=1,RN=5,故=1所以t=1F（7）M（2）K（0）123468910571112A（2）B（3）C（10）D（4）G（5）E（6）H（7）J（9）I（6）K（4）L（5）N（6）025152128333937434446464444394033282115520完工期TE=46关键路：A-B-C-E-H-G-I-L-M最小赶工方案如图所示。第64页/共66页（3）（2）中的问题能用线性规划的方法解决。设决策变量Xi为工序AN的压缩时间（i=114）第65页/共66页感谢您的观看！第66页/共66页