海島優(yōu)化方案答案

數(shù)學(xué)建模.doc123海島優(yōu)化方案分析摘要經(jīng)濟水平的增加，帶動了旅游業(yè)的發(fā)展。本文研究了5個島嶼與港口之間最短距離及乘船計劃。以最小費用為準(zhǔn)則，制定了最優(yōu)化一日游、二日游套餐。以及為滿足游客的需要，通過考慮游客量及費用兩大方面，找到建設(shè)旅館的最優(yōu)地方，與最優(yōu)規(guī)模。問題一：對于一日游問題，首先考慮單線整體旅游，以所游兩地的最大承受能力的最小值為游客量對 C52=10種路線分別計算，得到每條路線的費用。考慮到游客人數(shù)不定，所以以旅游線進行分類分為6種，1、2、3、4、5。分別對這5種線，從10種路線中進行最優(yōu)匹配。根據(jù)所旅游景點盡可能分散，旅客盡可能多，總費用盡可能少的原則進行匹配。根據(jù)1mRu3衡量得到最優(yōu)的五種一日游套餐對兩日游，按C54 5種考慮，利用Dijkstra算法，得到每種路線的最優(yōu)走法。同時僅有C、D兩地可以入住，所以在參觀景點次序排列時第二個位置（游客在旅游地直接入?。┗虻谌齻€位置（游客不在旅游地入住，在第二天旅游地旅游之前先入?。┍仨毷?C、D兩景點中至少一個。并且在游客規(guī)模取景點承受能力的人數(shù)與旅館容納能力的最小值作為該次旅游的人數(shù)規(guī)模。 結(jié)合最有走法，與條件限制。其次，根據(jù)一日游的原則以相同的方法可以得到最優(yōu)的兩種套餐， 見表格5問題二：在假設(shè)所有景點都達到接待游客的能力后，得到所建旅店的最大規(guī)模，分別計算各點到B、C、D點在最大規(guī)模的情形下，根據(jù)算法3，利用公式u210sxk(8.5t14t1)1.5(100t140t2min(245,Ri))2)(1min(245,Ri)得到U2b33125kU2c44445kU2d51215k找到最低費用的位置，因此選取 B島為新建旅館地點。同時將規(guī)模按階降低，利用相同的算法得到關(guān)于U2b的四組數(shù)據(jù)：245,33125k），(220，39288k)，（200,27370k），（180,30311k）將這四組數(shù)據(jù)以規(guī)模人數(shù)為x軸，以總費用為y軸。用插值與擬合的方法得到x、y之間的精品文檔交流相應(yīng)關(guān)系，取變化率最小，即圖線最平緩的點的x值進行取整，作為新建旅館的規(guī)模人數(shù)。即在B點建立旅館且最大承受能力為200人。由于在考慮一日游問題上， 沒有考慮住宿問題， 所以一日游套餐不需要要改動。 但是二日游問題上有一條最短路徑因為B不能入住而舍去，需要改動。然后以相同的方法制定相應(yīng)的套餐。符號說明:因租船所產(chǎn)生的費用u1:路程費u2：損失費t1:租大船的條數(shù)t2:租小船的條數(shù)：游客人數(shù)每條路線的最短路程:船只每公里費用系數(shù)Ri:第i個景點的游客承受力U2i:第i個景點到B點的費用V：表示所選兩景點中，接受游客的能力中的最小值。：景點個數(shù)。問題分析問題一分析：一日游：由表1島嶼與港口之間距離，先繪制出海島與港口粗略的平面分布圖。再利用matlabfloyd算法，求在兩點間的最短路。首先考慮旅行費問題，由已求出的五個海島與港口六個點的任意兩點的最短距離， 計算出（C52種）每種路線的最短路程，然后依次得到相應(yīng)的每條路線的路程費用 u1:。其次考慮游船損失問題。根據(jù) A、B、C、D、E各景點的承載游客的能力，所以，每條路線一般有：大船t1 0:3，小船t2 0:7之內(nèi)進行合理匹配。根據(jù)已求的路線，求每條路線兩個景點中最大承載能力的最小值為該條路線的規(guī)模人數(shù)， 計算出相應(yīng)精品文檔交流的u2。最后利用公式u1u2將C52結(jié)果按從小到大進行排列，根據(jù)游客的人數(shù)不同，考慮到實際問題，根據(jù)旅游線條數(shù)進行分類，得到5種分類?？紤]到每個套餐中景點分散度，最短距離與總費用三者之間所占的權(quán)重按從小到大排列得到最優(yōu)旅游套餐，取前六種路線即為旅游套餐。兩日游：按C54 5種考慮，利用Dijkstra算法，得到每種路線的最優(yōu)走法。同時僅有C、D兩地可以入住，所以在參觀景點次序排列時第二個位置（游客在旅游地直接入?。┗虻谌齻€位置（游客不在旅游地入住，在第二天旅游地旅游之前先入?。┍仨毷荂、D兩景點中至少一個。考慮到旅店的容納人數(shù)。游客規(guī)模取景點承受能力的人數(shù)與旅館容納能力的最小值作為該次旅游線的人數(shù)規(guī)模。 結(jié)合最有走法、條件限制，根據(jù)一日游的算法，得到相應(yīng)的 u1:、u2。其次，根據(jù)制定一日游套餐的原則，以相同的方法可以得到最優(yōu)二日游套餐。問題二分析：建設(shè)新旅店問題，只需考慮兩大準(zhǔn)則，建設(shè)地點、建設(shè)規(guī)模。建設(shè)地點：首先以衡量標(biāo)準(zhǔn) u u1 u2最小來標(biāo)量。其中 u1：各個景點分別到 BgCgD的最短距離總和，u2：假設(shè)在同一時刻，各個景點都達到最大承載能力。選取各個景點的最大承載能力的總?cè)藬?shù)的和（景點最大游客量）的50%減去C、D景點所承受能力的總?cè)藬?shù)。得到建立旅館的最大容納規(guī)模。根據(jù)損失費用標(biāo)量得到u2。利用uu11u2將B、C、D各點的情況依次算出，進行比較得到結(jié)果。（其中u1100t1sx0.85k40t2sxk，u12umin(245,Ri))1.5(100t140t2min(245,Ri)由u2u1u12將U2b、U2c、U2d依次算出，取min(U2b,U2c,U2d)的位置，即為新建旅館的建設(shè)地點。建設(shè)國模：考慮到景點每天的游客流量不同，所以將最大游客流量按階（以 20為一個單位）進行計算分別得到（ 245，U2i），(220,U2i),(200, U2i)，（180，U2i）四點，然后利用插值與擬合的方法得到，以 x:規(guī)精品文檔交流模人數(shù)，y:總費用的相關(guān)關(guān)系圖像，取斜率最小（圖像最平緩）的人數(shù)規(guī)模階段（近似取整），確定建旅館的規(guī)模大小。由于在考慮一日游問題上，沒有考慮住宿問題，所以一日游套餐不需要要改動。但是二日游問題上有一條最短路徑因為B不能入住而舍去，需要改動。重新考慮最短路線，最優(yōu)游客人數(shù)，最優(yōu)購船計劃，游覽費用。同時在于其它四條路線進行比較，利用原先相同的方法，制定二日游套餐。模型建立與求解問題一由表1島嶼及港口之間的距離，利用 ps軟件，畫出海島與港口的平面分布圖圖1：1＞一日游問題：假設(shè)該旅游區(qū)每天都有大量的游客來旅游，超過了各個景點的接待游客的能力。由于每個景點游半天，因此一日游涉及到2個景點的選取。因此有C52 10種情形，首先利用 matlabfloyd 算法求出任意兩點（海島與港口）間的最短距離得到如下表格表格1：加權(quán)圖的任意兩個島嶼之間的距離和路徑距離矩陣M 路徑矩陣N精品文檔交流0462150607012345646030325311512344621300485390123456M=324802195N=2345650160535321085143456701159095850123456由此，得到相應(yīng)的 10條游覽路線的最短路程。根據(jù)路程費用的公式： u1 ks0.85t1 t2 結(jié)合已經(jīng)求出的最短路程，得到每條路線的路程費用。因為每個景點的最大承載能力有限制，所以選取每條路線中兩個景點的最大承載能力的最小值，作為該條游覽路線的最大游覽人數(shù)。 根據(jù)大船、小船的容納人數(shù)，依此確定每條路線相應(yīng)的t1:、t2:。然后根據(jù)公式：u2 u11.5100t140t2V，計算出每條路線的損失費用。V由于費用包括客均費用與損失費用，即u u1 u2通過普通算法2（路程費用，損失費用）得到每種路線的總游覽費用。對于多種購船方案如下處理。其中：由于 V確定相應(yīng)的t1、t2會得到相對應(yīng)的分配，可能會得到兩種分配， a1、a2例如：PBCP:S235km其中：V250人得到a1t13（游船少載50人）a2t12(游船少載30人)t20t22針對a1：u123530.85k599.25ku2u12501.550179.775uu1u2799.025k針對a2：u123520.85k869.5ku2u12501.550260.85uu1u21130.35k精品文檔交流Q ua1ua2選取a1乘船方案將這10種方案依次算出游覽費用。并且按照路線、最短路程、大船數(shù)量、小船數(shù)量、游覽總費用，并按從小到大的順序排列繪制成表格。表格2：路線最短路程t1總費用t2PACP181km21488.7kPADP215km21580.5kPABP231km21623.7kPBDP242km30628.22PCDP233km30727.40PBCP235km30779.03PDEP201km061518.43PAEP215km061566.44PCEP228km061661.14PBEP253km061843.28考慮到每天景點的游客量的不確定性，依據(jù)每天景點的游覽路線的總條數(shù)進行分類。大致分成5類，1、2、3、4、5（1：只有一個景點達到最大承載能力。5所有景點，在同一時刻都達到最大承載能力）按照景點分散度，旅客人數(shù)及總費用，利用函數(shù)W 1(mRu)衡量，得到最優(yōu)匹配，選取合理的 5種匹配繪制成表3格如下。表格3：線條數(shù)最佳人數(shù)最佳路線1經(jīng)E210PDEP1不經(jīng)E240PACP2全經(jīng)E420PAEPPDEP2無要求520PACPPBDP3無要求730PACPPBDPPCEP

最佳分配（人數(shù)與路線相對應(yīng)）PDEP210PACP240PAEP210PDEP210PACP240PBDP280PBDP240PACP280PCEP精品文檔交流二日游：由于每日只能游2個景點，因此2日游需對4個景點進行旅游，在5個景點中C54 5，所以有5種景點旅游選擇，分別是：ABCD ABCE ACDE BCDE ABDE將5種情形分別進行討論：1、ABCE首先利用matlab行遍性問題中的TSP算法（程序見附錄求最短路）可以得到由P點出發(fā)經(jīng)過全部A、B、C、D回到P的最短路徑圖線。但由于，僅有C、D兩個島嶼有游客可供住宿，所以在最短路線中，要求第2個位置（游客可以在旅游景點入住）或第3個位置（游客可以在旅游景點入住然后參觀）必須是C、D中的至少得任意一個。若所得路線滿足條件，則是所求路線。否則需進行下步計算。將ABCD進行滿足條件的全排列，分別利用算法計算每個排列的人均費用，取人均費用最小的排列為該四個景點的最優(yōu)游覽路線，并且得到相應(yīng)的路程費用。。取每條路線中四個景點的最大承載能力的、旅館最大容納能力的最小值，最為該條路線的最優(yōu)游覽人數(shù)。根據(jù)一日游求解損失費用的方法，得到每條路線在最優(yōu)人數(shù)下的損失費用。然后把得到的數(shù)據(jù)按照路線、最短路程、大船數(shù)量、小船數(shù)量、人均費用回執(zhí)成表格。得到如下表格。表格4最t1t2人均總費景點路線短距離用ABCDPACBDP248km21669.6kABCEPACBEP259km21590.15kACDEPEDCAP245km21803.25kBCDEPECBDP295km21940.21kABDEPEDBAP254km21840.12k考慮到實際問題，考慮到每個套餐中景點分散度，最短距離與總費用三者之間所占的權(quán)重，根據(jù)一日游套餐制定的與原則嗎，得到如下二日游旅游套餐。將所到的數(shù)據(jù)按照最優(yōu)路線條數(shù)，最優(yōu)路線、最短路程、最優(yōu)大船數(shù)量、最優(yōu)小船數(shù)量、人均費用揮之表格，如下。表格5：路線條數(shù)最佳路線最佳人t1人均費用數(shù)t21PACBDP24021669.6k1PACBEP21021590.15k2PACBDP450421609.81PEDCAPk注：由于D的住宿承受力是200，因此當(dāng)達到景點容納能力后，若在D入住會大于住宿的承載力，因此在考慮BCDE及ABDE路線時，此時客人數(shù)量只能取兩者最小的一個，因此雙方考慮后的到如上表格精品文檔交流問題二此問題要求確定新建旅館的地點與規(guī)模人數(shù)，所以分兩部分進行1.地點首先，假設(shè)在同一時刻所有景點都滿員，則得到x=145050%x=725同時假設(shè)C、D旅館都達到最大承受能力，所以所建旅館的最大規(guī)模為725-200-280=245（人）其次分別利用算法計算出U2b、U2c、U2du2u1u12u1100t1sx0.85k40t2Sxu12u11.5(100t140t2min(245,Ri)min(245,Ri)因此可得U2b33125kU2c44445kU2d51215k選取B點為所建旅館的地點。2.規(guī)模每天游覽景點的人數(shù)不同，因此以新建旅館的最大承受能力依次遞減20人，分析對應(yīng)的U2b的變化情況。由算法 5可得如下4組數(shù)據(jù)（245，33125） （220,44445）（200,27370） （180,30311）。其次，分別將這4組數(shù)據(jù)，利用matlab插值與擬合的方法，得到關(guān)于以規(guī)模人數(shù)為x軸，以總費用為y軸的相應(yīng)關(guān)系如圖精品文檔交流用matlab中的figure工具找到最平緩位置（斜率變化不明顯）。因此得到此時x在180:205。然后，進行精細(xì)分析。用matlab中坐標(biāo)工具，可以得到該曲線中的最低點（199,27365）如圖因此，取x=200即為該新旅館的規(guī)模人數(shù)。由于一日游問題不考慮住宿問題，因此在游覽套餐中一日游的不需要改動。由于二日游問題在考慮住宿條件。 在增加新的旅館后，縮小了條件限制，擴大了可選擇點。現(xiàn)在二日游問題上，游覽路線的第二個位置或第三個位置可以是B、C、D、三點重的任意一個。因此在所求的最短路徑中因B不能住宿而舍去的路線，精品文檔交流現(xiàn)在需要重新進行考慮。因為P E C B D P是如上所說的問題，所以經(jīng)過重新計算后年得到P C B D E P相應(yīng)的最短距離： 258km， 大船數(shù)量：2，小船數(shù)量：0，最優(yōu)人數(shù)：200，總費用：578.025k，將新的路線進行重新考慮，因此二日游套餐需要改動，改動結(jié)果如下。表格6：路線條數(shù)最佳路線最佳人t1t人均費用數(shù)21PCBDEP20020578.02k1PACBEP21021590.15k2PACBDP450421609.81PEDCAPk程序附件求最短路matlab程序a=[04621506070;460303255115;21300485390;50324802195;60555321085;701159095850][D,R]=floyd(a)%function[D,R]=floyd(a);n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endendRfork=1:n精品文檔交流fori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendkDRendD=04621506070460303253115213004853905032480219560535321085701159095850R=123456123446123456123456143456123456二日游最短路lingo 程序：MODEL:SETS:CITY/1..6/:U;!U(I)=sequenceno.ofcity;LINK(CITY,CITY):DIST,!Thedistancematrix;X;!X(I,J)=1ifweuselinkI,J;ENDSETS精品文檔交流DATA:!Distancematrix,itneednotbesymmetric;DIST=07011590957004621501154603032902130048955032950;ENDDATA!Them