6旅行推销员问题的一种解法-王荣荣

《6旅行推销员问题的一种解法-王荣荣》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、论文题目：旅行推销员问题的一种解法院系：数学科学学院专业：应用数学姓名：王荣荣学号：02211044指导教师：郭爱平完成时间：2005年5月16号旅行推销员问题的一种解法王荣荣（包头师范学院数学科学学院）摘要：通过提出“旅行推销员问题travelingsalesmanproblem”来介绍如何求解与生活息息相关的机床运行问题。最优哈密顿回路是“旅行推销员问题”的最优解，也是机床运行问题的最佳选择。关键词：旅行推销员问题　最优哈密顿回路　最优推销员回路中图分类号：O1一个旅行推销员在返回他所在的城市之前，他要走遍上司安排他去的所有城市。我们如何能找到一条最佳路线，

2、使推销员以最小的总路程（或时间，旅费）走遍这些城市，最后再回到他所在的城市。这就是著名的“旅行推销员问题”。这个问题可以用图论语言说的更广义一些，“旅行推销员问题“就是连通加权图（G，W）。其中G的顶点视为各个城市，城市间的航线视为边，权视为两个城市间的距离，也可以看作是两座城市间航线上的飞机的飞行时间或机票钱。旅行推销员问题我们在实际工作中经常会遇到。在此我选取一个比较典型又实用的例子来求解它的最佳路线。例1:做为一个设计师，要在一机械车间设计一条最佳流程线，在此车间加工的每一工件可以不按顺序地但必须走遍n台不同机床。记这n台不同机床为v1,v2…vn，记工件

3、从机床vi到机床vj的调整时间为tij。现在我要利用“旅行推销员问题“的解法来求解每一工件走遍n台不同机床的最佳路线。设连通加权无向图(G,W),即为本例的示意图。至少包含图G中每一个顶点的一次的回路称之为推销员回路（salesmancircuit），而包含图G中每一个顶点只有一次的回路称之为哈密顿回路（Hamiltoniancircuit），具有最小总长度的推销员回路称之为最优推销员回路（optimumsalesmancircuit），而且也是一般推销员问题的最优解。具有最小总长度的哈密顿回路称之为最优哈密顿回路（optimumHamiltoniancircu

4、it），而且也是推销员问题的最优解。最优推销员回路不一定是最优哈密顿回路。例如：见下面所示的图。这个图的唯一的哈密顿回路是（a，b），（b，c），（c，a），总长度等于2+2+6=10。而通过顶点a点两次的最优推销员回路（b，a），（a，b），（b，c），（c，b）的总长度等于1+2+2+1=6。因此，最优推销员回路不一定是最优哈密顿。那什么情况下一般推销员问题的解才是哈密顿回路呢？定理1：如果图G中每一对x，y都存在a（x，y）≤a（x，z）+a（z，y）（对所有z不等于x，z不等于y）(1)那么哈密顿回路就是图G一般推销员问题的最优解(如果存在的话)。从定理

5、我们可以看出，如果图G满足三角不等式，那么图G推销员问题的最优解就是图G一般推销员问题的最优解。但遗憾的是并不是所有的图都具有哈密顿回路。因此，我们应该确定所研究的图是否具有哈密顿回路。（更详尽的关于哈密顿回路存在条件的分析可以参阅伯奇（Berge）1973专著）。下面我采用一种数学模型中用过的方法来求解上面提出的关于机床运行的问题。这个方法是我借用匈牙利法的思想,截取其中的前两步,并反复利用所得到的结果设n=6，6个不同的机床间调整时间用矩阵D表示如下：-1-2-1-3-4-3V1V2V3V4V5V6V1V2V3V4V5V6D=（tij）6*6=其中tij表示

6、机床vi到机床vj的调整时间。上面的矩阵是对称的，即从机床vi到机床vj的调整时间等于从机床vj到机床vi的调整时间。（此方法也可用于非对称型矩阵，即从机床vi到机床vj的调整时间不等于从机床vj到机床vi的调整时间。）很显然,图G中包含哈密顿圈和哈密顿回路,图G是哈密顿图(论证哈路的存在性)每行抽取最小的元素，并令矩阵D的每行的所有元素都减去该行的最小元素，得：16=1+2+1+3+4+3121343V1V2V3V4V5V6D1=V1V2V3V4V5V6再用D1各列的所有元素减去该列的最小元素，得：16=14+1+1121343V1V2V3V4V5V6D2=V

7、1V2V3V4V5V6下面论证为什么以D为调整时间矩阵的问题的解和以D2为调整时间矩阵的问题的解是一样的。每行的所有元素减去该行的最小元素，可以视为从该行所代表的机床到其它不同机床的调整时间统一减少，减少的时间量是相同的。每列的所有元素减去该列的最小元素，可看做是该列所代表的机床到其它不同机床的调整时间统一减少，而且减少的时间量也是相同的。每个工件进入任一个机床以后出去就完成了这道工序。所以,起初的最佳路径仍是统一减少调整时间后的最佳路径。这就证明了我们的结论。下面讨论以D2为调整时间矩阵问题的解。D2的每行每列都至少有一个零元素。因为t13=0，从机床v1出发

8、必然选择机床v3作为下一