最佳旅游路線設(shè)計(jì)第三組11.問(wèn)題描述今年暑假，西南交通大學(xué)數(shù)學(xué)系要召開(kāi)“××學(xué)術(shù)議”，屆時(shí)來(lái)自國(guó)內(nèi)外的許多著名學(xué)者都會(huì)相聚成都。在會(huì)議結(jié)束后，主辦方希望能安排這些遠(yuǎn)道而來(lái)的貴賓參觀四川省境內(nèi)的著名自然和人文景觀，初步設(shè)想有如下線路可供選擇：一號(hào)線：成都→九寨溝、黃龍；二號(hào)線：成都→樂(lè)山、峨嵋；三號(hào)線：成都→四姑娘山、丹巴；四號(hào)線：成都→都江堰、青城山；五號(hào)線：成都→海螺溝、康定；每條線路中的景點(diǎn)可以全部參觀，也可以參觀其中之一。不僅如此，一起參觀景點(diǎn)的人數(shù)越多，每人承擔(dān)的費(fèi)用也會(huì)越小。2結(jié)合上述要求，請(qǐng)你回答下列問(wèn)題：一、請(qǐng)你們?yōu)橹鬓k方設(shè)計(jì)合適的旅游路線，使會(huì)議代表在會(huì)議結(jié)束后的10天時(shí)間內(nèi)花最少的錢(qián)游盡可能多的地方。二、如果有一些會(huì)議代表的時(shí)間非常充裕（比如一個(gè)月），他們打算將上述旅游景點(diǎn)全部參觀完畢后才離開(kāi)四川，請(qǐng)你們?yōu)樗麄冊(cè)O(shè)計(jì)合適的旅游路線，使在四川境內(nèi)的交通費(fèi)用盡量地節(jié)省。三、主辦方在會(huì)議開(kāi)始前對(duì)所有參會(huì)的100位代表旅游意向進(jìn)行了調(diào)查，調(diào)查數(shù)據(jù)見(jiàn)附件1所示。充分考慮這些代表的意愿，請(qǐng)你們?yōu)橹鬓k方設(shè)計(jì)代表們合適的旅游路線，使他們?cè)跁?huì)議結(jié)束后的10天時(shí)間內(nèi)花最少的錢(qián)游盡可能多的地方。32.問(wèn)題分析2.1問(wèn)題背景的理解：根據(jù)對(duì)題目的理解我們可以知道，旅游的總費(fèi)用包括交通費(fèi)用和在景點(diǎn)游覽時(shí)的費(fèi)用，而在確定了要游覽的景點(diǎn)的個(gè)數(shù)后，所以我們的目標(biāo)就是在滿足所有約束條件的情況下，求出成本的最小值。2.2問(wèn)題一和問(wèn)題二的分析：?jiǎn)栴}一要求我們?yōu)橹鬓k方設(shè)計(jì)合適的旅游路線，使會(huì)議代表在會(huì)議結(jié)束后的10天時(shí)間內(nèi)花最少的錢(qián)游盡可能多的地方。在這里我們的做法是在滿足相應(yīng)的約束條件下，先確定游覽的景點(diǎn)數(shù)，然后計(jì)算出在這種情況下的最小花費(fèi)。這樣最終會(huì)得出幾種最佳方案，而組織方可以根據(jù)自己的實(shí)際情況進(jìn)行選擇。問(wèn)題二實(shí)質(zhì)上是在問(wèn)題一的基礎(chǔ)上改變了時(shí)間約束，即代表們要游覽所有的景點(diǎn)，我們完全可以使用與問(wèn)題一同樣的方法進(jìn)行求解。2.3問(wèn)題三的分析：?jiǎn)栴}三要求我們?cè)趩?wèn)題一的基礎(chǔ)上充分考慮代表們對(duì)各個(gè)景點(diǎn)的意愿來(lái)設(shè)計(jì)最佳旅游路線，而代表們的意愿由附件1給出。對(duì)于意愿，我們的做法是將其轉(zhuǎn)化為相應(yīng)的權(quán)重，然后乘以相應(yīng)的旅游景點(diǎn)的花費(fèi)，再利用問(wèn)題一的模型得出幾種最佳方案供主辦方選擇。43.模型假設(shè)1.所給的5條路線每條路線中的景點(diǎn)可以全部參觀，也可以參觀其一；2.參觀景點(diǎn)的人數(shù)越多，每人承擔(dān)的費(fèi)用越少；3.數(shù)學(xué)系使用旅游大巴安排代表們往返于各個(gè)旅游景點(diǎn)，其交通費(fèi)用、在景點(diǎn)的花費(fèi)、在景點(diǎn)的逗留時(shí)間參照當(dāng)?shù)乜瓦\(yùn)公司及旅行社的數(shù)據(jù)；4.代表們所乘坐的旅游大巴平均時(shí)速為50km/h，平均費(fèi)用為0.3元/km；5.一個(gè)景點(diǎn)直接到達(dá)另外一個(gè)景點(diǎn)是指，途中經(jīng)過(guò)的其他景點(diǎn)只是一個(gè)轉(zhuǎn)站地，而并不進(jìn)行游覽；6.在限定的時(shí)間內(nèi)，代表們最終要返回成都，并且假設(shè)成都是代表們肯定要去的一個(gè)旅游景點(diǎn)；7.假設(shè)參觀景點(diǎn)的人數(shù)每增加一人，每個(gè)代表在景點(diǎn)的費(fèi)用就減少原價(jià)的1‰；8.代表們?cè)谕局泻陀斡[景點(diǎn)的時(shí)間為12小時(shí)，而另外12小時(shí)為休息、用餐及其他瑣事時(shí)間。54.符號(hào)說(shuō)明,

——第個(gè)或者第個(gè)景點(diǎn)，

=1,2,……,11;

分別表示成都、九寨溝、黃龍、樂(lè)山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺溝、康定；——每個(gè)會(huì)議代表的旅游總花費(fèi)；——每個(gè)會(huì)議代表在第個(gè)景點(diǎn)的逗留時(shí)間；——每個(gè)會(huì)議代表在第個(gè)景點(diǎn)的總消費(fèi)；——從第個(gè)景點(diǎn)到第個(gè)景點(diǎn)路途中所需時(shí)間；——從第個(gè)景點(diǎn)到第個(gè)景點(diǎn)所需的交通費(fèi)用；

65.模型建立5.1

問(wèn)題一：

目標(biāo)函數(shù)的確立：經(jīng)過(guò)對(duì)題目分析，我們可以知道本題所要實(shí)現(xiàn)的目標(biāo)是，使會(huì)議代表在10天時(shí)間內(nèi)花最少的錢(qián)游覽盡可能多的地方。顯然，花費(fèi)最少和游覽的景點(diǎn)盡量多是該問(wèn)題的兩個(gè)目標(biāo)。因此，我們的做法是在滿足相應(yīng)的約束條件下，先確定游覽的景點(diǎn)數(shù)，然后計(jì)算出在這種情況下的最小花費(fèi)。這樣最終會(huì)得出幾種旅游路線，而組織方可以根據(jù)自己的實(shí)際情況進(jìn)行選擇。游覽的總費(fèi)用由2部分組成，分別為交通總費(fèi)用和在旅游景點(diǎn)的花費(fèi)。我們定義：

——每個(gè)代表的旅游總花費(fèi)；

——每個(gè)代表的交通總費(fèi)用；

——每個(gè)代表的旅游景點(diǎn)的花費(fèi)；從而得到目標(biāo)函數(shù)：Min

＝

＋7（1）交通總花費(fèi)因?yàn)楸硎緩牡趥€(gè)景點(diǎn)到第個(gè)景點(diǎn)所需的交通費(fèi)用，而是判斷代表們是否從第個(gè)景點(diǎn)直接到第個(gè)景點(diǎn)的0—1變量，因此我們可以很容易的得到交通總費(fèi)用為：8（2）旅游景點(diǎn)的花費(fèi)

