《【VIP专享】lingo-TSP问题.pdf》由会员分享，可在线阅读，更多相关《【VIP专享】lingo-TSP问题.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、9姓名专业班级课程876543211085470193072Lingo唐波城市618109503430554实验项目学 号111312分析与解答：141009985145177966信息与计算科学 2010 级17101485710170102141414812102112798814139实验日期272023271711191612171810211099LINGOLINGO 课课程程试验专题试验专题TSPTSP162310787192050基于 Lingo 的数学实验132513018212313051218230成绩指导教师16182125016121813任弛远方法一：设城市之间的距离
2、用矩阵d来表示，其中d为下三角矩阵，dij表示城2014-4-1例：设有一个销售员从 10 个城市中的某一个城市出发，去其他的 9 个城市推销产品。10 个城市相互距离如下表所示。要求每个城市到达且仅到达一次，回到原出发城市。问：他应该如何选择旅行路线，使总路程最短？前言：TSP 问题，即巡回旅行商问题，也称为货担郎问题，早期是 1759 年Euler 提出的骑士旅行问题。1948 年，有美国兰德公司推动，成为近代组合优化问题中的一个典型难题，它被证明为是 NP 难题。图论描述就是给定一个有向或者是无向的图，并给定他们各边的权值，找一个 Hamilton 圈使得总权最小。d=7 4 3mode
3、l:ni1i2 j1endsetsdata:5 10 5 8 9 9 14 6 14 10 9 7得到的结果：min z xijdijLINGO 具体程序如下：12 5 21 10 8 13sets:city/1.10/;link(city,city)|&1#GT#&2:d,x;13 14 8 9 7 5 23 11 17 27 23 20 25 21 18 18 17 12 16 19 13 18 12 16;xj12j1s.txikxji 2i 2,3,4,.,njikix 0或1ijij0若城市不到城市xij则建立该 TSP 问题的模型如下:ij1若城市到城市市i与城市j之间的距离。设
4、0-1 矩阵x用来表示经过的各城市之间的路线。设它的主要思想就是与第一个城市相连的有两个城市，与第i个城市相连的有两个城市，每个城市都有相连的两个城市，这个自然就够成一个 Hamilton 圈，但是不保证有多个圈的情况。enddatamin=sum(link:d*x);sum(city(j)|j#GT#1:x(j,1)=2;for(city(i)|i#GT#1:sum(city(j)|j#GT#i:x(j,i)+sum(city(k)|k#LT#i:x(i,k)=2);for(link:bin(x);每个城市后也只有一个城市考虑每个城市前只有一个城市ij0若城市不到城市xijij,ij1若城市
5、到城市且在前X(7,5)1.000000 8.000000X(8,6)1.000000 5.000000X(9,1)1.000000 11.00000X(10,8)1.000000 12.00000X(10,9)1.000000 16.00000X(4,3)1.000000 5.000000X(6,5)1.000000 7.000000X(7,2)1.000000 5.000000Variable Value Reduced CostX(3,2)1.000000 3.000000X(4,1)1.000000 5.000000 Global optimal solution found.Obje
6、ctive value:77.00000 Objective bound:77.00000 Infeasibilities:0.000000 Extended solver steps:0 Total solver iterations:12设 0-1 矩阵x用来表示经过的各城市之间的路线。设i1,i jnj1,jinxij1i 1,2,3,.,nxij1j 1,2,3,.,n结果分析：从这个结果我们可以看出，该 TSP 问题的最短距离是 77km，其最短路线为：14327 5681091。该方法将 TSP 问题求解化为线性规划，用 LINGO求解。求解速度极快，但是可能会形成一个子圈，没有办
7、法得到真正的最优解。回路，因此我们要加入约束条件，引入额外变量ui(i 1,2,3,.,n),即但是仅仅只有以上的条件是不能避免在一次遍历当中产生多于一个互不连通的方法二:设城市之间的距离用矩阵d来表示，dij表示城市i到城市j之间的距离。推。min z ni,j1对于该约束的解释是:dijijx编写的 LINGO 程序如下：uiuj 1,ujui 1，从而有0 2，导致矛盾。uiuj 1,ujuk 1,ukui 1,从而有0 3，导致矛盾。其他情况以此类uiujnxij n1,1 i j n于是就可以得到此方法的求解模型：一方面i与 j 不会构成回路，若构成回路，有xij1,xji1,则另一
8、方面i，j 与k不会构成回路，若构成回路，有xij1,xjk1,xki1,则有nxij1,j 1,2,3,.,ni1,i juiujnxij n1,1 i j ns.txij 0或，1i,j 1,2,3,.,nnx 1,i 1,2,3,.,nj1,jiijui为实数，i 1,2,3,.,nend运行结果显示：model:sets:city/1.10/:u;link(city,city):d,x;endsetsdata:d=0 7 4 5 8 6 12 13 11 18 7 0 3 10 9 14 5 14 17 17 4 3 0 5 9 10 21 8 27 12 5 10 5 0 14 9
9、10 9 23 16 8 9 9 14 0 7 8 7 20 19 6 14 10 9 7 0 13 5 25 13 12 5 21 10 8 13 0 23 21 18 13 14 8 9 7 5 23 0 18 12 11 17 27 23 20 25 21 18 0 16 18 17 12 16 19 13 18 12 16 0;enddatamin=sum(link:d*x);for(city(j):sum(city(i)|j#ne#i:x(i,j)=1);for(city(i):sum(city(j)|j#ne#i:x(i,j)=1);for(link(i,j)|i#ne#j#and
10、#i#gt#1:u(i)-u(j)+10*x(i,j)=9);for(link:bin(x);Global optimal solution found.Objective value:77.00000 Objective bound:77.00000Infeasibilities:0.000000Extended solver steps:0Total solver iterations:785Variable Value Reduced CostX(1,4)1.000000 5.000000X(2,7)1.000000 5.000000X(3,2)1.000000 3.000000X(4,
11、3)1.000000 5.000000X(5,6)1.000000 7.000000X(6,8)1.000000 5.000000X(7,5)1.000000 8.000000X(8,10)1.000000 12.00000X(9,1)1.000000 11.00000X(10,9)1.000000 16.00000结果分析：从该结果可以看出，与方法一得到的结果相同，它的优点是可以很好的解决圈的问题，不会出现有子圈的问题；缺点是对规模较大的问题的计算非常耗时。心得体会：学习 LINGO 后，觉得有些数学问题变得更简单了，例如以前解决TSP 问题我们采用是纯计算方式：蛮力法，回溯法等，现在采用计算机，充分发扬了计算机与数学的结合，讲计算机与数学整合到一块，这是现代社会所需要的综合型人才息息相关，所以学习lingo 是大学里面和工作比较接近的科目，所以我觉得 lingo 真好！