數(shù)學(xué)建模論文——城市小區(qū)便民服務(wù)點(diǎn)的設(shè)置與調(diào)度優(yōu)化模型

1、賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)填寫）：2015高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承 諾 書我們仔細(xì)閱讀了全國大學(xué)生數(shù)學(xué)建模競賽章程和全國大學(xué)生數(shù)學(xué)建模競賽參賽規(guī)則（以下簡稱為“競賽章程和參賽規(guī)則”，可從全國大學(xué)生數(shù)學(xué)建模競賽網(wǎng)站下載）。我們完全明白，在競賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽章程和參賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽章程和參賽規(guī)則，以保證競賽的公

2、正、公平性。如有違反競賽章程和參賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們授權(quán)全國大學(xué)生數(shù)學(xué)建模競賽組委會(huì)，可將我們的論文以任何形式進(jìn)行公開展示（包括進(jìn)行網(wǎng)上公示，在書籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等）。我們參賽選擇的題號(hào)（從A/B/C/D中選擇一項(xiàng)填寫）： 我們的報(bào)名參賽隊(duì)號(hào)（12位數(shù)字全國統(tǒng)一編號(hào)）： 參賽學(xué)校（完整的學(xué)校全稱，不含院系名）： 參賽隊(duì)員 (打印并簽名) ：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期： 年 月 日 （此承諾書打印簽名后作為紙質(zhì)論文的封面，注意電子版論文中不得出現(xiàn)此頁。以上內(nèi)容請(qǐng)仔細(xì)核對(duì)，如填寫錯(cuò)誤，論文可能被取消評(píng)獎(jiǎng)資格。）賽區(qū)評(píng)

3、閱編號(hào)（由賽區(qū)組委會(huì)填寫）：2015高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號(hào) 專 用 頁賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人備注送全國評(píng)閱統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)填寫）：全國評(píng)閱隨機(jī)編號(hào)（由全國組委會(huì)填寫）：（此編號(hào)專用頁僅供賽區(qū)和全國評(píng)閱使用，參賽隊(duì)打印后裝訂到紙質(zhì)論文的第二頁上。注意電子版論文中不得出現(xiàn)此頁，即電子版論文的第一頁為標(biāo)題、摘要和關(guān)鍵詞頁。）城市小區(qū)便民服務(wù)點(diǎn)的設(shè)置與調(diào)度優(yōu)化模型摘要隨著經(jīng)濟(jì)不斷增長，基礎(chǔ)設(shè)施的需求不斷增加，便民服務(wù)點(diǎn)作為城市基礎(chǔ)化建設(shè)的重要組成部分仍需不斷完善。由于人力、物力和資金等資源是有限的，如何根據(jù)城市的小區(qū)實(shí)際分布情況與需求合理地設(shè)置小區(qū)便民服務(wù)點(diǎn)，分

4、配各服務(wù)點(diǎn)的服務(wù)范圍，充分利用有限資源為全市市民提供一個(gè)生活方便、優(yōu)質(zhì)的服務(wù)，是有關(guān)部門面臨的一個(gè)實(shí)際問題。問題一：分配各便民服務(wù)點(diǎn)的服務(wù)范圍（1）題目要求在全市12個(gè)便民服務(wù)點(diǎn)位置確定的情況下，按照盡量短時(shí)間內(nèi)到達(dá)服務(wù)點(diǎn)和工作量均衡的原則為各便民服務(wù)點(diǎn)分配服務(wù)范圍。對(duì)此問題本文用Floyd算法建立最短路徑模型，利用MATLAB進(jìn)行求解，得到每個(gè)服務(wù)點(diǎn)到居民點(diǎn)的最短路徑。（2）我們對(duì)于120個(gè)居民點(diǎn)在最短時(shí)間到達(dá)服務(wù)點(diǎn)的問題，以所用時(shí)間最小為目標(biāo)，建立0-1整型規(guī)劃模型，借助LINGO進(jìn)行求解，得出各條路徑所需最短時(shí)間，結(jié)合（1）最后得到全市現(xiàn)有每個(gè)便民服務(wù)點(diǎn)的服務(wù)范圍如表1。問題二：對(duì)于確定

