旅游線路的優(yōu)化設(shè)計

1、2011年第八屆蘇北數(shù)學(xué)建模聯(lián)賽題 目 b題 旅游線路的優(yōu)化設(shè)計摘要隨著社會的發(fā)展，旅游日益成為現(xiàn)實社會的熱點，為了得到一個比較實惠的旅游方案，我們需要有一套比較完善的預(yù)算體系，建立這樣一套體系是一個多目標(biāo)的決策問題。這一問題的重點在于將經(jīng)濟、時間等因素融入預(yù)算體系，使得預(yù)算的一個旅游方案更完善、更合理。本文主要研究最佳旅游路線的設(shè)計問題。在滿足相關(guān)約束條件的情況下，花最少的錢游覽盡可能多的景點是我們追求的目標(biāo)。基于對此的研究，建立數(shù)學(xué)模型，設(shè)計出最佳的旅游路線。為了提出合適的旅游路線，本文選擇了合適的模型，得到合適的路線，并給出了一些結(jié)果。第一問游完10個景點，且要費用最少。為此，我們建立旅

2、行商模型，以消費最低為目標(biāo)，再輔以lingo軟件編程對模型求解，從而推出旅游路線，再根據(jù)具體的旅游路線計算出總費用。推薦方案為: 徐州-青島-北京-太原-西安-洛陽-九江-常州-舟山-黃山-徐州.由此計算出總消費為：2689元第二問要在費用不限，且需的最短時間的方案。該問題可以以運籌學(xué)有關(guān)最優(yōu)化和圖論的相關(guān)知識為基礎(chǔ)，建立基于蟻群模型為基礎(chǔ)的優(yōu)化模型。輔以matlab編程得到最佳路線為：徐州洛陽舟山九江黃山青島武漢祁縣西安北京徐州。按此路線，總共費用為：9908。旅游最短時間為6天零十個小時45分。 第三問時間充裕，要求費用低于2000元，把各景點看成純數(shù)學(xué)中的點，利用應(yīng)用圖論中的思想，尤其是

3、dijkstra算法模型求解。在建模中，把各景點間的路費和門票作為巡回圖邊的鄰接矩陣權(quán)，使原題變圖論中的求最短連通圖問題，利用lingo軟件求解得到旅游路線應(yīng)為：徐州-青島-北京-太原-洛陽-西安-武漢-黃山-徐州。最少費用為:1945元。第四問給定五天的時間約束，我們借助于層次分析法的思想，先找出適合游覽的景點，在確定最終旅游方案。利用lingo編程進行求解，從而得到旅游路線為：徐州-洛陽-青島-武漢-祁縣喬家-西安-常州-八達(dá)嶺-徐州。由此計算出總費用為:6775元第五問是在雙重限定條件下，求最多能游覽景點數(shù)目并確定旅游方案。此問題屬于多目標(biāo)函數(shù)的最優(yōu)化問題。同樣借助lingo編程對模型進

4、行求解，得到最優(yōu)的旅游路線為: 徐州-北京-太原-西安-洛陽-漢口-常州-徐州花費時間為：5.1號5.5號20:39，在五天內(nèi)， 總共費用為：1765元。關(guān)鍵字：旅行商 tsp 層次分析法 圖論 蟻群算法 dijkstra算法一、問題重述隨著人們的生活不斷提高，旅游已成為提高人們生活質(zhì)量的重要活動。江蘇徐州有一位旅游愛好者打算現(xiàn)在的今年的五月一日早上8點之后出發(fā)，到全國一些著名景點旅游，最后回到徐州。由于跟團旅游會受到若干限制，他(她)打算自己作為背包客出游。他預(yù)選了十個省市旅游景點，如表1所示。表1. 預(yù)選的十個省市旅游景點省市景點名稱在景點的最短停留時間江蘇常州市恐龍園4小時山東青島市嶗山

5、6小時北京八達(dá)嶺長城3小時山西祁縣喬家大院3小時河南洛陽市龍門石窟3小時安徽黃山市黃山7小時湖北武漢市黃鶴樓2小時陜西西安市秦始皇兵馬俑2小時江西九江市廬山7小時浙江舟山市普陀山6小時假設(shè)：(a) 城際交通出行可以乘火車(含高鐵)、長途汽車或飛機（不允許包車或包機），并且車票或機票可預(yù)訂到。(b) 市內(nèi)交通出行可乘公交車(含專線大巴、小巴)、地鐵或出租車。(c) 旅游費用以網(wǎng)上公布為準(zhǔn)，具體包括交通費、住宿費、景點門票(第一門票)。晚上20：00至次日早晨7：00之間，如果在某地停留超過6小時，必須住宿，住宿費用不超過200元/天。吃飯等其它費用60元/天。(d) 假設(shè)景點的開放時間為8:00

