20年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽b題

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

2、擇一項(xiàng)填寫）： B我 們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話） ： 所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜?： 參賽隊(duì)員 （打印并簽名 ） ：1. 韓曉峰2. 楊曉帆3. 李弘倩指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 （打印并簽名 ）：日期： 2011年 9月11日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2011 高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編號(hào)專用頁賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度摘要在（1）第一問中，我們根據(jù)附表 1 所給各路口坐

3、標(biāo)算出 A圖中每條路線的長(zhǎng)度， 然后通過 floyd 算法找出了兩點(diǎn)之間的最短路程， 得出矩陣 D，通過使用 matlab 圈出各 服務(wù)平臺(tái)到周圍路口小于 3min（即 3km）的點(diǎn)，再根據(jù)就近原則，將各路口劃分到這個(gè) 圈中離此路口最近的交巡警平臺(tái)。對(duì)于任意到交巡警平臺(tái)路程大于3min（即 3km）序號(hào)為 28，29，38，39，61，92 的五個(gè)路口，則采用就近原則人工劃入距離其最近的交巡 警平臺(tái)轄區(qū)，這樣就在保證出警時(shí)間基本都小于 3min 的條件下，劃分出各警務(wù)平臺(tái)合 理的管轄范圍。對(duì)于（1）第二問中，我們采用指派模型，用 lingo 軟件對(duì) 20 個(gè)巡警服務(wù)平臺(tái)對(duì) 17 個(gè)城市出入口進(jìn)

4、行封鎖的方法進(jìn)行了優(yōu)化， 得到初步的調(diào)度方案。 在這個(gè)方案的基礎(chǔ)上， 如果在某條巡警服務(wù)平臺(tái)調(diào)度路線中經(jīng)過其他的的調(diào)度點(diǎn)， 則與所經(jīng)過的調(diào)度點(diǎn)互換目 標(biāo)路口，由此得到最佳調(diào)度方案，即最快 8 分鐘可以實(shí)現(xiàn)快速封鎖路口。對(duì)于（ 1）第三問，我們按照工作量均衡和出警時(shí)間盡可能短的原則考慮增加交巡 警平臺(tái)。首先，利用 excel 算出了各轄區(qū)內(nèi)交巡警服務(wù)平臺(tái)的工作量總和以及出警時(shí)間 的平均值，求出了所有轄區(qū)的工作總量與出警時(shí)間的平均值，取出工作總量明顯高于平 均值且平均出警時(shí)間超過 3min 的四個(gè)轄區(qū)來增設(shè)新的交巡警平臺(tái)。我們通過（ 1）第一 問中的最短路程矩陣得到各轄區(qū)內(nèi)種增設(shè)平臺(tái)的所有可能的方

5、法， 通過比較每種方法的 工作量總和及出警時(shí)間綜合考慮得到一個(gè)最優(yōu)的設(shè)置。最后通過 spss 軟件求得優(yōu)化前 后兩組數(shù)據(jù)的標(biāo)準(zhǔn)差，比較后發(fā)現(xiàn)優(yōu)化后的數(shù)據(jù)標(biāo)準(zhǔn)差明顯下降，達(dá)到了優(yōu)化的目的。在（2）第一問中，首先參照（ 1）中 A 區(qū)的處理方法分別求出了城區(qū) B，C，D，E， F中路口到最近交巡警服務(wù)平臺(tái)的路程， 出警時(shí)間以及工作量。 通過 spss 軟件計(jì)算出標(biāo) 準(zhǔn)差，并與優(yōu)化后的 A 城區(qū)進(jìn)行比較，找出了交巡警平臺(tái)明顯分配不合理（標(biāo)準(zhǔn)差遠(yuǎn)高 于 A 區(qū)優(yōu)化后方案的標(biāo)準(zhǔn)差） 的三個(gè)區(qū)，在其距離較遠(yuǎn)工作量較大的路口增設(shè)服務(wù)平臺(tái)。對(duì)于（ 2）中第二問搜捕嫌疑犯問題，我們采用時(shí)間圈法，以事發(fā)地點(diǎn)為圓心

