選址問題數(shù)學(xué)模型

《選址問題數(shù)學(xué)模型》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、選址問題數(shù)學(xué)模型摘要本題是用圖論與算法結(jié)合的數(shù)學(xué)模型，來解決居民各社區(qū)生活中存在三個(gè)的問題：合理的建立3個(gè)煤氣繳費(fèi)站的問題；如何建立合理的派出所；市領(lǐng)導(dǎo)人巡視路線最佳安排方案的問題。通過對原型進(jìn)行初步分析，分清各個(gè)要素及求解目標(biāo)，理出它們之間的聯(lián)系.在用圖論模型描述研究對象時(shí)，為了突出與求解目標(biāo)息息相關(guān)的要素，降低思考的復(fù)雜度。對客觀事物進(jìn)行抽象、化簡，并用圖來描述事物特征及內(nèi)在聯(lián)系的過程.建立圖論模型是為了簡化問題，突出要點(diǎn)，以便更深入地研究問題針對問題1：0-1規(guī)劃的窮舉法模型。該模型首先采用改善的Floyd-War

2、shall算法計(jì)算出城市間最短路徑矩陣見附錄表一；然后，用0-1規(guī)劃的窮舉法獲得模型目標(biāo)函數(shù)的最優(yōu)解，其煤氣繳費(fèi)站設(shè)置點(diǎn)分別在Q、W、M社區(qū)，各社區(qū)居民繳費(fèi)區(qū)域見表7-1，居民與最近的繳費(fèi)點(diǎn)之間平均距離的最小值11.7118百米。針對問題2：為避免資源的浪費(fèi)，且滿足條件，建立了以最少分組數(shù)為目標(biāo)函數(shù)的單目標(biāo)最優(yōu)化模型，用問題一中最短路徑的Floyd算法，運(yùn)用LINGO軟件編程計(jì)算,得到個(gè)社區(qū)之間的最短距離，再經(jīng)過計(jì)算可得到本問的派出所管轄范圍是2.5千米。最后采用就近歸組的搜索方法，逐步優(yōu)化，最終得到最少需要設(shè)置3個(gè)派出

3、所，其所在位置有三種方案，分別是：（1）K區(qū)，W區(qū)，D區(qū)；（2）K區(qū)，W區(qū)，R區(qū)；（3）K區(qū)，W區(qū)，Q區(qū)。最后根據(jù)效率和公平性和工作負(fù)荷考慮考慮，其第三種方案為最佳方案，故選擇K區(qū)，W區(qū)，Q區(qū)，其各自管轄區(qū)域路線圖如圖8-1。針對問題3：建立了雙目標(biāo)最優(yōu)化模型。首先將問題三轉(zhuǎn)化為三個(gè)售貨員的最佳旅行售貨員問題，得到以總路程最短和路程均衡度最小的目標(biāo)函數(shù)，采用最短路徑Floyd算法，并用MATLAB和LINGO軟件編程計(jì)算，得到最優(yōu)樹圖，然后按每塊近似有相等總路程的標(biāo)準(zhǔn)將最優(yōu)樹分成三塊，最后根據(jù)最小環(huán)路定理，得到三組巡視路

4、程分別為11.8、11和12.5，三組巡視的總路程達(dá)到35.3，路程均衡度為12%,具體巡視路線安排見表9-1和圖9.2。關(guān)鍵詞Floyd-Warshall算法窮舉法最小生成樹最短路徑1問題重述1.1問題背景這是一個(gè)最優(yōu)選址問題，是一種重要的長期決策，它的好壞直接影響到服務(wù)方法，服務(wù)質(zhì)量，服務(wù)效率，服務(wù)成本，所以選址問題的研究有著重大的經(jīng)濟(jì)社會(huì)和軍事意義。1.2問題的提出實(shí)際問題：某城市共有24個(gè)社區(qū)A，B，C、、、、、、Y，任何兩個(gè)社區(qū)之間都是相通的，只是有的社區(qū)是有道路直接相連，有的是通過其他社區(qū)聯(lián)系在一起，各個(gè)社區(qū)

