2011年全國數(shù)學建模競賽試卷68組

1、2011 高教社杯大學生數(shù)學建模競賽承諾書仔細閱讀了學生數(shù)學建模競賽的競賽規(guī)則.完全明白，在競賽開始后參賽隊員不能以任何方式（包括、電子郵件、網(wǎng)上等）與隊外的任何人（包括指導教師）研究、與賽題有關。知道，別人的成果是競賽規(guī)則的, 如果別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文處和參考文獻中明確列出。鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。競賽規(guī)則的行為，受到嚴肅處理。參賽選擇的題號是（從A/B/C/D 中選擇一項填寫）：B的參賽報名號為（如果賽區(qū)設置報名號的話）：0868所屬學校（請?zhí)顚懲暾娜汗枮I市工程大學參賽隊員 (打印并

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

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

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

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

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

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

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

9、量后，最終確定各交巡圍，如下圖：務的管轄范交巡務管轄范圍分布圖：表示交巡務管轄范圍分布表3.2調(diào)度3.2.1 模型的假設分區(qū)原則。交巡追求最優(yōu)原則。交巡口。務只自己管轄范圍內(nèi)的道口。在一定范圍內(nèi)選擇最短路徑，用最少的時間務路3.一一原則。一個交巡務只一個道口。4.交巡警以平均速度 60km/h 行駛，無堵車、拋錨等意外停車。交巡警所在節(jié)點序號管轄節(jié)點序號交巡警所在節(jié)點序號管轄節(jié)點序號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 定義符號說明U： V：被節(jié)點集合， 道口節(jié)點集合，Y：其它節(jié)點集合，d(，d(： 到 的距離，3.2.3 模型的建立及求解。在給定的交通網(wǎng)絡中，每個頂點代表一個路口，每一條線段代表一條公路，把交通網(wǎng)絡簡化、抽象成幾何圖形，把問題轉(zhuǎn)化成求從 20 個交巡務待選點中選出 13 個點到另

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

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

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

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