运筹学教程PPT课件

1、1第1111章 网络计划 网络计划图的基本思想： 首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。 通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路. 通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。 第1页/共51页2第1节 网络计划图 1.1 基本术语 1.2 双代号网络计划图第2页/共51页31.1

2、 基本术语 网络计划图:在网络图上标注时标和时间参数的进度计划图。 节点、箭线:网络计划图的基本组成元素。 箭线:一段带箭头实射线或虚射线 节点:用“”或“”表示箭线之间的连接点 工作:将整个项目按需要粗细程度分解成若干需要耗费时间或需要耗费其他资源的子项目或单元 工程项目网络计划图的两种表达方式： 双代号网络计划图 工作计算法 节点计算法 单代号网络计划图第3页/共51页41.1 基本术语 双代号网络计划图： 用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用（i-j）两个代号及箭线表示一项工作。在箭线上标记必须的信息 单代号网络计划图 用节点表示工作，箭线表示工作之

3、间的先完成与后完成的关系为逻辑关系。 在节点中标记必须的信息ji持续时间工作名称或代号工作代号工作名称持续时间工作代号工作名称持续时间第4页/共51页51.2 双代号网络计划图 例1 1 开发一个新产品，需要完成的工作和先后关系，各项工作需要的时间汇总在逻辑关系表中，见表11-1。要求编制这项目的网络计划图和计算有关参数。 序号工作名称工作代号工作持续时间(天)紧后工作1产品设计和工艺设计A60B,C,D,E2外购配套件B45L3锻件准备C10F4工装制造1D20G, H5铸件E40H6机械加工1F18L7工装制造2G30K8机械加工2H15L9机械加工3K25L10装配与调试L35/表11-

4、1第5页/共51页61.2 双代号网络计划图 根据表11-1中数据，绘制以下网络图，见12346758设计 A60工装制造 1 D20工装制造2 G30加工3 K25装配 L35铸件 E40加工 2 H15外购配套件 B加工1 F1845锻件 C10虚工作 E图11-3第6页/共51页71.2 双代号网络计划图应遵循的规则和术语1 1、网络计划图的方向、时序和节点编号 网络计划图是有向、有序的赋权图，按项目的工作流程自左向右地绘制。 在时序上反映完成各项工作的先后顺序。 节点编号必须按箭尾节点的编号小于箭头节点的编号来标记。 在网络图中只能有一个起始节点，表示工程项目的开始。一个终点节点，表示

5、工程项目的完成。 从起始节点开始沿箭线方向顺序自左往右，通过一系列箭线和节点，最后到达终点节点的通路，称为线路。第7页/共51页81.2 双代号网络计划图2 2、紧前工作和紧后工作 紧前工作是指紧排在本工作之前的工作；且开始或完成后，才能开始本工作。 紧后工作是指紧排在本工作之后的工作；本工作开始或结束后，才能开始或结束的工作。 在复杂的工程项目中，它们之间的有三种关系：结束后，才开始（FS）；开始后，才开始(SS)；结束后，才结束(FF)。 从起始节点至本工作之前在同一线路的所有工作，称为先行工作；自本工作到终点节点在同一线路的所有工作，称为后继工作。工作G的先行工作有工作A,D;工作K,L

6、是工作G的后继工作。第8页/共51页91.2 双代号网络计划图3 3、虚工作 在双代号网络计划图中，虚工作只表示相邻工作之间的逻辑关系，不占用时间和不消耗人力，资金等的虚设的工作。虚工作用虚箭线 表示4 4、相邻两节点之间只能有一条箭线连接, ,否则将造成逻辑上的混乱。 错误画法:图11-4 为了使两节点之间只有一条箭线，可增加一个节点，并增加一项虚工作。正确画法：图11-5图11-4图11-5第9页/共51页101.2 双代号网络计划图5 5、网络计划图中不能有缺口和回路 在网络计划图中严禁出现从一个节点出发，顺箭线方向又回到原出发节点，形成回路。回路将表示这工作永远不能完成。网络计划图中出

7、现缺口，表示这些工作永远达不到终点。项目无法完成。 6 6、平行工作 可与本工作同时进行的工作7、起始节点与终点节点 当工程开始或完成时存在几个平行工作时，可以用虚工作将它们与起始节点或终点节点连接起来第10页/共51页111.2 双代号网络计划图8 8、线路 网络图中从起点节点沿箭线方向顺序通过一系列箭线与节点，最后到达终点节点的通路。 关键路线 持续时间最长的线路，或称主要矛盾线。 关键路线上的各工作为关键工作，因为它的持续时间决定了整个项目的工期。线路线路的组成各工作的持续时间之和（天）1604535=140260101835=12336020302535=170460201535=13

