20xx全國數學建模競賽b題優秀論文(編輯修改稿)

　

【文章內容簡介】 時間大于 3分鐘時，損失時間 =到達時間 3。即 0 , 3= 3,im jt o th e r w is e??? ???到 達 時 間 不 超 過 分 鐘損 失 時 間 其中， 1mjt 表示 A 區 m 號平臺到 j 號節點的最短時間， 1,2,...,92j ? ? 管轄范圍和事故發生地的界定 A 區的交通網絡由路口節點與連通節點的各個路段組成，在管轄范圍的劃分時我們必須考慮節點、路段如何歸屬的問題。我們定義路段 (, )Qi j （ ij? ）是由節點 i 和節點 j 連通而成的路段，路段中間不存在節點 。 考慮事故發生地的界定，當事故發生在路口節點 i 時，我們認為事故發生地即為節點 i ； 當事故發生在路段 (, )Qi j （ ij? ） 時，考慮路段長度一般較小，簡化處理，認為事故發生地為節點 i 。這樣即把事故的發生地統一于路口節點。 考慮節點、路段的歸屬范圍，當平臺 m 管轄節點 i 時，我們認為平臺 m 管轄路段 (, )Qi j （ ij? ） ，這樣，一旦路口節點 i 的管轄范圍確定下來，路段 (, )Qi j 的管轄范圍也隨之確定下來，即把管轄范圍的歸屬問題轉化為節點的劃分歸屬問題。 基于以上考慮，我們 只要給出 A 區 20 個平臺管轄路口節點的方案，即完成了平臺的管轄范圍分配。 ? 建立罰函數 題目中要求事故發生后平臺警力到達時間盡量不超過 3 分鐘，這個是解決問題的關鍵約束條件。首先，我們將其作為緊約束建立以 所有平臺到各個管轄節點總時間最小為目標函數的優化模型，經過檢驗發現約束過強導致模型無解，從圖1中分析原因可知，交通網絡中部分路段（如 1416,1528,1529）過長，無論如何分配，必存在個別節點到周圍的任意平臺的路段長超過 3000m,如節點 28只與節點 29（未設置平臺）、 15（設置平臺）連通，節點 28只能 歸平臺 15 管轄，但路段 2815 長度為 4750m(3000m),故無論如何分配，管轄節點 28的平臺到達該節點的時間都大于 3 分鐘，不滿足要求。 因此，我們利用 罰函數法 [3] 求解該模型（該模型實際上為帶約束的非線形規劃問題），其思想是：利用問題的原目標函數和損失時間約束函數構造出增廣目 10 標函數，把該問題轉化為不考慮損失時間約束的非線形規劃問題來求解。 增廣目標函數由兩個部分構成，一部分是原目標函數，另一部分是由損失時間約束函數構造出的“懲罰”項，“懲罰”項的作用是 對“到達時間超出 3 分鐘”的點進行“懲罰”。我們采用外部罰函數法，這種方法的迭代點一般在可行域的外部移動，隨著迭代次數的增加，“懲罰”的力度也越來越大，從而迫使迭代點向可行域靠近。 我們設法加大不可行點處對應的目標函數值，使不可行點不能成為非線性約束問題的最優解，于是對于可行域基于損失時間作一懲罰函數，如下： 1110 , 3 m in 1 , 2 , . . . , 2 0 1 , 2 , . . . , 9 21 0 ( 3 ) , 3 m inmjmj i m j m jtf m jtt???? ? ?????? 其中，1mjt表示 A 區 m 號平臺到 j 號節點的最短時間， 1,2,...,92j ? 如果損失時間大于 0，則以 10 倍的損失時間 10( 3)imjt ? 作為“懲罰”項對“到達時間超出 3 分鐘”的點進行“懲罰”；如果損失時間為 0，則說明到達時間不超出 3 分鐘，不予懲罰。 模型建立 決策變量 題目中關鍵是確定路口節點的分配方案，即節點 j 是否屬于 1m 服務平臺管轄，服務 平臺編號 km 表示第 k 區的第 m 個服務平臺， 1,2,...,6k? 分別代表 6 個城區，故模型的決策變量為 1 1 , 1 , 1 , 2 , . . . , 2 00,mj jmWmo th e r w is e????? 號 路 口 節 點 由 號 平 臺 管 轄 增廣目標函數 題目要求當服務平臺管轄的范圍內出現突發事件時，交巡警盡量能在 3 分鐘內到達事發地。從全區的服務平臺服務情況考慮，取所有平臺到各個節點的總時間最小為目標函數，同時考慮 損失時間約束函數構造出增廣目標函數，利用外部罰函數法對“到達時間超出 3 分鐘”的點進行“懲罰”。增廣目標函數如下： 2 0 9 2 2 0 9 2111 1 1 1m in m j m jm j m jtf? ? ? ??? ? ? ? 其中， （ 1） 1mjt 表示 1m 號平臺到 j 號節點的最短時間， 1,2,...,92j ? 1,2,...,20m? （ 2） 1mjf 表示 1m 號平臺 到 j 號節點的損失時間的懲罰函數， 1,2,...,92j ? 1,2,...,20m? 約束條件 11 ? 服務平臺數量限制 A區的交巡警服務平臺共 20 個，約束如下： 9211 2 0 1 , 2 , .. ., 2 0 1 , 2 , .. ., 9 2mjj W m j? ? ? ?? ? 事故管轄權歸屬限制 我們認為一起事故僅由管轄該事故發生地的服務平臺負責解決，即每一個路口節點僅有一個服務平臺 管轄，約束如下： 2011 1 1 , 2 , . . . , 2 0 1 , 2 , . . . , 9 2mjm W m j? ? ? ?? ? 事故發生地到達時間限制 此為該問題的關鍵限制條件。事故發生后，管轄該路口節點的服務平臺盡量在 3 分鐘內派出 交巡警到達現場。根據前面對此限制條件的分析，我們利用罰函數法將此約束放到目標函數中，罰函數如下： 11 1 , 2 , . . . , 2 0 1 , 2 , . . . , 9 2m j j m jim j MWt m jv???? ? ? 1110 , 3 m in 1 , 2 , . . . , 2 0 1 , 2 , . . . , 9 23 , 3 m inmjmj i m j m jtf m jtt???? ? ?????? 其中， （ 1） j? 表示 j 號節點是 否有人報警， 1,2,...,92j ? （ 2） 1mjM 表示 1m 號平臺到 j 號節點的最短距離， 1,2,...,92j ? （ 3） v 表示每輛警車的時速， 60 /v km h? ? 綜上所述，我們給出平臺管轄范圍分配模型 [4] ，如下： 12 20 92 20 92111 1 1 111192112011111m i n0 , 3 m i n1 , 2 , ..., 20 1 , 2 , ..., 923 , 3 m i n20 1 , 2 , ..., 20 1 , 2 , ..., 92.. 1 1 , 2 , ..., 20 1 , 2 , ..., 921 , 2 , ..m j m jm j m jmjmjim j m jmjjmjmm j j m jmjtftf m jttW m jst W m jMWtmv?? ? ? ???????? ? ??????? ? ?? ? ?????? ? ? ???1., 20 1 , 2 , ..., 921 , 1 , 2 , ..., 20 1 , 2 , ..., 92mjjW i f m j m j???????????? ???? ? ? ???? 其中， （ 1） j? 表示 j 號節點是否有人報警， 1,2,...,92j ? （ 2） 1mjM 表示 1m 號平臺到 j 號節點的最短距離， 1,2,...,92j ? （ 3） v 表示每輛警車的時速， 60 /v km h? （ 4） 1mjt 表示 A 區 m 號平臺到 j 號節點的最短時間， 1,2,...,92j ? （ 5） 1 1 , 1 , 1 , 2 , . . . , 2 00,mj jmWmo th e r w is e????? 號 路 口 節 點 由 號 平 臺 管 轄 （ 6） 1mjf 為罰函數， 1110 , 3 m in 1 , 2 , . . . , 2 0 1 , 2 , . . . , 9 23 , 3 m inmjmj im j m jtf m jtt???? ? ?????? 模型求解 對上述模型利用 lingo 軟件 [5] 求解（代碼見附錄 3），其中 1mjM 表示 1m 號平臺到 j 號節點的最短距離， 1,2,...,92j ? ，可由 dijskstra 算法得到（見附 錄 2）。最終計算結果數據及平臺管轄范圍方案（見表 1），下給出分配方案的示意圖（圖2）。 13 圖 2 A 區平臺管轄范圍分配方案 表 1 各平臺的管轄范圍分配 平臺編號 所管轄節點編號 1 1， 67,68,69,71,73,74,75,76,78 2 2， 39,40,43