第八章图与网络分析.ppt

《第八章图与网络分析.ppt》由会员分享，可在线阅读，更多相关《第八章图与网络分析.ppt（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 第八章 图与网络分析最短路问题最短路的应用第一讲：最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型，如设备更新、管道的铺设、线路的安排、厂区的布局等。最短路问题的一般提法是：设 为连通图，图中各边 有权 (表示 ，之间没有边）,为图中任意两点，求一条道路 ，使它是从 到 的所有路中总权最小的路。即：最小。最短路算法中1959年由 （狄克斯特洛）提出的算法被公认为是目前最好的方法，我们称之为 算法。下面通过例子来说明此法的基本思想。条件：所有的权数 思路：逐步探寻。下求 到 的最短路：1）从 出发，向 走。首先，从 到 的距离为0，给 标号（0）。画第一个弧

2、。（表明已 标号，或已走出 ）从 出发，只有两条路可走 ，其距离为2）可能最短路为 给 划成粗线。划第二个弧。给 标号（4）。表明走出 后走向 的最短路目前看是 ，最优距离是4。现已考察完毕第二个圈内的路，或者说，已完成 的标号。3）接着往下考察，有三条路可走：可选择的最短路为 给 划成粗线。划第3个弧。给 标号（6）。4）接着往下考察，有四条路可走：可选择的最短路为 给 划成粗线。划第4个弧。给 标号（8）。5）接着往下考察，有四条路可走：可选择的最短路为 给 划成粗线。划第5个弧。给 标号（9）。6）接着往下考察，有四条路可走：可选择的最短路为 给 划成粗线。划第6个弧。给 标号（13）。

3、7）接着往下考察，有四条路可走：可选择的最短路为 同时给 划成粗线。分别给 标号（14）。最后，从 逆寻粗线到 ，得最短路：长度为15。第二讲：最短路问题的两个应用最短路问题在图论应用中处于很重要的地位，下面举两个实 际应用的例子。例12/P264 设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使 用，购买新的？如果继续使用旧的，要负维修费；若要购买 一套新的，要负购买费。试确定一个5年计划，使总支出最小若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表8-2所示.项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费

4、5681118残值43210表8-2解：把这个问题化为最短路问题。用点 表示第i年初购进一台新设备，虚设一个点 ，表示第5年底。边 表示第i年购进的设备一直使用到第j年初（即第j-1年底）。边 上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买费、维修的全部费用（可由表8-2计算得到）。这样设备更新问题就变为：求从 到 的最短路问题.给 划成彩线。给 划成彩线。给 划成彩线。给 划成彩线。给 划成彩线。计算结果：最短路最短路路长为49。即：在第一年、第三年初各购买一台新设备为最优决策。这时5年的总费用为49。例13(选址问题P265)已知某地区的交通网络如图8-37所示，其中点代表

5、居民小区，边代表公路，为小区间公路距离，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？解 求中心的问题。解决方法：先求出 到其它各点的最短路长如再求即为所求。比如求 给 划成彩线。给 划成彩线。给 标号20。给 划成彩线。给 标号30。分别给 划成彩线。分别给 标号33。给 划成彩线。给 标号63。其它计算结果见下表：小区号0 30 50 63 93 45 609330 0 20 33 63 15 306350 20 0 20 50 25 405063 33 20 0 30 18 336393 63 50 30 0 48 639345 15 25 18 48 0 1

6、54860 30 40 33 63 15 063表 8.1由于 最小，所以医院应建在 ，此时离医院最远的小区 距离为48。三.Floyd（佛洛伊德）算法这里介绍得Floyd（1962年）可直接求出网络中任意两点间的最短路。令网络中的权矩阵为其中当其他算法基本步骤为：输入权矩阵例14/P266 计算其中例如：中不带角标的元素表示从 到 的距离（直接有边），带角标的元素表示借 为中间点时的最短路长。中不带角标的元素表示从 到 的距离（直接有边），带角标的元素表示借 为中间点时的最短路长。在放开 的基础上，再放开注意到：在放开 点的基础上，再放开 考察最短路。注意到：说明所有点经过 并没有缩短路程。

7、只有一个新增元素表示任意两点间的最短路长及其路径。第二讲 最大流问题最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流、供水系统中有水流，金融系统中有现金流，通信系统中有信息流，等等。一 有关概念：例：下图是输油管道网，为起点，为终点，为中转站，边上的数字表示该管道的最大输油能 力（也称容量），记为 ，问应如何安排各管道输油量，才能使从到的总输油量最大？分别称 为发点、收点。其余的点称为中间点。每一个边上都给定一个容量的网络称为容量网络，记 的每一个边上都给定一个实际流量 的网络称为给定了网络一个流。容量限制 条件：对每一边上都有 平衡条件：a)中间点：流入量=流出量

