2011年全國(guó)數(shù)學(xué)建模競(jìng)賽試卷68組

1、2011 高教社杯大學(xué)生數(shù)學(xué)建模競(jìng)賽承諾書仔細(xì)閱讀了學(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的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）：0868所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜汗枮I市工程大學(xué)參賽隊(duì)員 (打印并

2、簽名) ：1.2.3. 指導(dǎo)教師或指導(dǎo)教師組(打印并簽名)：日期： 2011 年 9 月 12 日賽區(qū)評(píng)閱（由賽區(qū)評(píng)閱前進(jìn)行）：2011 高教社杯大學(xué)生數(shù)學(xué)建模競(jìng)賽頁(yè)賽區(qū)評(píng)閱（由賽區(qū)評(píng)閱前進(jìn)行）：賽區(qū)評(píng)閱（可供賽區(qū)評(píng)閱時(shí)使用）：（由賽區(qū)送交前）：評(píng)閱（由評(píng)閱前進(jìn)行）：評(píng)閱人評(píng)分備注交巡務(wù)的設(shè)置與調(diào)度摘要本文針對(duì)交巡務(wù)的設(shè)置、管轄范圍和調(diào)度警務(wù)資源問題，建立目標(biāo)規(guī)劃模型、層次分析模型和動(dòng)態(tài)規(guī)劃模型，并用LINGO求解，給出了一定方案。問題一：1）交巡務(wù)管轄范圍的分配，運(yùn)用層次分析模型，先從考慮3分鐘出警可到達(dá)事發(fā)地，初步確定管轄范圍，然后考慮工作量分配均衡問題，最終確定20個(gè)管轄范圍；2）調(diào)度問

3、題，運(yùn)用動(dòng)態(tài)規(guī)劃模型，轉(zhuǎn)變成從20個(gè)已知中選出13個(gè)和另外13個(gè)已知被封路口組成一一對(duì)應(yīng)且距離和最短問題，在8分鐘內(nèi)可以將13條出入A去的要道全部；3）增加個(gè)數(shù)和位置問題，運(yùn)用比較模擬法，在第一問的基礎(chǔ)上，已劃分出20個(gè)管轄區(qū)進(jìn)行相互比較，從而到出警時(shí)間長(zhǎng)和工作量不均衡的轄區(qū)，進(jìn)而增加4，提高工作效率。4 個(gè)新增位置問題二：1）分析該市現(xiàn)有交巡務(wù)設(shè)置方案的合理性，從的數(shù)量和位置上分別入手，首先構(gòu)造一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)，判斷出的數(shù)量明顯不夠，需增加的位置進(jìn)行驗(yàn)證，用LINGO29個(gè)；然后建立目標(biāo)規(guī)劃模型，對(duì)原解出他們是可行解。針對(duì)不合理的地方，給出了解決方案，即新增29個(gè)的位置分布圖；2）調(diào)度方案，先確

4、定3分鐘后嫌疑人的蹤跡范圍，進(jìn)行3種情況分類，將交通網(wǎng)絡(luò)簡(jiǎn)化成圖論中幾何路線問題，用最小距離法，確定方案，圍堵時(shí)間：13分鐘 ，最小面積：4平方公里。：交巡務(wù)，動(dòng)態(tài)規(guī)劃，調(diào)度優(yōu)化，圖論點(diǎn)序號(hào)XY29246337483153746639836291445380目錄摘要1一、問題重述3二、問題分析3三、模型的建立與求解43.1 交巡務(wù)管轄范圍43.1.1 模型的建立及求解4調(diào)度6模型的假設(shè)6定義符號(hào)說明7模型的建立及求解7增加個(gè)數(shù)及位置93.3.1 模型的建立及求解93.23.3務(wù)設(shè)置方案合理性103.4 交巡模型的假設(shè)10定義符號(hào)說明10模型的建立及求解11方案12模型的假設(shè)12模型的建立及求解

5、133.5四、模型的推廣14五、模型的評(píng)價(jià)與優(yōu)化14六、參考文獻(xiàn)15一、 問題的重述有某一城市在市區(qū)的一些交通要道和重要部位設(shè)置交巡務(wù)。且假設(shè)每個(gè)交巡務(wù)的職能和配備基本相同。由于警務(wù)資源是有限的，須根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡務(wù)、分配各的管轄范圍、調(diào)度警務(wù)資源?，F(xiàn)已知該市A 區(qū)及全市 6 區(qū)交通網(wǎng)絡(luò)與有如下問題需要解決：設(shè)置示意圖。交巡警的時(shí)速為 60km/h。（1） 請(qǐng)為該市中心城區(qū) A 的交通網(wǎng)絡(luò)和現(xiàn)有的 20 個(gè)交巡務(wù)分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在 3 分鐘內(nèi)有交巡警到達(dá)事發(fā)地。突發(fā)事件發(fā)生，需要調(diào)度全區(qū) 20 個(gè)交巡務(wù)的的資源，對(duì)進(jìn)出該區(qū)的 13