8、0560401535=150表11-2 例1的5条线路第11页/共51页121.2 双代号网络计划图9 9、网络计划图的布局 尽可能将关键路线布置在网络计划图的中心位置，按工作的先后顺序将联系紧密的工作布置在邻近的位置。 为了便于在网络计划图上标注时间等数据，箭线应是水平线或具有一段水平线的折线。 在网络计划图上附有时间坐标或日历进程。1010、网络计划图的类型 总网络计划图，以整个项目为计划对象，编制网络计划图，供决策领导层使用。 分级网络计划图，这是按不同管理层次的需要，编制的范围大小不同，详细程度不同的网络计划图；供不同管理部门使用。 局部网络计划图，将整个项目某部分为对象，编制的更详细

9、的网络计划图，供专业部门使用。第12页/共51页13第1111章 网络计划第1节 网络计划图第2节 网络计划图的时间参数计算第3节 时标网络计划图第4节 网络计划的优化第5节 网络计划软件第13页/共51页14第2节 网络计划图的时间参数计算 网络计划的时间参数计算有几种类型 双代号网络计划有工作计算法和节点计算法 单代号网络计划有节点计算法。以下仅介绍工作计算法。 网络图中工作的时间参数 工作持续时间(D)； 工作最早开始时间（ES）； 工作最早完成时间（EF）； 工作最迟开始时间（LS）； 工作最迟完成时间（LF）； 工作总时差（TF）； 工作自由时差（FF）。第14页/共51页15第2节

10、 网络计划图的时间参数计算 2.1 工作持续时间D 2.2 计算关系式 第15页/共51页162.1 工作持续时间D 1.单时估计法(定额法) 每项工作只估计或规定一个确定的持续时间值的方法。一般具有工作的工作量，劳动定额资料以及投入人力的多少等，计算各工作的持续时间； 工作持续时间 nSRQD Q 工作的工作量。以时间单位表示，如小时；或以体积、重量、长度等单位表示； R 可投入人力和设备的数量； S 每人或每台设备每工作班能完成的工作量； n 每天正常工作班数。第16页/共51页172.1 工作持续时间D 2. 三时估计法 在不具备有关工作的持续时间的历史资料时，在较难估计出工作持续时间时

11、，可对工作进行估计三个时间值，然后计算其平均值。这三个时间值是： 乐观时间在一切都顺利时，完成工作需要的最少时间，记作a。 最可能时间在正常条件下，完成工作所需要时间，记作m。 悲观时间在不顺利条件下，完成工作需要最多时间，记作b。 按平均意义可用以下公式计算工作持续时间值： 226;64abbmaD方差第17页/共51页182.2 计算关系式 各时间参数的关系见图11-6 参数的计算可在网络图上进行，步骤为: (1) 计算各路线的持续时间 (2) 按网络图的箭线的方向，从起始工作开始，计算各工作的ES,EF. (3) 从网络图的终点节点开始，按逆箭线的方向，推算出各工作的LS,LF. (4)

12、 确定关键路线(CP)。 (5) 计算TF,FF. (6) 平衡资源工作 A工作 A工作 A 的紧后工作 BESi-jLSi-jEFi-jLFi-jESj-kEFj-kLSi-kLFj-k工作a的总时差工作a的自由时差工作A的总时差最早开始最迟开始TFi-j=LSi-j-ESi-jTFi-j=LFi-j-EFi-jFFi-j=ESj-k-EFi-j工作持续时间 D i i-j图11-6第18页/共51页192.2 计算关系式 计算例1的各工作的时间参数，并将计算结果记入网络计划图的相应工作的中，见图11-7 。12346758设计 A60工装制造 1 D20工装制造2 G30加工3 K25装配

13、 L35铸件 E40加工 2 H15外购配套件 B加工1 F1845锻件 C10ESLSEFLF标记：0060 606060170 170135 135135135110 110110110808080801351351006060706013512011710010588115107809011712070TFFF0030304704747000000002001820图11-7第19页/共51页202.2 计算关系式 1. 工作最早开始时间ES和工作最早完成时间EF的计算 利用网络计划图，从网络计划图的起始点开始，沿箭线方向依次逐项计算。第一项工作的最早开始时间是为0，记作ES1-j=0。

