全國(guó)數(shù)學(xué)建模競(jìng)賽C題預(yù)覽

2008全國(guó)賽C題“地面搜索

”

解法淺談1各位專家、教練下午好！2一、2008全國(guó)賽C題題目:5.12汶川大地震使震區(qū)地面交通和通訊系統(tǒng)嚴(yán)重癱瘓。救災(zāi)指揮部緊急派出多支小分隊(duì)，到各個(gè)指定區(qū)域執(zhí)行搜索任務(wù)，以確定需要救助的人員的準(zhǔn)確位置。在其它場(chǎng)合也常有類似的搜索任務(wù)。在這種緊急情況下需要解決的重要問(wèn)題之一是:制定搜索隊(duì)伍的行進(jìn)路線，對(duì)預(yù)定區(qū)域進(jìn)行快速的全面搜索。通常，每個(gè)搜索人員都帶有GPS定位儀、步話機(jī)以及食物和生活用品等裝備。隊(duì)伍中還有一定數(shù)量的衛(wèi)星電話。GPS可以讓搜索人員知道自己的方位。步話機(jī)可以相互進(jìn)行通訊。衛(wèi)星電話用來(lái)向指揮部報(bào)告搜索情況。3下面是一個(gè)簡(jiǎ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)題需要解決:4問(wèn)題1:假定有一支20人一組的搜索隊(duì)伍,擁有1臺(tái)衛(wèi)星電話。請(qǐng)?jiān)O(shè)計(jì)一種你認(rèn)為耗時(shí)最短的搜索方式。按照你的方式，搜索完整個(gè)區(qū)域的時(shí)間是多少?能否在48小時(shí)內(nèi)完成搜索任務(wù)?如果不能完成，需要增加到多少人才可以完成。問(wèn)題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í)間是多少?5二、問(wèn)題1的分析1、對(duì)題意的理解（1）搜索完整個(gè)區(qū)域的時(shí)間,是指最后一名隊(duì)員從出發(fā)點(diǎn)到達(dá)集結(jié)點(diǎn)所用的時(shí)間.（2）能否在48小時(shí)內(nèi)完成搜索任務(wù),是指“純工作”時(shí)間能否控制在48小時(shí)內(nèi),不包括進(jìn)餐或休息時(shí)間.（3）題目?jī)H給出了搜索時(shí)的平均行進(jìn)速度,并未給出隊(duì)員停頓下來(lái)搜索一個(gè)半徑為20米的圓形區(qū)域需要花費(fèi)多少時(shí)間,因此對(duì)于搜索方式理解為在行進(jìn)中連續(xù)或分段連續(xù)進(jìn)行搜索.62、問(wèn)題的分析（1）搜索時(shí)間下限的估計(jì)需要搜索的面積為11200米×7200米=8064ⅹ104平方米,一個(gè)隊(duì)員的搜索半徑為20米,若將上述矩形區(qū)域劃分成40ⅹ40的小正方形,共有50400個(gè)小正方形,20個(gè)隊(duì)員,平均每個(gè)隊(duì)員要搜索2520個(gè)小正方形.一個(gè)隊(duì)員搜索一個(gè)小正方形的最短用時(shí)“轉(zhuǎn)向

”66.67秒“掃角

”“直穿

”40/0.6=66.67秒+“掃

角

”7“直穿”2520個(gè)小正方形需用時(shí)2520×66.67=168008.4秒=46.669小時(shí)（下限）（2）小組搜索方式的確定隊(duì)員之間要相互聯(lián)絡(luò),不能分得太開(kāi),20個(gè)隊(duì)員一字排開(kāi)能搜索的寬度為800米,將待搜索的矩形區(qū)域分成126個(gè)800ⅹ個(gè)正方形的搜索.“直穿”一個(gè)方塊,每個(gè)隊(duì)員需要搜索800米800的正方形,依次完成這126820號(hào)40ⅹ39=1560米以上不包括“掃角”,而每個(gè)隊(duì)員需“掃角”“轉(zhuǎn)向

