數(shù)學(xué)建模b題標(biāo)準(zhǔn)答案

1、2011 高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承諾書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng) 上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的，如果引用別人的成果或其他公開的 資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參 考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī) 則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號是（從 A/B/C/D中選擇一項填寫）：B我們的參賽報名號為（如果賽區(qū)設(shè)

2、置報名號的話）： 所屬學(xué)校（請?zhí)顚懲暾娜罕本┐髮W(xué)參賽隊員（打印并簽名）：1.姚勝獻(xiàn)2.許錦敏3.劉迪初指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）：劉業(yè)輝日期：2011 年9月12日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：2011高教社杯全國大學(xué)生數(shù)學(xué)建模競賽 編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）： 賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）： 全國評閱編號（由全國組委會評閱前進(jìn)行編號）： 交巡警服務(wù)平臺的設(shè)置與調(diào)度 摘要本文通過建立整數(shù)規(guī)劃模型，解決了分配各平臺管轄范圍、調(diào)度警務(wù)資源以及合理 設(shè)置交巡警服務(wù)平臺這三個

3、方面的問題；通過建立線性加權(quán)評價模型定量評價了某市現(xiàn) 有交巡警服務(wù)平臺設(shè)置方案的合理性，并根據(jù)各個區(qū)對服務(wù)平臺需求量的不同，提出了 重新分配全市警力資源的解決方案。在計算交巡警服務(wù)平臺到各個路口節(jié)點的路程時， 使用了圖論里的floyd算法。針對問題一的第一個子問題，首先假設(shè)交巡警服務(wù)平臺對某個路口節(jié)點的覆蓋度是 二元的，引入決策變量，建立了 0-1整數(shù)規(guī)劃模型。交巡警出警應(yīng)體現(xiàn)時間的緊迫性， 所以選擇平均每個突發(fā)事件的出警時間最短作為目標(biāo)函數(shù)，運用基于MATLAB勺模擬退火算法進(jìn)行求解，給出了中心城區(qū) A的20個服務(wù)平臺的管轄范圍，求得平均每個案件 的出警時間為1.013分鐘。針對問題一的第二

4、個子問題，為了實現(xiàn)對中心城區(qū) A的13個交通要道的快速全封 鎖，以最短的封鎖時間為目標(biāo)，建立了 0-1整數(shù)規(guī)劃模型，利用lingo軟件編程求解， 給出了該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案，并求得對 13個交通要道實現(xiàn)全封鎖 最短需要8.02分鐘。問題一的第三個子問題是交巡警服務(wù)平臺的選址問題?？紤]到建設(shè)新的服務(wù)平臺需 要投入更多的成本和警務(wù)資源，還需平衡各個服務(wù)平臺的工作量。因此，以增加最少的 服務(wù)平臺數(shù)和服務(wù)平臺工作量方差最小為目標(biāo)，采用集合覆蓋理論，建立了雙目標(biāo)0-1整數(shù)規(guī)劃模型，用基于 MATLAB勺模擬退火算法求解出增加的服務(wù)平臺數(shù)為 4個，新增 的服務(wù)平臺具體位置為 A8,A40,

5、A48,A88 ,并得到各個服務(wù)平臺的工作強(qiáng)度方差為 2.28。針對問題二的第一個子問題，通過建立線性加權(quán)評價模型定量評價了該市現(xiàn)有交巡 警服務(wù)平臺設(shè)置方案的合理性，結(jié)果發(fā)現(xiàn)全市服務(wù)平臺覆蓋率較低且各個區(qū)的工作量不 均衡，得出全市服務(wù)平臺的布局存在明顯的不合理的結(jié)論。并確定各區(qū)域人口密度、各 區(qū)域公路總長度以及各區(qū)域平均每天總的發(fā)案率為各區(qū)域?qū)谎簿枨蟮闹笜?biāo)，然后根據(jù)各個區(qū)對服務(wù)平臺需求量的不同，提出了較為合理的分配全市警力資源的解決方案。對于問題二的第二個子問題，以圍堵范圍最小和調(diào)動警力最少的原則，通過分析案 發(fā)后嫌疑犯可能到達(dá)的位置，給出了圍堵方案。關(guān)鍵詞：交巡警服務(wù)平臺0-1整數(shù)規(guī)劃模

6、擬退火法一、問題重述“有困難找警察”，是家喻戶曉的一句流行語。警察肩負(fù)著刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能。為了更有效地貫徹實施這些職能，需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警服務(wù)平臺。 每個交巡警服務(wù)平臺的職能和警力配備基本相同。由于警務(wù)資源是有限的，如何根據(jù)城市的實際情況與需求合理地設(shè)置交巡警服務(wù)平臺、分配各平臺的管轄范圍、調(diào)度警務(wù)資源是警務(wù)部門面臨的一個實際課題。試就某市設(shè)置交巡警服務(wù)平臺的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問題：（1）附件1中的附圖1給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個交巡警服務(wù)平臺的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見附件2。請為各交巡警服務(wù)平

