运筹学6.图与网络分析-最短路

第6章 图与网络分析,图的基本概念与基本定理 树和最小支撑树 最短路问题 网络最大流,本章内容重点,引 言,图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。,引 言,随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。,引 言,1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图1a所示。,引 言,A,B,图1 a,C,D,引 言,当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。 为了寻找答案，1736年欧拉将这个问题抽象成图1b所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。,引 言,图1 b,A,C,D,B,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例：公路或铁路交通图、管网图、通讯联络图等各节点及联系的边。如果用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合 G=V,E 式中：V点的集合,E边的集合 如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等这样的图称为网络图。,1.图的基本概念与模型,用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显得并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。,如图6-1所示： 端点，关联边，相邻 环，多重边，简单图 次，奇点，偶点，孤立点 链，圈，路，回路，连通图 完全图，偶图 子图，部分图 例1,2.树和最小支撑树,树图（简称树，记作T（V,E） 在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。,性质1 任何树中必存在次为1的点。 性质2 具有n个顶点的树的边数恰好为 （n-1）条。 性质3 任何具有n个点、（n-1）条边的连通 图是树图。,2.1树的性质,2.2 图的最小部分树,如果G1是G2的部分图，则称G1是G2的部分树（或支撑树）。树图的各条边称为树枝（假定各边均有权重），一般图G2含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（也称最小支撑树） 定理1 图中任一个点i，若j是与i相邻点中距离最近的，则边i,j一定必含在该图的最小部分树内。 推论 把图的所有点分成V和 两个集合，则两集合之间连线的最短边一定含在最小部分树内。,练习:写下图的树图,练习,用破圈法求出下图的一个树图。,取一个圈(v1,v2,v3,v1)，在一个圈中去 掉边e3 。在剩下的图中，再取一个圈 （v1,v2,v4,v3,v1），去掉边e4 。再从圈 （v3,v4 v5,v3）中去掉边e6 。再从圈 (v1,v2,v5,v4,v3,v1 ）中去掉边e7， 这样，剩下的图不含圈，于是得到一个 支撑树，如下图所示。,2.3 避圈法和破圈法,（1）避圈法 从网络图中依次寻找权数较小的边，寻找过程中，节点不得重复，即不得构成圈。注意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最短树或证明网络不存在最短树。 在图中寻找最小部分树的步骤：P153,（2）破圈法, 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树； 去掉该圈中权数最大的边； 反复重复 两步，直到最短树。,练习：用破圈法求出下图的最小部分树,图a,图b,最短路问题,最短路问题是网络理论中应用最广泛的问题之一。许多优 化问题都可以使用这个模型，如设备更新、管道的铺设、 线路的安排、厂区的布局等。,最短路问题的一般提法是：设 为连通图，图中 各边 有权 ( 表示 ， 之间没有边）, 为图中任意两点，求一条道路 ，使它是从 到 的所有路中总权最小的路。即：,最小。,最短路算法中1959年由 （狄克斯特洛）提出的 算法被公认为是目前最好的方法，我们称之为 算 法。下面通过例子来说明此法的基本思想。,条件：所有的权数,思路：逐步探寻。,下求 到 的最短路：,1）从 出发，向 走。首先，从 到 的距离为0，给 标号（0）。画第一个弧。（表明已 标号，或已走出 ）,从 出发，只有两条路可走 ，其距离为,2）,可能最短路为, 给 划成粗线。, 划第二个弧。, 给 标号（4）。,表明走出 后走向 的最短路目前看是 ，最优距离 是4 。,现已考察完毕第二个圈内的路，或者说，已完成 的标号。,3）接着往下考察，有三条路可走：,可选择的最短路为, 给 划成粗线。, 划第3个弧。, 给 标号（6）。,4）接着往下考察，有四条路可走：,可选择的最短路为, 给 划成粗线。, 划第4个弧。, 给 标号（8）。,5）接着往下考察，有四条路可走：,可选择的最短路为, 给 划成粗线。, 划第5个弧。, 给 标号（9）。,6）接着往下考察，有四条路可走：,可选择的最短路为, 给 划成粗线。, 划第6个弧。, 给 标号（13）。,7）接着往下考察，有四条路可走：,可选择的最短路为, 同时给 划成粗线。, 分别给 标号（14）。,最后，从 逆寻粗线到 ，得最短路：,长度为14。,最短路问题的两个应用,最短路问题在图论应用中处于很重要的地位，下面举两个实 际应用的例子。 例1设备更新问题 某工厂使用一台设备，每年年初工厂要作出决定：继续使 用，购买新的？如果继续使用旧的，要负维修费；若要购买 一套新的，要负购买费。试确定一个5年计划，使总支出最小,若已知设备在各年的购买费，及不同机器役龄时的残值与 维修费，如表2所示.,表2,解：把这个问题化为最短路问题。,用点 表示第i年初购进一台新设备，虚设一个点 ，表示第 5年底。,边 表示第i年购进的设备一直使用到第j年初（即第j-1 年底）。,边 上的数字表示第i年初购进设备，一直使用到第j年 初所需支付的购买费、维修的全部费用（可由表8-2计算得 到）。,这样设备更新问题就变为：求从 到 的最短路问题.,表2,给 划成彩线。,给 划成彩线。,给 划成彩线。,给 、 划成彩线。,给 划成彩线。,计算结果：最短路,最短路路长为49。,即：在第一年、第三年初各购买一台新设备为最优决策。 这时5年的总费用为49。,例3 (选址问题 ) 已知某地区的交通网络如图所示， 其中点代表居民小区，边代表公路，边权为小区间公路距离， 问区中心医院应建在哪个小区，可使离医院最远的小区居民就 诊时所走的路程最近？,解 求中心的问题。 解决方法：先求出 到 其它各点的最短路长 如,再求,即为所求。,比如求,给 划成彩线。,给 划成彩线。,给 标号20。,给 划成彩线。,给 标号30。,分别给 划成彩线。,分别给 标号33。,给 划成彩线。,给 标号63。,其它计算结果见下表：,表 1,由于 最小，所以医院应建在 ，此时离医院最 远的小区 距离为48。,第四节 最大流问题,最大流问题是一类应用极为广泛的问题，例如在交通运输 网络中有人流、车流、货物流、供水系统中有水流，金融 系统中有现金流，通信系统中有信息流，等等。,一 有关概念：,例：下图是输油管道网， 为起点， 为终点， ， ， ， 为中转站，边上的数字表示该管道的最大输油能 力（也称容量），记为 ，问应如何安排各管道输油量， 才能使从到的总输油量最大？, 分别称 为发点、收点。其余的点称为中间点。, 每一个边上都给定一个容量的网络称为容量网络，记,的每一个边上都给定一个实际流量 的网络称为给 定了网络一个流。,容量限制 条件： 对每一边上都有,平衡条件： a) 中间点： 流入量=流出量。 b) 发收点： 发出流量=汇入流量。,若 ，称边 是饱和边。, 可增广链：是指从 到 有一条链，此链上有 的现象出现。（非饱和链）,这种流称为可行流。上图就是一个可行流。使流量达到 最大的流称为最大流 。,二 求解最大流：,先给标号 （，+），其中意思是流入的结点，现没 有，纯属一个符号。+表示的流出量。因它上面没有结点 来控制它，故设为+.,1） 寻找可增广链：,b) 接着检查与 相邻接的点 ， ， 。 已饱和，流量 不可再增。再检查 ，可调整量为 4-2=2，可提供量+， 取调整量,给 标号 ，其中 表示 的所调整量2来自 ，且 为正向流（向前流） 。,同理，给 标号,下对已标号点（可望调整点）接着向下检查。 已饱 和。再检查与 相邻接且未标号的点,调整量为,给 标号为,d) 检查与 相邻接且未标号的点 ， 。而 对 来讲是流 入，现欲增加流出量，应压缩 的流入量，只要的流入量,可令调整量为,给 标号为,表示可控量，反方向流量。,f) 下面检查与 相邻接且未标号的点 ，同理，调整量：,给 标号为,g) 最后，给 标号,2）调整流量：从 到 所画出的彩线即为可增广链。沿 该可增广链，从 倒推，标“”号的在实际流量上加上 该调整量，标“”符号的在实际流量上减去该调整量。完 成调整过程。,重新开始标号，寻找可增广链。当标到 时，与 ， 相 邻接的点 ， ， 都不满足标号条件，标号无法继续，且 没有完成标号。此时最大流量即为所求。,习题,1、某人购买一台摩托车，准备在今后4年内使用，他可在第一年初购一台新车，连续使用4年，也可于任何一年末卖掉，于下一年初换一台新车。已知各年初的新车购置价见下表，不同役龄车的年使用维护费及年末处理价见表2。（a)要求确定该人使用摩托车的最优更新策略，使4年内用于购买、更换及使用维护的总费用为最省；（b）若摩托车最多使用三年必须更新，重新求解此问题。,2（1） 1（1） 2（2） 2（0） 1（1） 1（1） 1（1） 5（5） 5（4） 4（3） 2（2） 2（2） 2（0） 2（1） 5（5） 3（2） 3（3） 1（0） 2（1） 2（2） 2（2） 5（4） 1（1） 4（4） 5（2） 5（3）,3（2） 5（4） 5（5） 3（3） 4（3） 3(3) 9(9) 4(4) 8(6) 12(10) 2(2) 3(3) Vs 2(0) 3(3) Vt Vs Vt 4(4) 2(0) 5(4) 6(4) 2(2) 6(6) 6(5) 2(2) 9(6) 5(4) 5(4),