劉 鋒

(雞西大學(xué)電氣與信息工程系,黑龍江雞西 158100)

計(jì)算機(jī)在地面探測問題數(shù)學(xué)建模中的應(yīng)用研究

劉 鋒

(雞西大學(xué)電氣與信息工程系,黑龍江雞西 158100)

對(duì)于地面探測問題,我們建立了相關(guān)的最小路徑數(shù)學(xué)模型,利用MATLAB數(shù)學(xué)軟件和 CAD制圖軟件求解并作圖,利用VB語言進(jìn)行編程,模擬出整個(gè)探測過程?？紤]到實(shí)際情況,在探測過程中忽略了一些可能影響探測行進(jìn)速度的因素,著重對(duì)行進(jìn)路線的最小化進(jìn)行了最優(yōu)分析。在給出現(xiàn)有問題答案的同時(shí),還可利用該模型用盡可能少的人力和物力,在最短的時(shí)間內(nèi)完成對(duì)固定區(qū)域的全方位探測。

最小路徑分析;模糊數(shù)學(xué)模型;GPS定位儀;可行性方案

1 問題提出

5·12汶川大地震使震區(qū)地面交通和通訊系統(tǒng)嚴(yán)重癱瘓。救災(zāi)指揮部緊急派出多支小分隊(duì),到各個(gè)指定區(qū)域執(zhí)行探測任務(wù),以確定需要救助的人員的準(zhǔn)確位置。在其他場合也常有類似的探測任務(wù)。在這種緊急情況下需要解決的重要問題之一是:制定探測隊(duì)伍的行進(jìn)路線,對(duì)預(yù)定區(qū)域進(jìn)行快速的全面探測。通常,每個(gè)探測人員都帶有 GPS定位儀、步話機(jī)以及食物和生活用品等裝備。隊(duì)伍中還有一定數(shù)量的衛(wèi)星電話。GPS可以讓探測人員知道自己的方位。步話機(jī)可以相互進(jìn)行通訊。衛(wèi)星電話用來向指揮部報(bào)告探測情況。

下面是一個(gè)簡化的探測問題。有一個(gè)平地矩形目標(biāo)區(qū)域,大小為11 200m×7 200m,需要進(jìn)行全境探測。假設(shè):出發(fā)點(diǎn)在區(qū)域中心;探測完成后需要進(jìn)行集結(jié),集結(jié)點(diǎn) (結(jié)束點(diǎn))在左側(cè)短邊中點(diǎn);每個(gè)人探測時(shí)的可探測半徑為 20m,探測時(shí)平均行進(jìn)速度為0.6m/s;不需探測而只是行進(jìn)時(shí),平均速度為1.2m/s。每個(gè)人帶有 GPS定位儀、步話機(jī),步話機(jī)通訊半徑為1 000m。探測隊(duì)伍若干人為一組,有一個(gè)組長,組長還擁有衛(wèi)星電話。每個(gè)人探測到目標(biāo),需要用步話機(jī)及時(shí)向組長報(bào)告,組長用衛(wèi)星電話向指揮部報(bào)告探測的最新結(jié)果?，F(xiàn)在有如下問題需要解決:

(1)假定有一支 20人一組的探測隊(duì)伍,擁有 1臺(tái)衛(wèi)星電話。請(qǐng)?jiān)O(shè)計(jì)一種你認(rèn)為耗時(shí)最短的探測方式。按照你的方式,探測完整個(gè)區(qū)域的時(shí)間是多少?能否在 48h內(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í)間是多少?

2 模型假設(shè)與說明

2.1 模型假設(shè)

(1)假設(shè)在探測過程中不考慮余震、天氣、個(gè)人等因素對(duì)探測進(jìn)程的影響;

(2)假設(shè)在探測過程中 GPS定位儀、步話機(jī)、衛(wèi)星電話等設(shè)備不出故障;

(3)假設(shè)在探測到某目標(biāo)后無時(shí)間間隔繼續(xù)探測下一目標(biāo)。

2.2 符號(hào)說明

Si(i=1,2,3,4…)S為各段路程,i為各段路程順序號(hào);Ti(i=1,2,3,4…)T為各段路程探測或行進(jìn)使用的時(shí)間,i為各段路程順序號(hào);ti′(i=1,2,3,4…)甲組各段探測路徑所需時(shí)間;ti(i=1,2,3,4…)丙組各段探測路徑所需時(shí)間;V1探測時(shí)平均行進(jìn)速度;V2不需探測只行進(jìn)時(shí)平均速度;Ts為 B完成探測任務(wù)的時(shí)間;Tg為 B在拐彎處探測時(shí)間;T完成總?cè)蝿?wù)的時(shí)間;A探測隊(duì)伍中左側(cè)排頭;B探測隊(duì)伍中左側(cè)排頭;r每個(gè)人探測時(shí)的可探測半徑。

3 模型的建立與求解

3.1 問題一

