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

1、地面搜索的數(shù)學(xué)模型 摘 要本文主要討論設(shè)計(jì)了搜索11200米×7200米的矩形目標(biāo)區(qū)域的優(yōu)化路徑，以保證對預(yù)定區(qū)域進(jìn)行快速全面的搜索。問題一，我們討論了如何使20人一組的搜索隊(duì)伍在最短時(shí)間完成搜索任務(wù)。首先將其轉(zhuǎn)化為圖論問題，得到距離圖（圖5-3），然后建立滿足完全搜索的0-1規(guī)劃模型【模型一】，利用lingo8.0求解得到最短搜索的路徑圖（圖5-4），總搜索時(shí)間為51.1018小時(shí)，不能夠在48小時(shí)內(nèi)完成搜索任務(wù)。為保證在48小時(shí)內(nèi)完成搜索任務(wù)，采用減少搜索道即增加道寬的方法確定增加的最少人數(shù)。根據(jù)模型一建立了【模型二】和動態(tài)規(guī)劃模型【模型三】，得到最終的搜索路徑（圖5-7），增加

2、的最少人數(shù)為3人，分為8道，完成搜索耗時(shí)46.1019小時(shí)。模型二、三具有通用性，可給出任意搜索道數(shù)的最短搜索時(shí)間及規(guī)定48小時(shí)內(nèi)完成搜索需要增加的人數(shù)（表5-1）。另外考慮改變搜索起始點(diǎn)的位置，建立了通用模型【模型四】，結(jié)合模型三求得不同分道數(shù)下完成搜索任務(wù)增加的最少人數(shù)和完成時(shí)間（表5-2），由模型四也得到分8道和增加最少3人能完成搜索任務(wù)，完成時(shí)間為45.1059小時(shí)，比模型二優(yōu)。問題二，討論了如何將50人分三組并選擇最佳搜索路徑，使搜索時(shí)間最短。把矩形分三個(gè)區(qū)域，按均分道寬和不均分道寬討論。對于均分搜索，確立了兩種方式（圖5-10、5-11），建立【模型五】求得最短搜索時(shí)間分別為圖5-

3、10的23.1151小時(shí)和圖5-11的23.3524小時(shí)。結(jié)論是采用均分搜索以圖5-10的搜索方式最優(yōu)，但浪費(fèi)的人員較多。對非均分搜索，引入搜索橫徑與道寬相對差異度q，人數(shù)均衡度r等因子作為限制條件，建立規(guī)劃模型【模型六】求得人員分組為16人、17人、17人；所劃區(qū)域?qū)挿謩e為2304米、2448米、2448米；所耗最短總時(shí)間為23.1151小時(shí)，還是避免不了人員的浪費(fèi)?？紤]浪費(fèi)人員，建立規(guī)劃模型【模型七】，得到在50個(gè)人的基礎(chǔ)上，可以最大限度減少5人仍能在原來時(shí)間上完成搜索任務(wù)。此模型通過改進(jìn)可以得到在規(guī)定時(shí)間規(guī)定組數(shù)或完成的搜索的人員分配，安排多少人來完成任務(wù)，也可以在實(shí)現(xiàn)在規(guī)定人數(shù)的人員分

4、組問題，是一個(gè)推廣性較好的數(shù)學(xué)模型。關(guān)鍵詞：路線轉(zhuǎn)換；距離圖；0-1規(guī)劃；動態(tài)規(guī)劃1、 問題重述5.12汶川大地震使震區(qū)地面交通和通訊系統(tǒng)嚴(yán)重癱瘓。救災(zāi)指揮部緊急派出多支小分隊(duì)，到各個(gè)指定區(qū)域執(zhí)行搜索任務(wù)。在這種緊急情況下需要解決的重要問題之一是：制定搜索隊(duì)伍的行進(jìn)路線，對預(yù)定區(qū)域進(jìn)行快速的全面搜索。通常，每個(gè)搜索人員都帶有g(shù)ps定位儀、步話機(jī)以及食物和生活用品等裝備。隊(duì)伍中還有一定數(shù)量的衛(wèi)星電話。gps可以讓搜索人員知道自己的方位。步話機(jī)可以相互進(jìn)行通訊。衛(wèi)星電話用來向指揮部報(bào)告搜索情況。下面是一個(gè)簡化的搜索問題。有一個(gè)平地矩形目標(biāo)區(qū)域，大小為11200米×7200米，需要進(jìn)行全境

