數(shù)學(xué)建模選址問題參考模板

1、選址問題摘要 目前，社區(qū)的優(yōu)化管理和最佳服務(wù)已經(jīng)成為一種趨勢，并且為城市的發(fā)展作出了一定的貢獻。本文針對在社區(qū)中選址問題及巡視路線問題，分別建立了多目標決策模型、約束最優(yōu)化線路模型，并分別提供了選址社區(qū)和巡視路線。對于問題一，我們建立了單目標優(yōu)化模型，考慮到各社區(qū)居民到收費站點的平均距離最小，我們使用floyd 算法并通過matlab 編程，算出任意兩個社區(qū)之間的最短路徑，并以此作為工具，使用01變量列出了目標函數(shù)。在本題中，我們根據(jù)收費站數(shù)、超額覆蓋等確定了約束條件，以保證收費站覆蓋每個社區(qū)，同時保證居民與最近煤氣站之間的平均距離最小,最終利用lingo 軟件求得收費站建在M、Q、W三個社區(qū)

2、。對于問題二，同樣是單目標優(yōu)化模型，較之問題一不同的是，問題二不需要考慮人口問題，但需要確定選址的個數(shù)。接下來的工作分了兩步，第一步，我們通過01變量列出目標函數(shù)，以超額覆蓋等確定約束條件，用lingo 軟件編程求出最小派出所站點的個數(shù);第二步，我們利用第一步中求出的派出所個數(shù)作為新的約束條件，建立使總距離最小的優(yōu)化模型，最終利用lingo 軟件求得三個派出所分別建在W、Q、K社區(qū)。對于問題三，我們建立了約束最優(yōu)化線路模型，根據(jù)floyd 算法求得的任意兩個社區(qū)之間的最短路徑，建立了以w 點為樹根的最短路徑生成樹，并據(jù)此對各點的集中區(qū)域進行劃分，再利用破圈法得到最短回路。在本題中，我們初定了兩

3、種方案，并引入均衡度對兩種方案進行比較，最終采用了方案二。最后，我們用matlab編程求解方案二中各組的巡視路線為113百米，123百米，117百米，均衡度8.13%。具體路線見關(guān)鍵詞：最短路徑 hamilton圈 最優(yōu)化 floyd算法1 / 151問題重述在社區(qū)中繳費站的選址對于居民快速繳費和充分的利用公共設(shè)施的資源有很重要的指導(dǎo)意義。某城市共有24個社區(qū)，各社區(qū)的人口（單位：千人）如下:編號ABCDEFGHIJKL人口10121861015487111311編號MNPQRSTUVWXY人口11892214871015281813各社區(qū)的的道路連接如下圖 （注：橫線上的數(shù)據(jù)表示相鄰社區(qū)之間

4、的距離，單位：百米）本題要解決的問題如下：（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è)與符號說明2.1模型假設(shè)：假設(shè)1：相鄰兩個社區(qū)之間的道路近似認為是直線，把城市地圖抽象成由點和線

5、組成的無向網(wǎng)絡(luò)賦權(quán)圖；假設(shè)2：假設(shè)警車到達事發(fā)點的途中沒有障礙，即不考慮路況和其他突發(fā)事件的影響，警車按照其行駛速度勻速行駛直至到達事件發(fā)生的地點。假設(shè)3：巡視過程中，各個小組行駛的速度基本相同。假設(shè)4：各個小組巡視過程中，不因特殊情況延誤時間。假設(shè)5：各個小組巡視過程中，不考慮小組在每個社區(qū)的停留時間。假設(shè)6：不考慮警察的反應(yīng)時間，即接到事故報警后，能夠立即趕往事故發(fā)生地。2.2 模型符號： 收費站集合（一）或派出所集合（二）社區(qū)集合 社區(qū)的人口數(shù)，即社區(qū)的權(quán)重 社區(qū)到社區(qū)的最短距離 社區(qū)被超額覆蓋的次數(shù)（01）變量，1表示在社區(qū)建立煤氣站（一）或派出所（二）（01）變量，1表示煤氣站（一）

6、或派出所覆蓋社區(qū)說明：“一”代表問題一中符號表示的意義，“二”表示問題二中符號所表示的意義。3問題分析3.1問題一分析本問題的目標是從一個有多個社區(qū)組成的區(qū)域中，選出一定數(shù)目的社區(qū)設(shè)置收費站，建立所得收費站網(wǎng)絡(luò)，實現(xiàn)居民與最近的收費站之間平均距離最小.在多目標的選址問題中，宜采用單目標優(yōu)化模型，并充分體現(xiàn)收費站的效率性。首先我們使用floyd 算法并通過matlab 編程，算出任意兩個社區(qū)之間的最短路徑，并以此作為工具，使用01變量列出了目標函數(shù)。在問題一中，我們根據(jù)收費站數(shù)、超額覆蓋等確定了約束條件，以保證收費站覆蓋每個社區(qū)，同時保證居民與最近煤氣站之間的平均距離最小3.2問題二分析第二問需