7、臺分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在3 分鐘內(nèi)有交巡警（警車的時速為60km/h）到達(dá)事發(fā)地。對于重大突發(fā)事件，需要調(diào)度全區(qū) 20 個交巡警服務(wù)平臺的警力資源，對進(jìn)出該區(qū)的 13條交通要道實現(xiàn)快速全封鎖。實際中一個平臺的警力最多封鎖一個路口，請給出該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案。根據(jù)現(xiàn)有交巡警服務(wù)平臺的工作量不均衡和有些地方出警時間過長的實際情況，擬在該區(qū)內(nèi)再增加2 至 5 個平臺，請確定需要增加平臺的具體個數(shù)和位置。（2）針對全市（主城六區(qū)A, B, C, D, E, F）的具體情況，按照設(shè)置交巡警服務(wù)平臺的原則和任務(wù)， 分析研究該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案

8、（參見附件） 的合理性。如果有明顯不合理，請給出解決方案。如果該市地點P（第32個節(jié)點）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調(diào)度全市交巡警服務(wù)平臺警力資源的最佳圍堵方案。二、模型假設(shè)（ 1）每個交巡警服務(wù)平臺的職能和警力配備基本相同；（ 2）警車的行駛速度恒定，不考慮實際交通狀況的影響；（ 3）交巡警服務(wù)平臺接到報警后能立即出警，中間沒有延誤；（ 4）每個節(jié)點只能被一個服務(wù)平臺管轄；（ 5）一個平臺的警力最多封鎖一個路口。三、符號說明 服務(wù)平臺A管轄第j個路口節(jié)點的決策變量；在中心城區(qū)A中，從第i個服務(wù)平臺到第j個交叉路口節(jié)點的最短時間

9、； 中心城區(qū)A的第j個交叉路口節(jié)點的發(fā)案率;在中心城區(qū)A內(nèi)平均每個案件的出警時間;在中心城區(qū)A內(nèi)封鎖13個出入城區(qū)的路口節(jié)點的最短時間;¥丞城區(qū)A的13個出入城區(qū)的路口節(jié)點標(biāo)號的集合； 而不服務(wù)平臺的工作強(qiáng)度； 第k區(qū)分配的服務(wù)平臺資源比率。四、問題分析在城市規(guī)劃中，交巡警服務(wù)平臺的布局是一項非常重要的內(nèi)容。長期以來，由于種 種原因，目前的城市建設(shè)大多對警務(wù)資源的規(guī)劃缺乏科學(xué)性。交巡警服務(wù)平臺的選址、 管轄區(qū)域的劃分多依據(jù)經(jīng)驗進(jìn)行，大多數(shù)城市均不同程度地存在服務(wù)平臺布局不合理、 管轄范圍分配不均、警務(wù)資源調(diào)度困難等問題。另外，警務(wù)資源常常是有限的，設(shè)置交 巡警服務(wù)平臺也需要大量成本。

10、所以更有效地分配和調(diào)度警務(wù)資源對于城市的長治久安 有著重要的意義。本文著力解決的是合理地確定交巡警服務(wù)平臺的數(shù)量及其位置，合理 分配各平臺的管轄范圍以及當(dāng)重大突發(fā)事件發(fā)生時快速有效地調(diào)度警務(wù)資源這三方面 的問題。(1)對于問題一：在問題一中又有三個子問題需要解決。第一是要對中心城區(qū)A的20個現(xiàn)有交巡警服務(wù)平臺分配管轄范圍。首先假設(shè)每個 交叉路口節(jié)點要么被其中一個服務(wù)平臺完全管轄，要么被完全不管轄，即覆蓋度是二元 的，所以考慮到用0-1整數(shù)規(guī)劃模型。要使得案發(fā)后的損失減低到最小，就要求警方在 接到報警后能在最短的時間內(nèi)到達(dá)事故現(xiàn)場。 這樣就確定了平均每個突發(fā)事件警方出警 時間的目標(biāo)函數(shù)。第二是當(dāng)

11、重大突發(fā)事件發(fā)生后，要對中心城區(qū) A的20個交巡警服務(wù)平臺的警力資 源進(jìn)行調(diào)度，從而對進(jìn)出該區(qū)的13條交通要道實現(xiàn)快速全封鎖。同樣考慮使用 0-1整 數(shù)規(guī)劃模型。因為要求對交通要道實現(xiàn)全封鎖，所以問題的關(guān)鍵是合理調(diào)度警務(wù)資源使 得封鎖全部要道所需的總時間達(dá)到最小， 也就是使得出警時間最長的服務(wù)平臺所需的時 間盡可能的小。第三是針對現(xiàn)有的中心城區(qū)A的20個交巡警服務(wù)平臺進(jìn)行分析后，需要新增加25 個服務(wù)平臺以解決工作量不平衡和部分路口節(jié)點出警時間過長的問題。這屬于交巡警服務(wù)平臺選址問題。一方面考慮采用集合覆蓋模型1,目的是在滿足所有節(jié)點3分鐘內(nèi)都 有警方到達(dá)的條件下，使新增設(shè)的服務(wù)平臺數(shù)目盡可能

12、得小，從而降低了建設(shè)成本。另 一方面也要考慮新增設(shè)服務(wù)平臺后，能夠解決服務(wù)平臺工作量不平衡的問題，所以把盡 可能均衡各個服務(wù)平臺工作量作為第二個目標(biāo)。因此考慮需要建立一個兩目標(biāo)的 0-1整數(shù)規(guī)劃模型。(2)對于問題二：問題二中有兩個問題需要解決，一是根據(jù)已有的數(shù)據(jù)，評價全市六個區(qū)內(nèi)現(xiàn)有的交 巡警服務(wù)平臺的數(shù)目和布局的合理性，如果不合理就給出解決方案；二是當(dāng)該市P處發(fā)生重大刑事案件時，調(diào)度全市警力資源設(shè)計出最佳的圍堵方案。對于第一個小問題，要先按照設(shè)置交巡警服務(wù)平臺的原則和任務(wù)，對全市的交巡警 服務(wù)平臺的數(shù)目和布局討論其合理性。 交巡警服務(wù)平臺的選址應(yīng)遵循盡量使每個交巡警 服務(wù)平臺的工作量基本均

