數學建模選址問題完整參考模板

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

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

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

4、的距離，單位：百米）本題要解決的問題如下：（1） 方便社區(qū)居民繳納煤氣費，煤氣公司現擬建三個煤氣繳費站，問煤氣繳費站為了怎樣選址才能使得居民與最近煤氣站之間的平均距離最小。 (2) 市公安局擬在該城區(qū)建立若干個派出所，請為派出所分配管轄范圍，使其在所管轄的范圍內出現突發(fā)事件時，盡量能在3分鐘內有警察（警車的時速為 50km/h）到達事發(fā)地，問設置多少個派出所比較合理，位置選在哪？(3) 社區(qū)W是市政府所在地，市領導從W出發(fā)巡視，分三組巡視所有社區(qū)，為了盡快完成巡視，請問如何安排巡視路線。2 模型假設與符號說明2.1模型假設：假設1：相鄰兩個社區(qū)之間的道路近似認為是直線，把城市地圖抽象成由點和線

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

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

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

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

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

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

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

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

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

14、函數二的約束條件目標函數二只比目標函數一多了一個約束條件，為所建派出所的個數為3，即：5.2.4 綜上所述，目標函數二的模型為：5.2.5問題二的求解及結果分析我們通過lingo軟件編程，求得所建派出所個數為3，分別建在W,Q,K社區(qū)。所用程序見附錄。 5.3問題三：巡線問題5.3.1目標函數的建立根據題意，我們將巡視路線圖抽象為一個賦權無向連通圖G(V,E),先要分三組進行巡視，則需要將G(V,E)分成三個子圖，在每個子圖中尋找路程最小的回路（i=1，2，3），于是我們以各組的總路程和各組的行駛路程的均衡度為目標函數：5.3.2約束條件為：5.3.3結果分析其中方案一劃分的區(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ī)院急救站，巡邏警點，消防站選點等類似公共設施的規(guī)劃建設，只需將參數和約束條件作相應修改即可。（2） 該模型易于推廣普及，僅需要一副城市地圖和相應的坐標信息，便可以解決中值選址問題。 （3）模型三解決的是旅行商問題具有普遍性。6.2缺點：（1） 模型三中的計算都只是近似計算，不能夠保證所求的解為最優(yōu)解。（2） 模型三缺乏嚴格的理論基礎和它的求解過程中存一個點經過多次的情況過。（3） 模型三的分組隨機性比較大，存在不合理的情況。（4） 模型三和模型二的建立沒有考慮停留時間。（5） 模型一和模型二假設理想化，沒有考慮到諸多因素，實際問題可能更復雜6.3推廣：（1）可以結合計算機進行多次仿真模擬使結果更加準確。（6） 巡視的過程中要考慮在社區(qū)在社區(qū)的停留時間。（3）在劃分區(qū)域時可以增加方案，多種方案進行比較更加具有說服力。模型一和模型二可以用于，模型三建立的模