7、要求出在相應(yīng)的時間限制下，為了使中位選址問題達到最優(yōu)需要，在該社區(qū)建立派出所站點的個數(shù)。根據(jù)警車的行駛速度50km/h以及反應(yīng)時間限制在3分鐘內(nèi)，得出派出所站點與相應(yīng)區(qū)域內(nèi)的點的最大距離應(yīng)小于d3×50/60km=25(百米)。運用中位點問題模型，采用參數(shù)規(guī)劃的約束法，可以很好的解決該問題。首先我們利用floyd算法算出每對頂點的最短距離，然后利用單目標最優(yōu)化模型以派出所的個數(shù)的和為目標函數(shù)，保證每個點被覆蓋一次，考慮某個社區(qū)派出所站點與社區(qū)是否被站點覆蓋的關(guān)系，其它點到站點的最小距離小于等于25百米，利用lingo軟件求出最少派出所的個數(shù)，最后以其它點到站點的最小總的距離為目標函數(shù)

8、。在第一步的基礎(chǔ)上加上站點的個數(shù)，最終利用lingo軟件求出站點位置。3.3問題三分析此題研究的是最佳巡視路線設(shè)計問題，要求從w點出發(fā)分三組巡視完所有社區(qū)后，并盡快回到w點。此問題可以轉(zhuǎn)化為推銷員問題，再設(shè)計相應(yīng)的算法求解。為了使三組能夠在短時間內(nèi)完成巡視，那么就要求三組所走總路程最小；同時，為了使三組能夠在幾乎等量的時間內(nèi)完成巡視，我們就要求三組巡視路程盡可能的均衡。綜上兩點考慮，我們建立了以三組巡視路線總路程值最小和三組路程的均衡度兩個目標函數(shù)的模型。首先我們可以利用第一問求出的w點到其余頂點的最短路, 建立了以w 點為樹根的最短路徑生成樹,其中規(guī)定從w點出發(fā)的樹枝稱為干支，然后把所得的生

9、成樹按以下原則分成三組。準則一：盡量使同一干支上及其分支上的點分在同一組；準則二：應(yīng)將相鄰的干支上的點分在同一組；準則三：盡量將長的干支與短的干支分在同一組。然后利用hamilton算法分別構(gòu)造出每組路線值最小的回路，如果兩個目標值不佳，我們可以重新分組，經(jīng)過多次調(diào)整達到較為合適的結(jié)果，最終找出該區(qū)域的最佳巡視路徑。4數(shù)據(jù)分析4.1模型一的數(shù)據(jù)分析：首先畫出各社區(qū)的人口圖 根據(jù)人口圖可以看出C社區(qū)、Q社區(qū)和W社區(qū)的人口比較多，在考慮建煤氣站時應(yīng)該使這些地區(qū)到煤氣站的距離比較短，這樣的話選的煤氣站的地址會更合理。4.2模型二的分析：由于要求警車3分鐘類到達事發(fā)地點。因根據(jù)警車的行駛速度50km/

10、h，得出派出所站點與相應(yīng)區(qū)域內(nèi)的點的最大距離應(yīng)小于d3×50/60km=25(百米)。即即警車行駛最遠行車距離為25百米4.3模型三的數(shù)據(jù)分析：（1）定義 一個圖G是指一個二元組（V（G）,E(G)）,其中元素稱為圖G的頂點（2）給出一種求最小生成樹的方法（破圈法）：設(shè)G由n個結(jié)點構(gòu)成的連通圖，下面的算法產(chǎn)生的最小生成樹。算法的基本思想：先將圖G的邊按權(quán)的遞減順序排列后，依次檢驗每條邊，在保持連通的情況下，每次刪除最大權(quán)邊，直到余下n-1條邊為止。（3）均衡度的定義 （越小說明分組的均衡性越好）。（4）我們把24個社區(qū)看作24個頂點，它們之間的距離為權(quán)重，建立鄰接矩陣，求出各點到w的

11、最短距離。則畫出以w為根的樹如下：5模型的建立與求解首先，我們用floyd算法求出任意兩個社區(qū)之間的最短距離，以便問題一，問題二，問題三的求解。5.1問題一：煤氣站的選址問題5.1.1 確定目標函數(shù)由問題一的題目要求，要求煤氣站的選址能夠使居民到最近煤氣站的平均距離最小，此問題等價于求煤氣站的選址使24個社區(qū)的所有居民到最近煤氣站的總距離最小。因此，我們把目標函數(shù)定為：所有居民到最近煤氣站的總距離S.5.1.2 確定約束條件（1）根據(jù)題目要求，所建煤氣站數(shù)目為3，即： （2）只有在社區(qū)建立了煤氣站，社區(qū)才能被覆蓋，即： （3）社區(qū)被社區(qū)覆蓋的總次數(shù)減去被超額覆蓋的次數(shù)應(yīng)該大于等于1，即： （4

