資源描述：
《旅行商問題數(shù)學建模》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、黃石理工學院數(shù)學建模大型作業(yè)2011—2012學年第1學期10目錄一．摘要二．旅行問題1.問題描述2.符號說明3.模型設計4.建模求解5.模型分析6.三．建模過程及心得體會四．參考文件10一．摘要本文是一個圍繞旅行商問題和背包問題這兩個經典問題的論文。問題一，是一個依賴與每個城市去一次且僅去一次的路線確定問題，問題二類似于問題一。問題三是一個依賴于可背重量限制的背包問題。關鍵詞：HAMILTON回路LINGO最優(yōu)旅行路線0-1模型二．旅行問題問題描述某人要在假期內從城市A出發(fā)，乘火車或飛機到城市B,C,D,E,F旅游購物。他計劃走遍
2、這些城市各一次且僅一次，最后返回城市A。已知城市間的路費數(shù)據(jù)見附表1，請你設計一條旅行路線使得他的總路費最少。如果臨行他因故只能去4個城市，該怎樣修訂旅行路線？在城市間旅游時他計劃購買照相機，衣服，書籍，攝像機，漁具，白酒，食品，而受航空行李重量的限制以及個人體力所限，所買物品的總重量不能超過15kg，各種物品的價格見附表2.請你為他決策買哪些物品，使所買物品價值最大。附表1：ABCDEFA0120250330210150B120098350225300C250980520430280D3303505200270185E210225
3、4302700420F1503002801854200附表2照相機衣服書籍攝像機漁具白酒食品香煙重量（kg）12434221價格(元)130027503204350140030012060010模型設計首先給出一個定義：設v1,v2,......,vn是圖G中的n個頂點，若有一條從某一頂點v1出發(fā)，經過各節(jié)點一次且僅一次，最后返回出發(fā)點v1的回路，則稱此回路為HAMILTON回路。問題1.分析：這個優(yōu)化問題的目標是使旅行的總費用最少，要做的決策是如何設定旅行路線，決策受的約束條件：每個城市都必須去，但僅能去一次。按題目所給，將決定變
4、量，目標函數(shù)和約束條件用數(shù)學符號及式子表示出來，就可得一下模型。模型建立：對于6個城市的旅行問題設A,B,C,D,E,F六個城市分別對應v1,v2,v3,v4,v5,v6。假設表示從城市i到城市j的費用。定義0-1整數(shù)型變量=1表示從城市i旅行到城市j，否則=0。則旅行問題的數(shù)學模型可表示為一個整數(shù)規(guī)劃問題。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ù)）。事實上，在最優(yōu)解中，=訪問城市的順序數(shù)。模型求解運用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得到結果：總費用為1163路線：A-B-C-F-D-E-A問題2.臨時因故只能去4個城市，那么應該怎樣安排旅行路線。分析：在B,C,D,E,F五個城市中選4個城市，顯然有5種可能，按照問題一中的模型，將費用矩陣稍作修改，運