6、至18:00。問題：根據(jù)以上要求，針對如下的幾種情況，為該旅游愛好者設(shè)計詳細(xì)的行程表，該行程表應(yīng)包括具體的交通信息(車次、航班號、起止時間、票價等)、賓館地點和名稱，門票費用，在景點的停留時間等信息。(1) 如果時間不限，游客將十個景點全游覽完，至少需要多少旅游費用？請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。(2) 如果旅游費用不限，游客將十個景點全游覽完，至少需要多少時間？請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。(3) 如果這位游客準(zhǔn)備2000元旅游費用，想盡可能多游覽景點，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。(4) 如果這位游客只有5天的時間，想盡可能多游覽景點，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。

7、(5) 如果這位游客只有5天的時間和2000元的旅游費用，想盡可能多游覽景點，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。二、問題分析這其實是一個旅行商問題。此類問題又常被描述為旅行推銷員問題，貨郎擔(dān)問題，簡稱tsp問題。是最典型的最短路徑問題。該問題要求尋求旅行商從某一點出發(fā)，經(jīng)過所給定的點以后，再回到出發(fā)點的最短路徑。題目中所要求的費用最少、時間最短，從本質(zhì)上來講，都是此類問題的簡單推廣。三、問題假設(shè)1、火車票價與火車行駛里程成正比；2、天氣良好，至少不會對列車運行造成影響；3、最短旅游路徑是一個回路4、乘坐公交車去一旅游景點游玩，一般情況下，所需公交運費為5元；5、不考慮旅游者滿意度問題。6.每

8、天伙食費達(dá)到最高標(biāo)準(zhǔn)60元/天。四、符號說明符號符號意義符號符號意義ni第1個城市到第i個城市的中間城市集合s到達(dá)i城之前中途所經(jīng)過的城市集合（i，s）描述過程的狀態(tài)變量k(i,s)從1城市開始由k各中間城市的s集到第i城市的最短路線上緊相鄰著第i城市前面那個城市。vi第i個城市xk(i)=pk(i,s)決策函數(shù)dij從i到j(luò)城的距離t旅行的總耗時t0乘坐旅行工具所耗費時間tp在旅游景點停留所花費時間tw1等待旅游景點開放所花費時間tw2等待列車所花費時間minf(x)|xsf為目標(biāo)函數(shù)，s為可行解集合m算法中螞蟻的數(shù)量d（i，j=1,2,3，n）表示邊（i，j）之間的距離(此處表示兩城市之間

9、乘坐飛機所需的近似最短時間)n城市個數(shù) t時刻在（i，j）上殘留的信息素量更新后邊上的信息素量更新前邊上的信息素量第只螞蟻本次循環(huán)中留在邊上的信息素量本次循環(huán)中邊上的信息量增量常數(shù)第只螞蟻在本次循環(huán)中所走過的路徑長度gai,j=maxintvi，vj是不關(guān)聯(lián)的，否則為權(quán)值（大于0的實數(shù)）dist1.n當(dāng)前求得的最短路徑pay各景點門票cost各城市間路費time各城市交通所花時間五、模型建立與求解5.1 問題一模型：旅行商動態(tài)規(guī)劃模型5.1.1模型分析：問題一需要確定在時間不限的情況下,游客要想把十個景點全瀏覽完，至少需要的旅游費用。這個問題屬于組合優(yōu)化問題，此處采用動態(tài)規(guī)劃的遞推方法求解是比

10、較方便的。該游客是從第一個城市開始的，設(shè)游客走到第i個城市，記作：ni=2,3,4,、,i-1,i+1,、n表示由第1個城市到第i個城市的中間城市集合。s表示到達(dá)i城之前中途所經(jīng)過的城市集合，則有sui因此，可選取（i，s）作為描述過程的狀態(tài)變量，決策為由一個城市走到另一個城市，并定義最優(yōu)值函數(shù)k(i,s)為從1城市開始經(jīng)由k個中間城市的s集到i城的最短路線的距離，則可寫出動態(tài)規(guī)劃的推遞關(guān)系為：k(i,s)=mink-1(j,sj)+dji （式5.1.1）(k=1,2,n-1；i=2,3,n.) sui邊界條件為0(i,)=d1i，這里為空集。設(shè)pk（i，s）為最優(yōu)決策函數(shù)，它表示從第一個城

