图论与网络优化dzm.ppt
《图论与网络优化dzm.ppt》由会员分享,可在线阅读,更多相关《图论与网络优化dzm.ppt(32页珍藏版)》请在三一办公上搜索。
1、主讲:段滋明,2012暑期数学建模,网 络 优 化,图是一种直观形象的描述已知信息的方式,它使事物之间的关系简介明了,是分析问题的有用工具。用点表示研究对象,用点之间的连续表示对象之间的相互关系。图论与网络分析是运筹学的一个分支,内容十分丰富,应用非常广泛。,一、图,无向图有向图,赋权图(网络),完全图,K5,K3,3,二分图,二、几个著名问题,图论中著名问题.1736年,图论的创始人Euler巧妙地将此问题化为图的不重复一笔画问题,并证明了该问题不存在肯定回答,发表了第一篇论文.,例:七桥问题,问题:一个散步者能否走过七座桥,且每座桥只走 过一次,最后回到出发点。,例:四色猜想,能否用四种颜
2、色给地图染色,使相邻的国家有不同的颜色。,点:国家;边:两个国家有公共边界。,问题:能否用四种颜色给平面图的点染色,使有公共边的点有不同的颜色。,公元1852年,格里斯发现无论多么复杂的地图,只要用四种颜色就能将相邻的区域区分开来,这就是所谓“四色猜想”。直到公元1976年,才由美国数学家同时操作三台超大型汁算机作了近200亿个逻辑判断,花费1200个机时,才取得了“四色猜想”的证明。,例:Hamilton图,哈密尔顿游戏:用正十二面体上20个顶点表示20个城市,要求参加游戏者沿着各边行走,走遍每一个城市且仅走一次,最后回到出发城市。,旅行商售货(TSP)问题:在如上问题中,若已知任意两城市间
3、的旅行费用,问如何安排旅行路线使总费用最少?,例:中国邮路问题,一个邮递员送信,要走完他所负责的全部街道分送信件,最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。,点:路口;边:两路口之间道路,第i条道路长ei。,1962年,由我国数学家管梅谷提出,国际上称为中国邮递员问题。问题:求一个圈,过每边至少一次,并使圈的长度最 短。,三、最短路问题,最短路问题是网络理论中应用最广泛的问题之一.许多优化问题可以使用这个模型如设备更新、管道铺设、线路安排、厂区布局等.,最短路问题:在一个赋权图G上,给定两个顶点u和 v,在所有连接顶点u和 v 的路中,寻找路长最短的路(称为u
4、和 v最短路.)u和 v最短路的路长也称为u和 v的距离-d(u,v).,有些最短路问题也可以求网络中某指定点到其余所有结点的最短路、或求网络中任意两点间的最短路.,1、网络无负权的最短路,本算法由Dijkstra于1959年提出,可用于求解指定两点间的最短路,或从指定点到其余各点的最短路,目前被认为是求无负权网络最短路问题的最好方法。,Dijkstra算法,Ford算法基本思想:为逐次逼近的方法。每次求出从出发点v0到其余点的有限制的最短路,逐次放宽条件。最多迭代|V|-1次.,2、网络有负权的最短路,Ford算法,3、网络上任意两点间的最短路Floyd算法,常用的几种解法,例1 设备更新问
5、题.,某工厂使用一台设备,每年年初工厂都要作出决定如果继续使用旧的,要付维路费;若购买一台新设备要付购买费。试制定一个5年的更新计划,使总支出最少。,若已知设备在各年年初的价格为:,还知使用不同年数的设备所需要的维修费用为:,可把这个问题化为最短路问题。,用点vi表示第i年年初购进一台新设备虚设一个点v6,表示第五年年底。弧(vi,vj)表示第i年初购进的设备一直使用到第j年年初(即第j-1年年底).,这样设备更新问题就变为:求从v到v6 的最短路。求解得:v1,v3,v6 及 v1,v4,v6 均为最短路。总的支付费用均为53。,已知某地区的交通网络如图所示,其中点代表居民小区,便表示公路,
6、wij为小区间公路距离问区中心医院应建在哪个小区,可使离医院最远的小区居民就诊时所走的路程最近?,例2 选址问题.,解:实际要求出图的中心,可以化为一系列求最短路问题。先求出v1到其它各点的最短路长dj,令D(v1)max(d1,d2,d7)表示若医院建在v1,则离医院最远的小区距离为D(v1)。再依次计算v2,v3,v7 到其余各点的最短路,类似求出D(v2),D(v3),D(v7)。D(vi)中最小者即为所求,计算结果见下表。,由于D(v6)48 最小,所以医院应建在v6,此时离医院最远的小区(v5)距离为48.,树(tree)是一个不包含圈的简单连通图。n个顶点的树有n-1条边。树中度为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络 优化 dzm
链接地址:https://www.31ppt.com/p-6257978.html