選址問題數(shù)學(xué)模型

選址問題數(shù)學(xué)模型摘要本題是用圖論與算法結(jié)合的數(shù)學(xué)模型，來解決居民各社區(qū)生活中存在三個的問題：合理的建立3個煤氣繳費站的問題；如何建立合理的派出所；市領(lǐng)導(dǎo)人巡視路線最佳安排方案的問題。通過對原型進行初步分析，分清各個要素及求解目標(biāo)，理出它們之間的聯(lián)系.在用圖論模型描述研究對象時，為了突出與求解目標(biāo)息息相關(guān)的要素，降低思考的復(fù)雜度。對客觀事物進行抽象、化簡，并用圖來描述事物特征及內(nèi)在聯(lián)系的過程.建立圖論模型是為了簡化問題，突出要點，以便更深入地研究問題針對問題1：0-1規(guī)劃的窮舉法模型。該模型首先采用改善的Floyd-Warshall算法計算出城市間最短路徑矩陣見附錄表一；然后，用0-1規(guī)劃的窮舉法獲得模型目標(biāo)函數(shù)的最優(yōu)解，其煤氣繳費站設(shè)置點分別在Q、W、M社區(qū)，各社區(qū)居民繳費區(qū)域見表7-1，居民與最近的繳費點之間平均距離的最小值11.7118百米。針對問題2：為避免資源的浪費，且滿足條件，建立了以最少分組數(shù)為目標(biāo)函數(shù)的單目標(biāo)最優(yōu)化模型，用問題一中最短路徑的Floyd算法，運用LINGO軟件編程計算,得到個社區(qū)之間的最短距離，再經(jīng)過計算可得到本問的派出所管轄范圍是2.5千米。最后采用就近歸組的搜索方法，逐步優(yōu)化，最終得到最少需要設(shè)置3個派出所，其所在位置有三種方案，分別是：（1）K區(qū)，W區(qū)，D區(qū)；（2）K區(qū)，W區(qū)，R區(qū)；（3）K區(qū)，W區(qū)，Q區(qū)。最后根據(jù)效率和公平性和工作負荷考慮考慮，其第三種方案為最佳方案，故選擇K區(qū)，W區(qū)，Q區(qū)，其各自管轄區(qū)域路線圖如圖8-1。針對問題3：建立了雙目標(biāo)最優(yōu)化模型。首先將問題三轉(zhuǎn)化為三個售貨員的最佳旅行售貨員問題，得到以總路程最短和路程均衡度最小的目標(biāo)函數(shù)，采用最短路徑Floyd算法，并用MATLAB和LINGO軟件編程計算，得到最優(yōu)樹圖，然后按每塊近似有相等總路程的標(biāo)準(zhǔn)將最優(yōu)樹分成三塊，最后根據(jù)最小環(huán)路定理，得到三組巡視路程分別為11.8、11和12.5，三組巡視的總路程達到35.3，路程均衡度為12%,具體巡視路線安排見表9-1和圖9.2。關(guān)鍵詞Floyd-Warshall算法窮舉法最小生成樹最短路徑1問題重述1.1問題背景這是一個最優(yōu)選址問題，是一種重要的長期決策，它的好壞直接影響到服務(wù)方法，服務(wù)質(zhì)量，服務(wù)效率，服務(wù)成本，所以選址問題的研究有著重大的經(jīng)濟社會和軍事意義。1.2問題的提出實際問題：某城市共有24個社區(qū)A，B，C、、、、、、Y，任何兩個社區(qū)之間都是相通的，只是有的社區(qū)是有道路直接相連，有的是通過其他社區(qū)聯(lián)系在一起，各個社區(qū)對應(yīng)人口（單位：千人）如表1-1：表1-1編號ABCDEFGHIJKL人口10121861015487111311編號MNPQRSTUVWXY人口11892214871015281813各社區(qū)的的道路連接如圖1.1圖1.1（注：橫線上的數(shù)據(jù)表示相鄰社區(qū)之間的距離，單位：百米）1.3本文具體需要解決的問題(1)為了方便社區(qū)居民繳納煤氣費，煤氣公司現(xiàn)擬建三個煤氣繳費站，問煤氣繳費站怎樣選址才能使得居民與最近煤氣站之間的平均距離最小。(2)市公安局擬在該城區(qū)建立若干個派出所，請為派出所分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在3分鐘內(nèi)有警察（警車的時速為50km/h）到達事發(fā)地，問設(shè)置多少個派出所比較合理，位置選在哪？(3)社區(qū)W是市政府所在地，市領(lǐng)導(dǎo)從W出發(fā)巡視，分三組巡視所有社區(qū)，為了盡快完成巡視，合理的安排巡視路線2模型假設(shè)不考慮各社區(qū)的實際尺度，簡化為點處理；每個社區(qū)的居民都去繳費站繳費；只在社區(qū)擬建三個煤氣繳費站；每個社區(qū)的居民只能到離該社區(qū)最近的煤氣繳費站繳費；若與某些社區(qū)最近的繳費站有若干個，即其可能與若干個繳費點的距離相同且最鄰近，為保證各繳費點工作負擔(dān)波動不大，該社區(qū)的居民只能到最鄰近的其中一個納稅點繳稅；假設(shè)路況相同，警車到達個社區(qū)途中按照規(guī)定的速度勻速行使；3符號說明表3-1符號符號意義第個社區(qū)的居民人口數(shù)社區(qū)間可行的最短路徑長度社區(qū)是否到社區(qū)繳費是否在社區(qū)設(shè)置繳費站均衡度賦權(quán)連通圖子圖中的最佳回路邊的邊權(quán)點的點權(quán)的各邊權(quán)之和的各點權(quán)之和；；；4問題分析4.1問題1的分析此題主要考慮居民平均最短距離，解決的是多源選址問題，找到三個煤氣繳費站最佳選址。當(dāng)考慮到社區(qū)人口數(shù)量和和各社區(qū)之間的距離時，人口量是影響平均最短距離的首要因素，盡可能把煤氣繳費站建在人口密集的區(qū)域。本問題的目標(biāo)是從24個社區(qū)組成區(qū)域內(nèi)中，選出一定3個社區(qū)設(shè)置煤氣繳費站,建立繳費點網(wǎng)絡(luò)，實現(xiàn)居民與最近的繳費點之間平均距離最小。對于每個社區(qū)繳費點的建立與否只有兩種可能，所以可以通過計算社區(qū)間的最短路徑，然后充分利用社區(qū)的居民以及道路信息，采用合適的方法搜索繳費點；再確定各繳費點管轄的區(qū)域，直到求得最優(yōu)解。本問題重點要解決如何選擇繳費點和如何劃分繳費區(qū)域，即建立合理的最優(yōu)繳費點搜索和區(qū)域劃分模型。4.2問題2的分析此問題是突發(fā)事件應(yīng)急救援設(shè)施選址決策模型，首先要求派出所分配管轄范圍覆蓋所有的區(qū)域,在考慮具體目標(biāo)時,一是從快速反應(yīng)或者公平性考慮,要求派出所至需求點的最大距離最小化;二是從應(yīng)急救援設(shè)施的使用效率出發(fā),要求派出所至需求區(qū)的總加權(quán)距離為最小。最后,在建立應(yīng)派出所時還要考慮相關(guān)的成本資金問題，最少的派出所能在滿足所有要求的情況下覆蓋所有區(qū)域。4.3問題3的分析要求分三組（路）巡視，得到總路程最短且各組盡可能均衡的巡視路線，可轉(zhuǎn)化為三個售貨員的最佳旅行售貨員問題。先用MATLAB軟件編程計算得到加權(quán)網(wǎng)絡(luò)圖的最小生成樹，按每塊近似有相等總路程的標(biāo)準(zhǔn)將最小生成樹分成三塊，每一塊都轉(zhuǎn)化為一個最佳旅行售貨員問題。即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點W出發(fā)，行遍所有頂點至少一次，使得總權(quán)（路程）最小.解決此類問題的一般方法是不現(xiàn)實的，本題可使用近似算法來求得近似最優(yōu)解.再確定總路程最短且滿足各組盡可能均衡的路線的目標(biāo)函數(shù)，最后對目標(biāo)函數(shù)適當(dāng)改進，得到最終的雙目標(biāo)最優(yōu)化模型。5數(shù)據(jù)的分析根據(jù)圖1.1和表1-1可以看出24個社區(qū)人口密度不同，各社區(qū)之間的距離也不同，得出如下道路信息表：表5-1道路信息表社區(qū)編號從該社區(qū)出發(fā)的道路數(shù)與該社區(qū)直接相連的社區(qū)編號及道路長度(百米)A3C(24)，S(20)，X(16)B3I(28)，W(22)，X(18)C5A(24)，D(11)，E(9)，T(10)，W(15)D3C(11)，Q(9)，S(8)E4C(9)，F(xiàn)(8)，T(6)，U(9)F6E(8)，L(10)，U(14)，W(11)，G(11)，Y(11)G3F(11)，I(10)，W(15)H4M(15)，P(19)，K(11)，Y(8)I4B(28)，P(19)，G(10)，Y(25)J3L(8)，N(6)，U(8)K3M(12)，H(11)，P(23)L4F(10)，J(8)，Y(10)，M(9)M4N(6)，L(9)，H(15)，K(12)N2M(6)，J(6)P3H(19)，I(19)，K(23)Q3R(7)，D(9)，V(10)R2S(12)，Q(7)S3A(20)，D(8)，R(12)T3C(10)，E(6)，V(7)U4E(9)，F(xiàn)(14)，J(8)，V(15)V3Q(10)，T(7)，U(15)W5B(22)，C(15)，F(xiàn)(11)，G(15)，X(8)X3A(16)，B(18)，W(8)Y4F(11)，H(8)，I(25)，L(10)若將24社區(qū)個之間的的道路網(wǎng)絡(luò)圖，社區(qū)看作一個圖的頂點，各社區(qū)的公路看作此圖對應(yīng)頂點間的邊，各條公路的長度看作對應(yīng)邊上的權(quán)，所給各社區(qū)的的道路連接如圖就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖。利用圖論中的一些算法對問題一，二三進行簡答。同時根據(jù)個社區(qū)人口居住情況可以得出如下人口統(tǒng)計圖：圖5.1根據(jù)表5.1和圖5.1可以看出W，Q兩個社區(qū)人口量最多，且從該社區(qū)出發(fā)的道路數(shù)比較多，很可能是煤氣繳費站的設(shè)置點，同時也是派出所設(shè)置點；K社區(qū)人口量也比較多，且連接各道路距離比較大，因此，K點可能是派出所設(shè)置點。這些是從圖形和圖標(biāo)表面直觀得出的，需要建模去驗證。6求最短路徑問題一、二、三均需要計算出兩社區(qū)間距離矩陣，記錄對應(yīng)的最短路徑，以便分區(qū)時作為參考條件。最短路徑算法主要由改善的floyd-warshall算法實現(xiàn)，最后獲得由任意兩城市間距離矩陣和對應(yīng)的最短路徑。算法具體原理如下：1）利用社區(qū)間道路信息，構(gòu)造鄰接矩陣。若城市和間無直接連通的道路，則令元素為正無窮大；否則為和直接連通的道路長度。社區(qū)間道路信息可知是24，根據(jù)社區(qū)間道路信息表可以得出鄰接矩陣為，見附錄1。2)獲得兩社區(qū)間距離矩陣。、的元素分別表示為、，對于所有的城市、和，如果，則令，（表示從城市到要經(jīng)過城市，若，表示兩城市可直達）。經(jīng)過matlab和lingo軟件編程計算的出矩陣和，見附錄2其流程圖如下：開始開始構(gòu)造鄰接矩L陣兩社區(qū)間距離矩陣D社區(qū)間最短路徑矩陣R結(jié)束圖6.1改善的floyd-warshall算法流程圖7問題1的解答7.1模型的建立該模型首先采用改善的Floyd-Warshall算法計算出城市間最短路徑矩陣；然后，用0-1規(guī)劃的窮舉法獲得模型目標(biāo)函數(shù)的最優(yōu)解。目標(biāo)函數(shù)的確立：為使得居民與最近煤氣站之間的平均距離最小，只要各社區(qū)居民在滿足區(qū)域要求的條件下，在各個社區(qū)的每個居民都去煤氣繳費站的情況下，居民的平均路徑最短，因此只要求出所有居民到離社區(qū)附近的繳費站的總路程最小，然后除以個社區(qū)居民所有人數(shù)。故目標(biāo)函數(shù)為：2)約束條件的確立(1)若表示社區(qū)j不到社區(qū)i繳費，表示社區(qū)j到社區(qū)i繳費，根據(jù)模型假設(shè)（4）可知，每個社區(qū)的居民只能到附近最近的一個繳費站繳費，因此可有約束條件：，j=1,2,…24。(2)若表示不在社區(qū)i設(shè)置煤氣繳費站，表示在社區(qū)i設(shè)置煤氣繳費站，根據(jù)模型假設(shè)（3）可知，只能在社區(qū)設(shè)置3個煤氣繳費站，所以有約束條件為：(3)只有在社區(qū)i設(shè)置繳費點，社區(qū)j的居民才有可能去社區(qū)i繳費；如果不在社區(qū)i設(shè)置繳費點，社區(qū)j的居民不可能去社區(qū)i繳費。因此，；,或者，即存在約束條件：。3）模型流程圖如下：7.2綜上所述得到最優(yōu)化模型(1)目標(biāo)函數(shù)(2)約束條件7.3求解與結(jié)果分析該模型為線性規(guī)劃模型，我們采用Matlab和LINGO程序求解（見附錄三，模擬程序一），用實現(xiàn)0-1規(guī)劃法求得繳費點、對應(yīng)的各繳費區(qū)域，求得最小距離加權(quán)和，并求出其平均距離，其結(jié)果如下表：表7-1繳費站位置繳費社區(qū)QD，Q，R，S，T，VWA，B，C，E，F(xiàn)，G，I，W，XMH，J，K，L，M，N，P，V，Y最小距離加權(quán)和是337.3千米，目標(biāo)函數(shù)的最優(yōu)解，即居民與最近的繳費點之間平均距離的最小值11.7118百米。8問題2的簡答8.1問題推斷根據(jù)上面求最短路徑求出的任意兩點的最短距離矩陣,可以看出到的最短距離最長，百米，要使能在3分鐘內(nèi)有警察（警車的時速為50km/h）到達事發(fā)地，則公安局最大行駛的路程為：為需要設(shè)置派出所的個數(shù)，要使派出所能夠在滿足要求的情況下覆蓋整個區(qū)域，則當(dāng)時，可以隨意的選取多種方案，但是很多社區(qū)可以可以同時滿足兩個或者三個派出所，且個別排除所管轄范圍很小，甚至只有一個社區(qū)，造成成本和資源的浪費，因此可以推斷需要設(shè)置三個派出所，但這需要下面模型的驗證。8.2模型的建立模型建立的方法是在問題1中改進而來的，只是目標(biāo)函數(shù)發(fā)生改變，為：增加了一個約束條件：，即保證警察在3分鐘內(nèi)到達事發(fā)地。8.3綜上所述,我們得到問題一的模型目標(biāo)函數(shù)：約束條件為：8.4模型的求解與分析8.4.1求解結(jié)果用MATLAB軟件編程計算（見附錄三，模擬程序二）應(yīng)設(shè)派出所三個，有三種設(shè)置方案。方案一：派出所位置應(yīng)設(shè)在社區(qū)K，D，W；其管轄范圍為：表8-1派出所管轄范圍派出所位置管轄范圍管轄人口數(shù)（千人）總路程（單位：千米）DD，Q，R，V，T，C,S,E100361WA，B，F(xiàn)，G，I，L，X,W,U115KH，J，K，M，N，P，Y73方案二：派出所位置應(yīng)設(shè)在社區(qū)K，R，W；其管轄范圍為:表8-2派出所管轄范圍派出所位置管轄范圍管轄人口數(shù)（千人）總路程（單位：千米）RD，Q，R，V，T，S72368WA，B，C,F，G，I，X,W,U,E132KH，J，K，M，N，P，Y,L84方案三：派出所位置應(yīng)設(shè)在社區(qū)K，Q，W；管轄范圍如下表所示：表8-3派出所管轄范圍派出所位置管轄范圍管轄人口數(shù)（千人）總路程（單位：千米）QD，Q，R，S，T，V，C，U100357WA，B，E，F(xiàn)，G，I，X，W104KH，J，K，L，M，N，P，Y848.4.2結(jié)果分析和最佳方案選擇根據(jù)以上三種方案的表8-1、8-2、8-3對比可以看出：方案一和方案二其管轄范圍的人口分布量不均勻；尤其是方案二的派出所設(shè)置點在W區(qū)，管轄范圍的人口量較大，給W區(qū)派出所帶來較大的工作負荷，影響工作效率。而R區(qū)的管轄范圍的人口量較小，工作量較少；方案一，二，三其人口均衡度分別是36.52%、45.45%、19.23%，故第三種方案的均衡度最好；根據(jù)每種方案的其總路程來看，其第三種方案的總路程最小，使總體效率得到提高。根據(jù)以上分析可以確定方案三為最佳方案，派出所的位置分別設(shè)置在Q區(qū)、W區(qū)、K區(qū)，其管轄范圍圖如下：圖8.19問題3的簡答9.1模型的建立(1)均衡度分析實際路程均衡度:為最大容許均衡度，顯然0≤≤1，越小，說明分組的均衡度越好。(2)目標(biāo)函數(shù)的確定將社區(qū)公路示意圖抽象為一個賦權(quán)連通圖，再把圖分成三個子圖（=1,2,3）,在每個子圖中尋找最佳回路（=1,2,3），為回路的各邊權(quán)之和。要使總路程最短且各組又盡可能均衡的巡視路線，要使總路程最短，可以盡量讓每個子圖的邊權(quán)之和最小，確定目標(biāo)函數(shù)：易知，上式兩個目標(biāo)函數(shù)相互矛盾，不可能同時達到。然而，要使總路程最短，可以盡量讓每個子圖的邊權(quán)之和最小，又邊權(quán)為，n為每個子圖中社區(qū)的總數(shù)，則有：9.3綜上所述,我們得到問題一的模型9.4模型的求解與分析根據(jù)prim算法，用MATLAB軟件編程計算得到圖的最小生成樹（見附錄三，模擬程序三），如下圖所示：圖9.1最小生成樹模型由于在最優(yōu)樹上,各邊權(quán)接近,要使最優(yōu)樹分解時,分解結(jié)果盡量均衡，則各子圖包含的頂點就應(yīng)盡量接近（24/3=8）8個，由此得到最優(yōu)樹的分解原則如下：（1）分解點為W點或盡可能接近W點；（2）分解所得的三個子圖包含的頂點數(shù)盡可能接近8個；（3）盡量使分解所得的子圖為連通圖；（4）盡量使子圖與W的最短路上的點在該子圈內(nèi)，盡量使各子圖內(nèi)部形成環(huán)路。根據(jù)以上原則，選取與W點相近的F點作為分解點，得到分解后的結(jié)果圖如下圖所示：圖9.2分解后的結(jié)果圖通過增環(huán)、擴環(huán)、換枝等方法，對子圖內(nèi)部進行適當(dāng)調(diào)整優(yōu)化，尋找出最佳巡視回路，運用LINGO軟件編程計算得到結(jié)果如下表：表9-1三組巡視路線小組路線路程之和總路程一W,F,G,I,B,X,A,X,W118353二W,C,T,V,U,Q,R,Q,S,D,C,W110三W,F,L,J,N,M,K,P,H,Y,F,W125根據(jù)上表數(shù)據(jù)，得到分組路程均衡度為，所以這種分法的均衡性較好。10模型的評價、改進以及推廣10.1模型的評價1）模型的優(yōu)點(1）運用了圖論的建立尋優(yōu)模型，建模的方法簡單易懂，盡管建模過程中應(yīng)用了圖論的最短路程理論，但仍可以用初等數(shù)學(xué)的方法解決的問題；(2)本問題的算法具有普遍性，對更普遍的這一類問題都能用本文的算法解決，只需更改相應(yīng)的參數(shù)值；(3)模型一采用窮舉法，結(jié)果可靠；(4)建立的規(guī)劃模型能與實際緊密聯(lián)系，結(jié)合實際情況對問題進行求解，使得模型具有很強的通用性和推廣性；(5)模型的計算采用專業(yè)的數(shù)學(xué)軟件，可信度較高。2）模型的缺點（1）因為本題村莊個數(shù)較小，之間距離較短，應(yīng)用歷遍的方法仍能應(yīng)用人工與計算機的結(jié)合在短時間內(nèi)求出解。然而對于復(fù)雜的實際問題如果點數(shù)很大，間距很大的情況可能耗時很大；(2)模型和算法的選取比較單一，未能用到更多、更好的優(yōu)化模型，缺乏與其他模型的對比性；(3)其中的窮舉法針對本題比較簡單，但對實際其他較復(fù)雜問題不具有通用性。10.2模型的改進模型一可以采用分區(qū)模型，大大提高了程序的空間和時間復(fù)雜度；也可以用簡化模型，用最近鄰法大致確定最優(yōu)解的區(qū)域，然后再用窮舉法進行求解，相比單純的窮舉法簡化了問題規(guī)模，又使所做出的模型答案具有信服力。10.3模型的推廣本文所用的三個模型可以應(yīng)用的范圍較廣，在圖形數(shù)據(jù)處理及簡化方面均可運用該模型均作為參考。這個模型不僅僅適用于居民繳費站的最佳選址問題，它對規(guī)劃問題的求解都可以起到指導(dǎo)作用。本題的求解是一個典型的規(guī)劃問題，我們的模型的使用范圍非常廣泛，這一解決問題的模型可以推廣到其他服務(wù)性行業(yè)的選址中的方案的確定，例如旅行售貨員問題，只不過需要考慮的約束條件和追求的目標(biāo)有所不同。參考文獻[1]趙希男.主成分分析法評價功能淺析[J].系統(tǒng)工程,1995,13(2):24~27.[2]王麗.圖論在算法設(shè)計中的應(yīng)用[J].系統(tǒng)工程理論與實踐,2007[3]徐權(quán)智，楊晉浩，數(shù)學(xué)建模[M]，北京：高等教育出版社，2004附錄附錄一鄰接矩陣ABCDEFGHIJKLA0Inf24InfInfInfInfInfInfInfInfInfBInf0InfInfInfInfInfInf28InfInfInfC24Inf0119InfInfInfInfInfInfInfDInfInf110InfInfInfInfInfInfInfInfEInfInf9Inf08InfInfInfInfInfInfFInfInfInfInf8011InfInfInfInf10GInfInfInfInfInf110Inf10InfInfInfHInfInfInfInfInfInfInf0InfInf11InfIInf28InfInfInfInf10Inf0InfInfInfJInfInfInfInfInfInfInfInfInf0Inf8KInfInfInfInfInfInfInf11InfInf0InfLInfInfInfInfInf10InfInfInf8Inf0MInfInfInfInfInfInfInf15InfInf129NInfInfInfInfInfInfInfInfInf6InfInfPInfInfInfInfInfInfInf1919Inf23InfQInfInfInf9InfInfInfInfInfInfInfInfRInfInfInfInfInfInfInfInfInfInfInfInfS20InfInf8InfInfInfInfInfInfInfInfTInfInf10Inf6InfInfInfInfInfInfInfUInfInfInfInf914InfInfInf8InfInfVInfInfInfInfInfInfInfInfInfInfInfInfWInf2215InfInf1115InfInfInfInfInfX1618InfInfInfInfInfInfInfInfInfInfYInfInfInfInfInf11Inf825InfInf10MNPQRSTUVWXYAInfInfInfInfInf20InfInfInfInf16InfBInfInfInfInfInfInfInfInfInf2218InfCInfInfInfInfInfInf10InfInf15InfInfDInfInfInf9Inf8InfInfInfInfInfInfEInfInfInfInfInfInf69InfInfInfInfFInfInfInfInfInfInfInf14Inf11Inf11GInfInfInfInfInfInfInfInfInf15InfInfH15Inf19InfInfInfInfInfInfInfInf8IInfInf19InfInfInfInfInfInfInfInf25JInf6InfInfInfInfInf8InfInfInfInfK12Inf23InfInfInfInfInfInfInfInfInfL9InfInfInfInfInfInfInfInfInfInf10M06InfInfInfInfInfInfInfInfInfInfN60InfInfInfInfInfInfInfInfInfInfPInfInf0InfInfInfInfInfInfInfInfInfQInfInfInf07InfInfInf10InfInfInfRInfInfInf7012InfInfInfInfInfInfSInfInfInfInf120InfInfInfInfInfInfTInfInfInfInfInfInf0Inf7InfInfInfUInfInfInfInfInfInfInf015InfInfInfVInfInfInf10InfInf7150InfInfInfWInfInfInfInfInfInfInfInfInf08InfXInfInfInfInfInfInfInfInfInf80InfYInfInfInfInfInfInfInfInfInfInfInf0附錄二最短距離矩陣DABCDEFGHIJKLA03424283335395449506545B34037484133375228516343C2437011917283638264727D28481102028394749375838E334192008192729173818F3533172880111921183010G39372839191103010294121H54523647271930033261118I49283849292110330394231J5051263717182926390248K65634758383041114224021L4543273818102118318210M54523647271930154012129N56573243232435214561814P684755664638291919452337Q37572092331425052335741R326427163038495759406448S20541982836475557456646T34471021614253335234424U4247182991425333583216V415417191321324042234731W242215261911153025294121X161823342719233833374929Y46442839191122825181910MNPQRSTUVWXYA545668373220344241241646B525747576454474754221844C363255202719101817152328D4743669168212919263439E2723462330286913192719F192438313836141421111911G303529424947252532152322H15211950575533334030388I404519525957353542253325J1264533404523823293718K121823576466443247414919L91437414846241631212910M0634455255332035303819N6040394651291429354324P34400697674525259445227Q4539690717172510354342R5246767012243217424849S55517417120293727343647T3329521724290157253325U20145225323715015253325V3529591017277150324032W3035443542342525320822X3843524348363333408030Y19242742494725253222300附錄三模擬程序一clcclearR=[1012186101548711131111892214871015281813];n=24;a=zeros(n);a(1,3)=24;a(1,18)=20;a(1,23)=16;a(2,23)=18;a(2,22)=22;a(2,9)=28;a(3,5)=9;a(3,19)=10;a(3,4)=11;a(3,22)=15;a(4,16)=9;a(4,18)=8;a(5,19)=6;a(5,6)=8;a(5,20)=9;a(6,7)=11;a(6,24)=11;a(6,12)=10;a(6,20)=14;a(6,22)=11;a(7,9)=10;a(7,22)=15;a(8,15)=19;a(8,11)=11;a(8,13)=15;a(8,24)=8;a(9,15)=19;a(9,24)=25;a(10,12)=8;a(10,14)=6;a(10,20)=8;a(11,13)=12;a(11,15)=23;a(12,24)=10;a(12,13)=9;a(13,14)=6;a(16,17)=7;a(16,21)=10;a(17,18)=12;a(19,21)=7;a(20,21)=15;a(22,23)=8;a=a+a';%Floyd算法求每對頂點之間的最短距離M=max(max(a))*n^2;%M為充分大的正實數(shù)d=a+((a==0)-eye(n))*M;path=zeros(n);fork=1:nfori=1:nforj=1:nifd(i,j)>d(i,k)+d(k,j)d(i,j)=d(i,k)+d(k,j);path(i,j)=k;endendendend%確定繳費站的位置L=[];L1=[];L2=[];S=[];S(1)=0;k=2;forx=1:24fory=1:24forz=1:24forn=1:24L(1)=d(n,x);L(2)=d(n,y);L(3)=d(n,z);L1(n)=p(n)*min(L);endS(k)=sum(L1)/sum(R);b=1:k-2;if(S(k)<S(k-b))L2(1)=x;L2(2)=y;L2(3)=z;endk=k+1;endendendfori=1:k-2S(i)=S(i+1);endSmin=min(S);%最小平均距離wz=L2;%繳費站的位置fprintf('最小平均距離:')disp(Smin)fprintf('繳費站的位置:')disp(wz)模擬程序二clcclearn=24;a=zeros(n);a(1,3)=24;a(1,18)=20;a(1,23)=16;a(2,23)=18;a(2,22)=22;a(2,9)=28;a(3,5)=9;a(3,19)=10;a(3,4)=11;a(3,22)=15;a(4,16)=9;a(4,18)=8;a(5,19)=6;a(5,6)=8;a(5,20)=9;a(6,7)=11;a(6,24)=11;a(6,12)=10;a(6,20)=14;a(6,22)=11;a(7,9)=10;a(7,22)=15;a(8,15)=19;a(8,11)=11;a(8,13)=15;a(8,24)=8;a(9,15)=19;a(9,24)=25;a(10,12)=8;a(10,14)=6;a(10,20)=8;a(11,13)=12;a(11,15)=23;a(12,24)=10;a(12,13)=9;a(13,14)=6;a(16,17)=7;a(16,21)=10;a(17,18)=12;a(19,21)=7;a(20,21)=15;a(22,23)=8;a=a+a';%Floyd算法求每對頂點之間的最短距離M=max(max(a))*n^2;%M為充分大的正實數(shù)d=a+((a==0)-eye(n))*M;path=zeros(n);fork=1:nfori=1:nforj=1:nifd(i,j)>d(i,k)+d(k,j)d(i,j)=d(i,k)+d(k,j);path(i,j)=k;endendendend%確定派出所的位置L=[];L1=[];L2=[];S=[];c=1;forx=1:24fory=1:24forz=1:24forn=1:24L(1)=d(n,x);L(2)=d(n,y);L(3)=d(n,z);L1(n)=min(L);endb=1:n;if(L1(b)<=25)L2(1)=x;