工期网络图的时间——费用优化.doc

时间费用优化某施工单位提交的一项目的网络计划资料如表1所示。如下：序号活动紧前活动正常作业时间（单位：天）最短时间tti乐观时间ai最可能时间mi悲观时间bi正常作业期望时间ti作业时间方差2i正常期望时间对应直接费用(百元)li直接费用（百元）fi直接费用率ki13333012433CA44105124424DB55116124415MA,B31011916/9129126EC,M6666034727GC,M2910816/957838HD,E13534/9636求：（1）每项活动按正常平均时间作业，请绘制相应的网络计划图，指出此时的关键线路（在图上用双色线或色笔标出），并计算出工期。（2）接（1），如果考虑外部影响导致每项活动作业时间发生的随机波动（见表1中悲观时间和乐观时间所在列），那么该项目完工概率要达到90%以上，则该工程工期不低于多少天？（3）接（1）。施工单位经分析后，考虑有些工作可适当赶工（见最短时间所在列），并估算出各工作每赶工1天所需增加的费用（直接费率，见表1最后一列），间接费用为每天9百元。给出增加赶工费最少的方案（要求写出每步调整的工作，调整的天数及最后方案的网络计划，并在最后方案的网络计划中标出关键线路）。（4）请建立第（3）问对应的线性规划模型。33144M 9031140H 3G8E 6D6C53B4A49481319220192239101319104130413131901319040444404413211142244131319192222440034事件i时间参数标记：事件i最早时间tE(i)；事件i最迟时间tL(i)工作（i,j）时间参数标记：tES(i,j)tEF(i,j)TF(i,j)tLS(i,j)tLF(i,j)FF(i,j)最早开 最早结 总时差始时间 束时间最迟开始时间 最迟结束时间 自由时差解：（1）以各工作的正常作业期望时间为工序时间，绘制网络图如下：双代号网络图的绘图原则如下：（1）网络图是有方向的，不允许出现回路，不允许出现从右到左的箭头。（2）直接连接两个相邻节点之间的活动只能有一个，如果实在要表示并列关系可用虚工序。（3）箭线首尾必有节点，不能从箭线中间引出另一条箭线。（4）网络图必须只有一个网络始点和一个终点。（5）各项活动之间的衔接必须按逻辑关系（紧前关系、紧后关系）进行。（6）事件节点采用数字编号，在同一网络图中不允许重复使用，每条箭线箭头节点的编号（J）必须大于其箭尾节点的编号（I）。（7）尽量避免箭线交叉（采用过桥法或指向处理法）。（8）标注出各项工作的准确历时或时间期望值。（9）虚工序用虚箭线表示，仅表达一种工作顺序的先后依赖关系，有两种作用：如果a工序到b工序之间顺着箭头方向仅隔一个虚工序，则a仍是b的紧前活动。如果a、b、c三个活动共用一个开始节点i，则可用虚工序表示这三个活动并行展开且三者都是末端活动。各活动的正常作业期望时间ti=(ai+4mi+bi)/6，方差2i=(bi-ai)2/36，计算见表1第7、8列。以活动M为例，计算如下：t5=(a5+4m5+b5)/6=(3+410+11)/6=9，25=(11-3)2/36=16/9。用图上计算法求出各事件时间参数，然后再求出各工作时间参数，计算结果如上图所示。其中总时差为0的活动组成关键路线（如上图红色箭线所示）：；该项目期望完工工期为22天。（提问：某工序开始节点和结束节点的最早时间与最迟时间相等，它就一定是关键活动吗？答：不一定。比如图中的G活动满足该条件但不是关键活动。）（2）该工程按期望时间完工的工期TE22天，等于各关键活动期望完工时间之和=4+0+9+6+3)。期望总工期的均方差 。假设工程工期Tk服从正态分布N(22,1.7950552)，则完工的概率保证不小于90%的计算表达式为：。计算得到，Tk24.325(天)（3）直接费用率Ki=(fi-li)/(ti-tti),如A的直接费用率K1=(16-4)/(4-2)=6百元/天。时间费用优化方法：【优化原则】优化时，首先选择赶工费用率最低的关键活动进行赶工，非关键活动不需要赶工因为还可利用总时差；每赶工1天（单独某活动赶工或者各关键活动同时赶工）增加的直接费用不超过单位间接费用，否则不值得赶工（原则1和原则4得以反映）。每一次允许的压缩时间以符合以下全部原则为限度。原则1：该关键活动赶工费用率不大于单位间接费用，否则不值得压缩；原则2：关键活动实际压缩时间不大于自身赶工可压缩时间极限；原则3：压缩允许时间不大于关键路线与次关键路线的工期之差。（理由：优化只能使关键路线增多，而不能使之越来越少）；原则4：须同时压缩的各并列关键活动赶工费用率之和不大于单位间接费用，并且不超过各并列关键活动的赶工压缩时间极限。第一步：在关键路线上，直接费用率最低的工作是E（2=min(6,2）9，原则1)，它自身可以赶工2天（=6-4，原则2）。次关键路线是和，时间长度都为21，决定了关键路线这一步只能赶工1天（=22-21，原则3）。因此，工作E赶工 1天(=min(1,2)，剩余赶工时间为1天（=2-1）。这时，关键路线变为两条：，工期都为21天，工作G的1天时差用完而成为关键活动；次关键路线为和，时间长度都为20天。第二步：在上一步赶工以后得到的两条关键路线上，直接费率最低的工作仍是E（2=min(6,2,3）9原则1)，其并列关键活动G自身允许赶工1天（=8-7，原则4后半句），因此E和G同时赶工（2+39, 原则4前半句）1天(=min(1(原则2),8-7,21-20（原则3）)，之后E不能再赶工（0=1-1）； G不能再赶工。这时，关键路线仍为，工期都为20天。次关键路线为和，时间长度都为19天。 第三步：在上一步赶工以后得到的两条关键路线中，工作E、G、H、M、都不能再赶工，唯有工作A可以赶工（69，原则1)，它自身可以赶工2天(=4-2,原则2)，但次关键路线决定了它只能赶工1天(=min(4-2,20-19（原则3）)，之后A的赶工时间还剩余1天（=2-1）。这之后，关键路线变为四条：、以及，工期都为19天。次关键路线为两条：和，时间长度都为15天。第四步：在上一步赶工以后得到的四条关键路线中，工作E、G、H、M、都不能再赶工，关键A和B同时赶工(69，39原则1；6+3=9,原则4前半句)1天（=min(1(原则2),3-2(原则4后半句)，19-15（原则3）)，则总费用不变但工期缩短了。赶工以后，关键路线仍是上一步中所述的那四条。第五步：在四条关键路线中，所有关键活动都不能再赶工，所以优化过程结束。M 9H 3G8(7)E 6(4)D6C53(2)B4(2)A综上所述，在第四步赶工优化以后，各工作的正常工作时间（同原始数据）和赶工后的实际工作时间（见括号中的数字），以及4条关键路线(见图中红色箭线)如下图所示。 由于赶工导致直接费用增加额(4-2)6+(3-2)3+(6-4)2+(8-7)3=22(百元)，导致间接费用节约额(22-18)9=36(百元)，所以该项目的总费用降低了14百元(=36-22)。因此，优化后的总费用TC1=TC0-14=229+li-14=198+(4+1+2+2+12+3+5+6)-14=219（百元）。（4）设节点i的实际开始时间为第tj+1天初，t7为项目的最早完成时刻；设工序（ij）实际的赶工压缩时间为yij天。 习题2：样题：已知下列资料，见表1所示：表1活动期望作业时间/天紧前活动赶工后最短完成时间/天赶进度一天所增加的直接费用（元）乐观时间/天悲观时间/天最可能时间/天ABCD5265A、BA3144600200300100414163106525.55.75工程的间接费用500（元/天）要求：1.请画出该工程的工期网络图（试题比本题略复杂，考单代号网络图绘制）。2.在图上求出所有事件、活动的各种时间参数（自由时差可以不求），以图例标注各种参数符号。3、请算出在12天以内完工的概率。若完工概率不低于90%，则工期可为多少天？4.如果要求缩短两天，应该对哪些活动进行赶工？对上述赶工的经济效益进行分析。（考试题还没有这一问难）TE(i)TL(i)节点i的开工时间节点i的结束时间解：1.该工程按各活动期望时间安排的双代号工期网络图，如图1所示。5265A00055B03325D5611011C5501111虚55055001111图1 工期网络“箭线图”及时间参数图解5555B工作最早完成时间是2，其紧后活动C最早开工时间为5，所以B活动的自由时差为3(=5-2)。见红色字体标记。3活动代号(i,j)最早开工时间ES(i,j)最迟开工时间LS(i,j)活动总时差TF(i,j)最早完工时间EF(i,j) 最迟完工时间LF(i,j)2.该工程的单代号网络图如下：055A0055510D6111结束开始022B3355611C5011图2 工期网络“前导图”及时间参数图解时间参数的图例说明如下：ESDUEFIDLSTFLF其中，ES、EF、LS、LF、TF分别表示最早开始时间、最早结束时间、最迟开始时间、最早结束时间、总时差；DU表示工作历时；ID表示工作代号。2、求解见图1或者图2。关键路线由总时差为零的活动、组成（或者：开始AC结束）。正常工期11天。3、（这一问可能在选择题中考查，课本113-115页有相应的知识点）计算举例：表1中C活动的期望时间为6天，因为6=(4+45.5+10)/6；A活动时间方差：(6-4)2/36=1/9；C活动时间方差：(10-4)2/36=1由第2问已经求出了关键路线是，即关键活动是A活动、虚工序、C活动。整条关键路线的时间方差2=2A+2C=1/9+1=10/9，于是其标准差为103天。关键路线的期望长度t=tA+0+tC=5+6=11天。因此，12天之内完工的概率P（t12）=P12-11103=P(0.9487)=82.86%（查正态分布表）；设x天之内完工的概率Px-11103=0.9，查正态分布表可得出x-11103=1.2816，因此x=1.2816103+1112.3513天。4、第一步：次关键路线是（或者：开始AD结束），时间长度为10，决定了关键路线这一步最多只能赶工1天（=11-10）。在关键路线上，活动A、C的直接费用率分别为600、300，但只有后者不超过间接费用率500，活动C可以赶工2天（=6-4）。所以，活动C赶工 1天(=min(1,2)，剩余赶工时间为1天（=2-1）。这时，关键路线变为两条：（或者：开始AD结束），（或者：开始AC结束），工期都为10天，工作D的1天时差用完而成为关键活动；次关键路线为（或者：开始BC结束），时间长度为7天。关键路线和次关键路线时差为3天。第二步，在上一步赶工以后得到的两条关键路线上，D活动直接费率最低（100=min(300,100)），它可以赶工1天(=5-4)，其并列关键活动C还可赶工1天，而且若二者同时赶工直接费用率之和400(=100+300)不超过间接费用率500,因此D和C同时赶工1天(=min(3,5-4,6-1-4)，之后C和D都不能再赶工（0=1-1）。此后，关键路线仍为（或者：开始AC结束）、（或者：开始AD结束），工期都为9天。次关键路线为（或者：开始BC结束），时间长度为6天。至此，关键活动A、C、D都不能再赶工，已经达到缩短工期2天的要求。总成本最大下降幅度=(11-9)500-(6-4)300+(5-4)100=300元。附录1、双代号网络图的绘图原则如下：（1）网络图是有方向的，不允许出现回路，不允许出现从右到左的箭头。（2）直接连接两个相邻节点之间的活动只能有一个，如果实在要表示并列关系可用虚工序。（3）箭线首尾必有节点，不能从箭线中间引出另一条箭线。（4）网络图必须只有一个网络始点和一个终点。（5）各项活动之间的衔接必须按逻辑关系（紧前关系、紧后关系）进行。（6）事件节点采用数字编号，在同一网络图中不允许重复使用，每条箭线箭头节点的编号（J）必须大于其箭尾节点的编号（I）。（7）尽量避免箭线交叉（采用过桥法或指向处理法）。（8）标注出各项工作的准确历时或时间期望值。（9）虚工序用虚箭线表示，仅表达一种工作顺序的先后依赖关系，有两种作用：如果a工序到b工序之间顺着箭头方向仅隔一个虚工序，则a仍是b的紧前活动。如果a、b、c三个活动共用一个开始节点i，则可用虚工序表示这三个活动并行展开且三者都是末端活动。2、时间费用优化，即如何赶工需要综合考虑的几个原则，如下：在关键路线上，选择赶工费用率（即直接费用率）最低的活动，首先看其赶工费用率是否不超过每天的间接费用，如果是那么它值得赶工；否则，会导致总费用增加。是否值得赶工，还要看其与之并列的关键活动，即该活动的赶工费用率与并列关键活动的赶工费用率之和不超过每天间接费用，才能导致总费用不上升。当然如果项目方不在乎总费用上升（可能项目方会因此得到另外的别的奖励）的话，前面两步的确定的关键活动也是可以赶工的。如果前两步通过了，请继续看：观察上述选定关键活动自身的赶工时间极限，即目前工作时间与最短工作时间的差值，记为a；如果该关键活动有并列关键活动，也要看它们的赶工时间极限。取这些赶工时间极限的最小值，记为b。如果并列活动都是非关键活动，那么这一条就不看了，因为它们此时可以利用总时差而不存在赶工的问题。观察目前关键路线长度与次关键路线长度的时间差，记为c。选定活动的赶工时间也不能超过之。所以，某选定关键活动这一步的实际赶工时间就是d=min(a,b,c)。后面几条是对前面原则的提示，并非优化原则：注意该选定活动如果有并列关键活动