数学建模案例分析-- 图与网络方法建模5最短投递路线的设计.doc_第1页
数学建模案例分析-- 图与网络方法建模5最短投递路线的设计.doc_第2页
数学建模案例分析-- 图与网络方法建模5最短投递路线的设计.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

5 最短投递路线的设计一、最优环游邮递员从邮局中取出邮件，递送到不同地点，然后再返回邮局。假设要求他至少一次走过他投递范围内的每一条街道，我们希望选择一条尽可能短的路线。在一个网络中，经过它的每条边的链称为欧拉链，经过中每一边至少一次的闭链称为的环游，经过中每一边恰好一次的环游称为欧拉环游。一个图能一笔画就是该图有欧拉环游。显然上述问题就是在具有非负权的网络中找出一条权最小的环游，这种环游称为最优环游。若有欧拉环游，则它的每一条欧拉环游具有相同的权，它也必然是最优环游。对有欧拉环游的网络，我们可以采用弗莱里（Fleury）算法求得的最优环游。弗莱里算法计算步骤如下：1、任意选取的一个顶点，置；2、假设链已选定，从中按下述方法选取：（1）和相关联；（2）尽量不选（是中去掉边而得到的图）的割边（即去掉此边后，图变为不连通），除非没有非割边可选择。3、设另一关联点为。若，重复步骤2；否则即为的一条欧拉环游。若网络没有欧拉环游，此时最优环游通过的某些边将超过一次。下面是一种有关引进重复边的算法。将边的两个端点再用一条权为的新边连接时，称为边的重复边。因此，问题可以重新叙述如下：给定一个具有非负权的网络，（1）用添重复边的方法求得的一个欧拉赋权母图，使得下式尽可能小；（2）求的欧拉环游。当点数较少时，可用奇偶点图上作业法求解，为此我们不加证明介绍下述两个结论。结论1网络有欧拉环游当且仅当中每一点的次为偶数。结论2最优环游具有这样的性质：（1）每条边至多重复一次；（2）每一圈上重复边的长度不超过该圈总长的一半。当某一圈上重复边的长度超过该圈总长的一半时，将该圈中的所有重复边去掉，该圈中未重复的边重复，从而得奇偶点图上作业法如下：（1）若每一点的次均为偶数，则用弗莱里算法求得其欧拉环游，此即为的最优环游。（2）若不然，则用添重复边的办法得到的欧拉赋权母图。求得的欧拉环游（用弗莱里算法）。（3）若某一条边在欧拉赋权母图中重复多次，只要去掉该边的偶数次重复边，总可以使得该边至多重复一次，这样的图仍为欧拉赋权母图。（4）然后逐一检查的每一个圈，当某一圈上重复边的长度超过该圈总长的一半时，将该圈中的所有重复边去掉，该圈中未重复的边重复，所得到的图也是欧拉赋权母图。二、应用举例 设某邮递员负责投递邮件的街道如图1（a）所示，求出该邮递员的最短投递路线。 1v2v3v5v6v8v7v9v12v13v2v5v6v8v7v9v11v12v13v2v3v5v6v8v7v9v11v13v1v4v10v1v4v10图1(a)图1(b)图1(c)457444224511252v11v3v12v10v14v4 该网络有8个奇点: 、，用添重复边的办法得图1(b)。按结论2进行调整,圈其总长为12,而重复边长为11,此时去掉重复边、 ,添加重复边。同样在圈中其总长为21，重复边长为12也超过一半。经调整后得到新的网络图1（c）。检
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论