警力分布模型

2010高教社杯全國(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中選擇一項(xiàng)填寫）： 警力分布我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）：所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜? 參賽隊(duì)員（打印并簽名）：1. 翁曉柳 周歡祥 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）： 數(shù)模組日期：年—月—日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2006高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編號(hào)專用頁(yè)賽區(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)）：警力的分布摘要今年以來(lái)，全國(guó)各地出現(xiàn)了中小學(xué)生被犯罪分子砍殺的惡性殺人事件。為了維護(hù)廣大學(xué)生的生命安全，某市公安部門要將學(xué)校安保工作納入綜合控制體系，加強(qiáng)社會(huì)嫌疑人員監(jiān)控與防范。這就需要在學(xué)校附近道路上安排警員執(zhí)勤點(diǎn)，以做好應(yīng)急處置工作，對(duì)學(xué)校險(xiǎn)情進(jìn)行快速反應(yīng)，及時(shí)處置。本文要解決的就是19個(gè)學(xué)校以及周邊各個(gè)路段的警力分布問題，從而在確保安全保衛(wèi)工作正常進(jìn)行的條件下，使得所安排的警力人數(shù)最少，并且使警員在遇到險(xiǎn)情時(shí)能盡快趕到事發(fā)現(xiàn)場(chǎng)。根據(jù)附件中的各點(diǎn)的坐標(biāo)和圖中所給的各標(biāo)志點(diǎn)之間的相鄰關(guān)系，我們求得任意兩個(gè)相鄰標(biāo)志點(diǎn)的距離，再用Floyd算法求得任意兩點(diǎn)間的最短距離。在此基礎(chǔ)上，我們遍歷出與每個(gè)學(xué)校的距離小于0.8個(gè)單位的標(biāo)志點(diǎn)和與二類學(xué)校小于1.6個(gè)單位的標(biāo)志點(diǎn)，再?zèng)Q策出至少需要多少位警員并在此基礎(chǔ)上進(jìn)行優(yōu)化。如下是我們所決策出的警員的執(zhí)勤點(diǎn)方位示意圖：鉆石點(diǎn)的位置即為警員的執(zhí)勤位置，綠色點(diǎn)表示第一步所滿足警員最少時(shí)的分布點(diǎn)，紅圈中的藍(lán)色點(diǎn)表示優(yōu)化后使得所有警員行程時(shí)間總和最少時(shí)的點(diǎn)的分布（藍(lán)點(diǎn)僅表示紅圈內(nèi)的綠色點(diǎn)的變動(dòng)，紅圈外綠色點(diǎn)的位置無(wú)變化）。在研究執(zhí)勤點(diǎn)不限定在標(biāo)志點(diǎn)的問題時(shí)，我們把學(xué)校與學(xué)校間的可行道路作為研究對(duì)象，使得警員在道路上可以兼顧道路兩頭的學(xué)校，同時(shí)使得警員人數(shù)盡可能的少。運(yùn)用線性規(guī)劃和0—1規(guī)劃的方法，我們得出上圖中W與乙E1與G1,K1與G1,N1與B2,U1與E1,J與G1,B2與I2這些學(xué)校之間的道路上需設(shè)置執(zhí)勤點(diǎn)。最后，我們對(duì)得出的結(jié)果一一檢驗(yàn)，完全符合實(shí)際情況，對(duì)警員的安排恰到好處，最大程度上利用了有限的人力資源。關(guān)鍵字：警力分布Floyd算法線性規(guī)劃優(yōu)化決策一、問題的重述今年3月23日早晨，福建出現(xiàn)了中小學(xué)生被犯罪分子砍殺的惡性殺人事件。為了維護(hù)廣大中小學(xué)生的生命安全，某市公安部門要將學(xué)校安保工作納入綜合控制體系，加強(qiáng)社會(huì)嫌疑人員監(jiān)控與防范。要求在上下學(xué)高峰時(shí)段統(tǒng)籌派遣警力值勤護(hù)衛(wèi)，加強(qiáng)校園周邊巡邏與保衛(wèi)。在學(xué)生、幼兒上下學(xué)的重點(diǎn)時(shí)段，各所中小學(xué)、幼兒園附近道路上安排警員執(zhí)勤點(diǎn)，以做好應(yīng)急處置工作，對(duì)學(xué)校險(xiǎn)情進(jìn)行快速反應(yīng)，及時(shí)處置?，F(xiàn)有某區(qū)域內(nèi)學(xué)校分布如圖，各標(biāo)志點(diǎn)之間的道路為直線段。如果警員的執(zhí)勤點(diǎn)布置在標(biāo)志點(diǎn)，在接警后警員能以200米/分的速度趕往現(xiàn)場(chǎng)，根據(jù)學(xué)校人數(shù)的規(guī)模分類，各類學(xué)校要求盡可能在1分鐘之內(nèi)到達(dá)，第2類學(xué)校要求盡可能在2分鐘之內(nèi)能有第二名警員到達(dá)?，F(xiàn)在的問題是我們?cè)撛谀男?biāo)志點(diǎn)安排盡可能少的警員來(lái)維護(hù)各個(gè)學(xué)校的安全，還有就是如果執(zhí)勤點(diǎn)不限定在標(biāo)志點(diǎn)，我們又該如何安排警員執(zhí)勤以使得警員人數(shù)最少？二、模型的假設(shè)針對(duì)以上問題，我們提出以下合理假設(shè)：1、 警員在遇到險(xiǎn)情時(shí)，以200米/分鐘的速度勻速趕赴現(xiàn)場(chǎng)。2、 各相關(guān)學(xué)校不會(huì)在同一時(shí)間出現(xiàn)險(xiǎn)情。3、 學(xué)校的入口即為圖中學(xué)校標(biāo)志的位置。4、 題中所提供的數(shù)據(jù)為真實(shí)數(shù)據(jù)。5、 警員必須沿著圖中的道路走。三、符號(hào)說明如無(wú)特別說明，本文的符號(hào)具有以下意義：m,.:任意兩個(gè)標(biāo)志點(diǎn)，與j間的距離m:標(biāo)志點(diǎn)間的距離組成的距離矩陣n:標(biāo)志點(diǎn)的鄰接矩陣七：鄰接矩陣的元素。D:相鄰標(biāo)志點(diǎn)間的距離矩陣。D:相鄰標(biāo)志點(diǎn)i與j間的距離W:標(biāo)志點(diǎn)的權(quán)值矩陣d:標(biāo)志點(diǎn)間的最短距離矩陣七：標(biāo)志點(diǎn)i與j之間的最短距離。I:第一類學(xué)校順序值向量（列向量）J:第二類學(xué)校順序值向量（列向量）四、問題的分析本題所要解決的是19個(gè)學(xué)校以及周邊各個(gè)路段的警力分布問題，根據(jù)現(xiàn)實(shí)生活狀況，我們首先要考慮的是警力資源的限制，即要使得所布置的警力盡可能的少，其次是在警員數(shù)量最少的情況下，力求警員到達(dá)現(xiàn)場(chǎng)的時(shí)間盡可能的短，即要使得布置警力的標(biāo)志點(diǎn)與所負(fù)責(zé)的學(xué)校間的路程盡可能的短。所以我們要以警員數(shù)量的總和最少與警員所需要經(jīng)過的路程總和最小來(lái)考量警力布置的優(yōu)劣。根據(jù)題意，警員的執(zhí)勤點(diǎn)布置在標(biāo)志點(diǎn)，在接警后能以200米/分的速度趕往現(xiàn)場(chǎng)。各類學(xué)校要求盡可能在1分鐘之內(nèi)到達(dá)，第2類學(xué)校要求盡可能在2分鐘之內(nèi)能有第二名警員到達(dá)。也就是說，所有學(xué)校與它最近的一個(gè)警員布置點(diǎn)的距離都不能超過200米，以1:250的比例結(jié)算（即250米為一個(gè)單位），二者間的最短距離要小于0.8個(gè)單位。第二類學(xué)校還要在400米以內(nèi)有另外一個(gè)警力布置點(diǎn)，以1:250的比例結(jié)算，二者間的最短距離要小于1.6個(gè)單位。我們可以據(jù)此而將學(xué)校分為兩類，第一類為只需要一個(gè)警力的學(xué)校，第二類為需要兩個(gè)警力的學(xué)校。因此，我們必須先根據(jù)題中所給的數(shù)據(jù)計(jì)算出各標(biāo)志點(diǎn)兩兩之間的最短距離。然后在根據(jù)dj<0.8或寸司<1.6得到第一類學(xué)校和第二類學(xué)校周邊的有效標(biāo)志點(diǎn)。結(jié)合可能出現(xiàn)的一個(gè)警員負(fù)責(zé)多個(gè)學(xué)校（n>2）的情況，我們就可以利用線性優(yōu)化，設(shè)定0—1變量，從而得到是警員數(shù)量最少的模型，求出至少需要的警員數(shù)量。對(duì)于問題2和問題3,我們可以在實(shí)現(xiàn)警員人數(shù)最少的情況下求警員所要走的路線的路程最短，即對(duì)警員到達(dá)各個(gè)學(xué)校的總時(shí)間最短這一問題進(jìn)一步探究。四、模型的建立與求解目前，針對(duì)中小學(xué)生的暴力傷人事件越來(lái)越頻繁，各學(xué)校安全形勢(shì)越來(lái)越嚴(yán)峻。19個(gè)學(xué)校分布散亂，95個(gè)標(biāo)志點(diǎn)與各路段分布狀況復(fù)雜，而公安部門警力有限。如何在確保各學(xué)校安全的情況下，使得所需要的警員人數(shù)最少？如何使得警員到達(dá)現(xiàn)場(chǎng)的時(shí)間盡可能的短？

