运筹学教程.pptx

清华大学出版社1第11章 网络计划n第1节网络计划图n第2节网络计划图的时间参数计算n第3节时标网络计划图n第4节网络计划的优化n第5节网络计划软件清华大学出版社清华大学出版社2第11章 网络计划v网络计划图的基本思想：网络计划图的基本思想：首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路.通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。清华大学出版社清华大学出版社3第1节 网络计划图v1.1基本术语v1.2双代号网络计划图清华大学出版社清华大学出版社41.1 基本术语v网络计划图:在网络图上标注时标和时间参数的进度计划图。v节点、箭线:网络计划图的基本组成元素。箭线:一段带箭头实射线或虚射线节点:用“”或“”表示箭线之间的连接点v工作:将整个项目按需要粗细程度分解成若干需要耗费时间或需要耗费其他资源的子项目或单元v工程项目网络计划图的两种表达方式：双代号网络计划图o工作计算法o节点计算法单代号网络计划图清华大学出版社清华大学出版社51.1 基本术语v双代号网络计划图：用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用（i-j）两个代号及箭线表示一项工作。在箭线上标记必须的信息v单代号网络计划图用节点表示工作，箭线表示工作之间的先完成与后完成的关系为逻辑关系。在节点中标记必须的信息清华大学出版社清华大学出版社61.2 双代号网络计划图v例例1 1 开发一个新产品，需要完成的工作和先后关系，各项工作需要的时间汇总在逻辑关系表中，见表11-1。要求编制这项目的网络计划图和计算有关参数。序号工作名称工作代号工作持续时间(天)紧后工作1产品设计和工艺设计A60B,C,D,E2外购配套件B45L3锻件准备C10F4工装制造1D20G,H5铸件E40H6机械加工1F18L7工装制造2G30K8机械加工2H15L9机械加工3K25L10装配与调试L35/表11-1清华大学出版社清华大学出版社71.2 双代号网络计划图v根据表11-1中数据，绘制以下网络图，见图11-3清华大学出版社清华大学出版社81.2 双代号网络计划图应遵循的规则和术语1 1、网络计划图的方向、时序和节点编号、网络计划图的方向、时序和节点编号v网络计划图是有向、有序的赋权图，按项目的工作流程自左向右地绘制。v在时序上反映完成各项工作的先后顺序。v节点编号必须按箭尾节点的编号小于箭头节点的编号来标记。v在网络图中只能有一个起始节点，表示工程项目的开始。一个终点节点，表示工程项目的完成。v从起始节点开始沿箭线方向顺序自左往右，通过一系列箭线和节点，最后到达终点节点的通路，称为线路。清华大学出版社清华大学出版社91.2 双代号网络计划图2 2、紧前工作和紧后工作、紧前工作和紧后工作v紧前工作是指紧排在本工作之前的工作；且开始或完成后，才能开始本工作。v紧后工作是指紧排在本工作之后的工作；本工作开始或结束后，才能开始或结束的工作。v在复杂的工程项目中，它们之间的有三种关系：结束后，才开始（FS）；开始后，才开始(SS)；结束后，才结束(FF)。v从起始节点至本工作之前在同一线路的所有工作，称为先行工作；自本工作到终点节点在同一线路的所有工作，称为后继工作。工作G的先行工作有工作A,D;工作K,L是工作G的后继工作。清华大学出版社清华大学出版社101.2 双代号网络计划图3 3、虚工作、虚工作v在双代号网络计划图中，虚工作只表示相邻工作之间的逻辑关系，不占用时间和不消耗人力，资金等的虚设的工作。虚工作用虚箭线 表示4 4、相邻两节点之间只能有一条箭线连接、相邻两节点之间只能有一条箭线连接,否则将造成逻否则将造成逻辑上的混乱。辑上的混乱。v错误画法:图11-4v为了使两节点之间只有一条箭线，可增加一个节点，并增加一项虚工作。正确画法：图11-5图11-4图11-5清华大学出版社清华大学出版社111.2 双代号网络计划图5 5、网络计划图中不能有缺口和回路、网络计划图中不能有缺口和回路v在网络计划图中严禁出现从一个节点出发，顺箭线方向又回到原出发节点，形成回路。回路将表示这工作永远不能完成。网络计划图中出现缺口，表示这些工作永远达不到终点。项目无法完成。6 6、平行工作、平行工作v可与本工作同时进行的工作7、起始节点与终点节点、起始节点与终点节点v当工程开始或完成时存在几个平行工作时，可以用虚工作将它们与起始节点或终点节点连接起来清华大学出版社清华大学出版社121.2 双代号网络计划图8 8、线路、线路v网络图中从起点节点沿箭线方向顺序通过一系列箭线与节点，最后到达终点节点的通路。v关键路线持续时间最长的线路，或称主要矛盾线。关键路线上的各工作为关键工作，因为它的持续时间决定了整个项目的工期。线路线路的组成各工作的持续时间之和（天）1604535=140260101835=12336020302535=170460201535=130560401535=150表11-2例1的5条线路清华大学出版社清华大学出版社131.2 双代号网络计划图9 9、网络计划图的布局、网络计划图的布局v尽可能将关键路线布置在网络计划图的中心位置，按工作的先后顺序将联系紧密的工作布置在邻近的位置。v为了便于在网络计划图上标注时间等数据，箭线应是水平线或具有一段水平线的折线。v在网络计划图上附有时间坐标或日历进程。1010、网络计划图的类型、网络计划图的类型v总网络计划图，以整个项目为计划对象，编制网络计划图，供决策领导层使用。v分级网络计划图，这是按不同管理层次的需要，编制的范围大小不同，详细程度不同的网络计划图；供不同管理部门使用。v局部网络计划图，将整个项目某部分为对象，编制的更详细的网络计划图，供专业部门使用。清华大学出版社14第11章 网络计划n第1节网络计划图n第2节网络计划图的时间参数计算n第3节时标网络计划图n第4节网络计划的优化n第5节网络计划软件清华大学出版社清华大学出版社15第2节 网络计划图的时间参数计算v网络计划的时间参数计算有几种类型网络计划的时间参数计算有几种类型双代号网络计划有工作计算法和节点计算法单代号网络计划有节点计算法。以下仅介绍工作计算法。v网络图中工作的时间参数网络图中工作的时间参数工作持续时间(D)；工作最早开始时间（ES）；工作最早完成时间（EF）；工作最迟开始时间（LS）；工作最迟完成时间（LF）；工作总时差（TF）；工作自由时差（FF）。清华大学出版社清华大学出版社16第2节 网络计划图的时间参数计算v2.1工作持续时间Dv2.2计算关系式清华大学出版社清华大学出版社172.1 工作持续时间Dv1.单时估计法单时估计法(定额法定额法)每每项项工工作作只只估估计计或或规规定定一一个个确确定定的的持持续续时时间间值值的的方方法法。一一般般具具有有工工作作的的工工作作量量，劳劳动动定定额额资资料料以以及及投投入入人人力力的的多多少少等等，计算各工作的持续时间；计算各工作的持续时间；工作持续时间工作持续时间 Q工作的工作量。以时间单位表示，如小时；或以体积、重量、长度等单位表示；R可投入人力和设备的数量；S每人或每台设备每工作班能完成的工作量；n每天正常工作班数。清华大学出版社清华大学出版社182.1 工作持续时间Dv2.三时估计法三时估计法在不具备有关工作的持续时间的历史资料时，在较难估计出工作持续时间时，可对工作进行估计三个时间值，然后计算其平均值。这三个时间值是：o乐观时间在一切都顺利时，完成工作需要的最少时间，记作a。o最可能时间在正常条件下，完成工作所需要时间，记作m。o悲观时间在不顺利条件下，完成工作需要最多时间，记作b。按平均意义可用以下公式计算工作持续时间值：清华大学出版社清华大学出版社192.2 计算关系式v各时间参数的关系见图11-6v参数的计算可在网络图上进行，步骤为:(1)计算各路线的持续时间(2)按网络图的箭线的方向，从起始工作开始，计算各工作的ES,EF.(3)从网络图的终点节点开始，按逆箭线的方向，推算出各工作的LS,LF.(4)确定关键路线(CP)。(5)计算TF,FF.(6)平衡资源图11-6清华大学出版社清华大学出版社202.2 计算关系式v计算例1的各工作的时间参数，并将计算结果记入网络计划图的相应工作的中，见图11-7。图11-7清华大学出版社清华大学出版社212.2 计算关系式v1.工作最早开始时间ES和工作最早完成时间EF的计算利用网络计划图，从网络计划图的起始点开始，沿箭线方向依次逐项计算。第一项工作的最早开始时间是为0，记作ES1-j=0。(起始点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)利用双代号的特征，在表中确定某工作的紧前工作和紧后工作。凡是后续工作的箭尾代号与某工作的箭头代号相同者，便是它的紧后工作；凡是先行工作的箭头代号与某工作的箭尾代号相同者，便是它的紧前工作。清华大学出版社清华大学出版社222.2 计算关系式v例1中ES,EF的计算值在表11-3的，列中。表11-3清华大学出版社清华大学出版社232.2 计算关系式v2.工作最迟开始时间LS与工作最迟完成时间LF从终点节点开始，采用逆序法逐项计算。即按逆箭线方向，依次计算各工作的最迟完成时间LF和最迟开始时间LS，直到第一项工作为止。网络图中最后一项工作(i n)(j=n)的最迟完成时间应由工程的计划工期确定。在未给定时，可令其等于其最早完成时间,即LFi-n=EFi-n。EFi-n由表11-3中的计算结果是已知的了。并且应当小于或等于计划工期规定的时间 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.清华大学出版社清华大学出版社242.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)60LF1-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=0E(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-100=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清华大学出版社清华大学出版社252.2 计算关系式v3.工作时差是指工作有机动时间。有两种时差：工作总时差和工作自由时差。o工作总时差TFi-j：在不影响工期的前提下，工作所具有的机动时间，按工作计算法，为表11-4中=的数据。TFi-j=EFi-jESi-jDi-j=LSi-jESi-j 或TFi-j=LFi-jEFi-jo工作自由时差FF：在不影响其紧后工作最早开始的前提下，工作所具有机动时间:FFi-j=ESj-kESi-jDi-j;或 FFi-j=ESj-kEFi-j清华大学出版社26第11章 网络计划n第1节网络计划图n第2节网络计划图的时间参数计算n第3节时标网络计划图n第4节网络计划的优化n第5节网络计划软件清华大学出版社清华大学出版社27第3节 时标网络计划图v标注有时间坐标的网络计划图称为时标网络计划图，图中箭线的长度就表示工作持续时间的长度。v时间坐标简称时标，在网络计划图的上方或下方用来表示工程进度时间的坐标轴。v图中可用实粗箭线或实红色的箭线表示关键工作和关键线路，并且可用不同线型表示工作的总时差和自由时差。v例1的时标网络计划图如图11-8所示：图11-8清华大学出版社28第11章 网络计划n第1节网络计划图n第2节网络计划图的时间参数计算n第3节时标网络计划图n第4节网络计划的优化n第5节网络计划软件清华大学出版社清华大学出版社29第4节 网络计划的优化v4.1工期优化v4.2资源优化v4.3时间费用优化清华大学出版社清华大学出版社304.1 工期优化v工期优化指：尽量缩短工程项目的完工工期。v主要可采取的措施：技术措施：提高工效，缩短关键工作的持续时间，使关键线路的时间缩短。组织措施：充分利用非关键工作的总时差，合理调配人力、物力和资金等资源。增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期缩短。清华大学出版社清华大学出版社314.2 资源优化v资源优化：在项目工期不变的条件下，均衡地利用资源。v具体操作如下：优先安排关键工作所需要的资源。利用非关键工作的总时差，错开各工作的开始时间，避开在同一时区内集中使用同一资源，以免出现高峰。在确实受到资源制约，或在考虑综合经济效益的条件下，在许可时，也可以适当地推迟工程的工期。实现错开高峰的目的。清华大学出版社清华大学出版社324.2 资源优化v通过例1说明平衡人力资源的方法。假设在例1中，现有机械加工工人为65人，要完成工作D,F,G,H,K，各工作需要的工人人数列于表11-5中。表11-5清华大学出版社清华大学出版社334.2 资源优化v若上述工作若都按最早开始时间安排，在完成各关键工作的75天工期中，每天需要机械加工工人人数如图11-9所示。有10天需要80人，另10天需要81人。超过了现有机械工人人数的约束。调整：以虚线表示的非关键路线上非关键工作F,H有机动时间，若将工作F延迟10天开工，就可以解决第7080天的超负荷问题；将工作H推迟10天开工，可以解决第100110天的超负荷问题。图11-9图11-10清华大学出版社清华大学出版社344.3 时间费用优化v时间-费用优化问题的提法如何使项目工期尽可能缩短，费用尽可能少；在保证既定项目完成时间条件下，所需要费用最少；在费用限制条件下，项目完工时间最短。v完成项目的费用可分为：1.直接费用：直接与项目规模有关的费用。包括材料费用，直接生产工人工资等。为了缩短工作持续时间和工期，就需要增加投入，即增加直接费用。2.间接费用。包括管理费等。一般按项目工期长度进行分摊。工期愈短，分摊的间接费用就愈少。清华大学出版社清华大学出版社354.3 时间费用优化v一般项目的总费用与直接费用和间接费用及项目工期之间存在着一定关系，如图11-11。T1 最短工期，项目总费用最高；T2 最经济的工期；T3 正常的工期当总费用最少工期短于要求工期时，这就是最佳工期。图11-11清华大学出版社清华大学出版社364.3 时间费用优化v进行时间费用优化的步骤：计算工作费用增加率（简称费用率）费用增加率：缩短工作持续时间每一单位时间（如一天）所需要增加的费用。按工作的正常持续时间计算各关键工作的费用率：Ci-j 工作ij的费用率CCi-j 将工作ij持续时间缩短为最短持续时间后，完成该工作所需要的直接费用.CNi-j 在正常条件下完成工作ij所需要的直接费用DNi-j 工作ij正常持续时间DCi-j 工作ij最短持续时间清华大学出版社清华大学出版社374.3 时间费用优化v进行时间费用优化的步骤：计算工作费用增加率（简称费用率）找出费用率最低的一项关键工作或一组关键工作作为缩短持续时间的对象，其缩短后的值不能小于最短持续时间，不能成为非关键工作。同时计算相应增加的总费用，然后考虑由于工期的缩短间接费用的变化，在这基础上计算项目的总费用。重复以上步骤，直到获得满意的方案为止。清华大学出版社清华大学出版社384.3 时间费用优化v通过例1说明已知项目的每天间接费用为400元，利用表11-6中的已知资料，按图11-7安排进度，项目正常工期为170天。表11-6清华大学出版社清华大学出版社394.3 时间费用优化图11-7清华大学出版社清华大学出版社404.3 时间费用优化v170天方案若要缩短这方案的工期，首先从缩短关键路线上直接费用率最小的工作的持续时间，在170天方案中关键工作K,G的直接费用率是最低。从表中可见这两项工作的持续时间都只能缩短10天。v150天方案总直接费用增加到68900（2901035010）=75300元。由于缩短工期，可以减少间接费用40020=8000元，150天方案的总费用与170天方案相比，可以节省1600元。清华大学出版社41第11章 网络计划n第1节网络计划图n第2节网络计划图的时间参数计算n第3节时标网络计划图n第4节网络计划的优化n第5节网络计划软件清华大学出版社清华大学出版社42第5节 网络计划软件v5.1概况v5.2编制网络计划图前的准备工作v5.3软件的功能清华大学出版社清华大学出版社435.1 概况v手工编制网络计划图的时代：20世纪60年代v1980年以后，微机开始普及v1983年以后，出现了微机上使用的网络计划软件v网络计划软件随计算机的更新换代而不断改进v目前网络计划技术应用软件水平已经大约处在第五代。大多数软件利用Windows操作系统，可处理表格及图形输入方式，图形横道图(Gantt图)带逻辑连线、单代号网络计划图，完成各种数值计算等。v第六代：面向对象的图形智能化的操作，并在不断完善。清华大学出版社清华大学出版社445.1 概况v我国梦龙科技有限公司开发的智能项目动态控制软件，目前是国内工程领域中用户最多的项目进度控制软件极易进行进度计划编制、进度计划优化、以及进度跟踪反馈、进度分析、控制等各方面工作可同时优化、计划、管理和控制多个项目；可以多方案分析比较,目标计划跟踪,可以实时监控利用先进的资源平衡来优化资源计划；采用图形化操作，双代号网络图，并同时自动生成7种不同模式图，双代号网络图、单代号、逻辑图、单双混合图、横道图、时标网络图完全根据不同的需要来反映工程各种数据。将整个项目作为一个系统加以处理，通过网络计划形式对整个系统统筹规划，并进行有效的监控管理，解决项目上最关心的两个问题：进度和费用。v以网络计划为核心技术的梦龙智能项目管理动态控制系统MrPert，很好地解决了项目管理者关心的两个问题：进度和费用，为有效地管理工程提供了极大的方便。清华大学出版社清华大学出版社455.1 概况v大量的工程项目实践表明，应用网络计划技术管理后可以缩短建设周期20%，降低工程成本10%之多，而编制网络计划所需费用仅为总费用的0.1%。v在三峡工程、50年大阅兵、“神舟”号研制和发射等众多的项目中，梦龙的MrPert系统得到很好的应用。v有关网络计划的计算机软件的开发和研究发展很快。v现有商品化的软件：如国外的网络计划软件：TimeLine,ProjectScheduler,MicrosoftProject等。清华大学出版社清华大学出版社465.2 编制网络计划图前的准备工作v1.项目的工作分解结构项目的工作分解结构（work breakdown structure，WBS）将一个项目按由粗到细的原则，分解为若干层次，一般是树状结构。分解的粗细程度取决于使用者的要求。最好将项目的工作分解层次多一些，细一些。这是一项基础工作，要求项目的WBS应当是稳定的。确定工作的逻辑关系，列出工作逻辑关系表。当将整个项目的WBS输入计算机后，软件可按使用者的需要，随时显示不同层次的纲目和细目。将工作按逻辑关系表输入计算机后，软件能自动地给WBS的每组成部分指定识别编号。计算机根据工作的识别编号进行运算。并按软件具有的功能，自动完成各种图表的绘制和有关参数的计算。清华大学出版社清华大学出版社475.2 编制网络计划图前的准备工作v2.数据数据。收集和整理对应项目工作分解结构各层次工作的数据。与计算工作持续时间有关的数据对应各工作的所需要资源定额及其有关技术经济指标与计算项目经济指标有关的各工作的费用数据，以便进行项目的时间费用分析。v3.熟悉有关网络计划软件的术语熟悉有关网络计划软件的术语。一类是基本的，掌握本章的基本术语后，就比较容易理解不同软件中的术语。另一类是进一步分析用的术语。需要专门学习，不同软件在表述上有所差异。清华大学出版社清华大学出版社485.3.软件的功能v网络计划软件一般都具有：项目清单表资源清单表任务清单表甘特图网络图项目分解结构树形图资源分布图日历各种分析报告或报表清华大学出版社清华大学出版社495.3.软件的功能v图与表之间的数据是动态连接的，保证数据输入或修改的一致性。v当在任务清单表中输入项目的各工作与有关数据后，软件自动生成甘特图v网络图根据日历中指定的项目开工日期，按规定的每月或周的工作日和工作班数；计算出各工作的最早开始日期最迟开始日期最早结束日期最迟结束日期并计算出关键路线和时差v软件具有平衡资源和优化资源利用功能。v根据需要可打印出，不同详细程度的网络计划图和有关报表。清华大学出版社清华大学出版社505.3.软件的功能v1.界面界面。一般软件都采用视窗界面，能显示：带有时标的甘特图界面，网络计划图界面，资源平衡界面，可指定日期的日历，资源配置表等。显示需要的计算结果。显示关键路线（CPM）v2.操作操作。软件启动后，软件具有操作提示或帮助，便于使用。可以修改初始数据，新增加工作或删改已有工作。各工作的细化或合并，在界面上很容易实现。进行调整软件给出得图表。编制需要的计算关系式和设计输出报表的格式。通过人机交换，进一步分析网络和优化网络等。v3.输出结果输出结果。打印出网络计划图，甘特图（横道图），资源平衡图，日历进度计划，分析报表等。有的软件可允许使用者自行设计报表的格式和打印需要的内容。清华大学出版社清华大学出版社51 说明v编制网络计划图,需要有完整的原始数据.v数据的采集,整理，加工是一项基础工作。