14、(起始点i=1)。第一件工作的最早完成时间EF1-j=ES1-j+D1-j。第一件工作完成后，其紧后工作才能开始。它工作最早完成时间EF就是其紧后工作最早开始时间ES。本工作的持续时间D。表示为：EFi-j=ESi-j+Di-j 计算工作的ES时,当有多项紧前工作情况下，只能这些紧前工作中都完成后才能开始。因此本工作的最早开始时间是：ES=max(紧前工作的EF)其中EF=ES+工作持续时间D，表示为：ESi-j=maxh(EFh-i)=maxh(ESh-iDh-i) 利用双代号的特征，在表中确定某工作的紧前工作和紧后工作。凡是后续工作的箭尾代号与某工作的箭头代号相同者，便是它的紧后工作；凡是

15、先行工作的箭头代号与某工作的箭尾代号相同者，便是它的紧前工作。第20页/共51页212.2 计算关系式 例1中ES,EF的计算值在表11-3的，列中。表11-3第21页/共51页222.2 计算关系式 2. 工作最迟开始时间LS与工作最迟完成时间LF 从终点节点开始，采用逆序法逐项计算。即按逆箭线方向，依次计算各工作的最迟完成时间LF和最迟开始时间LS，直到第一项工作为止。网络图中最后一项工作(i n)(j=n)的最迟完成时间应由工程的计划工期确定。在未给定时，可令其等于其最早完成时间,即LFi-n=EFi-n。EFi-n由表11-3中的计算结果是已知的了。并且应当小于或等于计划工期规定的时间

16、 Tr。 LF=min(紧后工作的LS)，LS=LF工作持续时间D 其它工作的最迟开始时间LSi-j=LFi-j Di-j;当有多个紧后工作时，最迟完成时间LF=min(紧后工作的LS),或表示为LFi-j=mink(LFj-kDj-k)。 计算从下到上地进行，从工作（7-8）开始，令表11-4的列最后一行LF7-8=EF7-8=170.第22页/共51页232.2 计算关系式工作i-j持续时间Di-j最迟完成时间LFi-j=min(LSj-k)最迟开始时间LSi-j=LFi-jDi-j总时差TFi-j=LSi-j-ESi-j自由时差FFi-j=ESj-kEFi-j=-=-A(1-2)60LF

17、1-2=LS2-4=60LS1-2=LF1-2-60=60-60=00-0=0FF1-2= ES2-3-EF1-2=0B(2-7)45LF2-7=LS7-8=135LS2-7=LF2-7-45=135-45=9090-60=30FF2-7=ES7-8-EF2-7=135-105=30C(2-3)10LF2-3=LS3-7=117LS2-3=LF2-3-10=117-10=107107-60=47FF2-3=ES3-7-EF2-3=70-70=0D(2-4)20LF2-4=LS4-6=80LS2-4=LF2-4-20=80-20=6060-60=0FF2-4=ES4-6-EF2-4=8080=0

18、E(2-5)40LF2-5=LS5-7=120LS2-5=LF2-5-40=120-40=8080-60=20FF2-5=ES5-7EF2-5=100-100=0F(3-7)18LF3-7=LS7-8=135LS3-7=LF3-7-18=135-18=117117-70=47FF3-7=ES7-8-EF3-7=135-88=47G(4-6)30LF4-6=LS6-7=110LS4-6=LF4-6-30=110-30=8080-80=0FF4-6=ES6-7-EF4-6=110-110=0H(5-7)15LF5-7=LS7-8=135LS5-7=LF5-7-15=135-15=120120-10

19、0=20FF5-7=ES7-8-EF5-7=135-115=20K(6-7)25LF6-7=LS7-8=135LS6-7=LF6-7-25=135-25=110110-110=0FF6-7=ES7-8-EF6-7=135-135=0L(7-8)35LF7-8=EF7-8=170LS7-8=LF7-8-35=170-35=135130-135=0FF7-8=T-170=170-170=0表11-4第23页/共51页242.2 计算关系式 3.工作时差 是指工作有机动时间。有两种时差：工作总时差和工作自由时差。 工作总时差TFi-j：在不影响工期的前提下，工作所具有的机动时间，按工作计算法，为表1

20、1-4中=的数据。 TFi-j=EFi-jESi-jDi-j=LSi-jESi-j 或TFi-j=LFi-jEFi-j 工作自由时差FF：在不影响其紧后工作最早开始的前提下，工作所具有机动时间: FFi-j=ESj-kESi-jDi-j; 或 FFi-j=ESj-kEFi-j第24页/共51页25第1111章 网络计划第1节 网络计划图第2节 网络计划图的时间参数计算第3节 时标网络计划图第4节 网络计划的优化第5节 网络计划软件第25页/共51页26第3节 时标网络计划图 标注有时间坐标的网络计划图称为时标网络计划图，图中箭线的长度就表示工作持续时间的长度。 时间坐标简称时标，在网络计划图的