13、衡和每個節(jié)點突發(fā)事件發(fā)生時在3分鐘內(nèi)有警力到達(dá)的原則。所以選用各個服務(wù)平臺平均每天的工作強(qiáng)度(平均每天處理的突發(fā)事件數(shù))的方差和服 務(wù)平臺的覆蓋率（區(qū)域內(nèi) 3 分鐘內(nèi)有警方到達(dá)事發(fā)地的節(jié)點占區(qū)域內(nèi)總結(jié)點的比率）為指標(biāo)來進(jìn)行評價。如果在全市范圍內(nèi)現(xiàn)有交巡警服務(wù)平臺設(shè)置方案存在明顯的不合理性， 那么可能存在如下兩種原因：第一，該市分配給各個區(qū)的交巡警服務(wù)平臺比率不合理；第二，各個區(qū)內(nèi)的交巡警服務(wù)平臺選址方案不合理。對于第二種原因，在第一問第三個子問題中對A區(qū)交巡警服務(wù)平臺設(shè)置方案已經(jīng)做過詳細(xì)討論，可推廣到其他幾個區(qū)中?，F(xiàn)在設(shè)法解決由第一種原因引起不合理性的問題。據(jù)此，我們提出了依據(jù)各區(qū)域人口密度、

14、各區(qū)域公路總長度以及各區(qū)域平均每天總的發(fā)案率為三個評判指標(biāo)， 在全市范圍內(nèi)重新分配警力資源，也就是重新分配每個區(qū)服務(wù)平臺數(shù)量的解決方案。對于第二個小問題，首先分析出，在案發(fā)后的 3 分鐘內(nèi)，警方還未接到報警，即使嫌疑人開車駛過服務(wù)平臺，警方不能識別出嫌疑人；而3 分鐘后警方已接到報警，設(shè)此時警方掌握了足夠證據(jù)，故可以假設(shè)3 分鐘后只要警方與嫌疑人相遇就能夠?qū)⑵渥カ@。警方在接到報警后，根據(jù)嫌疑人可能逃跑的路徑，可以估計出嫌疑人逃跑的大致范圍，所以問題就轉(zhuǎn)化為，投入最少的警力以最快的速度形成包圍圈，并確保嫌疑犯在這段時間內(nèi)無法跑出包圍圈，即可認(rèn)為圍堵方案成功。五、模型的建立5.1 問題一：（ 1）

15、對于第一個子問題，考慮使用 0-1 整數(shù)規(guī)劃模型，下面確定目標(biāo)函數(shù)和約束條件。觀察每個路口節(jié)點平均每天的發(fā)案率，發(fā)現(xiàn)發(fā)案率不是很大，所以追加假設(shè)為每個服務(wù)平臺有足夠的時間去處理管轄范圍內(nèi)的突發(fā)事件， 即當(dāng)某個服務(wù)平臺處理一起突發(fā)事件的同時，在它所管轄的區(qū)域內(nèi)不會發(fā)生其他的突發(fā)事件。設(shè)問題的決策變量為xij 是 0-1 變量，即為了及時高效地處理突發(fā)事件，警方到達(dá)事發(fā)地應(yīng)爭分奪秒，在滿足時間緊迫性要求的前提下，使得平均每個案件的出警時間最短，所以確立了平均每個案件的出警時間最短作為唯一的目標(biāo)。然后確定了兩個約束條件，一是當(dāng)每個路口節(jié)點有突發(fā)事件發(fā)生時，都至少有一個服務(wù)平臺的交巡警到達(dá)現(xiàn)場處理事件

16、；二是要求任一服務(wù)平臺到達(dá)其所管轄的路口節(jié)點的時間都小于 3 分鐘。于是問題就轉(zhuǎn)化為求下面的 0-1 整數(shù)規(guī)劃問題：（ 2）對于第二個子問題，我們?nèi)钥紤]使用0-1 整數(shù)規(guī)劃模型。用 xijk 表示決策變量，即其中根據(jù)對問題的分析，要實現(xiàn)對要道的快速全封鎖，所以模型的目標(biāo)是使封鎖所有要道的總時間最短。所以關(guān)鍵在于控制封鎖要道所需時間最長的服務(wù)平臺的出警時間，使之達(dá)到最小值。確定了兩個約束條件，其一是當(dāng)每個路口節(jié)點有突發(fā)事件發(fā)生時，都至少有一個服務(wù)平臺的交巡警到達(dá)現(xiàn)場處理事件； 其二是一個平臺的警力最多封鎖一個路口。故，建立以下數(shù)學(xué)模型（ 3）對于第三個子問題，首先分析現(xiàn)有的交巡警服務(wù)平臺的分布，