11、市開始經(jīng)k個中間城市的s集到第i城市的最短路線上緊相鄰著第i個城市前面的那個城市。5.1.2 模型假設(shè)查資料得火車(含高鐵)、長途汽車或飛機，三種交通工具。其單位定價標(biāo)準(zhǔn)為飛機0.75元每公里（數(shù)據(jù)來源：中國民航局網(wǎng)站）;火車基本票價0.05861元每公里，對于加快票部分，普快十幾本票價的20%，快速是40%，空調(diào)是基本票價的25%，硬臥價上中下分別是基本票價的110%,120%,130%,軟臥上下是基本票價的175%，195%，再加30%的綜合費用，動車票價為0.375元每公里。（數(shù)據(jù)來源:2000年11月實施的鐵路旅客票價表數(shù)據(jù)顯示，單位旅程三種基本交通工具的基本費用為飛機最貴，其次是長途

12、汽車，最便宜的是火車硬座。為了實現(xiàn)費用最省，我們采用全程均用火車（硬座）為交通工具的方案。基于以上資料我們做了如下假設(shè); 1.火車票價與火車行駛里程成正比,由求解最短路徑求得最省錢方案；2.城市間來回里程相同。5.1.3 模型求解在鐵道部的網(wǎng)站上可以查詢出題目所給定的城市之間的距離里程（如表5.1.1）旅游城市距離（單位：公里）（表5.1.1）根據(jù)上表的距離，并基于我們所提出的假設(shè)。在具體實現(xiàn)上，根據(jù)圖論和組合最優(yōu)化中的哈密頓問題，得出以下求解過程：設(shè)vi表示第i個城市，i=1,2,3,4,5,6,7,8,9,10,11.與城市對應(yīng)關(guān)系如下：v1v2v3v4v5v6v7v8v9v10v11徐州

13、常州青島北京太原洛陽黃山漢口西安九江舟山?jīng)Q策函數(shù)記為xk(i)=pk(i,s),那么f10(v1,v2,v3,v4,v5,v6,v7,v8,v9,v10)表示從v1出發(fā)經(jīng)過v2,v3,v4,v5,v6,v7,v8,v9,v10各一次，最后回到v1的最短路程，利用公式（5.1.1）:得到:f3（v1，v2，v3，v4）=mind12+f2（v2， v3， v4），d13+f2（v3； v2， v4），d14+f2（v4； v2， v3）f10（v1，v2，v3，v4，v5，v6，v7 ,v8，v9，v10，）=mind12+f9（v2， v3， v4, v5，v6, v7,v8, v9 ,v10

14、 ），d13+f9（v3, v2， v4, v5，v6， v7 v 8,v9， v10），d19+f9（v9； v2， v3, v4， v5, v6， v7, v8，v10）先從最后一個階段求解。 f0（v2， ）=d21f0（v3， ）=d31 f0（v4， ）=d41 以上分別從v2，v3，v4，v5，v6，v7 ,v8，v9，v10，直接到v1距離。f1（v2， v3）=d23+ f0（v3， ）f1（v2， v4）=d24+ f0（v4， ）f1（v3， v2）=d32+ f0（v2， ）f1（v3， v4）=d34+ f0（v4， ）f1（v4， v2）=d42+ f0（v2， ）

15、f1（v4， v3）=d43+ f0（v3， ） 進一步求f2（v2， v3， v4）=min d23+f1（v3， v4），d24+f1（v4， v3）f2（v3， v4， v2）=min d32+f1（v2， v4），d34+f1（v4， v2）f2（v4， v2， v3）=min d42+f1（v2， v3），d43+f1（v3， v2）最后求f10（v1，v2，v3，v4，v5，v6，v7 ,v8，v9，v10，）=mind12+f9（v2， v3， v4, v5，v6, v7,v8, v9 ,v10 ），d13+f9（v3, v2， v4, v5，v6， v7 v 8,v9， v10

