运筹学基础-网络计划(2012修正)

第七章计划评审方法和关键线路法网络计划技术计划评审技术（ProgramEvaluationandReviewTechnique，PERT)是一种组织生产和进行计划管理的科学方法，也称统筹法。它是综合运用计划评审技术和关键路线法的一种较为先进和计划管理方法。关键路线法（Criticalpathmethod,简写CPM)是对计划项目进行核算、评价，然后选定最优计划方案的一种技术。是在计划项目的各项错综复杂的工作中，抓住其中的关键路线进行计划安排的一种方法。第一节PERT网络图及其绘制规则网络图又叫箭头图或统筹图，它是计划项目的各个组成部分内在逻辑关系的综合反映，是进行计划和计算的基础，即网络计划技术的基础是网络图。一、网络图的分类箭线式网络图以箭线代表作业(活动)，以结点代表作业的开始和完成。需要引进虚作业(以虚线表示)，其特点是布图明朗，应用广泛。结点式网络图以结点代表作业(活动)，以箭线表示各之间的待后承接关系。不需要引进虚作业，但其特点是线条纵横交错，不一目了然，应用不广泛。箭线式网络图例135791113151719212325272931ABDEFGHCIJKLMNOPQ箭线代表作业结点代表作业的开始和完成结点（事件）式网络图例始BACDEFGHIJKMNOLPQx结点代表作业箭线代表作业的衔接二、箭线式网络图的构成箭线式网络图是由作业、事件（结点）和线路三个部分组成。1.作业指任何消耗人力、物力或时间等资源的相对独立的作业过程，又称作业或工序。作业在网络图中的表示在网络图中作业用箭线“→”表示，从箭尾到箭头表示一项作业的开始到终结的过程。在箭线的左（上）侧写上作业的名称，右（下）侧写上该作业所占用的时间。与某项作业前面直接相连的作业称为紧前作业，其后直接相连的后继作业为紧后作业。虚作业：虚作业是为了表达相邻工序之间的逻辑关系而虚设的作业。不消耗时间、费用和资源，一般用虚箭线表示。026机器解体82天机器部分维修总装试车5天1天2.事件（结点）事件（也叫结点），是相邻作业的分界点，标志着作业的开始或结束。事件（结点）在网络图中的表示一般用圆圈“Ο”来表示，每个结点编上顺序号；•箭尾结点表示作业的开始，•箭头结点表示作业的完成。结点既不消耗人力、物力，也不占用时间。一项规划只有一个总开始结点称为最初结点，和一个总结束结点称为最终结点。处在网络中间的结点具有两重性，对前面的作业它是终点、对后面的作业它是始点1539b711achijkefd3.线路线路是指从最初事件开始，顺着箭线的方向，由各项作业连贯组成的，到达最终事件的一条路。从最初事件到最终事件可以有不同的路。1539b711achijkefd563765(6)13115530908(5)13115730908630(4)131179(3)1311753010(2)171166125(1)1511712路长：线路的总长度称为路程长，也是线路总作业时间如图所示：从起点①连续到终点⑪的各条线路是路长最长的线路称为关键线路关键路线在所有的线路中，总作业时间最长的线路就是关键路线。或叫主要矛盾线。关键线路决定整个网络计划的完工时间。关键路线，也可由所有各条线路的路长中最长的一条线路所决定。网络分析的主要任务是找出工程中的关键路线，因为它决定着完工期。如果这条线路上工作进度有耽误，则整个工程的工期就要向后推迟；相反，如果能采取积极措施缩短这条线路的完工时间，工期就可能提前。1539b711achijkefd563765关键路线三、绘制网络图的规则和注意事项方向的规定网络图是有方向的，工序应按工艺流程顺序或工作的逻辑关系从左向右排列。作业表示的规定一条箭线和它的相关结点只能代表一项作业，不能代表多项作业两个结点之间只能有一条箭线相连正确的画法13可引入虚作业。132不正确的画法虚作业是为了表达相邻作业之间的逻辑关系而虚设的作业。它不消耗时间、费用和资源，一般用虚箭线表示。虚作业的引进原因(1)虚作业两个事件之间的工作过程只能代表一项作业，当两个或两个以上的作业具有同一个始点和终点时，需要引入虚作业，予以区别。026机器解体82天机器部分维修总装试车5天3天4电器部分维修虚作业3天虚作业的引进原因(2)是为了正确表示各个作业之间的先后承接关系，有时必须引入虚作业。如一个工程各个作业之间的先后关系如表：活动名称紧接的前项活动abcdef无无无a,ba,ca,b,c1539b711achijkefd各项作业之间的关系和表达方式作业a结束后可以开始b和cabc作业c在a和b均结束后才能开始abca、b两项均结束后可以开始c和dacdbc在a结束后即可进行、d必须在a、b两项均结束后才能开始。acdb不允许出现缺口与回路编号应从始事件开始，按照时序依次从小到大对事件编号，直到终事件。编号时不允许箭头编号小于箭尾编号。事件的编号原则箭尾事件(i)小于箭头事件(j)；一般采用非连续编号，即可空留出几个号，跳着编，将来有变化时，不致打乱全局。132132网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。尽量避免箭线之间的交叉1234569781011为了方便计算和美观清晰，PERT网络图中通过调整布局，尽量避免箭线之间的交叉。调整前1234569781011调整后四、箭线式网络图的绘制1.任务的分解就是把一个计划项目的总任务分解成一定数量的分任务，并确定它们之间的先后承接关系分解任务的原则工作的性质不同或由不同单位执行的工作应分开；同一单位进行的工作，时间先后不衔接的要分开；如产品设计与工装设计，铸造、锻、机械加工、装配要分开如技术设计与工作图设计，材料采购与外协件采购要分开占用时间不消耗资源，但影响工程完工日期的工作应作为分任务；如油漆后的干燥，热处理后的冷却，方案的审批等分解任务的要求编制计划要熟悉业务，了解工程项目的各个组成部分，深入调查。例：下表是某一工程的作业明细表任务经过分解以后，可以列出作业明细表。作业紧接的前项作业作业时间(周)ABCDEFGHIJ无无A，BBACE，FD，FG，HI2341532765某一工程的作业时细表2.画网络图(以前图为例)第一步：先画出无紧前作业的A、B，给网络始点编号为①作业紧接的前项作业作业时间(周)ABCDEFGHIJ无无A，BBACE，FD，FG，HI2341532765第二步：用一条斜线“\”消去已画入网络图的作业A、B，在A后面，画出紧前作业为A的作业E；在B后面，画出紧前作业为B的作业D；给新增的事件编号为③、⑤，在A与B后面，画出紧前作业为A、B的作业C；画作业C时要引进虚作业，为新增的事件编号为⑦。第三步：用一条斜线“\\”消去已画入网络图的作业C将F画在紧前作业C之后；为新增的事件编号为⑨。第四步：用一条斜线“\\\”消去已画入网络图的作业D、E、F将G画在紧前作业E、F之后；将H画在紧前作业D、F之后，引入虚作业第五步：再用一条斜线“\”消去已画入网络图的作业G、H以此类推，最后得出网络图某工程的网络图1AB3ED5C79F13GH1511I1719J21作业紧接的前项作业作业时间(周)ABCDEFGHIJ无无A，BBACE，FD，FG，HI2341532765又例作业名称紧接的前项作业abcdef无无无a,ba,ca,b,cf1357911abcde练习：作业名称ABCDEF紧前作业无无无ABB、C练习1：练习2：作业名称ABCDEF紧前作业无无A、BBCD答案F175311ACDE作业名称ABCDEF紧前作业无无无ABB、CB答案F15311ACDB作业名称ABCDEF紧前作业无无A、BBCD7E9第二节网络时间的计算网络时间的计算有三种计算方法：图上计算法、表格计算法和EXCEL计算法。图上计算法要用的有关符号作业最早开始符号。在长方形符号中标以作业最早开始时间值，该符号放在箭线的上方，靠近前事件i的右上角。作业最迟完成符号。在三角形符号中标以作业最迟完成时间值，该符号放在箭线的好方，靠近后事件j的左好角。ESi,j19101379LFi,j一、图上计算法（一）作业时间作业时间就是在一定的生产技术条件下，完成一项作业或一道工序所需的时间，符号Ti,j就是表示i→j这项作业的作业时间。三种可能估计：最乐观时间：在最理想的情况下完成工序所需时间a；最悲观时间：在最不利的情况下完成工序所需时间b；最可能时间：在正常情况下完成工序所需时间m。加权平均就是工序时间t64j,iEbmat工序时间期望时间确定作业时间的方法：(1)单一时间估计法：就是在估计各项作业的时间时，只确定一个时间值。(2)三种时间估计法：就是在估计各项作业的作业时间时，先估计出三个时间值，然后再求出完成该作业的作业时间。22E)6tab（方差例、求作业的期望时间和方差各项作业的三个估计时间如下表，求各作业的期望时间和方差。作业(i,j)代号估计完成时间（a-m-d)/T(1)(2)(3)(1,2)A3-5-7(1,3)B8-9-16(1,4)C8-11-14(3,4)D2-4-6(2,5)E3-4-5(4,6)F8-16-18(5,6)G18-20-28(5,8)H26-33-52(5,7)I18-25-32(7,8)J12-15-18(6,8)K11-21-25计算：作业(i,j)代号估计完成时间（a-m-b)/T期望完成时间（d）方差(1,2)A3-5-750.44(1,3)B8-9-16101.78(1,4)C8-11-14111.00(3,4)D2-4-640.44(2,5)E3-4-540.11(4,6)F8-16-18152.78(5,6)G18-20-28212.78(5,8)H26-33-523518.78(5,7)I18-25-32255.44(7,8)J12-15-18151.00(6,8)K11-21-25205.4464j,iEbmat22E)6tab（（二）作业时间参数计算}{max0,,1ihihjihijjTESESES其值等于从初始点起到本作业的最长路线上各作业时间之和。从最初作业开始，自左向右，顺着箭线方向逐个计算。1.作业最早可能开工时间ESi,j截取下面部分讨论在箭线式网络图中，要计算的作业时间有两个，即作业的最早开始时间、最迟完成时间。43EF479113551315CDGH65作业最早开始时间计算如下：已知：ES3,7=3，ES5,7=3，T3,7=4，T5,7=3，T7,9=4。求ES7,9=？ES9,11=？ES11,13=？ES11,15=？ES7,9=max{ES3,7+T3,7，ES5,7+T5,7｝=max{3+4，3+3}=7ES9,11=ES7,9+T7,9=7+4=11ES7,9=？43EF479113531315CDGH6533ES9,11=？ES11,13=？ES11,15=？711ES11,13=ES11,15=ES9,11+T9,11=11+3=1414142.作业最迟必须完工时间LFi,j}{min,,jikjkjiijjnTLFLFTLF总指作业最迟必须完工的时刻，否则将会影响后续作业按时开工，以至推迟整个工程的完工时间。最终作业的最迟完成时间应等于总完工时间从终点开始，从右向左，逆箭线方向逐个计算。截取下面部分讨论43EF479113531315CDGH65事件最迟完成时间计算如下：已知：LF11,13=20，LF11,13=20，T7,9=4，T9,11=3，T11,13=6，T11,15=5。求LF9,11=？，LF7,9=？LF9,11=min{LF11,13-T11,13，LF11,15-T11,15}=min{20-6,20-5}=14LF7,9=LF9,11-T9,11=14-3=11LF9,11=？LF7,9=？43EF479113531315CDGH652020LF3,7=？LF5,7=？1411LF3,7=LF5