运筹学第七章图论1121

第七章图论第77页第七章图论主要内容：1、图的基本概念；2、网络图的绘制；3、时间参数的计算；4、网络图的调整与优化。重点与难点：网络图的绘制规划和方法，网络时间的计算、工期－资源优化方法，工期－成本优化方法。要求：熟练掌握网络图的绘制方法与技巧，准确计算作业时间和事项时间，能够用网络优化方法解决实际问题。图论是运筹学的一个分支。它广泛应用于物理学、化学、控制论、信息论、管理科学、电子计算机等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论方法来解决。§1基本概念例1铁路交通图例2有五种化学药品，不能放在一起的，用线联起来，那么至少用几个库房存放？（属于染色问题）1、图：由一些点mVVV,,1和这些点之间的一些连线meeE,,1构成的集合E，VG，称为图。2、边：图中不带箭头的连线，称为边。3、弧：图中带箭头的连线，称为弧。4、无向图：由点和边组成的图，称为无向图。5、有向图：由点和弧组成的图，称为有向图。北京天津济南青岛郑州徐州连云港武汉南京上海V5V1V2V3V4v1e4v4e5v5e1e3e6e9v1v2v4v3v5v6v7v8第七章图论第78页6、链：如果序列ikikiiiiveevev,,,,,,12211满足1,itititvve,t=1，…，k，则称其为联接1iv与ikv的链，简记为ikiivvv,,,21。7、路：若在链中，每一条弧的方向皆与序列的走向相一致，则称其为由iv到jv的路。注意：路有方向，链无方向。8、圈：在链ikiivvv,,,21中，若ikivv1，则称其为一个圈。9、回路：第一个点与最后一个点相同的路，称为回路。10、连通图：若图EVG,中，任意两点iV和jV之间至少存在一条链，则称EVG,为连通图。11、网络：给定一个有向图AVD,，在V中指定了两个点，一个称为发点（记为1v），另一个称为收点（记为tv）。其余的点称为中间点。对于每一条弧Avvji,，对应有一个数ijc，称为弧上的“权”。通常把这种赋权的有向图D称为网络。§2网络计划用网络分析的方法编制的计划称为网络计划。它是五十年代末发展起来的一种编制大型工程进度计划的有效方法。编制网络计划包括计算时间参数、确定关键路线及网络优化等内容。一、网络图的组成网络图一般有以下要素组成：1.工程：待计划安排的一项施工任务、科研项目或其它复杂的任务，都称为工程。2.工序：一项工程常包括许多必须完成的、具有明确意义的工作任务单元，称这些工作任务单元为工序。3、事项：相邻工序的分界点用注有编号的节点来表示，这些编号的节点称为事项。事项既表示前面工序的结束，又表示后面工序的开始，起着承前启后的作用。在一个网络图中，只能用一个事项表示整个工程的开始，用一个事项表示整个工程的结束。4．路：一般是指从网络开始事项经过序贯连续的过程达到网络终结事项的工序与事项的集合。5、紧前工序、紧后工序：如果a、b为互相衔接的两道工序，a工序必须在b工序开始前完成，b工序必须在a工序结束后才能开始，则称a工序为b工序的紧前工序，b工序为a工序的紧后工序。6、虚工序：虚工序是不消耗人力、物力、财力和时间等资源的虚构工序。用虚线构成的箭号表示，如A。引入虚工序的目的是为了表示某些工序间的相互联系，使其符合逻辑关系。二、网络图的绘制第七章图论第79页例：用网络图表示：注意：弧表示工序，权表示工序所需时间，结点表示事项。绘制基本规则：1、按工艺流程顺序由左向右排列；2、不能有缺口和回路；在网络图中，除始点、终点之外，其它各结点的前后都应有弧连接，即不能有缺口，使网络图从始点经任何路线都可以到达终点。网络图中，不能有回路，即不能有循环现象，否则将使组成回路的工序永远不能结束，工程永远不能完工。如：3、相邻的两个结点之间只能有一个工序；如：可增加虚工序4、网络图中只能有一个起点和一个终点；拆迁工程设计土建设计采购设备厂房土建设备安装设备调试abcdefg132456tatbtctdtetetg234123422`2``3第七章图论第80页如：可用虚工序增加起点和终点5、编号：箭头号大于箭尾号（由小到大）。一般用箭标删除法来处理：如1234568013524786①③⑤⑥②④⑦第七章图论第81页例某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如下表，要求绘制该工程的网络图。工序紧后工序工序时间（天）ab,c,d,e60bL45cf10dg,h20eh40fL18gk30hL15kL25L-35解：绘图如下：三、图络时间与关键路线1．路线与关键路线在网络图中，从始点开始，按照各个工序的顺序，连续不断地到达终点的一条通路，称其为路线。在上例中，共有5条路线。在各条路线上，完成各个工序的时间之和是不完全相等的。其中，完成各个工序需要时间最长的路线称为关键路线。组成关键路线的工序称为关键工序。当然，关键路线是相对的，也是可以变化的，在采取一定的技术组织措施之后，关键路线有可能变为非关键路线，而非关键路线也有可能变为关键路线。2．网络时间的计算(1)作业时间：每道工序（i,j）的完成时间t(i,j)称为作业时间。作业时间的确定有两种方法：①一时估计法12467835a60d20g30k25Lh15e40f18c10b45第七章图论第82页在确定作业时间时，只给出一个时间值，在具备劳动定额资料的条件下，或者在具有类似工序的作业时间消耗的统计资料时，可以根据这些资料，用分析对比的方法确定作业时间。②三时估计法在不具备劳动定额和类似工序的作业时间消耗的统计资料，且作业时间较长，未知的和难以估计的因素较多的条件下，对完成工序可估计三种时间，之后计算它们的平均时间作为该工序的作业时间。64,bmajit其中a最乐观时间：在顺利情况下，完成工序所需要的最少时间。m最可能时间：在正常情况下，完成工序所需要的时间。b最悲观时间：在不顺利情况下，完成工序所需要的时间。（2）事项时间①事项最早时间jtE：事项最早可能发生的时间称为作业最早时间。通常按箭头事项计算事项最早时间，它等于从始点事项到本事项最长路线的时间长度。一般从始点事项开始，自左向右逐个事项向前计算。箭头事项的最早时间等于箭尾事项最早时间加上作业时间，当同时有两个或若干个箭线指向箭头事项时，选择最大值。01EtjititjtEiE,max其中jtE--箭头事项j的最早时间itE--与j事项相邻的各箭尾最早时间例：ntTEE--终点事项最早时间，为最早完工时间。②事项最迟时间itL；在不误总工期的前提下，事项i最迟发生时间，称为事项最迟时间。事项最迟时间通常按箭尾事项的最迟时间计算，从右向左顺序进行。ntTntEELjitjtitLjL,min13674250024881616101055714“红色”数字表示总时差31122722003175041604227第七章图论第83页其中iTL----箭尾事项i的最迟时间jTL--箭头事项j的最迟时间③工序（i,j）的总时差R(i,j)：在不误总工期的前提下，工序（i,j）的最早开始时间可以推迟的时间，称为工序（i,j）的总时差。jititjtjiREL,,工序总时差越大，表明该工序在整个网络中的机动时间越大，可以在一定范围内将该工序的人力、物力等资源利用到关键工序上去，以达到缩短工期的目的。当ititEL时，事项i为关键事项；当0,jiR时，工序ji,为关键工序。定理：充要条件（1）事项i是关键事项结点i在一条关键路线上；充要条件（2）工序ji,是关键工序弧ji,在一条关键路线上。四、网络优化绘制网络图、计算网络时间和确定关键路线，得到一个初始的计划方案。但通常还要对初始方案进行调整和完善。根据计划的要求，综合地考虑进度、资源利用及降低费用等目标，确定最优的计划方案。即进行网络优化。我们介绍两种方法：（一）工期资源优化在编制网络计划、安排工程进度的同时，就要考虑尽量合理地利用现有资源，并缩短工期。但是，由于一项工程所包括的工序繁多，涉及到的资源利用情况比较复杂，往往不可能在编制网络计划时，一次把进度和资源利用都能够作出统筹合理的安排，常常是需要进行几次综合平衡后，才能得到比较合理的计划方案。具体的要求和作法是：1．优先安排关键工序所需要的资源；2．利用非关键工序的总时差，错开各工序的开始时间，拉平资源需要量的高锋；3．在确实受到资源限制，或者在考虑综合经济效益的条件下，也可以适当地推迟工程完工时间。例：已知完成工序时间、各工序所需劳动力（人/天），如图所示。该工程的人力资源供应强度为12天人/天，问如何安排工程进度？521367400248816161010557143天4人/天52422543725742664426第七章图论第84页进度横道图日期工序12345678910111213141516(1.2)55(1.3)77777(1.4)444444④④④④④④⑷⑷⑷(2.5)4444(3.4)6666(3.5)444(3.6)2222(4.7)444④4④⑷⑷(5.6)55(5.7)22222222222222(6.7)666666合计161216121515111115111115111620101216161210141612131711711812812812888868注：虚线表示机动时间人数（二）时间——费用优化（工期——成本优化）1．在编制网络计划过程中，研究如何使该工程完工时间短、费用少；或者在保证既定的工程完工时间的条件下，所需要的费用最少；或者在限制费用的条件下，工程完工时间最短；这些就是时间——费用优化所要研究和解决的问题。2．一项工程所需要的费用分为两大类：（1）直接费用；包括直接生产工人的工资及附加费，设备、能源、工具及材料消耗等直接与完成工序有关的费用。（2）间接费用；包括管理人员的工资、办公费等。16121234567时间第七章图论第85页3．直接费用、间接费用、总费用与工程完工时间的关系，如图所示。T/正常时间图中，正常时间是在现有的生产技术条件下，由各工序的作业时间所构成的工程完工时间。极限时间是为了缩短各工序的作业时间而采取一切可能的技术组织措施之后，可能达到的最短的作业时间和完成工程项目的最短时间。4．最低成本日程。在进行时间——费用优化时，需要计算在采取各种技术措施之后，工程项目的不同的完工时间所对应的工序总费用和工程项目所需要的总费用，使得工程费用最低的工程完工时间称为成本日程（如图中T’值）。编制网络计划，无论是以降低费用为主要目标，还是以尽量缩短工程完工时间为主要目标，都要计算最低成本日程，从而提出优化方案。直接费用变动率(`)极限时间正常时间用正常时间的工序直接费用极限时间的工序直接费g缩短一天工期增加的直接费用工程工序费用极限时间总费用直接费用间接费用