（一）問題1的求解：?jiǎn)栴}1要求解警員的最少數(shù)量，我們必須先根據(jù)題中所給的數(shù)據(jù)計(jì)算出各標(biāo)志點(diǎn)任意兩兩之間的最短距離。然后再根據(jù)匕＜0.8或匕＜1.6得到第一類學(xué)校和第二類學(xué)校周邊的有效標(biāo)志點(diǎn)。最后結(jié)合可能出現(xiàn)的一個(gè)警員負(fù)責(zé)多個(gè)學(xué)校（n＞2）的情況，利用線性優(yōu)化得到是警員數(shù)量最少的模型，求出至少需要的警員數(shù)量，同時(shí)還可以得到警員布置的初步方案。1、首先我們可以根據(jù)題中所給的各個(gè)標(biāo)志點(diǎn)的坐標(biāo)，用matlab計(jì)算出任意兩點(diǎn)之間的直線距離，得到95*95的距離矩陣：m1nmm1nm2nmm. .m= : :pm m m）2:根據(jù)題中的分布圖，我們可以得到各標(biāo)志點(diǎn)的鄰接矩陣:fn11 n12n21 n22. .\o"CurrentDocument"npm m m）2:根據(jù)題中的分布圖，我們可以得到各標(biāo)志點(diǎn)的鄰接矩陣:fn11 n12n21 n22. .\o"CurrentDocument"n= : :n2n，即如果兩個(gè)點(diǎn)相鄰，則鄰接矩陣中相對(duì)應(yīng)的元素頃n1 nn2的值為1，否則為0；例如：1和2這兩個(gè)點(diǎn)相鄰，那么n=n=1。12 213、根據(jù)Floyd算法，我們是要求出各標(biāo)志點(diǎn)任意兩兩之間的距離，所以我們需要得到相鄰兩個(gè)標(biāo)志點(diǎn)的直線距離。我們可以利用距離矩陣的元素m^與n〃的點(diǎn)乘積得到相鄰標(biāo)志點(diǎn)間的距離矩陣：儼11 D12……D]DD D21 22 2n\o"CurrentDocument"D=m.*n= :: .?. :PD D DJn1n2 nn4、我們可以將D中不相鄰點(diǎn)間距離0改為無(wú)窮大（Inf）從而得到標(biāo)志點(diǎn)與標(biāo)志點(diǎn)間的權(quán)值矩陣:I匕……匕]wW W21 22 2nw=: : :，即如果1和5之間不相鄰，也即不能直接到達(dá)，頃w w Jn1 n2 nn那么d中的D=0和D=0都將變成w和w等15 5115 51于無(wú)窮大（Inf）,否則則等于D中相應(yīng)元素的數(shù)據(jù)。5、運(yùn)用rd11d21算法求出任意兩點(diǎn)間最短距離，得到最短距離矩陣 d:….算法求出任意兩點(diǎn)間最短距離，得到最短距離矩陣 d:….…d2nFloyd

