旅行商問題數(shù)學(xué)建模

1、黃石理工學(xué)院 數(shù)學(xué)建模 大型作業(yè) 20112012 學(xué)年 第1學(xué)期目錄一摘要二旅行問題1. 問題描述2. 符號說明3. 模型設(shè)計(jì)4. 建模求解5. 模型分析6.三建模過程及心得體會四參考文件一摘要本文是一個(gè)圍繞旅行商問題和背包問題這兩個(gè)經(jīng)典問題的論文。問題一，是一個(gè)依賴與每個(gè)城市去一次且僅去一次的路線確定問題，問題二類似于問題一。問題三是一個(gè)依賴于可背重量限制的背包問題。關(guān)鍵詞：HAMILTON回路 LINGO 最優(yōu)旅行路線 0-1模型二旅行問題問題描述 某人要在假期內(nèi)從城市A出發(fā)，乘火車或飛機(jī)到城市B,C,D,E,F旅游購物。他計(jì)劃走遍這些城市各一次且僅一次，最后返回城市A。已知城市間的路費(fèi)

2、數(shù)據(jù)見附表1，請你設(shè)計(jì)一條旅行路線使得他的總路費(fèi)最少。如果臨行他因故只能去4個(gè)城市，該怎樣修訂旅行路線？ 在城市間旅游時(shí)他計(jì)劃購買照相機(jī)，衣服，書籍，攝像機(jī)，漁具，白酒，食品，而受航空行李重量的限制以及個(gè)人體力所限，所買物品的總重量不能超過15kg，各種物品的價(jià)格見附表2.請你為他決策買哪些物品，使所買物品價(jià)值最大。附表1：ABCDEFA0120250330210150B120098350225300C250980520430280D3303505200270185E2102254302700420F1503002801854200附表2照相機(jī)衣服書籍?dāng)z像機(jī)漁具白酒食品香煙重量（kg）1243

3、4221價(jià)格(元)1300275032043501400300120600 模型設(shè)計(jì)首先給出一個(gè)定義：設(shè)v1,v2,.,vn是圖G中的n個(gè)頂點(diǎn)，若有一條從某一頂點(diǎn)v1出發(fā)，經(jīng)過各節(jié)點(diǎn)一次且僅一次，最后返回出發(fā)點(diǎn)v1的回路，則稱此回路為HAMILTON回路。 問題1.分析：這個(gè)優(yōu)化問題的目標(biāo)是使旅行的總費(fèi)用最少，要做的決策是如何設(shè)定旅行路線，決策受的約束條件：每個(gè)城市都必須去，但僅能去一次。按題目所給，將決定變量，目標(biāo)函數(shù)和約束條件用數(shù)學(xué)符號及式子表示出來，就可得一下模型。 模型建立：對于6個(gè)城市的旅行問題設(shè)A,B,C,D,E,F六個(gè)城市分別對應(yīng)v1,v2,v3,v4,v5,v6。假設(shè)表示從城市

4、i到城市j的費(fèi)用。定義0-1整數(shù)型變量=1表示從城市i旅行到城市j，否則=0。則旅行問題的數(shù)學(xué)模型可表示為一個(gè)整數(shù)規(guī)劃問題。 min z= (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)解中取普通的整數(shù)值（從而在約束條件中，可以限定這些變量為整數(shù)）。事實(shí)上，在最優(yōu)解中，=訪問城市的順序數(shù)。模型求解運(yùn)用LINGO，輸入程序：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CI

5、TY / 1.6/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric; COST= 0 120 250 330 210 150 120 0 98 350 225 300 250 98 0 520 430 280 330 350 520 0 270 185 210 225 430 270 0 420 150 3

6、00 280 185 420 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems; F

7、OR( CITY( J)| 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1);END得到結(jié)果：總費(fèi)用為1163路線：A-B-C-F-D-E-A問題2.臨時(shí)因故只能去4個(gè)城市，那么應(yīng)該怎樣安排旅行路線。分析：在B,C,D,E,F五個(gè)城市中選

8、4個(gè)城市，顯然有5種可能，按照問題一中的模型，將費(fèi)用矩陣稍作修改，運(yùn)用LINGO分別解除5種可能的費(fèi)用，進(jìn)行比較，即得結(jié)果。（1）選取B,D,E,F，計(jì)算旅行費(fèi)用：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CITY / 1.5/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matri

