5 图与网络计划-IE-工业工程.ppt

网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号 网络图只能一个开始节点，一个终止节点 不能出现循环路线 尽量少交叉，采用暗桥；有层次性。 使用暗桥 网络图的绘制步骤 确定目标，做好准备工作 任务分解和分析 绘制网络图 表4-1 调查项目的任务分解和分析 绘制作业图的方法 试探性绘制法 计算机辅助绘制法 流程图过渡绘制法 试探性绘制法：试探 试探性绘制法：修改 三、网络图时间参数计算 作业时间的确定 事项时间参数的计算 作业时间参数的计算 关键路线的寻找方法 按期完成计划的概率 作业时间的确定 对具有标准的作业，采用单一时间估计法 对一般性作业，采用三点时间估计法 最乐观时间：a 最可能时间：m 最悲观时间：b 计算时间期望值和方差 作业时间计算方法 事项参数的计算 事项最早时间 i i 图上计算法 事项最迟时间 作业最早时间 作业最迟时间 作业时间参数的计算 时差 总时差 单时差 时差之间的关系 表 作业时间参数计算 关键路线的确定方法 总时差为零的作业即是关键作业，关键作业构成关键路线 四、网络优化 工期限定，资源需要平衡 资源有限，工期希望最短 工期缩短，总费用最小 工期限定，资源需要平衡 工期不变，就是关键工作时间不能调整 资源不平衡将导致资源不足 利用时差，调整非关键路线上工作的开始时间，使资源实现平衡。 一个例子 各工作都按最早开始时间开始 调整非关键工作的开始时间 资源有限，要求工期最短 下图表示的项目只有10人工作 第一次调整 第二次调整 案例分析 * 图与网络计划 XX大学经济与管理学院 一、 图与网络的基本概念 图论中所研究的图与人们通常所说的图（如数学中的各种几何图形、函数图形）是完全不同的。 图：是若干个点和连接这些点中的连线所组成的图形。它不按比例尺画，线段不代表真正的长度，点和线的位置有随意性。 图中的点称为顶点，线称为边。 序列：图G中，若一些点和边按照一定的次序排列而成序列，称为由图G的点和边所组成的序列。 链：若图G中，由n+1个顶点v0,v1,…,vn和n条边e1,e2,…,en组成一个序列，其中每一条边ek和边ek-1在一个端点相连接，和ek+1的另一端点相连接，则称这样的序列为链。 （点和边交替序列{v0, e1, v1, e2, …, en ,vn} ） 且ei? [vi,vj]） 其中v0称为链的起点， vn称为链的终点。 链可以记为： {v0, v1, …,vn} 连通图：在图中，任意两点之间都有一条链相连，叫做连通图。否则是非连通图。 非连通图可以由几个连通图构成。 树：不含圈的连通图称为树。 林：一个不含圈的图称为林。林可以由多个树组成。 树的基本性质 任意两点之间有且只有一条链 若树有p个顶点，则共有q=p-1条边 若图是连通的，且q=p-1，则该图不含圈，因此是树 若图不含圈，且q=p-1，则该图联通，因此是树。 在树中任意去掉一条边，图就不连通。 在树中不相邻的两个顶点间添上一条边，恰好得到一个圈。 二、 树 最小生成树问题，就是赋权图上的最优化问题之一。 设有一连通图G=(V,E)，对于每一条边e=[vi,vj]，有一个权wij?0，最小生成树问题就是求图G的生成树T*，使得 避圈法:每步从未选的边中，选一条最小权的边，使与已选边不构成圈。 寻找最小生成树的方法 破圈法：任取一圈，从圈中去掉一条最大权的边，在余下的图中，重复这个步骤，直到无圈为止，即可求得最小树。 三、 最短路问题 在前面讨论的图G=(V,E)，是由点V和边E组成的，没有标明某点到另一点的方向，即[vi,vj]与[vj,vi]是相同的，这种图称为无向图。 但在实际生活中，很多问题用无向图描述不清楚。如交通中的单行道；一项工程中各工序的先后问题等等。显然这些关系仅用边是反映不出来的，这时，可以用一条带箭头的线vj?vi反映vj与vi之间的这种关系。 如工序vi必须在工序vj完成后才能开始。 有向图： 由点集V与弧集A组成的图D=(V,A)。在有向图中， [vi,vj]与[vj,vi]是不相同的。 （狄克斯托算法） 求最短路的标号法是狄克斯托于1959年提出的，适用于wij0的情况，它被公认为最有效的算法。 对每个节点，用两种标号：T和P，表示从始点到该节点的距离，P是最短距离，T是目前路径的距离。 通过不断改进T值，当其最小时，将其改为P。 开始时，令始点有P=0的P标号，其它节点有T= ?。 求解最短路问题的基本思路 Ford算法 Dijkstra算法不适用于负权网络 具有负权的网络，应当用Ford算法又叫修正标号法 修正标号法的特点是：不但最小T标号应当改为