最佳灾情巡视路线.doc
约17页DOC格式手机打开展开
最佳灾情巡视路线,页数 17 字数7672摘要：（建议最后写很多需要改）本题是一类图上点的行遍性问题，也就是要用若干条闭链覆盖图上所有的顶点（本题为乡村所在地），并使得某些指标达到最优（本题为使路程最近，耗时最短，各小组尽量均衡），也就是在图论和组合最优化中分别称为哈密尔顿问题和旅行商问题。针对此：本文首先利用两点间的最...
内容介绍
此文档由会员 天缘 发布
最佳灾情巡视路线
页数 17 字数 7672
摘要：（建议最后写很多需要改）本题是一类图上点的行遍性问题，也就是要用若干条闭链覆盖图上所有的顶点（本题为乡村所在地），并使得某些指标达到最优（本题为使路程最近，耗时最短，各小组尽量均衡），也就是在图论和组合最优化中分别称为哈密尔顿问题和旅行商问题。针对此：本文首先利用两点间的最短路长度作为该两点边的权构造了一个完全图，然后根据完全图形状和各顶点分布，将完全图分为三个区域。接着，本文给出了对各个区域分别运用解哈密尔顿圈的局部回路搜索法（3-代换法）和逐次改进法求解最短路径的方法。为给出均衡的多路巡视路线，先将图分划为均衡的多个子图，再在各个子图中分别求最优解，从而得到整体的均衡最优解。
第三问我们首先使用Dijkstra单源最短路径算法求出O中各点到O最短路径。然后用近似解法得出分组的最佳情况。
在模型的进一步分析中，考虑到模型的针对性太强，我们给出了运用最小生成树的新的求解方法从而能使模型普遍适应各种不同情况的灾情巡视问题。
根据偏差程度的大小来衡量巡视路线的均衡性, 最后得到了均衡性较好的分组路线。在所给条件下, 找出完成巡视的最短时间为6. 43 小时, 在这个时间限制下, 采用较为合理的分组方法, 找出22 个组。最后, 讨论了在组数一定的情况下, 将T、t 视为时间因素X ,V 视为速度因素Y , 分析X 、Y 变化对最佳巡视路线的影响。
关键字：
哈密尔顿问题和旅行商问题,完全图,最短路,局部回路搜索法（3-代换法）,最邻近算法,逐次修正法,最小生成树
参考书籍：
（1） 杜端甫，运筹图论（图、网络理论中的运筹问题）北京航空航天大学 1990
（2） 肖位枢 图论及其算法 航空工业出版社 1993
（3） 赵静，但琦.数学建模与数学实验（第二版）.[M]北京：高等教育出版社
页数 17 字数 7672
摘要：（建议最后写很多需要改）本题是一类图上点的行遍性问题，也就是要用若干条闭链覆盖图上所有的顶点（本题为乡村所在地），并使得某些指标达到最优（本题为使路程最近，耗时最短，各小组尽量均衡），也就是在图论和组合最优化中分别称为哈密尔顿问题和旅行商问题。针对此：本文首先利用两点间的最短路长度作为该两点边的权构造了一个完全图，然后根据完全图形状和各顶点分布，将完全图分为三个区域。接着，本文给出了对各个区域分别运用解哈密尔顿圈的局部回路搜索法（3-代换法）和逐次改进法求解最短路径的方法。为给出均衡的多路巡视路线，先将图分划为均衡的多个子图，再在各个子图中分别求最优解，从而得到整体的均衡最优解。
第三问我们首先使用Dijkstra单源最短路径算法求出O中各点到O最短路径。然后用近似解法得出分组的最佳情况。
在模型的进一步分析中，考虑到模型的针对性太强，我们给出了运用最小生成树的新的求解方法从而能使模型普遍适应各种不同情况的灾情巡视问题。
根据偏差程度的大小来衡量巡视路线的均衡性, 最后得到了均衡性较好的分组路线。在所给条件下, 找出完成巡视的最短时间为6. 43 小时, 在这个时间限制下, 采用较为合理的分组方法, 找出22 个组。最后, 讨论了在组数一定的情况下, 将T、t 视为时间因素X ,V 视为速度因素Y , 分析X 、Y 变化对最佳巡视路线的影响。
关键字：
哈密尔顿问题和旅行商问题,完全图,最短路,局部回路搜索法（3-代换法）,最邻近算法,逐次修正法,最小生成树
参考书籍：
（1） 杜端甫，运筹图论（图、网络理论中的运筹问题）北京航空航天大学 1990
（2） 肖位枢 图论及其算法 航空工业出版社 1993
（3） 赵静，但琦.数学建模与数学实验（第二版）.[M]北京：高等教育出版社
