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

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

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

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

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

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

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

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

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

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

10、是比較方便的。該游客是從第一個(gè)城市開始的，設(shè)游客走到第i個(gè)城市，記作：ni=2,3,4,、,i-1,i+1,、n表示由第1個(gè)城市到第i個(gè)城市的中間城市集合。s表示到達(dá)i城之前中途所經(jīng)過的城市集合，則有sui因此，可選?。╥，s）作為描述過程的狀態(tài)變量，決策為由一個(gè)城市走到另一個(gè)城市，并定義最優(yōu)值函數(shù)k(i,s)為從1城市開始經(jīng)由k個(gè)中間城市的s集到i城的最短路線的距離，則可寫出動(dòng)態(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、個(gè)城市開始經(jīng)k個(gè)中間城市的s集到第i城市的最短路線上緊相鄰著第i個(gè)城市前面的那個(gè)城市。5.1.2 模型假設(shè)查資料得火車(含高鐵)、長(zhǎng)途汽車或飛機(jī)，三種交通工具。其單位定價(jià)標(biāo)準(zhǔn)為飛機(jī)0.75元每公里（數(shù)據(jù)來源：中國(guó)民航局網(wǎng)站）;火車基本票價(jià)0.05861元每公里，對(duì)于加快票部分，普快十幾本票價(jià)的20%，快速是40%，空調(diào)是基本票價(jià)的25%，硬臥價(jià)上中下分別是基本票價(jià)的110%,120%,130%,軟臥上下是基本票價(jià)的175%，195%，再加30%的綜合費(fèi)用，動(dòng)車票價(jià)為0.375元每公里。（數(shù)據(jù)來源:2000年11月實(shí)施的鐵路旅客票價(jià)表數(shù)據(jù)顯示，單位旅程三種基本交通工具的基本費(fèi)用為飛機(jī)最貴，其次是

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

13、徐州常州青島北京太原洛陽(yáng)黃山漢口西安九江舟山?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 ,v

14、10 ），d13+f9（v3, v2， v4, v5，v6， v7 v 8,v9， v10），d19+f9（v9； v2， v3, v4， v5, v6， v7, v8，v10）先從最后一個(gè)階段求解。 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， ） 進(jìn)一步求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， v

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

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

18、m(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)青島-北京-太原-西安-洛陽(yáng)-九江-常州-舟山-黃山-徐州。通過對(duì)中國(guó)鐵路時(shí)刻表的查詢，得出：推薦方案為: 徐州-青島-北京-太原-西安-洛陽(yáng)-九江-常州-舟山-黃山-徐州.由此計(jì)算出總共消費(fèi)為：2689元如果時(shí)間不限，游客將十個(gè)景點(diǎn)全游覽完，滿足旅游費(fèi)用最少，旅游行程表如下：游客旅游路線圖字母順序既是旅游順序如下：5.2 問題二模型蟻群算法模型，tsp模型。5.2

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

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

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

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

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

24、 2643;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; pherom

25、one=ones(n,n); tabu_list=zeros(m,n); nc=0;%循環(huán)次數(shù)計(jì)數(shù)器routh_best=zeros(nc_max,n);%各次循環(huán)的最短路徑length_best=ones(nc_max,1);%各次循環(huán)最短路徑的長(zhǎng)度length_average=ones(nc_max,1);%各次循環(huán)所有路徑的平均長(zhǎng)度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=tab

26、u_list(i,1:(j-1);%已訪問的城市 city_remained=zeros(1,(n-j+1);%待訪問的城市 probability=city_remained;%待訪問城市的訪問概率 cr=1; for k=1:n%for循環(huán)用于求待訪問的城市。比如如果城市個(gè)數(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

27、.5;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由圖可以看出來旅游路線是一個(gè)閉合性的路線，不管從哪里起點(diǎn)，都是這樣一條最短路線。而且從收斂曲線上可以看出比較平穩(wěn)，沒有出現(xiàn)局部最優(yōu)解。由對(duì)式5.2.1的分析可知，在尋找花費(fèi)最短時(shí)間的路徑中，統(tǒng)籌考慮各個(gè)因素，進(jìn)而尋找出可行度高的最省事旅游方案。注：費(fèi)用單位（元），時(shí)間單位（小時(shí)）。通過對(duì)表的分析可知，旅游最短時(shí)間為6天零十個(gè)小時(shí)45分。

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

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

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

31、編程實(shí)現(xiàn)。針對(duì)本問題，我們做出從城市i到城市j旅行所需的全部費(fèi)用。如表（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=06270941063499395587152620150140165125731051656795701500116120125182168165170210941401160705318215015014535410616512070094

32、16710345146203341251259494011887286217199731821821671180641394591391051681501038764013751103551651651504528139137083216876717014514662455183011615295210354203171911032161160enddatamax=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注：運(yùn)行結(jié)果僅列出有用的那部分?jǐn)?shù)據(jù)。所以路徑為：v1-v3-v4-v5-v6-v9-v8-v7-v1。由結(jié)果可知該旅客的旅游路線應(yīng)為：徐州-青島-北京-太原-洛陽(yáng)-西安-武漢-黃山-徐州下面給出滿足要求的旅游方案。如表（5.3.2附）游客的旅游路線字

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

36、:level,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,2652

37、10,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

38、(i,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 variab

39、le 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注：只保留了部分有用的運(yùn)算結(jié)果。得出城市 v1 v2 v3 v4 v5 v6 v8 v9 但沒有得出最優(yōu)回路。從lingo運(yùn)行結(jié)果可以看出，在規(guī)定的時(shí)間內(nèi)，對(duì)應(yīng)的可以游覽的城市有：徐州，常州，青島，八達(dá)嶺，祁縣喬家，洛陽(yáng)，武漢，西安接下來，我們需要在這8個(gè)城市中選擇一條從徐州出發(fā)的最佳

41、旅游路徑，以上城市代碼和數(shù)值對(duì)應(yīng)關(guān)系如下表：12345678v1v2v3v4v5v6v7v8同樣借助于lingo軟件實(shí)現(xiàn)。程序如下：參照（表4.2.2），運(yùn)用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 ,94

42、3,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，對(duì)應(yīng)城市代碼：v1-v6-v3-v8-v5-v9-v2-v4-v1.由結(jié)果可知該旅客的旅游路線應(yīng)為：徐州-洛陽(yáng)-青島-武漢-祁縣喬家-西安-常州-八達(dá)嶺-徐州下面給出滿足要求的旅游方案。（如表5.4.2）游客的旅游路線圖字母順序既是旅游順序如下：5.5 問題五多目標(biāo)函數(shù)最優(yōu)化模型5.5.1 模型分析問題五是在雙重限制條件下，求最多能游覽景點(diǎn)數(shù)目。此問題屬于多目標(biāo)函數(shù)的最優(yōu)化問題。同樣可以借助于層次分析的思想，首先，找出在五天時(shí)間和2000元費(fèi)用限制下該旅客所能夠游覽