全國數(shù)模競賽

2011高教社杯全國大學生數(shù)學建模競賽承 諾 書我們仔細閱讀了中國大學生數(shù)學建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）： B 我們的參賽報名號為（如果賽區(qū)設置報名號的話）： 所屬學校（請?zhí)顚懲暾娜?杭州電子科技大學 參賽隊員 (打印并簽名) ：1. 費科斌 2. 楊志偉 3. 張佃鵬 指導教師或指導教師組負責人 (打印并簽名)： 數(shù)模組 日期： 年 月 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：2011高教社杯全國大學生數(shù)學建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：交巡警服務平臺的設置與調度摘要為了更好地利用警務資源，需要根據城市的實際情況進行合理的分配，本文研究的就是如何合理地設置交巡警服務平臺、分配各平臺的管轄范圍、調度警務資源等五個問題。針對問題一，首先用Floyd算法求出任意兩點之間最短路徑，然后對每個節(jié)點進行討論，找出離每一路口節(jié)點最近的服務平臺作為該節(jié)點的服務平臺，其次根據每一條路線和路線兩個端點的性質進行了分類討論：如果路線的兩個端點歸同一服務平臺管轄，則這條路線歸該服務平臺管轄；如果端點不歸同一平臺管轄，那么在該條線段太長的情況下，就把該路線平均分給兩個服務平臺管轄；在該線段不長的情況下，就直接把該線段分給其中一個距離較近的平臺管轄。這樣既對節(jié)點又對路線進行了管轄范圍的劃分，最后對模型的合理性進行了分析，有92.5%長度的路線能夠在三分鐘之內到達。針對問題二，要實現(xiàn)A區(qū)13個交通要道快速全部封鎖，必須使要調動的13個服務平臺中所有到達交通要道出口所花時間的最大值最小化，以此為目標建立0-1規(guī)劃，可以求得該最短封鎖時間為8.02分鐘，并進一步在目標值不變的情況下使總調度路程最小化建立0-1規(guī)劃的目標函數(shù)求得最終的調度方案。針對問題三，我們首先對A區(qū)根據各個節(jié)點的最短路徑進行了聚類分析，把A區(qū)四次分成2,3,4,5塊，為了方便計算和求解，根據實際情況人為的對分好類的選址范圍中可能選到的點進行了篩選，對于兩個不同的選址目的，我們將一個作為目標函數(shù)，另一個作為約束條件，從聚類好的每一塊中選擇一個節(jié)點作為新的平臺，建立0-1規(guī)劃，最終求得最合理的方案是再新增加四個服務平臺，分別對應的節(jié)點序號為：29，39，60，87。針對問題四，依照設置服務平臺的原則和任務，首先我們規(guī)定了四個評價指標分別為：距離服務平臺小于3千米的節(jié)點占總節(jié)點的比例；所有節(jié)點距離服務平臺的最長距離；人口密度與服務平臺密度的比例；以及整個區(qū)域的綜合發(fā)案率。我們用問題一的方法分別對六個區(qū)域中這些指標進行了求值，然后基于這四個指標對每個區(qū)域以及全市的服務平臺設置進行了模糊綜合評價，評價結果為較差，最后基于最小頂點覆蓋問題對不合理的地方進行了局部優(yōu)化。針對問題五，根據具體情況我們首先把嫌疑犯的活動限制在少數(shù)的幾個城區(qū)內，然后利用動態(tài)規(guī)劃的思想，將對嫌疑犯的包圍圈逐漸往小縮，根據交警和嫌疑犯所花費的時間進行比較，直到嫌疑犯恰好不能逃出包圍圈的那一刻，停止往小縮，最終得到的包圍圈確定在A,C區(qū)某一小片區(qū)域內。關鍵詞：Floyd算法 0-1規(guī)劃 聚類分析 模糊綜合評判 最小頂點覆蓋一問題重述 “有困難找警察”，是家喻戶曉的一句流行語。警察肩負著刑事執(zhí)法、治安管理、交通管理、服務群眾四大職能。為了更有效地貫徹實施這些職能，需要在市區(qū)的一些交通要道和重要部位設置交巡警服務平臺。每個交巡警服務平臺的職能和警力配備基本相同。由于警務資源是有限的，如何根據城市的實際情況與需求合理地設置交巡警服務平臺、分配各平臺的管轄范圍、調度警務資源是警務部門面臨的一個實際課題。試就某市設置交巡警服務平臺的相關情況，建立數(shù)學模型分析研究下面的問題：（1）附件1中的附圖1給出了該市中心城區(qū)A的交通網絡和現(xiàn)有的20個交巡警服務平臺的設置情況示意圖，相關的數(shù)據信息見附件2。請為各交巡警服務平臺分配管轄范圍，使其在所管轄的范圍內出現(xiàn)突發(fā)事件時，盡量能在3分鐘內有交巡警（警車的時速為60km/h）到達事發(fā)地。對于重大突發(fā)事件，需要調度全區(qū)20個交巡警服務平臺的警力資源，對進出該區(qū)的13條交通要道實現(xiàn)快速全封鎖。實際中一個平臺的警力最多封鎖一個路口，請給出該區(qū)交巡警服務平臺警力合理的調度方案。根據現(xiàn)有交巡警服務平臺的工作量不均衡和有些地方出警時間過長的實際情況，擬在該區(qū)內再增加2至5個平臺，請確定需要增加平臺的具體個數(shù)和位置。（2）針對全市（主城六區(qū)A，B，C，D，E，F(xiàn)）的具體情況，按照設置交巡警服務平臺的原則和任務，分析研究該市現(xiàn)有交巡警服務平臺設置方案（參見附件）的合理性。如果有明顯不合理，請給出解決方案。如果該市地點P（第32個節(jié)點）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調度全市交巡警服務平臺警力資源的最佳圍堵方案。二.模型的假設（1）假設發(fā)生突發(fā)狀況時，警員能夠以60km/h的平均速度趕往現(xiàn)場。（2）假設各個交巡警服務平臺的職能和警力配備基本相同。（3）假設線段上的案發(fā)率可以用端點上的案發(fā)率進行表示。（4）假設在逮捕犯罪嫌疑人時，犯罪嫌疑人的逃跑速度也為60km/h。（5）假設同一個交巡警服務平臺同時不能兼顧兩個節(jié)點。三城區(qū)A交巡警服務平臺優(yōu)化方案的設計3.1 符號說明任意一條路線的長度任意兩個交通路口節(jié)點之間的最短路徑原有的20個交巡警服務平臺對應的140條路線服務平臺在三分鐘之內能夠到達出事地點的滿意度能夠在三分鐘之內到出事地點所有線路總長所有線路總長在分配服務平臺是對應的選址0-1變量在進行對13個交通要道封鎖時，所有路線中最長路線全部封鎖各個要道所花費的最短時間警車行駛的平均速度全部封鎖好各個要道所走的總路線長度第個節(jié)點對應的發(fā)案率第個服務平臺對應的總的工作量各個服務平臺的總工作量的方差在選址時決定是否要選擇的0-1變量3.2 各交巡警服務平臺管轄范圍的分配3.2.1 問題分析要想讓各交巡警服務平臺使其在所管轄的范圍內出現(xiàn)突發(fā)事件時，盡量能在3分鐘內有交巡警到達事發(fā)地，我們認為是在不考慮各個交巡警服務平臺工作量的情況下，使A區(qū)每條路線上的點和各個交通路口節(jié)點都可以在20個服務平臺內找到路線離自己最短的服務平臺，這樣我們分別對各條路線和各交通路口節(jié)點進行了分析和討論。對于各個交通路口節(jié)點來說，為了找到任意兩個節(jié)點之間的最短路線，我們首先根據已知數(shù)據求出了圖中相鄰兩個節(jié)點之間各個路線的長度，然后Floyd算法就可以求出任意兩個交通路口節(jié)點的最短路線，最后對每一個交通路口節(jié)點到各個服務平臺最短路線求最小值，這樣就可以得出每個交通路口節(jié)點對應的平臺管轄范圍以及對應平臺的巡警到該節(jié)點所用的最短時間。對于各條路線上的點來說，根據實際情況我們盡量想把一條路線分在同一個管轄范圍之內，因此我們對140條路線中每條路線的兩個路口節(jié)點進行討論，如果這兩個路口節(jié)點在同一管轄范圍之內，這條路線就在該管轄范圍內；如果這兩個路口節(jié)點在不同的管轄范圍內，要再次進行分情況討論，根據路線的長短以及該條路線的節(jié)點是否就是服務平臺進行討論，最后確定是否要把這條路線分開進行管轄。最后我們對結果進行了驗證，對于所有能在3分鐘之內到達的路線的長度和能再3分鐘之內達到的交通節(jié)點的個數(shù)在整體中所占的比例進行了分析，對結果進行了合理的驗證。3.2.2 基于Floyd算法每個服務平臺所管轄的交通節(jié)點的求解（1）每兩點之間距離矩陣的建立首先建立一個距離矩陣，取任意兩個節(jié)點，如果這兩個節(jié)點有且僅有一條路線連接，則就等于該條路線的長度，即：否則認為該兩點的距離為，即：如果，則該兩點的距離為0，即：最后代入數(shù)據編程（程序見附錄）可求得該最短路徑矩陣，見附錄。（2）用Floyd算法求解。Floyd是一種動態(tài)規(guī)劃算法，對于每一對頂點 i和j，看看是否存在一個頂點i使得從i到k再到j比己知的路徑更短，如果是最短就更新它，最后把所有的可能的點都找完，就可以找到點i到點j的最短路徑path（i，j），其狀態(tài)轉移方程如下： 這樣根據其算法流程用matlab軟件編程（程序見附錄）可以求得這92交通節(jié)點中每兩個點的最短路線矩陣path，見附錄。在以上求出任意兩個交通節(jié)點最短距離的基礎上，可以在20個交巡警服務平臺中找到離每個交通節(jié)點最近的交巡警服務平臺。求公式如下：根據上式可以求得對于第i個交通節(jié)點都有一個服務平臺與其相對應。這樣就求出了每一個交巡警服務平臺所管轄的交通節(jié)點的所有數(shù)目如下表：交巡警服務平臺序號 各個服務平臺所管轄的交通節(jié)點序號11676869717374757678223940434470723354556566445760626364554950515253565859667730324748618833469931343545101011112627121225131321222324141415152829161636373817174142181880818283191977792020848586878889909192表 3-2-1 每個平臺所管轄的交通節(jié)點序號3.2.3 每個交巡警服務平臺所管轄的交通路線的求解對于各條路線上的點來說，根據實際情況，我們盡量想把一條路線分在同一個交巡警服務平臺管轄范圍之內，但是有些路線會太長，有些路線還會直接與交巡警服務平臺相連接，針對這些情況，我們不能把一條路線分在同一個服務平臺的管轄范圍之內，因此我們按照140條路線中每條路線的兩個交通路口節(jié)點的情況不同進行了分類討論：（1） 如果某條路線兩個交通路口節(jié)點A,B在同一交巡警服務平臺M管轄范圍之內，如下圖：MmA1B 圖 3-2-1這樣我們就把線段AB劃分在M交巡警服務平臺管轄范圍之內。（2）如果某條路線的兩個交通路口節(jié)點A,B在不同的兩個交巡警服務平臺管轄 范圍之內，如下圖：MmA1BNB圖 3-2-2其中 A節(jié)點屬于M服務平臺管轄，B節(jié)點屬于N服務平臺管轄，在這種情況下，我們首先要判斷一下這條線路的長度，如果太長，則不能歸同一個服務平臺管轄，因為線路太長對其行駛時間的影響很大；反之，我們就可以把歸同一服務平臺管轄，根據實際情況，我們對線段的長度按照一下規(guī)則進行分類討論：在放在一個服務平臺范圍內管轄時，我們比較一下兩個節(jié)點離其對應服務平臺的最短路徑的大小進行判斷來確定歸那個服務平臺管理：（3）還有一種情況是線段AB的兩個端點中本來自身就是服務平臺。如下圖： MMA1BN 圖3-2-3 針對這種情況，我們同樣要把線段AB平均分為兩段分在M,N兩個不同的服務平臺管轄范圍之內。根據以上算法和思路，我們用matlab軟件編程（程序見附錄），可以求得每一個交巡警服務平臺所單獨管轄的各條路線的序號，如下表：交巡警服務平臺序號各個平臺所管轄的交通線路的序號11,2，197,99,100,102,103,104,105,106,107,110,111,112,114,115,116,117,12023,60,61,64,65,66,101,10935,67,83,85,96,9847,84,86,87,88,89,91,92,93,9558，9,71,75,76,77,78,79,80,81,82,90610,72711, 21,44,45,46,57,73,74814,48,49,68,69,70915,47,50,51,52,5410381117,18,37,391219,36,401332,33,34,3514201522,41,421624,53,55,56,581725,26,62,1828,29,113,124,125,126,1271930,118,119,121,1222031，128,129,130,131,132,133,134,135,137,138,139,140表3-2-2 每個平臺單獨管轄的交通路線序號并得出有些路線平均分開歸兩個交巡警服務平臺管轄的情況如下表：由兩個平臺公共管轄的路線序號46131621232743596394這條路線對應的兩個服務平臺的序號3 94 28 910 915 716 1417 1815 716 1717 204 20表3-2-3 由兩個服務平臺共同管轄的路線序號3.2.4 結果的分析和比較在解決該問題時，我們的最終目標是在為了讓交巡警服務平臺能盡量在三分鐘之內到達事發(fā)地，為此，我們從各個方面對所求結果進行了驗證和分析：（1）首先我們對所有到達時間超過三分鐘的道路上的最長達到時間進行了統(tǒng)計（程序見附錄）如下表：道路序號5786420174023948482到達對應服務平臺所需要的最長時間（分鐘）3.04 3.11 3.22 3.26 3.27 3.30 3.37 3.45 3.45 3.45 道路序號3836587056925963643到達對應服務平臺所需要的最長時間（分鐘）3.54 3.59 3.71 3.87 4.11 5.21 5.41 5.92 5.96 9.42 表3-2-3 最長達到時間的統(tǒng)計結果由以上表格中的數(shù)據可以發(fā)現(xiàn)，在140條路線中，交巡警力到達的最大時間超過3分鐘的只有20條路線，而且這些時間都在3分鐘附近，所以以上數(shù)據可以發(fā)現(xiàn)都夠盡量滿足三分鐘內到達。（2）然后為了驗證結果做的是否滿意，我們規(guī)定了滿意度的公式為：即：通過matlab軟件編程（程序見附錄四）可以求得： 將其帶入得： 有上述分析可知，有92.5%的線路可以滿足在三分鐘之內到達，所以結果基本符合要求，滿意度很高，這樣也同樣驗證了我們解題方案的合理性。（3）在以上結果的基礎上并結合每個點的案發(fā)率的大小，在超過3分鐘到達的線路上，我們可以人工調整調度方案，犯罪嫌疑不會又逃脫的可能性，所以即使超出三分鐘也關系不是很大。3.3 根據0-1整數(shù)規(guī)劃制定服務平臺警力的調度方案3.3.1 問題分析為了實現(xiàn)A區(qū)13個交通要道快速全部封鎖，我們需要從20個交巡警服務平臺中調動13個服務平臺的警力分別去封鎖A區(qū)交通要道的出口，而且使13個平臺中所有到達交通要道出口所花時間的最大值最小化，這樣可以建立目標函數(shù)用0-1整數(shù)規(guī)劃解決該問題，并用lingo軟件編程求出要花費最長的時間。但是在該所花費的最長時間的前提下，同樣還有很多種調動方案，為了盡快使每個路口都要交警到達，同時盡量節(jié)約時間和成本，我們需要讓所有服務平臺到達對應的交通要道出口的總時間最短，這樣既可以進一步減小嫌疑目標逃離的可能性，同時減少了成本代價的付出。同樣以這個總時間最小化為目標函數(shù)，建立0-1整數(shù)規(guī)劃方程，用lingo軟件可以求出最終的調度方案。3.3.2 各個平臺所花時間的最大值最小化模型的建立和求解我們所要解決的問題是從20個服務平臺中選擇13個服務平臺進行調度分配到13個交通要道出口處，為了盡快實現(xiàn)全部交通要道的封鎖目的，我們讓服務平臺警力到達每個交通要道出口的時間中的最大值最小化，這樣就可以實現(xiàn)我們的目的。設表示的內容如下：由于每個服務平臺行駛的速度是一定的，因此我們可以把關于時間的目標函數(shù)轉化成關于所有路程中最大值最小化的問題，這樣我們可以建立目標函數(shù)如下： 在以上目標函數(shù)建立的基礎上，我們用lingo軟件編程（程序見附錄）可以求得：再將代入公式： 可求得實現(xiàn)全部封鎖各個交通要道所用的最短時間為：3.3.3 在最短時間封鎖要道的基礎上調度方案的進一步優(yōu)化在上述所求出實現(xiàn)全部封鎖各個要道所用最短時間的情況下，同樣還存在很多種調動方案，為了盡快使每個路口都有交警到達，我們需要讓所有服務平臺到達對應的交通要道的總時間最短，這樣同時可以減少成本的浪費和進一步減小嫌疑目標逃離的可能性，同樣設：以這個總時間最小化為目標函數(shù)，建立0-1整數(shù)規(guī)劃方程如下：用lingo軟件編程（程序見附錄）求得實現(xiàn)全部封鎖各個交通要道，各個交巡警服務平臺所花費的時間和為：并很容易得出最終的調度方案如下表：交通要道序出口號12345678910111213交通要道所對應的路口節(jié)點序號12141621222324282930383962對應的調度服務平臺序號12169141013111578254表4-3-1 交巡警服務平臺警力進行快速全城封鎖合理的調度方案3.4 基于聚類分析的新服務平臺的選址優(yōu)化方案3.4.1 問題分析如果要再選擇2到5個節(jié)點作為新的交巡警服務平臺，這屬于一個選址優(yōu)化問題，由于整個A區(qū)的節(jié)點太多，這樣給選址問題帶來了許多不便，為了使問題變的容易一點，我們對A區(qū)中所有節(jié)點進行了歐氏距離聚類分析，聚類的依據是每兩個節(jié)點之間的最短路徑。這樣根據不同情況，可以對A區(qū)進行不同數(shù)目的分塊。要選擇若干個節(jié)點作為新的交巡警服務平臺，就把A區(qū)分為若干個塊，這樣我們只需要從每一塊中選擇其中的一個節(jié)點就可以了。但是這樣聚類分塊以后，仍然會出現(xiàn)節(jié)點太多的情況，然后我們根據實際情況，一些顯而易見不會作為選址點的節(jié)點直接人為排除掉，這樣就大大減小了選擇的范圍，解決起來很方便。我們的最終目標是希望交巡警服務平臺的工作量盡量均衡和出警時間盡量短，我們把出警時間作為約束條件，把工作量盡量均衡作為目標函數(shù)，同時工作量可以認為是每個區(qū)域內所管轄的節(jié)點對應的發(fā)案率的和，使各個交巡警服務平臺的工作量的方差最小化，建立0-1整數(shù)規(guī)劃，進行求解，針對要選擇2到5個點分別進行求解，最后比較結果進行分析，決定要再選擇幾個交通服務平臺。3.4.2 基于最短距離聚類法對A區(qū)進行分塊聚類分析需要依據節(jié)點的相似性能進行分塊，根據實際情況，我們考慮到了每兩個節(jié)點間最短路徑，把離的比較近的一些點分在一塊，這樣先將92個節(jié)點各自分為一類，計算它們之間的最短路徑長度，選擇長度最小的兩個節(jié)點歸為新的一類，再計算這個新類與其它節(jié)點的距離，選擇距離小的兩個節(jié)點（或兩個新類）歸為新的一類，每次合并縮小一個以上的類，直到所有樣本都劃入一個新類為止。這里規(guī)定兩點間的距離，兩類間的距離。步驟如下：（1） 看各數(shù)據量綱是否一致，如果不一致要對數(shù)據進行正規(guī)化處理，并選擇一種計算距離的方法，我們這里選擇的是歐氏距離法。（2） 計算各樣本之間的距離，并記在分類距離對稱表中。（3） 選擇上述對稱表中的最短距離，設為，則將合成一個新類記為： （4） 計算新類與其它類之間的距離，并將第p，q行和列刪掉，作為一個新的對稱表。（5） 重復以上步驟，直到最后只剩下要實現(xiàn)的最終分類結果為止，并作聚類圖?；谝陨纤悸泛土鞒?，我們用matlab軟件進行了編程（程序見附錄），分別得出在把A區(qū)分為2,3,4,5塊的情況下，各類中包含節(jié)點的數(shù)目和序號，用圖表示如下：A區(qū)10,11,12,13,14,15,21,22, 23,24,25,26 27,28,29 1,2,3,4,5,6,7,8,9,16,17,18,19,20,30,31,90,91,92圖3-4-1 將A區(qū)分為兩類的情況A區(qū)1,2,3,4,5,7,8,9,16,17,18,19,20,30,.37,41,60,62,91,926,31,38,39, 40,6110,11,12,13, 14,15,21,22, 23,24,25,26 27,28,29 圖3-4-2 將A區(qū)分為三類的情況A區(qū)7,8,9，16,30，32,33,34,35,36,37,45,46,47,48,926,31,38,39, 40,6110,11,12,13, 14,15,21,22, 23,24,25,26 27,28,29 1,5,17,20,41,44, 49,61,62,91圖3-4-3 將A區(qū)分為四類的情況A區(qū)7,8,9,16,30,32,3334,35,3637,45,4647,486,31,38,39,40,6110,11,1213,14,1521,22,2324,25,26 27,28,29 1,2,3,4,1720,31,384144,5455,59,62,915,49,50,51,52,5356,57,58,60,92圖3-4-4 將A區(qū)分為五類的情況3.4.3 人為減小選址的范圍由于選址范圍過大，導致編程很難實現(xiàn)，就難以做到很精確的選址。我們采取人為的方法對選址范圍進行了調整。調整方法具體如下：（1）從地圖上很容易發(fā)現(xiàn)有些點距離已有的交巡警服務平臺很近，這些點我們就認為是歸原有的交巡警服務平臺管轄，所以把這些點從選址范圍內排除掉。我們給予的條件是把那些和已有的服務平臺最短路徑小于1.5千米的節(jié)點都排除掉，即如果第j個節(jié)點到原有的第i個服務平臺的距離：就把對應第j個節(jié)點排除掉，這樣就減小了選址范圍。（2）在地圖上還可以找到一些處于出口位置的節(jié)點，如果在這些節(jié)點設置成服務平臺的話，周圍的節(jié)點太少，這樣其工作量就很低，不符合實際要求，因此我們同樣把這些點也排除掉。經過以上重重篩選后，選址范圍大大減少了，選址也變的容易了。3.4.4 新增服務平臺的0-1整數(shù)規(guī)劃選址經過上述聚類分析和人為減小選址范圍的情況下，我們就可以建立選址模型，對目標進行優(yōu)化。我們增加交巡警服務平臺的主要目的，是為了解決各個交巡警服務平臺工作量不均衡和有些地方出警時間過長的實際存在的問題。這是一個多目標優(yōu)化問題，解決起來不是很方便，因此我們把其中一個目的作為目標函數(shù)，把另一個目的作為約束條件，這樣就把復雜的多目標優(yōu)化選址問題轉化為簡單的單目標優(yōu)化選址問題。(1)目標函數(shù)的確定我們把工作量盡量均衡作為目標函數(shù)，首先考慮到影響工作量的因數(shù)既有所管轄范圍內每條線路的長度，也有每條線路對應節(jié)點發(fā)案率的大小，這兩個因素都與工作量成正相關關系。我們這兩個因素的乘積作為每條線路的工作量。即第i個節(jié)點到第j個服務平臺的工作量大小可以用公式表示如下（其中表示第i個節(jié)點的發(fā)案率）：對于第j個服務平臺的總工作量可以表示為在它管轄范圍之內的工作量之和：公式如下： 為了盡量使各個服務平臺的總工作量均衡，我們可以用方差表示目標函數(shù)，方差越小，說明各個服務平臺的總工作量越均衡。方差可以如下表示：這樣就可以確定目標函數(shù)了。(2)另一個目標變?yōu)榧s束條件 對于另一個目標是使各個平臺出警時間盡量短，我們把出警時間作為一個約束條件，對于每一個平臺到其每一個管轄節(jié)點的出警時間都應該在4分鐘之內，也就是轉成路程的話就是在4千米之內即：這樣就成功的把多目標問題轉化成了單目標優(yōu)化問題。(3)建立0-1規(guī)劃進行求解 在對各種情況分類分好以后，設在每個選址范圍內共有n個點供選擇，其中k個點是原有的服務平臺，我們需要從余下的n-k個點中選取一個點使目標函數(shù)最優(yōu)。建立0-1規(guī)劃如下：根據以上目標函數(shù)和約束條件可以用lingo軟件編程（程序見附錄）求得結果（見附錄）。最后對選擇的2,3,4,5個地址分別運行程序，最終求得在選擇四個新服務平臺的情況下，目標已經很優(yōu)化了。下面是我們所選擇的這四個服務平臺所對應的節(jié)點的序號和坐標如表：新選服務平臺的位置29396087坐標(246,337)(371,333)(369,388)(448,381)表3-4-1 新選交巡警服務平臺的位置我們把所選擇的新的服務平臺標在地圖中如下：注：(1)大的五角星代表新選的服務平臺。(2)小的星號代表各個交通路口節(jié)點。圖3-4-5 新選擇的服務平臺四六區(qū)服務平臺的綜合評價和圍堵問題4.1 符號說明4.2 基于模糊綜合評價對全市六區(qū)服務平臺設置的評價4.2.1 問題分析能夠反應交巡警服務平臺設置是否合理的指標有很多，我們根據實際情況選擇了其中四個指標對其進行評價，這四個指標分別為在管轄范圍內距離服務平臺小于3千米的節(jié)點占總節(jié)點的比例；在管轄范圍內所有節(jié)點距離服務平臺的最長距離；在管轄范圍內的人口密度與服務平臺密度的比例；在管轄范圍內節(jié)點綜合的發(fā)案率。首先根據題目中給的數(shù)據我們可以編程求得這些指標對應的值，然后我們根據各個指標的重要性人為的對這些指標賦予不同的權重，最后用模糊綜合評價的方法對六個區(qū)域服務平臺設置方案進行了各自評價和綜合評價。根據評價的結果可以發(fā)現(xiàn)有些地區(qū)的平臺設置方案明顯不合理，但是對整個區(qū)域進行調整很難，也不是很經濟，所以我們依據最小割集，連通度，最小點覆蓋等方法依次舉例，對不合理的服務平臺設置進行了調整。4.2.2 各個評價指標的計算按照問題一中的解題思路，我們以同樣的方法可以對六個區(qū)域對管轄范圍都進行合理的分配，并用matlab軟件編程可以實現(xiàn)目的，最后求得各指標。(1) 距離服務平臺小于3千米的節(jié)點占總節(jié)點的比例的計算由定義可知：第一指標公式如下： 用matlab軟件進行編程（程序見附錄）可求得結果如下表：區(qū)域ABCDEF0.93480.91780.69480.76920.67960.6296表4-2-1 各區(qū)域指標一的計算結果(2) 所有節(jié)點距離服務平臺的最長距離的計算公式如下： 同樣用matlab軟件編程（程序見附錄）可求得結果如下表：區(qū)域ABCDEF27.686413.399136.089830.863941.248938.8427表4-2-2 各區(qū)域指標二的計算結果(3) 人口密度與服務平臺密度的比例的計算人口密度的計算公式是該區(qū)域的總人口與該區(qū)域總占地面積的比例，公式如下： 服務平臺密度計算公式是總得服務平臺的個數(shù)與總占地面積的比列，公式如下：所以該指標最終計算公式如下：代入數(shù)據求得結果如下表：區(qū)域ABCDEF32.6252.8828.1115.0674.818表4-2-3 各地區(qū)指標三的計算結果(4)節(jié)點綜合發(fā)案率的計算針對第四種指標的計算我們做了這樣的假設，我們把某路口的發(fā)案率和該路口附近地區(qū)的發(fā)案率都歸結到該路口處，以下圖為例，說明一下我們的計算方法:1234圖4-2-1圖中四個圓為四個路口且第三路口只和這三個圓直接相連，每兩個圓之間的線段為三條道路，它們的長度分別用，來表示，第個節(jié)點的發(fā)案率用來表示，為了方便計算，我們把所有線段上的發(fā)案率都歸結到一個點上，這樣第三個節(jié)點的平均發(fā)案率我們可以這樣計算： 根據以上表達式，將數(shù)據代入并編程求得結果如下：區(qū)域ABCDEF472812312722081表4-2-4 各地區(qū)指標四的求解結果4.2.3 基于上述四個指標對服務平臺設置的模糊綜合評價(1) 各指標的正規(guī)化處理 由于在以上求出的各個評價指標的量綱不一樣，因此在這里我們對各指標進行了正規(guī)劃處理，公式如下：由matlab編程（程序見附錄）計算結果如下表：區(qū)域ABCDEF指標一10.940.210.460.160指標二0.2410.070.1600.03指標三0.0700.0510.450.4指標四0.5410.120.1100.25表4-2-5（2）綜合評價的評價矩陣的確定這些量綱化后的值就可以作為單因素評價的評價結果，例如A區(qū)單因素評價后的結果為：由此可得綜合評價的評價矩陣為：R=（3）綜合評價權重的確定由于A為市區(qū)，所以占得比重應該很大，其它的五個區(qū)域相對較少，所以平均可以進行平均分配，這樣就可以得到評價的權重如下：W=0.5 0.1 0.1 0.1 0.1 0.1（4）進行綜合評價通過權重矩陣W和評價矩陣R的模糊變換得到模糊評判集S的公式如下：其中為模糊合成算子，在四種模糊合成算子中，我們選擇的是算子，因為該算子綜合程度比較強，利用信息比較全，屬于加權平均型的。由上述算子求出了集合如下：S=0.68 0.25 0.23 0.42最后通過對模糊評判向量S的分析作出綜合評論，我們這里采用的是加權平均原則，可表示為：其中k為待定系數(shù)（k=1或k=2），目的使控制較大的所起的作用。如對S=（0.68 0.25 0.23 0.42），評價等級集合為V=很好，一般，較差，差，各等級賦值分別為4,3,2,1，仿照普通加權法的計算公式，有即該市交巡警服務平臺巡邏的情況綜合評價結果為較差，有許多需要解決的地方。4.2.4 基于最小頂點覆蓋定理對市區(qū)進行局部優(yōu)化由上述評價結果可以發(fā)現(xiàn)，該市區(qū)的交巡警分布平臺布置并不是很合理，尤其是地圖上有些局部的服務平臺的設置很不合理。我們選取該地圖上的一部分為例，利用最小頂點覆蓋定理對其進行了局部優(yōu)化。最小頂點覆蓋是指一個頂點能夠覆蓋的范圍越廣越好，我們利用這個思想，認為與一個頂點連接的路線的數(shù)目越多越好，選擇這樣的點作為服務平臺的話，可以使該服務平臺在三分鐘之內可以到達的節(jié)點個數(shù)增加，但是同時我們又要考慮到發(fā)案率的問題，如果覆蓋太多路線的話，其總體發(fā)案率也會提高，這樣無形的增加了服務平臺的工作量。我們選取了C區(qū)中的局部地圖如下：圖4.2.4從圖4.2.4可以很明顯看出，顯然畫上圈的那個交巡警服務平臺設置的不合理，因為該點只與一條線路相連接，其覆蓋線段的數(shù)目太少了。如果我們將其移動到和它間隔一個節(jié)點的另外一個節(jié)點上的話，這樣該覆蓋中心就與三條線路相連接了，顯然可以增加能在三分鐘之內到達的節(jié)點的個數(shù)。這樣借助最小頂點覆蓋問題的思想，我們對圖中某些不合理的地方進行的局部的優(yōu)化和改進，方法很機動和方便。4.3 調度全市警力資源對嫌疑犯進行圍堵的最佳方案4.3.1問題分析 對于此題，我們假設交巡警在搜捕之前已經對目擊者進行了詢問，能夠確定嫌疑人的相貌，體型，和車的牌照和顏色，這樣，巡警就只要堵住關鍵的路口節(jié)點，根據具體情況把嫌疑犯的活動限制在少數(shù)的幾個城區(qū)內，實現(xiàn)快速搜捕。由于交巡警是案發(fā)后3分鐘才接到報警，所以首先要確定嫌疑犯在3分鐘的的活動范圍。但這里我們要考慮一個問題，就是嫌疑犯能否在3分鐘之內逃離A區(qū)，這就要我們對嫌疑犯的駕車速度進行討論，如果他的駕車速度不過于快，在報案前未能逃離A區(qū)，就只要調動A區(qū)的交巡警可以先堵住出入A城區(qū)的入口，然后根據嫌疑犯所有可能的逃跑路線運用不斷減小包圍圈的地毯式搜捕方法對嫌疑犯進行搜捕。但如果嫌疑犯的駕車速度很快，3分鐘后能夠逃離A區(qū)，根據嫌疑犯的作案地點，在考慮他的駕車速度符合常理的情況下，比如和警車的速度一樣，那么根據下面的計算，可以知道嫌疑犯最多只能活動在A城區(qū)和C城區(qū)，這就需要動用這幾個區(qū)的警力進行搜捕，方案也比前面所說的復雜的多，因為這是嫌疑犯的逃跑路線非常的多，但各區(qū)的交巡警只要確定包圍圈，然后不斷減小這個包圍圈，就能達到目的，搜捕到嫌疑人。下面就是我們根據嫌疑犯是否能夠逃離A區(qū)制定的圍堵方案。4.3.2 嫌疑犯未能逃離A區(qū) 發(fā)生重大刑事案件的地點位于第32節(jié)點上，根據分析A城區(qū)的交通網絡圖，通過第一題已經編號的程序可以求出這個節(jié)點與16節(jié)點城區(qū)出入口和30節(jié)點附近的7節(jié)點交巡警平臺的距離，分別為1.14km和3.31km。所以當嫌疑犯的駕車速度小于22.8km/h時，嫌疑犯無法逃離A區(qū)，由于這個速度值比較小，不是很符合實際，只要嫌疑犯以正常的駕車速度逃離，并且熟悉城區(qū)的地形，他就能逃離A區(qū)，所以我們在這里簡單地討論一下嫌疑犯被困在A區(qū)內時的搜捕方案。Stept1接到報案后迅速從最近的服務平臺派出一部分警力封鎖城區(qū)出入口。Stept2同時確定在3分鐘內嫌疑犯能夠逃離的范圍。Stept3根據嫌疑犯所有可能的逃離方向，所有可能到達的節(jié)點，從最近的服務平臺派出警力進行圍堵。Stept4不斷縮小搜捕范圍，直到嫌疑人被捕。 以上就是交巡警搜捕嫌疑犯的總體方案，在這種情況下就不具體計算了。下面我們主要要研究的就是嫌疑犯能夠逃離A城區(qū)，動用全市警力，對其所有可能藏身的城區(qū)進行快速搜捕的最佳方案。4.3.3嫌疑犯能夠逃離A城區(qū)我們知道，嫌疑犯只要駕車速度超過22.8km/h就能夠逃離A城區(qū)，在這里，我們不妨先假設嫌疑犯的駕車速度和警車時速一樣為60km/h。所以3分鐘內，嫌疑犯能夠逃跑的距離為3km，通過分析附圖一中A城區(qū)的交通路線圖，得出嫌疑犯有可能逃離A區(qū)經過的所有出入口，通過觀察與計算，并運用前面得出的公式，可得p點與這些節(jié)點的距離：所以嫌疑犯能夠在3分鐘之內從16和48節(jié)點逃離A區(qū)，我們假設各交巡警服務平臺能夠行動及時，將城區(qū)出入口這些關鍵節(jié)點給封鎖，所以我們只要考慮在A城區(qū)和C城區(qū)進行搜捕即可。(1)具體逮捕方案一、犯罪嫌疑人想盡快逃出市區(qū)，可以從在3分鐘內經過服務臺或沒有服務臺的的地 方逃走，經計算3分鐘內經過的服務臺為7,8,9服務臺。此時可能從38,28,29,30,48等出入A區(qū)的路口逃走，但是經計算d(16,38)d(32,38)-3d(15,28)d(32,28)-3d(15,29)3d(48,235)+ d(48,32)3由此可知在去往C區(qū)的路上警察已開始行動。三、由d(173,235) d(30,237)+ d(30,32)-3得，嫌疑犯從30點逃到C區(qū)，但由于他到達237點時，236點已被173點占據，所以只能另去別處。四、從長遠目標看擺在眼前有兩條路，一條須經過239點，另一條需經過247到246點，但很顯然第二條路行不通，因為d(173,246)d(246,247)+d(247,237)所以只能去239點。五、表面上到了239有三條道，但239-29點這條道已被15點服務臺封鎖，而且d(239,240)d(237,240)+d(237,32)-3所以只能選擇248目標點。六、經計算d(248,167)d(237,248)所以只能被逮捕。(2) 結果分析下面是嫌疑犯最優(yōu)逃跑路線：目標序號123456嫌疑犯所經過的點32730237238239表5-4-1 最優(yōu)逃跑路線最優(yōu)交巡警服務調配方案;（1） 第一時間把市區(qū)一些路口封鎖，具體分配如下表：交通警服務臺32415716封鎖的路口55406028,2930,4838表5-4-2 分配方案（2） 對C區(qū)第一時間一些路口封鎖，下表是各服務臺需要去封鎖的路口：交巡警服務臺173169167封鎖的路口235,245,246240248表5-4-3（3） 如此之后對所限制的路線進行地毯式全面搜索A區(qū)和C區(qū)。第一步：對A區(qū)虛線以上部分進行搜索圖5.4.2注：虛線以上區(qū)域就是A區(qū)交巡警搜捕的范圍第二步：對C區(qū)虛線一下部分進行搜索圖5.4.3注：虛線以下的區(qū)域就是C區(qū)交巡警的搜捕范圍五.模型的評價與改進5.1 我們建立的模型和方案的優(yōu)點：（1）在解決第一問分配各服務平臺管轄范圍時，我們考慮的比較全面，把每個節(jié)點分配到里各自最近的平臺后，還分析了幾種特殊情況，比如我們分配好各節(jié)點的“歸宿”后又考慮了當一條街道的兩各節(jié)點不歸同一個平臺管轄時，怎么分配這條街道；還有當一條街道過長或者一條街道的兩個節(jié)點就是交巡警服務平臺時，怎么合理得將這條街道分配給兩個服務平臺管轄。（2）在得出結果后，我們還對其做了合理度分析