17、發(fā)現(xiàn)存在交巡警服務(wù)平臺工作量不均衡和部分路口節(jié)點出警時間過長的問題。 這時考慮新增加幾個服務(wù)平臺，使得各個交巡警服務(wù)平臺的工作量盡可能相同以及使各個路口節(jié)點出警時間都被控制在3 分鐘內(nèi)。新建服務(wù)平臺需要成本，所以需要合理確定服務(wù)平臺的選址，使需要建立的服務(wù)平臺的數(shù)目最小。由此，我們參考集合覆蓋模型，建立了一個兩目標(biāo)0-1 整數(shù)規(guī)劃模型。設(shè)增加交巡警服務(wù)平臺后，平臺總數(shù)為 n0設(shè)平均每個交巡警服務(wù)平臺的建設(shè)成本為 1。對這一問題需要引入決策變量a。，設(shè)決策變量aj為定義服務(wù)平臺的工作強(qiáng)度為平均每天處理的突發(fā)事件數(shù)，則記qi表示第i個服務(wù)平臺的工作強(qiáng)度。集合覆蓋模型中考慮了建立服務(wù)平臺的成本，在給

18、定 3分鐘到達(dá)事發(fā)地的條件下， 其目標(biāo)之一是建設(shè)成本最小。另一方面，考慮到要使得各個服務(wù)平臺的工作量基本平衡， 所以確定第二個目標(biāo)為各個服務(wù)平臺平均每天工作強(qiáng)度的方差最小。模型描述為其中第一個約束條件說明所有路口節(jié)點都必須滿足在突發(fā)事件發(fā)生 3分鐘內(nèi)有警方到達(dá) 事發(fā)現(xiàn)場的要求。第二個約束條件則說明如果在 j點增設(shè)服務(wù)平臺，yj為1,否則為00 5.2問題二：(1)首先建立線性加權(quán)評價模型來分析評價該市交巡警服務(wù)平臺設(shè)置方案的合理性。根據(jù)第一問第一個子問題的模型，對六個區(qū)和全市可分別求出服務(wù)平臺的覆蓋率和 平均每個服務(wù)平臺工作強(qiáng)度的方差。確定兩個評價指標(biāo)，分別是各個區(qū)的服務(wù)平臺覆蓋 率以及各個服

19、務(wù)平臺的工作強(qiáng)度。設(shè)各個區(qū)和全市的服務(wù)平臺覆蓋率為g，做歸一化處理后的數(shù)據(jù)為gn；各個區(qū)內(nèi)服務(wù)平臺工作強(qiáng)度的方差為 s,方差的倒數(shù)1/s,做歸一化 處理后的數(shù)據(jù)為vn。那么綜合評價指標(biāo)h為 其中，為權(quán)重系數(shù)， 0,1 0(2)如果在全市范圍內(nèi)，現(xiàn)有交巡警服務(wù)平臺設(shè)置方案存在明顯的不合理性，那么可 能存在如下兩種原因：第一，該市分配給各個區(qū)的交巡警服務(wù)平臺資源比率不合理；第 二，各個區(qū)內(nèi)的交巡警服務(wù)平臺選址方案不合理。對于第二種原因，在第一問第三個子 問題中對A區(qū)交巡警服務(wù)平臺設(shè)置方案已經(jīng)做過詳細(xì)討論，現(xiàn)在設(shè)法解決由第一種原因 引起不合理性的問題?，F(xiàn)要在全市范圍內(nèi)重新分配警務(wù)資源， 也就是重新為

20、每個區(qū)分配交巡警服務(wù)平臺的 數(shù)目。由于每個區(qū)的實際狀況有所不同，那么每個區(qū)對交巡警服務(wù)平臺的需求量也不盡 相同。所以要根據(jù)每個區(qū)域內(nèi)對交巡警的需求量的大小來確定每個區(qū)域設(shè)置服務(wù)平臺數(shù) 目占總的服務(wù)平臺數(shù)目的比率。為此，需要引入各區(qū)域需求的權(quán)重來定量描述每個區(qū)對 服務(wù)平臺的需求量。下面確定各區(qū)域?qū)谎簿枨蟮臋?quán)重指標(biāo)。從服務(wù)群眾的角度考慮，可假設(shè)每個人 需要交巡警幫助的概率相同且相互獨立。那么，一地區(qū)對交巡警服務(wù)平臺的需求就與當(dāng) 地人口密度有關(guān)，人口密度越大，需求越大，所以引入人口密度為影響交巡警服務(wù)平臺 設(shè)置的第一個指標(biāo)。由分析知，人口密度是極大型指標(biāo)，即這個指標(biāo)越大，對交巡警服 務(wù)平臺的需求

21、越大。記這一指標(biāo)為r ,則對應(yīng)到A, B, C, D, E, F六個區(qū)為jlL北。 從交巡警服務(wù)平臺覆蓋率的角度考慮，當(dāng)這個區(qū)域的公路總長度越長時，則要求交巡警 服務(wù)平臺的密度越大，也就是交巡警服務(wù)平臺的需求量越大，于是引入公路長度作為第 二個指標(biāo)。止匕外，交巡警服務(wù)平臺的工作強(qiáng)度考慮，發(fā)案率大的地方要多配備警力，于 是引入發(fā)案率作為影響交巡警服務(wù)平臺設(shè)置的第三個指標(biāo)。確定好指標(biāo)后，對指標(biāo)進(jìn)行定量處理。1)各區(qū)域人口密度rk n (k 1,2, 6,對應(yīng)著A, B,C,D, E,F六個區(qū))，其中，以為第kSk區(qū)的總?cè)丝跀?shù)，Sk為第k區(qū)的總面積；2)主要交通干路總長度lk ;3)發(fā)案率fkWk