6、條交通要道實(shí)現(xiàn)快速全。在實(shí)際中一個(gè) 的最合理的方案。，現(xiàn)須確定增加最多一個(gè)路口的情況下，給出調(diào)度交巡務(wù)擬在該區(qū)內(nèi)再增加 2 至 5 個(gè)的具體個(gè)數(shù)和位置，以解決各交巡務(wù)的工作量不均衡和有些地方出警時(shí)間過長(zhǎng)。（2） 針對(duì)全市的具體情況，按照設(shè)置交巡務(wù)的原則和任務(wù)，分析研究該市現(xiàn)有交巡務(wù)設(shè)置方案的合理性。如果有明顯不合理，給出解決方案。該市地點(diǎn) P（第 32 個(gè)節(jié)點(diǎn)）處發(fā)生了，在案發(fā) 3 分鐘后接到，嫌疑人已駕車逃跑。給出調(diào)度全市交巡疑犯。務(wù)資源的最佳方案，以快速搜捕嫌二、 問題分析（1） 要確定各交巡務(wù)得管轄范圍，首要考慮的一點(diǎn)是，在 3 分鐘內(nèi)有交巡警可以到達(dá)事發(fā)地，即其最遠(yuǎn)行程為 3 公里（極

7、個(gè)別道口節(jié)點(diǎn)除外）。以此條件能夠初步確定各的管轄范圍。接下來進(jìn)一步思考工作量的分配問題，應(yīng)盡量使個(gè)工作量均衡分配，從而可精確劃分管轄范圍。調(diào)度問題：13 交通條要道，即13 個(gè)出入A 區(qū)的路口。調(diào)度 20 個(gè)交巡務(wù)的進(jìn)行，可轉(zhuǎn)變成從 20 個(gè)已知待選點(diǎn)中選出 13 個(gè)點(diǎn)到另外 13 個(gè)已知點(diǎn)的最短距離一一對(duì)應(yīng)且距離最小的圖論問題。確定增加個(gè)數(shù)和位置問題：對(duì)現(xiàn)有交巡確定出新增務(wù)的工作量不均衡和出警的個(gè)數(shù)與位置。時(shí)間過長(zhǎng)進(jìn)行分析，通過圖表對(duì)比，（2）分析該市現(xiàn)有交巡和位置進(jìn)行分析，根據(jù)交巡務(wù)務(wù)設(shè)置方案的合理性問題：從的數(shù)量的原則和任務(wù)確定一個(gè)參考標(biāo)準(zhǔn)，比較算出該市應(yīng)設(shè)置多少，進(jìn)而建立目標(biāo)規(guī)劃模型，

8、驗(yàn)證已有位的可行性，對(duì)明顯不合理的地方，給出解決方案。問題：案發(fā)后 3 分鐘，確定出嫌疑人可能逃逸到的地方，進(jìn)行分類討論，進(jìn)而設(shè)計(jì)方案，運(yùn)用圖論最短路徑法，確定方案。三、 模型的建立與求解3.1 交巡務(wù)管轄范圍3.1.1 模型的建立及求解運(yùn)用層次分析法為交巡務(wù)分配管轄范圍，首先考慮交巡警可在 3 分鐘到達(dá)事發(fā)地，即最遠(yuǎn)行程 3 公里，初步確定各的管轄范圍。再考慮由于各節(jié)點(diǎn)的發(fā)案率不同，導(dǎo)致工作量的不同這一問題，進(jìn)一步確定各的管轄范圍。圖表1 各3 分鐘能到達(dá)地方分布圖：表示3 分鐘能到達(dá)地方。由于各初定管轄范圍內(nèi)的發(fā)案率不同，僅考慮最遠(yuǎn)行程是不夠的，還要考慮各區(qū)的工作量是否均衡，在平衡各區(qū)工作

9、量后，最終確定各交巡圍，如下圖：務(wù)的管轄范交巡務(wù)管轄范圍分布圖：表示交巡務(wù)管轄范圍分布表3.2調(diào)度3.2.1 模型的假設(shè)分區(qū)原則。交巡追求最優(yōu)原則。交巡口。務(wù)只自己管轄范圍內(nèi)的道口。在一定范圍內(nèi)選擇最短路徑，用最少的時(shí)間務(wù)路3.一一原則。一個(gè)交巡務(wù)只一個(gè)道口。4.交巡警以平均速度 60km/h 行駛，無堵車、拋錨等意外停車。交巡警所在節(jié)點(diǎn)序號(hào)管轄節(jié)點(diǎn)序號(hào)交巡警所在節(jié)點(diǎn)序號(hào)管轄節(jié)點(diǎn)序號(hào)11、67、68、69、71、73、741111、26、2722、40、43、44、70、721212、2533、54、55、65、66、 、 、4、57、60、62、63、641414、2155、49、52、53

