TSP問題及LINGO求解技巧資料

1、TSP問題及LINGO求解技巧巡回旅行商問題(Traveling Salesman Problem , TSP),也稱為貨郎擔(dān)問題.最早可以追 溯到1759年Euler提出的騎士旅行問題.1948年,由美國蘭德公司推動(dòng),TSP成為近代組合優(yōu)化領(lǐng)域的一個(gè)典型難題.它已經(jīng)被證實(shí)屬于NP難題.用圖論描述TSP,給出一個(gè)圖G (V, E),每邊e E上有非負(fù)權(quán)值 w(e),尋找G的Hamilton圈C,使得C的總權(quán) W(C)w(e)最小.e E(C)幾十年來,出現(xiàn)了很多近似優(yōu)化算法.如近鄰法、貪心算法、最近插入法、最遠(yuǎn)插入法、 模擬退火算法以及遺傳算法.這里我們介紹利用LINGO軟件進(jìn)行求解的方法.問

2、題1 設(shè)有一個(gè)售貨員從10個(gè)城市中的某一個(gè)城市出發(fā),去其它9個(gè)城市推銷產(chǎn)品.10個(gè)城市相互距離如下表.要求每個(gè)城市到達(dá)一次僅一次后,回到原出發(fā)城市.問他應(yīng)如何選擇旅行路線,使總路程最短.表110個(gè)城市距離表城市1234567891010745861213111827031091451417173430591021827124510501491092316589914078720196614109701352513712521108130232118813148975230181291117272320252118016101817121619131812160我們采用線性規(guī)劃的方法求解設(shè)城市之

3、間距離用矩陣 d來表示,dij表示城市i與城市j之間的距離.設(shè)0-1矩陣X用 來表示經(jīng)過的各城市之間的路線.設(shè)0假設(shè)城市i不到城市jXj1 假設(shè)城市i到城市j,且i在j前考慮每個(gè)城市后只有一個(gè)城市,那么：nXj1, i 1,n考慮每個(gè)城市前只有一個(gè)城市,那么:nXjj1, j 1,n ；為此我們引入額外變量uj i 1,n附 加 以 下 充 分 約 束 條 件ui uj nXij n 1, 1 i j n ； 該約束的解釋：如i與j不會(huì)構(gòu)成回路,假設(shè)構(gòu)成回路,有：Xij 1, X ji 1,那么：ui u j1, u j ui1,從而有：0 2 ,導(dǎo)致矛盾.如i, j與k不會(huì)構(gòu)成回路,假設(shè)構(gòu)成

4、回路,有:Xij 1, Xjk 1, Xki 1 那么：ui u j1, u j uk1, uk ui 1從而有：0 3 ,導(dǎo)致矛盾.其它情況以此類推.于是我們可以得到如下的模型：i1ij但僅以上約束條件不能防止在一次遍歷中產(chǎn)生多于一個(gè)互不連通回路.min zdj xiji,j 1nxij 1, ji 1i jnstXj1,j 1j iuiujnxj%0或1,ui為實(shí)數(shù),1川,ni 1川,nn 1,1 i j ni,j 1,|,ni 1川,n前面問題的Lin go程序 !TSP quesi on;MODEL:SETS: city/1.10/:u; lin k(city,city):d,x; E