d.12d22n1 n2 nn二類是需要兩個(gè)警員的學(xué)校：根據(jù)題意，我們將學(xué)校分為兩類，第一類是只需要一個(gè)警員的學(xué)校，第二類是需要兩個(gè)警員的學(xué)校：I=（Ib七 Ip）二類學(xué)校順序值向量：J=（Jj七 Jp）7、根據(jù)上述分類，我們可以利用matlab編程，找到各學(xué)校及周邊的有效標(biāo)志點(diǎn)：距離第一類學(xué)校最短距離200米（0.8，表示0.8個(gè)有效單位，以下等同）以內(nèi)的標(biāo)點(diǎn)；距離各二類學(xué)校最短距離200米（0.8）以內(nèi)的標(biāo)點(diǎn)；距各二類學(xué)校最短距離400米（1.6）以內(nèi)的標(biāo)點(diǎn)，在以下表格中，我們稱有效點(diǎn)可安排警員維護(hù)相應(yīng)的學(xué)校的點(diǎn)。經(jīng)選擇得到：離一類學(xué)校200米的有效點(diǎn)（200）BBCSRSTWVWZYZA1B1K1J1K1N1M1N101U1S1T1U1V1G2G2H2N2N2R2Q2R2X2V2W2X2Y2I3I3J3P3G3P3

