基于Lingo旅游計(jì)劃制定方法(含代碼)

1、海 南 大 學(xué)數(shù)學(xué)模型課程設(shè)計(jì)論文題目： 基于Lingo的旅游計(jì)劃制定方法 班級(jí)： 信息與計(jì)算科學(xué) 姓名： 體貼的瑾色 學(xué)號(hào)： 指導(dǎo)教師： 日期： 2017.06 目錄基于Lingo的旅游計(jì)劃制定方法2摘要2一、問題描述3二、模型假設(shè)3三、問題分析3四、符號(hào)說明4五、模型建立4六、問題解決6七、回答問題9八、模型推廣9九、心得體會(huì)10參考文獻(xiàn)10程序附錄10基于Lingo的旅游計(jì)劃制定方法摘要本文針對海南十八個(gè)城市制定旅游規(guī)劃，在收集了大量的數(shù)據(jù)情況下，建立評(píng)價(jià)指標(biāo)，找到最優(yōu)的旅游路線。對于問題一因?yàn)椴灰笄蟪鼍唧w的路程最小值，所以我們使用matlab處理海南省的地圖，找到每個(gè)城市在地圖的相對

2、坐標(biāo)，從而得到城市之間的相對距離。以距離為權(quán)，以旅程的長度為評(píng)價(jià)標(biāo)準(zhǔn)建立模型，規(guī)劃最優(yōu)路線得到最小相對距離1488。11，注意這里的最小距離并不是實(shí)際上的最小距離。對于問題二將最小費(fèi)用矩陣代替距離矩陣，以旅程的總車費(fèi)為評(píng)價(jià)標(biāo)準(zhǔn)建立模型，規(guī)劃最優(yōu)路線，得到最小費(fèi)用為276元。對于問題三，在一二問的基礎(chǔ)上，綜合考慮省時(shí)省錢，得到評(píng)價(jià)標(biāo)準(zhǔn)表達(dá)式，建立模型，規(guī)劃最優(yōu)路線。一、問題描述本題要求在不同的約束條件下規(guī)劃出海南的最佳旅游路線，路線的基本要求是必須從?？诔霭l(fā)并回到?？?，并且經(jīng)過且經(jīng)過海南的每個(gè)城市（包括縣城）一次，并且每個(gè)市縣玩兩天。不同的問題約束條件是：（1）要求總路程最短。（2）允許選擇動(dòng)車

3、和大巴作為出行工具，規(guī)劃的路線使得出行總交通費(fèi)用最少。（3）綜合考慮一二問的條件，得到最優(yōu)路線，設(shè)定出相應(yīng)的評(píng)價(jià)準(zhǔn)則和指標(biāo)，修正模型。二、模型假設(shè)（1） 城市之間路程用城市的直線距離代替。（2） 近期城市之間的動(dòng)車價(jià)格和大巴價(jià)格視為定值。（3） 城市之間路費(fèi)取自動(dòng)車價(jià)格和大巴價(jià)格的最小值。（4） 假設(shè)不同城市之間的交通工具的速度均相差不大，即旅行時(shí)間由旅行路程唯一決定。三、問題分析通過查詢知道海南的市縣數(shù)量總共是有18個(gè)（三沙市除外），那么顯然這個(gè)問題是一個(gè)18個(gè)城市的TSP問題。用圖論的內(nèi)容來等價(jià)話描述為：設(shè) 是一個(gè)有向賦權(quán)圖，其中將城市看做節(jié)點(diǎn)構(gòu)成頂點(diǎn)集，如果和之間存在邊，即表示制定的旅游

4、方案中是從城市到城市。表示邊所賦的非負(fù)權(quán)重。 那么該問題就是指在帶權(quán)有向圖中,尋找從指定起始節(jié)點(diǎn)的一條經(jīng)過且僅經(jīng)過一次所有節(jié)點(diǎn)的具有最小權(quán)值總和的閉合路徑。不同的問題中所賦的權(quán)重代表的內(nèi)容不同：（1） 問題一中，因?yàn)椴灰笄蟪鼍唧w的最小值，所以我們使用matlab處理海南省的地圖，找到每個(gè)城市在地圖的具體坐標(biāo)，從而得到城市之間的距離。以距離為權(quán)建立模型，規(guī)劃最優(yōu)路線。（2） 問題二中，針對不同城市間的交通條件，選擇合適的交通方式，通過互聯(lián)網(wǎng)票務(wù)查詢得到結(jié)果。（3） 問題三中，綜合考慮條件，設(shè)計(jì)出省時(shí)又省錢的最優(yōu)化路線。四、符號(hào)說明 城市與城市之間的距離（路程，費(fèi)用等） 與城市相對應(yīng)的任意實(shí)數(shù)