6、，以 一分鐘所行使的路程為單位半徑，畫出等間隔的數(shù)個(gè)同心圓，這樣就可以確定每個(gè)時(shí)間 段嫌疑犯的逃逸范圍（因?yàn)槿我鈨牲c(diǎn)間的路程大于等于兩點(diǎn)間的距離，所以在某時(shí)間內(nèi) 嫌疑犯必定在對(duì)應(yīng)的時(shí)間圈內(nèi)） ，根據(jù)每個(gè)路口在這些時(shí)間圈上的位置，要求警察到這 些路口的時(shí)間小于罪犯到達(dá)的時(shí)間（即可以圍堵住罪犯） ，找出所有這些路口，構(gòu)成閉 圈，最小的閉圈便是圍堵罪犯的最佳方案。關(guān)鍵詞： floyd 算法，指派模型， spss 分析數(shù)據(jù)，時(shí)間圈法、問題的提出“有困難找警察”，這是一句家喻戶曉的流行語。警察是保證人民生命安全及財(cái)產(chǎn) 安全的守護(hù)神，他們肩負(fù)著刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能。為了 更有效地

7、貫徹實(shí)施這些職能， 所以需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警服 務(wù)平臺(tái)。每個(gè)交巡警服務(wù)平臺(tái)的職能和警力配備基本相同。由于警務(wù)資源是有限的，如 何根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡警服務(wù)平臺(tái)、分配各平臺(tái)的管轄范圍、調(diào) 度警務(wù)資源是警務(wù)部門面臨的一個(gè)實(shí)際課題。1.2 問題（1）附件 1 中的附圖 1 給出了該市中心城區(qū) A的交通網(wǎng)絡(luò)和現(xiàn)有的 20個(gè)交巡警服 務(wù)平臺(tái)的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見附件 2。請(qǐng)為各交巡警服務(wù)平臺(tái)分配管轄 范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在 3 分鐘內(nèi)有交巡警（警車的時(shí) 速為 60km/h）到達(dá)事發(fā)地。對(duì)于重大突發(fā)事件，需要調(diào)度全區(qū) 20

8、個(gè)交巡警服務(wù)平臺(tái)的警力資源，對(duì)進(jìn)出該區(qū) 的 13 條交通要道實(shí)現(xiàn)快速全封鎖。實(shí)際中一個(gè)平臺(tái)的警力最多封鎖一個(gè)路口，請(qǐng)給出 該區(qū)交巡警服務(wù)平臺(tái)警力合理的調(diào)度方案。根據(jù)現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡和有些地方出警時(shí)間過長(zhǎng)的實(shí)際情況， 擬 在該區(qū)內(nèi)再增加 2 至 5 個(gè)平臺(tái)，請(qǐng)確定需要增加平臺(tái)的具體個(gè)數(shù)和位置。（2）針對(duì)全市（主城六區(qū) A，B，C，D，E，F(xiàn)）的具體情況，按照設(shè)置交巡警服務(wù) 平臺(tái)的原則和任務(wù)， 分析研究該市現(xiàn)有交巡警服務(wù)平臺(tái)設(shè)置方案 （參見附件） 的合理性。 如果有明顯不合理，請(qǐng)給出解決方案。如果該市地點(diǎn) P（第32個(gè)節(jié)點(diǎn)）處發(fā)生了重大刑事案件，在案發(fā) 3分鐘后接到報(bào)警， 犯罪嫌疑