5、搜索。假設(shè)：出發(fā)點(diǎn)在區(qū)域中心；搜索完成后需要進(jìn)行集結(jié)，集結(jié)點(diǎn)（結(jié)束點(diǎn)）在左側(cè)短邊中點(diǎn)；每個(gè)人搜索時(shí)的可探測半徑為20米，搜索時(shí)平均行進(jìn)速度為0.6米/秒；不需搜索而只是行進(jìn)時(shí),平均速度為1.2米/秒。每個(gè)人帶有g(shù)ps定位儀、步話機(jī)，步話機(jī)通訊半徑為1000米。搜索隊(duì)伍若干人為一組,有一個(gè)組長，組長還擁有衛(wèi)星電話。每個(gè)人搜索到目標(biāo)，需要用步話機(jī)及時(shí)向組長報(bào)告，組長用衛(wèi)星電話向指揮部報(bào)告搜索的最新結(jié)果。現(xiàn)在有如下問題需要解決：1假定有一支20人一組的搜索隊(duì)伍, 擁有1臺衛(wèi)星電話。請?jiān)O(shè)計(jì)一種你認(rèn)為耗時(shí)最短的搜索方式。按照你的方式，搜索完整個(gè)區(qū)域的時(shí)間是多少? 能否在48小時(shí)內(nèi)完成搜索任務(wù)? 如果不能

6、完成，需要增加到多少人才可以完成。2為了加快速度，搜索隊(duì)伍有50人，擁有3臺衛(wèi)星電話，分成3組進(jìn)行搜索。每組可獨(dú)立將搜索情況報(bào)告給指揮部門。請?jiān)O(shè)計(jì)一種你認(rèn)為耗時(shí)最短的搜索方式。按照你的搜索方式, 搜索完整個(gè)區(qū)域的時(shí)間是多少? 二、符號說明：為0、1變量，表示是否選擇某條路，其形式為表示不選擇，表示選擇走該路；：表示從第點(diǎn)到第點(diǎn)的路程距離，兩點(diǎn)間沒有路的用無窮大表示，自己到 自己距離為0；：搜索道的寬度；：起點(diǎn)到終點(diǎn)的直線距離為5600米；：各個(gè)組的起點(diǎn)到各自的搜索起點(diǎn)的距離； ：第組的人數(shù)（）；：第組所搜索的區(qū)域的寬度。：搜索完成的最短總時(shí)間。 三、條件假設(shè)1搜救人員按直線行進(jìn)；2地面情況對搜

7、救人員的行進(jìn)速度無影響；3搜救人員向上級報(bào)告對搜索進(jìn)度無影響； 四、問題分析問題一： 1本問題要求設(shè)計(jì)20人一組的耗時(shí)最短的搜索13方式，為保證時(shí)間最短，首先要求20人每秒搜索的面積盡可能大，所以須并排相切站隊(duì)。由于每人步話機(jī)的通訊半徑為1000米，為保證每個(gè)搜索隊(duì)員搜索到目標(biāo)及時(shí)向組長報(bào)告，只要搜索寬度不超過1000米，即可保證通訊。因?yàn)椋?0人并排搜索的最寬距離為20×40=800米，所以20人可以同時(shí)并排向前搜索。2由于目標(biāo)區(qū)域?yàn)榫匦吻议L寬不同，因此有橫向搜索與縱向搜索兩種方式。由于20人的最大搜索寬度為800米，因此橫向搜索道路可分為7200/800=9個(gè)搜索道（圖4-1），

8、縱向搜索道路可分為11200/800=14個(gè)搜索道（圖4-2）。 圖4-1 橫向搜索道 圖4-2 縱向搜索道由圖示可見，雖然橫向道和縱向道的道數(shù)不同，但橫向搜索距離（9×11200=100800）和縱向搜索距離（14×7200=100800）相同。而縱向道的道數(shù)多，轉(zhuǎn)彎就多，所用時(shí)間比橫向道所用時(shí)間長。因此最短時(shí)間的搜索方式應(yīng)以橫向道搜索進(jìn)行。為使問題求解簡化，可將搜索道轉(zhuǎn)化為距離圖。根據(jù)搜索起始點(diǎn)的位置我們考慮兩種搜索方式：搜索方式一：搜索起點(diǎn)在目標(biāo)區(qū)域的中心，按照橫向搜索方式，根據(jù)圖論及優(yōu)化理論建立0-1規(guī)劃模型。搜索方式二：搜索起點(diǎn)在最上面或最下面道的端點(diǎn)。按照橫向搜