5、城市的數(shù)量 旅行車費(fèi) 旅行路程五、模型建立首先建立一二問的模型：目標(biāo)函數(shù)為： 保證從每個(gè)城市只離開一次： 保證只進(jìn)入每個(gè)城市一次： 變量約束： 但是滿足上述變量并不能保證找到最優(yōu)解，因?yàn)槿绻傻穆窂桨袃蓚€(gè)不連通的閉合子路徑，也滿足上述條件，但并不符合題意。所以還要增加約束使得不出現(xiàn)這種情況。文獻(xiàn)1中證明了如果滿足下述條件： 其中，那么能保證不出現(xiàn)獨(dú)立的閉合子路徑。城市之間的距離估算使用如下圖一所示海南省行政圖作為對象，使用matlab的ginput函數(shù)，找到每個(gè)市縣的具體坐標(biāo)，后如下圖二所示對城市進(jìn)行編號(hào)，計(jì)算得到城市之間的距離矩陣，結(jié)果如下圖三所示，注意這里并不需要考慮城市間是否有交通

6、工具來往，因?yàn)椴樵冎老嘟某鞘芯兄边_(dá)車次，只有部分相距較遠(yuǎn)的城市不可來往，而第一問要求的是路程最短，所以路線選擇只可能考慮相近城市來往。城市之間車費(fèi)是通過互聯(lián)網(wǎng)票務(wù)查詢系統(tǒng)按照模型假設(shè)收集，但是有部分城市之間并無直達(dá)車次，我們規(guī)定如果去其他城市轉(zhuǎn)乘次數(shù)不超過一次，那么這兩個(gè)城市間的車費(fèi)就是轉(zhuǎn)乘后的總車費(fèi)，若轉(zhuǎn)乘次數(shù)超過兩次，兩個(gè)城市就視為不能直接來往。在第二問中，因?yàn)橐笥?jì)算車費(fèi)最小的路線，所以我們規(guī)定不能直接來往的城市車費(fèi)記為10000元。數(shù)據(jù)結(jié)果顯示如下圖四。第三問要求綜合考慮省時(shí)，省錢，制定最優(yōu)方案。由假設(shè)條件知，本題的目標(biāo)函數(shù)應(yīng)該為：其中為區(qū)間的一個(gè)實(shí)數(shù)，但是因?yàn)槁烦毯唾M(fèi)用的量綱不

7、同，這樣得到的結(jié)果并不是很好，所以我們對目標(biāo)函數(shù)做一個(gè)修正，設(shè)一二問求得的最短的路程和最少的車費(fèi)分別為和，目標(biāo)函數(shù)（評(píng)價(jià)標(biāo)準(zhǔn)）為： 我們假設(shè)游客對省時(shí)和省錢同樣的看中，即，那么目標(biāo)函數(shù)為：本文的約束條件是一二問所有的約束條件。六、問題解決采用lingo編程（程序見附錄）求解得到第一問的矩陣使用matlab編程（程序見附錄）處理數(shù)據(jù)得到路線和路線圖為：路線：1432610913141516181712117851第二問模型求解后得到的軌跡圖為：路線為：1261310911714151816171285431第三問得到的軌跡圖為：路線為：1261310914151618171211734851靈敏

8、度分析：第三文中如果比較在意經(jīng)濟(jì)方面，那么令，則結(jié)果變?yōu)椋郝肪€為：1345812171816151471191013621如果經(jīng)濟(jì)比較寬裕，那么令，那么結(jié)果變?yōu)椋郝肪€為：1261310914151618171211785431七、回答問題回答問題（1）：要使路程最短，路線應(yīng)該設(shè)計(jì)為：?？?定安=澄邁=臨高=儋州=白沙=昌江=東方=樂東=五指山=保亭=三亞=陵水=萬寧=瓊中=屯昌=瓊海=文昌=?？诨卮饐栴}（2）：要使費(fèi)用最少，路線應(yīng)該規(guī)劃為：?？?臨高=儋州=東方=白沙=昌江=瓊中=屯昌=樂東=五指山=三亞=保亭=陵水=萬寧=瓊海=文昌=定安=澄邁=海口回答問題（3）：如果同等看重經(jīng)濟(jì)和時(shí)間則路

