运筹学第07章网络计划

1、第七章 网络计划(Network Programming)网络图 网络图的时间参数计算 网络计划优化 WinQSB软件应用 1917年，亨利甘特发明了著名的甘特图，使项目经理按日历制作任务图表，用于日常工作安排。 我国已故著名数学家华罗庚先生将这些方法总结概括称为统筹方法，在60年代初引入我国，而且身体力行地进行推广应用。 统筹方法的基本原理是：从需要管理的任务的总进度着眼，以任务中各工作所需要的工时为时间因素，按照工作的先后顺序和相互关系作出网络图，以反映任务全貌，实现管理过程的模型化。然后进行时间参数计算，找出计划中的关键工作和关键路线，对任务的各项工作所需的人、财、物通过改善网络计划作出

2、合理安排，得到最优方案并付诸实施。 1957年，杜邦公司将关键路径法（CPM）应用于设备维修，使维修停工时间由125小时锐减为7小时； 1958年，在北极星导弹设计中，应用计划评审技术（PERT），将项目任务之间的关系模型化，使设计完成时间缩短了2年。第一节 网络图 网络图是表示一项工程或一项生产任务中各个工作环节或各道工序的先后关系和所需时间的网状图，它由若干个节点和箭线组成。网络图分为双代号和单代号两种形式。 双代号网络图又称箭线型网络图，用箭线表示工序（或称为活动、作业）。每一条箭线的箭头和箭尾各有一圆圈，圆圈内编有号码，用前后两个圆圈中的号码表示这项工序，如图82（a）所示。 单代号网

3、络图又称为节点型网络图，它用节点表示工序，用箭线表示工序之间的关系，一个工序用一个节点表示。单代号网络图的表示方法如图82（b）所示。 一、箭线型网络图的组成要素 1. 工序 在网络计划中，一个工序就是一个具体活动过程，它需要消耗一定的时间和资源。 在箭线型网络图中，工序用带起、止节点的箭线表示。一条箭线代表一个工序，箭线上方标明工序名称或工序代号，下方标明该工序的活动时间，通常用t(i,j)表示，如图8-3所示: 2. 虚工序 既不需要消耗时间也不需要消耗资源的活动称为虚工序。虚工序是为了准确而清楚地表达各项工序之间的关系而引入的，一般用虚箭线表示。 3. 节点 节点又称事项、事件或节点。它

4、表示一项工序开始或结束的瞬间。在网络图中，节点用圆圈及圆圈内的数字表示。 4. 线路 线路有时又称为路线。观察图84可以发现，从网络图的起始节点出发，顺箭线方向经过一系列节点和箭线，到达网络图的终点节点有若干条通道，每一条通道都称为一条线路。 例如，ABDG（或用表示）就是一条线路。 线路上各个工序延续时间之和称为该线路的长度。其中最长的线路称为关键线路，关键线路上的工序称为关键工序。 需要指出的是，关键线路可以是一条或几条。 二、绘制网络图的规则 把表示各工作的箭线按照先后顺序及逻辑关系，由左至右排列画成图。再给节点统一编号，节点1表示整个计划的开始（总开始事项），图中最大的数码 n 表示计

5、划结束事项（总完工事项），节点由小到大编号，对任一工序(i,j)来讲ij。 绘制网络图时，需要注意以下绘图规则： 1. 网络图只能有一个起始节点和一个终点节点 1657893422. 网络图是有向图,不允许有回路12453673. 相邻两个节点 i,j 之间只能有一条箭线连接12ba4.必须正确表达紧前工序和紧后工序之间的逻辑关系52341abdc5.正确运用虚工序 如前面不符合规则的图8-5,图8-7,图8-8用添加虚工作的方法改画为正确的图。 123465789123ab c 的紧前工序为 a、b， d 的紧前工序为 b 。123456abdc下图错误 虚工作还可以用于正确表示平行工作与交

6、叉工作。一道工作分为几道工作同时进行,称为平行工作,如图8-12(a)中市场场调研(2,3)需12天： 123412（市场调研）如增加人力分为三组同时进行,可画为许多图：412435644 虚工序问题 仅用于表明平行工序间的逻辑关系； 虚工序越少越好。注意： 两件或两件以上的工作交叉进行，称为交叉工作。如工作A与工作B 分别为挖沟和埋管子,那么它们的关系可以是挖一段埋一段，不必等沟全部挖好再埋。可用下图表示。 1234567a3a2a1b1b2b3三、网络图的绘制 1、任务的分解将一项任务根据需要分解成若干个工序；确定各工序之间的关系，即确定紧前工序和紧后工序。紧前工序：当某工序开始时，在该工

