基于圖論和非線(xiàn)性規(guī)劃求最佳搜救路線(xiàn)問(wèn)題數(shù)學(xué)模型

1、 2014年河南科技大學(xué)模擬訓(xùn)練一承 諾 書(shū)我們仔細(xì)閱讀了數(shù)學(xué)建模選拔賽的規(guī)則.我們完全明白，在做題期間不能以任何方式（包括電話(huà)、電子郵件、網(wǎng)上咨詢(xún)等）與隊(duì)外的任何人研究、討論與選拔題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反選拔規(guī)則的, 如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守選拔規(guī)則，以保證選拔的公正、公平性。如有違反選拔規(guī)則的行為，我們將受到嚴(yán)肅處理。我們選擇的題號(hào)是（從A/B/C中選擇一項(xiàng)填寫(xiě)）： C 隊(duì)員簽名 ：1. 王瑞 2. 徐水帥 3. 石賽賽 日期： 2014 年 8 月

2、 20 日2014年河南科技大學(xué)數(shù)學(xué)建模競(jìng)賽選拔編 號(hào) 專(zhuān) 用 頁(yè)評(píng)閱編號(hào)（評(píng)閱前進(jìn)行編號(hào)）：評(píng)閱記錄（評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注基于圖論和非線(xiàn)性規(guī)劃求最佳搜救路線(xiàn)問(wèn)題摘要馬來(lái)西亞航空公司mh370航班意外失事引發(fā)了全球的關(guān)注，如何在最短的時(shí)間內(nèi)找到失事飛機(jī)殘骸以及黑匣子成為了關(guān)注焦點(diǎn)。本文將搜集的數(shù)據(jù)信息進(jìn)行處理，對(duì)已有的問(wèn)題作了合理的假設(shè)優(yōu)化，并應(yīng)用動(dòng)態(tài)規(guī)劃、圖論、網(wǎng)絡(luò)搜索、最優(yōu)化等理論，最終建立了最短路模型、最小時(shí)間模型從而得到最佳搜索路線(xiàn)。針對(duì)問(wèn)題一，通過(guò)查找資料得知搜救船的搜救半徑為6km，區(qū)域平均海洋深度為4.5km，運(yùn)用勾股定理得到實(shí)際搜尋半徑為4km。我們將著重搜救區(qū)域650

3、*93簡(jiǎn)化為一塊矩形區(qū)域648*96，為使在最短時(shí)間內(nèi)找到黑匣子，我們對(duì)常見(jiàn)的“平行線(xiàn)掃視搜尋法”做出改進(jìn)，通過(guò)將三艘船排開(kāi)，相鄰間隔為8km，橫向搜索，形成一條搜索寬度為24km的搜索帶。再根據(jù)實(shí)際搜尋半徑，我們將搜救區(qū)域劃分為108個(gè)24*24的小正方形，并繪制出相應(yīng)的網(wǎng)格圖，建立了以所行Hamilton路最短為目標(biāo)函數(shù)的圖論模型。另外我們考慮到拐角所用時(shí)間較長(zhǎng)，因此在所行最短的路線(xiàn)的基礎(chǔ)上使船隊(duì)經(jīng)過(guò)的拐角最少以達(dá)到最優(yōu)化結(jié)果，最終得到最佳線(xiàn)路圖，然后通過(guò)計(jì)算直線(xiàn)行駛和拐角所用時(shí)間，得到最短搜救時(shí)間為81.3h.對(duì)于問(wèn)題二，簡(jiǎn)化假設(shè)該題，計(jì)算飛機(jī)和輪船的平均搜索能力，以成本當(dāng)成目標(biāo)函數(shù)，以