9、索方式，建立了通用模型。問題二：為了加快速度， 搜索隊(duì)伍50人需分三組。分組原則考慮按橫向均勻分區(qū)和橫向分為三種不同的道寬兩種情況進(jìn)行地毯式搜索，搜索均從矩形道的頂角橫向掃描，到達(dá)終點(diǎn)，最后比較兩種方式的最短搜索時(shí)間，較小者為完成搜索的最短時(shí)間。情況一：橫向均勻分道由于道可以均勻分，因此可將道從上之下分為上、中、下三個(gè)部分，讓50個(gè)人分為三組分別到達(dá)各自部分的頂角，然后從頂角橫向搜索最后到達(dá)終點(diǎn)，由于問題一得出的結(jié)論為在人數(shù)多的時(shí)候道越寬用的時(shí)間也越短，因此50個(gè)人分為3組時(shí)應(yīng)該分為16、17、17個(gè)，此時(shí)道寬應(yīng)該按照16個(gè)人的搜索最大橫徑16×40=640米進(jìn)行搜索，這樣分得到的道

10、為最少，即7200/640=12個(gè)（見圖4-3），道寬為7200/12=600米。 圖4-3 均勻分為12個(gè)道由于分為三組，因此可將12個(gè)道均勻分為3個(gè)部分，每個(gè)小組各自先從起點(diǎn)到達(dá)自己搜索區(qū)域的頂角然后進(jìn)行地毯式搜索，最后回到終點(diǎn)，由此得到兩種搜索方式（圖5-8、5-9），按照搜索方式，根據(jù)問題一的分析，起點(diǎn)到搜索起點(diǎn)和矩形邊界上前進(jìn)的速度為1.2米/秒，搜索時(shí)速度為0.6米/秒，可計(jì)算出每種方式中每個(gè)組從起點(diǎn)到終點(diǎn)的時(shí)間，最后兩種方式中誰用的時(shí)間最短就為使橫向均勻分道的搜索時(shí)間最短的搜索方式。情況二：橫向分為三種不同的道寬情況一中考慮了均分，在50人分為16、17、17時(shí)，道寬是按照16人

11、的搜索距離640米分的道，每道道寬600米，分12個(gè)道，因此用17人去搜索的時(shí)候在道與道之間就重復(fù)了相當(dāng)大的搜索面積，因此浪費(fèi)了人員；由于搜索面積都一樣大，前面分析了對總的影響時(shí)間最大的就是分道，道越多時(shí)間就越長，因此我們考慮將50個(gè)人分三組，道寬分為三種，把整個(gè)面積按照情況一考慮，仍然分為三個(gè)區(qū)域給三個(gè)組走，我們的目的是三個(gè)區(qū)域各自均勻分道，因此就產(chǎn)生了三個(gè)道寬，由于終點(diǎn)在矩形中間，因此每個(gè)區(qū)域的寬度不能超過3600，否則時(shí)間肯定比圖13大，在這個(gè)基礎(chǔ)之上我們再考慮人員分配的差異不能太大，盡量均衡（也就是區(qū)域的寬度盡量相當(dāng)），要時(shí)間最短三個(gè)區(qū)域的分道的道數(shù)一定要相同，但是考慮通訊1000米，

12、我們認(rèn)為每組的的人員最多為1000/40=25人，我們的目的看能否安排50個(gè)人分三組分三個(gè)區(qū)域從原來的4個(gè)道減少數(shù)目，這樣搜索時(shí)間就更短了，另外考慮盡量讓人不浪費(fèi)，因此每個(gè)區(qū)域的道寬和其對應(yīng)人員搜索距離盡量之間的差異盡量小，且三個(gè)區(qū)域的差異相對比例保持基本平衡，由此，建立一個(gè)規(guī)劃模型可解決該問題。 五、模型的建立與求解問題一：從問題分析中我們確立了20個(gè)人均勻并排成道寬800米同時(shí)進(jìn)行橫向直線搜索的方案。（一）搜索道模型：根據(jù)問題分析建立的搜索道模型用圖5-1、5-2表示為： 圖5-1 人員向道兩邊依次散開 圖5-2人員搜索抵達(dá)邊界以橫向道為準(zhǔn)，由于要時(shí)間最短，每個(gè)人都應(yīng)同時(shí)進(jìn)行搜索且考慮一并