5、需要增加服務(wù)點(diǎn)的具體個(gè)數(shù)和位置的問題由問題一的分配結(jié)果可知，在現(xiàn)有便民服務(wù)點(diǎn)的設(shè)置下：還有幾個(gè)居民點(diǎn)不能在平均時(shí)間內(nèi)到達(dá)服務(wù)點(diǎn)，即到達(dá)服務(wù)點(diǎn)時(shí)間過長我們根據(jù)便民服務(wù)點(diǎn)工作量的方差定義工作量不均衡度，結(jié)果顯示：此時(shí)服務(wù)點(diǎn)的工作量不均衡度為6.5。為解決到達(dá)服務(wù)點(diǎn)時(shí)間過長和便民服務(wù)點(diǎn)工作量不均衡的問題。我們建立最優(yōu)化模型，求解結(jié)果表明：在增加三個(gè)服務(wù)點(diǎn)的情況下，可以解決居民點(diǎn)到服務(wù)點(diǎn)時(shí)間過長的問題。在此基礎(chǔ)上我們優(yōu)化分配方案：在增加幾個(gè)便民服務(wù)點(diǎn)的情況下，使服務(wù)點(diǎn)的工作量不均衡度降為多少。增加的三個(gè)服務(wù)點(diǎn)路口標(biāo)號(hào)見表2。關(guān)鍵詞：Floyd最短路徑算法 0-1整型規(guī)劃模型 最優(yōu)化模型 MATLAB

6、LINGO一、 問題重述某市為了方便市民生活，打算在市內(nèi)小區(qū)設(shè)置便民服務(wù)點(diǎn)，為市民就近提供醫(yī)療衛(wèi)生、繳費(fèi)等公共服務(wù)，但由于人力、物力和資金等資源是有限的，如何根據(jù)城市的小區(qū)實(shí)際分布情況與需求合理地設(shè)置小區(qū)便民服務(wù)點(diǎn)，分配各服務(wù)點(diǎn)的服務(wù)范圍，充分利用有限資源為全市市民提供一個(gè)生活方便、優(yōu)質(zhì)的服務(wù)，是有關(guān)部門面臨的一個(gè)實(shí)際問題。問題一：為了提高便民服務(wù)點(diǎn)的服務(wù)效率，同時(shí)考慮每個(gè)服務(wù)點(diǎn)工作量的均衡性，該市打算將居民點(diǎn)劃片服務(wù)，每個(gè)服務(wù)點(diǎn)面向一些居民點(diǎn)服務(wù)；建立數(shù)學(xué)模型，為各便民服務(wù)點(diǎn)分配服務(wù)居民點(diǎn)的范圍，使其在所服務(wù)居民點(diǎn)范圍內(nèi)的居民盡量在最短時(shí)間內(nèi)到達(dá)服務(wù)點(diǎn)，同時(shí)又要使每個(gè)服務(wù)點(diǎn)的工作量盡可能的均

7、衡。問題二：根據(jù)現(xiàn)有便民服務(wù)點(diǎn)的工作量不均衡和有些居民點(diǎn)到達(dá)服務(wù)點(diǎn)時(shí)間過長的實(shí)際情況，擬在該市內(nèi)再增加1至3個(gè)服務(wù)點(diǎn)，請(qǐng)確定需要增加服務(wù)點(diǎn)的具體個(gè)數(shù)和位置。該市目前有120個(gè)居民點(diǎn)和12個(gè)便民服務(wù)點(diǎn)，居民點(diǎn)和便民服務(wù)點(diǎn)的網(wǎng)絡(luò)分布情況見支持資料1，每個(gè)居民點(diǎn)位置、居民人口數(shù)和道路連接的數(shù)據(jù)信息見支持資料2；支持資料1：該市居民點(diǎn)和便民服務(wù)點(diǎn)的網(wǎng)絡(luò)分布示意圖。支持資料2：該市居民點(diǎn)位置、居民人口數(shù)和道路連接的相關(guān)數(shù)據(jù)表。二、問題的分析問題一：問題要求在市內(nèi)的12個(gè)便民服務(wù)點(diǎn)位置確定的情況下，按照盡量短時(shí)間內(nèi)到達(dá)服務(wù)點(diǎn)和工作量均衡的原則為各便民服務(wù)點(diǎn)分配服務(wù)范圍。本文引入賦權(quán)圖中任意兩頂點(diǎn)間的最短路