4、黑匣子的壽命、搜救工具的數(shù)量、搜救面積當(dāng)做約束條件，構(gòu)建非線(xiàn)規(guī)劃模型，運(yùn)用lingo軟件求得動(dòng)用飛機(jī)2架，輪船0艘 ，最小成本為2762088元。關(guān)鍵字 平行掃視搜尋 哈密爾頓圈 非線(xiàn)性規(guī)劃 1、問(wèn)題重述 馬來(lái)西亞航空370號(hào)班機(jī)空難，是指2014年齡月8日一班從馬來(lái)西亞吉隆坡前往中國(guó)北京的波音777-200ER航機(jī)失蹤事件，被認(rèn)為是有史以來(lái)“最離奇”的飛機(jī)失聯(lián)案例。1空難的謎團(tuán)不能解開(kāi)，很大程度上取決于能不能打撈到“黑匣子”。MH370的失聯(lián)，各國(guó)為此出動(dòng)了25架飛機(jī)，40艘艦艇，甚至包括若干衛(wèi)星。（1） 請(qǐng)你以MH370為基本背景，基于互聯(lián)網(wǎng)報(bào)導(dǎo)的這次事件的一些數(shù)據(jù)（如不同搜索設(shè)備的搜索能

5、力，速度，續(xù)航時(shí)間，代價(jià)等）基礎(chǔ)上，做出合理假設(shè)、簡(jiǎn)化，針對(duì)（2） 某一種搜索工具（如衛(wèi)星、飛船、船只）討論其搜索的范圍和優(yōu)缺點(diǎn)，制定相應(yīng)的最優(yōu)搜索方案；（3）若假設(shè)所有的飛機(jī)船艦及衛(wèi)星都有一個(gè)國(guó)家統(tǒng)一調(diào)度，再討論如何才是最優(yōu)飛機(jī)殘骸和黑匣子的方案？2、問(wèn)題分析問(wèn)題一的分析，由于搜救區(qū)域一定，故問(wèn)題就轉(zhuǎn)化為了如何利用現(xiàn)有的搜集力量在最短時(shí)間內(nèi)完成搜救任務(wù)。由于具備搜救能力的船只有限，要縮短時(shí)間，就要擴(kuò)大搜索半徑，減少搜救路程。所以可將可用船只一字排開(kāi)，橫向掃過(guò)區(qū)域。接著，根據(jù)橫向搜索寬度，可將搜索區(qū)域劃分為多個(gè)小方塊，每個(gè)方塊中心看作點(diǎn)，這樣便可以用圖論知識(shí)將最短搜索路徑轉(zhuǎn)化為求最短的哈密爾頓

6、圈問(wèn)題。緊接著，再考慮使路徑拐角最少，我們得出了最終的最短搜索路徑，進(jìn)而可求出最短搜救時(shí)間。問(wèn)題二的分析，問(wèn)題二受到了黑匣子的壽命、搜救工具的數(shù)量、搜救面積等因素的制約，且搜尋工作不得不考慮到成本的問(wèn)題，故此問(wèn)題可化為求在上述約束條件下，以總成本為目標(biāo)函數(shù)建立非線(xiàn)規(guī)劃模型，最后根據(jù)相關(guān)數(shù)據(jù)求得最小成本。 3、問(wèn)題假設(shè)1. 假設(shè)該海域?yàn)楹谙蛔幼罱K落水區(qū)域，且可近似看作標(biāo)準(zhǔn)矩形區(qū)域2. 假設(shè)搜尋工作不受天氣影響，搜尋設(shè)備能持續(xù)工作3. 假設(shè)海床是一塊平面，深度一定4. 假設(shè)相同的搜救工具搜救能力相同4、符號(hào)說(shuō)明符號(hào)說(shuō)明S問(wèn)題一總路程問(wèn)題一直線(xiàn)路程問(wèn)題一拐彎路程t問(wèn)題一搜尋時(shí)間x問(wèn)題二派出船的數(shù)量y

