TSP問(wèn)題《運(yùn)籌學(xué)》綜合性實(shí)驗(yàn)報(bào)告

1、華北科技學(xué)院基礎(chǔ)部綜合性實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告課程名稱運(yùn)籌學(xué)B實(shí)驗(yàn)學(xué)期 2011 至2012學(xué)年 第2學(xué)期學(xué)生所在系部基礎(chǔ)部年級(jí) 09專業(yè)班級(jí)計(jì)算B091班學(xué)生姓名張成林學(xué)號(hào) 200909014101任課教師孫士國(guó)實(shí)驗(yàn)成績(jī)2012年6月13日運(yùn)籌學(xué)B課程綜合性實(shí)驗(yàn)報(bào)告開課實(shí)驗(yàn)室：數(shù)學(xué)應(yīng)用實(shí)驗(yàn)室實(shí)驗(yàn)題目TSP問(wèn)題一、實(shí)驗(yàn)?zāi)康?）領(lǐng)會(huì)TSP問(wèn)題的理論和方法。2）會(huì)編制上述方法的基于lingo語(yǔ)言的計(jì)算程序，并用來(lái)求解有關(guān)問(wèn)題。3）熟悉求解TSP問(wèn)題的有關(guān)方法和理論。4）針對(duì)所給問(wèn)題編制程序，并上機(jī)計(jì)算其所需要的結(jié)果。二、設(shè)備與環(huán)境Lingo11.0軟件等三、實(shí)驗(yàn)內(nèi)容及要求TSP問(wèn)題1設(shè)有一個(gè)售貨員從10個(gè)城

2、市中的某一個(gè)城市出發(fā)，去其它9個(gè)城市推銷產(chǎn)品。10個(gè)城 市相互距離如下表。要求每個(gè)城市到達(dá)一次僅一次后，回到原出發(fā)城市。問(wèn)他應(yīng)如 何選擇旅行路線，使總路程最短。城市1234567891010745861213111827031091451417173430591021827124510501491092316589914A787201966141097013525137125211081302321188131489752301812911172723202521180161018171216191318121601 .問(wèn)題分析與建模：設(shè)城市之間距離用矩陣d來(lái)表示，其中d為下三角矩陣，dj.表

3、示城市i與城市j之 間的距離。設(shè)0-1矩陣s用來(lái)表示經(jīng)過(guò)的各城市之間的路線。設(shè)S. = 1j0若不從城市i到城市.1若從城市i到城市.則該TSP問(wèn)題轉(zhuǎn)化為如下線性模型:e 7 yyt imin Z = yy s d=2 j=1rE s=2y s +E s. = 2 i = 2,3, , nk is = 0或 1ij2.算法設(shè)計(jì)與實(shí)現(xiàn)程序如下：!TSP quesion;MODEL:SETS:city/1.10/;link(city,city)|&1#GT#&2:d,s;ENDSETSDATA:d= 7435105899146141097125211081313148975231117272320

4、252118181712161913181216;ENDDATAMIN=SUM(link:d*s);SUM(city(j)|j#GT#1:S(j,1)=2; 與第1個(gè)城市相連的有兩個(gè)城市;FOR(city(i)|i#GT#1:SUM(city(j)|j#GT#i:s(j,i)+SUM(city(k)|k#LT#i:s(i,k)=2); !與第i個(gè)城市相連有兩個(gè)城市;FOR(link:BIN(s);四、實(shí)驗(yàn)結(jié)果及分析模型結(jié)果如圖1所示File Edit LINGO Window Helpi舀舊i昌i對(duì)釗匾i 口|國(guó)%膺|。|。|舊i同&|田| mi| Global opt- iirial sol

5、ut- ionfound.Oto ject. ive value :77.00000Cto j ect ive inound:77.00000Inf eas ibi 1 it- ies :0.000000E:tended s Iver steps :0To tai s Ive 匚 iterat- i ons :12Var i：alnleValueReduced Cost-D i：2,1)7.000000.000000D i：3,1)4.000000D【3,2：l3.000000. 0OOCiOOD i：%1)5.000000.Di：h2：i10.00000. 0OOCIOOD i：4,3：i5

6、.000000.000000D i：5,1)8.000000.000000D【5.2：l9.000000. 0OOCIOOD i：5,3：i9.Di：5,4：i14. OOCiOO. 0OOCIOOD i：E,1)6.000000.000000D f6.2i14.00000.000000L LINGO 11.0 - Solution Report - LINGO1由圖1可知：S(3,2)=1,S(4,1)=1,S(4,3)=1,S(6,5)=1,S(7,2)=1,S(7,5)=1,S(8,6)=1,S(9, 1)=1,S(10,8)=1,S(10,9)=1。其它全為0。其最短路線為1 43275681091,最短距離為77公 里。五、總結(jié)通過(guò)本次綜合實(shí)驗(yàn)，我熟悉了 TSP最短路問(wèn)題的理論和方法，代碼實(shí)現(xiàn)了其算法和功能， 收獲很大。開始設(shè)計(jì)之時(shí)完全沒(méi)頭緒，對(duì)與理論學(xué)習(xí)不夠扎實(shí)的我深感“書到用時(shí)方恨少”只好 再把書上介紹的相關(guān)知識(shí)重新閱讀一遍，對(duì)知識(shí)進(jìn)行了全面而系統(tǒng)的梳理，遇到難處首先是苦思 冥想尋求方法，再向同學(xué)請(qǐng)教，終于熟練掌握了基本理論知識(shí)，而且領(lǐng)悟了諸多平時(shí)學(xué)習(xí)難以理 解掌握的的較難的知識(shí)。在這次的綜合實(shí)驗(yàn)中不僅檢驗(yàn)了我所學(xué)習(xí)的知識(shí)，也培養(yǎng)了我如何去把握一件事情，如何去 做一件事情，又如何完