考慮到每個(gè)人探測到目標(biāo),需要用步話機(jī)及時(shí)向組長報(bào)告,組長用衛(wèi)星電話向指揮部報(bào)告探測的最新結(jié)果,則在探測隊(duì)伍中每名探測隊(duì)員應(yīng)該與組長保持一定的距離 (原則上不能超過1 000m)我們可先將隊(duì)伍排成一排,組長位于中間位置,由于每名隊(duì)員的可探測的半徑為 r=20m,則此時(shí)隊(duì)伍排頭隊(duì)員與組長的距離為 380m<1 000m。為了對(duì)該平地矩形目標(biāo)區(qū)域進(jìn)行全境探測,我們可進(jìn)行地毯式掃描探測。

隊(duì)伍在行進(jìn)過程中的拐彎處,右端排頭 A與左端排頭 B的探測面積不同,則行進(jìn)路程會(huì)存在一定差異。如果讓每名隊(duì)員始終以恒定的速度進(jìn)行探測則可能會(huì)出現(xiàn)部分隊(duì)員由于行進(jìn)太快,與組長失去聯(lián)絡(luò)等情況。因此我們假設(shè)在探測過程中組長隨時(shí)協(xié)調(diào)每名隊(duì)員的行進(jìn)速度以保證所有隊(duì)員與組長的距離始終在步話機(jī)的通訊半徑1 000m的范圍內(nèi)。

分析探測行進(jìn)路線 (如圖1),其中:粗實(shí)線表示探測隊(duì)伍中組長的探測行進(jìn)路線,細(xì)實(shí)線表示左端排頭隊(duì)員 B的探測行進(jìn)路線,20名隊(duì)員排成一排探測的距離是 800m,考慮行進(jìn)過程中隊(duì)員之間探測速度的差異以及拐角區(qū)域等因素影響,為便于計(jì)算我們把探測目標(biāo)區(qū)域等分成 14×9=126個(gè)800×800m2的矩形區(qū)域。

可以確定在探測過程中,隊(duì)伍左端排頭 B探測面積最大,耗時(shí)最長,因此我們只分析 B探測所用的時(shí)間 Ts,我們可根據(jù)探測路線將探測行程分成若干段,每段所用的時(shí)間為 Ti(i=1,2,3,4…)則有 :Ti=Si/Vi

(1)所有隊(duì)員以 V2=1.2m/s的速度從出發(fā)點(diǎn)到達(dá)指定探測開始位置,其中 B所用的時(shí)間

(2)隊(duì)伍排列完成后,所有隊(duì)員以 V1=0.6m/s的速度開始探測,為便于計(jì)算我們可根據(jù)探測路線將探測行程分成若干段,(如圖2)每段所用的時(shí)間為 Ti,

B在拐彎處會(huì)遇到探測拐角,因此要完成全境探測,B需要以 V1=0.6m/s的速度向左前方 45°進(jìn)行探測然后以 V2=1.2m/s的速度原路返回 (如圖3)。

則每一處拐角所花的時(shí)間 Tg有:

B在全程中共有 14處相同的拐角,由此我們可算出 B探測任務(wù)所用的時(shí)間 Ts

原有的 20名隊(duì)員 (以組長為代表)以 V2=1.2m/s的速度從出發(fā)點(diǎn)到達(dá)如上指定開始位置,隊(duì)員 C處于探測隊(duì)伍的左端。組長以 V2=1.2m/s的速度向前行進(jìn) 40m,然后以 Vi=0.6m/s的速度向前探測,同時(shí)隊(duì)員 C以 Vi=0.6m/s的速度探測 40×800m2的區(qū)域。當(dāng)隊(duì)員 C完成 40×800m2的探測任務(wù)到達(dá)另一端時(shí),組長已向前行進(jìn) 800m,此刻隊(duì)員 C以V2=1.2m/s的速度追趕其他隊(duì)員。當(dāng)隊(duì)員 C重新追上組長并處于探測隊(duì)伍的一端時(shí),組長再以 V2=1.2m/s的速度向前行進(jìn) 40m,然后以 V1=0.6m/s的速度向前探測,同時(shí)隊(duì)員C再以 V1=0.6m/s的速度探測 40×800m2的區(qū)域。當(dāng)隊(duì)員C又一次完成 40×800m2的探測任務(wù)到達(dá)另一端時(shí),組長又向前行進(jìn)了 800m,此刻隊(duì)員 C還需以 V2=1.2m/s的速度追趕組長。依次循環(huán),直到探測任務(wù)完成。該數(shù)學(xué)模型的相關(guān)計(jì)算如下:

組長以V2=1.2m/s的速度向前行進(jìn) 40m的距離所需的時(shí)間;隊(duì)員 C完成 40×800m2的區(qū)域探測任務(wù)到達(dá)另一端所需要的時(shí)間;ty時(shí)間內(nèi)組長向前行進(jìn)了 800m;此時(shí),組長與隊(duì)員 C的距離;此時(shí)隊(duì)員 C與組長的最遠(yuǎn)距離為903.77(m)<1 000m,也能保證隊(duì)員 C用步話機(jī)及時(shí)向組長報(bào)告;隊(duì)員 C追上組長的時(shí)間;此時(shí)組長又向前行進(jìn)了 800m;于是每個(gè)追趕循環(huán)過程,組長一共向前行進(jìn)了 800+800+40=1 640m。在每一個(gè)追趕循環(huán)過程中次方案比上一方案節(jié)省的時(shí)間為。分析路線圖可知組長共向前行進(jìn)100 800m,則整個(gè)過程中最多可有個(gè)追趕循環(huán)過程,則總共節(jié)省的時(shí)間。因?yàn)?48.43-0.56=47.87h<48h,所以上述方案可行,即增加一名隊(duì)員即可保證在 48h內(nèi)完成探測任務(wù)。

3.2 問題二

分組探測時(shí)仍可采用上題的數(shù)學(xué)模型,即隊(duì)員以并排方式,組長位于隊(duì)伍中間協(xié)調(diào)組員向前探測。根據(jù)線性規(guī)劃理論可將目標(biāo)區(qū)域分成三塊,讓每組隊(duì)員分別完成探測任務(wù)并到達(dá)集結(jié)點(diǎn)的時(shí)間差盡可能小,經(jīng)分析可分為甲組 20人,乙組 20人,丙組 10人,其各組探測路徑如圖4。

下面對(duì)每組探測路徑所需時(shí)間進(jìn)行數(shù)學(xué)計(jì)算:

(1)甲組。

在探測過程中,仍需要比較一組探測隊(duì)伍中左右兩端排頭組員的探測路徑長度,如上可只分析探測路徑最長的排頭組員的探測時(shí)間。經(jīng)分析甲組中右端排頭所需的時(shí)間最長,其各段探測路徑所需時(shí)間如下:

注:黑粗實(shí)線表示甲乙組(兩組對(duì)稱)探測隊(duì)伍中組長的探測行進(jìn)路線,灰粗實(shí)線表示組探測隊(duì)伍中組長的探測行進(jìn)路線,細(xì)虛線表示隊(duì)伍一端排頭隊(duì)員的探測行進(jìn)路線。

(2)乙組。

由于乙組隊(duì)伍探測完成所分區(qū)域及路徑與甲組完全相同,并且甲乙兩組組員人數(shù)相同,所以乙組隊(duì)伍探測完成所分區(qū)域所需的時(shí)間

(3)丙組。

采用相同的分析方法分析丙組隊(duì)伍中右端排頭組員的探測路徑,其所需時(shí)間如下:

分析三組隊(duì)伍探測完成各自所分區(qū)域所需的時(shí)間甲組20.13h、乙組20.13h、丙組19.84h。此方案在丙組完成任務(wù)20.13-19.84=0.29(h)后,甲乙兩組同時(shí)完成探測任務(wù),即整個(gè)目標(biāo)區(qū)域探測完成需要20.13h。最優(yōu)的探測方案應(yīng)為 3組隊(duì)伍同時(shí)完成任務(wù),鑒于0.29h相對(duì)于20.13比較短暫,且此方案探測路徑比較簡單,重復(fù)路線較少,因此,此方案可行。

4 模型的質(zhì)量分析

4.1 模型的優(yōu)點(diǎn)

(1)本模型利用函數(shù)及計(jì)算機(jī)編程方法直接對(duì)題中所給的數(shù)據(jù)進(jìn)行處理;

(2)此模型簡潔實(shí)用,運(yùn)行速度快,可操作性強(qiáng),有較強(qiáng)的使用性和可預(yù)測性;

(3)建模的方法和思想對(duì)其他類似問題也適用,易于在多個(gè)領(lǐng)域推廣,當(dāng)與類似問題結(jié)合時(shí),僅需改變模型中的某些參數(shù)。

4.2 模型的缺點(diǎn)

本模型中忽略因素較多,組長需及時(shí)協(xié)調(diào)隊(duì)員的行進(jìn),工作量較大,探測任務(wù)未全部完成時(shí),部分隊(duì)員已處于未工作狀態(tài)。

[1]薛定宇,陳陽泉.高等應(yīng)用數(shù)學(xué)問題的 MATLAB求解[M].北京:清華大學(xué)出版社,2004.

[2]何文章.大學(xué)數(shù)學(xué)實(shí)驗(yàn) [M].哈爾濱:哈爾濱工程大學(xué)出版社,1999.

[3]王兵團(tuán).數(shù)學(xué)建?；A(chǔ)[M].北京:北京交通大學(xué)出版社,清華大學(xué)出版社,2004.

TP391

A

1674-6341(2010)01-0047-04

2009-12-02

劉鋒 (1980-),男,黑龍江密山人,講師,軟件教研室主任,碩士,從事軟件開發(fā)和數(shù)據(jù)庫方向研究。

責(zé)任編輯:柴造坡