13、排相切的方式垂直矩形的邊進(jìn)行搜索，剛好為一個(gè)搜索道，因此在上面的道上20個(gè)人都應(yīng)該并排從起點(diǎn)向道上散開為800米占道（圖5-1）；另外，每個(gè)人搜索面積是圓形的，因此要求20人一起的搜索時(shí)每個(gè)人都同時(shí)抵達(dá)矩形的最邊沿（圖5-1），這樣才能保證全部搜索完所有的面積。（二）距離圖的建立：把20個(gè)人看作一個(gè)點(diǎn)、搜索道看作一條邊，相鄰搜索道之間的距離為800米，以出發(fā)點(diǎn)和結(jié)束點(diǎn)及橫向道兩端點(diǎn)構(gòu)成一個(gè)距離圖4（圖5-3）。圖5-3 距離圖（三）兩種搜索方式下的模型建立與求解搜索方式一 根據(jù)距離圖，可建立從起點(diǎn)到終點(diǎn)搜索完面積的總路程最短的0-1規(guī)劃5，6模型為：目標(biāo)函數(shù)，總路程最小： 限制條件： 1）從起

14、點(diǎn)到其它點(diǎn)的邊之和大于等于1，保證至少有邊出去，則有： 2）所有點(diǎn)到終點(diǎn)的邊之和大于等于1，保證至少有邊到達(dá)終點(diǎn)，有： 3）中間點(diǎn)進(jìn)去和出去的邊要守恒，有： 4）所有搜索路徑必須走完，有： 5）對于從起點(diǎn)到終點(diǎn)的路必須連通，不能形成脫離的圈； 5）對于所有，有綜合以上，得到我們起點(diǎn)到終點(diǎn)滿足搜索路徑必走的條件的最短路的0-1規(guī)劃模型為： （模型一）根據(jù)建立的模型，利用lingo8.0軟件7編程（程序一）求解，得到起點(diǎn)到終點(diǎn)的最短路徑（圖5-4）為：圖5-4 最短路徑圖注： 圖中小括號的數(shù)字標(biāo)記為搜索的次序標(biāo)記，也為最短路的走向標(biāo)記。圖中從起點(diǎn)到終點(diǎn)的路程為： v1（起點(diǎn)）v2v7v15v16v

15、17v9v10v18v17v16v8v7v2v1v19v14v13v12v11v6v5v12v13v4v3v14v19（終點(diǎn)），總路程為119200米，共27條邊，其中有9條為搜索路（1、3、6、8、11、15、20、22、24、26），有16條邊界路（2、4、5、7、9、10、12、13、16、17、18、19、21、23、25、27），還有一條重復(fù)搜索路（14）。（1）最短時(shí)間的計(jì)算：按照要求，邊界路和重復(fù)的搜索路的行使速度為1.2米/秒，搜索路為0.6米/秒，因此根據(jù)6中的結(jié)果可以計(jì)算出最短搜索時(shí)間為： （小時(shí)）另在開始隊(duì)伍從起點(diǎn)處向兩邊散開占道和隊(duì)伍到達(dá)終點(diǎn)處匯聚需要時(shí)間，由于起點(diǎn)和終

16、點(diǎn)都是在中間道的中點(diǎn)上，因此散開和匯聚的的距離均只有400-20=380米，所用時(shí)間為： （小時(shí)）因此，隊(duì)伍從起點(diǎn)搜索完這個(gè)面積到達(dá)終點(diǎn)的總的最短時(shí)間為： （小時(shí)）綜上，我們把搜索矩形目標(biāo)區(qū)域的路線轉(zhuǎn)換為距離圖，利用圖論通過建立滿足條件的起點(diǎn)到終點(diǎn)的最短路徑的0-1規(guī)劃模型，最后計(jì)算得到搜索的走向，以及搜索完成的最短總時(shí)間為51.1018小時(shí)，因此，認(rèn)為20人一組是不可能在48小時(shí)之內(nèi)完成任務(wù)的。（2）增加人數(shù)的模型建立與求解根據(jù)上面的結(jié)果，20人一組是不能在48小時(shí)內(nèi)完成搜索任務(wù)。因此用增加人數(shù)、減少搜索道數(shù)來縮短搜索時(shí)間。而增加人數(shù)可減少搜索道，因此可將矩形目標(biāo)區(qū)域均勻分為橫向8道、7道、

