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

论文题目： 旅行推销员问题的一种解法 院 系： 数学科学学院 专 业： 应用数学 姓 名： 王荣荣 学 号： 02211044 指导教师： 郭爱平 完成时间： 2005年5月16号 旅行推销员问题的一种解法王荣荣（包头师范学院数学科学学院）摘要：通过提出“旅行推销员问题traveling salesman problem”来介绍如何求解与生活息息相关的机床运行问题。最优哈密顿回路是“旅行推销员问题”的最优解，也是机床运行问题的最佳选择。关键词：旅行推销员问题最优哈密顿回路最优推销员回路中图分类号：O1一个旅行推销员在返回他所在的城市之前，他要走遍上司安排他去的所有城市。我们如何能找到一条最佳路线，使推销员以最小的总路程（或时间，旅费）走遍这些城市，最后再回到他所在的城市。这就是著名的“旅行推销员问题”。这个问题可以用图论语言说的更广义一些，“旅行推销员问题“就是连通加权图（G，W）。其中G的顶点视为各个城市，城市间的航线视为边，权视为两个城市间的距离，也可以看作是两座城市间航线上的飞机的飞行时间或机票钱。 旅行推销员问题我们在实际工作中经常会遇到。在此我选取一个比较典型又实用的例子来求解它的最佳路线。例1:做为一个设计师，要在一机械车间设计一条最佳流程线，在此车间加工的每一工件可以不按顺序地但必须走遍n台不同机床。记这n台不同机床为v1,v2vn，记工件从机床vi到机床vj的调整时间为tij。现在我要利用“旅行推销员问题“的解法来求解每一工件走遍n台不同机床的最佳路线。设连通加权无向图(G,W),即为本例的示意图。至少包含图G中每一个顶点的一次的回路称之为推销员回路（salesman circuit），而包含图G中每一个顶点只有一次的回路称之为哈密顿回路（Hamiltonian circuit），具有最小总长度的推销员回路称之为最优推销员回路（optimum salesman circuit），而且也是一般推销员问题的最优解。具有最小总长度的哈密顿回路称之为最优哈密顿回路（optimum Hamiltonian circuit），而且也是推销员问题的最优解。最优推销员回路不一定是最优哈密顿回路。例如：见下面所示的图。这个图的唯一的哈密顿回路是（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一般推销员问题的最优解(如果存在的话)。从定理我们可以看出，如果图G满足三角不等式，那么图G推销员问题的最优解就是图G一般推销员问题的最优解。但遗憾的是并不是所有的图都具有哈密顿回路。因此，我们应该确定所研究的图是否具有哈密顿回路。（更详尽的关于哈密顿回路存在条件的分析可以参阅伯奇（Berge）1973专著）。下面我采用一种数学模型中用过的方法来求解上面提出的关于机床运行的问题。这个方法是我借用匈牙利法的思想,截取其中的前两步,并反复利用所得到的结果设n=6，6个不同的机床间调整时间用矩阵D表示如下：-1-2-1-3-4-3V1 V2 V3 V4 V5 V6V1V2V3V4V5V6D=（tij）6*6= 其中tij表示机床vi到机床vj的调整时间。上面的矩阵是对称的，即从机床vi到机床vj的调整时间等于从机床vj到机床vi的调整时间。（此方法也可用于非对称型矩阵，即从机床vi到机床vj的调整时间不等于从机床vj到机床vi的调整时间。）很显然,图G中包含哈密顿圈和哈密顿回路,图G是哈密顿图(论证哈路的存在性)每行抽取最小的元素，并令矩阵D的每行的所有元素都减去该行的最小元素，得：16=1+2+1+3+4+3121343V1V2V3V4V5V6D1= V1 V2 V3 V4 V5 V6再用D1各列的所有元素减去该列的最小元素，得：16=14+1+1121343V1V2V3V4V5V6D2= V1 V2 V3 V4 V5 V6下面论证为什么以D为调整时间矩阵的问题的解和以D2为调整时间矩阵的问题的解是一样的。每行的所有元素减去该行的最小元素，可以视为从该行所代表的机床到其它不同机床的调整时间统一减少，减少的时间量是相同的。每列的所有元素减去该列的最小元素，可看做是该列所代表的机床到其它不同机床的调整时间统一减少，而且减少的时间量也是相同的。每个工件进入任一个机床以后出去就完成了这道工序。所以,起初的最佳路径仍是统一减少调整时间后的最佳路径。这就证明了我们的结论。下面讨论以D2为调整时间矩阵问题的解。D2的每行每列都至少有一个零元素。因为t13=0，从机床v1出发必然选择机床v3作为下一个要到达的机床。在D2矩阵中划去t13元素所在的行和列，并将t31改为，这样是为了避免在继序往下做时出现工件经过机床v3后又重新回到机床v1的现象，这不符合工件加工要求。消去第一行及第三列的原因在于从机床v1出来只能在其它机床中选择一个机床,选了机床v3就不能选择其它机床了，而既然选择了机床v1到机床v3，那么从其它机床出来就不能再选机床v3了。V2V3V4V5V616D3= V1 V2 V4 V5 V6现在要选择从机床v3出来的下一个机床，因为t32=0，所以从机床v3出来的下一个机床选v2。划去t32元素所在的行和列，并将t21改为，这样是为了避免在继序往下做时出现工件经过机床v2后又重新回到机床v1的现象，这不符合工件加工要求。V1 V4 V5 V6V2V4V5V6D4= 而D4的第一行却无零元素出现，所以要该行的所有元素都减去这行的最小元素4，得：20=16+4D5V1 V4 V5 V6V2V4V5V6= 机床V2的下一个机必然是选机床V6了，因为t26=0，划掉t26所在的行和列，得：20V4V5V6 D6= V1 V4 V5 因为t64=0，所以从机床v6出来的下一个机床选v4。划去t64元素所在的行和列，并将t41改为，这样是为了避免在继序往下做时出现工件经过机床v4后又重新回到机床v1的情况，这不符合工件加工要求。20V4V5 D7= V1 V5 因为t45=0，所以从机床v4出来的下一个机床选v5。划去t45元素所在的行和列，得：D8=V51 20V1 而D8第一行没有零元素出现，所以要该行的所有元素都减去这行的最小元素1，得：D9=V50 21=20+1V1 因为t91=0，所以工件最后又回到机床v1。 故得一条流程线v1 v3 v2 v6 v4 v5 v1，总调整时间为21。它是否为最佳路径呢？ 我们回到矩阵D2：到机床V1的调整时间最短的是机床V3，到机床V3的调整时间最短的除了机床V1还有机床V2，不能选V1，只能选机床V2（原因见前面）；到机床V2的调整时间最短的除了机床V3， V1还有机床V6，不能选V3，V1，只能选机床V6；到机床V6的调整时间最短的只有V4；到机床V4的调整时间最短的除了机床V6， V1还有机床V5，不能选V6，V1，只能选机床V5；到机床V5的调整时间最短的除了机床V4只有V1，所以上面得到的回路是最佳流程线。 这种反复使用数学模型中匈牙利法的前两步的方法也可应用于机床调整时间矩阵为非对称矩阵的情况. 例2:假设现在设计师面对的是拥有三台机床的机械车间,而这三台机床相互之间有两条流程线可达,但流程线均是单程的,所以本例的图G是有向图.下面我引入一个定理,它可以判断有向图是否具有哈密顿回路.定理2: 如果图G满足下面条件,它就具有哈密顿回路: ()图G是强连通图;()对所有顶点xX,d(x)=n. 很显然,图G具有哈密顿回路.例2的调整时间矩阵为D.-2-3-1V4V2V3 D= V1 V2 V3 231V4V2V3 D1= V1 V2 V3 8=6+2V4V2V3 D2= V1 V2 V3 V2V3V2V3 V1 V2 V1 V3 D3= V1 V3 D”3= 10=8+212=8+4V2V3V2V3D4= D”4= V1 V2V1 V3 用与例1一样的方法得到上面一系列矩阵.求出的结果有两个:由矩阵D, D1 ,D2, D3 ,D4得到:由V1 到V2 到 V3 再回到V1,它的总调整时间为10;由矩阵D, D1 ,D2, D”3 ,D”4得到:由V1 到V3到 V2再回到V1,它的总调整时间为12. 所以这种方法更适合类似例1的情况使用.参考文献：1 杨骅飞，王朝瑞 组合数学及其应用M.北京理工大学出版社2 徐俊明 图论及其应用M.中国科学技术大学出版社3 卜月华，吴建专 图论及其应用M.中国科学技术大学出版社4 范逢曦 图论方法及其应用M.山西科技教育大学出版社5 美Fred Buckley 著，李慧霸 王风芹 译 图论简明教程M.清华大学出版社ONE SOLUTION TO THE TRAVELING SALESMAN PROBLEM Wang Rongrong(THE MATHS DEPARTMENT OF BAOTOU TEACHERS COLLDGE)Abstract: according to put forward the traveling salesman problem to introduce how to find the solution of the operation of machine tool that is closely linked with life. optimum Hamilton circuit is not only the o