7、問(wèn)題二派出飛機(jī)的數(shù)量m船的搜索能力n飛機(jī)的搜索能力K問(wèn)題二的搜救區(qū)域面積T問(wèn)題二黑匣子的壽命5、模型的建立與求解51問(wèn)題一的建立與求解5.1.1數(shù)據(jù)分析由于各國(guó)派出的搜救船各不相同，為簡(jiǎn)化問(wèn)題，我們將“永興島號(hào)遠(yuǎn)洋打撈救生船”作為標(biāo)準(zhǔn)，通過(guò)上網(wǎng)得出其性能參數(shù)表如下：排水量1.023萬(wàn)噸（正常），排水量1.305萬(wàn)噸（最大）主機(jī)6615千瓦（9000馬力）低速柴油機(jī)2臺(tái)，630千瓦柴油發(fā)電機(jī)組5臺(tái)主尺寸長(zhǎng)156.2米，設(shè)計(jì)水線(xiàn)長(zhǎng)140米，型寬（最大）20.6米，型深11.50米航速巡航速度18節(jié)，最大航速20節(jié)續(xù)航力18000海里自持力90晝夜編制298人直升機(jī)2架直-8直升機(jī)或超黃蜂大型直升機(jī)

8、黑匣子搜索儀搜尋半徑6km（注：1海里=1.852公里，1節(jié)=1.852km/h）根據(jù)表格，我們可知，船的航速為V=18*1.85233km/h，黑匣子搜索儀的搜尋半徑為6km，自持力為90晝夜，所以，搜索船一次性補(bǔ)給滿(mǎn)，可連續(xù)執(zhí)行搜救任務(wù)90天。通過(guò)上網(wǎng)查閱資料，我們得知只有少數(shù)搜救船裝備有黑匣子搜索儀，故我們假設(shè)有三艘船有。進(jìn)一步上網(wǎng)查詢(xún)，我們得到了失事飛機(jī)重點(diǎn)搜索區(qū)域面積為60,000 km（下圖黃色條狀），弧長(zhǎng)為650km，寬度為93km.如下圖：（注：黃色條帶為重要區(qū)域，藍(lán)色次之）為使問(wèn)題方便解決，我們近似地將此區(qū)域處理為一塊長(zhǎng)為648km，寬為96km的矩形區(qū)域如下圖：96km64

9、8km黑匣子在失事后沉入海底，海底地形凹凸不平，處理起來(lái)極為不便，故將其近似地看為是一塊平面。通過(guò)上網(wǎng)查找資料，我們將官方公布的黑匣子信號(hào)源深度4500m作為海床離海平面的距離。據(jù)分析，實(shí)際的搜索區(qū)域應(yīng)該為海面的搜索區(qū)域垂直投影到海床上的區(qū)域，也是一塊648km*96km的矩形，根據(jù)勾股定理可得，黑匣子搜索儀的實(shí)際搜索半徑約為4km，如下圖1所示：4km6km4.5km圖15.1.2模型的建立與求解為了使搜救方案更科學(xué)合理，通過(guò)查找相關(guān)搜救資料，我們得到了常見(jiàn)的海上搜救方法及其適用范圍表：搜救方法適用范圍扇形搜尋搜尋目標(biāo)位置準(zhǔn)確或搜尋區(qū)域較小時(shí)擴(kuò)展方形搜尋適用于當(dāng)搜尋目標(biāo)位置處于相對(duì)較近的區(qū)域

10、時(shí)航跡線(xiàn)搜尋適用于失事船舶在計(jì)劃航線(xiàn)上或附近遇險(xiǎn)雕而對(duì)事發(fā)位置小不確定平行掃視搜尋搜尋目標(biāo)位置很不確定并要求均勻覆蓋一廣闊區(qū)域橫移線(xiàn)搜尋較多應(yīng)用于航空器與船舶的協(xié)調(diào)進(jìn)行的搜救行動(dòng)岸線(xiàn)搜索船舶在熟知自身航行性能和航行水域狀況采取此方法移動(dòng)矩形搜索風(fēng)浪大、能見(jiàn)度低、夜間搜尋有效距離近、被搜尋目標(biāo)小不易發(fā)現(xiàn)、目標(biāo)漂移的速度較快由于失事飛機(jī)具體墜落地點(diǎn)不確定且范圍廣，與上述“平行掃視搜尋法”較吻合，其方法具體如下：當(dāng)執(zhí)行平行線(xiàn)掃視搜尋時(shí)，先設(shè)定一搜尋區(qū)域，并根據(jù)現(xiàn)場(chǎng)情況確定搜尋線(xiàn)間距，搜尋設(shè)施把搜尋區(qū)域的一角作為搜尋起始點(diǎn)，搜尋起始點(diǎn)通常在搜尋矩形內(nèi)距兩直角邊12搜尋線(xiàn)間距的位置，然后沿矩形長(zhǎng)邊來(lái)回保