5、對應(yīng)人口（單位：千人）如表1-1：表1-1編號(hào)ABCDEFGHIJKL人口10121861015487111311編號(hào)MNPQRSTUVWXY人口11892214871015281813各社區(qū)的的道路連接如圖1.1圖1.1（注：橫線上的數(shù)據(jù)表示相鄰社區(qū)之間的距離，單位：百米）1.3本文具體需要解決的問題(1)為了方便社區(qū)居民繳納煤氣費(fèi)，煤氣公司現(xiàn)擬建三個(gè)煤氣繳費(fèi)站，問煤氣繳費(fèi)站怎樣選址才能使得居民與最近煤氣站之間的平均距離最小。(2)市公安局?jǐn)M在該城區(qū)建立若干個(gè)派出所，請為派出所分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)

6、事件時(shí)，盡量能在3分鐘內(nèi)有警察（警車的時(shí)速為50km/h）到達(dá)事發(fā)地，問設(shè)置多少個(gè)派出所比較合理，位置選在哪？(3)社區(qū)W是市政府所在地，市領(lǐng)導(dǎo)從W出發(fā)巡視，分三組巡視所有社區(qū)，為了盡快完成巡視，合理的安排巡視路線2模型假設(shè)(1)不考慮各社區(qū)的實(shí)際尺度，簡化為點(diǎn)處理；(2)每個(gè)社區(qū)的居民都去繳費(fèi)站繳費(fèi)；(3)只在社區(qū)擬建三個(gè)煤氣繳費(fèi)站；(4)每個(gè)社區(qū)的居民只能到離該社區(qū)最近的煤氣繳費(fèi)站繳費(fèi)；(5)若與某些社區(qū)最近的繳費(fèi)站有若干個(gè)，即其可能與若干個(gè)繳費(fèi)點(diǎn)的距離相同且最鄰近，為保證各繳費(fèi)點(diǎn)工作負(fù)擔(dān)波動(dòng)不大，該社區(qū)的居民只能到

7、最鄰近的其中一個(gè)納稅點(diǎn)繳稅；(6)假設(shè)路況相同，警車到達(dá)個(gè)社區(qū)途中按照規(guī)定的速度勻速行使；3符號(hào)說明表3-1符號(hào)符號(hào)意義第個(gè)社區(qū)的居民人口數(shù)社區(qū)間可行的最短路徑長度社區(qū)是否到社區(qū)繳費(fèi)是否在社區(qū)設(shè)置繳費(fèi)站均衡度賦權(quán)連通圖子圖中的最佳回路邊的邊權(quán)點(diǎn)的點(diǎn)權(quán)的各邊權(quán)之和的各點(diǎn)權(quán)之和；；；4問題分析4.1問題1的分析此題主要考慮居民平均最短距離，解決的是多源選址問題，找到三個(gè)煤氣繳費(fèi)站最佳選址。當(dāng)考慮到社區(qū)人口數(shù)量和和各社區(qū)之間的距離時(shí)，人口量是影響平均最短距離的首要因素，盡可能把煤氣繳費(fèi)站建在人口密集的區(qū)域。本問題的目標(biāo)是從24

8、個(gè)社區(qū)組成區(qū)域內(nèi)中，選出一定3個(gè)社區(qū)設(shè)置煤氣繳費(fèi)站,建立繳費(fèi)點(diǎn)網(wǎng)絡(luò)，實(shí)現(xiàn)居民與最近的繳費(fèi)點(diǎn)之間平均距離最小。對于每個(gè)社區(qū)繳費(fèi)點(diǎn)的建立與否只有兩種可能，所以可以通過計(jì)算社區(qū)間的最短路徑，然后充分利用社區(qū)的居民以及道路信息，采用合適的方法搜索繳費(fèi)點(diǎn)；再確定各繳費(fèi)點(diǎn)管轄的區(qū)域，直到求得最優(yōu)解。本問題重點(diǎn)要解決如何選擇繳費(fèi)點(diǎn)