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