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

1、選址問題數(shù)學(xué)模型摘要 本題是用圖論與算法結(jié)合的數(shù)學(xué)模型，來解決居民各社區(qū)生活中存在三個(gè)的問題：合理的建立3個(gè)煤氣繳費(fèi)站的問題；如何建立合理的派出所；市領(lǐng)導(dǎo)人巡視路線最佳安排方案的問題。通過對原型進(jìn)行初步分析，分清各個(gè)要素及求解目標(biāo)，理出它們之間的聯(lián)系.在用圖論模型描述研究對象時(shí)，為了突出與求解目標(biāo)息息相關(guān)的要素，降低思考的復(fù)雜度。對客觀事物進(jìn)行抽象、化簡，并用圖來描述事物特征及內(nèi)在聯(lián)系的過程.建立圖論模型是為了簡化問題，突出要點(diǎn)，以便更深入地研究問題針對問題1：0-1規(guī)劃的窮舉法模型。該模型首先采用改善的floyd-warshall算法計(jì)算出城市間最短路徑矩陣見附錄表一；然后，用0-1規(guī)劃的窮

2、舉法獲得模型目標(biāo)函數(shù)的最優(yōu)解，其煤氣繳費(fèi)站設(shè)置點(diǎn)分別在q、w、m社區(qū)，各社區(qū)居民繳費(fèi)區(qū)域見表7-1，居民與最近的繳費(fèi)點(diǎn)之間平均距離的最小值11.7118百米。針對問題2：為避免資源的浪費(fèi)，且滿足條件，建立了以最少分組數(shù)為目標(biāo)函數(shù)的單目標(biāo)最優(yōu)化模型，用問題一中最短路徑的floyd算法，運(yùn)用lingo軟件編程計(jì)算,得到個(gè)社區(qū)之間的最短距離，再經(jīng)過計(jì)算可得到本問的派出所管轄范圍是2.5千米。最后采用就近歸組的搜索方法，逐步優(yōu)化，最終得到最少需要設(shè)置3個(gè)派出所，其所在位置有三種方案，分別是：（1）k區(qū)，w區(qū)，d區(qū)；（2）k區(qū)，w區(qū)，r區(qū)；（3）k區(qū)，w區(qū)，q區(qū)。最后根據(jù)效率和公平性和工作負(fù)荷考慮考慮，

3、其第三種方案為最佳方案，故選擇k區(qū)，w區(qū)，q區(qū)，其各自管轄區(qū)域路線圖如圖8-1。針對問題3：建立了雙目標(biāo)最優(yōu)化模型。首先將問題三轉(zhuǎn)化為三個(gè)售貨員的最佳旅行售貨員問題，得到以總路程最短和路程均衡度最小的目標(biāo)函數(shù)，采用最短路徑floyd算法，并用matlab和lingo軟件編程計(jì)算，得到最優(yōu)樹圖，然后按每塊近似有相等總路程的標(biāo)準(zhǔn)將最優(yōu)樹分成三塊，最后根據(jù)最小環(huán)路定理，得到三組巡視路程分別為11.8、11和12.5，三組巡視的總路程達(dá)到35.3，路程均衡度為12%,具體巡視路線安排見表9-1和圖9.2 。關(guān)鍵詞 floyd-warshall算法 窮舉法 最小生成樹 最短路徑1問題重述1.1問題背景這

4、是一個(gè)最優(yōu)選址問題，是一種重要的長期決策，它的好壞直接影響到服務(wù)方法，服務(wù)質(zhì)量，服務(wù)效率，服務(wù)成本，所以選址問題的研究有著重大的經(jīng)濟(jì)社會和軍事意義。1.2問題的提出實(shí)際問題：某城市共有24個(gè)社區(qū)a，b，c、y，任何兩個(gè)社區(qū)之間都是相通的，只是有的社區(qū)是有道路直接相連，有的是通過其他社區(qū)聯(lián)系在一起，各個(gè)社區(qū)對應(yīng)人口（單位：千人）如表1-1：表1-1編號abcdefghijkl人口10121861015487111311編號mnpqrstuvwxy人口11892214871015281813各社區(qū)的的道路連接如圖1.1 圖1.1（注：橫線上的數(shù)據(jù)表示相鄰社區(qū)之間的距離，單位：百米）1.3本文具體需