17、6道等等，直到得到的時(shí)間剛好小于48小時(shí)時(shí)，增加的人數(shù)就為最少。此時(shí)增加的人數(shù)可以用道寬來計(jì)算。根據(jù)以上的分析，橫向9道為奇數(shù)道，起點(diǎn)和終點(diǎn)在中間道的中間。但搜索道數(shù)目為偶數(shù)時(shí)，起點(diǎn)和終點(diǎn)在中間兩道的交界線上，例如8道時(shí)的道寬為米（圖5-5），那么在從起點(diǎn)向道分散開或向終點(diǎn)聚攏時(shí)的時(shí)間均為整個(gè)道寬，此時(shí)時(shí)間為小時(shí)，利用上面思想將搜索圖轉(zhuǎn)化為距離圖則為（圖5-6）。 圖5-5 8個(gè)道的橫向搜索道 圖5-6 8個(gè)道的距離圖同樣按照前面的模型我們可以得到8個(gè)橫向道的最短走向圖（5-7）： 圖5-7 8個(gè)搜索道的起點(diǎn)到終點(diǎn)搜索完的最短路徑圖圖中小括號的數(shù)字標(biāo)記為搜索的次序標(biāo)記，也為最短路的走向標(biāo)記，共

18、24條邊，其中有9條為搜索路（1、3、5、7、15、17、19、21、23），有14條邊界路（2、4、6、8、9、10、11、12、13、14、16、18、20、22），還有一條重復(fù)搜索路（24）。因此綜合奇數(shù)和偶數(shù)搜索道綜合考慮，在搜索區(qū)域分為道路時(shí)，都重復(fù)一條長為5600米搜索路，且搜索長為11200米的搜索道為條，搜索時(shí)走的邊界道寬的數(shù)量為條，因此我們可以建立以這種方式搜索的最短時(shí)間的通用模型，設(shè)道寬為，則最短路的最小時(shí)間為：還要考慮，在開始隊(duì)伍從起點(diǎn)要向道散開占道和到達(dá)終點(diǎn)聚攏需要的時(shí)間為：因此，按照我們的方法得到搜索的最短總時(shí)間的通用模型為： （模型二）對于可以增加的人數(shù)可以建立優(yōu)化

19、模型：目標(biāo)增加人數(shù)最少，設(shè)增加的人數(shù)為個(gè)，我們的目標(biāo)是使得增加人數(shù)最少有。綜上得到增加人數(shù)的動態(tài)優(yōu)化模型8： （模型三）這里，對于分個(gè)道，我們從題目可以考慮通訊問題，組里其他人員必須及時(shí)向組長報(bào)告情況，因此每個(gè)人和組長的最長距離為1000米，我們考慮把組長放在中間，因此隊(duì)員之間的最大距離為2000米，因此以2000米橫排搜索，這里7200/200=3.6，最少都要分4個(gè)道。利用lingo8.0軟件（程序二）依次取n=8,7,6,5,4求解分別得到結(jié)果為下表表5-1 不同分道在48小時(shí)以內(nèi)完成增加的最少人數(shù)分道數(shù)（n）增加人數(shù)（個(gè)）完成時(shí)間（小時(shí)）8346.10197640.678661035.

20、731551630.21342524.9444因此，建立了一個(gè)通用的模型可以適合任意的分道。由此看，最少增加3個(gè)人就可以完成任務(wù)，且總時(shí)間最小為46.019小時(shí)。搜索方式二 搜索起點(diǎn)在最上面或最下面道的端點(diǎn)的模型建立根據(jù)問題分析，得到奇數(shù)道和偶數(shù)道的最優(yōu)地毯式搜索路徑分別為（圖5-8、5-9）： 圖5-8 奇數(shù)道地毯式圖 圖5-9 偶數(shù)道地毯式圖從圖看奇數(shù)道應(yīng)該從起點(diǎn)到右邊的最上面或最下面道上，而偶數(shù)道從起點(diǎn)到左邊的最上面或最下面道上，這樣可以保證走的路徑最短，時(shí)間也最短。從圖5-8看，9道時(shí)以0.6米/秒的速度走了9條11200的道，以1.2米/秒的速度走了道寬12條道寬加半個(gè)道寬及從起點(diǎn)到