7、序前面必须完成的工序。 紧后工序：当某工序完成后，在该工序后面紧接着要开始的工序。工 作工 作 内 容紧前工作工时(周)A市场调查4B资金筹备10C需求分析A3D产品设计A6E产品研制D8F制定成本计划C,E2G制定生产计划F3H筹备设备B,G2I筹备原材料B,G8J安装设备H5K调集人员G2L准备开工投产I,J,K112345678910A410B6D3C8E2F3G2HI8J51LK22、绘制网络图 作出网络图,并在箭线上标出工时。 3. 节点编号 事项节点编号要满足前述的要求，即从起始节点到终点节点按从小到大编号，即工序(i,j)要求 ij 。 四、网络图的分类 1. 肯定型与概率型网络

8、图 肯定型网络图。每道工序的预计工时只为一个估计值，这通常是因为这些工序的实际完成情况一般地可按预计工时达到，即实现的概率等于或近于1。 I,J,KLGKHJB,GIB,GHFGC,EFDEADACBA紧前工作工 作 概率型网络图。每道工序用三种特定情况下的工时，即最快可能完成工时(a)、最可能完成工时(m)、最慢可能完成工时(b)来估计。 2. 总网络图与多级网络图 总网络图。总网络图画的比较概括、综合，反映任务的主要组成部分之间的组织联系。 分级网络图。分级网络图可细分为一级网络图、二级网络图等，分别供不同的管理层次使用。 ftamb第二节 网络图的时间参数计算 图8-15是一个简单的网络

9、图，从始点1到终点8共有4条线路。 计算网络图有关的时间参数，主要目的是找出关键线路（由于网络图中每道工序上表示的都是工时数，所以关键线路是指网络图中需时最长的线路总起点事项到总终点事项），为网络计划的优化、调整和执行提供明确的时间概念。 这4条线路分别为： 683522(天) 6846630(天) 656623(天) 644620(天)一、时间参数的计算公式 1. 事件时间参数 节点的最早时间TE 节点的最早时间TEj是指以节点 j 为开工工序的最早开始时间。用公式表示为： 即工序(j,k)的最早开始时间等于工序(i,j)的最早开始时间与工序(i,j)时间之和。 612344105 对于终点

