數(shù)學(xué)建模國(guó)家一等獎(jiǎng) 論文

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

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

3、覆蓋，以及10人組成的一個(gè)隊(duì)列一個(gè)來(lái)回的搜索覆蓋，于是3組可分為：2個(gè)隊(duì)伍為20人，1個(gè)隊(duì)伍為10人。隨后進(jìn)行隊(duì)伍搜索區(qū)域的劃分，根據(jù)各個(gè)隊(duì)伍人數(shù)確定該組分配到的方格的數(shù)量，劃分出各個(gè)隊(duì)伍的搜索區(qū)域。然后對(duì)三個(gè)區(qū)域進(jìn)行搜索路徑的優(yōu)化求解，改進(jìn)問(wèn)題一的模型，求出三個(gè)區(qū)域的搜索路徑。再根據(jù)實(shí)際情況，對(duì)路徑進(jìn)行適當(dāng)修改，得出20人的2個(gè)隊(duì)伍，需要19.816小時(shí)，10人的隊(duì)伍需要20.294小時(shí)。根據(jù)先完成搜索任務(wù)的隊(duì)伍能否有足夠的時(shí)間來(lái)幫助未完成搜索任務(wù)的隊(duì)伍提早完成任務(wù)的時(shí)間要求，判斷出該解是可以接受的。于是得到50人進(jìn)行搜救的時(shí)間為20.294小時(shí)。最后，對(duì)文中的模型進(jìn)行了優(yōu)缺點(diǎn)的分析。關(guān)鍵詞

4、：搜索模型；最優(yōu)路徑；一筆畫；遍歷網(wǎng)格；轉(zhuǎn)彎策略一、問(wèn)題重述有一個(gè)平地矩形目標(biāo)區(qū)域，大小為11200米×7200米，需要進(jìn)行全境搜索。假設(shè)：出發(fā)點(diǎn)在區(qū)域中心；搜索完成后需要進(jìn)行集結(jié)，集結(jié)點(diǎn)（結(jié)束點(diǎn)）在左側(cè)短邊中點(diǎn)；每個(gè)人搜索時(shí)的可探測(cè)半徑為20米，搜索時(shí)平均行進(jìn)速度為0.6米/秒；不需搜索而只是行進(jìn)時(shí),平均速度為1.2米/秒。每個(gè)人帶有GPS定位儀、步話機(jī)，步話機(jī)通訊半徑為1000米。搜索隊(duì)伍若干人為一組,有一個(gè)組長(zhǎng)，組長(zhǎng)還擁有衛(wèi)星電話。每個(gè)人搜索到目標(biāo)，需要用步話機(jī)及時(shí)向組長(zhǎng)報(bào)告，組長(zhǎng)用衛(wèi)星電話向指揮部報(bào)告搜索的最新結(jié)果?，F(xiàn)在有如下問(wèn)題需要解決：1假定有一支20人一組的搜索隊(duì)伍,

5、擁有1臺(tái)衛(wèi)星電話。請(qǐng)?jiān)O(shè)計(jì)一種你認(rèn)為耗時(shí)最短的搜索方式。按照你的方式，搜索完整個(gè)區(qū)域的時(shí)間是多少? 能否在48小時(shí)內(nèi)完成搜索任務(wù)? 如果不能完成，需要增加到多少人才可以完成。2為了加快速度，搜索隊(duì)伍有50人，擁有3臺(tái)衛(wèi)星電話，分成3組進(jìn)行搜索。每組可獨(dú)立將搜索情況報(bào)告給指揮部門。請(qǐng)?jiān)O(shè)計(jì)一種你認(rèn)為耗時(shí)最短的搜索方式。按照你的搜索方式, 搜索完整個(gè)區(qū)域的時(shí)間是多少?二、模型假設(shè)1. 假設(shè)搜索必須完全，不存在遺漏情況。2. 假設(shè)如果發(fā)現(xiàn)需要救助的人員，只需報(bào)告組長(zhǎng)，不影響其搜索速度。3. 假設(shè)救援人員進(jìn)食休息的時(shí)間不計(jì)。4. 隊(duì)員間不能間接向組長(zhǎng)報(bào)告情況。5. 假設(shè)每組隊(duì)員只能向本組組長(zhǎng)報(bào)告。6. 假

