本科毕业论文（设计）题目：中国邮递员问题综述学院统计与数理学院专业信息与计算科学班级2007级1班学号20070534119姓名指导教师王继强山东财政学院教务处制-0一一年五月中国邮递员问题综述高坤摘要：木文综合论述了运筹学中的中国邮递员问题，首先简介了该问题的起源，然后建立起该问题的图论模型，旨在使邮递员的投递线路最短，给出了算法和步骤，再借助lingo软件进行了实证分析•中国邮递---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---员问题的研究在网上交易和电子商务快速发展的今天尤其具有重要的现实意义.关键词：投递一笔画欧拉回路最短路Lingo—、引言图论是应用十分广泛的运筹学分支，它已广泛的应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域•在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决.例如，在组织生产小，为完成某项任务，各工学之间怎么样衔接，才能使生产任务完成的又快又好.一个邮递员送信，要走完他负责投递的所有街道，完成任务后回到邮局，应该按照怎么样的路线走，才能使得走的路线最短.中国投递员问题是I960年我们从生产实际中提出的一个数学问题，它是从下述实际问题中抽象出来的：“一个投递员应该怎么选择一条线路，才能既把所有由他负责的信件都送到，而所走的路程又最短”.在我们开始研究中国投递员问题以前，国外有人研究过所谓旅行售货员的问题，即「一个售货员要到n个城市去售货，问他应该选择怎样的一条线路，才能既走遍所有城市，并且走的路程最短”.这是一个著名的难题.肖n较大时，即使使用大型电子计算机，也很难解决.投递员面临的问题显然可以归纳为旅行售货员问题，事实上，只要把投递员必须送的每一个地点看成是一个城市就行了•但是一-般来说，投递员每次要到约二、三百个地点送信,如果归纳为旅行售货员问题来解决，将是一个规模很大的问题，是无法解决的•但是，在仔细分析了投递员面临的问题后，我们发现这个问题具有一定的特点，即需要送信的地点一般都是比较密集的排列在街道上的，因此，实际上，我们称这个问题为“最短投递线路问题”，1965年后国外称之为“中国投递员问题”・二、概念与原理一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局.如果他必须至少一次走过他管辖范围内的每一•条街道，如何选择投递路线，使邮递员走尽可能少的路程.这个问题是由我国数学家管梅谷先生(山东师范大学数学系教授)在1962年首次提岀的，因此在国际丄称之为中国邮递员问题.用图论的述语，在一个连通的赋权图G(U,E)中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的权数最小.也就是说要从包含G的每条边的冋路中找一条权数最小的回路.在实际生活中，人们为了反映一些对彖之间的关系，常常会在纸上用点和线画岀各种各样的示意图.例如：8世纪时，欧洲有一个风景秀丽的小城哥尼斯堡，那里有七座桥.如图1所示：河中的小岛A与河的左岸〃、右岸C各有两座桥相连结，河中两支流间的陆地D与4、B、C各有一座桥相连结•问：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？这个例子是历史丄非常有名的哥尼斯堡7桥问题•哥尼斯堡现在是立陶宛共和国的一个城市，图1是当地奈发夫岛附近的地域图，此例子就是当地人民小间流传久远的一个难题.直到1736年，数学家欧拉首次系统研究并完全解决了这类问题.---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---r>七桥问题引起了著名数学家欧拉(1707—1783)的关注•他把具体七桥布局化归为图2所示的简单图形，于是，七桥问题就变成一个一•笔划问题：怎样才能从A、B、C、D中的某一点出发，一笔划出这个简单图形(即笔不离开纸，而且b、c、d、£、f、g各条线只画一次不准重复)，并且最后返冋起点？一笔划出的图形中的各点或者都是与偶数条线相连的点，或者其中只有两个点与奇数条线相连.欧拉定理：如果一个网络是连通的并且奇顶点的个数等于0或2,那么它可以一•笔划出,否则它不可以一笔划岀.定义经过G的每条边的迹叫做G的Euler迹；闭的...