22、, (Nk表示第k區(qū)的節(jié)點集合)。ki Nk這三個指標(biāo)構(gòu)成矩陣其中Stepl： 一致化處理。由于這里的三個指標(biāo)均為極大型指標(biāo)，故不需要一致化處理。Step2：無量綱化處理。分別求出每個指標(biāo)的均值 上彳和均方差sr1sf ,無量綱處理 為* rk r* l k l* fk f .r (-)l 6 ， l (-)l 6， f (-)l 68rssfStep3:求權(quán)重。采用極差法求權(quán)重，為了求得權(quán)重，先求出 一 * 一rr max| r i r j |, 1 i, j 6同理可求得ll和ff ,令Z rr ll ff ,則權(quán)重則第k區(qū)分配的服務(wù)平臺資源比率為為了解決問題，我們追加假設(shè)：犯罪嫌疑人逃跑

23、的速度是恒定的，且等于警車的時速 60km/h(1)方案一：考慮到一般嫌疑犯對作案周邊環(huán)境比較熟悉，且嫌疑犯并不清楚是否有 人報警以及報警的具體時間，故嫌疑犯會盡量選擇避開交巡警服務(wù)平臺所在的節(jié)點。那 么嫌疑犯的逃跑的路線的組合就會減少很多。這樣圍堵方案的確定就簡單很多。(2)方案二：方案一本身存在一定缺陷，因為嫌疑犯是否對周邊環(huán)境熟悉，熟悉程度 是多少，以及嫌疑犯的心理和性格狀態(tài)如何，這些都是不確定的。所以，嫌疑犯仍然可 能隨機(jī)選擇逃跑的方向，這時嫌疑犯可選擇的逃跑路徑有很多種，圍堵方案也較難確定。 但是兩個模型的求解思路是一致的。最佳的圍堵嫌疑犯的方案，就是在出動的警力最少的情況下，在最短

24、時間內(nèi)把嫌疑 犯圍堵在一個盡可能小的包圍圈內(nèi)，使嫌疑犯不能逃出這個包圍圈。具體圍堵方案的步 驟如下：1)確定嫌疑犯3分鐘內(nèi)可以經(jīng)過的最多的點數(shù)，由于嫌疑犯是從P點連續(xù)移動的，所以這些節(jié)點構(gòu)成的圖是連通圖，設(shè)為G ,同時可以認(rèn)為G就是嫌疑犯的活動范圍。G以 外的點中是嫌疑犯尚未經(jīng)過的節(jié)點，其中有若干節(jié)點與G直接相連，這些節(jié)點就是嫌疑 犯下一步可能經(jīng)過的節(jié)點，記它們的集合為B ,記在G內(nèi)與B直接相連的節(jié)點構(gòu)成的集 合D,它表示嫌疑犯可以從D中某點出發(fā)，前往與之直接相連的B中的某點，以擴(kuò)大其 活動范圍。當(dāng)D 時，嫌疑犯就不能擴(kuò)大其活動范圍，這樣，相當(dāng)于嫌疑犯被限制在 了一個有限的區(qū)域，即嫌疑犯被成功

25、圍堵。2)取dk D,并取bi B ,且bi可由dk直接到達(dá)，這樣就構(gòu)成一個出逃的組合。以交巡 警接到報警的時刻為時間的原點，這時計算嫌疑犯和距離bi最近的交巡警到達(dá)b的時問，分別記為txi和tji。當(dāng)txi tji,表示嫌疑犯會先到達(dá)b,而交巡警后到達(dá)bi,這樣， 交巡警就不能圍堵成功，于是，嫌疑犯成功將活動范圍擴(kuò)大到b ,即應(yīng)該將bi加入到活動范圍G ,且bi可以作為下一步擴(kuò)大活動范圍的起始點，于是還應(yīng)該將 b加入到D ,且 與bi直接相連且在G外圍的節(jié)點加也要入B。注意此時dk可能不再有G外的節(jié)點與它直 接相連，這時是需要將 dk從D中刪除的。當(dāng)txi tji ,則嫌疑犯到達(dá)b的時間不比

26、交巡 警早，這樣交巡警就可以將嫌疑犯逃跑的這條路圍堵死，調(diào)遣這些交巡警前往 b ,且當(dāng) 他們被選定之后，就不能被再次調(diào)動，因為他們一旦被調(diào)走，可能使嫌疑人從這個節(jié)點擺脫圍堵。 在 txi tji 的情況下， 由于嫌疑人不能擴(kuò)大活動范圍到bi ， 于是bi 就不能加入G ，這時要把b從B中刪除。如果原先dk向外只與b直接相連，那么當(dāng)把b從B中刪除時， dk就不能作為嫌疑人擴(kuò)大活動范圍的起始點，這時需要把 dk從D中刪除；如果原先除 了 bi , dk還與B中其他節(jié)點直接相連，則不能把dk從D中刪除。這樣逐個對B 和 D 中直接相連的節(jié)點組合 (即出逃組合) 進(jìn)行如上分析， 當(dāng) D 時，嫌疑犯被限