9、人已駕車逃跑。為了快速搜捕嫌疑犯，請(qǐng)給出調(diào)度全市交巡警服務(wù)平臺(tái)警力資 源的最佳圍堵方案。二、模型的假設(shè)1. 警察接到報(bào)案后能立即出警2. 案發(fā)地點(diǎn)都在路口附近3. 嫌疑犯逃逸速度與警察速度相同4. 各城區(qū)內(nèi)交巡警平臺(tái)在不發(fā)生特殊情況時(shí)只管轄自己城區(qū)的路口5. 警察接到報(bào)警后犯罪嫌疑人不能再通過有警察的路口三、符號(hào)說明X m ：m點(diǎn)的橫坐標(biāo)Xn：n 點(diǎn)的橫坐標(biāo)Ym ：m點(diǎn)的縱坐標(biāo)Yn：n 點(diǎn)的縱坐標(biāo)L：任意兩點(diǎn)間距離xij ：交巡警平臺(tái) i 封鎖路口 jZ：交巡警平臺(tái)封鎖交通要道經(jīng)過的總路程Cij ：經(jīng)巡警平臺(tái) i 封鎖路口 j 所走的距離四、問題分析4.1 問題一附件 1 給出了某市中心城區(qū)

10、A的交巡警服務(wù)平臺(tái)的相關(guān)情況， 首先要求分配平臺(tái)管 轄范圍使交巡警在有突發(fā)事件時(shí)盡可能 3 分鐘內(nèi)趕到事發(fā)地； 而后要求給出重大事件時(shí) 20 個(gè)平臺(tái)快速封鎖 13條交通要道的合理方案，最后要求對(duì)交巡警服務(wù)平臺(tái)進(jìn)行改進(jìn)。對(duì)問題一的解答可先采用 floyd 算法算出任意兩點(diǎn)間最短路徑并根據(jù)就近原則進(jìn)行 分配管轄范圍；而后可利用指派模型對(duì)巡警封鎖路口問題進(jìn)行初步優(yōu)化；最后可根據(jù)出 警時(shí)間和工作量總和找出服務(wù)平臺(tái)不均衡的地方，優(yōu)化后可利用標(biāo)準(zhǔn)差進(jìn)行比較。4.2 問題二 根據(jù)附件中全市交巡警平臺(tái)的相關(guān)數(shù)據(jù)， 首先要求分析六個(gè)區(qū)的交巡警平臺(tái)設(shè)置方 案的合理性，并給出解決方案；最后要求給出一個(gè)調(diào)度服務(wù)平臺(tái)警

11、力資源的最佳圍堵方 案。對(duì)與問題二， 首先可計(jì)算出除 A區(qū)外其余五區(qū)的標(biāo)準(zhǔn)差并于優(yōu)化過的 A區(qū)想關(guān)數(shù)據(jù) 的標(biāo)準(zhǔn)差進(jìn)行比較，分析各區(qū)服務(wù)平臺(tái)設(shè)置方案的合理性；而對(duì)于最佳圍堵方案，我們 則可先做出帶有時(shí)間圈的圖然后采用時(shí)間圈法進(jìn)行優(yōu)化。五、模型的建立和求解5.1 問題一模型的建立和求解5.1.1 任意兩點(diǎn) m,n 之間的距離可利用程序由坐標(biāo)求得 得出一個(gè)關(guān)于各點(diǎn)距離的矩陣， R1 ，將相鄰兩點(diǎn)的距離保留，不相鄰點(diǎn)之間的距離變?yōu)?inf 用 floyd 算法（程序 1）求出任一兩點(diǎn)間的路程矩陣 R2 ，下圖為 R2的一部分：找出每個(gè)路口到交巡警平臺(tái)的 路程，并通過 matlab 程序（程序 2）根據(jù)

