最佳選址問題e

PAGEPAGE1833組李旭輝楊哲楊志巧最佳選址問題 摘要本文主要解決的是在社區(qū)中的最佳選址、最佳管轄分配和最佳路線的選擇問題，我們將各社區(qū)作為定點(diǎn)（V），將社區(qū)之間的道路作為邊，并把鄰接社區(qū)間的道路距離作為邊的權(quán)值(G)，采用圖論【1】的方法來分析這類問題。對于問題一：我們考慮將三個煤氣繳費(fèi)站建在三個社區(qū)之中，而24個社區(qū)居民繳費(fèi)時都選擇去最近的煤氣繳費(fèi)站。顯然這是一個多階段決策性問題。我們先用Floyd算法建立模型一，用Matlab求得任意兩個社區(qū)間的最短距離(見表3)。然后考慮到建三個繳費(fèi)站要在24個社區(qū)中做選擇，我們建立動態(tài)規(guī)劃模型（模型二），利用LINGO軟件【2】求得最優(yōu)解，最終得到去繳費(fèi)的居民平均行走路程最小值為1171m。最佳方案是將煤氣繳費(fèi)站建在M、Q、W三個社區(qū)。對于問題二：首先通過計(jì)算得知每個派出所轄區(qū)內(nèi)的所有社區(qū)距派出所的距離都不得超過2500m。在保證警察3分鐘內(nèi)趕到所轄范圍內(nèi)所有社區(qū)的前提下，首先考慮派出所的個數(shù)，使得派出所個數(shù)取得最小，然后我們再考慮派出所具體設(shè)定的位置，使得派出所到各社區(qū)的平均距離最小。這樣與問題一相似，我們建立動態(tài)規(guī)劃模型【3】。為了簡化模型，我們先根據(jù)社區(qū)間的距離判斷出派出所的個數(shù)至少為3個。然后我們先假設(shè)有3個派出所，若能滿足要求，則其為最優(yōu)個數(shù)，若3個不能滿足要求，我們就假設(shè)有四個，照此直到求出剛好能滿足條件的派出所個數(shù)。最終用C++我們得到最優(yōu)化方案，即：設(shè)定3個派出所，分別設(shè)在K、Q、W社區(qū)。對于問題三：首先我們將問題轉(zhuǎn)化成圖論中的旅行售貨員問題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)W出發(fā)，行遍所有巡視點(diǎn)至少一次再回到點(diǎn)W，使得總權(quán)（路程）最小。我們將圖中的24個社區(qū)組成的頂點(diǎn)集劃分成，將整個圖分成三個生成圖。領(lǐng)導(dǎo)巡視時間分為兩部分，路途時間和社區(qū)逗留時間。針對巡視組是否能較快完成巡視，我們給出了三項(xiàng)指標(biāo)：（1）三個巡視組巡視社區(qū)的個數(shù)的均衡度（2）每組巡視路線是否能盡量在以W社區(qū)為根部的樹圖之上（巡視總路線的長度）（3）三個巡視組總路程均衡度。當(dāng)三項(xiàng)指標(biāo)綜合起來最優(yōu)時，我們得到巡視的最佳方案。我們通過簡單分析，確定每個巡視組巡視8個社區(qū)，用Dijkstra算法求得以W點(diǎn)為根部的樹圖，然后采用兩邊逐次修正求最優(yōu)圈的方法找到較短路線。得到的最佳巡視方案為：組一：W—G—I—P—H—K—H—Y—L—F—W（巡視社區(qū)為：GIPHKYLFW）組二：W—F—L—M—N—J—U—V—T—E—C—W（巡視社區(qū)為：MNJUVTEC）組三：W—B—X—A—S—R—Q—D—C—W（巡視社區(qū)為：WBXASRQDC）關(guān)鍵詞：圖論Floyd算法Dijkstra算法動態(tài)規(guī)劃1.問題的重述在當(dāng)今社會，選址問題是各種企業(yè)最重要的問題之一，選址的好壞將直接影響到企業(yè)的利潤和市場競爭力，甚至決定了企業(yè)的命運(yùn)。而合理的安排地理位置不僅可以給人們的生活帶來極大的便利，更可以減小一些不必要的損失，因而選址問題就顯得尤為重要。在本文中，我們主要考慮某城市的繳費(fèi)站地址選擇與巡視路線選擇的數(shù)學(xué)建模問題。該城市共有24個社區(qū)，各社區(qū)的人口（單位：千人）如下表1所示：編號ABCDEFGHIJKL人口10121861015487111311編號MNPQRSTUVWXY人口11892214871015281813而每個社區(qū)之間都可通過一定的途徑到達(dá)，各社區(qū)之間的道路連接情況如下圖1所示：（注：橫線上的數(shù)據(jù)表示相鄰社區(qū)之間的距離，單位：百米）本題需要我們解決的問題有：（1）在該城市合理的安排3個煤氣繳費(fèi)站來方便社區(qū)居民繳納煤氣費(fèi)，確定煤氣繳費(fèi)站的地址使得居民與最近煤氣站之間的平均距離最小。（2）社區(qū)的安全是城市的重要部分，為了使每個社區(qū)的安全都得到保證，因?yàn)槭泄簿謹(jǐn)M在該城區(qū)建立若干個派出所，每個派出所都有各自的分配管轄范圍，希望在建成派出所以后要確保在每個社區(qū)出現(xiàn)突發(fā)事件時，管轄該社區(qū)的警察盡量能在3分鐘內(nèi)（警車的時速為50km/h）到達(dá)事發(fā)地。問設(shè)置多少個派出所比較合理，位置選在哪？（3）社區(qū)W是市政府所在地，市領(lǐng)導(dǎo)從W出發(fā)巡視，分三組巡視所有社區(qū)，為了盡快完成巡視，我們要合理的安排巡視路線使時間達(dá)到最少。2.模型的假設(shè)根據(jù)分析，我們給出如下假設(shè)：假設(shè)1：各社區(qū)去繳納費(fèi)用的人數(shù)占該社區(qū)總?cè)藬?shù)的比例相等假設(shè)2：收費(fèi)站和派出所只能建立在社區(qū)中假設(shè)3：當(dāng)煤氣站建在社區(qū)里時，本社區(qū)居民去交錢時行走的路程為0假設(shè)4：報(bào)警時間以及安排出警的時間忽略不計(jì)假設(shè)5：忽略警察啟動警車和剎車的過程，將全程看成勻速直線運(yùn)動假設(shè)6：市領(lǐng)導(dǎo)巡視時車速為35km/h到40km/h之間假設(shè)7：巡視時領(lǐng)導(dǎo)在社區(qū)的滯留時間大于20分鐘3.符號說明表2符號符號說明表示24個社區(qū)的序號表示社區(qū)到社區(qū)的最短距離表示社區(qū)的人數(shù)表示將煤氣繳費(fèi)站建立在這三個社區(qū)表示建立個派出所在這個社區(qū)里面表示第個巡視組巡視的社區(qū)的個數(shù)第個巡視組巡視的最短路程表示從到的只以集合中的節(jié)點(diǎn)為中間節(jié)點(diǎn)的最短路徑的長度其中分別可取A、B、C········Y等24個社區(qū)4.問題分析4.1問題一的分析為了找到煤氣繳費(fèi)站的最佳位置，我們首先要解決的問題是求出任意兩個社區(qū)間的最短距離。而Floyd算法可很好的解決這一問題。所以我們建立了Floyd算法的動態(tài)規(guī)劃模型。為了確定各個社區(qū)應(yīng)該去哪個繳費(fèi)站繳納費(fèi)用，這是一個多階段決策性問題，因此我們建立動態(tài)規(guī)劃模型來解決此問題。分析已知條件，我們考慮把煤氣站建在三個社區(qū)中，此時我們只需根據(jù)所求出的各個社區(qū)之間的最短距離（表3）即可知道其余各社區(qū)應(yīng)該去哪個繳費(fèi)站繳納費(fèi)用。因此我們首先解決的問題是確定將3個煤氣站建立在哪3個社區(qū)中，然后再確定各個社區(qū)應(yīng)該去哪個煤氣站繳納費(fèi)用，最后我們就可以知道每個煤氣站分別是哪些社區(qū)的居民來繳納費(fèi)用。將去各煤氣站繳納費(fèi)用的人的人數(shù)乘以各自所行走的路程，再將去3個煤氣站的人所走的總路程相加，最后再除以總?cè)藬?shù)即可得出平均距離。根據(jù)上述分析即可得到目標(biāo)函數(shù)，然后采用LINGO軟件根據(jù)各個限制條件即可求出最小值并確定煤氣繳費(fèi)站的最佳位置以及各個社區(qū)繳納煤氣費(fèi)用的站點(diǎn)。4.2問題二的分析在保證警察3分鐘內(nèi)趕到所管轄范圍內(nèi)所有社區(qū)的前提下，首先考慮派出所的個數(shù)，使得派出所個數(shù)取得最小，然后我們再考慮派出所具體設(shè)定的位置，使得派出所到各社區(qū)的平均距離最小。這樣與問題一相似，我們?nèi)匀唤討B(tài)規(guī)劃模型。為了簡化模型，我們首先考慮派出所的個數(shù)：我們設(shè)有n個派出所，先確定派出所的個數(shù)的取值從幾開始。分析表3我們可以知道任意兩個社區(qū)之間的最短距離比25大的有很多，所以建立一個派出所肯定是不夠的；再考慮建立兩個派出所，觀察圖1我們可以發(fā)現(xiàn)P社區(qū)到其他社區(qū)的距離均較遠(yuǎn)，因此有一個派出所必須離P較近，還有另外一個派出所不管設(shè)置在哪里我們都不能保證任何一個社區(qū)發(fā)生突發(fā)狀況時有警察在3分鐘之內(nèi)趕到。因此我們先假設(shè)有3個派出所，若能滿足要求，則其為最優(yōu)個數(shù)，若3個不能滿足要求，我們就假設(shè)有四個，照此直到求出剛好能滿足條件的派出所個數(shù)。確定派出所的個數(shù)以后，我們再考慮建立的位置，當(dāng)任何一個社區(qū)發(fā)生突發(fā)事件以后，每一個警察局都有其自己的最佳路線趕到社區(qū)，此時我們需要安排離該社區(qū)最近的派出所過去，這時候該社區(qū)就由這個派出所管轄。由1個社區(qū)推廣到24個社區(qū)，我們就確定了每個警察局的管轄范圍。題目要求在確定警察局的個數(shù)每個警察題目中提到警察必須在3分鐘之內(nèi)趕到始發(fā)地點(diǎn)，我們可以算出離派出所的最短距離為2500米，因此在每個管轄范圍內(nèi)的社區(qū)離警察局的最短距離必須小于2500米。根據(jù)這個限制條件，我們就可以確定警察局的數(shù)量、位置以及管轄范圍。4.3問題三的分析：本題給出了城市社區(qū)的公路網(wǎng)絡(luò)圖，要求的是在不同的條件下，社區(qū)巡視的最佳分組方案和路線.將每個社區(qū)看作一個圖的頂點(diǎn)，各社區(qū)之間的公路看作此圖對應(yīng)頂點(diǎn)間的邊，各條公路的長度看作對應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化圖論中一類稱之為旅行售貨員問題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)W出發(fā)，行遍所有頂點(diǎn)至少一次再回到點(diǎn)W，使得總權(quán)（路程）最小。本題是多旅行售貨員問題，因?yàn)轭}中有三個巡視小組，則所求的就是3條經(jīng)過同一點(diǎn)并覆蓋所有其他頂點(diǎn)又使邊權(quán)之和達(dá)到最小的閉鏈。針對此類問題，我們可用近似算法來求最優(yōu)解。為了盡快完成巡視，則需最后回來的一組領(lǐng)導(dǎo)盡早趕回市政府，這樣就要求三組巡視領(lǐng)導(dǎo)的巡視時間盡量均衡?？紤]到領(lǐng)導(dǎo)在一個社區(qū)逗留時間比到一個社區(qū)路程上花的時間要多很多，我們要求每一組領(lǐng)導(dǎo)要巡視8個社區(qū)。5.問題一的解答5.1模型一的建立確定目標(biāo)函數(shù)：我們利用一個三重循環(huán)產(chǎn)生一個存儲每個結(jié)點(diǎn)最短距離的矩陣，用圖的鄰接矩陣來存儲帶權(quán)有向圖。取為從到的只以集合中的節(jié)點(diǎn)為中間節(jié)點(diǎn)的最短路徑的長度。開始時，以任意兩個頂點(diǎn)之間的有向邊的權(quán)值作為路徑長度，沒有有向邊時，路徑長度為∞，當(dāng)k=0時,=，以后逐步嘗試在原路徑中加入其它頂點(diǎn)作為中間頂點(diǎn)，如果增加中間頂點(diǎn)后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。最終我們就得到任意兩個社區(qū)間的最短距離矩陣。1、若最短路徑經(jīng)過點(diǎn)k，則：若最短路徑不經(jīng)過點(diǎn)k，則：因此，我們得到目標(biāo)函數(shù)為：對于本題，當(dāng)k=24時，我們即可求得任意兩社區(qū)間的最短距離的矩陣。5.2模型一的求解：最終，我們用Matlab解得任意兩個社區(qū)之間的最短距離如下表3所示：5.3模型二的建立：首先我們假設(shè)將煤氣繳費(fèi)站建在社區(qū)、、中，那么各個社區(qū)的人就必須到這三個繳費(fèi)站之一去繳費(fèi)，因此我們需要根據(jù)表3所給出的各個社區(qū)之間的最短距離來確定社區(qū)應(yīng)該該到哪一個繳費(fèi)站繳費(fèi).在此處我們構(gòu)建動態(tài)規(guī)劃模型，于是引入函數(shù)，根據(jù)函數(shù)表達(dá)的意思，就是比較社區(qū)離哪個繳費(fèi)站較近，然后取得這個最小值，便可以確定任一社區(qū)到、、中的哪一個繳費(fèi)站繳納費(fèi)用。目標(biāo)函數(shù)的確定：由于題目所要求的是使得居民與最近煤氣站之間的平均距離最小，而平均距離又與總?cè)藬?shù)和總距離有關(guān)，因此我們需要求出總路程然后再除以總?cè)藬?shù)。求總路程：由于到各個繳費(fèi)站的社區(qū)人數(shù)都不相同，因此我們應(yīng)該先將去各煤氣站繳納費(fèi)用的人的人數(shù)乘以各自所行走的路程，再將去3個煤氣站的人走的總路程相加即可得到所有人行走的總路程。因此總路程的表達(dá)式為：題目要求的是建立煤氣站以后使得平均距離最小，因此需要將總路程除以總?cè)藬?shù)，因此目標(biāo)函數(shù)的表達(dá)式為：5.4模型二的求解根據(jù)上面做列出的目標(biāo)函數(shù)的表達(dá)式，再由已知條件所給出的各項(xiàng)限制條件，運(yùn)用LINGO軟件可確定將煤氣繳費(fèi)站建立在M、Q、W三個社區(qū)為最佳方案，其余21個社區(qū)應(yīng)該分別到哪個社區(qū)繳費(fèi)的情況見下表4：繳費(fèi)站到該繳費(fèi)站繳納費(fèi)用的社區(qū)MH,J,K,L,M,N,P,U,YQD,Q,R,S,T,VWA,B,C,E,F,G,I,W,X