11、持間距搜尋。圖：平行掃視搜尋圖解經(jīng)仔細(xì)分析，我們發(fā)現(xiàn)“平行掃視搜尋法”并不能直接解決問(wèn)題，故對(duì)其進(jìn)行改進(jìn)，具體過(guò)程如下：我們知道搜索區(qū)域一定，船速一定，故要使搜救時(shí)間最短，就要擴(kuò)大搜索半徑，減少搜救路程。關(guān)于擴(kuò)大搜索半徑，我們想到了將三艘搜救船一字排開(kāi)，相互間間隔為8km，這樣就形成了一個(gè)寬為24km的橫向掃面帶，則其在單位時(shí)間內(nèi)掃過(guò)的面積最大。接下來(lái)考慮減少路程，根據(jù)三艘船的排列方式，我們可以將矩形搜救區(qū)域劃分為108個(gè)24*24的小正方形，這樣，問(wèn)題就轉(zhuǎn)化為怎么在最短的時(shí)間內(nèi)把所有的小方格跑完。由于速度是確定的，所以只要使搜救路線(xiàn)最短即可。運(yùn)用圖論的知識(shí)，我們將每個(gè)小正方形的中心看作一個(gè)點(diǎn)

12、，最短搜救路線(xiàn)就轉(zhuǎn)化為了求經(jīng)過(guò)所有點(diǎn)的最小哈密頓圈。但考慮的每個(gè)小正方大小一樣，故得到的所有哈密頓圈大小也一樣，即路程一樣。通過(guò)進(jìn)一步分析和查找相關(guān)資料，為使時(shí)間最短，那就要減少搜救路線(xiàn)的拐角數(shù)，這就要求搜救船盡可能以直線(xiàn)行走，根據(jù)這些原則，我們得到了最終的搜救路線(xiàn)圖。二、模型假設(shè)三、符號(hào)約定搜救路線(xiàn)圖當(dāng)搜救船轉(zhuǎn)角時(shí)，會(huì)出現(xiàn)部分區(qū)域掃不到情況，如下圖所示：所以，最終路程S=直線(xiàn)路程+拐彎路程下面我們對(duì)拐彎路程作詳細(xì)分析。由于是3艘船一字?jǐn)[開(kāi)齊頭并進(jìn)，因此在整個(gè)過(guò)程中最左邊的船航程最大，因此我們只考慮最左邊的船的航程。另外，船在拐彎時(shí)會(huì)有90度彎和180度彎兩種情況。為方便描述，我們記最左邊的船

13、為一號(hào)船。當(dāng)船隊(duì)遇到90度拐角時(shí)，經(jīng)分析可知，一號(hào)船按如下圖2所示路線(xiàn)走可滿(mǎn)足在將區(qū)域全部掃描完整基礎(chǔ)上航程最短條件。 圖2 （注釋?zhuān)阂惶?hào)船走到區(qū)域的邊界時(shí)再朝下一個(gè)既定位置直線(xiàn)行駛。）當(dāng)船隊(duì)遇到180度拐角時(shí)，經(jīng)分析可知，船隊(duì)按如下圖3所示路線(xiàn)走可滿(mǎn)足條件。 圖3 （注釋?zhuān)寒?dāng)船隊(duì)遇到180度角時(shí)左右船位置互換。） 經(jīng)計(jì)算可得總距離S=+=4+(4.5+24*4+1.5+9)*24 由Matlab得s=2684.4km。又因?yàn)樗阉鞔?duì)的速度v=33km/h，我們可以得到最短搜索時(shí)間t=S/v=81.3453小時(shí)。5.2問(wèn)題二的建立與求解5.2.1建模思路由于衛(wèi)星涉及到的數(shù)據(jù)量多、大且不易找到，