12、就近原則篩選出小于 3min（3km） 的點(diǎn)，劃歸各交巡警平臺(tái)。對(duì)于大于 3min（3km）的點(diǎn) 28，29，38，39，61，92 在 R2中找出其對(duì)應(yīng)的 最短路程，并對(duì)其進(jìn)行分配 , 分區(qū)圖如下圖 1：圖 1 （不同顏色線條表示不同區(qū)域） 說明：（1）圖中實(shí)線表示市區(qū)道路；紅色線表示連接兩個(gè)區(qū)之間的道路； （2）實(shí)圓點(diǎn)“ · ”表示交叉路口的節(jié)點(diǎn)，沒有實(shí)圓點(diǎn)的交叉線為道路立交；（3）星號(hào)“ * ”表示出入城區(qū)的路口節(jié)點(diǎn)；4)圓圈“ ”表示現(xiàn)有交巡警服務(wù)平臺(tái)的設(shè)置點(diǎn)；5)圓圈加星號(hào)“ *” 表示在出入城區(qū)的路口處設(shè)置了交巡警服務(wù)平臺(tái)；5.1.2記交巡警平臺(tái) i=1 ，2,3 20出

13、入城區(qū)的路口節(jié)點(diǎn) j=1,2,3 13第一：一個(gè)交巡警平臺(tái)的警力最多封鎖一個(gè)路口13則有 xij 1,i 1,2,3.20j1第二：每個(gè)路口節(jié)點(diǎn)最少需要一個(gè)交巡警平臺(tái)的警力封鎖20則有 xij 1,j 1,2,3.13i1當(dāng)交巡警平臺(tái) i 封鎖路口節(jié)點(diǎn) j 時(shí)cij xij 表示交巡警平臺(tái)所走的路程，否則 cij xij =020 13 則，目標(biāo)函數(shù)為交巡警總路程 zcij xiji1j1 綜上所述，該問題為 0-1 規(guī)劃 模型為：13xij 1,i 1,2,3.20j120xij 1,j 1,2,3.13i1 xij 0或1 通過 lingo 編程(程序 3)求解出一個(gè)可使總時(shí)間即總路程最小

14、的最優(yōu)解。 通過 lingo 求出最快封鎖道路的初步優(yōu)化模型：X(2,11)1.00000039.82200X(4,13)1.0000003.500000X(5,12)1.00000024.75800X(7,10)1.0000005.831000X(8,9)1.000000104.9300X(9,4)1.000000115.3900X(10,7)1.00000082.43700X(11,5)1.00000032.69600X(12,1)1.0000000.000000X(13,6)1.0000005.000000X(14,2)1.0000000.000000X(15,8)1.00000047.

15、51800X(16,3)1.0000000.000000由于該問題中各平臺(tái)警察同時(shí)出發(fā)，對(duì)進(jìn)出該區(qū)的 13 條要道進(jìn)行快速封鎖，即要 找出最優(yōu)解中出發(fā)到相應(yīng)節(jié)點(diǎn)的最長(zhǎng)路程， 該平臺(tái)巡警到達(dá)節(jié)點(diǎn)所用的時(shí)間就為封鎖要 道所需的時(shí)間。根據(jù)求出的最優(yōu)分配方案，若某一平臺(tái)巡警 i 所要到達(dá)的要道途徑其他 平臺(tái) j ，則平臺(tái)巡警 j 應(yīng)前往平臺(tái)巡警 i 本應(yīng)前往的節(jié)點(diǎn)，這樣便可大幅度減少分配方 案中平臺(tái)巡警到被分配的節(jié)點(diǎn)的最長(zhǎng)距離，即可減少封鎖要道所需的時(shí)間。根據(jù)A 區(qū)圖結(jié)合以得出的最優(yōu)分配方案調(diào)節(jié)部分平臺(tái)巡警分配的節(jié)點(diǎn)即可很容易的求出該區(qū)交警服務(wù)平臺(tái)警力合理的調(diào)度方案 最短的調(diào)度方案為：巡警平臺(tái)序號(hào)路口