10、节点编号为 n ，其节点的最早时间就是整个任务（工程）的总最早完工时间，即： 节点的最迟时间TL 节点的最迟时间是指以 i 为完工节点工序的最迟必须完工时间。用公式表示为： 即工序(,i)的最迟必须完工时间等于工序(i,j)的最迟必须完工时间与工序(i,j)时间之差。 6234541061572. 工序时间参数 工序最早开始时间(ES) 利用确定的网络图，从网络图的起始节点开始，沿着箭线方向依次逐项计算。工序最早开始时间等于该工序对应的箭线的箭尾事件的最早可能发生时间，也是紧前工序最早可能完工时间的最大值。用公式表示为： 式中是工序(i,j)的紧前工序的箭尾节点，t(,i)是紧前工序 t(,i

11、)的时间。 工序最早完工时间(EF） 工序最早完工时间等于该工序的最早开始时间与工序所需时间之和，用公式表示为： 工序最迟必须开始时间(LS) 工序最迟必须开始时间是指为保证不影响紧后工序按期开工，本工序最迟必须开始的时间。用公式表示为： 式中k是工序(i,j)的紧后工序的箭头节点。 工序最迟必须完工时间(LF) 工序最迟必须完工时间是指为保证工程按期完工的最迟必须完成的时间。工序最迟必须完成时间就等于该工序的箭头事件的最迟必须发生时间，用公式表示即为： 工序总时差 工序总时差是指在不影响整个任务或工程工期，即不影响紧后工序的最迟必须开始时间的前提下，工序(i,j)的开始时间或完成时间可以前后

12、松动的最大范围。工序(i,j)的总时差计算公式为： 工序自由时差 工序自由时差是指在不影响紧后工序最早开始的条件下，工序(i,j)的开始时间或完成时间可以前后松动的最大范围。其计算公式为： 关键工序和关键线路 总时差为零的工序也叫做关键工序。 网络图中由关键工序组成的从起始节点到终点节点的线路称为关键线路。 二、网络时间参数计算举例 在网络图上计算时间参数时： 最早时间用符号“”表示 最迟时间用符号“”表示。 【8-1】以图8-14为例说明网络图时间参数的计算。 用图上计算法计算各工序最早开始时间和最迟开始时间； 用表上计算法计算各工序的6个参数； 确定任务的关键工序和关键线路。 解：如图8-

13、16，按照节点编号利用式(8.3)和式(8.5)依次计算各工序的最早开始时间和最迟开始时间，并标注于网络图上。 图中各工序的最早开始时间计算如下： 123456789104106382328512ADECFBGKIHJL320410182023232531323126232320181040123456789104106382328512ADECFBGKIHJL041018202323313225123456789104106382328512ADECFBGKIHJL041018202323313225323126232320181040图中各工序的最迟开始时间计算如下： 利用表上计算法计算各

14、工序的6个参数12582032863104工时t(i,j)I、J、KL(9-10)GK(6-9)HJ(8-9)B、GI(7-9)B、GH(7-8)G (6-7)FG(5-6)C、EF(4-5)DE(3-4)AD(2-3)AC(2-4)-B(1-7)-A(1-2)紧前工序工序004410182023232325233101315410182023242326293131311I、J、KL(9-10)29232GK(6-9)26255HJ(8-9)23238B、GI(7-9)24232B、GH(7-8)23230G (6-7)20203FG(5-6)18182C、EF(4-5)10108DE(3-

15、4)446AD(2-3)1543AC(2-4)13010-B(1-7)004-A(1-2)LSES工时t(i,j)紧前工序工序4107101820232325313025324231810182023232631313132323231311L(9-10)312529232K(6-9)313026255J(8-9)313123238I(7-9)262524232H(7-8)232323230 (6-7)232320203G(5-6)202018182F(4-5)181810108E(3-4)1010446D(2-3)1871543C(2-4)231013010B(1-7)44004A(1-2)

16、关键工序 LFEFLSES工时(周)工序013110000010160013110000000160是是是是是是是是123456789104106382328512ADECFBGKIHJL320410182023232531323126232320181040确定任务的关键工序和关键线路 A、D、E、F、G、I、L是关键工序。该问题的关键线路还可写为，总工期为32周。 第三节 网络计划优化 所谓网络计划的优化，就是在满足既定条件下，按一定的衡量指标寻求最优的网络计划过程。理想的衡量指标应综合工程周期、资源、费用等因素，但目前尚没有一个这样的能反映所有因素的综合模型。 从管理的角度看，网络计划的

17、优化可以分为三个主要内容： 缩短工期，以符合规定完工时间的要求，即时间优化。寻求总费用最低的最佳工期，即时间费用优化。工期基本不变，但资源利用最合理，即时间资源优化。 一、时间优化 时间优化就是不考虑人力、物力、财力资源的限制。 由于工期由关键线路上工序的时间所决定，压缩工期就在于如何压缩关键线路上工序的时间。缩短关键线路上工序时间的途径有： 利用平行、交叉工序缩短关键工序的时间； 在关键线路上赶工。 二、时间费用优化 时间费用优化就是在使工期尽可能短的同时，也使费用尽可能少。 1. 直接费用 直接费用是指能够直接计入成本计算对象的费用，如直接工人工资、原材料费用等。直接费用随工期的缩短而增加

18、。 直接费用与工序时间之间的关系图： 在线性假定条件下，活动每缩短一个单位时间所引起直接费用增加称为直接费用变化率，记为e，用公式表示为： 2. 间接费用 正常时间 赶工时间条件下工序所需最少时间为极限时间 正常费用 极限费用 间接费用是与整个工程有关的、不能或不宜直接分摊给某一活动的费用，包括工程管理费用、拖延工期罚款、提前完工的奖金、占用资金应付利息等等。间接费用与工期成正比关系，即工期越长，间接费用越高，反之则越低。 工程总费用、直接费用、间接费用与工期的关系图： 设工期从T压缩至 ，相应的总费用变化为：若：则工期还可以进步缩短；缩短工期，在总费用达到最低后又增加。 若：在进行时间费用优

19、化时，需要把握以下三条规则： 必须对关键线路上的活动赶工； 选择直接费用变化率最小的活动赶工； 在可赶工的时间范围内赶工。 【例8-2】某工程项目网络图如图8-20所示。各道工序的正常时间、正常费用、赶工时间、赶工费用列于表8-3中。设该项目的单位时间的间接费用为 1000元，找出最佳工期。 解：利用正常和赶工情况下的各种数据，计算费用变化率 作业代号节点正常时间赶工时间直接费用变化率时间(周)直接费用(千元)时间(周)直接费用(千元)A1-264350.33 B1-353150.50 C2-4745103.00 D2-653261.00 E3-464270.75 F4-563461.50 G

20、4-6965111.25 H5-722142.00 I6-742151.00 计算正常情况下的工程周期和总费用，确定关键线路。 从图中可以看出，关键路线是，总工期为26周，而总费用为： 3. 费用优化 费用优化方法有两种：一是渐近法，二是标记法。 近法是在各工序采用正常时间的基础上，不断选取费用率最小的关键工序或关键工序的组合，进行有效的时间压缩，从而得到总费用最低的最佳工期。 在图8-21中，工序A的直接费用率最小，因此优先考虑压缩工序A的工序时间。如将A的工序时间从6周压缩到4周。作业代号节点正常时间赶工时间直接费用变化率时间(周)直接费用(千元)时间(周)直接费用(千元)A1-26435

21、0.33 B1-353150.50 C2-4745103.00 D2-653261.00 E3-464270.75 F4-563461.50 G4-6965111.25 H5-722142.00 I6-742151.00 本次调整直接费用增加0.66千元，间接费用减少2千元。 根据直接费用率，选取关键线路上直接费用率最小的工序A、B进行组合优化。工序A、B均可以压缩1周。本次调整直接费用增加0.83千元，间接费用减少1千元。 作业代号节点正常时间赶工时间直接费用变化率时间(周)直接费用(千元)时间(周)直接费用(千元)A1-264350.33 B1-353150.50 C2-4745103.0

22、0 D2-653261.00 E3-464270.75 F4-563461.50 G4-6965111.25 H5-722142.00 I6-742151.00 根据直接费用率，选取关键线路上直接费用率最小的工序I进行优化。工序I可以压缩3周。 本次调整直接费用增加3千元，间接费用减少3千元。 作业代号节点正常时间赶工时间直接费用变化率时间(周)直接费用(千元)时间(周)直接费用(千元)A1-264350.33 B1-353150.50 C2-4745103.00 D2-653261.00 E3-464270.75 F4-563461.50 G4-6965111.25 H5-722142.00

23、 I6-742151.00 根据直接费用率，选取关键线路上直接费用率最小的工序G进行优化。工序G能够压缩2周，结果如图8-25所示。 本次调整直接费用增加2.5千元，间接费用减少2千元。 作业代号节点正常时间赶工时间直接费用变化率时间(周)直接费用(千元)时间(周)直接费用(千元)A1-264350.33 B1-353150.50 C2-4745103.00 D2-653261.00 E3-464270.75 F4-563461.50 G4-6965111.25 H5-722142.00 I6-742151.00 全部计算过程费用变化如表8-4所示： 总费用周数合计间接费用直接费用实际压缩可压

24、缩总工期（周）工序名称计算过程031265726131.662455.6624A32232.492355.4923A,B1,41335.492055.4920I33437.941855.9918G42三、有限资源的合理分配 一项任务的可用资源，一般情况下总是有限的，因此时间计划必须考虑资源问题。如讨论有限资源情况下使工期最短问题。 以人力资源为例。下图所示的网络图，已计算出关键路线为，总工期11天。箭杆上中标注数字为工作每天所需人力数。 12346596751344223433 画出带日程的网络图及资源动态曲线，如下图(图中虚线为非关键工作的总时差)： 901234567891011(天数)(

25、人数)05101520123564751346181920951 由上图可见，若按每道工作的最早开工时间安排，人力需求很不均匀，最多者为20人日，最少为1人日，这种安排即使在人力资源充足条件下也是很不经济的。现假设资源有限，每日可用人力为10人，下面进行计划调整，希望能不延迟总工期或尽量少延迟。 01234567891011(天数)(人数)05101520123564751346调整的基本原则是： (1)尽量保证关键工作的日资源需求量。 (2)利用非关键工作的时差错开各工作的使用资源时间。 (3)在技术章程允许条件下，可适当延长时差大的工作的工时，或切断某些非关键工作，以减少日总需求量。 具体方法是按资源的日需求量所划分的时间段逐步从始点向终点进行调整 9第一次调整：调整0，2时间段。919201815将需要9人的工序推后2天。01234567891011(天数)(人数)0510152012356475134618102091419第二次调整：调整2，3时间段。将需要9人的工序再推后1天。01234567891011(天数)(人数)0510152012356751364910791094第三次调整：调整3，11时间段。将需要9人的工序推到最后。将需要4人的工序推后1天。第四节 WinQSB软件应用 WinQSB软件在网络计划中的应用是通过调用软件中的P