• / 52
  • 下载费用:16 金币  

运筹学11-图和网络

关 键 词:
运筹学11-图与网络 运筹学图与网络
资源描述:
第十一章 图与网络规划 Graph Theory and Network Analysis 11.1 图与网络的基本概念 11.2 最短路问题 11.3 网络最大流问题 11.4 最小费用最大流问题 内容简介 n是近几十年来运筹学领域中发展迅速、而 且十分活跃的一个分支. n对实际问题的描述具有直观性 n广泛应用于物理学、化学、信息论、控制 论、计算机科学、社会科学以及现代经济 管理科学等许多科学领域. n图与网络分析的内容十分丰富.本章只介 绍图与网络的基本概念以及图论在路径问 题、网络流问题等领域中的应用.重点讲 明方法的物理概念、基本原理及计算步骤 . 11.1 图与网络的基本概念 n图的理论研究已有200多年的历史了.早 期图论与“数学游戏”有着密切关系.所谓“ 哥尼斯堡七桥”问题就是其中之一. 200多年前的东普鲁士有一座 哥尼斯堡城,城中有一条河叫 普雷格尔河,河中有两个岛屿 共建七座桥.平时城中居民大 都喜欢来这里散步,并提出这 样一个问题:一个散步者能否 经过每座桥恰恰一次再回到原 出发点. 11.1 图与网络的基本概念 n当时有许多人都探讨了这个问题,但不得其解 . n著名数学家欧拉(Euler)将这个问题简化为一 个如右图所示图形.图4个点A、B、C、D表示 两岸和小岛.两两点间连线表示桥. 11.1 图与网络的基本概念 n于是问题转化为一笔画问题,即能否从某一点 开始一笔画出这个图形,不许重复,最后回到 原出发点. n欧拉否定了这种可能性. n原因是图中与每一个点相关联的线都是奇数条 . n为此他写下了被公认为世界第一篇有关图论方 面的论文(1736年) 11.1 图与网络的基本概念 n1859年哈密尔顿提出 了另一种游戏:在一 个实心的12面体(见 图)的20个顶点上标 以世界上著名的城市 名称,要求游戏者从 某一城市出发,遍历 各城市恰恰一次而返 回原地,这就是所谓“ 绕行世界问题”. 11.1 图与网络的基本概念 n作图,此问题变成在从某 一点出发寻找一条路径, 过所有20个点仅仅一次, 再回到出发点. n解决这个问题可以按序号 1—2—3—4一…一20—1 所形成的一个闭合路径, 并称此路径为哈密尔顿圈 . n具有哈密尔顿圈的图称为 哈密尔顿图. 11.1 图与网络的基本概念 n由此可见,图论中所研究的图是由实际问题抽 象出来的逻辑关系图. n这种图与几何中的图形和函数论中所研究的图 形是不相同的. n这种图的画法具有一定的随意性,在保持相对 位置和相互关系不变的前提下,点的位置不一 定要按实际要求画,线的长度也不一定表示实 际的长度.而且画成直线或曲线都可以. n通俗地说,这种图是一种关系示意图. 11.1 图与网络的基本概念 n图的概念 n所谓图,就是顶点和边的集合,点的集合记为V ,边的集合记为E,则图可以表示为:G=(V,E ),点代表被研究的事物,边代表事物之间的联 系,因此,边不能离开点而独立存在,每条边都 有两个端点。 n在画图时,顶点的位置、边和长短形状都是无关 紧要的,只要两个图的顶点及边是对应相同的, 则两个图相同。 图的表示 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 点与边 n顶点数 集合V中元素的个数, 记作p(G)。 n边数 集合E中元素的个数,记 作q(G)。 n若e=[u,v]∈E,则称u和v为e的 端点,而称e为u和v的关联边 ,也称u,v与边e相关联。 n例如图中的图G,p(G)=6, q(G)=9, nv1,v2是e1和e2的端点,e1和e2 都是v1和v2的关联边。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 点边关系 n若点u和v与同一条边 相关联,则u和v为相 邻点;若两条边ei和ej 有同一个端点,则称ei 与ej为相邻边。 n例如在图中v1和v2为相 邻点, v1和v5不相邻; e1与e5为相邻边,e1和 e7不相邻。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 简单图 n若一条边的两个端点是同一 个顶点,则称该边为环;又 若两上端点之间有多于一条 边,则称为多重边或平行边 。 n例如图的e8为环,e1,e2为 两重边,e4,e5也是两重边 。 n含有多重边的图称作多重图 。 n无环也无多重边的图称作简 单图。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 图的次 n次 点v作为边的端点的 次数,记作d(v),如图中 ,d(v1)=5, d(v4)=6等 n端点次为奇数的点称作 奇点;次为偶数的点称 作偶点。 n次为1的点称为悬挂点, 与悬挂点连接的边称作 悬挂边; n次为0的点称为孤立点。 n图中的点v5即为悬挂点, 边e9即为悬挂边,而点v6 则是弧立点。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 定理 n若图G中所有点都是孤 立点,则称图G为空图 。 n定理1 所有顶点的次 的和,等于所有边数 的2倍。即 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 n定理2 在任一图中, 奇点的个数必为偶数 。 n设V1和V2分别是图G 中次数为奇数和偶数 的顶点集合。由定理 1有 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 链 n由两两相邻的点及 其相关联的边构成 的点边序列称为链 。 nv0称为链的起点, vn称为链的终点。 n若v0 ≠vn则称该链 为开链,反之称为 闭链或回路。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 简单链 n若链中所含的边均不 相同,则称为简单链 ;若点均不相同,则 称为初等链或通路。 n除起点和终点外点均 不相同的闭链,称为 初等回路或称为圈。 n例如图中 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 是一条链,且是开链,也是简单链,但不是初等链,因 为v1出现两次。 圈 n若链中所含的边均 不相同,则称为简 单链;若点均不相 同,则称为初等链 或通路。除起点和 终点外点均不相同 的闭链,称为初等 回路或称为圈。 n例如图中 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 是一个圈。 连通性 n若一个图G的任意两 点之间均至少有一条 通路(初等链)连接 起来,则称这个图G 是一个连通图,否则 称作不连通图。 n例如图中,v1和v6之 间没有通路,因此它 不是连通图,而如果 去掉v6,则构成一个 连通图。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 连通的意义 n连通是一个很重要的 概念,如果一个问题 所对应的图是一个不 连通图,则该问题一 定可以分解成互不相 关的子问题来加以研 究,即可以把不连通 图分解成连通的子图 来研究。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 子图 n子图的定义 设, G1=(V1,E1), G2=(V2,E2),如果 V1V2 ,又E1E2 , 则称G1是G2的子图。e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 e1 e2 e3 e4 e5 v2 v3 v1 必须指出,并不是从图 G2中任选一些顶点和边 在一起就组成G2的子图 G1,而只有在G2中的一 条边以及连接该边的两 个端点均选入G1时,G1 才是G2的子图。 特殊子图 n当G1中不包含G2中所 有的顶点和边,则称 G1是G2的真子图。 n部分图 若V1=V2, E1E2 ,则称G1为G2 的一个部分图。 n若V1V2 , nE1={ [u,v] | u∈V1, v∈V1},则称G1是G2中 由V1导出的导出子图。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 e1 e2 e3 e4 e5 v2 v3 v1 有向图 n在有些图中,边是没有方向的,即[u,v]=[v,u],这 种图称为无向图。 n而有些关系是不对称的,例如父子关系、上下级 关系、加工工序的先后顺序等都具有单向性,用 图来表示这些关系时,得到的边是具有方向的, 用带箭头的线来表示,称为弧。 n从顶点u指向υ的弧a,记作a=(u,v),(u,v)≠(v,u),其 中u称为a的起点,v称为a的终点,这样的图称为 有向图。仍以V表示点的集合,以A表示弧的集合 ,则有向图表示为D=(V,A) 有向图例 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 有向图的链路 n有向图中,在不考虑边的方向 时,也可以相同地定义链,若 有向图D=(V,A)中,P是 一个从u到v的链,且对P中每 一条弧而言,在序列中位于该 弧前面的点恰好是其起点,而 位于该弧后面的点恰好是其终 点,这个链P就称为是D中从u 到v的一条路。 n当路的起点与终点相同,即 u=v时,称作一条回路。 n顶点全不相同的路称为初等路 。 n除起点和终点外点均不相同的 回路称为初等回路。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 树及最小树问题 ■任何树至少有一个悬挂节点 2 4 3 51 2 4 3 51 2 4 3 51 ■如果树的节点个数为m,则 边的个数为m-1 ■树中任意两个节点之间只有 唯一的一条链 ■在树的任意两个不相邻的节 点之间增加一条边,则形成唯 一的圈 树及最小树问题 Ø 一个没有圈的图称为一个无圈图或称为林。 Ø 一个连通的无圈图则称为树,一个林的每个连通子图都 是一个树。 定理 以下关于树的六种不同描述是等价的: n 无圈连通图。 n 无圈,q=p-1。 n 连通,q=p-1。 n 无圈,但若任意增加一条边,则可得到一个且仅一个圈 。 n 连通,但若任意舍弃一条边,图便不连通。 n 每一对顶点之间有一条且仅有一条链。 网络概念 n 图只能用来研究事物之间有没有某种关系,而不能 研究这种关系的强弱程度。 n 网络 赋权的图 n 权 程度的度量,数量描述。 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 网络概念 n节点与(有向)边 每一条边和两个节点关联 ,一条边可以用两个节点 的标号表示(i,j) ji ■ 路径(Path) 前后相继并且方向相同的边序列 P={(1,2),(2,3),(3,4)} 4 2 3 1 4 2 3 1 ■ 网络由节点和边组成 网络概念 ■ 回路(Circuit) 起点和终点重合的路径称为回路 μ={(1,2),(2,4),(4,1)} 回路中各条边方向相同 4 2 3 1 ■ 链(Chain) 前后相继并且方向不一定相同的边 序列称为链 C={(1,2),(3,2),(3,4)} 4 2 3 1 网络概念 ■ 连通图 任意两个节点之间至少有一条 链的图称为连通图 2 4 3 51 ■ 圈(Cycle) 起点和终点重合的链称为圈 ρ ={(1,2),(2,4),(3,4),(1,3)} 圈中各条边方向不一定相同 4 2 3 1 ■ 树(Tree) 无圈的连通图称为树 树中只与一条边关联的节点称 为悬挂节点 网络概念 n平面图(planar graph),若在平面上可以画 出该图而没有任何边相交 n走过图中所有边且每条边仅走一次的闭行 走称为欧拉回路 n定理 :偶图一定存在欧拉回路(一笔画定理 ) n图中都是偶点的图称为偶图(even graph) 哈密尔顿回路( Hamiltonian circuit)问题 n连通图G(V,E)中的回路称为哈密尔顿回路,若该回路包 括图中所有的点。显然哈密尔顿回路有且只有 n 条边, 若|V|=n n连通图具有哈密尔顿回路的充分必要条件是什么?这个 问题是由爱尔兰数学家哈密尔顿1859年提出的,但至今 仍未解决 n欧拉回路是对边进行访问的问题,哈密尔顿回路是对点 进行访问的问题 n搜索哈密尔顿回路的难度是 NP-complete n任两点间都有边的图称为完全图(或全连接图) n完全图中有多少个不同的哈密尔顿回路? (n–1)!/2 n完全图中有多少个边不相交的哈密尔顿回路? (n–1)/2 n最小哈密尔顿回路问题 (NP-complete) n哈密尔顿路径:包含图中所有点的路径 n为什么说找两点间的最长路是非常困难的问题? 中国邮递员问题 n中国邮递员问题(Chinese Postman Problem, CPP)是 由我国管梅谷教授于1962年首先提出并发表的 n问题是从邮局出发,走遍邮区的所有街道至少一次再 回到邮局,走什么路由才能使总的路程最短? n如果街区图是一个偶图,根据定理 3,一定有欧拉回 路,CPP问题也就迎刃而解了 n若街区图不是偶图,则必然有一些街道要被重复走过 才能回到原出发点 n显然要在奇次点间加重复边 n如何使所加的边长度最少 n归结为求奇次点间的最小 匹配( minimum weighted match) — 由Edmons 给出多项式算法(1965) 旅行推销员问题(Traveling Salesman Problem) nTSP:设v1, v2, .,vn 为 n 个已知城市,城市之间 的旅程也是已知的,要求推销员从 v1出发,走遍所有 城市一次且仅一次又回到出发点,并使总旅程最短 n这种不允许点重复的旅行推销员问题就是最小哈密尔顿 回路问题 n一般旅行推销员问题(GTSP):允许点重复的TSP n典型的应用: n乡邮员的投递路线 n邮递员开邮箱取信的路线问题 n邮车到各支局的转趟问题 n运钞 n送奶、送水 n…. 网络最短树问题 n最短树问题的一般提法是:选取网络中的部分图, 使得网络连通,且使总权数最短。 n在实际应用中,经常碰到需要求一个赋权连通图的 最短树的问题。例如,用节点表示城市,用边表示 可以在两个城市之间架设光缆,边上的权表示光缆 的长度,试求应如何架设光缆,才能使任意两城市 之间均由光缆相通,且使光缆的总长度最短。 n求最短树的方法,依据的是树的特点,即无圈和连 通,加上最短的要求,方法主要有两种:一种称为 破圈法,一种称为避圈法 11.2 最短路问题 n最短路问题的一般提法是:欲寻找网络中从 起点υ1到终点υn的最短路线,即寻求连接 这两点的边的总长度为最小的通路,最短路 线中的网络大都是有向网络,也可以是无向 网络。 n最短路问题是网络分析中的一个基本问题, 它不仅可以直接应用于解决生产实际的许多 问题,如管道铺设、线路安排、厂区布局等 ,而且经常被作为一个基本工具,用于解决 其它的优化问题。 最短路问题的Dijkstra算法(双标号法) 步骤: 1.给出点V1以标号(0,s) 2.找出已标号的点的集合I,没标号的点的集合J以及弧的集合 3.如果上述弧的集合是空集,则计算结束。如果vt已标号( lt,kt),则 vs到vt的距离为lt,而从 vs到vt的最短路径,则 可以从kt反向追踪到起点vs 而得到。如果vt 未标号,则可以 断言不存在从 vs到vt的有向路。如果上述的弧的集合不是空 集,则转下一步。 4. 对上述弧的集合中的每一条弧,计算 sij=li+cij 。在所有 的 sij中,找到其值为最小的弧。不妨设此弧为(Vc,Vd), 则给此弧的终点以双标号(scd,c),返回步骤2。 n例1 求下图中v1到v6的最短路 n解:采用Dijkstra算法,可解得最短路径为v1 v3 v4 v6 n各点的标号图如下: v2 3 5 2 7 5 3 1 5 12 v1 v6 v5 v3 v4 (3,1) v2 3 5 2 7 5 3 1 5 12 V1 ( 0,s) v5 (8,4) v6 (2,1) v3 (3,3) v4 n例2 电信公司准备在甲、乙两地沿路架设一条光缆线,问如何架设使 其光缆线路最短?下图给出了甲乙两地间的交通图。权数表示两地间 公路的长度(单位:公里)。 n解:这是一个求无向图的最短路的问题。可以把无向图的每一边( vi,vj)都用方向相反的两条弧(vi,vj)和(vj,vi)代替,就化为有向 图,即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法 来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成 已标号的点到未标号的点的边的集合即可。 V1 (甲地) 15 17 6 2 4 4 4 3 10 6 5 v2 V7 (乙地) v3 v4 v5 v6 n例2最终解得: n最短路径v1 v3 v5 v6 v7,每点的标号见下图 (0,s) V1 (甲地) 15 17 6 2 4 4 3 10 6 5 (13,3 ) v2 (22,6) V7 (乙地) V5 (14,3) V6 (16,5) V3 (10,1) V4 (18,5) n例3 设备更新问题。某公司使用一台设备,在每年年初,公司就要决 定是购买新的设备还是继续使用旧设备。如果购置新设备,就要支付 一定的购置费,当然新设备的维修费用就低。如果继续使用旧设备, 可以省去购置费,但维修费用就高了。请设计一个五年之内的更新设 备的计划,使得五年内购置费用和维修费用总的支付费用最小。 n 已知:设备每年年初的价格表 n 设备维修费如下表 年份12345 年初价格1111121213 使用年数0-11-22-33-44-5 每年维维修 费费用 5681118 n例3的解:将问题转化为最短路问题,如下图: 用vi表示“第i年年初购进一台新设备”,弧(vi,vj)表示第i年年初购进的 设备一直使用到第j年年初。 n把所有弧的权数计算如下表: v1 v2v3v4v5v6 123456 11622304159 216223041 3172331 41723 518 6 (继上页) 把权数赋到图中,再用Dijkstra算法求最短路。 最终得到下图,可知,v1到v6的距离是53,最短路径有两条: v1 ---v3---v6和 v1---v4---v6 v1 v2v3v4v5v616 22 30 41 59 16 22 30 41 31 23 171817 23 V1 (0,s) v3v4 (41,1) v5 v6 22 30 41 59 16 (22,1) 30 41 31 23 171817 23 V2 (16,1 ) 16 (30,1 ) (53,3 ) (53,4 ) 11.4 网络最大流问题 Ø 所谓最大流问题就是在一定的条件下,要求流过网络 的物流、能量流或信息流等流量为最大的问题,在最 大流问题中一般有如下规定: 1) 网络有一个起点υs和一个终点υt 2) 网络是有向网络,即流有方向性。 3) 在网络各条弧上都有一个权,表示允许流过的最大流 量。若以bij表示由υi到υj的弧上允许流过的最大流量, 以xij表示实际流过该弧的流量,则0≤ xij ≤bij 4) 网络中,除起点υs和终点υt之外的任何顶点,流入量 总和应该等于流出量的总和。 一、最大流问题的数学模型 vs 10 11 6 5 4 7 3 9 15 vt v5 v3 v4 v2 二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向,如下图: (a)和 (b)、(c)和(d)的意义相同。 vi vj vi vj cij0 (a)(b) cij cij vi vj (cji) (c) vi vj cij cji (d) 求最大流的基本算法 (1)找出一条从发点到收点的路,在这条路上的每一条弧顺流方向的容 量都大于零。如果不存在这样的路,则已经求得最大流。 (2)找出这条路上各条弧的最小的顺流的容量pf,通过这条路增加网络 的流量pf。 (3)在这条路上,减少每一条弧的顺流容量pf ,同时增加这些弧的逆流 容量pf,返回步骤(1)。 例6 某石油公司拥有一个管道网络,使用这个网络可以把 石油从采地运送到一些销售点,这个网络的一部分如下图所 示。由于管道的直径的变化,它的各段管道(vi,vj)的流 量cij(容量)也是不一样的。cij的单位为万加仑/小时。如 果使用这个网络系统从采地 v1向销地 v7运送石油,问每小 时能运送多少加仑石油? 6 3 5 2 2 2 4 1 2 63 v1 v2 v7 v4 v3 v6 迭代运算步骤请见演示 11.5 最小费用最大流问题 n最小费用最大流问题:给了一个带收发点的网络,对每一条弧 (vi,vj),除了给出容量cij外,还给出了这条弧的单位流量的费用bij,要 求一个最大流F,并使得总运送费用最小。 一、最小费用最大流的数学模型 例7 由于输油管道的长短不一,所以在例6中每段管道( vi,vj )除 了有不同的流量限制cij外,还有不同的单位流量的费用bij ,cij的单位为万 加仑/小时, bij的单位为百元/万加仑。如图。从采地 v1向销地 v7运送石 油,怎样运送才能运送最多的石油并使得总的运送费用最小?求出最大流 量和最小费用。 (6,6) (3,4) (5,7) (2,5) (2,4) (2,3) (4,4) (1,3) (2,8) (3,2) v1 v2 v5 v7 v4 v3 v6 (6,3) 二、最小费用最大流的网络图论解法 对网络上弧(vi,vj)的(cij,bij)的表示作如下改动,用(b)来表示(a)。 vi vj vi vj (cij,bij ) (0,-bij ) (a)(b) (cij,bij ) (cij,bij ) vi vj (cji,bji ) (cij,bij ) vi vj (cji,bji ) (0,-bji) (0,-bji) (c)(d)
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:运筹学11-图和网络
链接地址:https://www.maidoc.com/p-15487376.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 


收起
展开