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

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