下载文档原格式
目录前言 (1)第一章中国邮递员问题的整数规划模型 (2)1.1 图论中模型 (2)1.2 中国邮递员问题的整数规划模型[5] (6)1.2.1 传统中国邮递员问题的建模 (6)1.2.2 广义中国邮递员问题及其建模 (7)1.2.3随机中国邮递员问题及其建模[7] (11)第二章中国邮递员问题的DNA计算 (14)2.1 DNA计算模型 (14)2.2 中国邮递员问题的图论模型变换 (15)2.3中国邮递员问题的DNA算法[11] (16)2.4 总结 (19)第三章中国邮路问题的数学模型 (20)3.1 问题的重述 (20)3.2 需解决的问题 (21)3.3 问题假设 (21)3.4 符号说明 (22)3.5 问题一的建模与求解 (23)（一）模型的分析与建立 (24)3.6 模型的求解 (27)结语 (30)致谢 (31)参考文献 (32)前言图论是一个新的数学分支，也是一门很有实用价值的学科，它在自然科学，社会科学等各领域均有很多应用。
近年来，计算机技术在图论中的应用使得图论得到飞速的发展，应用范围也不断拓广，已渗透到诸如语言学，逻辑学，物理学，化学，电讯工程，计算机科学以及数学的其它分支中。
特别在计算机科学中，如形式语言，数据结构，分布式系统，操作系统等方面均扮演着重要的角色。
最早的图论问题要追溯到1736年的哥尼斯堡七桥问题，而且在19世纪关于图论的许多重要结论都已相继提出。
但是直到20世纪20年代图论才引起广大学者的注意并得以广泛接受和传播。
其实现实生活中的许多问题都是可以通过图论中的相关知识得以解决的，这些例子俯拾即是。
例如，住在城市里的人出行的街道, 抽象出来就是由顶点(结点)和边(线) 构成的图, 在这个图上, 清洁工人必须把这个城市的所有街道清扫一遍，也就是走完所有的边，于是, 清洁工人马上遇到一个十分重要的图论问题: 怎样扫才能一条不落地把所有街道扫上一遍，而且使得所走的总路程最短，这就是典型的欧拉回路问题。
邮递员问题最短路径的解法邮递员问题，又称旅行商问题（Traveling Salesman Problem，TSP），是一个著名的组合优化问题。
它要求找到一条路径，使得邮递员从出发点出发，经过所有的城市且仅经过一次，最后回到出发点，同时路径长度最短。
由于邮递员问题是NP-hard问题，没有多项式时间的解法。
然而，存在一些启发式和近似算法可以在可接受的时间内找到较好的解决方案：1. 蛮力法：尝试所有可能的路径组合，计算每条路径的长度，最终选择最短路径作为解。
这种方法的时间复杂度为O(n!)，适用于较小规模的问题。
2. 最近邻算法：从一个起始点开始，每次选择离当前点最近的未访问过的城市作为下一个访问点，直到所有城市都被访问过，然后回到起始点。
该算法的时间复杂度为O(n^2)，虽然不能保证找到最优解，但是可以在较短的时间内找到较好的解。
3. 2-opt算法：先使用最近邻算法得到一个初始解，然后对路径进行优化。
2-opt算法通过不断交换路径中的两个边来减小路径的长度，直到没有可改进的交换。
该算法可以较快地优化路径，但无法保证找到全局最优解。
4. 遗传算法：使用进化计算的思想来解决TSP问题。
通过生成初始种群，交叉、变异等操作进行迭代优化，逐渐找到更好的路径。
遗传算法可以在较短时间内找到较好的解，但是无法保证找到最优解。
上述算法只是解决TSP问题的一部分方法，具体使用哪种方法取决于问题规模和时间要求。
对于较小规模的问题，可以使用蛮力法或者最近邻算法得到较好的解。
对于更大规模的问题，可以考虑使用启发式算法，如遗传算法等。
此外，还存在其他算法和优化技术用于处理TSP问题，根据具体情况选择合适的方法。
§4.中国邮递员问题（Chinese Postman Problem）1．问题的提出例5. 一个邮递员从邮局出发投递信件, 然后再返回邮局, 如果他必须至少一次地走过他负责投递范围内的每条街道, 街道路线如下图所示, 问选择怎样的路线才能使所走的路为最短?5 6 78问题的图论表述：在赋权G=[V, E]上找一条经每条边至少一次的权最小的圈。
1960年山东师范学院管梅谷教授首先提出此问题，并设计了一个“奇偶点表上作业法”，后来发现此法不是多项式算法，1973年，Edmonds和Johnson给出一个多项式算法。
2．哥尼斯堡七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如下图所示。
城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。
3．Euler圈Euler圈：经图G的每条边的简单圈Euler图：具有Euler圈的图Euler图非Euler图下面讨论的图G允许有重边，且重边被认为是有区别的边。
伪Euler 圈：经图G 的每条边至少一次的圈点v 的次：与点V 关联的边的数目奇(偶)点：该点的次为奇(偶)数命题1：G 的奇点个数为偶数命题2：G 中有伪Euler 圈 ⇔ G 无奇点中国邮递员问题可表述为：在图G 中找一条权最小的伪Euler 圈。
对于邮递员来说，有些街道可能会重复走，原问题便转化为尽可能少走重复的 街道。
我们将这些重复的边组成的集合称可行集，即找最小的可行集。
命题3：E *是最小可行集 ⇔ωωμμμ()()()()*()*()e e e E E E e E E ≤∑∑∀μ∈∩∈∩\初等圈重复的边 非重复的边4．算法思路由命题1，简单图G 的奇点个数为偶数，可设为v 1 , v 2 , …, v 2k , 对每个1≤ i ≤k, 找v 2i − 1 至v 2i 的链p i ，将p i 的边重复一次。
中国邮递员问题第一篇：中国邮递员问题运筹学第六组运筹学个人心得之中国邮递员问题我们第六组做的第二次案例就是中国邮递员问题，这个问题是运筹学中的经典命题。
这个案例讲的是：在中国的六个县城，每个县城都有一个县局，县局下面设立若干个邮政所，每天邮递员的任务就是从县局出发，依次到每一个邮政所送邮件，要求每个邮政所都必须去，而且只能去一次。
这就涉及到一个路线的规划问题，怎么走才能使得邮递员走的路最少，而且能够完成任务。
在做题之前考虑了很久，真不知道从何着手，国为以前确实没有接触过这个类型的题，没有一个能够行得通的办法。
后来，我们选定了一个代表性的区域，来尝试求解，国为第六个区域的变量最多，所以就选择这个区域作为突破口。
只要第六个区域求解成功，其它五个区域便迎刃而解了。
首先，我们画了一个由第六区域的十七个点所组成的17*17矩阵，一一对应设定变量，在去除对角线的17个变量之后，我们得到272个变量。
这是一个非常庞大的变量群体，若按传统的线性规划方法求解，求解过程将会变得异常艰辛，而且以前的模板，求解工具都不能求解这么多变量。
所以我们一度陷入混乱，求解工作停滞不前。
后来老师在对这价目案例作初步的讲解的时候，提出了用运输模型来对这个问题进行求解，此话一出，真是如醍醐灌顶，酣畅极了，眼前简直豁然一亮，真想“拍案而起”。
若用运输模型求解，这个问题将会变得非常简单。
一方面由于每行的出发点只能有一个，而每列的终点也只能有一个，这样看来，邮运筹学第六组递员总是变成了一个产销平衡的运输问题，产量和销量都有是1。
这样我们就完成了求解工作，在第一次求解得出结论后，我们画了一个路线图，发现有几个两点循环，没有形成一条大通路，于是我们重新加入了两点循环约束，进行二次求解；在第二次求解完成后，我们又重新画了路线图，结果发现有四点循环于是我们又加入四点循环约束，进行第三次求解，在得到第三次求解的结果后，我们又画出了路线图，这次刚好形成了一个完整的通路，保证了邮递员每点都走到且行走的路线最合理。