12、） î 型不僅僅可以用于災(zāi)情的巡視，還可以解決旅行線路的設(shè)定等。íì=社區(qū)建立煤氣站不在社區(qū)建立煤氣站在iiyi01（5） 5.1.3綜上所述，得到問題一的單目標最優(yōu)化模型5.1.4 模型一的求解及結(jié)果分析我們通過lingo軟件編程,得到三個煤氣站應(yīng)分別建在W,Q,M社區(qū)，居民與最近煤氣站的平均距離為11.7118百米。首先這三個社區(qū)分別分布于整個區(qū)域的西北部，東部，和南部，可以為各個社區(qū)的居民服務(wù)，從而又使平均距離達到最小，滿足了題目要求。5.2問題二：派處所的選址問題 5.2.1確定目標函數(shù)一在已知警車運行速度的前提下，我們將時間約束轉(zhuǎn)換成最遠距離約束，即最遠

13、行車距離為25百米。此時我們并不知道要在最遠行車距離為25百米的前提下，需要建多少個派出所站點才能覆蓋全部社區(qū)。因此，我們首先以最小派出所站點的個數(shù)為目標函數(shù)，即：5.2.2 確定目標函數(shù)一的約束條件（1）每個社區(qū)且僅被一個派出所覆蓋，即： （2）（2）派出所到社區(qū)的最短距離小于等于25百米，即： （3）只有在社區(qū)建立派出所，它才有可能覆蓋社區(qū)，即：5.2.3 綜上所述。目標函數(shù)一的模型為：用lingo軟件編程計算出在警車限制時間內(nèi)，在該社區(qū)建立的最少派出所站點為3。5.2.4 確定目標函數(shù)二在派出所的個數(shù)為3的前提下，我們建立所有社區(qū)到最近派出所總距離最小的目標函數(shù)，即:5.2.5 確定目標

14、函數(shù)二的約束條件目標函數(shù)二只比目標函數(shù)一多了一個約束條件，為所建派出所的個數(shù)為3，即：5.2.4 綜上所述，目標函數(shù)二的模型為：5.2.5問題二的求解及結(jié)果分析我們通過lingo軟件編程，求得所建派出所個數(shù)為3，分別建在W,Q,K社區(qū)。所用程序見附錄。 5.3問題三：巡線問題5.3.1目標函數(shù)的建立根據(jù)題意，我們將巡視路線圖抽象為一個賦權(quán)無向連通圖G(V,E),先要分三組進行巡視，則需要將G(V,E)分成三個子圖，在每個子圖中尋找路程最小的回路（i=1，2，3），于是我們以各組的總路程和各組的行駛路程的均衡度為目標函數(shù)：5.3.2約束條件為：5.3.3結(jié)果分析其中方案一劃分的區(qū)域如下（顏色相同

15、的點在同一組）：用改良的Hamilton圈算法最終算出個小組的路徑和路線長度如下：小組名稱路線總路線長度 （百米）路線總長度（百米）第一小組W-X-A-X-B-I-P-I-G-W149351第二小組W-F-E-T-V-Q-R-S-D-C-W95第三小組W-F-U-J-N-M-K-H-Y-L-F-W107因為該組的均衡度為：36.2%所以該分法的均衡度比較差，不宜采用。方案二劃分的準則如下（顏色相同的點在同一組）小組名稱路線總路線長度（百米）路線總長度（百米）第一小組W-B-I-P-I-G-W113353第二小組W-C-T-V-Q-D-Q-R-S-A-X-W123第三小組W-F-E-U-J-L-

16、J-N-M-K-H-Y-F-W117因為該組的均衡度為8.13% <10%所以該分法的均衡度比較好符合題意，選擇此種方案。6模型的評價及其改進6.1優(yōu)點：（1）模型一和模型二的適用范圍廣，他們的模型適用于諸如醫(yī)院急救站，巡邏警點，消防站選點等類似公共設(shè)施的規(guī)劃建設(shè)，只需將參數(shù)和約束條件作相應(yīng)修改即可。（2） 該模型易于推廣普及，僅需要一副城市地圖和相應(yīng)的坐標信息，便可以解決中值選址問題。 （3）模型三解決的是旅行商問題具有普遍性。6.2缺點：（1） 模型三中的計算都只是近似計算，不能夠保證所求的解為最優(yōu)解。（2） 模型三缺乏嚴格的理論基礎(chǔ)和它的求解過程中存一個點經(jīng)過多次的情況過。（3） 模型三的分組隨機性比較大，存在不合理的情況。（4） 模型三和模型二的建立沒有考慮停留時間。（5） 模型一和模型二假設(shè)理想化，沒有考慮到諸多因素，實際問題可能更復(fù)雜6.3推廣：（1）可以結(jié)合計算機進行多次仿真模擬使結(jié)果更加準確。（6） 巡視的過程中要考慮在社區(qū)在社區(qū)的停留時間。（3）在劃分區(qū)域時可以增加方案，多種方案進行比較更加具有說服力。模型一和模型二可以用于，模型三建立的模