27、制在了一個有限的區(qū)域，即嫌疑人被圍堵成功。圍堵成功時，各交巡警所在的位置即他們應(yīng)該在接到報警時被派遣到的位置。這樣就確定了圍堵調(diào)遣的方案。綜上所述，建立模型如下：初始條件為 G G ， I I0 ，即初始時刻 G 的點集和 I 的點集。F(Gx)表示求G中點的個數(shù)的函數(shù)，I表示交巡警服務(wù)平臺的集合，H(I)表示求I中改變位置的交巡警服務(wù)平臺的個數(shù)的函數(shù)，即求調(diào)遣的交巡警服務(wù)平臺的個數(shù)的函數(shù)， 0,1表示權(quán)重。從初始條件開始，進(jìn)行上面算法，直到 D 或者約束條件不滿足停止。當(dāng) D ，則圍堵成功，從所有出逃組合中選出目標(biāo)函數(shù)最優(yōu)的圍堵方案，就可以確定出最優(yōu)調(diào)遣方案；當(dāng)約束條件不滿足，則表示嫌疑犯成

28、功擺脫圍堵。下面給出算法流程圖。開始圖1圍堵方案的算法流程圖六、模型的求解6.1問題一:(1)第一個子問題需要先用floyd算法求解出各交巡警服務(wù)平臺到各個路口節(jié)點的最 短距離，在此基礎(chǔ)上再求解 0-1整數(shù)規(guī)劃模型。這個整數(shù)規(guī)劃模型的 0-1變量有1840 個，考慮用基于MATLAB勺模擬退火算法求解。根據(jù)約束“任一服務(wù)平臺到達(dá)其所管轄 的路口節(jié)點的時間都小于3分鐘”來過濾可行域，發(fā)現(xiàn)某些路口節(jié)點并不能嚴(yán)格地滿足“tjXj 3”這一約束條件，對于這類路口節(jié)點，可以放寬約束為 tjXj 3(1 j),使可 行域不為空集。用模擬退火法求解模型時，設(shè)置初始溫度 T。為100000,終止溫度Tf為 0

29、.0001 ,溫度衰減系數(shù)為0.995 ,Markov鏈長度為100,求得一個較優(yōu)解的目標(biāo)值為1.013 分鐘，管轄范圍如下：表一 A區(qū)各服務(wù)平臺的管轄范圍服務(wù)平臺節(jié)點管轄的節(jié)點AiA ,A64,A 67,A 68,A 69,A 71,A 73,A 74,A 75A2A2,A 39,A 40,A 43A3A3,A 44,A 54,A 55,A 66AA,A 57,A 58,A 62,A 63AA5,A 49,A 叫A 51,A 52,A 53,A 56AA6,A 58,A 59AA ,A 30,A 31,A 32,A 48,A 61AA8,A 46,A 47AA9,A 33,A 35,A 36

30、,A 45A10A10A11Ai1,A26,A27A12Ai2,A25A13A13,A21,A22,A23,A24Ai4Ai4Ai5Ai5,A28,A29A16A16,A37,A38,A34Ai7Ai7,A41 ,A42A18A18,A81,A84Ai9A19,A65,A76,A77,A78,A79,A80A20A20,A82,A83,A85,A86,A87,A88,A89,A90,A 91,A 92依據(jù)這個較優(yōu)解，可求得A區(qū)各個服務(wù)平臺的工作強(qiáng)度(平均每天處理案件的次數(shù)) 如下：表二 中心城區(qū)A各服務(wù)平臺的工作強(qiáng)度(次/天)服務(wù)平臺AiAAAAAAAA9A10工作強(qiáng)度9.2r 6.965.8

31、7.74 4.59.65.27.41.6服務(wù)平臺A11A12Ai3Al4A15A16Al7A18A19A20工作強(qiáng)度4.6r 4.08.52.54.8r 5.67.04.36.812.5圖2中心城區(qū)A各服務(wù)平臺的工作強(qiáng)度示意圖實際上，A區(qū)服務(wù)平臺不能完全覆蓋每一個路口節(jié)點，有些路口節(jié)點案發(fā)3分鐘后交巡警才能從服務(wù)平臺趕到，下面給出服務(wù)平臺需要超過3分鐘才能到達(dá)的路口節(jié)點及 到達(dá)時間：表三 超過3分鐘到達(dá)的路口節(jié)點及其到達(dá)時間路口節(jié)點A28A29A38A39A6iA92到達(dá)時間/min4.755.703.413.684.193.60分析以上結(jié)果可知，有些服務(wù)平臺的管轄范圍很大，工作強(qiáng)度也大，如A

32、i, A7,樂;而有些服務(wù)平臺的管轄范圍很小，工作強(qiáng)度小，如A。，A% A140這樣就存在有交巡警資源浪費和工作量過負(fù)荷等問題，A區(qū)服務(wù)平臺的設(shè)置不盡合理?？梢愿鶕?jù)需要新增加 服務(wù)平臺來平衡各個服務(wù)平臺的工作量。第二個子問題的0-1整數(shù)規(guī)劃模型利用lingo軟件編程求解，求得最快封鎖時間為8.02分鐘，具體的封鎖方案和對應(yīng)的時間如下：表四 封鎖方案及對應(yīng)的時間服務(wù)平臺節(jié)點AAAAA10A1A12被封鎖路口A16A48A29Aj0A22A23A24所用時間/min6.022.488.023.497.714.683.59服務(wù)平臺節(jié)點A13A14A5A|6Al7A被封鎖路口A12AA28A4A8A6