8、理論中的Floyd算法和0-1整型規(guī)劃模型進(jìn)行求解。記為市內(nèi)所有居民點(diǎn)的節(jié)點(diǎn)集合，為全市便民服務(wù)點(diǎn)的節(jié)點(diǎn)集合，為便民服務(wù)點(diǎn)到達(dá)居民點(diǎn)的最短距離。引入0-1變量,當(dāng)居民點(diǎn)分配給便民服務(wù)點(diǎn)管轄是為1，當(dāng)居民點(diǎn)不分配給便民服務(wù)點(diǎn)管轄是為0。即：由題目可知當(dāng)相對(duì)較小時(shí)，居民點(diǎn)可能分配給便民服務(wù)點(diǎn)，也可能分配給其他可在較短時(shí)間內(nèi)到達(dá)居民點(diǎn)的便民服務(wù)臺(tái)，而不分配給，故有;當(dāng)相對(duì)較大時(shí)，居民點(diǎn)不能在較短時(shí)間內(nèi)到達(dá)服務(wù)點(diǎn)，故此時(shí)路口不能分配給便民服務(wù)點(diǎn)管轄，故此時(shí)。根據(jù)上述的分配原則及每個(gè)路口只由一個(gè)便民服務(wù)點(diǎn)進(jìn)行管轄、每個(gè)便民服務(wù)點(diǎn)至少要管轄一個(gè)路口，可首先利用Floyd算法計(jì)算出12個(gè)服務(wù)點(diǎn)到120個(gè)居民

9、點(diǎn)的最短路徑，然后建立0-1規(guī)劃模型，并借助lingo進(jìn)行區(qū)域劃分。問題二：根據(jù)問題一（1）的分配方案可知此時(shí)每個(gè)便民服務(wù)點(diǎn)的工作量分別為：表1 按問題一的分配方案12個(gè)便民服務(wù)點(diǎn)的工作量編號(hào)123456工作量21946916編號(hào)789101112工作量412912612此時(shí)便民服務(wù)點(diǎn)的工作量不均衡度為6.3圖1 居民點(diǎn)和便民服務(wù)點(diǎn)的網(wǎng)絡(luò)布情況注：圖中圓圈“* ”表示設(shè)置了服務(wù)點(diǎn)；距離單位：公里由問題一可知現(xiàn)有便民服務(wù)點(diǎn)的工作量極其不均衡且有些地方路徑過長。針上述問題，題目要求再增加13個(gè)便民服務(wù)點(diǎn)來解決上述問題。本文建立優(yōu)化模型，然后利用lingo對(duì)模型進(jìn)行增加的平臺(tái)個(gè)數(shù)，可得到初步的分配方