16、24578916141011121315序號(hào)38624829301614211212242428則該方案的最長(zhǎng)路程為交巡警平臺(tái) 7 到路口 29，則該方案封鎖 13 條交通要道所需 的時(shí)間為 8.0155 分鐘。具體調(diào)度路線如下圖：5.1.3根據(jù)第一小問的分區(qū)，令各轄區(qū)序列號(hào)即為平臺(tái)巡警的標(biāo)號(hào)。借助 excle 工具計(jì)算 可知，轄區(qū)序號(hào)為 15,2,7,20 四個(gè)交巡警平臺(tái)的總工作量和平均出警時(shí)間遠(yuǎn)高于所有轄 區(qū)的平均值。故需要在這些轄區(qū)內(nèi)建立新的平臺(tái)。隨后利用 matlab 列舉出了轄區(qū)內(nèi)所有設(shè)置交巡警平臺(tái)的情況，并通過比較其出警 時(shí)間及工作量找出了最優(yōu)的交巡警平臺(tái)的設(shè)置方案。 其最優(yōu)位置分

17、別設(shè)在 48,43,88,29 同時(shí)將得出的新表與舊表進(jìn)行了比較如下表所示。表一：平均出警時(shí)間轄區(qū)序列號(hào)平均出警時(shí)間轄區(qū)序列號(hào)0.09150.0229500805550.0670.0248983769810.0620.044313771450.06200.01880022左表為未添加平臺(tái)前各轄區(qū)平均出570.0516警時(shí)間以及總平均出警時(shí)間0.05166765右表為添加平臺(tái)后各轄區(qū)平均出警676513時(shí)間以及總平均出警時(shí)間130.04由這兩個(gè)表可看出添加平臺(tái)后明顯0.045138總平均出警時(shí)間減少51380.0330.033784878480.0350.0357167160.0390.0394

18、26242620.0340.034227222720.02120.0212981598150.02110.0211738873880.0210.0216996990.01180.01187997990.01170.0117641564150.01190.0119641564150.0180.01855015501表二：各轄區(qū)平均工作總量轄區(qū)序號(hào)各轄區(qū)平均工作總量轄區(qū)序號(hào)0.4719310.03162295530.4290720.3504343670.3937820.24139883070.3316550.3316555左表為未添加平臺(tái)前各轄區(qū)平5均工作總量以及總平均工作時(shí)間0.310137右表

19、為添加平臺(tái)后各轄區(qū)平均0.15423489工作總量以及總平均工作總量0.296111由這兩個(gè)表可看出添加平臺(tái)后0.296111313明顯總平均出工作總量減少10.2823410.282341330.2090190.209019550.2041340.204134990.1949530.1949530.1622610.16226167670.1085310.10853188880.0954010.09540128280.0856210.08562178780.0798210.07982111110.0758280.075828660.0381810.0381819999Spss所出結(jié)果（ 1，3

20、 列分別為優(yōu)化前平均出警時(shí)間及平均工作總量數(shù)據(jù)， 2，4 列為優(yōu) 化后數(shù)據(jù) ）:首先通過 matlab 在轄區(qū)內(nèi)找出各新設(shè)平臺(tái)到路口的距離， 然后借助 excel 求出新的 總工作量和平均出警時(shí)間，并找出最優(yōu)新交巡警平臺(tái)5.2 問題二模型的建立和求解5.2.1我們參考了第一問中 A 區(qū)的分析思路，分別對(duì)其他五個(gè)區(qū)進(jìn)行分析，同樣求出了距 離矩陣 L，鄰接矩陣 D，（程序 4）任意兩點(diǎn)間最短路徑矩陣 NL，求解距離交巡警平臺(tái)最 短距離矩陣。然后利用 excel 表，進(jìn)行數(shù)據(jù)處理，得到出警時(shí)間及工作總量。最后利用 spss 軟件分析出 B，C，D，E，F(xiàn) 這五區(qū)的標(biāo)準(zhǔn)差，并與上一問中優(yōu)化過的 A區(qū)的