33、2所用時間/min5.983.274.756.744.766.73圖3 A區(qū)封鎖方案示意圖(3)第三個子問題所建立的是雙目標(biāo)的 0-1整數(shù)規(guī)劃模型，第一目標(biāo)為增加的服務(wù)平臺 最少，第二目標(biāo)為各個服務(wù)平臺每天的服務(wù)強(qiáng)度方差最小。為了求解模型，先只考慮第 一目標(biāo)，然后再在第一目標(biāo)最優(yōu)的情況下給出第二目標(biāo)最優(yōu)的解。依然用基于 MATLAB 的模擬退火算法求解出增加的服務(wù)平臺數(shù)最少為4,在此基礎(chǔ)上，求得使各服務(wù)平臺工作強(qiáng)度方差最小的平臺選址方案為 A8,A40,A48,A88 ,這時各個服務(wù)平臺的工作強(qiáng)度方差為 2.28,各個服務(wù)平臺的服務(wù)強(qiáng)度如下：表五 新增服務(wù)平臺后A區(qū)各服務(wù)平臺的服務(wù)強(qiáng)度(次/天

34、)服務(wù)平臺AAA3AAAA7A8工作強(qiáng)度7.66.166.65 5.95.15.55.1 1服務(wù)平臺AA10A11A12A3Al4A15A16工作強(qiáng)度5.21.64.64.08.52.53.75.1服務(wù)平臺A17A18A19A20A28A。A48A88工作強(qiáng)度5.35.55.75.92.75.25.35.8圖4新增服務(wù)平臺后A區(qū)各服務(wù)平臺的服務(wù)強(qiáng)度示意圖新增服務(wù)平臺后A區(qū)各服務(wù)平臺的管轄范圍如下。表六 新增服務(wù)平臺后A區(qū)各服務(wù)平臺的管轄范圍服務(wù)平臺節(jié)點管轄的節(jié)點AiAi ,A42,A 66,A 72,A 75,A 77AA2,A 67,A 69,A 76,A 78AA3,A 54,A 55,A

35、 64,A 65AA4,A 57,A 60,A 62,A 63AA5,A 53,A 59AA6,A50,A 51,A 52,A 56,A 58AA7,A 32,A 37,A 46AA8,A46,A47AA9,A 35,A45AioAl0AiiAl1,A26,A27Al2Al2,A25Al3Al3,A21,A22,A23,A24Al4Al4A|5Al5,A31Al6Al6,A34,A36Al7Al7,A40,A43,A70Al8Al8,A73,A79,A80,A84,A91Al9Al9,A68,A71 ,A73,A78A20A20,A81 ,A82,A83,A84A28A28,A29A40A38

36、,A39,A40,A44A48A30,A48,A49,A61A88A86,A87,A88,A89 Ag0,A92圖5新增的服務(wù)平臺及其管轄范圍的示意圖6.2問題二：(1)用第一問第一個子問題的模型對該市各區(qū)情況求解，得到各區(qū)和全市的服務(wù)平臺 的覆蓋率以及服務(wù)平臺的平均工作強(qiáng)度方差，統(tǒng)計結(jié)果如下：表七各區(qū)和該市的服務(wù)平臺覆蓋率及服務(wù)平臺的平均工作強(qiáng)度方差區(qū)域A區(qū)B區(qū)C區(qū)D區(qū)E區(qū)F區(qū)全市覆盍率0.93 10.920.69r 0.77 10.660.70r 0.76工作強(qiáng)度方差6.4720.0423.889.9425.2445.0023.12用最大最小法對以上數(shù)據(jù)進(jìn)行歸一化得到如下結(jié)果：表八評價指標(biāo)

37、歸一化后的數(shù)據(jù)區(qū)域A區(qū)B區(qū)C區(qū)D區(qū)E區(qū)F區(qū)全市r i0.960.11r 0.4100.15r 0.37 1i0.210.150.590.1300.16若認(rèn)為服務(wù)平臺覆蓋率和服務(wù)平臺的平均工作強(qiáng)度方差在評價體系中占同等重要的地位，即設(shè)權(quán)重系數(shù)為0.5,利用綜合評價指標(biāo)公式h gn (1) vn ,可求得各個區(qū)域的評價分?jǐn)?shù)分別為：A區(qū)1分，B區(qū)0.59分，C區(qū)0.13分，D區(qū)0.50分，E 區(qū)0.07分，F(xiàn)區(qū)0.08分，全市0.27分。從以上結(jié)果可知，A區(qū)服務(wù)平臺的覆蓋率最大，各個服務(wù)平臺的工作量較為均衡， 故A區(qū)得分最高。E區(qū)得分最低，說明E區(qū)服務(wù)平臺覆蓋率很低，區(qū)內(nèi)各個服務(wù)平臺工 作量明顯不均

