資源描述：
《旅行商問(wèn)題數(shù)學(xué)建模》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、黃石理工學(xué)院數(shù)學(xué)建模大型作業(yè)2011—2012學(xué)年第1學(xué)期10目錄一．摘要二．旅行問(wèn)題1.問(wèn)題描述2.符號(hào)說(shuō)明3.模型設(shè)計(jì)4.建模求解5.模型分析6.三．建模過(guò)程及心得體會(huì)四．參考文件10一．摘要本文是一個(gè)圍繞旅行商問(wèn)題和背包問(wèn)題這兩個(gè)經(jīng)典問(wèn)題的論文。問(wèn)題一，是一個(gè)依賴與每個(gè)城市去一次且僅去一次的路線確定問(wèn)題，問(wèn)題二類似于問(wèn)題一。問(wèn)題三是一個(gè)依賴于可背重量限制的背包問(wèn)題。關(guān)鍵詞：HAMILTON回路LINGO最優(yōu)旅行路線0-1模型二．旅行問(wèn)題問(wèn)題描述某人要在假期內(nèi)從城市A出發(fā)，乘火車或飛機(jī)到城市B,C,D,E,F旅游購(gòu)物。他計(jì)劃走遍
2、這些城市各一次且僅一次，最后返回城市A。已知城市間的路費(fèi)數(shù)據(jù)見附表1，請(qǐng)你設(shè)計(jì)一條旅行路線使得他的總路費(fèi)最少。如果臨行他因故只能去4個(gè)城市，該怎樣修訂旅行路線？在城市間旅游時(shí)他計(jì)劃購(gòu)買照相機(jī)，衣服，書籍，攝像機(jī)，漁具，白酒，食品，而受航空行李重量的限制以及個(gè)人體力所限，所買物品的總重量不能超過(guò)15kg，各種物品的價(jià)格見附表2.請(qǐng)你為他決策買哪些物品，使所買物品價(jià)值最大。附表1：ABCDEFA0120250330210150B120098350225300C250980520430280D3303505200270185E210225
3、4302700420F1503002801854200附表2照相機(jī)衣服書籍?dāng)z像機(jī)漁具白酒食品香煙重量（kg）12434221價(jià)格(元)130027503204350140030012060010模型設(shè)計(jì)首先給出一個(gè)定義：設(shè)v1,v2,......,vn是圖G中的n個(gè)頂點(diǎn)，若有一條從某一頂點(diǎn)v1出發(fā)，經(jīng)過(guò)各節(jié)點(diǎn)一次且僅一次，最后返回出發(fā)點(diǎn)v1的回路，則稱此回路為HAMILTON回路。問(wèn)題1.分析：這個(gè)優(yōu)化問(wèn)題的目標(biāo)是使旅行的總費(fèi)用最少，要做的決策是如何設(shè)定旅行路線，決策受的約束條件：每個(gè)城市都必須去，但僅能去一次。按題目所給，將決定變
4、量，目標(biāo)函數(shù)和約束條件用數(shù)學(xué)符號(hào)及式子表示出來(lái)，就可得一下模型。模型建立：對(duì)于6個(gè)城市的旅行問(wèn)題設(shè)A,B,C,D,E,F六個(gè)城市分別對(duì)應(yīng)v1,v2,v3,v4,v5,v6。假設(shè)表示從城市i到城市j的費(fèi)用。定義0-1整數(shù)型變量=1表示從城市i旅行到城市j，否則=0。則旅行問(wèn)題的數(shù)學(xué)模型可表示為一個(gè)整數(shù)規(guī)劃問(wèn)題。minz=(ij)s.t.=1（ij；j=1,2,……,6）=1(ij；i=1,2,……,6)(ij;i=2,3,……,6;j=2,3,……6)其中輔助變量（i=2,3,……,6）可以是連續(xù)變化的，雖然這些變量在最優(yōu)解中取普通的
5、整數(shù)值（從而在約束條件中，可以限定這些變量為整數(shù)）。事實(shí)上，在最優(yōu)解中，=訪問(wèn)城市的順序數(shù)。模型求解運(yùn)用LINGO，輸入程序：MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..6/:U;!U(I)=sequenceno.ofcity;LINK(CITY,CITY):COST,!Thecostmatrix;10X;!X(I,J)=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=
6、0120250330210150120098350225300250980520430280330350520027018521022543027004201503002801854200;ENDDATAN=@SIZE(CITY);MIN=@SUM(LINK:COST*X);@FOR(CITY(K):!Itmustbeentered;@SUM(CITY(I)
7、I#NE#K:X(I,K))=1;!Itmustbedeparted;@SUM(CITY(J)
8、J#NE#K:X(K,J))=1;!Weakformofthesubtourbr
9、eakingconstrains;!Thesearenotverypowerfulforlargeproblems;@FOR(CITY(J)
10、J#GT#1#AND#J#NE#K:U(J)>=U(K)+X(K,J)-(N-2)*(1-X(K,J))+(N-3)*X(J,K)););@FOR(LINK:@BIN(X));!MaketheX's0/1;!Forthefirstandlaststopweknow...;@FOR(CITY(K)
11、K#GT#1:U(K)<=N-1-(N-2)*X(1,K);U(K)>=1+(N-2)*X(K,1
12、));END得到結(jié)果：總費(fèi)用為1163路線：A-B-C-F-D-E-A問(wèn)題2.臨時(shí)因故只能去4個(gè)城市，那么應(yīng)該怎樣安排旅行路線。分析：在B,C,D,E,F五個(gè)城市中選4個(gè)城市，顯然有5種可能，按照問(wèn)題一中的模型，將費(fèi)用矩陣稍作修改，運(yùn)
