第六章运筹学图与网络

《第六章运筹学图与网络》由会员分享，可在线阅读，更多相关《第六章运筹学图与网络（71页珍藏版）》请在金锄头文库上搜索。

1、n图的基本概念与模型n树图和图的最小部分树n最短路问题n网络的最大流第五章 图与网络模型(Graph and network modelingn教学目的与要求:给学生建立起用图建模的 思想,学会用图分析问题.n重点与难点:图的各种概念,最短路的求法, 最大流的求法,其中难点是最大流的求法.n教学方法:课堂讲授结合WinQSB软件的使用 .n思考题,讨论题,作业:本章习题.n参考资料:见前言.n学时分配:8学时. 序言哥尼斯堡七桥问题:德国的哥尼斯堡城有一条普雷 格尔河,河中有两个岛屿,河的 两岸与岛屿之间有七座桥相互 连接.当地居民热衷于一项活动 ,一个散步者如何能走过这七座 桥,且每座桥只能

2、走一次,最终 回到出发地.试验者很多,但没 有人才成功.1736年瑞士科学家欧拉发表了关于图论方 面的第一篇科学论文,解决了著名的哥尼斯 堡七桥问题.欧拉将哥尼斯堡七桥问题抽象成如下的图形: 哥尼斯堡七桥问题变为,能否从图 的某一点开始不重复地一笔画出 这个图形.你能一笔画出吗?欧拉在论文中证明了这是不可 能的.为什么?理由是:图上的每一个顶点都与 奇数条边相连接,不可能一笔画 出.第一节 图的基本概念与基本定理一.图的基本概念日常生活中我们见过大量的图,如各种交通图, 各种管网图(电网图,自来水管网,煤气管网,计 算机网络).都是用点表示研究对象,用线(边) 表示这些对象间的关系.因此,图可

3、以定义为点 和边的集合.记作G=V,E,其中V是点的集合,E 是边的集合.在图的点和边上赋予权值(如距离 ,费用,容量等)则称这样的图为网络图记为N, 网络图又可分有向网络图和无向网络图.名词介绍:图中的点用v(vertex)表 示,边用e(edge)表示,每条 边用它联结的点表示,如端点,关联边(incident),相邻(adjacent): 若有边e可表为 称 为边e的端点; 称边e 为 的关联边;若点 与同一条 边关联,称点 相邻;若边 有公共的端 点,称边 相邻.图一环(loop)多重边,简单图:如果边e的两个端点 相重,称该边为环,如 .如果两个端点之间多 于一条边,称它具有多重边,

4、如 对于无环 无多重边的图称为简单图.次,奇点,偶点,孤立点,悬挂点:与某一点 相 关联的边的数目,称为点 的次,记为 如次为奇数的点称为奇 点,否则称为偶点,次为1的点称为悬挂点,次为0 的点称为孤立点. 链(chain),圈(cycle),路(route,path),回路,连 通图:图中某些点和边的交替序列若其中各边 互不相同,且对任意的 点 均相邻,称之为链.如果链中所有的顶点各不相同,这样的链称为路 .判断 哪一个是链,哪一个是路:对起点和终点相重合的链称为圈.起点和终点重 合的路称为回路.在一个图中,如果任意两点间 至少存在一条链,则称该图为连通图,否则为不 连通的.完全图,子图,支

5、撑子图(部分图) 一个简单图中,如果任意两点之间均有边相 连,称为完全图.例1 有甲,乙,丙,丁,戊,己六名运动员报名参加 A,B,C,D,E,F六个项目比赛.报名情况如下表,问 六个项目的比赛顺序如何安排,做到每名运动 员不连续参加两项比赛.ABCDEF甲*乙*丙*丁*戊*己*解:把比赛项目看作研究对象,用点表示.如果 两个项目没有同一名运动员参加,表明它们在 比赛顺序上可排在一起,在代表这两个项目的 点之间连一条线,得一图形.在该图中找一条 包含全部顶点的路,就是符合要求的比赛顺序 .结果:比赛顺序 是A,C,B,F,E,D.练习1 有甲,乙,丙,丁,戊,己六名运动员报名参 加A,B,C,

6、D,E,F六个项目比赛.报名情况如下表 ,问六个项目的比赛顺序如何安排,做到每名 运动员不连续参加两项比赛.ABCDEF甲*乙*丙*丁*戊*己*练习2 有八种化学药品A,B,C,D,P,R,S,T要放进 储藏室保管,出于安全原因,下列各组药不能放 在同一室内,A-R,A-C,A-T,R-P,P-S,S-T,T-B,B-D, D-C,R-S,R-B,P-D,S-C,S-D,问储藏这八种药至 少需几间房?具体的放置方法是什么?第二节 树和图的最小部分树(最小生成树)(Tree and minimal spanning tree)树的定义:无圈的连通图称为树,记为T=(V,E).铁路的转用线,管理机

7、构图,学科分类图,AHP决策方法 等,都可用树来表示.树的特点:1.树是边数最多的无圈连通图,即在 树上再任意增加一条边,必定出现圈;2.树的任意两点间,有一条且仅有一 条通路.也可以说,树是最脆弱的连通图,只要 在树中去掉任一条边,图就不连通了.图的最小部分树(最小生成树):设 是一个图,如 果 是 的支撑子图(部分图),且 是一个树, 则称 是 的部分树.树的各条边称为树枝.在 图的每条边上赋予权值的图称为赋权图. 在 中一般含有许多部分树,其中树枝总长为 最小的部分树,称为该图的最小部分树.部分树部分树图最小部分树的求法 方法一:避圈法例2 如图S,A,B,C,D,E,T代表村镇,村镇之

8、间的 连线上赋予了权值(可代表距离,费用,流量等) 现沿图中连线架设电线,使各村镇全部通电, 问如何架设使电线总长最短.(该图称为赋权 图或无向网络).最小生成树总长=2+2+1+3+1+5=14方法二:破圈法在无向网络图N中任取一个回路,去掉这个回路 中权数最大的边,得一新网络 ,在 中再任 取一回路,去掉这个回路中权数最大的边,得 . 如此继续下去,直到剩下的子图中不再含回路 为止,最后的这个子图为N的最小部分树.电线总长=2+2+1+3+1+5=14第三节 最短路(Shortest path)问题最短路问题是指在给定的网络(有向图和无向图) 中,找出任意两点间距离最短的一条路,这里的距

9、离是权值的代表.最短路问题可应用于选址,管道 铺设时的选线,设备更新,投资等方面. 本节介绍从某一点到其他各点之间最短距离的 Dijkstra算法和网络图上任意两点的最短距离的 矩阵算法.一.无向图最短路的Dijkstra算法(1959)基本思想:最短路的子路一定还是最短路.Dijkstra标号法的步骤:02447813例3 用狄克斯屈拉标号法求S到T的最短路.在用WIQSB 时，编号要按从左到右的顺序 。例4 设备更新问题 某企业使用一台设备,在每年年初企业领导决 定是购置新的还是继续使用旧的.其购置费和 维修费如下表.制定一个五年内的设备更新计 划,使总费用最少.年份第一 年第二 年第三

10、年第四 年第五 年 购置 费11 11 12 12 13使用年数0-1 1-2 2-3 3-4 4-5维修费 用5 6 8 11 18解:用点 表示”第i年年初购进一台新设备” 这种状态,增设一点 表示第五年年底.从 到 各画一条弧 i=1,2,3,4,5.弧 表示 在第i年年初购进的设备一直使用到第j-1年 年底或第j年年初.每条弧的权值可根据表中 的数据算出.用标号法算出从 到 的一条最短路:两个最优方案分别是: 第一方案:第一,三年各买一台新设备,总费用 为53(万元); 第二方案:第一,四年各买一台新设备,总费用 为53(万元).二.有向图的最短路问题例5 求 到各点的最短路.解:1.

11、先给顶点 标号(0,0),第一个数字表示 从起点到该点的长度(权值),第二个数字表示 该点的标号是从哪个相邻的顶点得到的,一般 地表为 ;例5 求 到各点的最短路.计算过程:三.求网络各点间最短距离的矩阵算法例6 求下面网络中各点间的最短距离.定义: 为图中相邻两点间的距离,若i和j不相 邻时 从i到j的路不一定是从i直接到j,它可以是从i出发经过 许多中间点到达j.如从S到B,如果只考虑经过一个中间 点时,则其最短距离是下列诸距离中的最小值,即 一般可写为 于是构造 一个新矩阵例如: 就是S到T的最短距离,与前边 计算结果相同.例7 如果例6中的七个点表示七个村镇,他们 要联合办一所小学,各

12、村小学生人数分别是 S-30,A-40,B-20,C-15,D-35,E-25,T-50. 问小学建在哪一个村镇,使小学生上(下)学 走的总路程为最短. 解:将 中第一行各数字乘S村小学生人数,这 些数表示小学建在各村时,S村小学生所走的路 程,同理可得出下表SABCDET S A B C D E T0 80 80 60 280 175 65060 0 40 45 210 125 550120 80 0 15 140 75 450120 120 20 0 175 100 500240 240 80 75 0 25 250210 200 60 60 35 0 300390 440 180 150

13、 175 150 0132 51030 880935910865* 1485小学应建在E村.第四节 网络的最大流(Maximal flow of network)流(Flow)就是将目标由一个地点运送到另一个 地点.如:公路中的交通流,控制系统中的信息流, 供水系统中的水流,金融系统中的现金流,邮政 系统中的信件流,等等.它们的共同问题是,希望 经过输送系统,将目标从一个地点运送到另一 个地点的运输量最大,或者将一定数量的目标 在该系统中从一个地点输送到另一个地点的费 用最小.这就是网络中的最大流问题和最小费 用最大流问题.一.网络最大流的概念 1.有向图和容量网络:有向图是指网络图中的连 线

14、是有规定方向的称为弧(arc),记为 它表 示弧的方向是从 有向图就是点与弧的集 合. 容量网络是指对网络上的每一条弧,都给出一个 最大的通过能力,称为该弧的容量,记为 或简记为 ,这样的网络称为容量网络. 在容量网络中规定一个发点(源点)s和一个收点( 汇点)t,其余的点称为中间点. 网络的最大流是指:网络中从发点到收点之间允 许通过的最大流量.我们只研究一个发点和一个收点的情况.对于 多个发点和多个收点的情况可将若干个发点 合并为一个新的发点对于收点也如此处理.2.流和可行流:流（flow）是指加在网络上的 一组负载.对加在弧 上的流,记为 或简记为 ,当 时称为零流.可行流（feasib

15、le flow）：在容量网络上满足下 列三个条件的一组流称为可行流 (1) 容量限制条件:对所有的弧有 (2) 中间点平衡条件:(3) 若以v(f)表示网络中从s到t的净输出量,则有任何容量网络上一定存在可行流,因为零流就 是可行流.定义:所谓求网络最大流,就是指在满足容量限 制条件和中间点平衡条件下,使v(f)值达到最大.二. 割和流量:在下图中,括弧外的数字表示最 大通过量,括弧內的数字为负载. 割(cut):将容量网络中的发点和收点分割开, 使s到t的流中断的一个弧集合.割的容量:割的弧集合中各弧的容量之和,用 表示,显然,割割的容量152117181924142515三.增广链（augmenting chain（path）: 如果在网络的发点和收点之间能找出一条链, 在这条链上所有的指向为st的弧(称为前向 弧,记为 ),存