9、x, it need not be symmetric; COST= 0 120 330 210 150 120 0 350 225 300 330 350 0 270 185 210 225 270 0 420 150 300 185 420 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X

10、( K, J) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems; FOR( CITY( J)| 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K

11、) = 1 + ( N - 2) * X( K, 1);END得到結(jié)果：總費(fèi)用：950路線：A-B-E-D-F-A(2)選取B,C,E,F，計(jì)算旅行費(fèi)用：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CITY / 1.5/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it

12、 need not be symmetric; COST= 0 120 250 210 150 120 0 98 225 300 250 98 0 430 280 210 225 430 0 420 150 300 280 420 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J)

13、 = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems; FOR( CITY( J)| 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K) = 1 +

14、 ( N - 2) * X( K, 1);END得到結(jié)果：總費(fèi)用：963路線：A-E-B-C-F-A(3)選取B,C,D,F,計(jì)算旅行費(fèi)用：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CITY / 1.5/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need n

15、ot be symmetric; COST= 0 120 250 330 150 120 0 98 350 300 250 98 0 520 280 330 350 520 0 185 150 300 280 185 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J) = 1;!W

16、eak form of the subtour breaking constrains;!These are not very powerful for large problems; FOR( CITY( J)| 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N -

17、2) * X( K, 1);END得到結(jié)果：總費(fèi)用：1013路線：A-B-C-F-D-A(4)選取路線:B,C,D,E,計(jì)算旅行費(fèi)用：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CITY / 1.5/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not

18、be symmetric; COST= 0 120 250 330 210 120 0 98 350 225 250 98 0 520 430 330 350 520 0 270 210 225 430 270 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J) = 1;!Weak

19、 form of the subtour breaking constrains;!These are not very powerful for large problems; FOR( CITY( J)| 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N - 2)

20、* X( K, 1);END得到結(jié)果：總費(fèi)用：1173路線:A-C-B-E-D-A(5)選取C,D,E,F,計(jì)算旅行費(fèi)用：MODEL:!Traveling Sales Problem for the cities of six city;SETS: CITY / 1.5/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be sym

21、metric; COST= 0 250 330 210 150 250 0 520 430 280 330 520 0 270 185 210 430 270 0 420 150 280 185 420 0 ;ENDDATA N= SIZE( CITY); MIN= SUM( LINK: COST * X); FOR( CITY( K): !It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1;! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J) = 1;!Weak for

22、m of the subtour breaking constrains;!These are not very powerful for large problems; FOR( CITY( J)| 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); !Make the Xs 0/1;! For the first and last stop we know.;FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X(

23、 K, 1);END得到結(jié)果：總費(fèi)用：1195路線：A-C-F-D-E-A因此，總結(jié)以上（1），（2），（3），（4），（5）五種情況可得:應(yīng)該選用路線：A-B-E-D-F-A?？傎M(fèi)用花費(fèi)最少，為950.問題3.在城市間旅游時(shí)他計(jì)劃購買照相機(jī)、衣服、書籍、攝像機(jī)、漁具、白酒、食品、香煙等物品，而受航空行李重量的限制以及個(gè)人體力所限，所買物品的總重量不能超過15kg，各種物品的價(jià)格見附表2。請你為他決策買哪些物品，使所買物品總價(jià)值最大？分析:解讀題意，實(shí)際上此題涉及背包問題，題目轉(zhuǎn)化為一個(gè)限重15公斤的背包，要求在8件可帶可不帶的物品中做出合理的方法。模型建立：將照相機(jī)，衣服，書籍，攝像機(jī)，漁具

24、，酒，食品和香煙編號為1，2，3，4，5，6，7，8。設(shè)總?cè)萘繛閎,為每個(gè)物品的重量，為每個(gè)物品各自的價(jià)格。定義一個(gè)變量，當(dāng)=1是，表示裝第i件物品，當(dāng)=0時(shí)，則不裝（i=1,2,8）.則約束條件為：max z=0或1，（i=1,2,8）模型求解：利用LINGO軟件求解，在LINGO中輸入以下程序：model: sets: M/1.8/:W; price/1.8/:p; number/1.8/:x; endsets data: W=1,2,4,3,4,2,2,1; P=1300,2750,320,4350,1400,300,120,600; enddata MAX=SUM(M:X*P); SUM(M:X*W)=15; FOR(M: