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

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

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

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

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

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

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

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

9、程）最小.解決此類問題的一般方法是不現實的，本題可使用近似算法來求得近似最優解.再確定總路程最短且滿足各組盡可能均衡的路線的目標函數，最后對目標函數適當改進，得到最終的雙目標最優化模型。5數據的分析 根據圖1.1和表1-1可以看出24個社區人口密度不同，各社區之間的距離也不同，得出如下道路信息表：表5-1道路信息表社區編號從該社區出發的道路數與該社區直接相連的社區編號及道路長度(百米)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社區個之間的的道路網絡圖，社區看作一個圖的頂點，各社區的公路看作此圖對應頂點間的邊，各條公路的長度看作對應邊上的權，所給各社區的的道路連接如圖就轉化為加權網絡圖。利用圖論中的一些算法對問題一，二三進行簡答。同時根據個社區人口居住情況可以得出如下人口統計圖：圖5.1根據表5.1和圖5.1可以看出w，q兩個社區人口量最多，且從該社區出發的道路數比較多，很可能是煤氣繳費站的設置點，同時也是派出所設置點；k社區人

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

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

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

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

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

17、件編程計算（見附錄三，模擬程序二）應設派出所三個，有三種設置方案。方案一：派出所位置應設在社區k，d，w；其管轄范圍為：表8-1 派出所管轄范圍派出所位置管轄范圍管轄人口數（千人）總路程（單位：千米）dd，q，r，v，t，c,s,e100361wa，b，f，g，i，l，x, w, u115kh，j，k，m，n，p，y73方案二：派出所位置應設在社區k，r，w；其管轄范圍為:表8-2派出所管轄范圍派出所位置管轄范圍管轄人口數（千人）總路程（單位：千米）rd，q，r，v，t，s72368wa，b，c,f，g，i，x, w, u,e132kh，j，k，m，n，p，y,l84方案三：派出所位置應設在社

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

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

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

21、；（4）盡量使子圖與w的最短路上的點在該子圈內，盡量使各子圖內部形成環路。根據以上原則，選取與w點相近的f點作為分解點，得到分解后的結果圖如下圖所示：圖9.2 分解后的結果圖通過增環、擴環、換枝等方法，對子圖內部進行適當調整優化，尋找出最佳巡視回路，運用lingo軟件編程計算得到結果如下表：表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根據上表數據，得到分組路程均衡度為，所以這種分法的均衡性較好。10模型的評價、改進以及推廣10.1模型的評價1

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

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

24、規劃問題，我們的模型的使用范圍非常廣泛，這一解決問題的模型可以推廣到其他服務性行業的選址中的方案的確定，例如旅行售貨員問題，只不過需要考慮的約束條件和追求的目標有所不同。 參考文獻1趙希男. 主成分分析法評價功能淺析 j . 系統工程, 1995, 13( 2) :24 27.2王麗.圖論在算法設計中的應用j. 系統工程理論與實踐,20073徐權智，楊晉浩，數學建模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算法求每對頂點之

36、間的最短距離m=max(max(a)*n2;%m為充分大的正實數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 %確定繳費站的位置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)