求文檔: 2008全國大學(xué)生數(shù)學(xué)建模c題論文

【專家解說】：2008年C題 地面搜索模型 如何制定搜救隊(duì)伍的行進(jìn)路線，在最短的時(shí)間內(nèi)對預(yù)定區(qū)域進(jìn)行快速的全面搜索是在此緊急情況下需要解決的重要問題之一。本文旨在研究在一平地矩形區(qū)域上的地面搜索問題。 地面搜索模型 山東電力高等?？茖W(xué)校 班藝瀚 閆忠偉 韓麗萍 丁梅 指導(dǎo) 論文點(diǎn)評: 本文根據(jù)實(shí)際問題的實(shí)際背景應(yīng)用圖論建立了搜索數(shù)學(xué)模型,分析了搜索過程中路徑選擇策略問題，對20人搜索問題提出有效的整體搜索方案和路徑選擇，計(jì)算了完成全面搜索所需要的時(shí)間，并研究了完成搜索人物所需要的人數(shù)，得到了較好的結(jié)果。對50人搜索問題提出了分組和分區(qū)域方案。本文的創(chuàng)新之處在于文章對種方案的均衡性進(jìn)行了較為深入的討論。 中國石油大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 王子亭教授 2008/09/25 摘 要 2008年5月12日汶川發(fā)生里氏8.0級特大地震，使得震區(qū)地面交通和通訊系統(tǒng)嚴(yán)重癱瘓。如何制定搜救隊(duì)伍的行進(jìn)路線，在最短的時(shí)間內(nèi)對預(yù)定區(qū)域進(jìn)行快速的全面搜索是在此緊急情況下需要解決的重要問題之一。本文旨在研究在一平地矩形區(qū)域上的地面搜索問題。 在問題一中，我們首先給出了20人一組的搜索隊(duì)伍,搜索完整個(gè)區(qū)域至少需要 個(gè)小時(shí)這樣一個(gè)有利的結(jié)論。我們先采用圓滾動模型，但會出現(xiàn)隊(duì)員與組長聯(lián)系不到的缺點(diǎn)；經(jīng)分析，采用圖論中的賦權(quán)連通圖法可以改進(jìn)圓滾動模型的缺點(diǎn)，組長在任何位置都可以聯(lián)系到所有隊(duì)員，搜索中不存在重疊現(xiàn)象，且搜索用的時(shí)間最短，在賦權(quán)連通圖用 算法找到最小生成樹，在此生成樹中采用擴(kuò)環(huán)策略、增環(huán)策略、換枝策略的思想，經(jīng)過調(diào)整，采用拐彎、不拐彎兩種搜索方法，尋找到20人一組的最佳搜索路線。按此方式，我們得到這樣幾個(gè)結(jié)果： (1)搜索完整個(gè)平面矩形區(qū)域所用的時(shí)間為 小時(shí)。 (2)在 小時(shí)以內(nèi)不能完成搜索任務(wù)。 (3)增加到 人，在47.41小時(shí)內(nèi)可以完成搜索任務(wù)。 在問題二中，我們采用第一、二組各20人，第三組10人的分組方式，給出了分組的均衡度 ，說明分組的均衡度很好。我們根據(jù)最小生成樹分解原則進(jìn)行分區(qū)域，再次采用擴(kuò)環(huán)策略、增環(huán)策略、換枝策略的思想，給出了第一、二組搜索完需要的時(shí)間是 ，第三組搜索完需要的時(shí)間是 。即50人三組搜索完整個(gè)平面矩形區(qū)域需要 。最后，給出了一個(gè) 雙層非線性規(guī)劃，將其內(nèi)層目標(biāo)函數(shù)、約束條件構(gòu)造了 條件，從規(guī)劃的角度分析了此模型。 圖論中的賦權(quán)連通圖法，將圖論，規(guī)劃，算法有機(jī)地結(jié)合在一起。 關(guān)鍵詞 ：最小生成樹 ；均衡度；規(guī)劃；圓滾動模型 一、 問題重述 1.1背景 2008年5月12日汶川大地震中，震區(qū)地面交通和通訊系統(tǒng)嚴(yán)重癱瘓。大家知道救助災(zāi)民的黃金時(shí)間是72小時(shí)，能在短時(shí)間內(nèi)搜索到需要救助的人員得位置，并更快的進(jìn)行救助是我們的首要任務(wù)。救災(zāi)指揮部緊急派出多支小分隊(duì)，到各個(gè)指定區(qū)域執(zhí)行搜索任務(wù)，以確定需要救助的人員的準(zhǔn)確位置。在這種緊急情況下需要解決的重要問題之一是：制定搜索隊(duì)伍的行進(jìn)路線，對預(yù)定區(qū)域進(jìn)行快速的全面搜索。 1.2簡化的搜索問題 我們有一個(gè)平地矩形目標(biāo)區(qū)域，需要進(jìn)行全境搜索。出發(fā)點(diǎn) 在區(qū)域中心；搜索完成后需要進(jìn)行集結(jié)，集結(jié)點(diǎn) 在左側(cè)短邊中點(diǎn)。每個(gè)人帶有GPS定位儀、步話機(jī)。搜索隊(duì)伍若干人為一組,有一個(gè)組長，組長還擁有衛(wèi)星電話。每個(gè)人搜索到目標(biāo)，需要用步話機(jī)及時(shí)向組長報(bào)告，組長用衛(wèi)星電話向指揮部報(bào)告搜索的最新結(jié)果。 1.3我們需要解決的問題 （ ）若搜索隊(duì)伍 人，一組, 臺衛(wèi)星電話。設(shè)計(jì)耗時(shí)最短的搜索方式并求出搜索完整個(gè)區(qū)域的時(shí)間。 若在 小時(shí)內(nèi)不能完成搜索任務(wù)，需要增加到多少人才可以完成。 （2）若搜索隊(duì)伍 人，三組， 臺衛(wèi)星電話。每組可獨(dú)立將搜索情況報(bào)告給指揮部門。設(shè)計(jì)耗時(shí)最短的搜索方式并求出搜索完整個(gè)區(qū)域的時(shí)間。 二、模型假設(shè) 假設(shè) 搜索目標(biāo)區(qū)域?yàn)殚L 米，寬 米的平地矩形區(qū)域，需要進(jìn)行全境搜索。 假設(shè) 每個(gè)搜索隊(duì)員搜索時(shí)的可探測半徑為 米，搜索時(shí)平均行進(jìn)速度為 米/秒；不需搜索只行進(jìn)時(shí),平均速度為 米/秒。 假設(shè) 步話機(jī)通訊半徑為 米。 假設(shè) 在出發(fā)點(diǎn)部署時(shí)，等到所有隊(duì)員都到自己的位置后所有人在同一時(shí)間出發(fā)。 假設(shè) 搜索隊(duì)員一旦發(fā)現(xiàn)目標(biāo)，直接向組長報(bào)告，組長立即向指揮部報(bào)告，報(bào)告時(shí)間為 秒，且不影響搜索工作。 假設(shè) 搜索隊(duì)員一旦發(fā)現(xiàn)目標(biāo)，能夠直接定位彼此的相對坐標(biāo)，并根據(jù)自己的 定位儀得到的自身坐標(biāo)，定出目標(biāo)的坐標(biāo)，花費(fèi)時(shí)間為 秒。 三、符號說明與概念 3.1符號說明 ---------- 賦權(quán)連通圖； ----------------- 賦權(quán)連通圖 的第 個(gè)子圖； ------------------ 子圖 中的最佳回路； ---------------- 邊 的邊權(quán)； ------------------ 點(diǎn) 的邊權(quán)； ----------------- 最佳回路 的各邊權(quán)之和； ------------------ 的各點(diǎn)權(quán)之和； --------------------- 搜索每塊區(qū)域的時(shí)間 為敘述方便起見，我們在文中不加說明的使用上述變量或符號的變形形式，它們的含義可通過上下文確定。 3.2概念 均衡度： 為該分組的實(shí)際時(shí)間均衡度，顯然 ， 越小，說明分組的均衡度越好； 最大容許均衡度： ； 均衡分組：取定一個(gè) 后， 和 滿足條件 （其中 ）的分組時(shí)一個(gè)均衡分組。 四、模型分析 4.1 搜索隊(duì)員為 人時(shí)的思路 4.1.1圓滾動性模型 圓滾動模型是以組長為圓心， 為半徑的圓以一定速度向前滾動。 用類比的方法就可以得到 人一起以同一速度向前搜索，覆蓋整個(gè)矩形區(qū)域。我們還給出了一些數(shù)據(jù)，見附錄一。 我們在表中取每個(gè)人到各點(diǎn)的時(shí)間，繪成每個(gè)人的時(shí)間——地點(diǎn)圖。 為了描述方便我們?nèi)?號，2號，20號人員的圖在同一圖中以不同顏色顯示，命令為： Show[p1,p2,p20] 由離散圖聯(lián)線得到的圖證明隨著每人路程的增加，圖形大致有兩兩之間距離增加的趨向。而且增加只出現(xiàn)在拐彎處，所有人的時(shí)間差成扇形分布，且外側(cè)時(shí)間叫大，當(dāng)?shù)搅酥毙袝r(shí)，時(shí)差不變。 在過程中我們可發(fā)現(xiàn)1號和20號有時(shí)調(diào)換位置，當(dāng)完成一次調(diào)換時(shí)，時(shí)差變化為0。在1-2-3-4、4-5-6-7-8、12-13-14-15出現(xiàn)一次完整調(diào)換。 由于20號人員在運(yùn)動中大多數(shù)時(shí)間在外側(cè)拐彎，因而造成速度上有較大變化。 同理1號人員速度有較小變化。從地點(diǎn)7-8-9-10-11-12處20號人員一直跑外圈，而1號跑內(nèi)圈。我們在離散圖中得到20號發(fā)生巨變（離散圖特性造成）。 在16-17-18期間速度發(fā)生變化（個(gè)人距離安排不同），同樣引起巨變。且所有人的時(shí)差最小。18-19上直線前進(jìn)，時(shí)差不變。19-20上以1.2米每秒速度在短距離上快速集合，時(shí)差變化微弱。 運(yùn)用此方法可能會出現(xiàn)聯(lián)系不上組長的情況?？梢哉{(diào)節(jié)，但是需要很大的工作量，所以我們給出下面的思路。 4.1.2圖論模型 在第一問中搜索隊(duì)只有一組，搜索路線從出發(fā)點(diǎn) 出發(fā)，沿預(yù)定路線遍歷全境，最后到集合點(diǎn) 集合。把該問題抽象為賦權(quán)連通圖問題，即：將探測范圍的內(nèi)切正方形作為研究點(diǎn)，又將以研究點(diǎn)組成的通信范圍的內(nèi)切正方形為研究點(diǎn) 。經(jīng)過大體運(yùn)算可以得到沿矩形長分布 個(gè)，寬分布 個(gè)；得一無向連通圖 ， ,兩點(diǎn)之間的長度，即為無向圖的邊權(quán) ，尋找一條最佳路線，即在圖 中，找到一條由 點(diǎn)到 點(diǎn)的路，它至少經(jīng)過所有頂點(diǎn) 一次，使總時(shí)間（總路程）最小。 搜索隊(duì)員為 人時(shí)的思路 如果搜索人員分成三組，每組搜索部分區(qū)域，且所有區(qū)域都搜索到，如果把這些區(qū)域都搜索到，即圖 中把圖分成若干個(gè)連通的子圖 ，每個(gè)子圖 中尋找一條包含 的回路 。 完成搜索的時(shí)間應(yīng)是各組搜索時(shí)間中最長的時(shí)間。故為使搜索效率高，因盡量使各組搜索時(shí)間接近，反映在圖 中分塊使盡量均衡。 五、模型建立與求解 5.1 搜索隊(duì)伍為 人時(shí)的模型 5.1.1一個(gè)有利的結(jié)論 命題： 人一組的搜索隊(duì)伍,搜索完整個(gè)區(qū)域至少需要 個(gè)小時(shí)。 證明：在不考慮部署、聚集等非搜索行為的情況下， 人為一組部署在矩陣的左上角，沿左側(cè)短邊以間距 米的距離一字排開，離最靠近上邊的一人距上邊為 米，即搜索范圍長為 米。由左到右開始搜索，達(dá)到最右邊時(shí)所有人員向下方平移 米，以此類推。由矩形寬度得 可劃分為 塊地區(qū)。 如圖1： 圖1 不考慮非搜索行為的情況下，分成的9塊區(qū)域及搜索順序 由搜索速度和矩形長度得，每塊區(qū)域需要搜索時(shí)間： 秒 搜索完 塊區(qū)域需要的時(shí)間為 秒 秒 小時(shí)。 因?yàn)檫@個(gè)結(jié)論是在絕對理想狀態(tài)下得到的最下限，現(xiàn)實(shí)中是不可能出現(xiàn)的。故模型結(jié)果一定大于該極限值 小時(shí)。 5.1.2模型建立 把通過各區(qū)域的時(shí)間示意圖抽象為一賦權(quán)連通圖 ，在賦權(quán)圖 中， 對應(yīng)示意圖中搜索人員所在地， 表示出發(fā)點(diǎn)所在地， 對應(yīng)示意圖中的位置，如果相鄰，則邊權(quán) =0；如果不相鄰，則邊權(quán) 為間距之差。 建立的數(shù)學(xué)模型如下： ， ， ，求 中回路 ，使得滿足： （1） ， （2） ； （3） （目標(biāo)為搜索時(shí)間最短） 5.1.3模型求解 將平面矩形區(qū)域平均分割成數(shù)個(gè) 的小正方形，得到平面矩形區(qū)域長邊有 個(gè)小正方形，寬邊上有 個(gè)小正方形。然后將小正方形壓縮成一個(gè)位于小正方形中心的點(diǎn)。平面矩形圖中形成 個(gè)點(diǎn)。為了計(jì)算方便，我們將在出發(fā)點(diǎn)左側(cè)的 個(gè)點(diǎn)，先不與考慮。就形成了如圖2(a) 的點(diǎn)圖。 圖2(a) 圖G的點(diǎn)集 圖2(b) 圖G 將圖2(a)中的點(diǎn)作為圖的頂點(diǎn)，做一圖 ，其點(diǎn)與邊的關(guān)系如圖2(b)，因?yàn)樽钚∩蓸淠馨瑘DG中所有頂點(diǎn) ，考慮最小生成樹。根據(jù)最小生成樹求解 算法： Step1 將 的 條邊按排序， 。取 ， ， Step2 邊 的端點(diǎn) 的標(biāo)號是否相等？ 是：取 ，轉(zhuǎn)Step2； 否：取 Step3 對一切滿足 的 ，取 Step4 中的邊數(shù) ？ 是：算法終止； 否：取 ，轉(zhuǎn)Step2。 我們找到圖的最小生成樹T如下： 圖 最小生成樹T 現(xiàn)要對已得到的最小生成樹T，變換圖形以獲得便于解的方案。 (a)擴(kuò)環(huán)策略： 如果在圖 中的路徑 中，有孤立的枝存在，如圖4所示代表1，2，3三個(gè)頂點(diǎn)，若 ，則應(yīng)考慮擴(kuò)環(huán)。 擴(kuò)環(huán)策略還可擴(kuò)展到多個(gè)頂點(diǎn)的情況，如圖4所示：擴(kuò)環(huán)后比擴(kuò)環(huán)前其權(quán)和變化為 。若 ，則應(yīng)擴(kuò)環(huán)。當(dāng) 時(shí)，擴(kuò)環(huán)后總時(shí)間更少，可進(jìn)行擴(kuò)環(huán)調(diào)整。 (a) 3點(diǎn)擴(kuò)環(huán)圖 (b) 多點(diǎn)擴(kuò)環(huán)圖 圖4 擴(kuò)環(huán)圖 (b)增環(huán)策略： 若環(huán)路上某頂點(diǎn)處長出兩條枝，且存在可使兩枝成環(huán)的邊，可考慮增環(huán)。增環(huán)前后其權(quán)和變化為 。若 ，則應(yīng)增環(huán)。當(dāng) 時(shí)，增環(huán)后總時(shí)間更少，可進(jìn)行增環(huán)調(diào)整。 我們對圖5進(jìn)行分析，發(fā)現(xiàn)擴(kuò)環(huán)策略條件完全滿足，故則兩種策略完全適用。 圖5 增環(huán)圖 (c)換枝策略： 若環(huán)路上某頂點(diǎn)長出一條枝，而該枝末梢同環(huán)路中另一頂點(diǎn)距離接近，可考慮換枝。如圖6所示，若 則應(yīng)考慮換枝。換枝的結(jié)果是使被重復(fù)的路減少。 圖6 換枝圖 根據(jù)以上的優(yōu)化策略及分塊結(jié)果，在 ， 中分別尋找一條從出發(fā)點(diǎn)出發(fā)，遍歷整個(gè)區(qū)域的最短時(shí)間。 在圖 中，求三條從出發(fā)點(diǎn)回到出發(fā)點(diǎn)的路 ，滿足 為 中經(jīng)過點(diǎn)的集合，使得 最小，且 與 相差不大。 結(jié)合圓滾動模型調(diào)整可得最優(yōu)圖為圖7。 圖7 搜索路線 搜索分析：當(dāng)以 人為一組搜索時(shí)， 人在中間以間隔為 米縱向分開，即 人的搜索范圍為 米，且 人在到達(dá)各自的位置上后， 人在同一時(shí)刻向前搜索，在拐彎處 人同時(shí)搜索到邊上，然后再平移 米到下一個(gè)要搜索的正方形上。 搜索時(shí)搜索方法可分為兩種：一種為不拐彎時(shí)的搜索方法；另一種為拐彎時(shí)的搜索方法。 (一)不拐彎時(shí)的搜索方法為：不拐彎時(shí)把正方形分為三部分，左右各 米，中間為 米，搜索時(shí)左邊 米以 米/秒的速度行進(jìn)，中間 米以 米/秒的速度行進(jìn)，右邊的 米以 米/秒的速度行進(jìn)。搜索圖為圖8(a)。 (二) 拐彎時(shí)的搜索方法為：在第一個(gè)正方形按不拐彎的搜索方法搜到矩形的邊界然后把 人按次序不變的方法平移到下一個(gè)正方形的邊界上，然后再按不拐彎的方法進(jìn)行搜索。搜索圖為圖8(b)。由返回點(diǎn)到出發(fā)點(diǎn)的圖為圖9。 (a) (b) 圖8 搜索圖 圖9 返回圖 5.1.4模型結(jié)果 結(jié)論一：搜索完整個(gè)平面矩形區(qū)域所用的時(shí)間為 小時(shí)。 搜索時(shí)間的計(jì)算分成如下幾步： (1)在出發(fā)點(diǎn)的部署時(shí)間：把 人按縱向以間距為 米的平均距離分開，時(shí)間 秒； (2)在不拐彎時(shí)搜索完一個(gè)正方形所用的時(shí)間： 秒； (3)在拐彎時(shí)搜索完一個(gè)彎所用的時(shí)間： 秒； (4)搜索完除出發(fā)點(diǎn)左側(cè) 個(gè)點(diǎn)外的點(diǎn)后回到出發(fā)點(diǎn)的時(shí)間： 秒； (5)在回到集結(jié)點(diǎn)的那條邊上時(shí)再回到集結(jié)點(diǎn)所用的時(shí)間： 秒； (6)由圖 可得，除去出發(fā)點(diǎn)左側(cè)的 個(gè)點(diǎn)后，圖上有 個(gè)拐彎處，有 個(gè)不拐彎的正方形。所以除去出發(fā)點(diǎn)左側(cè)的 個(gè)點(diǎn)后由出發(fā)點(diǎn)再回到出發(fā)點(diǎn)所用的時(shí)間為 ； (7) 搜索完成出發(fā)點(diǎn)左側(cè)的 個(gè)點(diǎn)再回到集結(jié)點(diǎn)所需的時(shí)間為 ； (8)所以搜索完整個(gè)矩形區(qū)域所用的時(shí)間為 小時(shí)。 結(jié)論二：在 小時(shí)以內(nèi)不能完成搜索任務(wù)。 由于在假設(shè) 中假設(shè)所有隊(duì)員在同一時(shí)間出發(fā)，在這其中離出發(fā)點(diǎn)近的隊(duì)員到達(dá)自己的位置后，離出發(fā)點(diǎn)遠(yuǎn)的隊(duì)員還沒到達(dá)自己的位置，所以離出發(fā)點(diǎn)近的隊(duì)員就有一段時(shí)間在等離出發(fā)點(diǎn)遠(yuǎn)的隊(duì)員，所以如果沒有假設(shè) 的話，我們上邊做的時(shí)間 小時(shí)還可以縮小，但是在出發(fā)點(diǎn)出最近的隊(duì)員與最遠(yuǎn)的隊(duì)員出發(fā)的時(shí)間間隔不到 秒，所以上邊算法得出的時(shí)間無論怎么縮小也不會小于 小時(shí)。 而且我們的算法算出的時(shí)間是最小的時(shí)間，所以在 小時(shí)以內(nèi)不能完成搜索任務(wù)。 結(jié)論三：增加到 人，在47.41小時(shí)內(nèi)可以完成搜索任務(wù)。 20人搜索完整個(gè)矩形區(qū)域需要48.47小時(shí)，若要在48個(gè)小時(shí)內(nèi)完成工作，則至少需要增加1人即21 人，命名增加的人為圈內(nèi)自由人，他先在1軌道以 米/秒的速度前進(jìn)，搜索人員以 米/秒的速度搜索，自由人行進(jìn)到 的路程時(shí)開始搜索，恰好與1軌道的搜索人員在該區(qū)域邊界處相遇，然后自由人轉(zhuǎn)向2軌道，以 米/秒的速度前進(jìn)，以后的運(yùn)動路線與前一個(gè)軌道相同，按照上述方法自由人依次補(bǔ)完20個(gè)人的路線，然后再從20軌道依次補(bǔ)向前一個(gè)軌道，總共補(bǔ)6次，而且中間不會出現(xiàn)與隊(duì)長失去聯(lián)系的情況，每次補(bǔ)380米，省時(shí) 秒，即1.06小時(shí)，所以21人可以用47.41小時(shí)搜索完整個(gè)區(qū)域。 5.2 搜索隊(duì)伍為 人時(shí)的模型 5.2.1 模型建立 50人搜索7200米寬的矩形區(qū)域，每人可以搜索寬度為40米，則平均每人搜索的趟數(shù)為 ，因?yàn)樽詈笠幻阉麝?duì)員完成任務(wù)的時(shí)間決定最終搜索時(shí)間，所以每人搜索的趟數(shù)越接近3.6越省時(shí)，若按18，18，14或16，16，18的方案分組，則會導(dǎo)致誤工現(xiàn)象，若按既橫向搜索也縱向搜索，則一定至少會有一組距離集合點(diǎn)遠(yuǎn)，這樣有效工作效率就會降低，導(dǎo)致耗時(shí)增加，綜上分析可得按第一組20人，第二組20人，第三組10人的方法分組橫向搜索會比較合理。 按以 人為一組搜索時(shí)的數(shù)據(jù)整個(gè)大矩形可分為 個(gè)小正方形，即為 個(gè)點(diǎn)，由上述分析， 人以 的分法分為三組，這 個(gè)點(diǎn)可以按 的比例分給這三個(gè)組，每組可分 ， ， ，分區(qū)域時(shí)把 人組分在離出發(fā)點(diǎn)近的那一個(gè)區(qū)域，由于 人組與 人組搜索相同距離時(shí) 人組所用的時(shí)間要長，所以這 個(gè)點(diǎn)就分為 ，按生成樹分解原則分區(qū)域， (1)分解點(diǎn)為出發(fā)點(diǎn)或盡可能接近出發(fā)點(diǎn)。 (2)分解所得的三個(gè)子圖所包含的頂點(diǎn)數(shù)盡可能接近 ， 盡量使分解所得子圖為連通圖，盡量使子圖與出發(fā)點(diǎn)最短路上的點(diǎn)在該子圖內(nèi)，盡量使各子圖的點(diǎn)在子圖內(nèi)部形成環(huán)路。 再經(jīng)過上面所用的擴(kuò)環(huán)策略，增環(huán)策略和換枝策略等有效優(yōu)化原則再結(jié)合圓滾動模型得到的分圖如下所示： 圖10 三組的搜索方式 5.2.2 模型求解 第一，二組搜索所用時(shí)間 由圖 可知 人組是上下對稱的，所以 人組的時(shí)間算一個(gè)就可以了，則由圖可得拐彎處有 個(gè)，其余的 未拐彎，所以在圖中搜索所用時(shí)間為： 搜索完回到途中路線后回到集結(jié)點(diǎn)所用的時(shí)間為： ； 在出發(fā)點(diǎn)部署所用時(shí)間為： ； 所以 人組從出發(fā)點(diǎn)到集結(jié)點(diǎn)所用的總時(shí)間為： 。 第三組搜索所用時(shí)間 人組搜索時(shí)的模型和 人組的模型一樣，把 人組的區(qū)域分為 個(gè) 的小正方形?？梢杂玫谝粏柕姆椒ㄕ业揭粋€(gè)用時(shí)最短的樹。 搜索完一個(gè)不拐彎的小正方形所用的時(shí)間為： 搜索完一個(gè)拐彎的小正方形所用的時(shí)間為： 中間以 米每秒的速度行進(jìn)的時(shí)間為： 所以 人組所用總時(shí)間為： 人搜索完所用時(shí)間 小時(shí)。 5.2.3 均衡度分析 均衡度 ，給定最大容許均衡度 ；顯然 。 比 小很多，說明分組的均衡度很好；這樣的分組是一個(gè)均衡分組。 5.2.4用規(guī)劃模型分析 設(shè)非線性規(guī)劃 和線性規(guī)劃 的可行解集合分別為 ， 。 利用規(guī)劃 的內(nèi)層目標(biāo)函數(shù)和約束條件，設(shè)拉格朗日函數(shù) ，構(gòu)造 條件，得到非線性規(guī)劃 其可行解集合為 。 根據(jù)最優(yōu)化理論 ，可以得到如下命題： (a) ； (b) 規(guī)劃 的最優(yōu)值不超過規(guī)劃 的最優(yōu)值； (c) 規(guī)劃 的Pareto最優(yōu)值不超過規(guī)劃 的最優(yōu)值。 以上結(jié)論來自文獻(xiàn)[1][5][7]，我們構(gòu)造此搜索問題的規(guī)劃模型，將搜索區(qū)域分成上下對稱的兩部分，先考慮上部分的搜索情況，下部分的與上部分的相同。上部分的搜索情況規(guī)劃為 其中 ， 變量 是指編號為 的人，占了多少條道，且這些道均相連。這是 非線性規(guī)劃，約束條件是線性的，可行解集合為凸集。 將規(guī)劃 變形得到 這是非線性規(guī)劃，其中約束條件中含有線性約束，以及由二次函數(shù)開平方根形成的非線性約束。由命題 可知，規(guī)劃 的可行解集合是規(guī)劃 的可行解集合的子集合，且前者的Pareto最優(yōu)值不超過后者的最優(yōu)值。 利用規(guī)劃 中內(nèi)層目標(biāo)函數(shù)和約束條件，得到 條件 計(jì)算 ，構(gòu)造規(guī)劃 規(guī)劃 的可行解集合是非線性規(guī)劃 可行解集合的子集合，規(guī)劃 的Pareto最優(yōu)值不超過規(guī)劃 的最優(yōu)值。 六 、模型的評價(jià)與擴(kuò)展 6.1 模型評價(jià) 本問題從實(shí)際出發(fā)，分析了多種情況，將矩形分成若干小區(qū)域，結(jié)合圓滾動思想，將搜索示意圖轉(zhuǎn)化為賦權(quán)連通圖，建立了最小生成樹的模型，并進(jìn)行了理論論證和實(shí)例論證。還利用均衡度判定出合理的人數(shù)組合，進(jìn)而達(dá)到了優(yōu)化設(shè)計(jì)的目的。除此之外又用到規(guī)劃模型，有成熟的理論基礎(chǔ)和相應(yīng)的專業(yè)軟件支持，可信度高。而且在整個(gè)搜索過程中，每位搜索人員都能夠直接與隊(duì)長聯(lián)系，及時(shí)將情況報(bào)告給隊(duì)長，并且20個(gè)人中隊(duì)長位置無限制，從而保證了信息傳遞的快速性和高效性。 6.2 模型擴(kuò)展 上述解法是解決簡化的搜索問題，如果考慮到實(shí)際問題就不適合了。如果把上面的采用圓滾動的方法改進(jìn)為每個(gè)人從一個(gè)圓的圓心以 米/秒前進(jìn)到另一個(gè)圓的圓心，然后就在圓內(nèi)判斷并停留若干秒，其速度為 米/秒。 此方法的好處為： （一） 這樣就可以很好的利用兩個(gè)速度 米/秒和 米/秒。 （二） 可以和實(shí)際的問題聯(lián)系起來。在實(shí)際問題中，任務(wù)管理員可以根據(jù)建筑物和場地來判斷需要救助的人的數(shù)量，不同場所幸存人數(shù)不同，我們可以將美國和新西蘭的研究成果綜合后得表 ，表 。 建筑類型 幸存者數(shù)量/平方米 安全幅度/平方米 公共集會場所 人 或 學(xué)校 人 或 醫(yī)院 人 或 商業(yè) 人 或 辦公室/政府機(jī)關(guān) 人 或 公共安全 人 或 住宅區(qū) 人 或 工業(yè) 人 或 倉儲 人 或37.1~83.6 表 各建筑類型中的幸存者數(shù)量和安全幅度 建筑物用途 人的數(shù)量 學(xué)校 人/教室 醫(yī)院 人/床位 住宅 人/居室 其他 人/停車位 表 建筑物用途及里面人的數(shù)量 （三）可以把三維空間簡化為二維空間來求解，這里可以把建筑物壓為平地，把人壓人也看為平地。 （四）可以縮短搜索時(shí)間。 參考文獻(xiàn)： [1] Thomas Svobodny 《數(shù)學(xué)模型》.2005年1月第一版第一次印刷。 [2]劉滿鳳，傅波，聶高輝：《運(yùn)籌學(xué)模型與方法教程例題分析與題解》.清華大學(xué)出版社， 。 [3]赫孝良，戴永紅，周義倉：《數(shù)學(xué)建模競賽賽題簡析與論文點(diǎn)評》 西安.西安交通大學(xué)出版社， 。 [4]姜啟源：《數(shù)學(xué)建?！?北京高等教育出版社， 。 [5].陳華富，《非線性極大極小問題的可行信賴域算法》電子科技大學(xué)學(xué)報(bào) Volzo No.4 Aug.2004。 [6]魏國華,傅家良,周仲良：《應(yīng)用運(yùn)籌學(xué)》.復(fù)旦大學(xué).復(fù)旦大學(xué)出版社. 。 [7]李輝，楊益民《一類非線性雙層規(guī)劃問題的最優(yōu)性條件》。 [8]顧建華，陳維鋒，郝清源，地震災(zāi)害現(xiàn)場救援搜索策略與搜索方法有關(guān)問題的討論，國際地震動態(tài)，No.61 Serial No.294。 [9]羅盧楊，龍繼東，唐小軍，災(zāi)情巡視路線尋優(yōu)模型，數(shù)學(xué)的實(shí)踐與認(rèn)識，Vol.28 No.1。