6、設(shè)隊(duì)員的身體和心理狀態(tài)不影響進(jìn)度。7. 假設(shè)搜索區(qū)域地面狀況不影響搜索速度。8. 假設(shè)設(shè)備在搜索過(guò)程中都正常工作。三、 符號(hào)說(shuō)明 20人排成隊(duì)列的長(zhǎng)度 增加的人數(shù) 不搜索時(shí)候行進(jìn)的速度 搜索時(shí)候行進(jìn)的速度 搜索需要花費(fèi)的時(shí)間 搜索時(shí)間的各個(gè)組成部分 表示矩形分割后的區(qū)域的標(biāo)號(hào) 表示標(biāo)號(hào)為的區(qū)域的各個(gè)方向的連接數(shù) 表示1個(gè)180度轉(zhuǎn)彎需要多耗費(fèi)的時(shí)間 表示1個(gè)90度轉(zhuǎn)彎需要多耗費(fèi)的時(shí)間四、問(wèn)題分析 本題針對(duì)一塊矩形區(qū)域進(jìn)行全境搜索問(wèn)題,在保證全部搜索到的情況下，使搜索時(shí)間最短，我們將20人看成排成一排的整體,并將大的矩形區(qū)域劃分為126個(gè)以800米為邊長(zhǎng)的正方形小區(qū)域，根據(jù)圖論中的一筆畫問(wèn)題,以

7、轉(zhuǎn)彎最少為約束條件進(jìn)行LINGO編程，計(jì)算出搜索路徑.當(dāng)隊(duì)伍增加為3時(shí)，先根據(jù)人數(shù)比例進(jìn)行大體的區(qū)域劃分，然后在根據(jù)問(wèn)題1的求解方法，計(jì)算出三個(gè)隊(duì)的最優(yōu)路徑。五、模型的建立與求解5.1 求解問(wèn)題一建立隊(duì)伍前進(jìn)和轉(zhuǎn)彎模型： 由于每個(gè)搜索隊(duì)員的搜索半徑為20米，為了簡(jiǎn)化模型，把20名搜索隊(duì)員排成一條直線，其中隊(duì)長(zhǎng)處于中間，這樣就更好的保證了隊(duì)員與隊(duì)長(zhǎng)的通訊： 總長(zhǎng)為800米共20個(gè) 圖(1-1) 搜索時(shí)候可以把20人組成的隊(duì)列看作一條長(zhǎng)800米的直線，搜索方向是沿著直線的垂線的方向，直線行進(jìn)的速度為搜索的速度。如下圖所示，直線向其垂線方向進(jìn)行時(shí)，會(huì)形成一個(gè)矩形軌跡，見圖(1-2)。 800米移動(dòng)方

8、向 圖(1-2) 但需要進(jìn)行轉(zhuǎn)彎時(shí)，分為2種情況，180度轉(zhuǎn)彎和90度轉(zhuǎn)彎：1、180度轉(zhuǎn)彎：圖(1-3) 如圖(1-3)所示，原直線沿著AB 邊向右移動(dòng)，當(dāng)?shù)竭_(dá)CD邊時(shí)，整體向上移動(dòng)，使得原CD邊與EC邊重合，然后EC邊繼續(xù)向左邊運(yùn)動(dòng)，搜索遇難人員。由 得， 即過(guò)180度的彎需要多耗費(fèi)的時(shí)間2、90度轉(zhuǎn)彎CDoAB圖(1-4)如圖(1-4)所示，原直線沿著AB 邊向右移動(dòng)，當(dāng)?shù)竭_(dá)CD邊時(shí)，直線上處于C點(diǎn)的人向O點(diǎn)運(yùn)動(dòng)，D點(diǎn)上的人向C點(diǎn)運(yùn)動(dòng)，點(diǎn)，直線中間的人員依然可以找到合適的路徑向OC邊移動(dòng)，使得CD與CO重合，然后CO邊繼續(xù)向上邊運(yùn)動(dòng)，搜索遇難人員。容易得出，該調(diào)整過(guò)程也需要的時(shí)間，即由以

9、上2個(gè)轉(zhuǎn)彎模型，可以得出，轉(zhuǎn)彎的時(shí)間為建立搜索路線模型：如表(1-1)所示，把矩形區(qū)域劃分為如下小塊，并且標(biāo)號(hào)為：表(1-1)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115

