趙宇杰 周玲 梁曄 王哲慧 李志乾

【摘要】本文建立了關(guān)于“地面搜索”問題的簡潔數(shù)學(xué)模型。將平地矩形區(qū)域劃分成小的矩形帶狀，綜合最大流思想進行分析推理，得到了搜索隊員能夠采用的最短路徑搜索方式。此模型原理簡單，方法實用。

【關(guān)鍵詞】最大流問題；最短路徑；帶狀區(qū)域

地面搜索問題對現(xiàn)實的防災(zāi)抗災(zāi)工作,起著不可忽視的作用。在抗災(zāi)救災(zāi)的緊急情況下，制訂搜索隊伍的行進路線，對預(yù)定區(qū)域進行快速的全面搜索顯得尤為重要。

本文建立了關(guān)于“地面搜索”問題的數(shù)學(xué)模型：首先采用圖解法對所給平地矩形區(qū)域劃分成小的矩形單元；其次，對每個搜索隊員的搜索面積做了分析，區(qū)域劃分的原則是將總長與總寬按照隊員組合所得的最大搜索距離的整數(shù)倍進行分解，把整個區(qū)域劃分成相互不重疊的帶狀（矩形）區(qū)域；再次，綜合最大流思想進行分析推理，得到了搜索隊員的最佳組合就是并排搜索；最后利用最短路徑方法，得出最優(yōu)的結(jié)果。依據(jù)這個結(jié)果為“地面搜索”提供了一個比較清晰直觀的最短路徑安排方式。

問題敘述：對于一個平地矩形目標區(qū)域，大小為11200 m×7200 m，需要進行全境搜索。搜索時要求如下：出發(fā)點在區(qū)域中心；搜索完成后需要進行集結(jié)，結(jié)束點在左側(cè)短邊中點；每個人搜索時的可探測半徑為20 m，搜索時平均行進速度為0。6 m/s；不需搜索而只是行進時,平均速度為1。2 m/s。每個人帶有GPS定位儀、步話機，步話機通訊半徑為1000 m。搜索隊伍若干人為一組,有一個組長，組長還擁有衛(wèi)星電話。每個人搜索到目標，需要用步話機及時向組長報告，組長用衛(wèi)星電話向指揮部報告搜索的最新結(jié)果。

現(xiàn)在有如下問題需要解決：假定有一支20人一組的搜索隊伍,擁有1臺衛(wèi)星電話。請設(shè)計一種耗時最短的搜索方式，求出搜索完整個區(qū)域的時間，看能否在48小時內(nèi)完成搜索任務(wù)；如果不能完成，需要增加到多少人才可以完成。

模型的建立與算法：

一、模型假設(shè)

搜索人員的通訊良好,每個人單獨向組長匯報無干擾；搜索人員的身體素質(zhì)及搜索能力相同；不考慮余震帶來的其他干擾,如道路中斷或阻塞；該區(qū)域中天氣對搜索任務(wù)無明顯影響；每個搜索人員所帶食物及生活用品等充足；該搜索組在搜索途中無滯留。

二、模型的建立

1。最大流問題的基本假設(shè)為:

(1)網(wǎng)絡(luò)中所有流起源于一個節(jié)點,這個節(jié)點叫做發(fā)點S(也稱為源或始點)；所有的流終止于另一個節(jié)點,這個節(jié)點叫做收點E(也稱為匯或終點)；

(2)其余所有的節(jié)點叫做轉(zhuǎn)運點；

(3)通過每一段弧的流只允許沿著弧的箭頭所指的方向流動。由發(fā)點發(fā)出的所有弧背向發(fā)點,而所有終結(jié)于收點的弧都指向收點；

(4)最大流問題的目標是使得從發(fā)點到收點的總流量的大小可以用兩種等價的方法來衡量,分別叫做從出發(fā)點出發(fā)的流量和進入收點的流量。

2。根據(jù)最大流的定義，與本題目對比，可以將人數(shù)的多少與流量的大小相類比，讓所有的搜索人員在劃分的區(qū)域內(nèi)并排搜索，保證搜索區(qū)域不重復(fù)并且搜索時間盡可能的少。搜索人員的路徑是一個有向的流動，單位時間內(nèi)通過的人數(shù)不可能超過最多人數(shù)，每個拐點處通過的人數(shù)也應(yīng)相等，流入的流量應(yīng)等于流出的流量，即為實際的人數(shù)。

三、模型的分析與求解

以20人為一組的搜索隊伍，最短搜索路徑為圖1所示。