”1號(hào)40米2號(hào)40ⅹ3

米……2200一次20號(hào)2號(hào)9稱1號(hào)為“內(nèi)拐”,20號(hào)為“外拐”內(nèi)拐一次用時(shí)87.38秒外拐一次用時(shí)2620.71秒三、模型的建立與求解如果不包括“掃角”與重復(fù)搜索,小組搜索一個(gè)方塊的距離為一定（1600米）,因此優(yōu)化的目標(biāo)是轉(zhuǎn)向最少。101112s.t.13一種近似解法1

、搜索線路的確定確定搜索線路的原則A盡量避免“空走

”B

盡量避免“轉(zhuǎn)向

”

C

盡量避免重復(fù)搜索14紅線代表1號(hào)

、藍(lán)線代表20號(hào)的搜索線路152、搜索時(shí)間的確定“轉(zhuǎn)向”32次,“直穿”94次具體1號(hào)內(nèi)拐17次，外拐15次；20號(hào)內(nèi)拐15次，外拐17次，20號(hào)最后到達(dá)集結(jié)點(diǎn).20號(hào)搜索用時(shí):=47.55小時(shí)20號(hào)總用時(shí):47.73小時(shí)20號(hào)出發(fā)及集結(jié)“空走”用時(shí):163、解的可行性驗(yàn)證組長(zhǎng)放在什么位置？假設(shè)隊(duì)員的信息在1000米的范圍內(nèi)可以相互交流，20號(hào)隊(duì)員的信息可傳達(dá)給19號(hào)隊(duì)員，如此通過(guò)數(shù)次傳遞，最終到達(dá)組長(zhǎng)處，為減少傳遞次數(shù)，將組長(zhǎng)放在11號(hào)位.在搜索過(guò)程中，只要保持相鄰兩個(gè)隊(duì)員的距離在1000米，就可以保證信息的傳達(dá).每“外拐”一次，相鄰兩個(gè)隊(duì)員中靠外的那個(gè)落后80米，若其后有一次“內(nèi)拐”，則追回這80米，因此，只有連續(xù)“外拐”12次以上相鄰兩個(gè)隊(duì)員間的距離才超過(guò)1000米，上述的搜索線路最多連續(xù)“外拐”5次，因此是可行的.綜合上面的討論,48小時(shí)內(nèi)可完成搜索任務(wù)17四、問(wèn)題2簡(jiǎn)解分析:為了盡量利用第一問(wèn)的解法，將50人分為20；20；10三組；對(duì)20人的組可直接利用前面的網(wǎng)格劃分；對(duì)10人的組，可將前面的800ⅹ800的網(wǎng)格細(xì)分為400ⅹ400的網(wǎng)格.在分配各組任務(wù)時(shí)，盡量做到均衡，兩個(gè)20人的組分配的搜索區(qū)域最好是對(duì)稱的.181920人組轉(zhuǎn)向8次，“直穿”4220號(hào)格外拐5次，內(nèi)拐3次20號(hào)搜索用時(shí):=19.268小時(shí)20號(hào)“空走”用20號(hào)總用時(shí):19.453小時(shí)1號(hào)總用時(shí):18.222小時(shí)時(shí):2010人組轉(zhuǎn)向31次，“直穿”691號(hào)拐17次，內(nèi)拐14次；10號(hào)外拐14，內(nèi)拐17次1號(hào)搜索用時(shí):=19.197小時(shí)1號(hào)“空走”用時(shí):綜上討論，全部50名隊(duì)員中10人組的1號(hào)最后到達(dá)，總用時(shí):19.475小時(shí)1號(hào)總用時(shí):19.475小時(shí)21五

、學(xué)生答卷中存在的問(wèn)題1.對(duì)題意缺乏理解“跳躍式瞬間搜索

”

“進(jìn)餐

、休息問(wèn)題

”2.文章表述不清許多無(wú)搜索線路圖3.遺漏部分區(qū)域4.計(jì)算有