图论与网络优化dzm.pptVIP

这个问题本质上是一个图论中的染色问题，但问题B 又与传统的染色问题不尽相同，它不仅限制了相邻的传送站的信道，并且还增加了对“隔开一点”的传送站的信道限制， 用经典染色理论的方法无法彻底解决。 图1. 六边形蜂窝系统 图2. 无限六正则格子图 定义：对简单图 ,设 , 若对任意两个顶点 ，有 则称 f 为 G 的一个 L(2,1)-标号或 L(2,1)-染色。 图的 L(2,1)- 标号： 更一般地，归结为图的 L(k1,k2, …, kp)-标号问题。 * * * * * * * * * * * * * * * * * * * * * * * * * * * 主讲：段滋明 网 络 优 化 图是一种直观形象的描述已知信息的方式，它使事物之间的关系简介明了，是分析问题的有用工具。用点表示研究对象，用点之间的连续表示对象之间的相互关系。 图论与网络分析是运筹学的一个分支，内容十分丰富，应用非常广泛。 一、图 v6 v7 v5 v4 v3 v2 v1 60 30 20 25 18 15 15 20 30 无向图 有向图 赋权图（网络） 完全图 K5 K3,3 二分图 二、几个著名问题 图论中著名问题. 1736年，图论的创始人Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答，发表了第一篇论文. 例：七桥问题 A B C D 问题：一个散步者能否走过七座桥，且每座桥只走 过一次，最后回到出发点。 例：四色猜想 能否用四种颜色给地图染色，使相邻的国家有不同的颜色。 点：国家； 边：两个国家有公共边界。 问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。 公元1852年，格里斯发现无论多么复杂的地图，只要用四种颜色就能将相邻的区域区分开来，这就是所谓“四色猜想”。 直到公元1976年，才由美国数学家同时操作三台超大型汁算机作了近200亿个逻辑判断，花费1200个机时，才取得了“四色猜想”的证明。 例：Hamilton图 哈密尔顿游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。 旅行商售货(TSP)问题： 在如上问题中，若已知任意两城市间的旅行费用，问如何安排旅行路线使总费用最少？ 例：中国邮路问题 一个邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。 点：路口； 边：两路口之间道路，第i条道路长ei。 1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。 问题：求一个圈，过每边至少一次，并使圈的长度最 短。 三、最短路问题 最短路问题是网络理论中应用最广泛的问题之一. 许多优化问题可以使用这个模型．如设备更新、管道铺设、线路安排、厂区布局等. 最短路问题：在一个赋权图G上，给定两个顶点u和 v，在所有连接顶点u和 v 的路中，寻找路长最短的路（称为u和 v最短路.） u和 v最短路的路长也称为u和 v的距离-d(u,v). 有些最短路问题也可以求网络中某指定点到其余所有结点的最短路、或求网络中任意两点间的最短路. 1、网络无负权的最短路 本算法由Dijkstra于1959年提出，可用于求解指定两点间的最短路，或从指定点到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。 ——Dijkstra算法 Ford算法基本思想：为逐次逼近的方法。每次求出从出发点v0到其余点的有限制的最短路，逐次放宽条件。最多迭代|V|-1次. 2、网络有负权的最短路 ——Ford算法 3、网络上任意两点间的最短路——Floyd算法 常用的几种解法 例1 设备更新问题. 某工厂使用一台设备，每年年初工厂都要作出决定．如果继续使用旧的，要付维路费；若购买一台新设备．要付购买费。试制定一个5年的更新计划，使总支出最少。 若已知设备在各年年初的价格为： 年度 第1年 第2年 第3年 第4年 第5年 购买费 11 11 12 12 13 还知使用不同年数的设备所需要的维修费用为： 使用年数 0-1 1-2 2-3 3-4 4-5 维修费用 5 6 8 11 18 可把这个问题化为最短路问题。 用点vi表示第i年年初购进一台新设备．虚设一个点v6 ,表示第五年年底。 弧(vi ,vj)表示第i年初购进的设备一直使用到第j年年初(即第j-1年年底). v1 v2 v3 v4 v5 v6 16 16 17 17 18 30