8、。b)发收点：发出流量=汇入流量。若 ，称边 是饱和边。可增广链：是指从 到 有一条链，此链上有 的现象出现。（非饱和链）这种流称为可行流。上图就是一个可行流。使流量达到最大的流称为最大流。二 求解最大流：a)先给标号 （，+），其中意思是流入的结点，现没b)有，纯属一个符号。+表示的流出量。因它上面没有结点c)来控制它，故设为+.1）寻找可增广链：b)接着检查与相邻接的点 ，。已饱和，流量不可再增。再检查 ，可调整量为 4-2=2，可提供量+，取调整量给 标号 ，其中 表示 的所调整量2来自 ，且为正向流（向前流）。同理，给 标号 c)下对已标号点（可望调整点）接着向下检查。已饱d)和。再检

9、查与 相邻接且未标号的点 调整量为给 标号为d)检查与 相邻接且未标号的点 ，。而 对 来讲是流入，现欲增加流出量，应压缩 的流入量，只要的流入量可令调整量为给 标号为表示可控量，反方向流量。f)下面检查与 相邻接且未标号的点 ，同理，调整量：给 标号为g)最后，给 标号2）调整流量：从 到 所画出的彩线即为可增广链。沿该可增广链，从 倒推，标“”号的在实际流量上加上该调整量，标“”符号的在实际流量上减去该调整量。完成调整过程。重新开始标号，寻找可增广链。当标到 时，与 ，相邻接的点 ，都不满足标号条件，标号无法继续，且没有完成标号。此时最大流量即为所求。第三讲：最大流问题的应用1.最大匹配问

10、题 二部图（也叫二分图）图G=(V,E),若V=XY且XY=，使得E中每一条边的两个端点必有一个属于X，另一个属于Y，则称G为二部图。记G=（X，Y，E），或G=（X，E，Y）。2匹配：对给定的二部图G=（X，Y，E），若有ME，且M中任意两条边都没有公共端点，则称M为G的一个匹配（也称对集）。既满足：一个人只多做一件工作，每件工作只多由一人来做。即为工作集与工人集之间的一个匹配。3最大匹配问题：表示G中所有的匹配集，即=M|M为G的匹配集|M|表示M的边数，若存在 M0 使对任意的M，有则称 M0 是G 的最大匹配。注：G中最大匹配方案可能不唯一。饱和点：M中任意边的端点称为（关于M的）饱和

11、点，G中其他顶点称为非饱和点。求最大匹配问题方法很多，以前学过交替链法，下介绍最大流法。即所谓2。多端网络问题：例16/P-274 设有5位待业者，5项工作，他们各自能胜任工作的情况如图8-47所示，要求设计一个就业方案，使尽量多的人能就业。其中表示工人。表示工作。二部图中最大匹配问题，可以转化为最大流问题求解。在二部图中增加两个新点 分别作为发点，收点。并用有向边把它们与原二部图中顶点相连，令全部边上的容量均为1。当网络流达到最大时，如果 上的流量为1，就让 作 工作，此即为最大匹配方案。第一次标号。调整第二次标号。再调整。第三次标号。调整。第四次标号。调整第五次标号。标号过程已无法再继续。

12、流量为1的画彩线。工人分别作故最多安排四个人工作。应用2例/习题8.21/P-282：现有5批货物，每批只需一条船装运，要由 ，所在地域运往 ，地域。至于货物从 ，运向 ，三点何处都一样，每批货物出发日期如表8-5，航船行所需天数如表8-6。船只空载和重载时航行时间相同。要求制定一个计划，在半个月内用最少的船只把5批货物运过去。地点510 /121，8地点232112表8-5（出发日期）表8-6（航行天数）解：设 ，分别表示每项运输任务的出发日期及完成日期（i=1，2，3，4，5）则由表8-5和表8-6知：任务路线571013121313810任务路线571013121313810要想用较少的