21、上方或下方用来表示工程进度时间的坐标轴。 图中可用实粗箭线或实红色的箭线表示关键工作和关键线路，并且可用不同线型表示工作的总时差和自由时差。 例1的时标网络计划图如图11-8所示：工作 A工作 B工作 C工作 D工作 E工作 F工作 G工作 H工作 K工作 L2 4 6 8 010604510204018301525352 4 6 8 0202 4 6 8 0302 4 6 8 0402 4 6 8 0502 4 6 8 0602 4 6 8 0702 4 6 8 0802 4 6 8 0902 4 6 8 01002 4 6 8 01102 4 6 8 01202 4 6 8 01302 4

22、 6 8 01402 4 6 8 01502 4 6 8 01602 4 6 8 01702 4 6 8 0180D工工作作关键路线非关键路线总时差自由时差图11-8第26页/共51页27第1111章 网络计划第1节 网络计划图第2节 网络计划图的时间参数计算第3节 时标网络计划图第4节 网络计划的优化第5节 网络计划软件第27页/共51页28第4节 网络计划的优化 4.1 工期优化 4.2 资源优化 4.3 时间费用优化第28页/共51页294.1 工期优化 工期优化指：尽量缩短工程项目的完工工期。 主要可采取的措施： 技术措施：提高工效，缩短关键工作的持续时间，使关键线路的时间缩短。 组织

23、措施：充分利用非关键工作的总时差，合理调配人力、物力和资金等资源。增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期缩短。第29页/共51页304.2 资源优化 资源优化：在项目工期不变的条件下，均衡地利用资源。 具体操作如下： 优先安排关键工作所需要的资源。 利用非关键工作的总时差，错开各工作的开始时间，避开在同一时区内集中使用同一资源，以免出现高峰。 在确实受到资源制约，或在考虑综合经济效益的条件下，在许可时，也可以适当地推迟工程的工期。实现错开高峰的目的。第30页/共51页314.2 资源优化 通过例1说明平衡人力资源的方法。 假设在例1中，现有机械加工工人为65人，要完成工作D

24、,F,G,H,K，各工作需要的工人人数列于表11-5中。表11-5第31页/共51页324.2 资源优化 若上述工作若都按最早开始时间安排，在完成各关键工作的75天工期中，每天需要机械加工工人人数如图11-9所示。 有10天需要80人，另10天需要81人。超过了现有机械工人人数的约束。 调整：以虚线表示的非关键路线上非关键工作F,H有机动时间，若将工作F延迟10天开工，就可以解决第7080天的超负荷问题；将工作H推迟10天开工，可以解决第100110天的超负荷问题。24675315天25天30天20天18天f(22人)d (58人)g (42人)k (26人)h (39人)6070809010

25、011012013065人58人80人64人26人42人65人81人天10天c24675315天25天30天20天18天f(22人)d (58人)g (42人)k (26人)h (39人)6070809010011012013065人58人64人26人42人65人天10天c图11-9图11-10第32页/共51页334.3 时间费用优化 时间-费用优化问题的提法 如何使项目工期尽可能缩短，费用尽可能少； 在保证既定项目完成时间条件下，所需要费用最少； 在费用限制条件下，项目完工时间最短。 完成项目的费用可分为： 1. 直接费用：直接与项目规模有关的费用。包括材料费用，直接生产工人工资等。为了缩

26、短工作持续时间和工期，就需要增加投入，即增加直接费用。 2. 间接费用。包括管理费等。一般按项目工期长度进行分摊。工期愈短，分摊的间接费用就愈少。第33页/共51页344.3 时间费用优化 一般项目的总费用与直接费用和间接费用及项目工期之间存在着一定关系，如图11-11。 T1 最短工期，项目总费用最高； T2 最经济的工期； T3 正常的工期 当总费用最少工期短于要求工期时，这就是最佳工期。间接费用直接费用项目总费用工期 T费用T1T2T3图11-11第34页/共51页354.3 时间费用优化 进行时间费用优化的步骤： 计算工作费用增加率 （简称费用率） 费用增加率：缩短工作持续时间每一单位