38、衡。全市的得分也較低，說明整個市區(qū)服務(wù)平臺覆蓋率都不高，全市各個 服務(wù)平臺工作量較為不平衡，所以可以判斷出該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案很不合 理，需要對服務(wù)平臺的設(shè)置進(jìn)行全市范圍內(nèi)的調(diào)整。由于該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案有明顯的不合理性，需要對現(xiàn)有的交巡警資源進(jìn)行合理化分配?；诂F(xiàn)有的數(shù)據(jù)，可獲得各個區(qū)的人口密度、交通干路總長度和發(fā)案率，統(tǒng)計結(jié)果 如下：表九 各個區(qū)的人口密度、交通干路總長度和發(fā)案率區(qū)域A區(qū)B區(qū)C區(qū)D區(qū)E區(qū)F區(qū)人口密度/萬人每平 方公里2.730.20.220.190.170.19干路長度/米401919187841 1818498303625552443564342發(fā)案率

39、/次每日124.566.4187.267.8119.4109.2根據(jù)所建立的模型，得出各個指標(biāo)的權(quán)重(r，d，f)= (0.31,0.35 , 0.34)由公式k r4 dd f 4可得出每個區(qū)分配的交巡警服務(wù)平臺的比 rditi 1i 1i 1率 (1，2，3，4，5，6)= (0.26,0.08,0.24,0.10,0.16,0.16)。假設(shè)全市的交巡警服務(wù)平臺的總數(shù)依然是80個，那么每個區(qū)理論上應(yīng)該分配的服務(wù)平臺數(shù)分別為：A區(qū)21個，B區(qū)6個，C區(qū)19個，D區(qū)8個，E區(qū)13個，F(xiàn)區(qū)13個。與原方案比較，A區(qū)增 力口 1個，B區(qū)減少2個，C區(qū)增加2個，D區(qū)減少1個，E區(qū)減少2個，F(xiàn)區(qū)增加3

40、個。對新的分配方案進(jìn)行分析研究：A區(qū)雖然平均每個服務(wù)平臺的工作強(qiáng)度偏低，但因A區(qū)人口密度高，考慮到治安情況復(fù)雜，交通容易出現(xiàn)堵塞等因素，應(yīng)分配較多的服務(wù) 平臺資源。B區(qū)的城區(qū)面積小，人口密度不大，服務(wù)平臺的覆蓋率大，可以考慮適當(dāng)減 少服務(wù)平臺。在原來的服務(wù)平臺設(shè)置方案中，C區(qū)的平均每個服務(wù)平臺的工作強(qiáng)度最大而且服務(wù)平臺覆蓋率很低,故可優(yōu)先考慮為C區(qū)增加交巡警服務(wù)平臺。D區(qū)和E區(qū)平均每個服務(wù)平臺的工作強(qiáng)度不大，可以適當(dāng)減少服務(wù)平臺個數(shù)。F區(qū)的服務(wù)平臺覆蓋率較低，平均每個服務(wù)平臺的工作強(qiáng)度較大，可適當(dāng)增加服務(wù)平臺數(shù)。如果全市交巡警服務(wù)平臺數(shù)保持80個，可以按照上述方案進(jìn)行區(qū)域之間的調(diào)度。 基于在全

41、市范圍內(nèi)服務(wù)平臺覆蓋率(76%過低的情況，建議該市適當(dāng)增加交巡警服務(wù) 平臺，服務(wù)平臺資源應(yīng)優(yōu)先分配給 C區(qū)。(2)下面給出圍堵的最佳方案：1)對方案一的求解：由于標(biāo)號7,15,8,9,10 , 16節(jié)點均為交巡警服務(wù)平臺，故嫌疑人 不會向這些方向逃跑，則嫌疑人會向標(biāo)號為37的節(jié)點的方向逃跑，3分鐘內(nèi)逃到最遠(yuǎn)的 節(jié)點的標(biāo)號為45。由此可知，在報警前，嫌疑人可能到過的節(jié)點為標(biāo)號分別為 31,33,34,35,36,37 , 45。如果嫌疑人在報警時已經(jīng)到達(dá)標(biāo)號為 45的節(jié)點，那么他會向 編號為55的節(jié)點逃跑，這時，只需標(biāo)號為3的節(jié)點處的交巡警前往55號節(jié)點，同時標(biāo) 號為2的節(jié)點補(bǔ)上標(biāo)號為3的節(jié)點的

42、位置，就可以將嫌疑人圍堵?。煌瑯尤绻诮谎簿?接到報警時，嫌疑人在標(biāo)號為36的節(jié)點，相似的討論后，得到嫌疑人只能向標(biāo)號為39和38的節(jié)點逃跑，這時只要標(biāo)號為節(jié)點 480的節(jié)點處的交巡警前往標(biāo)號為 561的節(jié)點 處堵截，就可以將逃犯圍堵成功。由于在交巡警接到報警時，嫌疑犯在其他可能的節(jié)點， 則嫌疑犯必須先前往45或者36號節(jié)點，由上面的分析知道，用同樣的方法依舊可以將 嫌犯圍堵成功。故圍堵方案如下。起始點圍堵點：3 55, 2 3, 480 561。2)方案二的求解：首先判斷出嫌疑人在 3分鐘報警前可能到達(dá)的節(jié)點有14個，它們的 標(biāo)號分別是 7,8,9,30,31,33,34,35,36,37,45,46,47,48 ，其中，從 47號向外逃跑,會 遇到8號節(jié)點的交巡警，從而直接被抓獲，故不需考慮這一節(jié)點。同理分析可知，只要 嫌疑犯從36,45,46,30,48這五個節(jié)點出發(fā)，仍然被圍堵，那么從其他節(jié)點出發(fā)也會被 圍堵(因為從其他節(jié)點出發(fā)