因?yàn)?/p>

表示會(huì)議代表們?cè)?/p>

個(gè)景點(diǎn)的總消費(fèi)，也可以表示出代表們是否到達(dá)過(guò)第

個(gè)和第

個(gè)景點(diǎn)，而整個(gè)旅游路線又是一個(gè)環(huán)形，

因此

實(shí)際上將代表們?cè)谒骄包c(diǎn)的花費(fèi)計(jì)算了兩遍，從而我們可得旅游景點(diǎn)的花費(fèi)為：9目標(biāo)函數(shù)如下：Min10①時(shí)間約束由題目可知，代表們?cè)诖ǖ穆糜螘r(shí)間應(yīng)該不多于10天(120小時(shí))，而這些時(shí)間包括在路途中的時(shí)間和在旅游景點(diǎn)逗留的時(shí)間。因?yàn)?/p>

表示從第

個(gè)景點(diǎn)到第

個(gè)景點(diǎn)路途中所需時(shí)間，所以路途中所需總時(shí)間

表示會(huì)議代表們?cè)诘?/p>

個(gè)景點(diǎn)的逗留時(shí)間，故代表們?cè)诼糜尉包c(diǎn)的總逗留時(shí)間為

因此，總的時(shí)間約束為：11②旅游景點(diǎn)數(shù)約束根據(jù)假設(shè)，整個(gè)旅游路線是環(huán)形，即最終代表們要回到成都，因此即表示代表們旅游的景點(diǎn)數(shù)，這里我們假定要旅游的景點(diǎn)數(shù)為（n=2，3，……，11）。因此旅游景點(diǎn)數(shù)約束為：12③0——1變量約束我們可以把所有的景點(diǎn)連成一個(gè)圈，而把每一個(gè)景點(diǎn)看做圈上一個(gè)點(diǎn)。對(duì)于每個(gè)點(diǎn)來(lái)說(shuō)，只允許最多一條邊進(jìn)入，同樣只允許最多一條邊出來(lái)，并且只要有一條邊進(jìn)入就要有一條邊出去。因此可得約束：（i，j=1，2，……，11）當(dāng)

