西交《离散数学》第六章拓展资源2

网院作业

西交《离散数学额》第六章 图论 拓展资源2
在工程管理中，经常使用到网络图的概念。网络图是用箭线和节点将某项工作的流程表示出来的图形。根据绘图表达方法的不同，分为双代号表示法（以箭线表示工作）和单代号表示法（以节点表示工作）；根据表达的逻辑关系和时间参数肯定与否，又可分为肯定型和非肯定型两大类；根据计划目标的多少，可以分为单目标网络模型和多目标网络模型。网络图的形式如图所示。其组成元素为箭线，节点和线路。节点和箭线在不同的网络图形中有不同的含义，在单代号网络图中，节点表示工作，箭线表示关系，而在双代号网络图中，箭线表示工作及走向，节点表示工作的开始和结束。线路是指从起点到节点的一条通路，工期最长的一条线路称为关键线路，关键线路上工作的时间必须保证，否则会出现工期的延误。
　　1. 什么是网络图 (Network planning)
　　网络图(Network planning)是一种图解模型，形状如同网络，故称为网络图。网络图是由作业、事件和路线三个因素组成的。
　　2. 组成内容
　　一、作业 (Activity)
　　作业，是指一项工作或一道工序，需要消耗人力、物力和时间的具体活动过程。在网络图中作业用箭线表示，箭尾i表示作业开始，箭头j表示作业结束。
　　作业的名称标注在箭线的上面，该作业的持续时间（或工时）Tij标注在箭线的下面。有些作业或工序不消耗资源也不占用时间，称为虚作业，用虚箭线（）表示。在网络图中设立虚作业主要是表明一项事件与另一项事件之间的相互依存相互依赖的关系，是属于逻辑性的联系。
　　二、事件 (Event)
　　事件，是指某项作业的开始或结束，它不消耗任何资源和时间，在网络图中用 “○”表示，“○”是两条或两条以上箭线的交结点，又称为结点。网络图中第一个事件（即○）称网络的起始事件，表示一项计划或工程的开始；网络图中最后一个事件称网络的终点事件，表示一项计划或工程的完成；介于始点与终点之间的事件叫做中间事件，它既表示前一项作业的完成，又表示后一项作业的开始。为了便于识别、检查和计算，在网络图中往往对事件编号，编号应标在“○”内，由小到大，可连续或间断数字编号。编号原则是：每一项事件都有固定编号，号码不能重复，箭尾的号码小于箭头号码（即i<j，编号从左到右，从上到下进行)。
　　三、路线 (Path)
　　路线，是指自网络始点开始，顺着箭线的方向，经过一系列连续不断的作业和事件直至网络终点的通道。一条路线上各项作业的时间之和是该路线的总长度（路长）。在一个网络图中有很多条路线，其中总长度最长的路线称为“关键路线”(Critical path)，关键路线上的各事件为关键事件，关键时间的周期等于整个工程的总工期。有时一个网络图中的关键路线不止一条，即若干条路线长度相等。除关键路线外，其它的路线统称为非关键路线。关键路线并不是一成不变的，在一定的条件下，关键路线与非关键路线可以相互转化。例如，当采取一定的技术组织措施，缩短了关键路线上的作业时间，就有可能使关键路线发生转移，即原来的关键路线变成非关键路线，与此同时，原来的非关键路线却变成关键路线。
　　3. 基本规则
　　绘制网络图必须严格遵循下列基本规则：
　　1、网络图中不能出现循环路线，否则将使组成回路的工序永远不能结束，工程永远不能完工。
　　2、进入一个结点的箭线可以有多条，但相邻两个结点之间只能有一条箭线。当需表示多活动之间的关系时，需增加节点(Node)和虚拟作业(Dummy activity)来表示。如下图1所示：
　　3、 在网络图中，除网络结点、终点外，其它各结点的前后都有箭线连接，即图中不能有缺口，使自网络始点起经由任何箭线都可以达到网络终点。否则，将使某些作业失去与其紧后（或紧前）作业应有的联系。
　　4、箭线的首尾必须有事件，不允许从一条箭线的中间引出另一条箭线。
　　5、为表示工程的开始和结束，在网络图中只能有一个始点和一个终点。当工程开始时有几个工序平行作业，或在几个工序结束后完工，用一个网络始点、一个网络终点表示。若这些工序不能用一个始点或一个终点表示时，可用需工序把它们与始点或终点连接起来。
　　6、网络图绘制力求简单明了，箭线最好画成水平线或具有一段水平线的折线；箭线尽量避免交叉；尽可能将关键路线布置在中心位置。
　　4. 逻辑关系
　　根据网络图中有关作业之间的相互关系，可以将作业划分为：紧前作业、紧后作业和交叉作业。
　　1、紧前作业，是指紧接在该作业之前的作业。紧前作业不结束，则该作业不能开始。
　　2、紧后作业，是指紧接在该作业之后的作业。该作业不结束，紧后作业不能开始。
　　3、平等作业，是指能与该作业同时开始的作业。
　　4、交叉作业，是指能与该作业相互交替进行的作业。
　　下图1反映了网络图中各作业之间的关系。假定C作业为该作业。
　　其中，A作业为C作业的紧前作业。
　　B、C、D三作业同时开始，B、D作业为C作业的平行作业。
　　E作业在C作业完成之后才能开始，E作业为C作业的紧后作业。
　　F、G作业为C作业的交叉作业，G交叉作业必须在紧后作业E与交叉作业F完成后才能开始。
　　网络图中作业之间的逻辑关系是相对的，不是一成不变的。只有指定了某一确定作业，考察它的与之有关各项作业的逻辑联系，才是有意义的。
本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986