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

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

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

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

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

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

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

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

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

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

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

11、錄（因為第三問綜合了前兩問，所以本文只附求解第三問的程序）：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、!費用矩陣;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); %一個隨機解(個體)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(