5、NDSETSDATA:d= C)745861213111870310914514171743 059102182712510 5 014910923168991407872019614 109701352513125 211081302321181314 897523018121117 2723202521180161817 121619131812160;ENDDATAMIN=SUM(li nk:d*x);城市j前有一個(gè)城市相連!城市i后前有一個(gè)城市相連；for(city(j):sum(city(i)|j# ne#i:x(i,j)=1); !for(city(i):sum(city(j)|j

6、# ne#i:x(i,j)=1);for(li nk(i,j)|i#NE#j#a nd#i#gt#1:u(i)-u(j)+10*x(i,j)<=9);FOR(li nk:BIN(x);End 得到的結(jié)果如下: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 432 7 5 6 8 10 9 1,最短距離為 77公里.問題2. 2005年電工杯B題比賽工程排序問題全民健身方案是1995年在國務(wù)院領(lǐng)導(dǎo)下,由國家體委會(huì)同有關(guān)部門、

7、 各群眾組織和社 會(huì)團(tuán)體共同推行的一項(xiàng)依托社會(huì)、全民參與的體育健身方案, 是與實(shí)現(xiàn)社會(huì)主義現(xiàn)代化目標(biāo)相配套的社會(huì)系統(tǒng)工程和跨世紀(jì)的開展戰(zhàn)略規(guī)劃.現(xiàn)在,以全民健身為主要內(nèi)容的群眾性體育活動(dòng)蓬勃開展,舉國上下形成了全民健身的熱潮,人民群眾健康水平不斷提升,同時(shí)也擴(kuò)大了競技體育的社會(huì)影響, 提升了競技體育水平. 現(xiàn)在各級(jí)、各類、各種運(yùn)動(dòng)比賽比比皆是, 這不但提升了全民的身體素質(zhì),而且使一批運(yùn)發(fā)動(dòng)脫穎而出,成為運(yùn)動(dòng)健將,為國家爭得了榮譽(yù).在各種運(yùn)動(dòng)比賽中,為了使比賽公平、公正、合理的舉行,一個(gè)根本要求是：在比賽項(xiàng) 目排序過程中,盡可能使每個(gè)運(yùn)發(fā)動(dòng)不連續(xù)參加兩項(xiàng)比賽,以便運(yùn)發(fā)動(dòng)恢復(fù)體力, 發(fā)揮正常水平.

8、1 表2是某個(gè)小型運(yùn)動(dòng)會(huì)的比賽報(bào)名表.有14個(gè)比賽工程,40名運(yùn)發(fā)動(dòng)參加比賽.表中第1行表示14個(gè)比賽工程,第1列表示40名運(yùn)發(fā)動(dòng),表中號(hào)位置表示運(yùn)發(fā)動(dòng)參 加此項(xiàng)比賽.建立此問題的數(shù)學(xué)模型, 并且合理安排比賽工程順序,使連續(xù)參加兩項(xiàng)比賽的運(yùn)發(fā)動(dòng)人次盡可能的少；2. 文件“運(yùn)發(fā)動(dòng)報(bào)名表中給出了某個(gè)運(yùn)動(dòng)比賽的報(bào)名情況.共有61個(gè)比賽工程,1050人參加比賽.請(qǐng)給出算法及其框圖, 同時(shí)給出合理的比賽工程排序表,使連續(xù)參加兩項(xiàng)比賽的運(yùn)發(fā)動(dòng)人次盡可能的少；3. 說明上述算法的合理性；4. 對(duì)“問題 2的比賽排序結(jié)果,給出解決“運(yùn)發(fā)動(dòng)連續(xù)參加比賽問題的建議及方 案.表2 某小型運(yùn)動(dòng)會(huì)的比賽報(bào)名表、_工程運(yùn)

9、發(fā)動(dòng)、12345678910111213141#2#3#4#5#6#7#8#9#10#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#27#28#29#30#31#32#33#34#35#36#37#38#39#40#問題一解答：假設(shè)工程i和工程j相鄰,可以計(jì)算出同時(shí)參加這兩個(gè)工程的人數(shù),作為i和j的距離dj.那么問題轉(zhuǎn)化為求工程1到工程14的一個(gè)排列,使相鄰距離和最小.我 們采用TSP問題求解.但由于開始工程和結(jié)束工程沒有連接, 可考慮引入虛擬項(xiàng) 目15,該虛擬工程與各個(gè)工程的距離都為 0.距離矩陣D的求法：該報(bào)名表用矩陣A40 14表示.1第

10、i個(gè)人參加工程jaij 0第i個(gè)人不參加工程j40那么 dijagakji j ,i, j, 1,2,川,14k 1dH 0 i 1,2,川,14另外 di,15 0,d15,i0 i 1,2,|,15由于問題1中40個(gè)運(yùn)發(fā)動(dòng)參加14個(gè)工程的比賽是word表,可將其拷貝到 Excel表中,然后將#替換為1,將空格替換為0,形成0-1表,并拷貝到數(shù)據(jù)文 件table1.txt 中.問題2中1050個(gè)運(yùn)發(fā)動(dòng)參加的61個(gè)工程比賽的Access數(shù)據(jù) 庫中的表保存為Excel表,然后在表中將#替換為1,將空格替換為0,形成0-1 表,并拷貝到數(shù)據(jù)文件table2.txt 中.在Matlab中編制如下程序

11、形成距離矩陣.load table1.txt;a=table1;m, n=size(a);d=zeros(n+1,n+1); % 定義距離矩陣；for i=1: nfor j=1: nfor k=1:md(i,j)=d(i,j)+a(k,i)*a(k,j); %計(jì)算不同工程之間距離endendendfor i=1: n+1d(i,i)=0;end%輸出文件fid=fope n('dis1.txt','w');for i=1: n+1for j=1: n+1fprin tf(fid,'%1d ',d(i,j);endfprin tf(fid,

12、9;n');endfclose(fid);輸出的距離矩陣D 為：021200101211110201410111310210110100031102210241011210210110010102011101120000120121112120110201011102210013112101214220111011110111310231211121010030110101011103110102012241030100122111223011040111122121310400000000000000000然后根據(jù)前面介紹的方法 2 程序：! 第一個(gè)問題的求解的程序：! 比賽工程排序

13、問題 ;model :sets :item / 1. 15/: u;link ( item, item ) :dist,x;endsetsn =size ( item);data : ! 距離矩陣 ;di st=fil e('c: lingo12prgdis1.txt'); ! 文件路徑 ;! 輸 出為 1 的變量 ;text()= writef or( link(i,j) |x(i,j)#GT#0:' x(',i,',',j,')=',x(i,j);enddat aMIN =SUM(link:dist*x);for (item(

14、j)：sum(item(i)|j#ne#i:x(i,j)=1);!點(diǎn)j 前有一個(gè)點(diǎn)相連for( ite m(i) :sum(ite m(j) |j#ne#i:x(i,j)=1);!點(diǎn) i 后前有一個(gè)點(diǎn)；! 保證不出現(xiàn) 子 圈 ;for(link(i ,j) |i#N E#j#and#i#gt#1:u(i)-u(j)+n*x(i,j)<=n-1 );FORIink:BIN(x);!定義X為0-1 變量；end其中數(shù)據(jù)文件dis1.txt 為：021200101211110201410111310210110100031102210241011210210110010102011101120

15、000120121112120110201011102210013112101214220111011110111310231211121010030110101011103110102012241030100122111223011040111122121310400000000000000000Lin go12求解結(jié)果為： 目標(biāo)值z(mì)=2x(1,8)=1 x(2,6)=1 x(3,11)=1 x(4,13)=1 x(5,1)=1x(6,3)=1x(7,5)=1 x(8,15)=1 x(9,4)=1 x(10,12)=1 x(11,7)=1x(12,14)=1x(13,10)=1 x(14,2

16、)=1 x(15,9)=1由于15是虛擬項(xiàng),去掉后對(duì)應(yīng)序列為9-4-13-10-12-14-2-6-3-11-7-5-1-8-9那么工程排序如下,其中箭頭上所示數(shù)字為連續(xù)參加相鄰兩工程的運(yùn)發(fā)動(dòng)數(shù).94 131012142即有兩名運(yùn)發(fā)動(dòng)連續(xù)參加比賽.問題2解答與問題1相同,只是工程變成61個(gè),引入虛擬工程后變?yōu)?2個(gè),運(yùn) 發(fā)動(dòng)為1050名.模型建立同問題1.在問題一中的Matlab程序中只需要將表 table1.txt 改為table2.txt,輸出數(shù)據(jù)文件將dis1.txt 改為dis2.txt 就可以了.在Lingo程序中將工程數(shù)由15修改為62,使用的數(shù)據(jù)文件由15改為62,同樣可以運(yùn)行,

17、只是運(yùn)行時(shí)間較長,本程序在Lingo12中大約運(yùn)行6分鐘左右.原始數(shù) 據(jù)文件table2.txt和Matlab輸出的距離矩陣dis2.txt ,由于數(shù)據(jù)較大這里不列出,可參見附錄.Lingo 程序! 第二個(gè)問題的求解的程序：! 比賽工程排序問題 ;model :sets : item / 1. 62/: u;link ( item, item ) :dist,x;endsetsn = size ( item); data : ! 距離矩陣 ;di st=fil e('c: lingo12prgdis2.txt');! 文件路徑 ;! 輸 出為 1 的變量 ;text()= wr

18、itef or( link(i,j) |x(i,j)#GT#0:' x(',i,',',j,')=',x(i,j);enddat aMIN =SUM(link:dist*x);for (item(j):sum(item(i)|j#ne#i:x(i,j)=1);!點(diǎn)j 前有一個(gè)點(diǎn)相連for( ite m(i) :sum(ite m(j) |j#ne#i:x(i,j)=1);! 點(diǎn) i 后前有一個(gè)點(diǎn) ;! 保證不出現(xiàn) 子 圈 ;for(link(i ,j) |i#N E#j#and#i#gt#1:u(i)-u(j)+n*x(i,j)<=n-1

19、);FORlink:BIN(x);!定義X為0-1 變量；endLingo12 求解結(jié)果：Lin go12求解結(jié)果為：目標(biāo)值 z=5x(1,19)=1 x(2,44)=1 x(3,50)=1 x(4,25)=1 x(5,20)=1 x(6,15)=1 x(7,42)=1 x(8,59)=1 x(9,35)=1 x(10,3)=1 x(11,54)=1 x(12,21)=1 x(13,32)=1 x(14,41)=1 x(15,40)=1 x(16,57)=1 x(17,22)=1 x(18,9)=1 x(19,60)=1 x(20,6)=1 x(21,10)=1 x(22,37)=1 x(23,14)=1 x(24,51)=1 x(25,13)=1 x(26,27)=1 x(27,29)=1 x(28,17)=1 x(29,24)=1 x(30,5