時(shí)，因?yàn)槌啥际浅霭l(fā)點(diǎn)，所以

；

時(shí)，因?yàn)榇韨冏罱K要回到成都，所以13約束條件如下：14

模型的求解與結(jié)果分析：15從而根據(jù)模型，使用Lingo編程，得出結(jié)果如下表：（其中數(shù)字1-11分別表示成都、九寨溝、黃龍、樂(lè)山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺溝、康定）16對(duì)于上述結(jié)果，我們的推薦為：路線一：成都→樂(lè)山→都江堰→青城山→成都旅游景點(diǎn)數(shù)：4人均費(fèi)用：623元；路線二：成都→都江堰→青城山→丹巴→樂(lè)山→成都旅游景點(diǎn)數(shù)：5人均費(fèi)用：949元；路線三：成都→樂(lè)山→康定→丹巴→青城山→都江堰→成都旅游景點(diǎn)數(shù)：6人均費(fèi)用：1207元。17創(chuàng)新一minmax18約束條件19創(chuàng)新二轉(zhuǎn)化單目標(biāo)法線性加權(quán)和法：按照m個(gè)目標(biāo)的重要程度，分別乘以一組權(quán)系數(shù)，然后相加作為目標(biāo)函數(shù)。20約束條件215.2問(wèn)題二此問(wèn)與第一問(wèn)大同小異，不同的是代表們要完成所有景點(diǎn)的旅游，而目標(biāo)函數(shù)是求最少的交通費(fèi)。由第一問(wèn)結(jié)論可知，交通費(fèi)用為：

22模型建立：綜上所述，我們可以得到總的模型為：約束條件：23模型求解與結(jié)果分析：根據(jù)模型，使用Lingo編程，得出結(jié)果為：245.3問(wèn)題三此問(wèn)在第一問(wèn)的基礎(chǔ)上增加了代表們意愿這一條件，通過(guò)對(duì)附件一的觀察，我們發(fā)現(xiàn)代表們的意愿分為“去”、“不去”和“無(wú)所謂”三種。怎樣將這些文字轉(zhuǎn)換到公式中來(lái)表達(dá)代表們的意愿就成為了解決該問(wèn)的關(guān)鍵。在這里我們采用加權(quán)重的方式，將代表們的意愿理解為對(duì)該線路上兩個(gè)景點(diǎn)的權(quán)重，又因?yàn)槲覀冏罱K的目標(biāo)是使旅游的費(fèi)用最少，因此越熱門(mén)的景點(diǎn)相應(yīng)的權(quán)重也應(yīng)該越低（這是因?yàn)闄?quán)重越低，其與該景點(diǎn)的費(fèi)用相乘后也越低，從而增加了對(duì)該景點(diǎn)游覽的可能性）。25代表們意愿26數(shù)據(jù)處理將所有的“去”替換為0，所有的“不去”替換為1，所有的“無(wú)所謂”替換為0.5，從而得到一個(gè)100X5的矩陣我們定義：——第

個(gè)旅游景點(diǎn)的權(quán)重。由假設(shè)可知成都是代表們肯定要游覽的一個(gè)景點(diǎn)，因此

。27對(duì)其他權(quán)重進(jìn)行標(biāo)準(zhǔn)化處理可得：28模型建立綜上所述，我們可以得到總的模型為：約束條件：29模型求解與結(jié)果分析：（其中數(shù)字1—11分別表示成都、九寨溝、黃龍、樂(lè)山、峨嵋、四姑娘山