16、），d19+f9（v9； v2， v3, v4， v5, v6， v7, v8，v10）得出最短路長，再來求最短路程，運用以上思想和數(shù)據(jù)，輔以lingo進行運算，編程如下：model:sets:city/1.11/:u;link(city,city):dist,x;endsetsdata:dist=048471281484847371956486062211004840119512881332956506655134413661671211950888922962154315771349139418008141288888050881215331196120013141910848133292

17、250807921530109365113891848473956962812792011036403879641442719506154315331530110307511500604705564655157711961093640751010273281080860134413491200651387150010270110217206221361394131413899646043281102090511006161800191018481442705108017209050enddatan=size(city);min=sum(link:dist*x);for(city(k):sum(

18、city(i):x(i,k)=1;);for(city(k):sum(city(j):x(k,j)=1;);for(city(k):for(city(j)|j#gt#1#and#k#gt#1:u(j)-u(k)+n*x(j,k)青島-北京-太原-西安-洛陽-九江-常州-舟山-黃山-徐州。通過對中國鐵路時刻表的查詢，得出：推薦方案為: 徐州-青島-北京-太原-西安-洛陽-九江-常州-舟山-黃山-徐州.由此計算出總共消費為：2689元如果時間不限，游客將十個景點全游覽完，滿足旅游費用最少，旅游行程表如下：游客旅游路線圖字母順序既是旅游順序如下：5.2 問題二模型蟻群算法模型，tsp模型。5.2.1

19、 模型分析問題二需要確定在費用不限的情況下,游客要想把十個景點全瀏覽完，至少需要的旅行時間。這個問題可以以運籌學(xué)有關(guān)最優(yōu)化和圖論的相關(guān)知識為基礎(chǔ)，建立基于蟻群模型為基礎(chǔ)的優(yōu)化模型。旅行的總耗時t=乘坐旅行工具所耗費時間t0+在旅游景點停留所花費時間tp+等待旅游景點開放所花費時間tw1+等待列車所花費時間tw2 式5.2.1在相互關(guān)聯(lián)、相互制約的限制因素中，乘坐旅行工具所耗費時間to，及在旅游景點停留所花費時間tp比較易于控制，基于我們所做出的假設(shè)，所以應(yīng)從乘坐旅行工具所耗費時間to盡可能短著手，以to為自變量建立最優(yōu)化模型。一般來說，此類問題可以表述為：minf(x)|xs其中，f為目標(biāo)函數(shù)

20、，s為可行解集合。注意，可行解的數(shù)目必須是有限多個。顯然，是可以通過枚舉法求解此類問題。但在最壞的情況下，這類問題的復(fù)雜度是指數(shù)級的，在限定的時間內(nèi)不能完成，因此，另辟蹊徑，借助有基于蟻群的matlab算法求解。m表示算法中螞蟻的數(shù)量，d（i，j=1,2,3，n）表示邊（i，j）之間的距離(此處表示兩城市之間乘坐飛機所需的近似最短時間)，（參見表4.2.1），n為城市個數(shù)，表示t時刻在（i，j）上殘留的信息素量，初始時刻各邊信息素量相等。螞蟻k在t時刻由城市i轉(zhuǎn)移到城市j的概率為 p （1）式中：為先驗知識或能見度，針對具體問題根據(jù)啟發(fā)式規(guī)則而定；為邊上殘留信息的重要程度；為啟發(fā)信息的重要程度

21、；為螞蟻的禁忌表即螞蟻所走過的城市集。隨著時間的推移，以前螞蟻留下的信息逐漸消逝，用參數(shù)表示信息素的揮發(fā)率，當(dāng)螞蟻完成1次循環(huán)后，個路徑上的信息量根據(jù)下列公式作調(diào)整 （2） （3） （4）式中：表示更新后邊上的信息素量；表示更新前邊上的信息素量；表示第只螞蟻本次循環(huán)中留在邊上的信息素量；表示本次循環(huán)中邊上的信息量增量；為常數(shù)；表示第只螞蟻在本次循環(huán)中所走過的路徑長度。當(dāng)周游次數(shù)達(dá)到設(shè)定值是算法結(jié)束。旅行時間最小表表4.2.1注：為了使實驗數(shù)據(jù)更加合理，選擇航班時刻表中的中位數(shù)作為去往各地的最短時間。5.2.2 模型求解 在利用蟻群算法進行旅游模型的計算式，我們利用了matlab軟件。我們利用m

22、atlab進行編程，運用size函數(shù)，zeros函數(shù)等一些matlab常用函數(shù)，對蟻群算法進行編程實現(xiàn)。其中 c表示 n個城市的坐標(biāo)，n2的矩陣；nc_max 最大迭代次數(shù)；m 螞蟻個數(shù)；alpha 表征信息素重要程度的參數(shù)；beta 表征啟發(fā)式因子重要程度的參數(shù)； rho 信息素蒸發(fā)系數(shù)；q 信息素增加強度系數(shù)；r_best 各代最佳路線； l_best 各代最佳路線的長度； 編寫acatsp(c,nc_max,m,alpha,beta,rho,q)函數(shù)，由蟻群算法的原理分四部分處理：m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游 ；計算待選城市的概率分布；記錄本次迭代最佳路線；更新信息素

23、。利用matlab軟件編程程序（部分）如下：clear all close all clc m=31; c=1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;4196 1004; 4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;1332 695;3715 1678; 3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2367; 3394 2

24、643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975;%城市的坐標(biāo)矩陣nc_max=200; alpha=1; beta=5; rho=0.5; q=100; n=size(c,1);%表示tsp問題的規(guī)模，亦即城市的數(shù)量d=ones(n,n);%表示城市完全地圖的賦權(quán)鄰接矩陣，記錄城市之間的距離for i=1:n for j=1:n if ij d(i,j)=sqrt(c(i,1)-c(j,1)2+(c(i,2)-c(j,2)2); end d(j,i)=d(i,j); endendeta=1./d; pheromon

25、e=ones(n,n); tabu_list=zeros(m,n); nc=0;%循環(huán)次數(shù)計數(shù)器routh_best=zeros(nc_max,n);%各次循環(huán)的最短路徑length_best=ones(nc_max,1);%各次循環(huán)最短路徑的長度length_average=ones(nc_max,1);%各次循環(huán)所有路徑的平均長度while ncnc_max rand_position=; for i=1:ceil(m/n) rand_position=rand_position,randperm(n); end for j=2:n for i=1:m city_visited=tabu_

26、list(i,1:(j-1);%已訪問的城市 city_remained=zeros(1,(n-j+1);%待訪問的城市 probability=city_remained;%待訪問城市的訪問概率 cr=1; for k=1:n%for循環(huán)用于求待訪問的城市。比如如果城市個數(shù)是5，而已訪問的城市city_visited=2 4,則經(jīng)過此for循環(huán)后city_remanied=1 3 5 if length(find(city_visited=k)=0 city_remained(cr)=k; cr=cr+1; end end 然后設(shè)置初始量m=11;alpha=1;beta=5;rho=0.5

27、;nc_max=200;q=100;得到的結(jié)果是shortest_path=8 5 9 2 4 1 6 11 10 7 3旅游的線路圖figure of length_best and ength_averagefigure of shortest path由圖可以看出來旅游路線是一個閉合性的路線，不管從哪里起點，都是這樣一條最短路線。而且從收斂曲線上可以看出比較平穩(wěn)，沒有出現(xiàn)局部最優(yōu)解。由對式5.2.1的分析可知，在尋找花費最短時間的路徑中，統(tǒng)籌考慮各個因素，進而尋找出可行度高的最省事旅游方案。注：費用單位（元），時間單位（小時）。通過對表的分析可知，旅游最短時間為6天零十個小時45分。5.

28、3 問題三模型：dijkstra算法模型, 最短路徑模型5.3.1 模型分析問題三需要確定在2000元旅游費用的限制條件下，最多能夠游覽多少景點。從對問題一及問題二的求解過程中可知，乘坐單次單程火車返回徐州所花費的費用fo基本相同，大致都可以為100元，那么可以把這個問題構(gòu)建為單源點下的最短路徑模型。即有11個城市，編號為1、211，每個城市之間的路徑長度保存在二位數(shù)組a中，如aij表示從城市i與城市j的旅行所需的全部費用。令sum=(ij)+f0式（5.3.1）應(yīng)該求得滿足sum=2000元的情況下， j取值個數(shù)的最大值。針對這一問題，我們應(yīng)用圖論中的dijkstra算法求解，對于一個含有1

29、1個頂點的完全圖，從某一個頂點vi到其余頂點vj的最短路徑。設(shè)圖g用鄰接矩陣的方式存儲在ga中，gai,j=maxint表示vi，vj是不關(guān)聯(lián)的，否則為權(quán)值（大于0的實數(shù)）。設(shè)集合s用來保存已求得最短路徑的終點序號，初始時s=vi表示只有源點，以后每求出一個終點vj，就把它加入到集合中并作為新考慮的中間頂點。設(shè)數(shù)組dist1.n用來存儲當(dāng)前求得的最短路徑，并不斷檢查這些最短路徑是否滿足式（3.2.1）。執(zhí)行時，先從源點以外的頂點（即待求出最短路徑的終點）所對應(yīng)的dist數(shù)組元素中，找出其值最小的元素（假設(shè)為distm），該元素值就是從源點vi到終點vm的最短路徑長度，對應(yīng)的pathm中的頂點或

30、邊的序列即為最短路徑。接著把vm并入集合s中，然后以vm作為新考慮的中間頂點，即可求得更短的路徑，則用它代替distj，同時把vj或邊（vm，vj）并入到pathj中。重復(fù)以上過程n-2次，即可在dist數(shù)組中得到從源點到其余各終點的最段路徑長度，對應(yīng)的path數(shù)組中保存著相應(yīng)的最段路徑。5.3.2 模型假設(shè)基于以上分析作如下假設(shè)： 1一個城市中市內(nèi)交通工具為公交，5元標(biāo)準(zhǔn)。 2.lingo程序中城市個數(shù)n近似看作游覽了n天，去除其他費用400，得出上限值。5.3.3 模型求解。在利用dijkstra算法進行最短連通圖模型的計算，可以借助lingo軟件。利用lingo進行編程，對該問題進行編程

31、實現(xiàn)。針對本問題，我們做出從城市i到城市j旅行所需的全部費用。如表（5.3.2）表（5.3.2）利用上述數(shù)據(jù)，lingo程序如下：model:sets: city/1.11/:level,pay,y; link(city,city):x,cost;endsetsdata:pay= 0 160 90 45409080230180200120;cost=0627094106349939558715262015014016512573105165679570150011612012518216816517021094140116070531821501501453541061651207009416

32、710345146203341251259494011887286217199731821821671180641394591391051681501038764013751103551651651504528139137083216876717014514662455183011615295210354203171911032161160enddatamax=sum(city:y);sum(link(i,j)|i #ne# j: cost(i,j)*x(i,j)+sum(city:pay*y)=level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i); );)

33、;for(city(i)|i #gt# 1: level(i)=1+(n-2)*x(i,1););endlocal optimal solution found. objective value: 8.000000 objective bound: 8.000000 infeasibilities: 0.000000 extended solver steps: 136 total solver iterations: 42429 variable value reduced cost n 8.000000 0.000000x( 1, 3) 1.000000 0.000000x( 3, 4)

34、1.000000 0.000000x( 4, 5) 1.000000 0.000000x( 5, 6) 1.000000 0.000000x( 6, 9) 1.000000 0.000000x( 7, 1) 1.000000 0.000000x( 8, 7) 1.000000 0.000000x( 9, 8) 1.000000 0.000000注：運行結(jié)果僅列出有用的那部分?jǐn)?shù)據(jù)。所以路徑為：v1-v3-v4-v5-v6-v9-v8-v7-v1。由結(jié)果可知該旅客的旅游路線應(yīng)為：徐州-青島-北京-太原-洛陽-西安-武漢-黃山-徐州下面給出滿足要求的旅游方案。如表（5.3.2附）游客的旅游路線字母順

35、序既是旅游順序：5.4 問題四模型：層次分析法模型5.4.1 模型分析問題四需要確定在規(guī)定的時間限制條件下，最多能夠游覽多少景點。通過對第二問的分析，很明顯可以看出，在五天的時間內(nèi)，不可能把全部的旅游景點都游玩一邊。因此，可以借助于層次分析法的思想，將此問題分為兩個步驟來考慮。首先，找出在五天內(nèi)所能夠游覽的景點，；其次，選擇最優(yōu)的旅游路線。5.4.2 由以上思想作如下假設(shè)： 1.五天內(nèi)可利用與旅游時間小于2400分鐘。5.4.2 模型求解針對本問題，結(jié)合上述的模型分析，要先從十個景點中，選擇出可以游覽的城市。在此，借助于lingo程序。程序如下：model:sets: city/1.11/:l

36、evel,pay,y; link(city,city):x,cost;endsetsdata:pay= 0 240 360 180180 180420 120 120420 360;cost=0,280,250,70,310,195,248,225,297,250,180290,0,240,105 ,1078, 255,170,270,110,180,210240,944,0,50,697,245,180,115,115,225,24570,130,80,0,60,95,120,130,110,135,130240,1155,669,65,0,225,240,943,70,245,265210

37、,275,225,80,225,0,220,210,240,200,190170,240,160,120,220,230,0,195,110,135,225230,260,100,115,80,220,240,0,75,155,210255,115,100,100,110,230,100,70,0,240,220255,190,210,130,245,200,155,160,240,0,145180,265,250,300,300,195,200,230,230,180,0;enddatamax=sum(city:y);sum(link(i,j)|i #ne# j: cost(i,j)*x(i

38、,j)+sum(city:pay*y)=level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i); ););for(city(i)|i #gt# 1: level(i)=1+(n-2)*x(i,1););endlocal optimal solution found. objective value: 8.000000 objective bound: 8.000000 infeasibilities: 0.2998640e-06 extended solver steps: 46 total solver iterations: 115277 variable

39、 value reduced cost n 2.000000 0.000000 y( 1) 1.000000 -1.000000 y( 2) 1.000000 -1.000000 y( 3) 1.000000 -1.000000 y( 4) 1.000000 -1.000000 y( 5) 1.000000 -1.000000 y( 6) 1.000000 -1.000000 y( 8) 1.000000 -1.000000 y( 9) 1.000000 -1.000000 x( 1, 6) 1.000000 0.000000 x( 2, 9) 1.000000 0.000000 x( 3,

40、8) 1.000000 0.000000 x( 4, 5) 1.000000 0.000000 x( 5, 4) 1.000000 0.000000 x( 6, 1) 1.000000 0.000000 x( 8, 3) 1.000000 0.000000 x( 9, 2) 1.000000 0.000000注：只保留了部分有用的運算結(jié)果。得出城市 v1 v2 v3 v4 v5 v6 v8 v9 但沒有得出最優(yōu)回路。從lingo運行結(jié)果可以看出，在規(guī)定的時間內(nèi)，對應(yīng)的可以游覽的城市有：徐州，常州，青島，八達(dá)嶺，祁縣喬家，洛陽，武漢，西安接下來，我們需要在這8個城市中選擇一條從徐州出發(fā)的最佳旅游

41、路徑，以上城市代碼和數(shù)值對應(yīng)關(guān)系如下表：12345678v1v2v3v4v5v6v7v8同樣借助于lingo軟件實現(xiàn)。程序如下：參照（表4.2.2），運用lingo程序得出如下model:sets:city/1.8/:u;link(city,city):dist,x;endsetsdata:dist= 0,280,250,70,310,195 ,225,297 290,0,240,105 ,1078, 255 ,270,110 240,944,0,50,697,245, 115,115 70,130,80,0,60,95, 130,110 240,1155,669,65,0,225 ,943,

42、70 210,275,225,80,225,0 ,210,240 230,260,100,115,80,220, 0,75 255,115,100,100,110,230, 70,0 ;enddatan=size(city);min=sum(link:dist*x);for(city(k):sum(city(i):x(i,k)=1;);for(city(k):sum(city(j):x(k,j)=1;);for(city(k):for(city(j)|j#gt#1#and#k#gt#1:u(j)-u(k)+n*x(j,k)6-3-7-5-8-2-4-1，對應(yīng)城市代碼：v1-v6-v3-v8-v5-v9-v2-v4-v1.由結(jié)果可知該旅客的旅游路線應(yīng)為：徐州-洛陽-青島-武漢-祁縣喬家-西安-常州-八達(dá)嶺-徐州下面給出滿足要求的旅游方案。（如表5.4.2）游客的旅游路線圖字母順序既是旅游順序如下：5.5 問題五多目標(biāo)函數(shù)最優(yōu)化模型5.5.1 模型分析問題五是在雙重限制條件下，求最多能游覽景點數(shù)目。此問題屬于多目標(biāo)函數(shù)的最優(yōu)化問題。同樣可以借助于層次分析的思想，首先，找出在五天時間和2000元費用限制下該旅客所能夠游覽的景點，；其次，