14、故我們僅假設(shè)現(xiàn)有的搜救力量只有船和飛機(jī)，且飛機(jī)和船都可由同一點(diǎn)調(diào)度。經(jīng)查閱資料，黑匣子發(fā)射信號(hào)的能力只有30天，飛機(jī)有25架，船有40艘，搜救面積為問(wèn)題一中黃色搜救區(qū)域的3倍，即 18000(用K表示)所以以它們作為約束變量，建立以總成本為目標(biāo)函數(shù)的線(xiàn)性規(guī)劃模型，以求得最小成本。5.22模型建立與求解通過(guò)查找資料，我們得到了飛機(jī)和船的搜救力量信息：為便于解決問(wèn)題，我們各個(gè)型號(hào)的搜救能力取平均值，將其作為標(biāo)準(zhǔn)。得到：船的搜尋能力m=(9+12+50+24+56+21+42+25+21+24+19+27+47+58+62)/15=43.2 n mile/h.=148.17.168km/h飛機(jī)的搜尋

15、能力n=(180+220+150+180+220)/5=190 n mile/h.=651.681 km/h（1 n mile=3.4299 km）另外我們查找數(shù)據(jù)得到輪船和飛機(jī)的耗油量以及考慮到人工成本等因素得出輪船每小時(shí)搜尋需要花費(fèi)a=3000元，飛機(jī)需要花費(fèi)b=10000元。搜索時(shí)間T=K/（mx+nb）設(shè)需要調(diào)用的船x艘，飛機(jī)y架，總成本為z，由非線(xiàn)性規(guī)劃的相關(guān)知識(shí)可建立數(shù)學(xué)模型：min z=(3000*x+10000*y)*180000/(148.17168*x+651.681*y)s.t. 0X40 0Y25 0180000/(148.17168*x+651.681*y)30*24

16、用lingo軟件進(jìn)行求解，其程序如下：min=(3000*x+10000*y)*180000/(148.17168*x+651.681*y);x<=40；y<=25;180000/(148.17168*x+651.681*y)<=720;gin(x);gin(y);運(yùn)行結(jié)果如下：Local optimal solution found. Objective value: 2762088. Objective bound: 2762088. Infeasibilities: 0.000000 Extended solver steps: 7 Total solver itera

17、tions: 228 Variable Value Reduced Cost X 0.000000 100307.4 Y 2.000000 0.000000 Row Slack or Surplus Dual Price 1 2762088. -1.000000 2 40.00000 0.000000 3 23.00000 0.000000 4 581.8956 0.000000根據(jù)結(jié)果，我們決定派出兩架飛機(jī)執(zhí)行全部搜索任務(wù)，最小成本為2762088元。6.模型的評(píng)價(jià)優(yōu)點(diǎn)：1、問(wèn)題一中我們?cè)诶碚摵图?xì)節(jié)方面把握的非常到位，在理論方面我們運(yùn)用了哈密爾頓回路的原理，將問(wèn)題簡(jiǎn)化為求哈密爾頓圈的最優(yōu)解，并聯(lián)合實(shí)際求出在將區(qū)域全部掃描完的基礎(chǔ)上的最短路線(xiàn)。在細(xì)節(jié)方面比如在計(jì)算搜索半徑時(shí)我們考慮到海床對(duì)搜索半徑的影響進(jìn)而得到實(shí)際的搜索半徑，還有船隊(duì)在遇到拐角時(shí)可能會(huì)未搜索一定區(qū)域等。另外我們還用photoshop軟件做出效果圖使得該模型更好理解。2、運(yùn)用lingo求解問(wèn)題，使結(jié)果更具說(shuō)服力缺點(diǎn)：在考慮問(wèn)題時(shí)我們并未考慮搜救中心到搜救地點(diǎn)的距離以及各搜救船只和飛機(jī)的搜索能力的不同等現(xiàn)實(shí)因素。7、參考文獻(xiàn)1.圖論，作者王樹(shù)禾，科學(xué)出版社2