文档介绍：Forpersonaluseonlyinstudyandresearch;mercialuse肃TSP问题及LINGO求解技巧羂螈巡回旅行商问题(TravelingSalesmanProblem,TSP),也称为货郎担问题。最早可以追溯到1759年Euler提出的骑士旅行问题。1948年,由美国兰德公司推动,TSP成为近代组合优化领域的一个典型难题。它已经被证明属于NP难题。肄用图论描述TSP,给出一个图,每边上有非负权值,寻找G的Hamilton圈C,,出现了很多近似优化算法。如近邻法、贪心算法、最近插入法、最远插入法、模拟退火算法以及遗传算法。这里我们介绍利用LINGO软件进行求解的方法。螁袈问题1设有一个售货员从10个城市中的某一个城市出发,去其它9个城市推销产品。10个城市相互距离如下表。要求每个城市到达一次仅一次后,回到原出发城市。问他应如何选择旅行路线,使总路程最短。蒅表110个城市距离表芃城市薀1羈2袆3羅4艿5肈6芇7莂8莂9肈10莃1膄0肀7膈4袄5薂8衿6芈12芅13芄11袂18莈2蚆7螂0蚁3蒇10肇9蒄14蒀5薇14膄17羂17腿3蚇4薅3蚄0节5蚇9羆10肅21羄8螁27芀12螇4蚃5袁10蚁5膅0螆14袀9袈10羇9蒅23羀16艿5虿8芄9肀9蚀14肇0肃7膀8肁7蝿20肆19芀6***6芆14袄10莀9薈7羈0蚃13蚄5罿25蒆13蚆7螄12莀5膈21蒅10袃8螁13薆0膄23羃21羈18莈8羃13肃14荿8螆9羆7肃5螀23蒇0螅18膃12膁9羅11薃17芃27芇23蚇20节25莃21蚈18膅0莅16蒃10聿18袇17肄12薂16蒀19芅13袃18蚂12袁16羇0羆蚂我们采用线性规划的方法求解羈设城市之间距离用矩阵来表示,表示城市与城市之间的距离。设0--1矩阵用来表示经过的各城市之间的路线。设蝿蚅考虑每个城市后只有一个城市,则:螂荿考虑每个城市前只有一个城市,则:膆;蒄但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。袂为此我们引入额外变量,附加以下充分约束条件:;螀该约束的解释:袈如与不会构成回路,若构成回路,有:节,,则:羂,,从而有:膀,导致矛盾。莆如,与不会构成回路,若构成回路,有:芅,,则:肂,,从而有:莇,导致矛盾。肈其它情况以此类推。肄膂螈于是我们可以得到如下的模型:薆螃芁腿芈袆前面问题的Lingo程序芁!TSPquesion;薀MODEL:蚆SETS:薅city/1..10/:u;莁link(city,city):d,x;羁ENDSETS莈DATA:莄d=07 4 5 8 6 12 13 11 18蒁70 3 10 9 14 5 14 17 17肈430 5 9 10 21 8 27 12袅5105 0 14 9 10 9 23 16膃89 9 14 0 7 8 7 20 19薁61410 9 7 0 13 5 25 13葿12521 10 8 13 0 23 21 18薇13148 9 7 5 23 0 18 12膅111727 23 20 25 21 18 0 16蚁181712 16 19 13 18 12 16 0;衿肅ENDDATA羄MIN=***@SUM(link:d*x);螁***@for(city(j):***@sum(city(i)|j#ne#i:x(i,j))=1);!城市j前有一个城市相连;芀***@for(city(i):***@sum(city(j)|j#ne#i:x(i,j))=1);!城市i后前有一个城市相连;螇***@for(link(i,j)|i#NE#j#and#i#gt#1:u(i)-u(j)+10*x(i,j)<=9);蚃***@FOR(link:***@BIN(x));袁End蚁膅得到的结果如下:X(3,2)=1,X(4,1)=1,X(4,3)=1,X(6,5)=1,X(7,2)=1,X(7,5)=1,X(8,6)=1,X(9,1)=1,X(10,8)=1,X(10,9)=1。其它全为0。螆其最短路线为1—4—3—2—7—5—6—8—10—9—1,最短距离为77公里。,由国家体委会同有关部门、各群众组织和社会团体共同推行的一项依托社会、全民参与的体育健身计划,是与实现社会主义现代化目标相配套的社会系统工程和跨世纪的发展战略规划。现在,以全民健身为主要内容的群众性体育活动蓬勃开展,举国上下形成了全民健身的热潮,人民群众健康水平不断提高,同时也扩大了竞技体育的社会影响,提高了竞技体育水平。现在各级、各类、各种运动比赛比比皆是,这不但提高了全民的身体素质,而且使一批运动员脱颖而出,成为运动健将,为国家争得了荣誉。羀在各种运动比赛中,为了使比赛公平、公正、合理的举行,