10、案，最后再引入工作量不均衡度，通過計(jì)算求解可確定增加便民服務(wù)點(diǎn)的數(shù)目與位置。三、模型的假設(shè) 假設(shè)每個(gè)便民服務(wù)點(diǎn)的職能和人力配備基本相同； 假設(shè)每個(gè)路口只由一個(gè)便民服務(wù)點(diǎn)進(jìn)行管轄； 假設(shè)每個(gè)便民服務(wù)點(diǎn)至少管轄一個(gè)路口； 假設(shè)居民都按最短路徑到達(dá)各服務(wù)點(diǎn)； 工作量：每個(gè)便民服務(wù)點(diǎn)所管轄范圍內(nèi)的所有居民點(diǎn)人數(shù)之和； 時(shí)間：居民到達(dá)服務(wù)點(diǎn)所需時(shí)間；四、符號(hào)說明第個(gè)居民點(diǎn)到第個(gè)便民服務(wù)點(diǎn)的最短距離第個(gè)居民點(diǎn)人數(shù)第個(gè)便民服務(wù)點(diǎn)第個(gè)居民點(diǎn)總?cè)藬?shù)新增點(diǎn)候選集居民點(diǎn)是否分配給便民點(diǎn)工作量距離目標(biāo)值均方差五、模型的建立與求解5.1問題一（1）：服務(wù)范圍的確定Floyd算法最短路徑模型模型建立：Floyd算法：根據(jù)

11、問題一（1）的分析確定函數(shù)為目標(biāo)函數(shù)： 約束條件： 模型求解1.最短路徑矩陣A的建立本文選用Floyd算法確定市內(nèi)任意兩個(gè)路口之間的最短路徑矩陣。Floyd算法為：從任意節(jié)點(diǎn)到任意節(jié)點(diǎn)的最短路徑不外乎2種可能，1是直接從到，2是從經(jīng)過若干個(gè)節(jié)點(diǎn)到。所以，我們假設(shè)為節(jié)點(diǎn)到節(jié)點(diǎn)的最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)，我們檢查是否成立，如果成立，證明從到再到的路徑比直接到的路徑短，我們便設(shè)置，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn)，中記錄的便是到的最短路徑的距離。通過上述算法，利用數(shù)學(xué)軟件MATLAB計(jì)算出各節(jié)點(diǎn)的最短路徑，組成一個(gè)最短路徑矩陣。圖2 偏差值與目標(biāo)最優(yōu)解的坐標(biāo)圖由圖可看出在1500附近，目標(biāo)函數(shù)值

12、變動(dòng)最小，為此我們選擇1500為偏差限目標(biāo)值：3518.575.1.3最終分配方案的確定從最短路徑矩陣中，我們可以清楚看到如下問題：（1） 在僅滿足分配標(biāo)準(zhǔn)時(shí)有些路口可以被多個(gè)路口管轄；（2）在僅滿足分配標(biāo)準(zhǔn)時(shí)個(gè)別居民點(diǎn)離服務(wù)點(diǎn)距離過大；那么此時(shí)并不滿足模型的要求必須對(duì)進(jìn)行處理，以得到滿足要求的最終分配方案。首先解決（1）中出現(xiàn)的問題，此過程我們利用數(shù)學(xué)軟件MATLAB進(jìn)行處理，相應(yīng)的程序見附錄。步驟一：由集合覆蓋矩陣將120個(gè)居民點(diǎn)分為A、B、C三類：A類：已只由一個(gè)巡警服務(wù)臺(tái)進(jìn)行管轄；B類：可被多個(gè)巡警服務(wù)臺(tái)進(jìn)行管轄；C類；還不能被任何巡警服務(wù)臺(tái)進(jìn)行管轄；步驟二：將A類中的路口直接分配給對(duì)

13、其進(jìn)行管轄的唯一的巡警服務(wù)臺(tái)。步驟三：將B類中的路口按最近原則分配給距離它最近的巡警服務(wù)臺(tái)。然后解決（2）中的問題。將任何服務(wù)點(diǎn)都不能在規(guī)定時(shí)間內(nèi)到達(dá)的居民點(diǎn)按就近原則進(jìn)行分配。表2最后得到最終的分配方案如下：服務(wù)平臺(tái)管轄范圍服務(wù)人數(shù)（人）最長距離A11,19,64,65,70,71,72,73,74,7,76,77,80,811610056.54864A22,42,43,66,67,68,69,78,791480068.19103A33,18,20,40,44,53,54,6313300115.0042A44,49,52,56,57,58,59,60,61,62,991560052.1055