13、船只在115天内完成任务，关键是自上一任务到达的时间加上返回的时间能否赶上下一个任务出发的时间。若能，则一只船就能完成两批货物的运输任务。以下试运行：任务路线5710131213138105号7号8号回10号地点232112表8-6（航行天数）8号12号回13号14号回任务路线57101312131381010号3号地点232112表8-6（航行天数）1号13号5号回共两只船在13号以前就把5批货物全部运了出去。是否最优？一只船可行否？如何解决？作一个二部图，点集X和Y都表示这5项任务，两点间有连线的条件是第i件任务完成后可赶上作第j件任务。有连线即有匹配，连线越多（匹配数越大）一只船重复使用

14、次数多，使用船只数就越少。最大的匹配就是用最少的船。任务路线571013121313810任务路线571013121313810地点232112表8-6（航行天数）此表示共两只船可完成任务：解不唯一。第四讲：最小费用最大流大家知道，法求最短路只适应于权 0的情况，当网络中出现负权时，此法失效，如：一。带负权的最短路问题：求 到 的最短路。下面通过例子来说明带负权的网络的最短路求法：逐次逼近法：1给标号 （0）。画弧。给 划成彩线。划第二个弧。给 标号（-3）。给 划成彩线。划第三个弧。给 标号（1）。给 划成彩线。划第四个弧。给 标号（2）。给 划成彩线。划第五个弧。给 再次标号（0）。去掉

15、彩线。分别给 划成彩线。划第六个弧。分别给 标号（6）。给 划成彩线。划第七个弧。给 标号（10）。给 划成彩线。到达 已经无负权，路程不可能再减少。给 标号（9）。最短路径为：距离：10。5 最小费用流的问题前两节主要讲了两个问题：最短路问题和最大流问题。下面介绍网络中二者的结合问题：最小费用流的问题。问题的提出是这样的：在一个关于流的网络中，人们不仅需要流达到一定的数量，（甚至达到最大，即最大流）而且每一个流量要有一定的费用，流所走的路线不一样，单位费用不一样。同样数量的流量，可能走的路线不一样，总的费用不一样。从而在限定网络流的基础上，让流沿那些边走，能使总的费用最小（这里的最小费用问题

16、又看成最短路问题）。特别的，当最大流不惟一时，在所有最大流中求一个流f,使总费用最低。流量的费用 ，记为用规划语言可以这样描述：若给定容量网络G=（V，E，C）除给定每个边上的容量外，还给定G=（V，E，C，D）若给定G的一个可行流 ,在总的流量（常数）下使求最费用最大流的基本思想是：从零流 开始，以费用作为边的长度，用求最短路的方法，求出可增广链，调整流量，使其流量逐步达到要求的数量。下通过例子来说明。例：在图8-55所示的网络中，求流量为10的最小费用流。边上括号内为 。先假设此网络是空架子，即0-流。然后，逐步调整流量到10，在什么路线上增加流量？在费用最小的路线上调流量。为简单，把费用

17、网络先拿出来。借费用最短路作为可行流的可增广链，从而在保证流量的同时，又保证费用最低。看下图：上图为0流图，边上的括号内为在此可增广链上，取容量最小的值min8,5,7=5,调整量为5。调整后图为此时，网络流量为 =510，此流的费用为：返回到费用网络中，继续找最短路，进而继续调整。在下面流量的调整中，注意到图（c)有些边的流量已饱和，只能降低，不能再升，如 。而有些边可降，可升。如 。下次调整为了表达上面的意思，我们在费用流网络中，可升、可降的边用两个箭头表示，如下图：下用逐次逼近法求 到 的费用最短路。标 （0），画第一个弧。标 （1），画第二个弧。分别标 （4）、（4），画第三个弧。标号 （5）。画第四个弧。经检查，已没有修改的必要。显然，流的调整量为2。调整后为此时，网络流量为 =710，此流的费用为：在已用过的链上，可增可降的双箭头，只增不降的单箭头。下用逐次逼近发求最短路（可增广链）：显然，流的调整量为3。调整后为此时，网络流量为 =10，最小费用为：