《图与网络计划工业工程》由会员分享，可在线阅读，更多相关《图与网络计划工业工程（58页珍藏版）》请在金锄头文库上搜索。
1、图与网络计划图与网络计划 XX大学经济与管理学院大学经济与管理学院一、 图与网络的基本概念 图论中所研究的图与人们通常所说的图（如数学中的各种几何图形、函数图形）是完全不同的。图：是若干个点和连接这些点中的连线所组成的图形。它不按比例尺画，线段不代表真正的长度，点和线的位置有随意性。 图中的点称为顶点，线称为边。序列：图G中，若一些点和边按照一定的次序排列而成序列，称为由图G的点和边所组成的序列。链：若图G中，由n+1个顶点v0,v1,vn和n条边e1,e2,en组成一个序列，其中每一条边ek和边ek-1在一个端点相连接，和ek+1的另一端点相连接，则称这样的序列为链。 （点和边交替序列v0,
2、 e1, v1, e2, , en ,vn ）且ei vi,vj） 其中v0称为链的起点， vn称为链的终点。链可以记为： v0, v1, ,vn 连通图：在图中，任意两点之间都有一条链相连，叫做连通图。否则是非连通图。非连通图可以由几个连通图构成。树：不含圈的连通图称为树。林：一个不含圈的图称为林。林可以由多个树组成。树的基本性质任意两点之间有且只有一条链若树有p个顶点，则共有q=p-1条边若图是连通的，且q=p-1，则该图不含圈，因此是树若图不含圈，且q=p-1，则该图联通，因此是树。在树中任意去掉一条边，图就不连通。在树中不相邻的两个顶点间添上一条边，恰好得到一个圈。二、 树最小生成树问
3、题，就是赋权图上的最优化问题之一。设有一连通图G=(V,E)，对于每一条边e=vi,vj，有一个权wij0，最小生成树问题就是求图G的生成树T*，使得避圈法:每步从未选的边中，选一条最小权的边，使与已选边不构成圈。寻找最小生成树的方法破圈法：任取一圈，从圈中去掉一条最大权的边，在余下的图中，重复这个步骤，直到无圈为止，即可求得最小树。三、 最短路问题在前面讨论的图G=(V,E)，是由点V和边E组成的，没有标明某点到另一点的方向，即vi,vj与vj,vi是相同的，这种图称为无向图。 但在实际生活中，很多问题用无向图描述不清楚。如交通中的单行道；一项工程中各工序的先后问题等等。显然这些关系仅用边是
4、反映不出来的，这时，可以用一条带箭头的线vjvi反映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算法不适用于负权网络具有负权的网络，应
5、当用Ford算法又叫修正标号法修正标号法的特点是：不但最小T标号应当改为P标号，P标号也可以修改，修改后的P标号再次改为T标号。Ford算法算例（一）网络流的基本概念 许多系统包含了流量问题。如公路系统中的车辆流、金融系统中的现金流、控制系统中的信息流、供水系统中的水流。 最大流问题，它主要是确定一个已知网络所能承受的最大流通量以及如何达到这个最大流通量。发点、收点：给一个有向图D=(V,A)，在V中指定了一点，称为发点，记为Vs，再指定一点，称为收点，记为Vt。其余的点称为中间点。容量：等于每一个弧(vi,vi) A，对应一个Cij，称为弧的容量，通常我们把它叫做网络，记为D=(V,A,C)
6、。四、最大流问题饱和弧和非饱和弧：若给一个可行流f= fij ，我们把网络中使fij cij的弧称为饱和弧。 fij 0的弧称为非零流弧。正向弧和反向弧:若u是网络中从发点S到收到t的一条链，我们定义链的方向是从vs vt，则链上的弧被分为两类：（1）弧的方向与链的方向一致，称为前向弧（正向弧），它的全体记为u+。（2）弧的方向与链的方向相反，称为后向弧（反向弧），它的全体记为u。二、求解网络最大流的基本原理给出一初始可行流，例如fij 0 。寻找增广链，若存在，则通过该增广链调整、增加网络流。若不存在增广链，则网络流不可再增加。求得最大流。定理：可行流f为最大流的充分必要条件是当且仅当网络不
7、存在增广链。第二次迭代第三次迭代：最优解一、网络计划技术的基本概念工程计划与甘特图不易表现工程全貌不便于对各项工作的安排进行筹划和推敲不能识别影响进度的关键工作不能反映一项工作不能按进度完成时对工程进度的影响计划评审技术(PERT)与关键路线法(CPM)系统性和协调性动态性和可控性科学性六、网络计划技术甘特图前甘特图的网络图二、网络图的绘制网络图的构成作业（工作、工序、活动），箭头表示，箭头之上表示工作名称，之下表示工作时间。可有虚工作。事项，节点表示，表示某个工作的结束和另一工作的开始。一个基建项目网络图从开始节点到结束节点的一条路经叫做路线一个网络图的有多条路线，每条路线有一个总时间总时间
8、最长的路线叫做关键路线，关键路线的总时间叫做工期看下面的例子网络图的路线以上网络图共有8条路线可以计算出这8条路线的总时间，最长的是16天。关键路线是当某些工作的时间调整后，可能引起关键路线的变化和工期的变化。例如将工作E的时间缩短为4天，则工期缩短为13天，关键路线将变为1346BEG5651356BFH553网络图的画法作业的串联作业的并联作业的交叉作业的合并绘制网络图的基本原则两事项间只能有一项作业改为网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号网络图只能一个开始节点，一个终止节点不能出现循环路线尽量少交叉，采用暗桥；有层次性。使用暗桥网络图的绘制步骤确定
9、目标，做好准备工作任务分解和分析绘制网络图表4-1 调查项目的任务分解和分析绘制作业图的方法试探性绘制法计算机辅助绘制法流程图过渡绘制法试探性绘制法：试探试探性绘制法：修改三、网络图时间参数计算作业时间的确定事项时间参数的计算作业时间参数的计算关键路线的寻找方法按期完成计划的概率作业时间的确定对具有标准的作业，采用单一时间估计法对一般性作业，采用三点时间估计法最乐观时间：a最可能时间：m最悲观时间：b计算时间期望值和方差作业时间计算方法事项参数的计算事项最早时间ii图上计算法事项最迟时间作业最早时间作业最迟时间作业时间参数的计算时差总时差单时差时差之间的关系表 作业时间参数计算关键路线的确定方法总时差为零的作业即是关键作业，关键总时差为零的作业即是关键作业，关键作业构成关键路线作业构成关键路线四、网络优化工期限定，资源需要平衡资源有限，工期希望最短工期缩短，总费用最小工期限定，资源需要平衡工期不变，就是关键工作时间不能调整资源不平衡将导致资源不足利用时差，调整非关键路线上工作的开始时间，使资源实现平衡。一个例子各工作都按最早开始时间开始调整非关键工作的开始时间资源有限，要求工期最短下图表示的项目只有10人工作第一次调整第二次调整案例分析案例分析
