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