我們分別將M、Q、W三個繳費(fèi)站染成不同顏色，去該繳費(fèi)站繳納費(fèi)用的社區(qū)與其染成相同顏色。去M社區(qū)繳費(fèi)的社區(qū)表示為黃色，去Q社區(qū)繳納費(fèi)用的表示為藍(lán)色，去W社區(qū)繳納費(fèi)用的表示為紅色，具體情況見下圖2：各社區(qū)居民到M、Q、W三個社區(qū)繳納費(fèi)用時各自所走的路程用圖3表示如下：圖3綜上所述：最終將煤氣繳費(fèi)站建立在M、Q、W三個社區(qū)中可使居民與最近煤氣站之間的平均距離最小且最小平均距離為1171米。5.5問題一的結(jié)果分析分析表1，我們根據(jù)所給出的各社區(qū)的人數(shù)采用EXCLE作出了如下的柱狀圖，如圖4所示：分析上述圖6可知我們可以知道社區(qū)C、F、Q、V、W、X為居住人數(shù)較多的社區(qū)，在考慮建立收費(fèi)站的時候，我們可以初步假設(shè)將收費(fèi)站建立在離這幾個社區(qū)較近地方。而上面所給出的結(jié)果是建立在M、Q、W三個社區(qū)，最終結(jié)果與開始的一種設(shè)想大部分吻合，即Q、W兩個社區(qū)設(shè)置為了繳費(fèi)站，但是M社區(qū)離這幾個社區(qū)均較遠(yuǎn)，因此在解決實(shí)際問題的時候我們應(yīng)該結(jié)合實(shí)際情況來看。6.問題二的解答6.1模型的準(zhǔn)備在問題分析中我們提到需要在保證能夠趕到突發(fā)現(xiàn)場的情況下盡可能的減少派出所的數(shù)量，因此我們先假設(shè)派出所的個數(shù)為個，設(shè)為，那么當(dāng)任何一個社區(qū)發(fā)生突發(fā)事件時，這個派出所就必須選擇離該社區(qū)最近的派出所趕到突發(fā)現(xiàn)場，因此我們需要確定這個派出所離社區(qū)的最短距離，因此引入函數(shù)來確定當(dāng)社區(qū)發(fā)生突發(fā)事件時應(yīng)該哪個派出所趕往此地。6.2目標(biāo)函數(shù)的確定由于題目給出的條件是為派出所分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在3分鐘內(nèi)有警察（警車的時速為50km/h）到達(dá)事發(fā)地。因此我們首先需要確定每一個派出所所管轄的范圍，此時根據(jù)各個社區(qū)離派出所的距離來確定其管轄范圍。題目要求警察必須在三分鐘之內(nèi)趕到事發(fā)現(xiàn)場，因此需要保證派出所能夠在3分鐘之內(nèi)趕到其管轄的范圍內(nèi)，并且使其所走的總路程的平均值最小，用數(shù)學(xué)表達(dá)式表達(dá)為：又題目給出的限制條件為3分鐘之內(nèi)，所以我們可以理解為在管轄范圍內(nèi)的任意一個社區(qū)離它的距離都小于2500米（用圖中的單位表示就是25）因此最終建立的模型可表示為：6.3模型的求解根據(jù)上述分析以及各限制條件，我們運(yùn)用C語言編程求出了三種符合問題的方案。派出所應(yīng)該建立的個數(shù)均為3個，只是建立的社區(qū)有所不同：分別建立在K、Q、W這三個社區(qū)分別建立在D、K、W這三個社區(qū)分別建立在K、R、W這三個社區(qū)而題目要求的是給出最佳方案，因此我們根據(jù)計(jì)算距離的長短確定第一種方案為最佳方案。下圖表示出了各派出所所管轄的范圍，不同顏色的區(qū)域分別表示不同的管轄區(qū)域，其中K社區(qū)所在的警局分管的社區(qū)有H、J、K、L、M、N、P、Y等8個社區(qū)；Q社區(qū)所在的警局分管的社區(qū)有D、Q、R、S、T、V等7個社區(qū)；W社區(qū)所在的警局分管的社區(qū)有A、B、C、E、F、G、I、L、U、W、X等11個社區(qū)。其中由于L社區(qū)到K社區(qū)和W社區(qū)的最短距離相等，因此當(dāng)L社區(qū)發(fā)生突發(fā)狀況時，管轄該社區(qū)的兩個警局趕往事發(fā)現(xiàn)場的時間是一樣的。各警察局與其管轄范圍內(nèi)社區(qū)的距離見下圖5。各警局的管轄情況用圖表示如下圖6所示，不同的管轄區(qū)域所用的顏色不同。經(jīng)過分析計(jì)算我們可以求出3個警局到其分管的各個社區(qū)的最短距離和的平均值為14.75（百米）。6.4問題二的結(jié)果分析在模型的求解中我們得到符合題目要求的有三種方案，然而題目說要找出合理的因此我們通過計(jì)算距離來確定最優(yōu)方案。通過計(jì)算，我們可以知道當(dāng)派出所建立在K、Q、W三個社區(qū)時，所走的路程的平均值為14.75（百米）；當(dāng)派出所建立在D、K、W三個社區(qū)時，所走路程的平均值為15（百米）；當(dāng)派出所建立在K、R、W三個社區(qū)時，所走的路程的平均值為15.3（百米）。因此我們可以知道第一種方案為最佳方案，這樣有利于警察出警，不僅節(jié)約時間還使居民的安全得到了保障。7.問題三的解答指標(biāo)一：三個巡視組巡視社區(qū)的個數(shù)的均衡度考慮到領(lǐng)導(dǎo)在一個社區(qū)逗留時間比到一個社區(qū)路程上花的時間要多很多，我們把其作為最重要的一項(xiàng)指標(biāo)，指標(biāo)一的表達(dá)式為：當(dāng)三組領(lǐng)導(dǎo)巡視社區(qū)的個數(shù)相等時，取得最小值0。指標(biāo)二：巡視的總路程（路線盡量設(shè)在樹圖之上）我們用Dijkstra算法求W到各點(diǎn)的最小距離。第一步，將每一點(diǎn)到w點(diǎn)的距離找到（未與w點(diǎn)直接連接的點(diǎn)到w點(diǎn)的距離默認(rèn)為無限大）;第二步，將w點(diǎn)放入到S集合中，然后開始找到w點(diǎn)距離最小的點(diǎn)（加入到S集合中），將S集合中的每一點(diǎn)都與w點(diǎn)關(guān)聯(lián)（如果有直接關(guān)聯(lián)的邊），看從點(diǎn)w到該點(diǎn)（中間經(jīng)過若干S集合中的點(diǎn)）的權(quán)值之和是不是小于w與該點(diǎn)間直接邊的權(quán)值，如果小于的話就替換該點(diǎn)的最短路徑，并且記錄該點(diǎn)的前一點(diǎn);第三步，一直重復(fù)第二步，直至S集合中的點(diǎn)被取完為止。通過上述步驟，我們可以得出w點(diǎn)到每一點(diǎn)的最短距離，并且通過之前記錄的點(diǎn)可以找到w點(diǎn)到該店的最短的路徑。于是我們畫出以W點(diǎn)為根部的樹圖，如下圖7所示：3214532145從社區(qū)出發(fā)有24個節(jié)點(diǎn)，我們只能找到一種較合理的劃分準(zhǔn)則，對圖1進(jìn)行初步劃分后分別求出3個回路的的近似最佳旅行售貨員回路的權(quán)。在分組時應(yīng)遵循三個原則：1、三個組的回路上點(diǎn)的個數(shù)接近。2、盡量使同一干枝上及其分支上的點(diǎn)分在同一組。3、應(yīng)將相鄰的干枝上的點(diǎn)分在同一組。于是我們得到三組點(diǎn)集，即：={W,B,X,A,S,R,Q,D,C,V,T}；={W,G,I,P,K,H,Y,F,L,M,F}；={F,L,M,N,J,U,E,V,T,C}。指標(biāo)三：三個巡視組總路程均衡度為實(shí)際均衡度。因?yàn)槁眯惺圬泦T問題不存在多項(xiàng)式內(nèi)的準(zhǔn)確時間算法，所以只能用近似算法來求得最優(yōu)解。其中其中為的導(dǎo)出子圖中的最佳旅行售貨員回路，為的權(quán)，i，j=1，2,3.從指標(biāo)二得出分組后的點(diǎn)集，在此基礎(chǔ)上當(dāng)指標(biāo)三取得最小值。此時最小，那么巡視時間也最短。最佳巡視方案為：組一：W—G—I—P—H—K—H—Y—L—F—W（巡視社區(qū)為：GIPHKYLFW）；組二：W—F—L—M—N—J—U—V—T—E—C—W（巡視社區(qū)為：MNJUVTEC）；組三：W—B—X—A—S—R—Q—D—C—W（巡視社區(qū)為：WBXASRQDC）。8.模型的評價8.1模型的優(yōu)點(diǎn)1、用Floyd算法構(gòu)建的模型容易理解，代碼編寫簡單，可廣泛用于求解兩點(diǎn)之間的最短距離；2、兩個動態(tài)規(guī)劃模型思路清晰，變量因子和目標(biāo)函數(shù)明確易懂。3、根據(jù)模型二我們可以得到每個社區(qū)的居民選擇繳費(fèi)的站點(diǎn)，以及他們的路線；由模型三可知3個派出所轄區(qū)內(nèi)有哪些社區(qū)以及去社區(qū)的最短路線。8.2模型的缺點(diǎn)：1、Floyd算法的時間復(fù)雜度比較高，不適合計(jì)算大量數(shù)據(jù)。2、模型三對派出所的個數(shù)做出了具體假設(shè)，不適用于解決多目標(biāo)問題。3、模型中沒考慮煤氣繳費(fèi)站和派出所設(shè)在社區(qū)之間的道路旁，且未考慮警察接聽電話和安排出警的時間。9.模型的改進(jìn)及推廣9.1模型的改進(jìn)1.在模型二和模型三中考慮將煤氣繳費(fèi)站和派出所建在鄰接的兩個社區(qū)之間的道路上，在原模型的基礎(chǔ)上再建立非線性規(guī)劃模型。2.在模型三中，考慮居民報(bào)警和派出所安排出警的時間，還有警車的啟動時間和路程。通過查閱資料，得到相關(guān)數(shù)據(jù)。3.在模型四中，因初始圈不同，最終得到的最優(yōu)圈也可能不同，所以我們采用多種方法產(chǎn)生多個初始圈，然后用二邊逐次修正法得到最優(yōu)圈。9.2模型的推廣我們構(gòu)建的模型一和模型二不僅可以用于繳費(fèi)站的最佳選址問題，還可以運(yùn)用于工廠、醫(yī)院、超市等的最佳選址問題和貨物配送問題。模型四可廣泛用于生活，如多地旅游的路線安排、送郵遞的路線選擇等，該模型有較大的應(yīng)用價值。10．參考文獻(xiàn)[1]殷劍宏圖論及其算法北京中國科技大學(xué)出版社2003[2]謝金星優(yōu)化建模與LINDO/LINGO軟件北京清華大學(xué)出版社2005[3]張潤琦動態(tài)規(guī)劃北京北京理工大學(xué)出版社198911.附錄問題一模型一程序如下：%w表示臨街矩陣；w=[0 inf 24 inf inf inf inf inf inf inf inf inf inf inf inf inf inf 20 inf inf inf inf 16 infinf 0 inf inf inf inf inf inf 28 inf inf inf inf inf inf inf inf inf inf inf inf 22 18 inf24 inf 0 11 9 inf inf inf inf inf inf inf inf inf inf inf inf inf 10 inf inf 15 inf infinf inf 11 0 inf inf inf inf inf inf inf inf inf inf inf 9 inf 8 inf inf inf inf inf infinf inf 9 inf 0 8 inf inf inf inf inf inf inf inf inf inf inf inf 6 9 inf inf inf infinf inf inf inf 8 0 11 inf inf inf inf 10 inf inf inf inf inf inf inf 14 inf 11 inf 11inf inf inf inf inf 11 0 inf 10 inf inf inf inf inf inf inf inf inf inf inf inf 15 inf infinf inf inf inf inf inf inf 0 inf inf 11 inf 15 inf 19 inf inf inf inf inf inf inf inf 8inf 28 inf inf inf inf 10 inf 0 inf inf inf inf inf 19 inf inf inf inf inf inf inf inf 25inf inf inf inf inf inf inf inf inf 0 inf 8 inf 6 inf inf inf inf inf 8 inf inf inf infinf inf inf inf inf inf inf 11 inf inf 0 inf 12 inf 23 inf inf inf inf inf inf inf inf infinf inf inf inf inf 10 inf inf inf 8 inf 0 9 inf inf inf inf inf inf inf inf inf inf 10inf inf inf inf inf inf inf 15 inf inf 12 9 0 6 inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf 6 inf inf 6 0 inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf 19 19 inf 23 inf inf inf 0 inf inf inf inf inf inf inf inf infinf inf inf 9 inf inf inf inf inf inf inf inf inf inf inf 0 7 inf inf inf 10 inf inf infinf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7 0 12 inf inf inf inf inf inf20 inf inf 8 inf inf inf inf inf inf inf inf inf inf inf inf 12 0 inf inf inf inf inf infinf inf 10 inf 6 inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf 7 inf inf infinf inf inf inf 9 14 inf inf inf 8 inf inf inf inf inf inf inf inf inf 0 15 inf inf infinf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10 inf inf 7 15 0 inf inf infinf 22 15 inf inf 11 15 inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 8 inf16 18 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8 0 infinf inf inf inf inf 11 inf 8 25 inf inf 10 inf inf inf inf inf inf inf inf inf inf inf 0];%floyd算法；D=w;n=size(w);path=zeros(n);fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;endendend%迭代，更新Dpathfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendenddisp(D);問題一模型二程序如下：!最短距離求解;model:!集合;sets:point/1..24/:r;distance(point,point):L;minvalue(point,point,point):num;endsets!數(shù)據(jù);data:r=1012186101548711131111892214871015281813;L=034242833353954495065455456683732203442412416463403748413337522851634352574757645447475422184424370119172836382647273632552027191018171523282848110202839474937583847436691682129192634393341920081927291738182723462330286913192719353317288011192118301019243831383614142111191139372839191103010294121303529424947252532152322545236472719300332611181521195057553333403038849283849292110330394231404519525957353542253325505126371718292639024812645334045238232937186563475838304111422402112182357646644324741491945432738181021183182109143741484624163121291054523647271930154012129063445525533203530381956573243232435214561814604039465129142935432468475566463829191945233734400697674525259445227375720923314250523357414539690717172510354342326427163038495759406448524676701224321742484920541982836475557456646555174171202937273436473447102161425333523442433295217242901572533254247182991425333583216201452253237150152533254154171913213240422347313529591017277150324032242215261911153025294121303544354234252532082