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

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

1、论文题目：旅行推销员问题的几种解法院系：数学科学学院专业：应用数学姓名：王荣荣学号：02211044指导教师：郭爱萍完成时间：2005年5月16号旅行推销员问题的几种解法王荣荣（包头师范学院数学科学学院）摘要：通过提出“旅行推销员问题travelingsalesmanproblem”来介绍如何求解与生活息息相关的机床运行问题。最优哈密顿回路是“旅行推销员问题”的最优解，也是机床运行问题的最佳选择。关键词：旅行推销员问题，最优哈密顿回路，最优推销员回路。KEYWORD：travelingsalesmanproblem，optimumHamiltoncircuit，

2、optimumsalesmancircuit.中图分类号：O1一个旅行推销员在返回他所在的城市之前，他要访遍上司安排他去的所有城市。我们如何能找到一条路线，使推销员以最小的总路程（或时间，旅费）访遍这些城市，最后再回到他所在的城市。这就是著名的“旅行推销员问题”。这个问题可以用图论语言说的更广义一些，“旅行推销员问题“就是在给定的连通加权图（G，W）。其中G的顶点视为各个城市，城市间的航线视为边，权视为两个城市间的踞离，也可以视为时间或旅费。旅行推销员问题我们在实际工作中和理论研究中经常会遇到。在此我选取一个比较典型又实用的例子来求其最优哈密顿回路。例1:某一机

3、械车间，每一工件可以不按顺序地但必须走遍n台不同机床的每一台。记这n台不同机床为v1,v2…vn.然而，只要工件从机床vi到机床vj就需要调整时间tij。现在我要利用“旅行推销员问题“来确定每一工件走遍n台不同机床的最快路线。设连通加权无向图(G,W),即为本例的流程图。至少包含图G中每一个顶点的一次的回路称之为推销员回路（salesmancircuit），而包含图G中每一个顶点只有一次的回路称之为哈密顿回路（Hamiltoniancircuit），具有最小总长度的推销员回路称之为最优推销员回路（optimumsalesmancircuit），而且也是一般推销员

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

5、，z）+a（z，y）（对所有z不等于x，z不等于y）(1)那么哈密顿回路就是图G一般推销员问题的最优解(如果存在的话)。（参见《网络和图的最优化算》[美]E.米涅尔著李家滢赵关旗译）从定理我们可以看出，如果图G满足三角不等式，那么图G推销员问题的最优解就是图G一般推销员问题的最优解。但遗憾的是并不是所有的图都具有哈密顿回路。因此，我们应该确定所研究的图是否具有哈密顿回路。（更详尽的关于哈密顿回路存在条件的分析可以参阅伯奇（Berge）1973专著）。下面我采用一种数学建模中用过的方法来求解上面提出的关于机床运行的问题。设n=5，5个不同的机床间调整时间用矩阵D表

6、示如下：V1V2V3V4V5D=(tij)5*5=V1V2V3V4V5其中tij表示vi到vj的调整时间。上面的矩阵是对称的，即从vi到vj的调整时间等于从vj到vi的调整时间。（此方法也可用于非对称型矩阵）每行抽取最小的元素，并令矩阵D的每行的所有元素都减去该行的最小元素，得：32211D1=再用D1各列的所有元素减去该列的最小元素，得：10=3+2+2+1+1+1D2=重要的结论在于以D为调整时间矩阵问题的解和以D2为调整时间的解是一样的。每行的所有元素减去该行的最小元素，相当于从该行所对应的机床到其它不同机床的调整时间一律减少，减少的时间量是相同的。每列的

7、所有元素减去该列的最小元素，可看做是该列所对应的机床到其它不同机床的调整时间一律减少，而且减少的时间量是相同的。工件进入每个机床一次且仅一次，而且从该机床出去一次，也仅有一次。最佳路径仍是减少调整时间后的最佳路径。这就证明了我们的结论，反正进出都一次。下面讨论以D2为调整时间矩阵问题的解。D2的特点是每行每列都有零元素至少一个。例如：从v1出发必然选择v3作为下一站，因t13=0。在D2矩阵中划去t13元素所在的行和列，并将t13改为，这样是为了避免出现v1v3v1的现象，这不符合问题的要求。消去第一行及第三列的原因在于每点进出仅一次。10V2V3V4V5D3=

8、V1V2V4V5在矩阵D