21、標(biāo)準(zhǔn)差 進(jìn)行比較，發(fā)現(xiàn) C,E,F 三個(gè)城區(qū)是交巡警服務(wù)平臺(tái)是指明顯不合理的城區(qū)，應(yīng)該進(jìn)行優(yōu)化，增加新的交巡警服務(wù)平臺(tái)到工作總量最長(zhǎng)或者離交巡警服務(wù)平臺(tái)較遠(yuǎn)的點(diǎn)表一： B區(qū)路口到最新交巡警平臺(tái)的最短距離路程序號(hào)出警時(shí)間案發(fā)率工作量29.8641012.98641.16.5700823.2871022.32870.94.1916619.6471031.96470.51.964728.6271542.86270.63.4352428.8041552.88040.74.0325621.7551562.17551.14.7861表二： C區(qū)路口到最近交巡警平臺(tái)的距離路程序號(hào)出警時(shí)間案發(fā)率工作量24.1

22、661822.41662.411.5996838.211833.8211.29.170414.081841.4081.43.942454.5833175.45830.66.5499645.0113184.50111.19.9024233.53193.351.49.38表三： D區(qū)路口到交巡警平臺(tái)的最近距離路程序號(hào)出警時(shí)間案發(fā)率工作量111.0732911.1070.4246.7309118.4633011.8460.1280.655490.9733319.09730.6165.521741.853694.1851.235.0284578.0853707.80851.2121.945373.61

23、33717.36131.5108.3775表四： E區(qū)路口到交巡警平臺(tái)的最近距離路程序號(hào)出警時(shí)間案發(fā)率工作量191.0538719.1051.1730.0021125.2538812.5250.8313.7513144.1238914.4120.2415.411539.9834713.99831.631.9728115.6524721.56521.84.89970214.4224731.44221.84.15988239.8784743.98781.631.8051表五： F 區(qū)路口到交巡警平臺(tái)的最近距離路程序號(hào)出警時(shí)間案發(fā)率工作量37.3664863.73661.427.9243638.05

24、34873.80531.128.9606225.4954882.54951.512.99997.07115800.707111.41.000009104218.9745811.8974165.7745826.57740.4所以 C,E,F 的交巡警服務(wù)平臺(tái)不合理， 應(yīng)該在其工作量總和較大的地方或者是離交 巡警服務(wù)平臺(tái)很遠(yuǎn)的路口設(shè)置新的交巡警服務(wù)平臺(tái)。5.2.2根據(jù)題目要求，首先利用 matlab 程序(程序 5)建立以 P點(diǎn)為圓心建立一個(gè) 3 分鐘 圈，即半徑為 30mm。然后建立半徑逐次增加 10mm的同心圓 , 定每個(gè)時(shí)間段嫌疑犯的逃逸 范圍(因?yàn)槿我鈨牲c(diǎn)間的路程大于等于兩點(diǎn)間的距離，所以

25、在某時(shí)間內(nèi)嫌疑犯必定在對(duì) 應(yīng)的時(shí)間圈內(nèi))，從而方便對(duì)其進(jìn)行圍堵，通過這種算法我們給出了圍堵匪徒的近似最最優(yōu)圍堵方案如下圖：六、模型的評(píng)價(jià)6.1 模型的優(yōu)點(diǎn)本文采用了 matlab 的繪圖方法在新的簡(jiǎn)圖上明確標(biāo)明了各路口和交巡警服務(wù)平臺(tái) 的序號(hào)，利用傳統(tǒng)的 Floyd 算法建立了任意兩點(diǎn)間的最短距離矩陣，從而劃分了每個(gè)交 巡警服務(wù)平臺(tái)的管轄范圍，結(jié)果準(zhǔn)確。并在簡(jiǎn)圖上明確標(biāo)明了各轄區(qū)，形象具體。將快 速封鎖路口的合理方案轉(zhuǎn)化為指派模型，運(yùn)用 lingo 求出近似最優(yōu)解。使用 spss 軟件 對(duì)工作量總和進(jìn)行了定性的比較。在第二問中創(chuàng)新使用時(shí)間圈法，準(zhǔn)確預(yù)測(cè)了嫌疑犯各 個(gè)時(shí)段的逃跑范圍，并可及時(shí)預(yù)測(cè)

