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

./理工學(xué)院數(shù)學(xué)建模大型作業(yè)2011—2012學(xué)年第1學(xué)期目錄一．摘要二．旅行問題問題描述符號(hào)說明模型設(shè)計(jì)建模求解模型分析三．建模過程及心得體會(huì)四．參考文件一．摘要本文是一個(gè)圍繞旅行商問題和背包問題這兩個(gè)經(jīng)典問題的論文。問題一,是一個(gè)依賴與每個(gè)城市去一次且僅去一次的路線確定問題,問題二類似于問題一。問題三是一個(gè)依賴于可背重量限制的背包問題。關(guān)鍵詞：HAMILTON回路LINGO最優(yōu)旅行路線0-1模型二．旅行問題問題描述某人要在假期從城市A出發(fā),乘火車或飛機(jī)到城市B,C,D,E,F旅游購物。他計(jì)劃走遍這些城市各一次且僅一次,最后返回城市A。已知城市間的路費(fèi)數(shù)據(jù)見附表1,請(qǐng)你設(shè)計(jì)一條旅行路線使得他的總路費(fèi)最少。如果臨行他因故只能去4個(gè)城市,該怎樣修訂旅行路線？在城市間旅游時(shí)他計(jì)劃購買照相機(jī),衣服,書籍,攝像機(jī),漁具,白酒,食品,而受航空行重量的限制以及個(gè)人體力所限,所買物品的總重量不能超過15kg,各種物品的價(jià)格見附表2.請(qǐng)你為他決策買哪些物品,使所買物品價(jià)值最大。附表1：ABCDEFA0120250330210150B120098350225300C250980520430280D3303505200270185E2102254302700420F1503002801854200附表2照相機(jī)衣服書籍?dāng)z像機(jī)漁具白酒食品香煙重量〔kg12434221價(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é)符號(hào)及式子表示出來,就可得一下模型。模型建立：對(duì)于6個(gè)城市的旅行問題設(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。則旅行問題的數(shù)學(xué)模型可表示為一個(gè)整數(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)解中取普通的整數(shù)值〔從而在約束條件中,可以限定這些變量為整數(shù)。事實(shí)上,在最優(yōu)解中,=訪問城市的順序數(shù)。模型求解運(yùn)用LINGO,輸入程序：MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..6/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=0120250330210150120098350225300250980520430280330350520027018521022543027004201503002801854200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;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>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;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è)城市中選4個(gè)城市,顯然有5種可能,按照問題一中的模型,將費(fèi)用矩陣稍作修改,運(yùn)用LINGO分別解除5種可能的費(fèi)用,進(jìn)行比較,即得結(jié)果。〔1選取B,D,E,F,計(jì)算旅行費(fèi)用：MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=01203302101501200350225300330350027018521022527004201503001854200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;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>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=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:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=012025021015012009822530025098043028021022543004201503002804200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;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>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<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:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=012025033015012009835030025098052028033035052001851503002801850;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;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>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到結(jié)果：總費(fèi)用：1013路線：A-B-C-F-D-A<4>選取路線:B,C,D,E,計(jì)算旅行費(fèi)用：MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=012025033021012009835022525098052043033035052002702102254302700;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;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>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到結(jié)果：總費(fèi)用：1173路線:A-C-B-E-D-A<5>選取C,D,E,F,計(jì)算旅行費(fèi)用：MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=02503302101502500520430280330520027018521043027004201502801854200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;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>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<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。請(qǐng)你為他決策買哪些物品,使所買物品總價(jià)值最大？分析:解讀題意,實(shí)際上此題涉及背包問題,題目轉(zhuǎn)化為一個(gè)限重15公斤的背包,要求在8件可帶可不帶的物品中做出合理的方法。模型建立：將照相機(jī),衣服,書籍,攝像機(jī),漁具,酒,食品和香煙編號(hào)為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.則約束條件為：maxz==0或1,〔i=1,2,……,8模型求解：利用LINGO軟件求解,在LINGO中輸入以下程序：model:sets:M/1..8/:W;price/1..8/:p;number/1..8/:x;endsetsda