27、时间（如一天）所需要增加的费用。 按工作的正常持续时间计算各关键工作的费用率： Ci-j 工作ij的费用率 CCi-j 将工作ij持续时间缩短为最短持续时间后，完成该工作所需要的直接费用. CNi-j 在正常条件下完成工作ij所需要的直接费用 DNi-j 工作ij正常持续时间 DCi-j 工作ij最短持续时间jijijijijiDCDNCNCCC第35页/共51页364.3 时间费用优化 进行时间费用优化的步骤： 计算工作费用增加率 （简称费用率） 找出费用率最低的一项关键工作或一组关键工作作为缩短持续时间的对象，其缩短后的值不能小于最短持续时间，不能成为非关键工作。 同时计算相应增加的总费用

28、，然后考虑由于工期的缩短间接费用的变化，在这基础上计算项目的总费用。 重复以上步骤，直到获得满意的方案为止。第36页/共51页374.3 时间费用优化 通过例1说明 已知项目的每天间接费用为400元，利用表11-6中的已知资料，按图11-7安排进度，项目正常工期为170天。表11-6第37页/共51页384.3 时间费用优化图11-7第38页/共51页394.3 时间费用优化 170天方案 若要缩短这方案的工期，首先从缩短关键路线上直接费用率最小的工作的持续时间，在170天方案中关键工作K,G的直接费用率是最低。从表中可见这两项工作的持续时间都只能缩短10天。 150天方案 总直接费用增加到6

29、8900（2901035010）=75300元。由于缩短工期，可以减少间接费用40020=8000元，150天方案的总费用与170天方案相比，可以节省1600元。工期方案 170 天方案 150 天方案 140 天方案 缩短关键工作 K, G D, H, ,E 缩短工作持续时间（天） 10 ，10 105，5 直接费用（元） 68900 75300 83800 间接费用（元） 68000 60000 56000 总费用（元） 139600 135300 139800 第39页/共51页40第1111章 网络计划第1节 网络计划图第2节 网络计划图的时间参数计算第3节 时标网络计划图第4节 网络

30、计划的优化第5节 网络计划软件第40页/共51页41第5节 网络计划软件 5.1 概况 5.2 编制网络计划图前的准备工作 5.3 软件的功能第41页/共51页425.1 概况 手工编制网络计划图的时代：20世纪60年代 1980年以后，微机开始普及 1983年以后，出现了微机上使用的网络计划软件 网络计划软件随计算机的更新换代而不断改进 目前网络计划技术应用软件水平已经大约处在第五代。大多数软件利用Windows 操作系统，可处理表格及图形输入方式，图形横道图(Gantt图)带逻辑连线、单代号网络计划图，完成各种数值计算等。 第六代：面向对象的图形智能化的操作，并在不断完善。第42页/共51

31、页435.1 概况 我国梦龙科技有限公司开发的智能项目动态控制软件，目前是国内工程领域中用户最多的项目进度控制软件 极易进行进度计划编制、进度计划优化、以及进度跟踪反馈、进度分析、控制等各方面工作 可同时优化、计划、管理和控制多个项目；可以多方案分析比较, 目标计划跟踪,可以实时监控 利用先进的资源平衡来优化资源计划；采用图形化操作，双代号网络图，并同时自动生成7种不同模式图，双代号网络图、单代号、逻辑图、单双混合图 、横道图、时标网络图完全根据不同的需要来反映工程各种数据。 将整个项目作为一个系统加以处理，通过网络计划形式对整个系统统筹规划，并进行有效的监控管理，解决项目上最关心的两个问题：

32、进度和费用。 以网络计划为核心技术的梦龙智能项目管理动态控制系统MrPert，很好地解决了项目管理者关心的两个问题：进度和费用，为有效地管理工程提供了极大的方便。第43页/共51页445.1 概况 大量的工程项目实践表明，应用网络计划技术管理后可以缩短建设周期20%，降低工程成本10%之多，而编制网络计划所需费用仅为总费用的0.1%。 在三峡工程、50年大阅兵、“神舟”号研制和发射等众多的项目中，梦龙的MrPert系统得到很好的应用。 有关网络计划的计算机软件的开发和研究发展很快。 现有商品化的软件：如国外的网络计划软件：Time Line, Project Scheduler, Microsoft Project等。第44页/共51页455.2 编制网络计划图前的准备工作 1. 项目的工作分解结构（work breakdown structure ，WBS） 将一个项目按由粗到细的原则，分解为若干层次，一般是树状结构。 分解的粗细程度取决于使用者的要求。最好将项目的工作分解层次多一些，细一些。这是一项基础工作，要求项目的W