26、到各點(diǎn)警察與嫌疑犯的到達(dá)次序，為追堵行動(dòng)提供有 力支持。6.2 推廣與不足在解決一些追及問題或者尋找最優(yōu)路徑時(shí)， 通過時(shí)間圈法可以快速有效的得到解決。 由于計(jì)算量問題，未能給出一個(gè)很好的解決新交巡警服務(wù)平臺(tái)設(shè)置點(diǎn)問題的方法。七、參考文獻(xiàn)1 肖華永, 實(shí)用數(shù)學(xué)建模與軟件應(yīng)用 ,西北工業(yè)大學(xué)出版社 ,2008 年11月第1版2 西北工業(yè)大學(xué)數(shù)學(xué)建模指導(dǎo)委員會(huì) , 數(shù)學(xué)建模簡(jiǎn)明教程 ,高等教育出版社 ,2008 年 9 月第 1 版3 姜啟源等 , 數(shù)學(xué)模型 , 高等教育出版社 ,2010 年 11 月第 22次印刷 附錄： 程序 1： floyd 算法：n=92D=data;path=zeros(

27、n,n);fori=1:nforj=1:nifD(i,j)=inf path(i,j)=j;end end end fork=1:n fori=1:n forj=1:n ifD(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k) end end end end程序 2： (1)劃分轄區(qū)程序： fori=1:1:20 forj=21:1:92 ifD(j,i)>=30D(j,i)=inf end end end k=1 form=21:1:92 B(k,1)=D(m,1)B(k,2)=1 B(k,3)=m forn

28、=1:1:19 t=21-n ifD(m,t-1)>D(m,t) B(k,1)=D(m,t) B(k,2)=t end ifD(m,t-1)<D(m,t) t=t-1B(k,1)=D(m,t) B(k,2)=t end end k=k+1 end (2)篩選出矩陣中每行最小的元素 fori=1:1:97 k(i)=infendfori=12:1:108forj=1:1:11m=i-11ifk(m)>=F(i,j)k(m)=F(i,j)endendend程序 3：lingo 優(yōu)化模型的程序：model:sets:p/1.20/;r/1.13/;assign(p,r):c,x;e

29、ndsetsdata:c=222.41,160.29,92.868,192.94,210.96,225.02,228.98,190.01,195.16,120.84 ,58.81,118.5,48.852,204.68,141.3,73.881,173.95,191.98,206.03,211.25,172.29,177.44,103.11,39 .822,103.1,60.351,183.57,127.67,60.256,160.32,178.35,192.41,190.14,151.17,156.32,81.996,6 0.939,81.979,43.934,218.93,150.09,8

30、2.669,182.74,200.76,214.82,225.5,161.55,154.63,80.307,48 .61,73.236,3.5,174.88,129.7,62.279,162.35,176.1,190.15,181.45,113.07,106.15,31.829,94. 211,24.758,51.827,175.19,130,62.585,162.65,176.4,190.46,181.76,113.37,106.46,32.135,94.51 7,25.064,53.392,147.52,109.07,41.648,141.72,148.73,162.78,154.09,8

31、5.702,80.155,5.831,73 .58,12.902,79.193,140.97,94.339,26.922,126.99,142.18,156.24,147.54,102.28,104.93,30.608,58.854,30.995,86.773,130.15,82.742,15.325,115.39,131.36,145.42,136.72,97.757,107.24,33.245,47.257,40.316,93.367,75.866,127.76,68.475,95.108,77.08,91.135,82.437,141.95,151.43,77.436,10 0.41,8