21、搜索起點(diǎn)的距離；而圖5-9的8道時(shí)以0.6米/秒的速度走了8條11200的道，以1.2米/秒的速度走了道寬10條道寬加半個(gè)道寬及從起點(diǎn)到搜索起點(diǎn)的距離；因此可以總結(jié)得到奇數(shù)道和偶數(shù)道共同的1120道數(shù)為道，而道寬條數(shù)為條，奇數(shù)的多了0.5條，從圖看起點(diǎn)到搜索起點(diǎn)的距離為起點(diǎn)到終點(diǎn)的距離和終點(diǎn)到搜索起點(diǎn)的平方和開方，設(shè)起點(diǎn)到終點(diǎn)距離為（1120米），終點(diǎn)到搜索起點(diǎn)的距離為（3600米），設(shè)道寬為，因此可以得出計(jì)算最短時(shí)間的通用模型為： （模型四）通過模型我們計(jì)算得到9道搜索的最短時(shí)間為50.5255小時(shí)，48個(gè)小時(shí)不能完成搜索；8道的道寬為900米，因此20個(gè)人的搜索橫徑為800米，不夠，因此根

22、據(jù)900/40=22.5，最少還需要加3個(gè)人才能滿足條件，另外我們考慮所有人最大只能相隔1000米因此最多只能25個(gè)人一組，23個(gè)人滿足條件，最后得到的8道時(shí)間為45.1059小時(shí)，可以在48個(gè)小時(shí)以內(nèi)完成任務(wù)，比前面時(shí)間更短。因此我們認(rèn)為這種方式比上面直接從起點(diǎn)開始的地毯式搜索時(shí)間要短些，搜索路徑更好一點(diǎn)。 我們可以根據(jù)9中的模型可以分別取，用lingo8.0（程序三）求解可以得到以下結(jié)果：表5-2 不同分道在48小時(shí)以內(nèi)完成增加的最少人數(shù)分道數(shù)（n）增加人數(shù)（個(gè)）完成時(shí)間（小時(shí)）8345.10597639.861261034.318951628.967042523.1151由表可以知道，此

23、搜索方法的結(jié)果每減少一道增加的人數(shù)和9中的一樣，但對應(yīng)的搜索時(shí)間明顯低于9中的搜索時(shí)間。說明這種搜索方式比前面要好一點(diǎn)。問題二：根據(jù)問題分析分橫向均勻分道和橫向分為三種不同的道寬兩種方式進(jìn)行地毯式搜索（一）橫向均勻分道根據(jù)問題分析確定的兩種搜索方式，如（圖5-10、5-11）： 圖5-10 圖5-11虛線箭頭為各個(gè)組開始的地毯式搜索方向，從圖看起點(diǎn)和終點(diǎn)均在中間，因此1組和3組所用的時(shí)間相同，但是1，2，3組在進(jìn)行區(qū)域的地毯式搜索中的區(qū)域時(shí)間相同，均為搜索4次11200米和轉(zhuǎn)3個(gè)邊界道寬，不同的是1與2、3在從起點(diǎn)到達(dá)各自的搜索起點(diǎn)的路程不同，且從搜索完畢后回到終點(diǎn)的邊界路上用的時(shí)間也不同；圖

24、5-10中1、3組從地毯式搜索完畢要經(jīng)3個(gè)道寬人員全部回到終點(diǎn)，2組則從地毯式搜索完畢經(jīng)2個(gè)道寬人員回到終點(diǎn)；圖5-11中的2組和圖5-10中的2組一樣，1、3組則從地毯式搜索完畢經(jīng)6個(gè)道寬人員回到終點(diǎn)，但是與圖5-11不一樣的就在1、3組到達(dá)自己搜索頂角的路程比圖5-11短。結(jié)合問題分析綜合，圖5-10中1、3組各自總共經(jīng)過一個(gè)1.2米/秒的對角線到達(dá)自己的搜索起點(diǎn)，再經(jīng)過4次0.6米/秒的地毯式搜索，各自共經(jīng)過6個(gè)1.2米/秒的邊界道寬到達(dá)終點(diǎn)，2組總共經(jīng)過一個(gè)1.2米/秒的對角線到達(dá)自己的頂角，再經(jīng)過4次0.6米/秒的地毯式搜索，共經(jīng)過5個(gè)1.2米/秒的邊界道寬到達(dá)終點(diǎn)；圖5-11的2組