14、5A55,22,30,47,48,50,51,55,1340052.50731A66,32,33,34,35,36,37,45,46,891630040.04293A77,15,28,29,31,106,1091440098.17466A88,13,21,23,24,25,26,27,82,1460050.93686A99,14,83,84,85,86,87,88,90,921540055.85048A1010,16,38,39,91,93,94,95,98,100,103,1470047.01612A1111,96,97,101,102,104,108,113,115,117,1201330

15、072.03523A1212,17,41,105,107,110,111,112,114,116,118,1191560074.34954EMBED Equation.DSMT4 圖3 居民點(diǎn)和便民服務(wù)點(diǎn)的最短路徑網(wǎng)絡(luò)5.2問題二：確定增加平臺(tái)的個(gè)數(shù)與位置用lingo設(shè)計(jì)增加的平臺(tái)個(gè)數(shù)模型的建立與求解優(yōu)化模型建立：根據(jù)問題一確定函數(shù)為：約束條件： 當(dāng) 時(shí)，否則為 得到的最優(yōu)目標(biāo)函數(shù)值要小于13533 (j=1,2,12)根據(jù)平局工作量公式與工作量不均衡度公式，利用lingo分別對(duì)分配方案中巡警服務(wù)臺(tái)的工作量不均衡度進(jìn)行計(jì)算。從49至64范圍內(nèi)取出若干個(gè)偏差限與所對(duì)應(yīng)的目標(biāo)函數(shù)值，得坐標(biāo)圖如下：

16、圖4偏差值與目標(biāo)最優(yōu)解的坐標(biāo)圖由圖可看出在1500附近，目標(biāo)函數(shù)值變動(dòng)最小，為此我們選擇1500為偏差限最優(yōu)目標(biāo)函數(shù)值2618.287增加3個(gè)服務(wù)點(diǎn)，標(biāo)號(hào)與坐標(biāo)分別為：20 （244,134）109 （19,56）116 （248,76）最后，利用lingo運(yùn)用搜索法得到：至少從候選集Q中選出3個(gè)路口來設(shè)置便民服務(wù)點(diǎn)，才能解決到服務(wù)點(diǎn)時(shí)間過長的問題。此時(shí)共有1938種可能的分配方案。表2滿足題目二要求的3個(gè)便民服務(wù)點(diǎn)的路口標(biāo)號(hào)X( 18, 20) 1.000000 X( 20, 20) 1.000000 X( 22, 99) 1.000000 X( 25, 106) 1.000000 X( 2

17、6, 106) 1.000000 X( 27, 106) 1.000000 X( 28, 106)1.000000 X( 48, 99) 1.000000 X( 75, 20) 1.000000 X( 76, 20)1.000000 X( 77, 20) 1.000000 X( 78, 20)1.000000 X( 79, 20)1.000000 X( 80, 20)1.000000 X( 81, 20)1.000000 X( 82, 106)1.000000 X( 99, 99) 1.000000 X( 106, 106)1.000000 X( 109, 106)1.000000 表3 方案

18、一中15個(gè)服務(wù)點(diǎn)的管轄范圍服務(wù)平臺(tái)管轄范圍服務(wù)人數(shù)（人）最長距離A11,19,64,65,70,71,72,73,74,76,77,80,811310056.54864A22,42,43,66,67,68,69,751330060.79228A33,18,40,44,53,54,631310069.64803A44,49,52,56,57,58,59,60,61,62,99980052.10554A55,22,30,47,48,50,511350052.50731A66,32,33,34,35,36,37,45,461330040.04293A77,15,28,29,31,106,109104

19、0084.98434A88,13,21,23,24,25,26,27,821160050.93683A99,14,85,86,87,88,90,921070034.13871A1010,16,38,39,94,93,91,95,98,100,1031310046.08345A1111,96,97,101,102,104,108,113,115,117,1201040072.03523A1212,41,105,107,110,111,1121310032.949472018,20,75,76,77,78,79,80,81,1320036.779439922,48,99690052.8131610

