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

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

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

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

4、的距離，單位：百米）本題要解決的問題如下：（1） 方便社區(qū)居民繳納煤氣費(fèi)，煤氣公司現(xiàn)擬建三個(gè)煤氣繳費(fèi)站，問煤氣繳費(fèi)站為了怎樣選址才能使得居民與最近煤氣站之間的平均距離最小。 (2) 市公安局?jǐn)M在該城區(qū)建立若干個(gè)派出所，請(qǐng)為派出所分配管轄范圍，使其在所管轄的范圍內(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ū)，為了盡快完成巡視，請(qǐng)問如何安排巡視路線。2 模型假設(shè)與符號(hào)說明2.1模型假設(shè)：假設(shè)1：相鄰兩個(gè)社區(qū)之間的道路近似認(rèn)為是直線，把城市地圖抽象成由點(diǎn)和線

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

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

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

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

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

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

11、最短距離。則畫出以w為根的樹如下：5模型的建立與求解首先，我們用floyd算法求出任意兩個(gè)社區(qū)之間的最短距離，以便問題一，問題二，問題三的求解。5.1問題一：煤氣站的選址問題5.1.1 確定目標(biāo)函數(shù)由問題一的題目要求，要求煤氣站的選址能夠使居民到最近煤氣站的平均距離最小，此問題等價(jià)于求煤氣站的選址使24個(gè)社區(qū)的所有居民到最近煤氣站的總距離最小。因此，我們把目標(biāo)函數(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綜上所述，得到問題一的單目標(biāo)最優(yōu)化模型5.1.4 模型一的求解及結(jié)果分析我們通過lingo軟件編程,得到三個(gè)煤氣站應(yīng)分別建在W,Q,M社區(qū)，居民與最近煤氣站的平均距離為11.7118百米。首先這三個(gè)社區(qū)分別分布于整個(gè)區(qū)域的西北部，東部，和南部，可以為各個(gè)社區(qū)的居民服務(wù)，從而又使平均距離達(dá)到最小，滿足了題目要求。5.2問題二：派處所的選址問題 5.2.1確定目標(biāo)函數(shù)一在已知警車運(yùn)行速度的前提下，我們將時(shí)間約束轉(zhuǎn)換成最遠(yuǎn)距離約束，即最遠(yuǎn)

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

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

15、的點(diǎn)在同一組）：用改良的Hamilton圈算法最終算出個(gè)小組的路徑和路線長度如下：小組名稱路線總路線長度 （百米）路線總長度（百米）第一小組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因?yàn)樵摻M的均衡度為：36.2%所以該分法的均衡度比較差，不宜采用。方案二劃分的準(zhǔn)則如下（顏色相同的點(diǎn)在同一組）小組名稱路線總路線長度（百米）路線總長度（百米）第一小組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因?yàn)樵摻M的均衡度為8.13% <10%所以該分法的均衡度比較好符合題意，選擇此種方案。6模型的評(píng)價(jià)及其改進(jìn)6.1優(yōu)點(diǎn)：（1）模型一和模型二的適用范圍廣，他們的模型適用于諸如醫(yī)院急救站，巡邏警點(diǎn)，消防站選點(diǎn)等類似公共設(shè)施的規(guī)劃建設(shè)，只需將參數(shù)和約束條件作相應(yīng)修改即可。（2） 該模型易于推廣普及，僅需要一副城市地圖和相應(yīng)的坐標(biāo)信息，便可以解決中值選址問題。 （3）模型三解決的是旅行商問題具有普遍性。6.2缺點(diǎn)：（1） 模型三中的計(jì)算都只是近似計(jì)算，不能夠保證所求的解為最優(yōu)解。（2） 模型三缺乏嚴(yán)格的理論基礎(chǔ)和它的求解過程中存一個(gè)點(diǎn)經(jīng)過多次的情況過。（3） 模型三的分組隨機(jī)性比較大，存在不合理的情況。（4） 模型三和模型二的建立沒有考慮停留時(shí)間。（5） 模型一和模型二假設(shè)理想化，沒有考慮到諸多因素，實(shí)際問題可能更復(fù)雜6.3推廣：（1）可以結(jié)合計(jì)算機(jī)進(jìn)行多次仿真模擬使結(jié)果更加準(zhǔn)確。（6） 巡視的過程中要考慮在社區(qū)在社區(qū)的停留時(shí)間。（3）在劃分區(qū)域時(shí)可以增加方案，多種方案進(jìn)行比較更加具有說服力。模型一和模型二可以用于，模型三建立的模