9、線為：?？?臨高=儋州=東方=白沙=昌江=樂東=五指山=保亭=三亞=陵水=萬寧=瓊中=屯昌=澄邁=定安=瓊海=文昌=海口如果較看重經(jīng)濟(jì)則路線為：?？?澄邁=定安=文昌=瓊海=萬寧=陵水=三亞=保亭=五指山=樂東=屯昌=瓊中=昌江=白沙=東方=儋州=臨高=?？谌绻^看重時(shí)間則路線為：海口=臨高=儋州=東方=白沙=昌江=樂東=五指山=保亭=三亞=陵水=萬寧=瓊中=屯昌=瓊海=文昌=定安=澄邁=?？诎?、模型推廣本文解決的問題是針對海南旅游，推廣到一般情況，某人計(jì)劃到個(gè)城市進(jìn)行旅游，要求分別從省時(shí)，省錢和綜合考慮兩個(gè)方面進(jìn)行規(guī)劃路線。設(shè)計(jì)劃決策變量為 ： 目標(biāo)函數(shù)為： 城市與城市之間的距離（路程，費(fèi)用

10、等）約束條件為： 九、心得體會(huì)通過本次建模實(shí)驗(yàn)，我對數(shù)學(xué)建模了解更加深刻了一些。本題開始我是通過使用遺傳算法解決，發(fā)現(xiàn)雖然收斂的十分迅速，但是進(jìn)入到了一個(gè)局部最優(yōu)解，始終找不到全局最優(yōu)解。然而使用數(shù)學(xué)建模的方法，找到約束條件，用lingo計(jì)算，很快的就找到了最優(yōu)解。所以，建模中算法并非最重要的，根本還是要實(shí)實(shí)在在的建立模型。參考文獻(xiàn)1王繼強(qiáng)。 基于LINGO的旅行商問題的建模方法J。 計(jì)算機(jī)工程與科學(xué),2014,(05):947-950。2姜啟源，謝金星。數(shù)學(xué)模型（第四版）。北京：高等教育出版社，2011，1。3謝金星，薛毅。LINGO軟件的基本使用方法。北京：清華大學(xué)出版社，2005，程序附

11、錄（因?yàn)榈谌龁柧C合了前兩問，所以本文只附求解第三問的程序）：sets:dian/1.18/:u; link(dian,dian):d,m,x;endsetsdata:m=ole(E:jianmo01。xlsx,data2);d=ole(E:jianmo01。xlsx,data1);enddatan=size(dian);min=(sum(link(i,j)|i#ne#j:d(i,j)*x(i,j)-1488。11)/1488。11*0。5+(sum(link(i,j)|i#ne#j:m(i,j)*x(i,j)-276)/276*0。5;m=ole(E:jianmo01。xlsx,data2);

12、!費(fèi)用矩陣;d=ole(E:jianmo01。xlsx,data1);!距離矩陣; for(dian(i):for(dian(j)|j#ne#i#and#j#gt#1:u(i)-u(j)+n*x(i,j); if i=18 hah=hah,海口; endendhah3。 (OutputPath):% 輸出路徑函數(shù)%輸入：R 路徑function p=OutputPath(R)R=R,R(1);N=length(R);p=num2str(R(1);for i=2:N p=p,num2str(R(i);enddisp(p)4。畫圖：function DrawPath(Chrom,X)R=Chrom(1,:) Chrom(1,1); %一個(gè)隨機(jī)解(個(gè)體)figure;hold onplot(X(:,1),X(:,2),o,color,0。5,0。5,0。5)plot(X(Chrom(1,1),1),X(Chrom(1,1),2),rv,MarkerSize,20)for i=1:size(X,1) text(X(i,1)+7,X(i,2)+10,num2str(i),color,1,0,0,FontSize,14);endA=X(