10、116117118119120121122123124125126 根據(jù)圖論中關(guān)于奇頂點(diǎn)個(gè)數(shù)為偶數(shù)就能一次走完全程而不重復(fù)行走的原理，判斷出這些方格可以用一條不重復(fù)的線路走完。 由于出發(fā)點(diǎn)在矩形區(qū)域中央，即和交線的中點(diǎn)處，設(shè)定搜索隊(duì)首先進(jìn)入?yún)^(qū)域，然后在搜索完全部區(qū)域后，最后回到，過(guò)程是一筆畫成的，沒有重復(fù)，由于在轉(zhuǎn)彎時(shí)，需要額外花費(fèi)時(shí)間來(lái)進(jìn)行調(diào)整，所以，當(dāng)轉(zhuǎn)彎數(shù)為最少時(shí)，是該題目的最優(yōu)解答。 如表(1-1)可以看出：矩形中的各個(gè)小區(qū)域在前后左右有另外的小區(qū)域與其相鄰（邊界的區(qū)域較特殊，可能某個(gè)方向沒有相鄰的區(qū)域）。把各個(gè)小區(qū)域看成一個(gè)點(diǎn)，如果要進(jìn)行一筆畫，則除了開始點(diǎn)只有一個(gè)出口和結(jié)束點(diǎn)只有一

11、個(gè)入口，每個(gè)點(diǎn)均有兩個(gè)接口與其他區(qū)域連接。 （1）一個(gè)點(diǎn)有上下左右四個(gè)方向，用字母表示這個(gè)點(diǎn)在方向上是否與其它點(diǎn)連接，1為連接，0為不連接，分別表示上下左右四個(gè)方向。以2個(gè)特殊的點(diǎn)為例，如： 點(diǎn)：由于在頂角，則其上邊和左邊必定沒有連接，所以，。 點(diǎn)：由于在下邊沿，則其下邊必定沒有連接，所以 全面的表示出這些點(diǎn)的特征，表達(dá)式為：（2）由于每個(gè)點(diǎn)的連接個(gè)數(shù)只能為2個(gè)（除外）， 所以，（3）如果有2個(gè)點(diǎn)，一個(gè)點(diǎn)的左邊與另一個(gè)點(diǎn)連接，則另一個(gè)點(diǎn)的右端必定與該點(diǎn)連接。基于這個(gè)原則，得到如下表達(dá)式： （4）為了判定在一個(gè)點(diǎn)處是否轉(zhuǎn)彎，只要判定該點(diǎn)的2個(gè)接口是否為上和下，或者左和右，當(dāng)一個(gè)為上，一個(gè)為下，可