5、要解決的問題(1)為了方便社區(qū)居民繳納煤氣費(fèi)，煤氣公司現(xiàn)擬建三個(gè)煤氣繳費(fèi)站，問煤氣繳費(fèi)站怎樣選址才能使得居民與最近煤氣站之間的平均距離最小。(2) 市公安局?jǐn)M在該城區(qū)建立若干個(gè)派出所，請為派出所分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在3分鐘內(nèi)有警察（警車的時(shí)速為 50km/h）到達(dá)事發(fā)地，問設(shè)置多少個(gè)派出所比較合理，位置選在哪？(3) 社區(qū)w是市政府所在地，市領(lǐng)導(dǎo)從w出發(fā)巡視，分三組巡視所有社區(qū)，為了盡快完成巡視，合理的安排巡視路線2模型假設(shè)(1) 不考慮各社區(qū)的實(shí)際尺度，簡化為點(diǎn)處理 ；(2) 每個(gè)社區(qū)的居民都去繳費(fèi)站繳費(fèi)；(3) 只在社區(qū)擬建三個(gè)煤氣繳費(fèi)站；(4) 每個(gè)社

6、區(qū)的居民只能到離該社區(qū)最近的煤氣繳費(fèi)站繳費(fèi)；(5) 若與某些社區(qū)最近的繳費(fèi)站有若干個(gè)，即其可能與若干個(gè)繳費(fèi)點(diǎn)的距離相同且最鄰近，為保證各繳費(fèi)點(diǎn)工作負(fù)擔(dān)波動不大，該社區(qū)的居民只能到最鄰近的其中一個(gè)納稅點(diǎn)繳稅；(6) 假設(shè)路況相同，警車到達(dá)個(gè)社區(qū)途中按照規(guī)定的速度勻速行使；3符號說明表3-1符號符號意義第個(gè)社區(qū)的居民人口數(shù)社區(qū)間可行的最短路徑長度社區(qū)是否到社區(qū)繳費(fèi)是否在社區(qū)設(shè)置繳費(fèi)站均衡度賦權(quán)連通圖子圖中的最佳回路邊的邊權(quán)點(diǎn)的點(diǎn)權(quán)的各邊權(quán)之和的各點(diǎn)權(quán)之和；4問題分析4.1問題1的分析此題主要考慮居民平均最短距離，解決的是多源選址問題，找到三個(gè)煤氣繳費(fèi)站最佳選址。當(dāng)考慮到社區(qū)人口數(shù)量和和各社區(qū)之間的

7、距離時(shí)，人口量是影響平均最短距離的首要因素，盡可能把煤氣繳費(fèi)站建在人口密集的區(qū)域。 本問題的目標(biāo)是從24個(gè)社區(qū)組成區(qū)域內(nèi)中，選出一定3個(gè)社區(qū)設(shè)置煤氣繳費(fèi)站, 建立繳費(fèi)點(diǎn)網(wǎng)絡(luò)，實(shí)現(xiàn)居民與最近的繳費(fèi)點(diǎn)之間平均距離最小。對于每個(gè)社區(qū)繳費(fèi)點(diǎn)的建立與否只有兩種可能，所以可以通過計(jì)算社區(qū)間的最短路徑，然后充分利用社區(qū)的居民以及道路信息，采用合適的方法搜索繳費(fèi)點(diǎn)；再確定各繳費(fèi)點(diǎn)管轄的區(qū)域，直到求得最優(yōu)解。本問題重點(diǎn)要解決如何選擇繳費(fèi)點(diǎn)和如何劃分繳費(fèi)區(qū)域，即建立合理的最優(yōu)繳費(fèi)點(diǎn)搜索和區(qū)域劃分模型。4.2問題2的分析 此問題是突發(fā)事件應(yīng)急救援設(shè)施選址決策模型， 首先要求派出所分配管轄范圍覆蓋所有的區(qū)域, 在考慮

8、具體目標(biāo)時(shí),一是從快速反應(yīng)或者公平性考慮, 要求派出所至需求點(diǎn)的最大距離最小化; 二是從應(yīng)急救援設(shè)施的使用效率出發(fā), 要求派出所至需求區(qū)的總加權(quán)距離為最小。最后, 在建立應(yīng)派出所時(shí)還要考慮相關(guān)的成本資金問題，最少的派出所能在滿足所有要求的情況下覆蓋所有區(qū)域。4.3問題3的分析要求分三組（路）巡視，得到總路程最短且各組盡可能均衡的巡視路線，可轉(zhuǎn)化為三個(gè)售貨員的最佳旅行售貨員問題。先用matlab軟件編程計(jì)算得到加權(quán)網(wǎng)絡(luò)圖的最小生成樹，按每塊近似有相等總路程的標(biāo)準(zhǔn)將最小生成樹分成三塊，每一塊都轉(zhuǎn)化為一個(gè)最佳旅行售貨員問題。即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)w出發(fā)，行遍所有頂點(diǎn)至少一次，使得總權(quán)（路

9、程）最小.解決此類問題的一般方法是不現(xiàn)實(shí)的，本題可使用近似算法來求得近似最優(yōu)解.再確定總路程最短且滿足各組盡可能均衡的路線的目標(biāo)函數(shù)，最后對目標(biāo)函數(shù)適當(dāng)改進(jìn)，得到最終的雙目標(biāo)最優(yōu)化模型。5數(shù)據(jù)的分析 根據(jù)圖1.1和表1-1可以看出24個(gè)社區(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(8)，t(6)，u(9)

10、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(14)，j(8)，v(1

11、5)v3q(10)，t(7)，u(15)w5b(22)，c(15)，f(11)，g(15)，x(8)x3a(16)，b(18)，w(8)y4f(11)，h(8)，i(25)，l(10)若將24社區(qū)個(gè)之間的的道路網(wǎng)絡(luò)圖，社區(qū)看作一個(gè)圖的頂點(diǎn)，各社區(qū)的公路看作此圖對應(yīng)頂點(diǎn)間的邊，各條公路的長度看作對應(yīng)邊上的權(quán)，所給各社區(qū)的的道路連接如圖就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖。利用圖論中的一些算法對問題一，二三進(jìn)行簡答。同時(shí)根據(jù)個(gè)社區(qū)人口居住情況可以得出如下人口統(tǒng)計(jì)圖：圖5.1根據(jù)表5.1和圖5.1可以看出w，q兩個(gè)社區(qū)人口量最多，且從該社區(qū)出發(fā)的道路數(shù)比較多，很可能是煤氣繳費(fèi)站的設(shè)置點(diǎn)，同時(shí)也是派出所設(shè)置點(diǎn)；k社區(qū)人

12、口量也比較多，且連接各道路距離比較大，因此，k點(diǎn)可能是派出所設(shè)置點(diǎn)。這些是從圖形和圖標(biāo)表面直觀得出的，需要建模去驗(yàn)證。6求最短路徑問題一、二、三均需要計(jì)算出兩社區(qū)間距離矩陣，記錄對應(yīng)的最短路徑，以便分區(qū)時(shí)作為參考條件。最短路徑算法主要由改善的floyd-warshall算法實(shí)現(xiàn)，最后獲得由任意兩城市間距離矩陣和對應(yīng)的最短路徑。算法具體原理如下：1）利用社區(qū)間道路信息，構(gòu)造鄰接矩陣。若城市和間無直接連通的道路，則令元素為正無窮大；否則為和直接連通的道路長度。社區(qū)間道路信息可知是24，根據(jù)社區(qū)間道路信息表可以得出鄰接矩陣為，見附錄1。 2) 獲得兩社區(qū)間距離矩陣。、的元素分別表示為、， 對于所有的

13、城市、和，如果，則令，（表示從城市到要經(jīng)過城市，若，表示兩城市可直達(dá)）。經(jīng)過matlab和lingo軟件編程計(jì)算的出矩陣和，見附錄2其流程圖如下：開始構(gòu)造鄰接矩l陣兩社區(qū)間距離矩陣d社區(qū)間最短路徑矩陣r結(jié)束 圖6.1 改善的floyd-warshall算法流程圖7問題1的解答7.1模型的建立該模型首先采用改善的floyd-warshall算法計(jì)算出城市間最短路徑矩陣；然后，用0-1規(guī)劃的窮舉法獲得模型目標(biāo)函數(shù)的最優(yōu)解。1) 目標(biāo)函數(shù)的確立：為使得居民與最近煤氣站之間的平均距離最小，只要各社區(qū)居民在滿足區(qū)域要求的條件下，在各個(gè)社區(qū)的每個(gè)居民都去煤氣繳費(fèi)站的情況下，居民的平均路徑最短，因此只要求出

14、所有居民到離社區(qū)附近的繳費(fèi)站的總路程最小，然后除以個(gè)社區(qū)居民所有人數(shù)。故目標(biāo)函數(shù)為：2)約束條件的確立(1)若表示社區(qū)j不到社區(qū)i繳費(fèi)，表示社區(qū)j到社區(qū)i繳費(fèi)，根據(jù)模型假設(shè)（4）可知，每個(gè)社區(qū)的居民只能到附近最近的一個(gè)繳費(fèi)站繳費(fèi)，因此可有約束條件：，j=1,2,24。 (2)若表示不在社區(qū)i設(shè)置煤氣繳費(fèi)站，表示在社區(qū)i設(shè)置煤氣繳費(fèi)站，根據(jù)模型假設(shè)（3）可知，只能在社區(qū)設(shè)置3個(gè)煤氣繳費(fèi)站，所以有約束條件為： (3)只有在社區(qū)i設(shè)置繳費(fèi)點(diǎn)，社區(qū)j的居民才有可能去社區(qū)i繳費(fèi)；如果不在社區(qū)i設(shè)置繳費(fèi)點(diǎn)，社區(qū)j的居民不可能去社區(qū)i繳費(fèi)。因此，；,或者，即存在約束條件：。3）模型流程圖如下：7.2綜上所述

15、得到最優(yōu)化模型(1)目標(biāo)函數(shù)(2)約束條件7.3求解與結(jié)果分析該模型為線性規(guī)劃模型，我們采用matlab和lingo程序求解（見附錄三，模擬程序一），用實(shí)現(xiàn)0-1規(guī)劃法求得繳費(fèi)點(diǎn)、對應(yīng)的各繳費(fèi)區(qū)域，求得最小距離加權(quán)和，并求出其平均距離，其結(jié)果如下表：表7-1繳費(fèi)站位置繳費(fèi)社區(qū)qd，q，r，s，t，vwa，b，c，e，f，g，i，w，xmh，j，k，l，m，n，p，v，y最小距離加權(quán)和是337.3千米，目標(biāo)函數(shù)的最優(yōu)解，即居民與最近的繳費(fèi)點(diǎn)之間平均距離的最小值11.7118百米。8問題2的簡答8.1問題推斷根據(jù)上面求最短路徑求出的任意兩點(diǎn)的最短距離矩陣,可以看出到的最短距離最長，百米，要使能在3

16、分鐘內(nèi)有警察（警車的時(shí)速為 50km/h）到達(dá)事發(fā)地，則公安局最大行駛的路程為：為需要設(shè)置派出所的個(gè)數(shù)，要使派出所能夠在滿足要求的情況下覆蓋整個(gè)區(qū)域，則當(dāng)時(shí)，可以隨意的選取多種方案，但是很多社區(qū)可以可以同時(shí)滿足兩個(gè)或者三個(gè)派出所，且個(gè)別排除所管轄范圍很小，甚至只有一個(gè)社區(qū)，造成成本和資源的浪費(fèi)，因此可以推斷需要設(shè)置三個(gè)派出所，但這需要下面模型的驗(yàn)證。8.2模型的建立模型建立的方法是在問題1中改進(jìn)而來的，只是目標(biāo)函數(shù)發(fā)生改變，為：增加了一個(gè)約束條件：，即保證警察在3分鐘內(nèi)到達(dá)事發(fā)地。8.3綜上所述,我們得到問題一的模型目標(biāo)函數(shù)：約束條件為：8.4模型的求解與分析8.4.1求解結(jié)果用matlab軟

17、件編程計(jì)算（見附錄三，模擬程序二）應(yīng)設(shè)派出所三個(gè)，有三種設(shè)置方案。方案一：派出所位置應(yīng)設(shè)在社區(qū)k，d，w；其管轄范圍為：表8-1 派出所管轄范圍派出所位置管轄范圍管轄人口數(shù)（千人）總路程（單位：千米）dd，q，r，v，t，c,s,e100361wa，b，f，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è)在社

18、區(qū)k，q，w；管轄范圍如下表所示：表8-3 派出所管轄范圍派出所位置管轄范圍管轄人口數(shù)（千人）總路程（單位：千米）qd，q，r，s，t，v，c，u100357wa，b，e，f，g，i，x，w104kh，j，k，l，m，n，p，y848.4.2結(jié)果分析和最佳方案選擇根據(jù)以上三種方案的表8-1、8-2、8-3對比可以看出：（1） 方案一和方案二其管轄范圍的人口分布量不均勻；（2） 尤其是方案二的派出所設(shè)置點(diǎn)在w區(qū)，管轄范圍的人口量較大，給w區(qū)派出所帶來較大的工作負(fù)荷，影響工作效率。而r區(qū)的管轄范圍的人口量較小，工作量較少；（3） 方案一，二，三其人口均衡度分別是36.52%、45.45%、19.2

19、3%，故第三種方案的均衡度最好；（4） 根據(jù)每種方案的其總路程來看，其第三種方案的總路程最小，使總體效率得到提高。根據(jù)以上分析可以確定方案三為最佳方案，派出所的位置分別設(shè)置在q區(qū)、w區(qū)、k區(qū)，其管轄范圍圖如下： 圖8.19問題3的簡答9.1模型的建立(1)均衡度分析實(shí)際路程均衡度:為最大容許均衡度，顯然01，越小，說明分組的均衡度越好。(2)目標(biāo)函數(shù)的確定將社區(qū)公路示意圖抽象為一個(gè)賦權(quán)連通圖，再把圖分成三個(gè)子圖（=1,2,3）,在每個(gè)子圖中尋找最佳回路（=1,2,3），為回路的各邊權(quán)之和。要使總路程最短且各組又盡可能均衡的巡視路線，要使總路程最短，可以盡量讓每個(gè)子圖的邊權(quán)之和最小，確定目標(biāo)函數(shù)

20、：易知，上式兩個(gè)目標(biāo)函數(shù)相互矛盾，不可能同時(shí)達(dá)到。然而，要使總路程最短，可以盡量讓每個(gè)子圖的邊權(quán)之和最小，又邊權(quán)為，n為每個(gè)子圖中社區(qū)的總數(shù)，則有： 9.3綜上所述,我們得到問題一的模型9.4模型的求解與分析根據(jù)prim算法，用matlab軟件編程計(jì)算得到圖的最小生成樹（見附錄三，模擬程序三），如下圖所示：圖9.1最小生成樹模型由于在最優(yōu)樹上,各邊權(quán)接近,要使最優(yōu)樹分解時(shí), 分解結(jié)果盡量均衡，則各子圖包含的頂點(diǎn)就應(yīng)盡量接近（24/3=8）8個(gè)，由此得到最優(yōu)樹的分解原則如下：（1）分解點(diǎn)為w點(diǎn)或盡可能接近w點(diǎn)；（2）分解所得的三個(gè)子圖包含的頂點(diǎn)數(shù)盡可能接近8個(gè)；（3）盡量使分解所得的子圖為連通圖

21、；（4）盡量使子圖與w的最短路上的點(diǎn)在該子圈內(nèi)，盡量使各子圖內(nèi)部形成環(huán)路。根據(jù)以上原則，選取與w點(diǎn)相近的f點(diǎn)作為分解點(diǎn)，得到分解后的結(jié)果圖如下圖所示：圖9.2 分解后的結(jié)果圖通過增環(huán)、擴(kuò)環(huán)、換枝等方法，對子圖內(nèi)部進(jìn)行適當(dāng)調(diào)整優(yōu)化，尋找出最佳巡視回路，運(yùn)用lingo軟件編程計(jì)算得到結(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模型的評價(jià)、改進(jìn)以及推廣10.1模型的評價(jià)1

22、）模型的優(yōu)點(diǎn) (1）運(yùn)用了圖論的建立尋優(yōu)模型，建模的方法簡單易懂，盡管建模過程中應(yīng)用了圖論的最短路程理論，但仍可以用初等數(shù)學(xué)的方法解決的問題； (2)本問題的算法具有普遍性，對更普遍的這一類問題都能用本文的算法解決，只需更改相應(yīng)的參數(shù)值； (3)模型一采用窮舉法，結(jié)果可靠；(4) 建立的規(guī)劃模型能與實(shí)際緊密聯(lián)系，結(jié)合實(shí)際情況對問題進(jìn)行求解，使得模型具有很強(qiáng)的通用性和推廣性； (5) 模型的計(jì)算采用專業(yè)的數(shù)學(xué)軟件，可信度較高。2）模型的缺點(diǎn) （1）因?yàn)楸绢}村莊個(gè)數(shù)較小，之間距離較短，應(yīng)用歷遍的方法仍能應(yīng)用人工與計(jì)算機(jī)的結(jié)合在短時(shí)間內(nèi)求出解。然而對于復(fù)雜的實(shí)際問題如果點(diǎn)數(shù)很大，間距很大的情況可能耗

23、時(shí)很大；(2)模型和算法的選取比較單一，未能用到更多、更好的優(yōu)化模型，缺乏與其他模型的對比性； (3) 其中的窮舉法針對本題比較簡單，但對實(shí)際其他較復(fù)雜問題不具有通用性。10.2模型的改進(jìn)模型一可以采用分區(qū)模型，大大提高了程序的空間和時(shí)間復(fù)雜度；也可以用簡化模型，用最近鄰法大致確定最優(yōu)解的區(qū)域，然后再用窮舉法進(jìn)行求解，相比單純的窮舉法簡化了問題規(guī)模，又使所做出的模型答案具有信服力。10.3 模型的推廣本文所用的三個(gè)模型可以應(yīng)用的范圍較廣，在圖形數(shù)據(jù)處理及簡化方面均可運(yùn)用該模型均作為參考。這個(gè)模型不僅僅適用于居民繳費(fèi)站的最佳選址問題，它對規(guī)劃問題的求解都可以起到指導(dǎo)作用。 本題的求解是一個(gè)典型的

24、規(guī)劃問題，我們的模型的使用范圍非常廣泛，這一解決問題的模型可以推廣到其他服務(wù)性行業(yè)的選址中的方案的確定，例如旅行售貨員問題，只不過需要考慮的約束條件和追求的目標(biāo)有所不同。 參考文獻(xiàn)1趙希男. 主成分分析法評價(jià)功能淺析 j . 系統(tǒng)工程, 1995, 13( 2) :24 27.2王麗.圖論在算法設(shè)計(jì)中的應(yīng)用j. 系統(tǒng)工程理論與實(shí)踐,20073徐權(quán)智，楊晉浩，數(shù)學(xué)建模m，北京：高等教育出版社，2004附錄附錄一鄰接矩陣abcdefghijkla0inf24infinfinfinfinfinfinfinfinfbinf0infinfinfinfinfinf28infinfinfc24inf0119

25、infinfinfinfinfinfinfdinfinf110infinfinfinfinfinfinfinfeinfinf9inf08infinfinfinfinfinffinfinfinfinf8011infinfinfinf10ginfinfinfinfinf110inf10infinfinfhinfinfinfinfinfinfinf0infinf11infiinf28infinfinfinf10inf0infinfinfjinfinfinfinfinfinfinfinfinf0inf8kinfinfinfinfinfinfinf11infinf0inflinfinfinfinfinf

26、10infinfinf8inf0minfinfinfinfinfinfinf15infinf129ninfinfinfinfinfinfinfinfinf6infinfpinfinfinfinfinfinfinf1919inf23infqinfinfinf9infinfinfinfinfinfinfinfrinfinfinfinfinfinfinfinfinfinfinfinfs20infinf8infinfinfinfinfinfinfinftinfinf10inf6infinfinfinfinfinfinfuinfinfinfinf914infinfinf8infinfvinfinfinf

27、infinfinfinfinfinfinfinfinfwinf2215infinf1115infinfinfinfinfx1618infinfinfinfinfinfinfinfinfinfyinfinfinfinfinf11inf825infinf10mnpqrstuvwxyainfinfinfinfinf20infinfinfinf16infbinfinfinfinfinfinfinfinfinf2218infcinfinfinfinfinfinf10infinf15infinfdinfinfinf9inf8infinfinfinfinfinfeinfinfinfinfinfinf69in

28、finfinfinffinfinfinfinfinfinfinf14inf11inf11ginfinfinfinfinfinfinfinfinf15infinfh15inf19infinfinfinfinfinfinfinf8iinfinf19infinfinfinfinfinfinfinf25jinf6infinfinfinfinf8infinfinfinfk12inf23infinfinfinfinfinfinfinfinfl9infinfinfinfinfinfinfinfinfinf10m06infinfinfinfinfinfinfinfinfinfn60infinfinfinfin

29、finfinfinfinfinfpinfinf0infinfinfinfinfinfinfinfinfqinfinfinf07infinfinf10infinfinfrinfinfinf7012infinfinfinfinfinfsinfinfinfinf120infinfinfinfinfinftinfinfinfinfinfinf0inf7infinfinfuinfinfinfinfinfinfinf015infinfinfvinfinfinf10infinf7150infinfinfwinfinfinfinfinfinfinfinfinf08infxinfinfinfinfinfinfi

30、nfinfinf80infyinfinfinfinfinfinfinfinfinfinfinf0附錄二最短距離矩陣dabcdefghijkla03424283335395449506545b34037484133375228516343c2437011917283638264727d28481102028394749375838e334192008192729173818f3533172880111921183010g39372839191103010294121h54523647271930033261118i49283849292110330394231j50512637171829263

31、90248k65634758383041114224021l4543273818102118318210m54523647271930154012129n56573243232435214561814p684755664638291919452337q37572092331425052335741r326427163038495759406448s20541982836475557456646t34471021614253335234424u4247182991425333583216v415417191321324042234731w242215261911153025294121x1618

32、23342719233833374929y46442839191122825181910mnpqrstuvwxya545668373220344241241646b525747576454474754221844c363255202719101817152328d4743669168212919263439e2723462330286913192719f192438313836141421111911g303529424947252532152322h15211950575533334030388i404519525957353542253325j1264533404523823293718k

33、121823576466443247414919l91437414846241631212910m0634455255332035303819n6040394651291429354324p34400697674525259445227q4539690717172510354342r5246767012243217424849s55517417120293727343647t3329521724290157253325u20145225323715015253325v3529591017277150324032w3035443542342525320822x384352434836333340

34、8030y19242742494725253222300附錄三模擬程序一clcclearr=10 12 18 6 10 15 4 8 7 11 13 11 11 8 9 22 14 8 7 10 15 28 18 13;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

35、;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算法求每對頂點(diǎn)之

36、間的最短距離m=max(max(a)*n2;%m為充分大的正實(shí)數(shù)d=a+(a=0)-eye(n)*m;path=zeros(n);for k=1:n for i=1:n for j=1:n if d(i,j)d(i,k)+d(k,j) d(i,j)=d(i,k)+d(k,j); path(i,j)=k; end end endend %確定繳費(fèi)站的位置l=;l1=;l2=;s=;s(1)=0;k=2;for x=1:24 for y=1:24 for z=1:24 for n=1:24 l(1)=d(n,x); l(2)=d(n,y); l(3)=d(n,z); l1(n)=p(n)*min(l); end s(k)=sum(l1)/sum(r); b=1:k-2; if(s(k)d(i,k)+d(k,j) d(i,j)=d(i,k)+d(k,j); path(i,j)