10、、561515、28、2966、47、50、51、58、59、 、 、7、30、48、611717、41、4288、32、33、45、461818、81、82、83、84、89、9099、31、34、35、371919、75、76、77、78、79、8010102020、85、86、87、88、91、923.2.2 定義符號(hào)說明U： V：被節(jié)點(diǎn)集合， 道口節(jié)點(diǎn)集合，Y：其它節(jié)點(diǎn)集合，d(，d(： 到 的距離，3.2.3 模型的建立及求解。在給定的交通網(wǎng)絡(luò)中，每個(gè)頂點(diǎn)代表一個(gè)路口，每一條線段代表一條公路，把交通網(wǎng)絡(luò)簡(jiǎn)化、抽象成幾何圖形，把問題轉(zhuǎn)化成求從 20 個(gè)交巡務(wù)待選點(diǎn)中選出 13 個(gè)點(diǎn)到另

11、外已知 13 個(gè)定點(diǎn)的最短距離問題。和被封道口交通網(wǎng)絡(luò)的簡(jiǎn)化圖說明：1)：表示出入A 城區(qū)的路口節(jié)點(diǎn)。2)：表示交巡務(wù)的設(shè)置點(diǎn)。3)4)5)：表示設(shè)有交巡圖形中數(shù)字表示節(jié)點(diǎn)序號(hào)。務(wù)的出入A 城區(qū)的路口節(jié)點(diǎn)。線段上數(shù)字表示相鄰兩節(jié)點(diǎn)的距離，為毫米，比例尺為 1:100000。目標(biāo)函數(shù)：mind(= d(+= d(+= d(+U=1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19， 20（節(jié)點(diǎn)）V=12，14，16，21，22，23，24，28，29，30，38，48，62（節(jié)點(diǎn)）用 LINGO經(jīng)計(jì)算結(jié)果如下：到結(jié)論：最快 8 分鐘內(nèi)完成。3.3增加個(gè)數(shù)

12、及位置3.3.1 模型的建立及求解A 區(qū)發(fā)案率分布A 區(qū)新增分布圖：新增加的交巡務(wù)A 區(qū)新增5 個(gè)，位置如下：3.4 交巡務(wù)設(shè)置方案合理性3.4.1 模型的假設(shè)1.每個(gè)交巡務(wù)的配置基本相同。2.接到無延遲出警。3.4.2 定義符號(hào)說明點(diǎn)序號(hào)XY29246337483153746639836291445380A(k),B(k),，F(xiàn)(k):A 區(qū)，B 區(qū)，F(xiàn) 區(qū)的節(jié)點(diǎn)3.4.3 模型的建立及求解1.個(gè)數(shù)合理性評(píng)判標(biāo)準(zhǔn)該市設(shè)置方案由上表對(duì)比可看出：該市的平均處理率、管轄路程、節(jié)點(diǎn)覆蓋數(shù)均大于指標(biāo)，明顯數(shù)量設(shè)置不合理，應(yīng)增加個(gè)數(shù)。增加數(shù)目后設(shè)置方案增加后，幾個(gè)指標(biāo)接近標(biāo)準(zhǔn)指標(biāo)，從而確定該方案合理。2

13、.位置評(píng)判目標(biāo)函數(shù)：總時(shí)間=巡邏時(shí)間+出警處理時(shí)間約束條件：，i，j 在同一區(qū)路程發(fā)案率節(jié)點(diǎn)數(shù)數(shù)平均處理率平均管轄路程平均覆蓋節(jié)點(diǎn)數(shù)15306.43674.55821096.114km5.3路程發(fā)案率節(jié)點(diǎn)數(shù)數(shù)平均處理率平均管轄路程平均覆蓋節(jié)點(diǎn)數(shù)15306.43674.5582808.4312519km7.3平均處理率平均管轄路程平均覆蓋節(jié)點(diǎn)數(shù)615km5.5V=60km/h簡(jiǎn)化模型后：將已知 80 個(gè)的信息代入上式，經(jīng) LINGO 計(jì)算是可行解，說明該市現(xiàn)安排的交巡務(wù)的位置合理。綜上給出新的解決方案，即新增 29 個(gè)位置分布圖，如下：29 個(gè)：新增加位置3.5方案3.5.1 模型的假設(shè)1.嫌疑

14、人駕車逃逸始終在行駛。2.嫌疑人車速與交巡速相當(dāng)（60km/h）。3.交巡警在過程中，無堵車、撞車、拋錨等意外事件。4.交巡警不可跨區(qū)追捕、。3.5.2 模型的建立及求解嫌疑人駕車行駛 3 分鐘后，以節(jié)點(diǎn) 32 為圓心，半徑為 3 公里畫圓，確定區(qū)、3他可能出現(xiàn)的地方，他不會(huì)超出此范圍，區(qū)，如下圖：此區(qū)域分為三個(gè)部分，1 區(qū)、2進(jìn)而對(duì)此進(jìn)行，對(duì)每一種情況給出方案，采用圖論最小距離進(jìn)行。1 區(qū)3 區(qū)本文使用篩選、排除法，有效地減少了數(shù)據(jù)的處理，建立常見的規(guī)劃模型，很方便地求出結(jié)果。對(duì)于復(fù)雜的交通網(wǎng)絡(luò)問題轉(zhuǎn)化為數(shù)學(xué)中常見的圖論問題，化繁為簡(jiǎn)，主次分明，使計(jì)算方便快捷。5.2 缺點(diǎn)：1 本文幾處采用近似計(jì)算，對(duì)