12、以說(shuō)明該點(diǎn)處不轉(zhuǎn)彎；當(dāng)一個(gè)為左，一個(gè)為右，也可以說(shuō)明該點(diǎn)處不轉(zhuǎn)彎。用表達(dá)式來(lái)表示如下： 當(dāng)時(shí)，為不轉(zhuǎn)彎。 根據(jù)以上（1）（2）（3）（4）四點(diǎn)，可以轉(zhuǎn)化為一個(gè)優(yōu)化問(wèn)題的求解。目標(biāo)函數(shù)：約束條件：，用LINGO編寫程序（見附錄），可以得到對(duì)應(yīng)的上下左右四個(gè)方向是否有連接的數(shù)據(jù)，根據(jù)數(shù)據(jù)可以表示出其路線圖。為了方便觀看，用線路圖表示路線如圖(1-5):圖(1-5) 如圖(1-5)可知，通過(guò)LINGO軟件解決了不重復(fù)和彎角最小的問(wèn)題，可是其沒有解決一筆畫問(wèn)題，在圖中出現(xiàn)了一個(gè)閉合的路徑，不和其他路徑進(jìn)行相連接，由于程序?yàn)槲覀兘鉀Q了不重復(fù)和彎角最小的問(wèn)題，我們?nèi)绻M(jìn)行適當(dāng)?shù)奈⒄{(diào)，對(duì)最優(yōu)結(jié)果的影響是很微

13、小的。觀察圖形，對(duì)那個(gè)閉合路徑進(jìn)行修改，使得他和其他路徑相連接。 對(duì)圖像的調(diào)整結(jié)果如下：圖（1-6） 如圖(1-6)所示該路線經(jīng)過(guò)了所有的區(qū)域，一共需要轉(zhuǎn)彎17個(gè)，則轉(zhuǎn)彎所需的時(shí)間為 除轉(zhuǎn)彎外的時(shí)間外，其余時(shí)間設(shè)都為搜索前進(jìn)，為 得， 由于在開始搜索時(shí)，所有隊(duì)員都處在矩形區(qū)域中央，即左邊沿的中點(diǎn)處，為了讓隊(duì)員排列成一條直線，則所有隊(duì)員向兩邊散開，使其均勻分布在左邊沿，這一過(guò)程需要耗費(fèi)的時(shí)間為得， 在搜索結(jié)束時(shí)候，所有隊(duì)員都均勻分布在的下邊沿，為了讓他們到達(dá)集合地點(diǎn)（的左邊沿的中點(diǎn)），需要耗費(fèi)的時(shí)間為得，則所以搜索完整個(gè)區(qū)域的時(shí)間是50.117小時(shí)，不能在48小時(shí)內(nèi)完成搜索。建立增加人數(shù)的模型

14、為了滿足能夠在48小時(shí)內(nèi)搜索完成搜索任務(wù)，決定增加人數(shù)為，這個(gè)人的作用就是為了幫助原20個(gè)人的隊(duì)伍分擔(dān)部分搜索區(qū)域，來(lái)達(dá)到原20人的隊(duì)伍能在48小時(shí)內(nèi)完成搜索任務(wù)的目的。隊(duì)伍搜索區(qū)域的時(shí)間包括，其中是最有可能進(jìn)行優(yōu)化的數(shù)據(jù)，也是可以減少幅度最大的時(shí)間因素。讓增加的個(gè)人在這段時(shí)間里發(fā)揮作用，來(lái)減少。建立模型：只考慮隊(duì)員搜索所有路線的時(shí)間，由于不轉(zhuǎn)彎所以隊(duì)員行進(jìn)路線可視為一條直線。把原20人和新增加的個(gè)人分為2個(gè)隊(duì)伍，只要個(gè)人的隊(duì)伍離原20人的隊(duì)伍距離不超過(guò)1000米，就可以和組長(zhǎng)保持連續(xù)，但兩隊(duì)伍的搜索是獨(dú)立完成的。ABCDE 圖（1-7） 如圖(1-7)，可以把行進(jìn)路線分割為一大一小交替的段落

15、。其中A為原20人隊(duì)伍搜索的區(qū)域，B為增加的個(gè)人隊(duì)伍趁著原20人隊(duì)伍在搜索A區(qū)域時(shí)，以速度移動(dòng)過(guò)去搜索的路線。當(dāng)原20人隊(duì)伍搜索完A時(shí)，要繼續(xù)搜索C區(qū)域，可以速度經(jīng)過(guò)B區(qū)域，此時(shí)個(gè)人的隊(duì)伍又以速度移動(dòng)到D，如此交替?？梢园l(fā)現(xiàn)，總共搜索節(jié)約的時(shí)間，就是20 人隊(duì)伍以速度穿過(guò)B，D所節(jié)省的時(shí)間，且節(jié)約的時(shí)間為原來(lái)大部隊(duì)經(jīng)過(guò)B，D時(shí)間的一半。得到方程： 解得 因此，如果想在48小時(shí)內(nèi)完成搜索應(yīng)該增加2個(gè)搜索隊(duì)員。5.2 求解問(wèn)題二 由問(wèn)題一的選擇路徑模型可知，需要搜索的矩形區(qū)域長(zhǎng)和寬可以被20人組成的直線的長(zhǎng)度整除，也可以被10人組成的直線的長(zhǎng)度整除，為了便于計(jì)算和工作安排，我們做如下設(shè)定：1. 把

16、50人分為三組，人數(shù)分別為20、20、10人；2. 為了使搜索所用時(shí)間最短，則三組所用時(shí)間相等；3. 在不考慮轉(zhuǎn)彎時(shí)間的條件下，如問(wèn)題一所示，把矩形區(qū)域分為126個(gè)區(qū)域由于最終所有隊(duì)伍必須回到一點(diǎn)，所以除去該點(diǎn)所在的區(qū)域，三隊(duì)分得的區(qū)域個(gè)數(shù)為為50，50，25時(shí)時(shí)間最短。 如圖(2-1)，分出了區(qū)域，上下兩個(gè)圖形塊為20人搜索的面積，中間區(qū)域10個(gè)人隊(duì)伍搜索的區(qū)域。 以上理論是理想化的圖形，實(shí)際上要考慮轉(zhuǎn)彎等因素，所以時(shí)間可能會(huì)不相同。 圖(2-1) 如圖(2-1)可知，上下兩個(gè)區(qū)域是對(duì)稱的，他們的搜索路徑時(shí)相同的。而中間區(qū)域必須把每個(gè)小區(qū)域的邊長(zhǎng)變?yōu)?00，才能利用問(wèn)題一種的方法進(jìn)行10人搜