32、4.507,146.52,37.914,83.374,112.86,50.724,32.696,46.751,38.053,186.33,195.82,121.82,1 44.79,128.89,190.9,0,119.5,144.34,86.854,68.826,64.771,35.917,217.81,227.3,153.3,176.27,16 0.37,222.38,59.771,59.733,127.15,27.083,9.0554,5,23.854,228.08,237.57,163.57,161.21 ,170.64,213.32,119.5,0,67.417,32.65,50.6

33、78,64.733,83.587,179.41,188.9,114.9,101.48,121 .97,153.59170.34,131.89,64.474,164.54,171.55,185.61,176.91,47.518,57.005,44.015,96.405,51.086,117.38,144.39,67.417,0,100.07,118.1,132.15,150.96,111.99,121.48,47.48,34.059,54.551,86.169,217.87,149.03,81.616,181.68,199.71,213.77,224.44,185.48,194.97,120.9

34、7,47.557,128.04,78.206,242.52,185.15,117.73,217.8,235.82,249.88,249.09,210.12,215.27,140.95,83 .67,136.99,67.344,225.51,169.62,102.2,202.27,220.29,234.35,232.08,193.12,198.26,123.94,76 .393,119.99,50.337,269.5,212.13,144.71,244.78,262.81,276.87,276.07,229.38,222.47,148.15,110.66,141.07,64.489;enddat

35、amin=sum(assign(i,j):c(i,j)*x(i,j);for(p(i):sum(r(j):x(i,j)<=1);for(r(j):sum(p(i):x(i,j)>=1);for(assign(i,j):bin(x(i,j);end6. 求解最有效的增設(shè)平臺(tái)地點(diǎn)：A15=30,47;30,48;30,61;47,30;47,48;47,61;48,30;48,47;48,61;A2=43,44;43,70;43,72;44,39;44,40;44,43;44,70;44,72;70,39;70,40;70,43;7 0,44;70,72;72,39;72,40;72,

36、43;72,44;72,70;A20=84,85;84,86;84,87;84,88;84,89;84,90;84,91;84,92;85,84;85,86;85,87;85,88;85,89;85,90;85,91;85,92;86,84;86,85;86,87;86,88;86,89;86,90;86,91;86,92;87,84;87,85;87,86;87,88;87,89;87,90;87,91;87,92;88,84;88,85;88,86;88,87;88,89;88,90;88,91;88,92;89,84;89,85;89,86;89,87;89,88;89,90;89,91

37、;89,92;90,84;90,85;90,86;90,87;90,88;90,89;90,91;90,92;91,84;91,85;91,86;91,87;91,88;91,89;91,90;91,92;92,84;92,85;92,86;92,87;92,88;92,89;92,90;92,91;A7=30,47;30,48;30,61;47,30;47,48;47,61;48,30;48,47;48,61;61,30;61,47;61,48;fori=1:1:9A15(i,3)=D(A15(i,1),A15(i,2)endfori=1:1:30A2(i,3)=D(A2(i,1),A2(i

38、,2)endfori=1:1:72A20(i,3)=D(A20(i,1),A20(i,2)endfori=1:1:12A7(i,3)=D(A7(i,1),A7(i,2)end程序 4：(1)求全圖的鄰邊矩陣 DD=forj=1:1:582form=1:1:928if(s(m,1)=j)D(s(m,2),j)=1endendfori=1:1:582forj=1:1:582ifD(i,j)=1D(j,i)=D(i,j);endendend(2)求B區(qū)的相鄰點(diǎn)距離矩陣( D為鄰接矩陣， LB為任意兩點(diǎn)間的路程矩陣)D=LB=for i=93:1:165for j=93:1:165m=i-92n=j-92N(m,n)=LB(m,n)*D(i,j)endend程序 5：k=1:582;, 'MarkerSize', 'MarkerSize'gplot(D(k,k),Coordinates, 'g-*' );hold on; for i=1:1:20 text(Coordinates(i,1),Co