地面搜索問題的優(yōu)化模型—數(shù)學(xué)建模論文

《地面搜索問題的優(yōu)化模型—數(shù)學(xué)建模論文》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、地面搜索問題的優(yōu)化模型摘要本文針對地面搜索過程中人員安排和路線選擇問題，建立了優(yōu)化模型，并給出了相應(yīng)算法，用LINGO軟件編程，在確保所有地點都不遺漏且不重復(fù)的情況下，合理安排人員和線路，使得搜索用時最短。問題一的求解中，把20個搜索隊員排成一行，向前搜索。從局部和總體兩個方面對人員行進(jìn)和路線選擇。在局部方面，考慮到人員行進(jìn)中90度和180度轉(zhuǎn)彎的情況，給出了兩種轉(zhuǎn)彎策略，并計算出這兩種轉(zhuǎn)彎的情況需要多耗費的時間；在總體方面，把需要進(jìn)行搜索的區(qū)域分割成的126個方格，利用一筆畫原理，判斷出這些方格可以用一條不重復(fù)的線路走完?？紤]到轉(zhuǎn)彎需要多耗費時間，建立了

2、以轉(zhuǎn)彎次數(shù)最少，并且從起始點開始不重復(fù)行走到達(dá)集結(jié)點的模型，利用LINGO軟件進(jìn)行編程求解，得到了最少轉(zhuǎn)彎的模型。考慮到具體情況，對上述模型得到的路線進(jìn)行適當(dāng)調(diào)整，得到最終的搜索線路安排圖。根據(jù)圖表，計算出20個隊員進(jìn)行搜索需要50.117小時，無法在48內(nèi)完成搜索任務(wù)。考慮到隊員和組長距離不超過1000米，設(shè)計一種讓20名搜索隊員組成的隊伍和新增人員組成的隊伍進(jìn)行交替行進(jìn)的模型，以確保讓整個搜索過程控制在48小時以內(nèi)。最后給出了該行進(jìn)模型的相應(yīng)算法，通過計算，得出增加2個隊員可以確保搜索在48小時內(nèi)完成。問題二的求解中，首先對50名人員分3組進(jìn)行分析，由

3、于矩形區(qū)域被分割后形成的小區(qū)域恰好能被20人組成的一個隊列一次搜索覆蓋，以及10人組成的一個隊列一個來回的搜索覆蓋，于是3組可分為：2個隊伍為20人，1個隊伍為10人。隨后進(jìn)行隊伍搜索區(qū)域的劃分，根據(jù)各個隊伍人數(shù)確定該組分配到的方格的數(shù)量，劃分出各個隊伍的搜索區(qū)域。然后對三個區(qū)域進(jìn)行搜索路徑的優(yōu)化求解，改進(jìn)問題一的模型，求出三個區(qū)域的搜索路徑。再根據(jù)實際情況，對路徑進(jìn)行適當(dāng)修改，得出20人的2個隊伍，需要19.816小時，10人的隊伍需要20.294小時。根據(jù)先完成搜索任務(wù)的隊伍能否有足夠的時間來幫助未完成搜索任務(wù)的隊伍提早完成任務(wù)的時間要求，判斷出該解是

4、可以接受的。于是得到50人進(jìn)行搜救的時間為20.294小時。17最后，對文中的模型進(jìn)行了優(yōu)缺點的分析。關(guān)鍵詞：搜索模型；最優(yōu)路徑；一筆畫；遍歷網(wǎng)格；轉(zhuǎn)彎策略一、問題重述有一個平地矩形目標(biāo)區(qū)域，大小為11200米×7200米，需要進(jìn)行全境搜索。假設(shè)：出發(fā)點在區(qū)域中心；搜索完成后需要進(jìn)行集結(jié)，集結(jié)點（結(jié)束點）在左側(cè)短邊中點；每個人搜索時的可探測半徑為20米，搜索時平均行進(jìn)速度為0.6米/秒；不需搜索而只是行進(jìn)時,平均速度為1.2米/秒。每個人帶有GPS定位儀、步話機，步話機通訊半徑為1000米。搜索隊伍若干人為一組,有一個組長，組長還擁有衛(wèi)星電話。每個人搜索到

5、目標(biāo)，需要用步話機及時向組長報告，組長用衛(wèi)星電話向指揮部報告搜索的最新結(jié)果?，F(xiàn)在有如下問題需要解決：1．假定有一支20人一組的搜索隊伍,擁有1臺衛(wèi)星電話。請設(shè)計一種你認(rèn)為耗時最短的搜索方式。按照你的方式，搜索完整個區(qū)域的時間是多少?能否在48小時內(nèi)完成搜索任務(wù)?如果不能完成，需要增加到多少人才可以完成。2．為了加快速度，搜索隊伍有50人，擁有3臺衛(wèi)星電話，分成3組進(jìn)行搜索。每組可獨立將搜索情況報告給指揮部門。請設(shè)計一種你認(rèn)為耗時最短的搜索方式。按照你的搜索方式,搜索完整個區(qū)域的時間是多少?17二、模型假設(shè)1.假設(shè)搜索必須完全，不存在遺漏情況。2.假設(shè)如果發(fā)

6、現(xiàn)需要救助的人員，只需報告組長，不影響其搜索速度。3.假設(shè)救援人員進(jìn)食休息的時間不計。4.隊員間不能間接向組長報告情況。5.假設(shè)每組隊員只能向本組組長報告。6.假設(shè)隊員的身體和心理狀態(tài)不影響進(jìn)度。7.假設(shè)搜索區(qū)域地面狀況不影響搜索速度。8.假設(shè)設(shè)備在搜索過程中都正常工作。三、符號說明20人排成隊列的長度增加的人數(shù)不搜索時候行進(jìn)的速度搜索時候行進(jìn)的速度搜索需要花費的時間搜索時間的各個組成部分表示矩形分割后的區(qū)域的標(biāo)號表示標(biāo)號為的區(qū)域的各個方向的連接數(shù)表示1個180度轉(zhuǎn)彎需要多耗費的時間表示1個90度轉(zhuǎn)彎需要多耗費的時間四、問題分析17本題針對一塊矩形區(qū)域進(jìn)行

7、全境搜索問題,在保證全部搜索到的情況下，使搜索時間最短，我們將20人看成排成一排的整體,并將大的矩形區(qū)域劃分為126個以800米為邊長的正方形小區(qū)域，根據(jù)圖論中的一筆畫問題,以轉(zhuǎn)彎最少為約束條件進(jìn)行LINGO編程，計算出搜索路徑.當(dāng)隊伍增加為3時，先根據(jù)人數(shù)比例進(jìn)行大體的區(qū)域劃分，然后在根據(jù)問題1的求解方法，計算出三個隊的最優(yōu)路徑。五、模型的建立與求解5.1求解問題一5.1.1建立隊伍前進(jìn)和轉(zhuǎn)彎模型：由于每個搜索隊員的搜索半徑為20米，為了簡化模型，把20名搜索隊員排成一條直線，其中隊長處于中間，這樣就更好的保證了隊員與隊長的通訊：總長為800米共20個圖

8、(1-1)搜索時候可以把20人組成的隊列看作一條長800米的直線，