17、索。 取出上邊區(qū)域單獨(dú)考慮，對(duì)方格標(biāo)號(hào)如表(2-1)：表(2-1)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950對(duì)問(wèn)題一中的模型進(jìn)行修改：目標(biāo)函數(shù)：約束條件：，通過(guò)LINGO編程(見附件：程序2)，在進(jìn)行適當(dāng)?shù)穆窂秸{(diào)整后，得到 圖(2-2)由于中間區(qū)域的搜索隊(duì)員的人數(shù)為10人,展開的長(zhǎng)度為400米，于是把區(qū)域再劃分為4個(gè)區(qū)域，得到如下區(qū)域表： 表(2-2)對(duì)問(wèn)題一中的模型進(jìn)行修改得：目標(biāo)函數(shù)： 約束條件： ，通過(guò)LINGO編程(見附件：程序3)，在進(jìn)行適當(dāng)?shù)穆?/p>

18、徑調(diào)整后，得到： 圖(2-3) 由于在求中間區(qū)域時(shí)候，不可避 免的進(jìn)行了較多的轉(zhuǎn)彎，所以圖(2-3)中“X”點(diǎn)處為沒有進(jìn)行分配的區(qū)域應(yīng)該平均分給20人的2個(gè)隊(duì)伍。依然使用來(lái)表示搜索某一區(qū)域的時(shí)間，其中分別表示，轉(zhuǎn)彎時(shí)間，搜索時(shí)間，開始搜索時(shí)候人員調(diào)配的時(shí)間，結(jié)束時(shí)候人員集合的時(shí)間。 由上述結(jié)果可以得出，20人的隊(duì)伍在比10人的隊(duì)伍早完成任務(wù)。設(shè)定搜索上邊區(qū)域和下邊區(qū)域的隊(duì)伍分別為第一、二隊(duì)，搜索中間區(qū)域的為第三隊(duì)。如果第一隊(duì)和第二隊(duì)有必要幫助第三隊(duì)完成搜索任務(wù)以縮短搜索時(shí)間，那么第一二兩隊(duì)和第三隊(duì)完成任務(wù)相差時(shí)間必須大于已經(jīng)結(jié)束搜索任務(wù)第一二隊(duì)走出集結(jié)點(diǎn)所在的區(qū)域時(shí)剛好碰到中間的隊(duì)伍完成搜索一起到集結(jié)點(diǎn)的時(shí)間，通過(guò)計(jì)算這段時(shí)間為，如果第一二隊(duì)比第三隊(duì)至少早完成搜索任務(wù)，才能幫助第三隊(duì)減少任務(wù)時(shí)間。由于第三隊(duì)比第一二隊(duì)晚完成搜索，小于小時(shí)，則沒有必要再減少第三隊(duì)的搜索時(shí)間，所以我們的方案是合理的。所以50個(gè)人分三組最少搜索時(shí)間是。六、優(yōu)缺點(diǎn)分析 優(yōu)點(diǎn)：劃分為網(wǎng)格，確定了隊(duì)員的大體移動(dòng)方向，避免了無(wú)規(guī)則的移動(dòng)，簡(jiǎn)化了問(wèn)題的求解。利用圖論的判斷了對(duì)搜索路線可以一筆畫，在編寫程序中避免了搜索過(guò)程中的重復(fù)搜索，節(jié)省了時(shí)間， 缺點(diǎn)：用LINGO程序求出的搜索路徑不一定是最優(yōu)解，只是一個(gè)較好的可行解。在考慮增加人數(shù)問(wèn)題的處理上，沒有考慮轉(zhuǎn)彎時(shí)間的變化，導(dǎo)致求出的人數(shù)相對(duì)變小。七、參考文獻(xiàn)1