25、與圖5-10一樣，1、3組各自總共經(jīng)過一個(gè)1.2米/秒的對角線到達(dá)自己的搜索起點(diǎn)，再經(jīng)過4次0.6米/秒的地毯式搜索，各自共經(jīng)過9個(gè)1.2米/秒的邊界道寬到達(dá)終點(diǎn)由此可計(jì)算出各個(gè)組的搜索總時(shí)間，設(shè)道寬為，起點(diǎn)到終點(diǎn)的距離為，各個(gè)組的起點(diǎn)到各自的搜索起點(diǎn)的距離為，設(shè)各個(gè)組經(jīng)過共經(jīng)過的邊界道寬的條數(shù)為條。因此第個(gè)組搜索的最短總時(shí)間的模型為： （模型五）通過此公式結(jié)合數(shù)據(jù)，計(jì)算出圖5-10和圖5-11兩種搜索方式的各組的搜索時(shí)間，各組中搜索時(shí)間最長的即為搜索的最短總時(shí)間，分別為：圖5-10有： 小時(shí) 小時(shí)因此圖5-10的搜索方式的最短總時(shí)間為23.1151小時(shí)。圖5-11有： 小時(shí) 小時(shí)因此圖5-1

26、1的搜方式的最短總時(shí)間為23.3524小時(shí)。總上，認(rèn)為均勻分道時(shí)，搜索方式以圖5-10的方式為最好，搜索的最段總時(shí)間為23.1151小時(shí)，所以在搜索的時(shí)候應(yīng)該選擇圖5-10的方式進(jìn)行搜索。（二）橫向分為三種道寬：建立一個(gè)規(guī)劃模型設(shè)三個(gè)組的人為，三個(gè)區(qū)域的寬度為，三個(gè)區(qū)域分的道數(shù)為個(gè)，我們的目標(biāo)就是使得分的道數(shù)最小和各個(gè)組搜索橫徑與道寬的相對差異保持平衡，橫徑平衡用指標(biāo)表示，道寬盡量平衡用指標(biāo)表示，則有：對于各個(gè)區(qū)域的道寬必須滿足：；對于人數(shù)有：；對于總寬度有：；由于終點(diǎn)在半矩形的中間，因此三個(gè)區(qū)域?qū)挾扔校海蝗藬?shù)盡量均衡：；每組人員數(shù)目的限制：；對于各個(gè)組搜索橫徑與道寬的相對差異保持平衡有： ；

27、 ；因此模型歸納為： （模型六）利用lingo8.0（程序四）軟件求解得：、，各個(gè)區(qū)域的道寬分別為576、612、612米，各個(gè)區(qū)域的分道數(shù)目仍然為4，不能減少，人員分配數(shù)目和原來的一樣，只是區(qū)域?qū)挾茸兞?，其大致圖為（圖5-12）： 圖5-12 優(yōu)化后的分道圖由于仍然分4道，按照圖5-10的分析，上圖1、3組的時(shí)間相同且比2組肯定大，因此最后計(jì)算的總時(shí)間為： 小時(shí)和圖5-10的時(shí)間一樣，因此按照橫向均勻分道和橫向分為三種道寬這兩種情況進(jìn)行搜索都可以得到耗時(shí)最短的搜索方式，搜索完整個(gè)區(qū)域的時(shí)間為23.1151小時(shí)。六、模型的進(jìn)一步分析在問題二中優(yōu)化后橫向分為三種道寬的規(guī)劃模型，求得的最短時(shí)間與橫

28、向均勻分道一樣，人員仍然處于浪費(fèi)狀態(tài)，由此認(rèn)為優(yōu)化了以后的模型還是不能改變時(shí)間的問題。因此考慮到有人員的浪費(fèi)，我們對模型進(jìn)行進(jìn)一步優(yōu)化，減少人員但保持剩余人員仍然分三個(gè)組，同樣分為三個(gè)區(qū)域，每個(gè)區(qū)域均為4個(gè)道，盡量不浪費(fèi)人員，看在50個(gè)人的基礎(chǔ)上最多可以減少多少人能夠保持最短時(shí)間搜索完，三個(gè)區(qū)域的寬度盡量保持一致，設(shè)最多減少個(gè)人，因此我們的模型又建立為： （模型七）利用lingo8.0（程序五）軟件求解得：、，走法和圖5-10一樣，搜索的總時(shí)間也為23.1151小時(shí)，最多可以減少5個(gè)人在同樣的時(shí)間里也可以完成任務(wù)。即只需要45個(gè)人，浪費(fèi)了5個(gè)人。此外此模型可以改進(jìn)得到在規(guī)定時(shí)間規(guī)定組數(shù)完成的搜