表（2）離二類學(xué)校200米的有效點(diǎn)（200）JIJKE1D1E1F1R1G1F1G1H1B2B2C2I2I2J2P2P2表（3）二類學(xué)校有效點(diǎn)（400）JFGHIJKLXYE1UVD1E1F1G1Q1R1S1T1G1VYD1E1F1G1H1I1B2P1Q1R1B2C2D2I2D2E2I2J2P2P2B3表（4）8、接下來(lái)，我們可以利用線性優(yōu)化與0—1變量，在各學(xué)校的有效點(diǎn)中選擇. . 11，取該有效點(diǎn)一個(gè)或兩個(gè)：]，取該有效點(diǎn)'，在此，B1表示B這個(gè)學(xué)校第一個(gè)有效點(diǎn)，即[0,不取該點(diǎn)B點(diǎn)；B2表示B這個(gè)學(xué)校第二個(gè)有效點(diǎn)，也即C點(diǎn)，根據(jù)以上表（1）、表（2）、表（3）、表（4）的數(shù)據(jù)，一一對(duì)應(yīng)起來(lái)，以此類推。我們利用lindo編寫模型一如下：目標(biāo)函數(shù)：MINB1+B2+S17+S18+S19+W21+W22+Z24+Z25+Z26+Z27+K135+K136+N138+N139+N140+U144+U145+U146+U147+G258+G259+N265+R268+R269+X273+X274+X275+X276+I386+I387+P384+P393+J5+J6+J7+J8+J9+J10+J11+J23+J24+E120+E121+E129+E130+E131+E132+E142+E143+E144+E145+G121+G124+G129+G130+G131+G132+G133+G134+B241+B242+B243+B253+B254+B255+I255+I256+I260+I261+P267+P279-2W21-2Z24-E129-E130-E131-E132-E142-E143-E144-E145-B255（因?yàn)椴煌膶W(xué)?？赡軙?huì)有同一個(gè)有效點(diǎn)，所以要減去相同有效點(diǎn)的個(gè)數(shù)）。約束條件B1+B2=1 !B這個(gè)學(xué)校要在B1（B點(diǎn)）或B2（C點(diǎn)）中的一個(gè)點(diǎn)上安排警員執(zhí)勤，以下等同。S17+S18+S19=1W21+W22=1Z24+Z25+Z26+Z27=1K135+K136=1N138+N139+N140=1U144+U145+U146+U147=1G258+G259=1N265=1R268+R269=1X273+X274+X275+X276=1I386+I387=1P384+P393=1J8+J9+J10=1E129+E130+E131+E143=1G131+G132+G133=1B253+B254=1I260+I261=1P267=1J5+J6+J7+J8+J9+J10+J11+J23+J24=2E120+E121+E129+E130+E131+E132+E142+E143+E144+E145=2G121+G124+G129+G130+G131+G132+G133+G134=2B241+B242+B243+B253+B254+B255=2I255+I256+I260+I261=2P267+P279=2W21-E121=0E121-G121=0Z24-J24=0J24-G124=0E129-G129=0E130-G130=0E131-G131=0E132-G132=0E142-B242=0E143-B243=0E144-U144=0E145-U145=0B255-I255=0ENDINT72利用lindo得到的結(jié)果為：得出至少需要的警員人數(shù)為：20并且得到初步的警員布置方案見表（5）（此處所得到的解不唯一）一類學(xué)校標(biāo)號(hào)對(duì)應(yīng)的執(zhí)勤點(diǎn)一類學(xué)校標(biāo)號(hào)對(duì)應(yīng)的執(zhí)勤點(diǎn)BCJJ(200)Y(400)STE1F1(200)S1(400)WWG1F1(200)Y(400)

