版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、2011B 題 交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度“有困難找警察”,是家喻戶曉的一句流行語。警察肩負(fù)著刑事執(zhí)法、治安 管理、交通管理、服務(wù)群眾四大職能。為了更有效地貫徹實(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í)際課題。試就某市設(shè)置交巡警服務(wù)平臺(tái)的相關(guān)情況, 建立數(shù)學(xué)模型分析研究下面的問 題:(1)附件 1(見原題)中的附圖 1(見原題)給出了該市中心城區(qū) A 的交通 網(wǎng)絡(luò)和現(xiàn)有的 20
2、 個(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)至U達(dá)事發(fā)地。對(duì)于重大突發(fā)事件,需要調(diào)度全區(qū) 20 個(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))的具體情
3、況,按照設(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)警, 犯罪嫌疑人已駕車逃跑。 為了快速搜捕嫌疑犯, 請(qǐng)給出調(diào)度全市交巡 警服務(wù)平臺(tái)警力資源的最佳圍堵方案。解答與程序問題 1對(duì)該問題的解決, 我們先建立數(shù)學(xué)模型, 將需要達(dá)至的目標(biāo), 包括至達(dá)事發(fā)地的時(shí)間盡 量短, 各服務(wù)平臺(tái)的工作量盡量均衡,用目標(biāo)函數(shù)表達(dá)出來,同時(shí)將需要滿足的約束也表達(dá)出來,構(gòu)成合適的數(shù)學(xué)模型。然后討論求解算法,最后給出具體的計(jì) 算結(jié)果。我們的路口管轄分配方
4、案分為兩步。第一步:對(duì)Tj 3的路口,分配給到達(dá)第 j個(gè)路口時(shí)間最少的平臺(tái)。第二步:對(duì)Tj乞3的所有路口,根據(jù)盡量使各平臺(tái)分配的任務(wù)量盡量均衡的原則進(jìn)行 優(yōu)化。計(jì)算得到3分鐘不能到達(dá)的路口及所屬平臺(tái)信息見表1。表13分鐘不能到達(dá)的路口及所屬平臺(tái)信息序號(hào)路口任務(wù)量所屬平臺(tái)最短時(shí)間(分鐘)1281.3154.752291.4155.703381.2163.414391.423.685610.674.196920.8203.60因此,我們將這6個(gè)路口分配給最近的平臺(tái),剩下的86個(gè)路口建立模型,根據(jù)任務(wù)量盡量均衡的原則進(jìn)行優(yōu)化。實(shí)現(xiàn)的Matlab程序見附錄1的b2011_1.m,利用Floyd算法計(jì)算
5、92個(gè)路口 的最短路矩陣,輸出表1數(shù)據(jù)。輸出20個(gè)平臺(tái)和剩余86個(gè)待分配路口的最短路 矩陣文件dt1.txt,86個(gè)路口的任務(wù)量文件ft1.txt。以及20個(gè)平臺(tái)和13個(gè)交通要 道的距離矩陣文件dis1.txt,該數(shù)據(jù)文件用于第二問計(jì)算。模型建立設(shè)有20個(gè)平臺(tái),路口有 86個(gè)。dij表示第i個(gè)平臺(tái)與第j個(gè)路口之間的最短路,由Floyd算法求得。i =1,2,20; j =1,2,86v為警車行駛速度。這里取v二60公里/小時(shí)=1000米/分。、亠一1第 j個(gè)路口分配給第i個(gè)平臺(tái)建立決策變量 x“決策變 ij 0第j個(gè)路口不分配給第i個(gè)平臺(tái)每個(gè)路口只分配給一個(gè)平臺(tái),有約束:20 Xij =1 j
6、 =1,2,.,86i 每個(gè)平臺(tái)至少管理一個(gè)路口,有約束:86 Xij -1 i -1,2,., 20j $每個(gè)平臺(tái)管理自己的路口,則有:xii = 1 , i = 1 , 2 ,,第j個(gè)路口到指派的平臺(tái)的時(shí)間為tj,滿足:20tj 八 Xj.dij /v j =1,2,.,86i 4其時(shí)間應(yīng)滿足不超過 3份鐘,則有:tj - 3 j = 1, 2 , . ,8計(jì)算第i個(gè)平臺(tái)分配的路口數(shù)的任務(wù)量為。設(shè)已知第j個(gè)路口的任務(wù)量(平均每天的發(fā)生報(bào)警案件數(shù)量)為fj, j =1,2,.,86,則第i個(gè)平臺(tái)已經(jīng)分配到的任務(wù)量:86Sj = w fj .xiji =1,2,., 20ywi為各平臺(tái)已分路口
7、數(shù)的任務(wù)量。由表1知為w2 =1.4,W7 = 0.6,= 1.4 1.3 = 2.7,W|6 =1.2, w20 = 0.8。其余為 0。各平臺(tái)分配的任務(wù)量平均值為:2020我們的冃標(biāo)是各平臺(tái)分配的任務(wù)量的標(biāo)準(zhǔn)差盡量小。即:20正(Smin Z= i丫 20-1因此我們得到的綜合模型為:20z (S -S)2minZ 二i m xj =1i 4867 Xj -1j 4j =12.,86i =1,2,.,20Xjj 二 1 i 二 1,2,.,2020tj sttj八 Xj.dij / v j =1,2,.,86i 43 j “2,8686S = Wj .芻 i =1,2,., 20j 二20
8、 i 420Xjj =0或 1i =1,2,., 20; j -1,2,.,86LINGO 程序見附錄 2的b2011_1.lg4。采用Lingo12優(yōu)化很快得到Z=1.76,表示每個(gè)平臺(tái)的任務(wù)量平均有1.76件的波動(dòng)。各平臺(tái)的分配方案見表2。表2各平臺(tái)管轄的路口分配及任務(wù)量平臺(tái)管轄的路口總?cè)蝿?wù)量取長(zhǎng)時(shí)間(分鐘)11,64,71,72,77,78,79,807.602.6022,40,69,747.402.5333,44,54,55,70,767.202.9744,57,60,62,63,65,667.302.8455,49,53,56,596.102.0866,50,51,52,586.10
9、2.3877,30,486.501.2988,32,33,476.902.0899,35,36,37,456.101.431010,1.6001111,26,274.601.641212,254.001.791313,21,22,23,248.502.7114142.5001515,316.402.971616,34,466.702.381717,41,42,437.001.791818,85,87,89,90,917.402.631919,67,68,73,75,82,837.202.792020,81,84,86,887.402.68問題2給出了該市中心城區(qū) A的交通網(wǎng)絡(luò)和現(xiàn)有的 20個(gè)交
10、巡警服務(wù)平臺(tái)的設(shè)置情況示意圖,相關(guān)的數(shù)據(jù)信息見附件 2(見原題)。對(duì)于重大突發(fā)事件,需要調(diào)度全區(qū)20個(gè)交巡警服務(wù)平臺(tái)的警力資源,對(duì)進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖。實(shí)際中一個(gè)平臺(tái)的警力最多封鎖一個(gè)路口,我們的目的是給出該區(qū)交巡警服務(wù)平臺(tái)警力合理的調(diào)度方案。對(duì)該問題,我們先建立最優(yōu)的調(diào)度模型,使各服務(wù)平臺(tái)到達(dá)交通要道的時(shí)間盡量的短。然后討論求解算法,最后給出具體的計(jì)算結(jié)果。模型建立對(duì)于重大突發(fā)事件,需要調(diào)度城市的交巡警服務(wù)平臺(tái)的警力資源,對(duì)進(jìn)出該區(qū)的多條交通要道實(shí)現(xiàn)快速全封鎖。采用的模型如下。設(shè)該市有20個(gè)平臺(tái),要封鎖的交通要道有13個(gè)。dj表示第i個(gè)平臺(tái)與第j個(gè)交通要道之間的最短路,由F
11、loyd算法求得。v為警車行駛速度。這里取v=60公里/小時(shí)=1000米/分鐘設(shè)0-1決策變量Xjj = 1第j個(gè)路口分配給第i個(gè)平臺(tái)圍堵j 0第j個(gè)路口不分配給第i個(gè)平臺(tái)圍堵對(duì)每個(gè)交通要道,需要且只需要分配一個(gè)平臺(tái)的警力,則有:20xij - 1 j -1,2,.,13i 1每個(gè)交巡警服務(wù)平臺(tái)的警力最多到一個(gè)交通要道去圍堵,因此有:13、x 豈 1i =1,2,20j壬設(shè)Tj表示到第j個(gè)路口的時(shí)間。則有:20Tj = djXj /v j =12,13i =1我們選取的第一目標(biāo)是到交通要道的最長(zhǎng)時(shí)間最小化,這樣可使最長(zhǎng)時(shí)間盡 量小。則第一目標(biāo)函數(shù)為:mi n = maxTj1直3當(dāng)最長(zhǎng)時(shí)間最小
12、情況下,我們同時(shí)對(duì)小于最時(shí)間的分配方式進(jìn)行優(yōu)化,使到達(dá)各交通要道的時(shí)間平均時(shí)間最小。則第二目標(biāo)函數(shù)為:137 min Z2 二13綜合上述,我們建立的的綜合模型為:13Tjmin Z2j 21320一xij = 1i 413E Xj 1 S.t j 二j =12.,13i =1,2,.,2020Tj =S dij xij / vidXj = 0或 1LINGO程序見附錄3的b2011_2g4??上葍?yōu)化第一目標(biāo), 得到最短時(shí)間為 8.02分鐘。 然后將Z1乞8.02作為約束優(yōu)化第二目標(biāo),得到最小的平均時(shí)間為3.55分鐘。圍堵 的具體方案見表3。表3 LINGO求解的最優(yōu)分配方案序號(hào)交通要道號(hào)分配
13、的平臺(tái)號(hào)到達(dá)時(shí)間(分鐘)112120214166.7431691.53421143.26522107.71623130.5724113.81828154.7592978.02103083.06113823.98124852.48136240.35該模型由于是非線性的,利用LINGO求解較為費(fèi)時(shí),通常也不能保證最優(yōu) 解。為此。我們也可以另外設(shè)計(jì)算法,便于快速求解,同時(shí)便于在后面的圍堵問 題中快速求解。3、算法設(shè)計(jì)我們的求解算法采用三步完成。第一步,先利用貪婪法盡量使各平臺(tái)到達(dá) 交通要道的時(shí)間盡量短。第二步,對(duì)到各交通要道的時(shí)間再進(jìn)行調(diào)整, 進(jìn)一步優(yōu) 化,直到最長(zhǎng)時(shí)間不能再減少為止。第三步,在保證
14、最長(zhǎng)時(shí)間不增大的情況下, 對(duì)到各交通要道的平均時(shí)間進(jìn)行調(diào)整,直到不再減小為止。算法步驟:1.先將13個(gè)交通要道依次分配給最近的路口。2將時(shí)間最長(zhǎng)的要道與其余的要道分配的平臺(tái)對(duì)換,若最長(zhǎng)時(shí)間可以減 少,則對(duì)換。實(shí)際中可在對(duì)換后,另一要道在剩余平臺(tái)中選擇最近的平臺(tái)。3.重復(fù)2,直到最長(zhǎng)時(shí)間不再減少為止。對(duì)平均時(shí)間的減少采用同樣的方法。直到總時(shí)間或平均時(shí)間不再減小結(jié)束。 輸出各路口對(duì)應(yīng)平臺(tái)及時(shí)間,平均時(shí)間。采用步驟1中貪婪法求得最長(zhǎng)時(shí)間為13.67分鐘,平均時(shí)間為3.95分鐘。采 用步驟二中減少最長(zhǎng)時(shí)間的算法, 經(jīng)過5次調(diào)整,最長(zhǎng)時(shí)間達(dá)到最小。最長(zhǎng)時(shí)間 為8.02分鐘,平均時(shí)間為3.78分鐘。計(jì)算的
15、結(jié)果見表4。遺憾的是沒有達(dá)到最 小的3.55分鐘。但該方法的優(yōu)點(diǎn)是計(jì)算速度快。不到1秒就可以計(jì)算出結(jié)果,比LINGO計(jì)算的2分多鐘快多了。表4貪婪算法計(jì)算出的圍堵方案序號(hào)交通要道號(hào)分配的平臺(tái)號(hào)到達(dá)時(shí)間(分鐘)112107.59214166.7431691.53421143.26522113.27623130.5724123.59828154.7592978.02103083.06113823.98124852.48136240.35對(duì)全市所有路口的圍堵,我們可建立同樣模型,分別采用LINGO和我們提出的貪婪算法計(jì)算。全市路口的圍堵計(jì)算:全市有交巡警平臺(tái)80個(gè),全市出入口位置有17個(gè)。要封鎖的交
16、通要道m(xù)=17個(gè),其集合為 J =151,153,177,202,203,264,317,325,328,332,362,387,418,483,541,572,578??晒┓峙涞钠脚_(tái) n =80 個(gè),其集合為 P= 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,93,94,95,96,97, 98,99,100,166,167,168,169,170,171,172,173,174,175,176,177,178,179, 180,181,182,320,321,322,323,324,325,326,327,328, 372,373,
17、374,375,376, 377,378,379,380,381,382,383,384,385,386,475,476,477,478,479,480,481,482,483,484 ,485。采用步驟一中貪婪法求得最長(zhǎng)時(shí)間為12.68分鐘,平均時(shí)間為5.07分鐘。該結(jié)果通過調(diào)整并不能減少最長(zhǎng)時(shí)間,可以驗(yàn)證,該分配方案中,除202號(hào)交通要道外,其余各交通要道都分配的到達(dá)時(shí)間最短的平臺(tái)。而到達(dá)202號(hào)交通要道的 時(shí)間最少的平臺(tái)為177,次之為175,177號(hào)平臺(tái)分配177號(hào)交通要道最佳,從 而分配175號(hào)平臺(tái)202號(hào)交通要道最佳。總的計(jì)算結(jié)果是最長(zhǎng)時(shí)間最小為12.68分鐘,平均時(shí)間最小為5.0
18、7分鐘。可驗(yàn)證該結(jié)果即為最優(yōu)結(jié)果。詳細(xì)結(jié)果見表5。表5全市利用貪婪算法計(jì)算出的圍堵方案序號(hào)交通要道號(hào)分配的平臺(tái)號(hào)到達(dá)時(shí)間(分鐘)1151963.192153994.4731771770420217511.6252031784.4562641666.6273171815.488325325093283280103323867.62113623238.111238710012.68134183797.419144834830155414847.04165724851.66175784795.76對(duì)比:利用Lingo12求解,耗時(shí)41分鐘,得到局部最優(yōu)解為35.6分鐘 因此,當(dāng)規(guī)模變大時(shí),采用簡(jiǎn)單的
19、貪婪算法有時(shí)候更方便快速。問題3給出了該市中心城區(qū) A的交通網(wǎng)絡(luò)和現(xiàn)有的 20個(gè)交巡警服務(wù)平臺(tái)的設(shè)置情況示意圖,相關(guān)的數(shù)據(jù)信息見附件 2。根據(jù)現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡和有些地方出 警時(shí)間過長(zhǎng)的實(shí)際情況,擬在該區(qū)內(nèi)再增加2至5個(gè)平臺(tái),請(qǐng)確定需要增加平臺(tái) 的具體個(gè)數(shù)和位置。對(duì)該問題,我們先建立最優(yōu)的調(diào)度模型,使各服務(wù)平臺(tái)到達(dá)交通要道的時(shí)間盡量短,各平臺(tái)的任務(wù)量盡量均衡。然后討論求解算法,并最后給出具體的計(jì)算結(jié)果。模型建立根據(jù)現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡和有些地方出警時(shí)間過長(zhǎng)的實(shí)際 情況,需要在一個(gè)區(qū)內(nèi)新增加一些平臺(tái)。我們需要確定新增加平臺(tái)的具體個(gè)數(shù)和位置。設(shè)該市要巡視的路口有92個(gè),其
20、序號(hào)為j =1,2,.,92。交巡警服務(wù)平臺(tái)現(xiàn)在已有20個(gè),其序號(hào)為i =1,2,.,20dj表示第i個(gè)平臺(tái)與第j個(gè)路口之間的最短路,由Floyd算法求得。v為警車行駛速度,這里取v = 60公里/小時(shí)=1000米/分鐘。設(shè)增加平臺(tái)數(shù)為k個(gè),則總共有平臺(tái)20 k個(gè)。且所有平臺(tái)都在92個(gè)路口中 選取。每個(gè)路口的日平均案件量為fi =1,2,.,92。下面我們建立新增平臺(tái)的多目標(biāo)規(guī)劃模型。設(shè)0-1變量Yj表示哪些路口選作平臺(tái),設(shè)j =1, 2, . ,9丫.第j個(gè)路口選作平臺(tái)j 0第j個(gè)路口不選作平臺(tái)建立0-1決策變量Xj表示平臺(tái)處理路口的情況。設(shè)i, j - 1, 2 ,.1 第i平臺(tái)處理第j個(gè)
21、路口X- = Iu 0 第i平臺(tái)不處理第j個(gè)路口第j路口需要而且只需要一個(gè)平臺(tái)處理。則有:92二 xj =1 j =1 , 2 , ., 9i 4平臺(tái)數(shù)總共為n k個(gè),則有:92、yj =20 kj 4其中已經(jīng)有20個(gè)平臺(tái),且為前20個(gè),因此yj =1 , j =1,2,20只有當(dāng)?shù)趇個(gè)路口選作平臺(tái)才能去處理第j路口,因此有:Xi j y i ,i j 1, 2 , . ., 9考慮各平臺(tái)警力到各路口的時(shí)間盡量小。我們計(jì)算到達(dá)各路口的時(shí)間。到達(dá)路口 j時(shí)間為:92Tj 八 Xj.dj/vj =1,2,.,92我們的目標(biāo)是讓最長(zhǎng)時(shí)間最小,因此有:m i n1m Tx1 恒蘭9 2j對(duì)任務(wù)量,我們
22、考慮將該點(diǎn)的發(fā)案數(shù)作為其度量值,則第i個(gè)平臺(tái)處理的任務(wù)量為:92W 二 Xjj. fji =1,2,. , 9j當(dāng)yi =0時(shí),所有Xj -0, j =1,2,.,92。則w =0。即該點(diǎn)沒有選作平臺(tái),其 任務(wù)量為0。平均任務(wù)量為:92二 wiW20 k下面計(jì)算各平臺(tái)任務(wù)量的離差平方和。在離差平方和中,其計(jì)算式為92S = V (Wi -W)2。但這里我們是對(duì)任務(wù)量 Wi0的20 k個(gè)平臺(tái)計(jì)算其離差平i 方和,因此其計(jì)算式為:92S 八 w -(20 k).W2i生樣本標(biāo)準(zhǔn)差為:;-. S/(20亠k1)我們的目標(biāo)是盡量使各平臺(tái)的任務(wù)量均衡,因此有:min Z2 = min . S/(n k
23、-1)綜合上述。我們得到的總模型為:min Z2 = min . S/(n k -1)-92Z Xij =1 j =1,2,.,92i 192Z yi =20 + ki 192Wj= Xj.fji =1,2,.,92j a92送ww = s.t 20+ k92S=w:(20+k).W2i壬92Tj =遲 Xj .dj /v j =1,2,.,92i=1Xij hi, j =1,2,.,92% =1,i =1,2,.,20Xjj =0或 1i, j =1,2,.,92y =0或 1i = 21,.,92該結(jié)果利用LINGO計(jì)算十分困難,考慮設(shè)計(jì)簡(jiǎn)單算法實(shí)現(xiàn)。3、算法設(shè)計(jì)貪婪法每次從超過3分鐘的路
24、口中選取使最長(zhǎng)時(shí)間最小的路口作為平臺(tái)。下次再如此進(jìn)行。到每個(gè)路口到平臺(tái)的時(shí)間都不超過3分鐘為止。計(jì)算程序?yàn)楦郊?4中的b2011_3.m。對(duì)A區(qū),路口數(shù)92,平臺(tái)數(shù)20,超過3分鐘的路口 6個(gè)。計(jì)算結(jié)果為:Kp= 1 Plat=28 maxT=4.1902Kp= 2 Plat=61 maxT=3.6822Kp= 3 Plat=38 maxT=3.6013Kp= 4 Plat=92 maxT=2.7083增加 4 個(gè)平臺(tái)最佳。問題 4 考慮全市 6 個(gè)區(qū)新增平臺(tái)情形對(duì) B 區(qū),路口數(shù) 73, 平臺(tái)數(shù) 8,超過 3 分鐘的路口 6超過3 分鐘的路口 ,平臺(tái) ,時(shí)間122943.29123943.3
25、7124963.21151963.19152993.37153994.47增加平臺(tái)數(shù),最長(zhǎng)時(shí)間Kp= 1 Plat=151 maxT=3.3653Kp= 2 Plat=122 maxT=2.9863 對(duì) B 區(qū),增加兩個(gè)平臺(tái),最長(zhǎng)出警時(shí)間為2.9863 分鐘 .其它區(qū)也可采用該程序計(jì)算, 之是要讓最大出警時(shí)間時(shí)候不超過 3 分鐘,需要增加平臺(tái) 數(shù)較多。全區(qū)同時(shí)考慮 全區(qū),路口數(shù) 582,平臺(tái)數(shù) 80 ,超過 3 分鐘的路口 138 增加平臺(tái)數(shù) ,最長(zhǎng)時(shí)間Kp= 1 Plat=389 maxT=9.1609Kp= 2 Plat=329 maxT=8.4671Kp= 3 Plat=387 maxT
26、=8.1188Kp= 4 Plat=417 maxT=8.1069Kp= 5 Plat=362 maxT=7.8085Kp= 6 Plat=248 maxT=7.0418Kp= 7 Plat=540 maxT=6.8605Kp= 8 Plat=199 maxT=6.6223Kp= 9 Plat=259 maxT=6.6068Kp=10 Plat=505 maxT=6.5832Kp=11 Plat=569 maxT=6.5686Kp=12 Plat=28 maxT=6.4259Kp=13 Plat=369 maxT=6.4152Kp=14 Plat=261 maxT=6.1636Kp=15 Pl
27、at=574 maxT=6.1112Kp=16 Plat=200 maxT=5.8259Kp=17 Plat=29 maxT=5.7575Kp=18 Plat=578 maxT=5.6953Kp=19 Plat=239 maxT=5.4752Kp=20 Plat=300 maxT=5.1506Kp=21 Plat=418 maxT=5.0529Kp=22 Plat=370 maxT=4.9555圖1增加平臺(tái)時(shí)間及對(duì)應(yīng)最大出警時(shí)間圖形從該結(jié)果來看,要讓最大出警時(shí)間少于3分鐘,需要增加很多平臺(tái)。因此可考慮何時(shí)即可。問題5.圍堵方案的確定5.1給定時(shí)間t可以包圍罪犯的最小包圍圈的確定給定時(shí)間t,給定
28、罪犯逃跑的速度 v,計(jì)算出罪犯能逃跑的范圍。這里我們采用點(diǎn)來表示其逃跑范圍。計(jì)算其全市總路口 N =581個(gè)中罪犯在t分鐘內(nèi)能到達(dá)的點(diǎn)集合,設(shè)為A(t)。 計(jì)算公式為:D(i,32) +A(t) -i |t,i =12,,581v其中32點(diǎn)為案發(fā)現(xiàn)場(chǎng),罪犯的逃跑開始點(diǎn)。D(i,32)為各點(diǎn)到32點(diǎn)的最短距離。同時(shí)計(jì)算與A(t)相鄰的點(diǎn)集合,設(shè)為 B(t)。B(t)二j |P(i,j) Ji A(t)其中P(i, j) 1表示i與j直接相連;P(i, j) =0表示i與j不直接相連。該數(shù)據(jù) 由附件2中全市交通路口的路線表單對(duì)應(yīng)數(shù)據(jù)得到。則可以包圍罪犯逃跑區(qū)域A(t)的最小閉包(用路口節(jié)點(diǎn)表示)為
29、 C(t):C(t)= B(t) -A(t)這里的減為集合之間的減法。即從點(diǎn)集合B(t)中去掉A(t)中已有的點(diǎn)。C(t)就是給定時(shí)間可以包圍罪犯的最小包圍圈。二、警察在給定時(shí)間t能否到達(dá)包圍圈的確定設(shè)C(t)中節(jié)點(diǎn)個(gè)數(shù)為L(zhǎng) ,可分配的平臺(tái)為K =80個(gè)。我們的目標(biāo)是采用問題T(t)。 T(t)為模型中(a)的最優(yōu)的模型對(duì)平臺(tái)的警力進(jìn)行分配,求出到達(dá)各節(jié)點(diǎn)的最長(zhǎng)時(shí)間 值。min Z 二 maxTjj(a)L7 Xij -1j呂80s.t丘Xij曰i h,2,80j =1,2,., L80T d x / vjij iji=1Xij =0 或 1若T(t)乞t -3,則警察可以完成包圍圈C(t)的
30、包圍。否則不能完成包圍。t - 3是因?yàn)樽锓赶忍优芰?3分鐘。我們的目標(biāo)就是求出在最短時(shí)間完成對(duì)罪犯的包圍。因此目標(biāo)函數(shù)為:mi nZ =t約束為T(t)乞t -3。因此總的模型為:mi nZ =tst T(t)蘭t3實(shí)際計(jì)算時(shí),可以采用從t = 3開始,每隔 30秒進(jìn)行計(jì)算,直到滿足約束條件T(t)空 t _3。實(shí)際計(jì)算中平臺(tái)數(shù)可以減少。若某平臺(tái)的警力在t-3分鐘內(nèi)都不能到達(dá)包圍圈G中任意點(diǎn),則該平臺(tái)刪除。即可選平臺(tái)集合為:Plat -i|Time(i, j) :::t -3, j G,i=1,2,.,80這樣可大大減少平臺(tái)數(shù),使問題規(guī)模減小,便于求解。計(jì)算程序見附件 5中的b2011_5_
31、1.m和附件6中的b2011_5_2.m。計(jì)算得到的結(jié)果見圍堵方案圖2和圍堵方案表6。圖2圍堵方案圖其中藍(lán)色O為內(nèi)部點(diǎn)紅色*為包圍點(diǎn),藍(lán)色為分配的平臺(tái)。表6圍堵方案表序號(hào)包圍點(diǎn)平臺(tái)號(hào)封鎖時(shí)間(分)罪犯逃跑到該點(diǎn) 時(shí)間(分)11414310.043221717310.6504326113.99.72654429158.70059.1556354126.441110.502564314.80019.3879476243.359.1319868195.23849.1530797035.97199.448181076186.13289.2384511168168312.4791122151716.62
32、7411.2542132171723.97179.83724142181706.27899.44592152271746.69989.22363162401739.695210.1541172481676.678820.5237182731825.102412.80881937132010.36115.89420482482311.1731214874817.56514.6402225494766.025510.7206235584755.052611.0991245624804.941611.3988警察在接到報(bào)案后,最長(zhǎng)完成封鎖時(shí)間為10.361 - 3 = 7.361分鐘。點(diǎn)評(píng):在完成該
33、題過程中,需要用 Matlab編程與LINGQ編程相結(jié)合共同完成問題 求解。利用Matlab可以進(jìn)行數(shù)據(jù)預(yù)處理,根據(jù) Floyd算法進(jìn)行最短路計(jì)算,對(duì) 包圍路線作圖,以及對(duì)自己設(shè)計(jì)的算法進(jìn)行計(jì)算。LINGO則可以直接根據(jù)模型進(jìn)行優(yōu)化計(jì)算,而其中使用的大量數(shù)據(jù)需要通過 Matlab計(jì)算輸出。這種通過Matlab 和LINGO相互結(jié)合完成計(jì)算,是近年來在競(jìng)賽中經(jīng)常使用的方法。程序附錄附件1:數(shù)據(jù)預(yù)處理及輸出數(shù)據(jù)文件的Matlab程序b2011_1.m。%初始數(shù)據(jù)處理,作圖,并得到92個(gè)路口之間的最短路 A(92,92),%計(jì)算并輸出20個(gè)平臺(tái)與13個(gè)路口之間距離 dis1.txt%輸出20個(gè)路口到
34、待分配路口 (86個(gè))的距離矩陣(20*86) dt1.txt%輸出待分配路口的(86)口的發(fā)案數(shù)ft1.txt%還可對(duì)LINGO計(jì)算結(jié)果按照規(guī)范形式輸出。load DA.txt %所有路口號(hào)(582個(gè)),x,y,區(qū),發(fā)案率%街道數(shù)據(jù)load DB.txt; % 連接線,928 條DA=DA(1:92,:); % 取前 92 個(gè)路口信息ma,na=size(DA);mb,nb=size(DB); pos=12,14,16,21,22,23,24,28,29,30,38,48,62;%A 區(qū)出入口位置k=20; %1-20 平臺(tái)x=DA(:,2);y=DA(:,3); f=DA(:,5);% 分
35、別獲得個(gè)路口的 x坐標(biāo),y坐標(biāo),發(fā)案數(shù)plot(x,y,bo,x(1:k),y(1:k),g*); % 作圖,藍(lán)色為所有路口,綠色為前20個(gè)平臺(tái)kp=0; % 統(tǒng)計(jì) A 區(qū)街道數(shù)LineA=zeros(200,2);for i=1:mbif DB(i,1)=92&DB(i,2)=92kp=kp+1;LineA(kp,1)=DB(i,1); LineA(kp,2)=DB(i,2);endend %將 A 區(qū)街道的起始點(diǎn)和終點(diǎn)分別放在數(shù)組 LineA(kp,1) 和 LineA(kp,2) 中。 hold onfprintf(A 區(qū)街道數(shù) %2dn,kp);px=zeros(2,1); py=ze
36、ros(2,1);for i=1:kppx(1)=x(LineA(i,1); py(1)=y(LineA(i,1);px(2)=x(LineA(i,2); py(2)=y(LineA(i,2);plot(px,py); %將 A 區(qū)所有街道連線end%利用 Floyd 算法求任意兩點(diǎn)之間最短路v=1000; % 每分鐘速度n=92; %A 區(qū)路口數(shù)為 92A=zeros(n,n); % 存儲(chǔ)任意兩點(diǎn)最短路for i=1:nfor j=1:nif(i=j) A(i,j)=0;else A(i,j)=1000000;endendendfor i=1:kp%給每條線路賦予距離point1=LineA
37、(i,1); point2=LineA(i,2); p1x=x(point1); p1y=y(point1) ; p2x=x(point2); p2y=y(point2);d=sqrt(p1x-p2x)A2+(p1y-p2yF2);A(point1,point2)=d;A(point2,point1)=d;endU=A; % 原始矩陣%1.1 利用 Floyd 算法計(jì)算最短距離矩陣for k=1:nfor i=1 :nfor j=1:n t=A(i,k)+A(k,j);if tA(i,j) A(i,j)=t; endend %end for jend %end for iend %end fo
38、r kA=100*A; % 每毫米代表 100 米,得到以米為單位的距離 .Dis=zeros(20,13); % 存儲(chǔ) 20 個(gè)平臺(tái)和 13 個(gè)交通要道的距離 for i=1:20for j=1:13ip=i;%第 ip 個(gè)平臺(tái)jp=pos(j); % 第 jp 個(gè)路口Dis(i,j)=A(ip,jp);endend %獲得 20 個(gè)平臺(tái)和 13 個(gè)交通要道(路口)的距離矩陣%輸出 20個(gè)平臺(tái)與 13 個(gè)路口之間距離 fid=fopen(d:lingo12datdis1.txt,w); % 此處目錄可修改 for i=1:20for j=1:13fprintf(fid,%6.2f ,Dis(
39、i,j);end fprintf(fid,n);endfclose(fid);n=92; % 路口數(shù)m=20; %平臺(tái)數(shù)Plat=1:m; % 平臺(tái)T=zeros(1,n); % 存儲(chǔ)到各路口的時(shí)間S=zeros(1,n); % 存儲(chǔ)到各路口時(shí)間最少的平臺(tái)號(hào)%求到各路口的最短時(shí)間和對(duì)應(yīng)的平臺(tái)號(hào)for j=1:njp=j; %路口mint=1000;for i=1:mip=Plat(i); % 平臺(tái)t=A(ip,jp)/v;if t3.0 U(j)=0; fprintf(%2d %2d %6.2f %6.2fn,j,S(j),T(j),f(j); end end %輸出超過 3 分鐘到達(dá)的路口%
40、獲得待分配的路口序號(hào) (時(shí)間不超過 3 分鐘的路口 )Lu=;for j=1:nif U(j)=1 Lu=Lu,j; endendr=length(Lu); % 剩余路口數(shù)%獲得 20 個(gè)平臺(tái)到剩路口 (86) 的距離矩陣D=zeros(m,r);%( 平臺(tái),路口 )for i=1:m %平臺(tái)數(shù) m=20for j=1:r %剩余路口數(shù) r=86 ip=Plat(i);jp=Lu(j); D(i,j)=A(ip,jp);endendfid=fopen(d:lingo12datdt1.txt,w); % 輸出 20*86 的距離矩陣for i=1:mfor j=1:rfprintf(fid,%6
41、.2f ,D(i,j);endfprintf(fid,n);endfclose(fid);fid=fopen(d:lingo12datft1.txt,w); % 輸出剩余 86 個(gè)路口的任務(wù)量 for j=1:rk=Lu(j);fprintf(fid,%5.1fn, f(k);endfclose(fid);%此段程序?qū)?LINGO 程序 b2011_1.lg4 計(jì)算結(jié)果進(jìn)行整理,開始時(shí)不需要。 TEST=1; % 當(dāng) TEST=1 ,對(duì) LINGO 計(jì)算結(jié)果進(jìn)行規(guī)范輸出,便于閱讀和寫作。if TEST=1%對(duì)對(duì) Lingo 求解結(jié)果進(jìn)行整合,重新按照規(guī)范格式輸出。 x=zeros(m,r);w
42、=0,1.4,0,0,0,0,0.6,0,0,0,0,0,0,0,2.7,1.2,0,0,0,0.8; % 初始各平臺(tái)的任務(wù)量%將 LINGO 計(jì)算結(jié)果拷貝在下面 .;x(1,1)=1 ;x(1,59)=1 ;x(1,66)=1 ;x(1,67)=1 ;x(1,72)=1 ;x(1,73)=1 ;x(1,74)=1 ;x(1,75)=1 ; x(2,2)=1 ;x(2,36)=1 ;x(2,64)=1 ;x(2,69)=1 ;x(3,3)=1 ;x(3,40)=1 ;x(3,50)=1 ;x(3,51)=1 ; x(3,65)=1 ;x(3,71)=1 ;x(4,4)=1 ;x(4,53)=1
43、 ;x(4,56)=1 ;x(4,57)=1 ;x(4,58)=1 ;x(4,60)=1 ; x(4,61)=1 ;x(5,5)=1 ;x(5,45)=1 ;x(5,49)=1 ;x(5,52)=1 ;x(5,55)=1 ;x(6,6)=1 ;x(6,46)=1 ; x(6,47)=1 ;x(6,48)=1 ;x(6,54)=1 ;x(7,7)=1 ;x(7,28)=1 ;x(7,44)=1 ;x(8,8)=1 ;x(8,30)=1 ; x(8,31)=1 ;x(8,43)=1 ;x(9,9)=1 ;x(9,33)=1 ;x(9,34)=1 ;x(9,35)=1 ;x(9,41)=1 ;x(1
44、0,10)=1 ; x(11,11)=1 ;x(11,26)=1 ;x(11,27)=1 ;x(12,12)=1 ;x(12,25)=1 ;x(13,13)=1 ;x(13,21)=1 ; x(13,22)=1 ;x(13,23)=1 ;x(13,24)=1 ;x(14,14)=1 ;x(15,15)=1 ;x(15,29)=1 ;x(16,16)=1 ; x(16,32)=1 ;x(16,42)=1 ;x(17,17)=1 ;x(17,37)=1 ;x(17,38)=1 ;x(17,39)=1 ;x(18,18)=1 ; x(18,80)=1 ;x(18,82)=1 ;x(18,84)=1
45、;x(18,85)=1 ;x(18,86)=1 ;x(19,19)=1 ;x(19,62)=1 ; x(19,63)=1 ;x(19,68)=1 ;x(19,70)=1 ;x(19,77)=1 ;x(19,78)=1 ;x(20,20)=1 ;x(20,76)=1 ; x(20,79)=1 ;x(20,81)=1 ;x(20,83)=1;%輸出每個(gè)平臺(tái)管轄的路口,任務(wù)量 ,最長(zhǎng)時(shí)間 fprintf(n 第一問 LINGO 求解結(jié)果的輸出 .n); fprintf( 平臺(tái),管理的路口 , 任務(wù)量, 最長(zhǎng)時(shí)間 :n);TT=zeros(m,1);W=zeros(m,1);for i=1:mfpri
46、ntf(%2d:,i);s1=w(i); % 初始任務(wù)TT(i)=0;for j=1:rif x(i,j)=1 jp=Lu(j); s1=s1+f(jp); t=A(i,jp)/v;if tTT(i) TT(i)=t;end fprintf(%2d,jp);endW(i)=s1;endfprintf( w=%5.2f t=%5.2fn,s1,TT(i);endend附件2問題1的LING012程序b2011_1g4。該程序?qū)?6個(gè)待分配路口進(jìn)行分派,所使用的數(shù)據(jù)文件 dt1.txt 和ft1.txt 由Matlab程序b2011_1.m生成。LINGO程序的計(jì)算結(jié)果可直接拷貝到b2011_1.
47、m中最后相應(yīng)位置,重新按照規(guī)范格式輸出。在 b2011_1.m中設(shè)置TEST=1控制輸出。!問題1的LINGC程序;model:sets :Plat/1.20/:s,w;Kou/1.86/:T,f;Assign(Plat,Kou):dis,x;endsetsdat a:v=1000;n=20;dis=fil e(d: lingo12datdt1.txt); !20個(gè)平臺(tái)和待分配的 86個(gè)路口的距離矩陣 ;f=fil e(d: lingo12datft1.txt);!待分配的 86個(gè)路口的發(fā)案量 ;text()=wri tefor(Ass ign(i,j)|x(i,j)#GT#0:;x(,i,j
48、,)=,x(i,j), ); w=0,1.4,0,0,0,0,0.6,0,0,0,0,0,0,0,2.7,1.2,0,0,0,0.8;!20個(gè)平臺(tái)的初始發(fā)案量 ;enddatamin=sqt(sum(Pla t(i):(s(i)-sv)A2)/(n-1); !標(biāo)準(zhǔn)差最小;for(Kou(j):sum (Pla t(i):x(i,j)=1); !每個(gè)路口恰好有一個(gè)平臺(tái) ;for(Plat(i): sum(Kou(j):x(i ,j)=1);! 每個(gè)平臺(tái)至少管理一個(gè)路口 ;for(Kou(j):T(j)=sum(Plat (i):x (i,j)*dis(i,j )/v) ); !第j 個(gè)路口的處理
49、時(shí)間; for(Kou(j):T( j)=3); ! 沒個(gè)路口到達(dá)時(shí)間少于 3分鐘;for(Plat(i):x(i,i)=1); ! 每個(gè)平臺(tái)管理自己的路口 ;for(Plat (i):s (i)=w(i)+sum(Kou(j) :f(j)*x(i,j);! 計(jì)算各平臺(tái)管轄 的路口的任 務(wù)量 ;sv=sum(Plat(i ):s( i)/n; ! 平均路口數(shù) ;for(Assign(i,j):bin(x(i,j);end附件3問題2的LINGO12程序b2011_2.lg4。該程序?qū)?13個(gè)交通要道的圍堵問題優(yōu)化求解。model:sets :Plat/1.20/;Kou/1.13/:T;Ass
50、ign(Plat,Kou):dis,x,Time;endsetsdata :v=1000;dis= file (d:lingo12datdis1.txt);!20 個(gè)平臺(tái)和 13個(gè)路口的距離矩陣 ; text ()= writefor (Assign(i,j)|x(i,j)#GT#0:x(,i,j,)=,x(i,j), );enddatamin =aver;! min=TT;TT=ma(xAssign(i,j):Time(i,j); ! 最大時(shí)間最小化 ;aver= sum(Kou(j) :T(j)/13; ! 平均時(shí)間 ;TT8.02; ! 當(dāng)優(yōu)化第二目標(biāo)時(shí)將第一目標(biāo)變?yōu)榧s束;for (Ass ign(i,j):Time(i,j)=x(i,j)*dis(i,j)/v);for(kou (j) :T(j)=sum(Pl at(i ):x(i,j)*dis(i,j)/v);! 到第 j 個(gè)路口 的時(shí)間 ;for(Plat(i): sum(KOu(j):x(i ,j)=1); !第i 個(gè)平臺(tái)最多到一個(gè)路口;for(Kou(j):sum(Plat(i):x(i,j )=1); !第j 個(gè)路口一定有一個(gè)平臺(tái)到達(dá);for(Assi gn
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 籃球場(chǎng)防水施工合同
- 社交媒體知識(shí)庫使用規(guī)范
- 商業(yè)步行街綠化草皮種植協(xié)議
- 體育設(shè)施用地供應(yīng)管理實(shí)施辦法
- 影視保險(xiǎn)理賠指南
- 協(xié)調(diào)部工作問題解決策略
- 汽車美容店廣告牌租賃合同范本
- 美術(shù)館展品維護(hù)指南
- 動(dòng)漫游戲產(chǎn)業(yè)招投標(biāo)關(guān)鍵環(huán)節(jié)
- 水庫建設(shè)工程款結(jié)算協(xié)議
- 第三章 閘板防噴器
- 鄉(xiāng)鎮(zhèn)精神文明建設(shè)工作專題調(diào)研報(bào)告
- 市值管理十大經(jīng)典案例
- 馬克思主義基本原理概論課程論文
- 智能材料課件完整版
- 江蘇500kV變電站軟母線安裝施工方案(附圖表)
- 《高等代數(shù)(一)》期中考試試題
- 鍋爐英語對(duì)照
- 中海煉化惠州煉油分公司“7-11”火災(zāi)事故
- 初三數(shù)學(xué) 動(dòng)點(diǎn)問題探究—幾何圖形中的動(dòng)點(diǎn)問題教案
- 建筑門窗幕墻檢測(cè)方案
評(píng)論
0/150
提交評(píng)論