29、索的人員分配，安排多少人來完成任務(wù)，也可以實(shí)現(xiàn)規(guī)定人數(shù)的人員分組問題，是一個(gè)推廣性很好的數(shù)學(xué)模型。七、模型的優(yōu)缺點(diǎn) （一）優(yōu)點(diǎn)：1把求走完區(qū)域面積所用時(shí)間最少問題巧妙的轉(zhuǎn)化為求兩點(diǎn)之間最短路徑問題,并巧妙的運(yùn)用0-1規(guī)劃解決圖論問題；2在問題一中建立了不同搜索道數(shù)所需的最短時(shí)間通用模型,可便捷的解決該類問題,使模型更具有適用性和推廣性；3采用各組人人緊密、并排式搜尋，避免了因?yàn)槭転?zāi)人較小范圍內(nèi)從未搜區(qū)域移動到已搜區(qū)域而引起的漏檢問題。4整篇文章采用文字與圖形結(jié)合說明，用圖則使問題簡單化，清晰化,更生動、形象說明各種路徑及各編隊(duì)過程。 （二）不足： 1本文只考慮了人員并排以圓相切的方式進(jìn)行搜索，

30、實(shí)際上還可以考慮是否可以以圓相交的方式進(jìn)行搜索，可能還會存在很多搜索方式使得時(shí)間更短。 2本文是考慮人與人并排相切搜索，還可以考慮相離的時(shí)候搜索的情況，另外本文只考慮了以直線路線行進(jìn)，可考慮曲線路徑時(shí)間更短，由于時(shí)間和技術(shù)等方面的限制，這些研究可以今后待續(xù)。 參考文獻(xiàn)1 勞倫斯，斯通，吳曉峰.最優(yōu)搜索理論.北京：海潮出版社，1990.2 吳曉鋒.白樺.最優(yōu)搜索理論的進(jìn)展j.運(yùn)籌學(xué)學(xué)報(bào)，1992年02期.3 朱清新.最優(yōu)搜索理論及其應(yīng)用j.世界科技研究與發(fā)展，2005年04期.4 盧開澄，盧華明著.圖論及其應(yīng)用. 北京：清華大學(xué)出版社，2005.1.5 姜啟源，邢文訓(xùn)，謝金星等.大學(xué)數(shù)學(xué)實(shí)驗(yàn).北

31、京：清華大學(xué)出版社，2005.5.6 wayne l.winston著.運(yùn)籌學(xué)-應(yīng)用范例與解法.北京：清華大學(xué)出版社，2006.7 謝金星，薛毅編著.優(yōu)化建模與lindolingo軟件.北京：清華大學(xué)出版社，2005.7. 8 董軍軍.動態(tài)規(guī)劃算法和貪心算法的比較與分析j，軟件導(dǎo)刊，2008.2.附 錄：lingo8.0求解程序問題1程序程序一：sets: a/1.19/:u; b/1.19/; l(a,b):v,y,c; endsets data:c=ole('files.','cc') ; enddata n=size(a); min=sum(l(i,j)|

32、i #ne# j:v(i,j)*c(i,j); for(l(i,j)|i#ne#j:v(i,j)>=y(i,j); sum(l(i,j)|i#ne#j:y(i,j)=n-1; for(a(i):for(b(j)|j #gt# 1 #and# j #ne# i:u(j)>=u(i)+y(i,j)-(n-2)*(1-y(i,j)+(n-3)*y(j,i);); for(a(i)|i #gt# 1:u(i)<=n-1-(n-2)*y(1,i);u(i)>=1+(n-2)*y(i,1); sum(b(j)|j #ne#1 :v(1,j)>=1; for(b(j)|j #n

33、e# 1 #and# j #ne# 19:sum(a(i):v(i,j)-sum(a(i):v(j,i)=0); sum(a(i)|i #lt# 19:v(i,19)>=1; v(1,2)+v(2,1)>=1;v(1,19)+v(19,1)>=1; v(3,14)+v(14,3)>=1;v(4,13)+v(13,4)>=1; v(5,12)+v(12,5)>=1;v(6,11)+v(11,6)>=1; v(7,15)+v(15,7)>=1;v(8,16)+v(16,8)>=1; v(9,17)+v(17,9)>=1;v(10,18)+v(18,10)>=1; for(l(i,j):bin(v(i,j);bin(y(i,j);程序二： 當(dāng)n為奇數(shù)時(shí)min=m;n=5;d=7200/n;40*(20+m)>=d;(11200*n/0.6+(560