《项目管理-运筹学-第10章 (1)》由会员分享，可在线阅读，更多相关《项目管理-运筹学-第10章 (1)（28页珍藏版）》请在金锄头文库上搜索。
1、第 十 章 图与网络分析,2,图与网络分析 引 言,起源：东普鲁士的哥尼斯堡，布雷格尔河上的七桥问题。 图论是应用非常广泛的运筹学分支，它已经广泛地应用于：系统科学，工程技术，交通运输，经济管理，电子计算机等各项领域。许多问题都可以同图论的理论和方法来加以解决。例如： 通信线路的架设， 输油管道的铺设， 铁路或者公路交通网络的合理布局等 都可以应用图论的方法，快捷地加以解决。,3,图与网络分析 引 言(七桥问题),4,5,图与网络分析 图的基本概念,图：由非空的结点集V以及由结点对表示的边所构成的边集E所构成。记作：G（V，E）。 图的分类,有向图：所有的边都是有向边，有向边（v1，v2）又称
2、弧； 无向图：所有的边都是无向边，无向边 v1，v2 又称边。,|V|p（G）p，称为图的阶数 |E|=q(G)=q，,有限图：V（G）、E（G）均为有限集合； 无限图： V（G）、E（G）至少一个为无限集合。,空图：q0的图。平凡图：p1的图。多重边、环。 简单图、多重图。结点的次数（度数），入度与出度。,6,图与网络分析 图的基本概念,悬挂点、悬挂边、孤立点。 支撑子图：对图G（V，E），若又有 则称 是G的支撑子图。,定理：,7,图与网络分析 树,不含圈的连通图，称为树。 定理1：设G（V，E）是一个树，p（G）2，则G中至少有两个悬挂点。 定理2：图G（V，E）是一个树，iff，G不含
3、圈，且仅有p1条边。 定理3：图G（V，E）是一个树，iff，G是连通的，且q（G）p（G）1。 定理4：图G是一个树，iff，G的任意两个结点之间有且仅有一条链。 注意三个条件：G连通，G不含圈， q（G）p（G）1，任两个成立即可构成树。,8,图与网络分析 树,图的支撑树 支撑树：设图T是图G的支撑子图，若T是树，则称T是G的支撑树。 定理：图G有支撑树的充要条件是图G是连通的。 赋权图：给图G的每条边vi,vj赋权wij，则称图G为赋权图。 最小支撑树问题：设连通赋权图G的每个权wij均非负。在图G的各个支撑树中，如何寻找一个支撑树，使其所有边的权数之和在各个支撑树中是最小的？ 求最小支
4、撑树的方法：破圈法，避圈法。,9,图与网络分析 树,Kruskal算法（避圈法） 先画出图G的所有结点。 从G中选择权数最小的一条边，将其加到图T对应的结点之间，但要求新图不构成回路。如此反复，直至构造出支撑树为止。 Prime算法（避圈法） 将G的结点集划分为：V1：已连接结点集；V2：未连接结点集。 方法：从G中任取一个结点，设为v1，取V1v1; V2中各结点与V1中各结点有边相连，从这些连接V1、V2的边 中选择一条长度最短者，其在V2中关联的结点设为v2，将v1，v2加到图中，并使V1：V1 v2，V2：V2 v2。 如此往复，直至V2为空集为止。,10,图与网络分析 树,例,v1,
5、v2,v3,v4,v5,v6,6,5,1,5,2,3,4,4,7,11,图与网络分析 最短路问题,解决某些复杂优化问题的重要工具，在设施选址、运输线路安排、设备更新等问题中有重要应用。 这里主要考虑赋权有向图的最短路问题。即求某结点v1到其它结点vj的最短路及其长度，最短路的长度称为距离。 Dijkstra算法 适用范围：图中无负权时。 基本思想：略。,12,图与网络分析 最短路问题,步骤： 设图中有v1，v2，vn共n个结点，求v1到其它结点的最短路。设S：从v1出发的最短路已求出的结点集合，设TVS。对S中的结点给予P标号，标号值表示v1到该结点的最短路；对T中的结点给予T标号，标号值表示
6、v1到该结点的最短路长度的某一上界。 对v1标上P标号0，则Sv1。 对其它结点标上T标号。,13,图与网络分析 最短路问题, 重复、以至, 用反向追踪法求v1vn的最短路。,例1,14,图与网络分析 最短路问题,例2,15,图与网络分析 最短路问题,应用举例：设备更新问题 每年年初，厂领导决定某设备是继续使用旧的，还是买新的。现制定一个5年内的设备更新计划，使总费用最低。,16,图与网络分析 最短路问题,应用举例：小学校（选矿厂）选址问题,A（50）,B（40）,C（60）,D（20）,E（70）,F（90）,2,7,4,6,8,1,3,1,6,3,学生人数,距离,问：学校建在何处，可以方便
7、所有学生上学？,17,图与网络分析 最短路问题,应用举例：消防队（派出所等）选址问题,各居民点之间的距离已知，发生火灾的可能性相同。若建立一个消防站，应建在何处？,若建立二个呢？,18,图与网络分析 最短路问题,生产与存储问题 某工厂生产一种产品，四个季度的需求如下：,每季度的最大产量：6。,生产成本,存储费用,问：每季度生产多少，可以使总费用降到最低？,19,图与网络分析 最大流问题,在许多实际的网络系统中都存在着流量和最大流问题。例如交通运输系统中的车辆流，城市给排水系统的水流、电路中的电流等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重
8、要的作用。,要求指定一个运输方案，使得从vs到vt的货运量最大。,20,图与网络分析 最大流问题,基本概念 可行流 网络上的一个流f叫做可行流，如果f满足以下条件 （1）容量条件：对于每一个弧（vi,vj）A,有0 fij cij. （2）平衡条件： 对于发点vs，有fsj-fjs=v(f) 对于收点vt，有ftj-fjt=-v(f) 对于中间点，有fij-fji=0 其中发点的总流量（或收点的总流量）v(f)叫做这个可行流的流量。 任意一个网络上的可行流总是存在的。例如零流v(f)=0,。 网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量v(f)达到最大值。,21,图与网络分析
9、 最大流问题,设流f=fij是网络D（V，A，C）上的一个可行流。 把D中：fij=cij的弧叫做饱和弧，fijcij的弧叫做非饱和弧; fij=0的弧叫做零流弧， fij0的弧为非零流弧。 设是网络D中连接发点s和收点vt的一条链。定义链的方向是从vs到vt，于是链上的弧被分为两类： 前向弧:与链的方向相同的弧，前向弧的集合记做+。 后向弧：与链的方向相反的弧，后向弧的集合记做-。 增广链，如果链满足以下条件： 1在弧（vi,vj）+上，有0fijcij,即+中的每一条弧是非饱和弧。 2在弧（vi,vj）-上，有0fijcij,即-中的每一条弧是非零流弧。,22,图与网络分析 最大流问题,结
10、合下例，明确前述概念。,23,图与网络分析 最大流问题,设图D=(V，A，C)，点集S,TV,ST=中。将起点在S，终点在T 的所有弧作成集合，记做（S，T）。 设一个网络D=（V，A，C）。如果点集V被剖分为两个非空集合V1和V2，发点vsV1,收点vtV2,那么将弧集（V1,V2）叫做是分离vs和vt的截集。 定义8.9 设一个截集（V1, V2）.将截集（V1,V2）中所有的弧的容量的和叫做截集的截量，记做s(V1,V2),亦即,24,图与网络分析 最大流问题,下面的事实是显然的：如果网络上的一个可行流f*和网络中的一个截集（V1*,V2*），满足条件v*(f*)=c(V1*,V2*),
11、那么f*一定是D上的最大流，而（V1*,V2*）一定是D的所有的截集中截量最小的一个（即最小截集）。 两个定理 定理1：网络中的一个可行流f*是最大流的充分必要条件是，不存在关于f*的增广链。 定理2：在一个网络D中，最大流的流量等于分离vs和vt的最小截集的截量。 定理1实际上提供了一个寻求网络系统最大流的方法： 标号法,25,图与网络分析 最大流问题,求最大流的标号法 从网络中的一个可行流f出发（如果D中没有f，可以令f是零流）。 1标号过程 在标号过程中，网络中的点分为：标号点（分为已检查和未检查两种）、未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的，以便找
12、出增广链；第二个标号是为了用来确定增广链上的调整量。 标号过程开始，先给vs标号（0，+）。这时，vs是标号未检查的点，其他都是未标号点。一般地，取一个标号未检查点vi，对一切未标号点vj： 1）如果vj在弧（vi,vj）上，fijcij,那么给vj标号（vi,l(vj)）.其中l(vj)=minl(vi),cij-fij.这时，vj成为标号未检查的点。 2）如果vj在弧（vj,vi）上，fij0,那么给vj标号（-vi, l(vj)）.其中l(vj)=minl(vi), fij.这时，vj成为标号未检查点。 于是vi成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广链，转入下一步调整过程。,26,图与网络分析 最大流问题,2.调整过程 首先按照vt和其他的点的第一个标号，反向追踪，找出增广链。再看vk的第一个标号，若是vi，则弧(vi,vk)都在上。依次类推，直到vs为止。这时，所找出的弧就成为网络D的一条增广链。取调整量= l(vt),即vt的第二个标号，令 再去掉所有的标号，对新的可行流f=fij,重新进行标号过程，直到找到网络D的最大流为止。,27,图与网络分析 最大流问题,例,28,图与网络分析 最大流问题,解之得,最小截集：截量为5,
