消防知識(shí)_城鎮(zhèn)消防站布局問題的探討

城鎮(zhèn)消防站布局問題的探討 楊賢濤（中國(guó)人民武裝警察部隊(duì)學(xué)院研究生一隊(duì) 河北廊坊 065000）摘要：消防站布局問題在城市規(guī)劃中具有重要作用，在考慮消防站覆蓋范圍和經(jīng)濟(jì)條件的情況下，將整個(gè)地區(qū)的消防站抽象為0-1整數(shù)線性規(guī)劃模型，利用隱枚舉法解決消防站的布局問題。具有科學(xué)性和合理性，避免了依靠經(jīng)驗(yàn)選址的弊端。關(guān)鍵字：消防站布局 整數(shù)線性規(guī)劃 隱枚舉法Abstract: The fire station location play an important role in urban planning. Considering this fire station jurisdiction and the citys economy, this paper abstracts the 0-1 integer linear programming mode from the whole areas fire station, then uses implicit enumeration to solve the problem of fire station location. This method is scientific and rational. It avoids the drawbacks of relying on experience in site selection. Keywords: fire station location, integer linear programming, implicit enumeration1引言城市消防規(guī)劃在城市建設(shè)和發(fā)展中具有重要意義,其中,消防站布局規(guī)劃尤為重要,其內(nèi)容包括消防站的選址和消防站責(zé)任區(qū)的劃分。由于中國(guó)早期的城市建設(shè)大多對(duì)消防規(guī)劃關(guān)注不夠, 消防站選址大多僅依據(jù)經(jīng)驗(yàn)進(jìn)行, 再加上地方政策等諸多原因, 因此,目前中國(guó)的部分城市中，存在著不同程度的消防站布局不合理、站址選擇較隨意的問題。某些地區(qū)消防延時(shí)相當(dāng)突出，而其他地區(qū)消防站卻設(shè)置過多，增加城市財(cái)政負(fù)擔(dān)。本文打算運(yùn)用整數(shù)線性規(guī)劃的方法，對(duì)城市消防站進(jìn)行最優(yōu)化布局，實(shí)例證明該方法是可行的。2整數(shù)線性規(guī)劃理論線性規(guī)劃（Linear Programming）是運(yùn)籌學(xué)的重要分支之一。自1947年美國(guó)數(shù)學(xué)家丹捷格（G.B.Dantzig）提出了求解線性規(guī)劃問題的方法單純形法之后，線性規(guī)劃在理論上趨于成熟，在實(shí)際中的應(yīng)用日益廣泛與深入。從解決技術(shù)問題中的最優(yōu)化設(shè)計(jì)到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、軍事、經(jīng)濟(jì)計(jì)劃與管理、決策等各個(gè)領(lǐng)域均可發(fā)揮作用。它具有適應(yīng)性強(qiáng)、應(yīng)用廣泛、計(jì)算技術(shù)比較簡(jiǎn)單的特點(diǎn)，是現(xiàn)代管理科學(xué)的重要基礎(chǔ)和手段之一。1 線性規(guī)劃的數(shù)學(xué)模型由：決策變量（Decision variables）、目標(biāo)函數(shù)（Objective function）及約束條件（Constraints）構(gòu)成，稱為三個(gè)要素。0-1整數(shù)線性規(guī)劃是一種特殊形式的整數(shù)規(guī)劃。0-1規(guī)劃在工廠選址問題、運(yùn)輸問題、投資問題、加工問題、開發(fā)新產(chǎn)品問題等方面有著廣泛的應(yīng)用,0-1規(guī)劃方法為管理人員作決策時(shí)提供了科學(xué)的依據(jù),是實(shí)現(xiàn)管理現(xiàn)代化的有力工具. 本文利用隱枚舉法對(duì)0-1線性規(guī)劃模型求解。30-1線性規(guī)劃的基本模型在實(shí)際管理中,很多問題無法歸結(jié)為線性規(guī)劃的數(shù)學(xué)模型,但卻可以通過設(shè)置邏輯變量建立起整數(shù)規(guī)劃的數(shù)學(xué)模型. 例如消防站選址決策問題:隨著經(jīng)濟(jì)的發(fā)展,城鎮(zhèn)規(guī)模擴(kuò)大，消防設(shè)施日益完善。某縣計(jì)劃新建幾個(gè)消防站，以滿足當(dāng)?shù)氐南佬枨?。而此縣有n個(gè)地點(diǎn)滿足條件。必須在其中選取合適的地點(diǎn)建設(shè)消防站。在進(jìn)行消防站布局時(shí)，必須要考慮到消防站必須能夠覆蓋整個(gè)縣，而且，一旦發(fā)生火災(zāi)，最近的消防站能夠在15分鐘內(nèi)抵達(dá)。同時(shí)，還要考慮到，當(dāng)?shù)氐慕?jīng)濟(jì)能力有限，而建設(shè)和運(yùn)行一個(gè)消防站需要大量資金支持。所以，消防站的數(shù)量不能太多。因此，管理層認(rèn)為應(yīng)該在財(cái)務(wù)分析的基礎(chǔ)上做出決策。對(duì)于這樣的問題，可以利用0-1整數(shù)線性規(guī)劃來解決，確立目標(biāo)函數(shù)，建立數(shù)學(xué)模型。0-1線性規(guī)劃模型的基本形式是：求解0-1型整數(shù)規(guī)劃最樸素的原理和方法便是窮舉法，即檢查變量取值為0或1的各種組合，注意比較相應(yīng)的目標(biāo)值以求得問題的最優(yōu)解，但這就需要比較2n個(gè)結(jié)果，當(dāng)n的數(shù)值很大時(shí)，這幾乎是不可能的。因此有必要設(shè)計(jì)一些方法，只檢查變量取值組合的一小部分，便能夠求得問題的最優(yōu)解，這樣的方法稱為隱枚舉法。2隱枚舉法不需要列出所有組合，只需關(guān)心目標(biāo)函數(shù)值的最優(yōu)可行組合，按目標(biāo)值從優(yōu)到劣依次列出組合，逐個(gè)檢驗(yàn)其可行性；最先滿足所有s.t的組合為最優(yōu)解，劣于最優(yōu)解的組合即使可行，也不列出檢驗(yàn)而隱去。4.實(shí)例分析說明某縣有六個(gè)重要鄉(xiāng)鎮(zhèn)，該縣政府計(jì)劃興建消防站，因此希望決定建立最少的消防站數(shù)以確保每個(gè)鄉(xiāng)鎮(zhèn)至少有一個(gè)消防隊(duì)伍能在15分鐘的車程內(nèi)到達(dá)。各鄉(xiāng)鎮(zhèn)間與其他鄉(xiāng)鎮(zhèn)的車程時(shí)間以下表1所示，試建立最優(yōu)化模型使得消防站數(shù)為最小。車程時(shí)間終點(diǎn)鄉(xiāng)鎮(zhèn)1鄉(xiāng)鎮(zhèn)2鄉(xiāng)鎮(zhèn)3鄉(xiāng)鎮(zhèn)4鄉(xiāng)鎮(zhèn)5鄉(xiāng)鎮(zhèn)6起始點(diǎn)鄉(xiāng)鎮(zhèn)101020303020鄉(xiāng)鎮(zhèn)210025352010鄉(xiāng)鎮(zhèn)320250153020鄉(xiāng)鎮(zhèn)430351501525鄉(xiāng)鎮(zhèn)530203015014鄉(xiāng)鎮(zhèn)620102025140表1決策變量為：1,如果消防站建在該鄉(xiāng)鎮(zhèn) Xj= 0,如果消防站沒有建在該鄉(xiāng)鎮(zhèn)j=1,2,6目標(biāo)函數(shù)為：Min Z = X1 + X2 + X3 + X4 + X5 + X6由上表，可以統(tǒng)計(jì)出各鄉(xiāng)鎮(zhèn)之間車程在15分鐘的情況，具體見表2：車程在15分鐘以內(nèi)的鄉(xiāng)鎮(zhèn)約束條件鄉(xiāng)鎮(zhèn)1鄉(xiāng)鎮(zhèn)1, 鄉(xiāng)鎮(zhèn)2X1+X21鄉(xiāng)鎮(zhèn)2鄉(xiāng)鎮(zhèn)1, 鄉(xiāng)鎮(zhèn)2, 鄉(xiāng)鎮(zhèn)6X1+X2+X61鄉(xiāng)鎮(zhèn)3鄉(xiāng)鎮(zhèn)3, 鄉(xiāng)鎮(zhèn)4X3+X41鄉(xiāng)鎮(zhèn)4鄉(xiāng)鎮(zhèn)3, 鄉(xiāng)鎮(zhèn)4, 鄉(xiāng)鎮(zhèn)5X3+X4+X51鄉(xiāng)鎮(zhèn)5鄉(xiāng)鎮(zhèn)4, 鄉(xiāng)鎮(zhèn)5, 鄉(xiāng)鎮(zhèn)6X4 + X5 + X61鄉(xiāng)鎮(zhèn)6鄉(xiāng)鎮(zhèn)2, 鄉(xiāng)鎮(zhèn)5, 鄉(xiāng)鎮(zhèn)6X2 + X5 + X61表2在表2中，X1+X21表示的含義是在鄉(xiāng)鎮(zhèn)1和鄉(xiāng)鎮(zhèn)2中必須建立至少一個(gè)消防站，以保證鄉(xiāng)鎮(zhèn)1一旦發(fā)生火災(zāi)，在15分鐘內(nèi)一定有消防隊(duì)伍趕到火場(chǎng)，以下的不等式表示的含義與之類似。由此可以建立數(shù)學(xué)模型為：Min Z= X1+X2+ X3 +X4 + X5 +X6S.T. X1+X21 X1+X2 +X61 X3 +X41 X3 +X4 + X51 X4 + X5 +X61 X2+ X5 +X61 Xj=0, 1 j=1,2,6解題時(shí)先通過試探的方法找一個(gè)可行解，容易看出（x1,x2,x3,x4,x5,x6）=(1,1,1,1,1,1)就是合于條件的，算出相應(yīng)的目標(biāo)函數(shù)值z(mì)=6。 我們求最優(yōu)解，對(duì)于極小化問題，當(dāng)然希望z6，于是增加一個(gè)約束條件： X1+X2+ X3 +X4 + X5 +X66 后加的條件稱為過濾條件。將7個(gè)約束條件按的順序排好（如表3所示），對(duì)每個(gè)解，依次代入約束條件左側(cè)，求出數(shù)值，看是否適合不等式條件，如果某一條件不適合，同行以下各條件就不必再檢查。在計(jì)算過程中，若遇到z值已小于條件右邊的值，應(yīng)改變條件，使右邊為迄今為止最大者，然后繼續(xù)運(yùn)算。通過設(shè)置和改進(jìn)過濾條件，可以大幅度減少計(jì)算量。解題步驟如下：點(diǎn)條件滿足條件？是（）否（）Z值（0，0，0，0，0，0）00（0，0，0，0，0，1）10（0，0，0，0，1，0）10（0，0，0，0，1，1）20（0，0，0，1，0，0）10（0，0，0，1，0，1）20（0，0，0，1，1，0）20（0，0，0，1，1，1）30（0，0，1，0，0，0）10（0，0，1，0，0，1）20（0，0，1，0，1，0）20（0，0，1，0，1，1）30（0，0，1，1，0，0）20（0，0，1，1，0，1）30（0，0，1，1，1，0）30（0，0，1，1，1，1）40（0，1，0，0，0，0）1110（0，1，0，0，0，1）2120（0，1，0，0，1，0）2110（0，1，0，0，1，1）3120（0，1，0，1，0，0）21211112表3（a）至此，z值已不能改進(jìn)，即得到最優(yōu)解，解答如下：X1=0X2=1X3=0X4=1X5=0X6=0Z=2也可以繼續(xù)計(jì)算，但在此題中，繼續(xù)計(jì)算已經(jīng)沒有意義，現(xiàn)將后續(xù)的計(jì)算過程列在表3（b）中：改進(jìn)過濾條件，用 X1+X2+ X3 +X4 + X5 +X62 代替，繼續(xù)進(jìn)行。點(diǎn)條件滿足條件？是（）否（）Z值（0，1，0，1，0，1）3（0，1，0，1，1，0）3（0，1，0，1，1，1）4（0，1，1，0，0，0）211110（0，1，1，0，0，1）3（0，1，1，0，1，0）3（0，1，1，0，1，1）4（0，1，1，1，0，0）3（0，1，1，1，0，1）4（0，1，1，1，1，0）4（0，1，1，1，1，1）5（1，0，0，0，0，0）1110（1，0，0，0，0，1）2110（1，0，0，0，1，0）2110（1，0，0，0，1，1）3（1，0，0，1，0，0）20（1，0，0，1，0，1）3（1，0，0，1，1，0）3（1，0，0，1，1，1）4（1，0，1，0，0，0）211110（1，0，1，0，0，1）3（1，0，1，0，1，0）3（1，0，1，0，1，1）4（1，0，1，1，0，0）3（1，0，1，1，0，1）4（1，0，1，1，1，0）4（1，0，1，1，1，1）5（1，1，0，0，0，0）1220（1，1，0，0，0，1）3（1，1，0，0，1，0）3（1，1，0，0，1，1）4（1，1，0，1，0，0）3（1，1，0，1，0，1）4（1，1，0，1，1，0）4（1，1，0，1，1，1）5（1，1，1，0，0，0）3（1，1，1，0，0，1）4（1，1，1，0，1，0）4（1，1，1，0，1，1）5（1，1，1，1，0，0）4（1，1，1，1，0，1）5（1，1，1，1，1，0）5（1，1，1，1，1，1）6表3（b）5 結(jié)論本文通過使用0-1整數(shù)線性規(guī)劃的隱枚舉法對(duì)消防站布局優(yōu)化問題提出了解決方法，為消防站的選址原則提供了科學(xué)依據(jù)，不再只是依靠經(jīng)驗(yàn)，在解決消防站布局優(yōu)化問題時(shí)，當(dāng)整數(shù)變量的個(gè)數(shù)較多時(shí)，可以利用MATLAB軟件對(duì)0-1線性規(guī)劃模型進(jìn)行程序化，從而省去了繁瑣的計(jì)算。在實(shí)際進(jìn)行消防站布局時(shí)，還要考慮其他主客觀因素，如當(dāng)?shù)氐牡貎r(jià)，是否有消防重點(diǎn)單位，風(fēng)向，行政區(qū)劃等。因此有可能導(dǎo)致不能覆蓋全縣，需要多次修正消防站布局。參考文獻(xiàn)1 李榮鈞,鄺英強(qiáng).運(yùn)籌學(xué)M.廣州:華南理工大學(xué)出版社.2007;4.2 甘應(yīng)愛,田豐