ZYB2C2(200)D2(400)K1K1I2J2(200)D2(400)N1N1P2P2(200)B3(400)U1S1G2H2N2N2R2R2X2X2I3J3P3P3表（5）把表（5）中的點(diǎn)在圖中標(biāo)示出來(lái)，警員安排的位置在圖上便一目了然，如圖（1）所示（圖中綠色的鉆石點(diǎn)即為警員的安置點(diǎn)，且每個(gè)安置點(diǎn)只安排一個(gè)警員）：■或嫌唳圖（1）（二）問題2的求解對(duì)于問題1的模型，存在一個(gè)很嚴(yán)重的問題，即得到的警員執(zhí)勤點(diǎn)布置方案只是可行方案，并不是最優(yōu)方案，也不是唯一解。例如，對(duì)于學(xué)校B，既可以將執(zhí)勤點(diǎn)安排在B點(diǎn)或C點(diǎn)都可行。而從最優(yōu)的角度來(lái)看，應(yīng)該講警員執(zhí)勤點(diǎn)安排在B點(diǎn)，這樣警員才能在最短時(shí)間內(nèi)到達(dá)現(xiàn)場(chǎng)。所以，我們必須建立優(yōu)化模型來(lái)彌補(bǔ)這個(gè)缺陷。我們將模型一得到的結(jié)果，即“至少需要警員20名”作為一個(gè)約束條件，以所有警員趕赴險(xiǎn)情現(xiàn)場(chǎng)所經(jīng)過路程的總和最短為目標(biāo)函數(shù)，以實(shí)現(xiàn)警員趕赴險(xiǎn)情現(xiàn)場(chǎng)所需時(shí)間的總和最少，從而做到更合理地安排警員的執(zhí)勤位置，為此我們建立模型二如下：目標(biāo)函數(shù)：MIN！前面的系數(shù)為有效點(diǎn)與相應(yīng)的學(xué)校之間的距離0B1+0.54745B2+0.34828S17+0S18+0.24187S19+0.5346W21+0W22+0.68949Z24+0Z25+0.43658Z26+0.68837Z27+0.4272K135+0K136+0.2508N138+0N139+0.39115N140+0.74669U144+0.51865U145+0U146+0.47434U147+0G258+0.46325G259+0N265+0.31385R268+0R269+0.75655X273+0.41593X274+0X275+0.5016X276+0I386+0.43566I387+0.27P384+0P393+1.5968J5+1.1286J6+0.8066J7+0.57315J8+0J9+0.24597J10+1.0541J11+0.80632J23+1.5272J24+1.06E120+1.5385E121+0.32016E129+0E130+0.7737E131+1.5402E132+1.5049E142+0.75326E143+1.1651E144+1.3931E145+1.5314G121+1.4547G124+1.2201G129+1.5402G130+0.76655G131+0G132+0.52498G133+1.2566G134+1.0338B241+0.80362B242+1.5553B243+0B253+0.70178B254+1.4326B255+1.4524I255+1.1007I256+0I260+0.66611I261+0P267+1.32P279約束條件：B1+B2=1S17+S18+S19=1W21+W22=1Z24+Z25+Z26+Z27=1K135+K136=1N138+N139+N140=1U144+U145+U146+U147=1G258+G259=1N265=1R268+R269=1X273+X274+X275+X276=1I386+I387=1P384+P393=1J8+J9+J10>=1 !J8、J9和J10中的一個(gè)標(biāo)志點(diǎn)可能會(huì)安排兩個(gè)警員，以下等同E129+E130+E131+E143>=1G131+G132+G133>=1B253+B254>=1I260+I261>=1P267>=1J5+J6+J7+J8+J9+J10+J11+J23+J24=2E120+E121+E129+E130+E131+E132+E142+E143+E144+E145=2G121+G124+G129+G130+G131+G132+G133+G134=2B241+B242+B243+B253+B254+B255=2I255+I256+I260+I261=2P267+P279=2W21-E121=0E121-G121=0Z24-J24=0J24-G124=0E129-G129=0E130-G130=0E131-G131=0E132-G132=0E142-B242=0E143-B243=0E144-U144=0E145-U145=0B255-I255=0B1+B2+S17+S18+S19+W21+W22+Z24+Z25+Z26+Z27+K135+K136+N138+N139+N140+U144+U145+U146+U147+G258+G259+N265+R268+R269+X273+X274+X275+X276+I386+I387+P384+P393+J5+J6+J7+J8+J9+J10+J11+J23+J24+E120+E121+E129+E130+E131+E132+E142+E143+E144+E145+G121+G124+G129+G130+G131+G132+G133+G134+B241+B242+B243+B253+B254+B255+I255+I256+I260+I261+P267+P279-2W21-2Z24-E129-E130-E131-E132-E142-E143-E144-E145-B255=20ENDINT57利用lindo運(yùn)算，我們得到了最優(yōu)解(見表6)：學(xué)校標(biāo)號(hào)對(duì)應(yīng)的執(zhí)勤點(diǎn)一類學(xué)校標(biāo)號(hào)對(duì)應(yīng)的執(zhí)勤點(diǎn)BBJJ(200) Y(400)SSE1F1(200) T1(400)WWG1F1(200) Y(400)ZYB2B2(200) D2(400)K1K1I2I2(200) D2(400)N1N1P2P2(200) P2(400)U1T1G2G2N2N2R2R2X2X2I3I3P3P3表（6）我們得出的最優(yōu)配置點(diǎn)為：BJSWYF1K1N1T1B2D2G2I2N2P2R2X2I3P3（注：P3這個(gè)執(zhí)勤點(diǎn)要安排兩個(gè)警員）。同樣把這些點(diǎn)標(biāo)示在圖上，并與之前的圖（1）進(jìn)行比較，優(yōu)化的效果便清晰可見。如圖（2），紅圈中藍(lán)色的點(diǎn)為現(xiàn)在所得出的點(diǎn)，綠色的點(diǎn)是之前所計(jì)算出的點(diǎn)，紅圈之外的綠色點(diǎn)相對(duì)于圖（1）中的點(diǎn)沒有發(fā)生變化。我們可以看到，藍(lán)色點(diǎn)標(biāo)示的學(xué)校與執(zhí)勤點(diǎn)之間的距離有著明顯的縮小，達(dá)到了優(yōu)化的效果。圖（2）（三）問題三的求解在執(zhí)勤點(diǎn)布置不限定在標(biāo)志點(diǎn)，而是限定在道路上的情況下，我們要重新考慮如何設(shè)置執(zhí)勤點(diǎn)，并且使得警員人數(shù)最少。由于取消了標(biāo)志點(diǎn)，我們只需要計(jì)算學(xué)校與學(xué)校之間的距離即可，我們重新研究學(xué)校與學(xué)校之間的距離關(guān)系，并一一考慮它們之間的相互約束條件。為使得警員的數(shù)量盡可能的少，我們?cè)囅朐趦蓚€(gè)或三個(gè)學(xué)校之間的道路上只安排一個(gè)警員，且警員可以從安置點(diǎn)在一分鐘內(nèi)可以到達(dá)他所執(zhí)勤的學(xué)校。根據(jù)前面所計(jì)算出來(lái)的距離矩陣D，我們用MATLAB編程分別得到一類學(xué)校與一類學(xué)校的距離，一類學(xué)校與二類學(xué)校的距離，二類學(xué)校與二類學(xué)校的距離。在此，我們篩選出任意兩個(gè)學(xué)校與學(xué)校之間的距離小于1.6個(gè)單位的學(xué)校，一類學(xué)校與二類學(xué)校的距離小于2.4個(gè)單位的學(xué)校，二類學(xué)校與二類學(xué)校小于3.2個(gè)單位的學(xué)校，在這些學(xué)校間的中間區(qū)域，我們可以安排警員執(zhí)勤來(lái)兼顧道路兩頭的學(xué)校，為此，我們可利用線性優(yōu)化和0—1變量來(lái)解得哪些道路中間可以安排警員?；谏鲜龇治?，我們建立以下模型。建立模型三：MATLAB編程求得學(xué)校與學(xué)校間的距離小于1.6個(gè)單位的所有學(xué)校如下（運(yùn)行程序見附件）：W與乙E1與G1。MATLAB編程求得一類學(xué)校與二類學(xué)校間的距離小于2.4個(gè)單位的所有學(xué)校如下（運(yùn)行程序見附件）：W與E1，W與G1，Z與J，Z與G1，K1與G1，N1與B2，U1與E1。MATLAB編程求得二類學(xué)校與二類學(xué)校間的距離小于3.2個(gè)單位的所有學(xué)校如下（運(yùn)行程序見附件）：J與G1，E1與G1，E1與B2，B2與I2。在這些學(xué)校中，由于二類學(xué)校J、B2和I2沒有距離相隔小于1.6個(gè)單位的學(xué)校，所以這三個(gè)學(xué)校必須各自安排一個(gè)警員，我們只要考慮在兩分鐘內(nèi)第二個(gè)警員到達(dá)這三個(gè)學(xué)校的情況。不在以上三種情況內(nèi)的學(xué)校，我們不予考慮，它們的警員執(zhí)勤點(diǎn)位置相對(duì)于問題二中的位置不發(fā)生變化，即有B,S,G2,N2,P2,R2,X2,I3,P3這九個(gè)點(diǎn)的位置不發(fā)生變化。我們用WZ表示W(wǎng)與Z之間的道路，E1G1表示E1與G1之間的道路，依次類推。我們用0、1變量分別表示該路段上無(wú)警員執(zhí)勤點(diǎn)和有警員執(zhí)勤點(diǎn)，道路上安置的警員要滿足所有學(xué)校的需求。所需警員最少也便是所要設(shè)置執(zhí)勤點(diǎn)的道路數(shù)最少。因此，我們得出目標(biāo)函數(shù)：MINWZ+WE1+WG1+ZJ+ZG1+K1G1+N1B2+U1E1+JG1+E1G1+E1B2+B2I2約束條件：WZ+WE1+WG1>=1 ！對(duì)于W點(diǎn)，它是一類學(xué)校，所以這三條道路中至少有一條要設(shè)警員執(zhí)勤點(diǎn)，以此類推。WZ+ZJ+ZG1>=1E1G1>=1 !E1和G1都是二類點(diǎn)，且它們之間的距離小于1.6單位，所以它們之間需要安排警員。K1G1>=1N1B2>=1U1E1>=1ZJ+JG1>=1WE1+U1E1+E1B2>=1！對(duì)于E1點(diǎn)，它是二類學(xué)校，所以這三條道路中至少有一條要設(shè)警員執(zhí)勤點(diǎn)，以此類推。E1B2+B2I2>=1WG1+ZG1+K1G1+JG1>=1B2I2>=1ENDINT11求得所要設(shè)置警員執(zhí)勤的道路為：WZ,E1G1,K1G1,N1B2,U1E1,JG1,B2I2。綜上所述，總共所要設(shè)置的執(zhí)勤點(diǎn)的個(gè)數(shù)是：3（J、B2和I2這三個(gè)點(diǎn)）+9（不予考慮的點(diǎn)）+7（7條道路）=19，而所需要的警員數(shù)量是20個(gè)，因?yàn)镻3這個(gè)執(zhí)勤點(diǎn)需要兩個(gè)警員。求得的結(jié)果相對(duì)于問題2的結(jié)果表面上好像沒有什么改進(jìn)，雖然所需警員人數(shù)沒有變化，但執(zhí)勤點(diǎn)的位置有所變動(dòng)，并且警員的執(zhí)勤范圍為一個(gè)小區(qū)域，而不再是一個(gè)點(diǎn)，這樣使得執(zhí)勤的秩序更為有效，人員調(diào)配上也更為靈活。五、模型的評(píng)價(jià)與改進(jìn)優(yōu)點(diǎn)：1、 、對(duì)于給出的大量的數(shù)據(jù)，我們首先對(duì)數(shù)據(jù)進(jìn)行處理，將其轉(zhuǎn)化為有用的數(shù)據(jù)，如：附件中的各點(diǎn)的坐標(biāo)轉(zhuǎn)化為點(diǎn)與點(diǎn)之間的距離。2、 模型建立的思路簡(jiǎn)單清晰，并且可以得到很好的效果。3、 模型的假設(shè)很符合實(shí)際生活，以致模型可以很好的運(yùn)用于相對(duì)應(yīng)得實(shí)際生活中。不足：1、沒有考慮特殊情況在內(nèi)，如：遇到不可抗力，多個(gè)學(xué)校同時(shí)發(fā)生險(xiǎn)情等可能性。2、在第3問中，模型沒有給出道路上的警員的具體范圍。五、參考文獻(xiàn)樓世博、金曉龍、李鴻祥等，圖論及其應(yīng)用，北京：人民郵電出版社，1982年王樹禾，圖論，北京：科學(xué)出版社，2004年左孝凌、劉永才等，離散數(shù)學(xué)，上海：上海科學(xué)技術(shù)文獻(xiàn)出版社，1982年林雪松、林德新等，MATLAB7.0應(yīng)用集錦，北京：機(jī)械工業(yè)出版社，2006年附件：dist(x,y)求任意兩點(diǎn)距離functionm=dist(a,b)%a為橫坐標(biāo)，b為縱坐標(biāo),且均默認(rèn)為列向量;fori=1:size(a,1)forj=1:size(b,1)m(i,j)=((a(i)-a(j))八2+(b(i)-b(j))⑵八0.5;endendtow(m) 將距離向量轉(zhuǎn)為權(quán)向量functionw=tow(m)fori=1:size(m,1)forj=1:size(m,2)ifm(i,j)==0m(i,j)=inf;endendendm%floyd.m%采用floyd算法計(jì)算圖a中每對(duì)頂點(diǎn)最短路%d是矩離矩陣%r是路由矩陣function[d,r]=floyd(a)n=size(a,1);d=a;fori=1:nforj=1:nr(i,j)=j;endendr;fork=1:nfori=1:nforj=1:nifd(i,k)+d(k,j)<d(i,j)d(i,j)=d(i,k)+d(k,j);r(i,j)=r(i,k);endendend%k%d%rend學(xué)校一類一類BSZK1N1U1G2N2R2X2I3P3[1182225363946586569758693]二類JE1G1B2I2P2[93032536067]求有效點(diǎn)0.8以內(nèi)functionA=place(I,d)A=zeros(size(I,1),10);fori=1:size(I,1)k=1;forj=1:size(d,2)ifd(I(i),j)<=0.8A(i,k)=j;k=k+1;endendend求有效點(diǎn)1.6以內(nèi)functionB=place1(J,d)B=zeros(size(J,1),15);fori=1:size(J,1)k=1;forj=1:size(d,2)ifd(J(i),j)<=1.6B(i,k)=j;k=k+1;endendend檢查鄰接矩陣是否對(duì)稱functionDE=jian(a)DE=zeros(size(a,1),2);fori=1:size(a,1)forj=1:size(a,1)ifa(i,j)?=a(j,i)DE(i,1)=i;DE(i,2)=j;endendendLINDO求最少的警員人數(shù)，及警員初步的分布(不是最佳的分布)MINB1+B2+S17+S18+S19+W21+W22+Z24+Z25+Z26+Z27+K135+K136+N138+N139+N140+U144+U145+U146+U147+G258+G259+N265+R268+R269+X273+X274+X275+X276+I386+I387+P384+P393+J5+J6+J7+J8+J9+J10+J11+J23+J24+E120+E121+E129+E130+E131+E132+E142+E143+E144+E145+G121+G124+G129+G130+G131+G132+G133+G134+B241+B242+B243+B253+B254+B255+I255+I256+I260+I261+P267+P279-2W21-2Z24-E129-E130-E131-E132-E142-E143-E144-E145-B255STB1+B2=1S17+S18+S19=1W21+W22=1Z24+Z25+Z26+Z27=1K135+K136=1N138+N139+N140=1U144+U145+U146+U147=1G258+G259=1N265=1R268+R269=1X273+X274+X275+X276=1I386+I387=1P384+P393=1J8+J9+J10=1E129+E130+E131+E143=1G131+G132+G133=1B253+B254=1I260+I261=1P267=1J5+J6+J7+J8+J9+J10+J11+J23+J24=2E120+E121+E129+E130+E131+E132+E142+E143+E144+E145=2G121+G124+G129+G130+G131+G132+G133+G134=2B241+B242+B243+B253+B254+B255=2I255+I256+I260+I261=2P267+P279=2W21-E121=0E121-G121=0Z24-J24=0J24-G124=0E129-G129=0E130-G130=0E131-G131=0E132-G132=0E142-B242=0E143-B243=0E144-U144=0E145-U145=0B255-I255=0ENDINT72求各有效點(diǎn)到各個(gè)學(xué)校的最短距離functionw=fild(I,J,d)w=zeros(size(I,1),size(J,2));fori=1:size(I,1)forj=1:size(J,2)ifJ(i,j)?=0endw(i,j)=d(I(i),J(i,j));endendendLINDO在警員人數(shù)最少的基礎(chǔ)上求警員所走行程最短的點(diǎn)MIN0B1+0.54745B2+0.34828S17+0S18+0.24187S19+0.5346W21+0W22+0.68949Z24+0Z25+0.43658Z26+0.68837Z27+0.4272K135+0K136+0.2508N138+0N139+0.39115N140+0.74669U144+0.51865U145+0U146+0.47434U147+0G258+0.46325G259+0N265+0.31385R268+0R269+0.75655X273+0.41593X274+0X275+0.5016X276+0I386+0.43566I387+0.27P384+0P393+1.5968J5+1.1286J6+0.8066J7+0.57315J8+0J9+0.24597J10+1.0541J11+0.80632J23+1.5272J24+1.06E120+1.5385E121+0.32016E129+0E130+0.7737E131+1.5402E132+1.5049E142+0.75326E143+1.1651E144+1.3931E145+1.5314G121+1.4547G124+1.2201G129+1.5402G130+0.76655G131+0G132+0.52498G133+1.2566G134+1.0338B241+0.80362B242+1.5553B243+0B253+0.70178B254+1.4326B255+1.4524I255+1.1007I256+0I260+0.66611I261+0P267+1.32P279STB1+B2=1S17+S18+S19=1W21+W22=1Z24+Z25+Z26+Z27=1K135+K136=1N138+N139+N140=1U144+U145+U146+U147=1G258+G259=1N265=1R268+R269=1X273+X274+X275+X276=1I386+I387=1P384+P393=1J8+J9+J10>=1E129+E130+E131+E143>=1G131+G132+G133>=1B253+B25