20、625,26,27,28,82,1061200027.26469五、模型的評(píng)價(jià)與推廣1.優(yōu)點(diǎn)：采用離散定位模型作為城區(qū)巡警服務(wù)臺(tái)優(yōu)化布局方法的應(yīng)基礎(chǔ),結(jié)合相關(guān)的影響因素，能很好地解決實(shí)際問題。本文把實(shí)際問題抽象成集合模型、規(guī)劃和圖論，完整準(zhǔn)確的描述了實(shí)際問題。本文所用算法，效率好精度高解決實(shí)際問題方便快捷。2.缺點(diǎn)：本文對(duì)工作量的定義只考慮路口發(fā)案率，沒有不同區(qū)人密度對(duì)便民服務(wù)點(diǎn)工作量的影響。本文較少考慮不同區(qū)的路口發(fā)案率相差加大，導(dǎo)致服務(wù)點(diǎn)工作量難以均衡。3.模型推廣：本模型不僅對(duì)便民服務(wù)點(diǎn)適用，而且可以廣泛運(yùn)于消防站、醫(yī)院等應(yīng)急服務(wù)設(shè)施的布局。六、參考文獻(xiàn)1 謝金星，優(yōu)化模型與LINDO/

21、LINGO軟件，北京：清華大學(xué)出版社，2006年。2 王沫然，MATLAB與科學(xué)，北京：電子工業(yè)出版社，2008年。3 方世昌，離散數(shù)學(xué)，西安：西安電子科技大學(xué)出版社，2009年4 吳美文，基于離散定位模型的城市消防站優(yōu)化布局方法*，系統(tǒng)仿真技術(shù)，2006年1月第2卷第一期：58-62頁。5陳馳任愛珠，消防站布局優(yōu)化的計(jì)算機(jī)方法J，清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2003,43（10）：13901393。6陳艷艷郭國旗，城市消防站的優(yōu)化布局J.消防科技，1999，（1）：26287吳軍，消防站優(yōu)化布局方法與技術(shù)研究，消防科學(xué)與技術(shù)2006年1月第25卷第1 期七、附錄附錄1(floyd算法求最短路徑

22、及距離)建立帶權(quán)鄰接矩陣A：p=xlsread('C:UsersadminDesktopbook1.xls');x=p(:,1);y=p(:,2);i=p(:,3);j=p(:,4);A=zeros(120,120);for k=1:120 a=i(k); b=j(k); A(a,b)=1; A(b,a)=1;endfor m=1:120 for n=1:120 if(A(m,n)=1) A(m,n)=sqrt(x(m)-x(n)2+(y(m)-y(n)2); else A(m,n)=50000; end endendfor m=1:120 for n=1:120 if(m=n

23、) A(m,n)=0; end endend xlswrite('C:UsersadminDesktopÁÚ½Ó¾ØÕó.xls', A);>> D,path=floyd(A);>> xlswrite('C:UsersadminDesktop×î¶Ì·¾ØÕó.xls', D);>> T=D(1:120,1:12);>> xlswrit

24、e('C:UsersadminDesktop·þÎñµãµÄ¾àÀë.xls', T);附錄2（用lingo劃分區(qū)域）：model:sets:department/1.120/;type/1.12/;a/1.120/:c;benefit(department,type):d,x;endsetsmin=sum(benefit(i,j):d(i,j)*x(i,j);for(benefit:bin(x);for(department(i): sum(type(j):x(i,j)=1);for(type(i):x(i,i)=1);for(type(j):(14800-sum(a(i):x(i,j)*c(i)<1450);for(type(j):(14800-sum(a(i):x(i,j)*c(i)>-1450);for(type(j):sum(a(i):x(i,j)*c(i)=q(j);for(type(j):max(department(i):x(i,j)*