1、高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承 諾 書我們仔細閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從a/b/c/d中選擇一項填寫）： 我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話）

2、： 所屬學(xué)校（請?zhí)顚懲暾娜?參賽隊員 (打印并簽名) ：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負責(zé)人 (打印并簽名)： 日期： 年 月 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：地面搜索摘要本文針對震后搜救問題，運用最優(yōu)化數(shù)學(xué)模型，找到了較理想的搜索路線。模型一運用最優(yōu)化線形法找到了線形搜尋方式；模型二利用多元函數(shù)區(qū)域方程，計算出搜尋時間為51.834小時

3、，之后運用哈密頓回路，找到了多種閉合回路。計算出最理想的路線，即所用時間最短的路徑，得出其時間為47 .90小時，所用時間能在48小時內(nèi)完成，第一個問題解決。對哈密頓理論推廣，找到了派出50 人的最佳路線（圖2-）所用時間為22.59小時。關(guān)鍵詞最優(yōu)化、哈密頓問題、線性規(guī)劃、多元函數(shù)、搜索、模型、 c語言程序1、 問題重述5.12汶川大地震使震區(qū)地面交通和通訊系統(tǒng)嚴重癱瘓。救災(zāi)指揮部緊急派出多支小分隊，到各個指定區(qū)域執(zhí)行搜索任務(wù)，以確定需要救助的人員的準確位置。在其它場合也常有類似的搜索任務(wù)。在這種緊急情況下需要解決的重要問題之一是：制定搜索隊伍的行進路線，對預(yù)定區(qū)域進行快速的全面搜索。通常，

4、每個搜索人員都帶有g(shù)ps定位儀、步話機以及食物和生活用品等裝備。隊伍中還有一定數(shù)量的衛(wèi)星電話。gps可以讓搜索人員知道自己的方位。步話機可以相互進行通訊。衛(wèi)星電話用來向指揮部報告搜索情況。下面是一個簡化的搜索問題。有一個平地矩形目標區(qū)域，大小為11200米7200米，需要進行全境搜索。假設(shè)：出發(fā)點在區(qū)域中心；搜索完成后需要進行集結(jié)，集結(jié)點（結(jié)束點）在左側(cè)短邊中點；每個人搜索時的可探測半徑為20米，搜索時平均行進速度為0.6米/秒；不需搜索而只是行進時,平均速度為1.2米/秒。每個人帶有g(shù)ps定位儀、步話機，步話機通訊半徑為1000米。搜索隊伍若干人為一組,有一個組長，組長還擁有衛(wèi)星電話。每個人

5、搜索到目標，需要用步話機及時向組長報告，組長用衛(wèi)星電話向指揮部報告搜索的最新結(jié)果。現(xiàn)在有如下問題需要解決：1假定有一支20人一組的搜索隊伍, 擁有1臺衛(wèi)星電話。請設(shè)計一種你認為耗時最短的搜索方式。按照你的方式，搜索完整個區(qū)域的時間是多少? 能否在48小時內(nèi)完成搜索任務(wù)? 如果不能完成，需要增加到多少人才可以完成。2為了加快速度，搜索隊伍有50人，擁有3臺衛(wèi)星電話，分成3組進行搜索。每組可獨立將搜索情況報告給指揮部門。請設(shè)計一種你認為耗時最短的搜索方式。按照你的搜索方式, 搜索完整個區(qū)域的時間是多少?二、符號說明 時間 搜索路線 時間 集結(jié)點 時間 出發(fā)點三、問題分析第一問題分析：令人寒心的傷亡

6、統(tǒng)計：四川省民政廳昨日發(fā)布消息，截至（5.31）日下午2時統(tǒng)計，全省1030.29萬人不同程度受災(zāi)，因災(zāi)死亡1人、傷病6.31萬人，直接經(jīng)濟損失21.31億元，其中農(nóng)業(yè)直接經(jīng)濟損失14.98億元。截至31日14時，全省已緊急下?lián)軕?yīng)急資金4070萬元。熱血的救援安排：讓我們共同祈禱受災(zāi)人數(shù)不要再增加，我們已派出一小分隊救援，就讓人員傷亡不要再增加，下面是我們應(yīng)就得具體安排。我們的設(shè)備如表（一）：人 員物 資12345678910組長11副組長121314151617181920步話機1111111111衛(wèi)星電話1111111111gps定位儀11111111111111111111食物若干若干若

7、干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干其他工具若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干5.12汶川大地震是讓全世界都震驚的一個消息，而在這時我們的同胞還在廢墟中等待著營救，這場大地震使震區(qū)地面交通和通訊系統(tǒng)嚴重癱瘓。我們必須前去營救，而在這時我們所面對的是大小為11200米7200米的廢墟，我們只有二十人，我們只有兩天的時間，只能比我們所擁有的時間短，要不會有更多的人員傷亡，所以當(dāng)我們完成不了時，我們可以求助，所以我們要想一個最優(yōu)的辦法來完成這次搜索，我們用的的是gps定位儀、步話機以及食物和生活用品等裝備下面是我們想的幾

8、種辦法來證明：首先我要收悉我們的地形圖，如圖（一）第一問題：二十人能否在48小時完成搜索。答：通過以下計算得出，可以在規(guī)定時間完成。模型一：最優(yōu)化線性法我們的出發(fā)點在圖中間也就是坐標點為（5600，3600），我們的二十個人用直升機直接送到坐標點，以進行下一步搜查行動，由于我們二十個人為一隊，而且我們有1臺衛(wèi)星電話，所以我們必須同步而行，以為我們聯(lián)系半徑為1000米，所以我們之間距離不得超過2000米，而不至于丟失隊友，造成更大的人員丟失，只有這樣我們才可以更好的搜索救援，下面是人員安排：我們把二十人按一定順序編號1到20號，每個人的搜索范圍為20米的半球從地面到地下，以保證被埋群眾也得救，每

9、個人行程如下面三維立體圖：如圖（二）我們通過知道隊員探測范圍半徑20米，搜索速度為0.6米/秒，不需搜索而只是行進時,平均速度為1.2米/秒，在通過地震是由于地裂，所以底下也有人，通過matlab設(shè)計出照底下的三維立體視圖。1.我們每個人的搜索范圍如圖所示，圖2表示我們每個隊員所能搜查的范圍，我們停留在abcd地面上，中心e是我們隊員，我們在圖一的中心為20人，當(dāng)我們落地時，二十個人散開為一個長為800米矩形：如圖（三）2.我們隊員就三成如圖所示的形狀，其長為800米，每個人站在圓中點，每個人相差40米，散開規(guī)則是最短的時間最快的展開隊形，其中十九個人不搜索前進，依次按距地形圖20，60，10

10、0760終止散開，最后一個人以0.6米/秒搜查速度前進，每個人到達自己的散開位置時，就已搜查速度前進向前推步前行，第二十號人人以搜查速度前進的原因是：圖三中陰影部分都是不搜查部分，我們不能丟下任何一部分已造成人員傷亡，所以我們要求第二十號人以搜索速度前進，我們可以減小未搜查部分，就如趨近于相切，如圖（四）我們可以把未搜查范圍花最小：3.我們的忠旨就是在最短的時間救最多的人，所以我們采用上述的疏散方法，散開時我們每個隊員都配發(fā)指令，一號到十九號行走一定路程就開始進行搜查行動，而二十號隊員始終以搜查速度前進，而這樣就導(dǎo)致20號隊員落后，通過下列分析運算可知：分析：由題意給內(nèi)容得知搜索時平均行進速度

11、為0.6米/秒；不需搜索而只是行進時,平均速度為1.2米/秒，所以跟就搜查散開方法得知分析如下：已知：一號到十九號都已1.2米/秒散開，而20號以0.6米/秒而不致使隊員走過的地方未進行營救搜查。但又因為每個人散開后并不停止，而是進行疏散后的隊形向前推步搜查，所以二十號隊員就落后，但我們的器械只能在2000米的范圍內(nèi)不丟失隊友，所以我們要讓隊友始終保持在2000米范圍內(nèi)，這樣我們就要找個地方讓他們的距離不要拉太長，所以我們考慮當(dāng)20人在轉(zhuǎn)折點時做個先后順序，有一位我們?nèi)I救每分每秒都有生命在呼喚，這是我們不能做無謂的等待，所以每個人在自己的路線上都不要停留去等待隊友，所以我們一直保持著前進的營

12、救路程，有一位我們的出發(fā)點是中心所以我們選擇沿線兩頭散開，疏散到預(yù)計的800米范圍，讓二十號不落后的時間段就是在每一次拐彎時，這樣我們就把距離變化為遠近近遠的行程。模型二：多元函數(shù)區(qū)域優(yōu)化地面搜索是一個復(fù)雜的行程路線，為了節(jié)省時間我們采用離散的優(yōu)化方法，即區(qū)域優(yōu)化和多元函數(shù)。計算過程如下：最優(yōu)化設(shè)計問題可以把20人分成幾個小分隊 每個小分隊負責(zé)某一個區(qū)域 最短時間即為所有小分隊同時完成任務(wù)所需時間 執(zhí)行任務(wù)離中心點近的分隊，區(qū)域可以安排大點 離中心點遠的分隊，區(qū)域小一點（因為還有步行時間） 具體幾人一分隊，區(qū)域面積多大，如下： 1 線性規(guī)劃問題的模型線性規(guī)劃問題的標準形式是：minc1x1+c

13、2x2+cnxn (1)s.t. 11 1 12 2 1n n 1 a x+a x+a x=b21 1 22 2 2n n 2ax +a x +a x=b (2)m1 1 m2 2 mn n ma x +a x +a x=b1 2 n x,x ,x 0其中(1)為目標函數(shù)，(2)為約束條件， 0( 1t1,t 2,t3 ) j x j= n為非負約束。線性規(guī)劃也常用矩陣 向量的形式表示。若記1 ( t1,t 2,t3 )tn c= c c ， 1 (t1,t 2,t3 )tn x = x x ， 1 ( t1,t 2,t3 )tm b= b b ，a 為mn矩陣，把非負約束0( 1, , )

14、j x j= n簡記為x 0 ，則線性規(guī)劃可表示為：minctxs.t. ax=bx 0 計算得到時間為176878秒約為49.133小時2 函數(shù)解析問題f（q r）=qn/rn n=(.5.6.)得到186630秒約為51.834小時，超時得到177893秒約為49.41473小時如圖（六）途中分不同的四個大區(qū)，兩個圓中心的是起始點，短邊上的是集結(jié)點，我們隊員以每一小區(qū)進行搜查，以其中的n個小區(qū)搜查，通過計算，隊員不但分離而且很有可能造成丟失，從而使這次搜查行動失敗，而且理論時間超長，預(yù)算不夠用。通過分析得到，模型一為合理方法，而二把組分開并且時間過長，還有區(qū)域分析法中的函數(shù)和

15、線性規(guī)劃并沒有解釋出最短時間，而是按每個人走的路程之和取得平均值，最后得到模型一運用哈密頓定理，和哈密頓圖分析得到，例：下列展示哈密頓定理我們拿出一個做例來解釋哈密頓并且對模型一分析。哈密頓圖主要定義：如果圖g中存在一條通過圖g中各個頂點一次且僅一次的回路，則稱此回路為圖的哈密頓回路；具有哈密頓回路的圖稱為哈密頓圖。如果圖g中存在一條通過圖g中各個頂點一次且僅一次的回路，則稱此回路為圖的哈密頓回路；具有哈密頓回路的圖稱為哈密頓圖。主要定理：設(shè)圖g是哈密頓圖，如果從g中刪去個p頂點得到圖g，則圖g的連通分支數(shù)小于等于p。設(shè)圖g是具有n(n=3)個頂點的無向簡單圖，如果g中任意兩個不同頂點的度數(shù)之

16、和大于等于n-1，則具有哈密頓通路，即g是半哈密頓圖。設(shè)圖g是具有n n(n=3)個頂點的無向簡單圖，如果g中任意兩個不同頂點的度數(shù)之和大于等于n，則g具有哈密頓回路，即g是哈密頓圖。例： 指出圖（七）是否哈密頓圖，有無哈密頓通路，回路？ 解 ：(1) 有哈密頓回路，故是哈密頓圖。(2) 只有哈密頓通路，無哈密頓回路，故不是哈密頓圖。(3) 既無哈密頓通路，又無哈密頓回路，當(dāng)然不是哈密頓圖。 下面我們對模型以進行統(tǒng)計，即圖示搜查路線，我們的出發(fā)點是矩形中心而集結(jié)點是短邊的中心，目的是搜查所有地形，所以我們可以搜索到每個角落，所以我們的路線滿足哈密頓圖，如果圖g中存在一條通過圖g中各個頂點一次且

17、僅一次的回路，則稱此回路為圖的哈密頓回路。下面我們畫出不同哈密頓圖來展示我們搜索路線，下面是初始動作和第一次轉(zhuǎn)彎時的動作： 如圖（五）寫出了搜查得出不開始，我們通過搜查開始和第一次轉(zhuǎn)彎，進行計算，我們得出了搜索路線，我們先把20人行走的路線看為一條直線，但是我們所進行的不是地毯式搜索，原因在于地毯式搜索要求同時出發(fā)，而如果同時出發(fā)就會浪費更多的時間，如：由計算得知隊員按一定的程序前進，而不是地毯式勘察，上圖中各線的意義： 點劃線 一號的開始路線和到達第一個轉(zhuǎn)折點的路線，還有行程。虛線 二十號開始路線和到達第一個轉(zhuǎn)折點的路線，還有行程。實線 組長的行程，由于隊員都按一定程序前進，所以最后定為主線

18、，也是中分線。雙點劃線 是隊員到達轉(zhuǎn)折點所形成的函數(shù)圖像，以為我們是一次行走的所以出現(xiàn)三角形圖。因為我們的隊員是按一定程序前進的，而我們所采取的是從中心散開，沿鄰近的邊散開，所以中心前進的人在開始就沒有不搜索時間，直接前行，也就是我們的組長十號依次副組長十一號沿邊不搜索前進40米到達搜索位置，而后不停留繼續(xù)前進，兩邊自動分開到自己的搜索點后以搜索速度向圖八中表示的路線推步前進，從而達到運算效果，然后我們分別計算出t.t.q的值，讓后取其中最大的，就為搜索的最短時間，然后通過優(yōu)化路徑求解，詳細分析運算在圖八下得出：下面是對圖五的詳細分析： t 一號在全過程中的時間 t 二十號在全過程中的時間 q

19、 組長在全過程中的時間 t1 所走搜索直線路程的時間 t2 轉(zhuǎn)折點轉(zhuǎn)折時所用的時間t3 不搜索對各段時間 t1 所走搜索直線路程的時間 t2 轉(zhuǎn)折點轉(zhuǎn)折時所用的時間t3 不搜索對各段時間 q1 所走搜索直線路程的時間 q2 轉(zhuǎn)折點轉(zhuǎn)折時所用的時間q3 不搜索對各段時間從這里可以看出我們行走的路線從開始就以把時間節(jié)省，我們采用程序散開，到達后不等人的路線前行，所以時間就在這被節(jié)省，下一步我們通過行走路線來采取最優(yōu)化方法，下面是我們制定的兩幅圖，具體是兩種不同的行走路線：下面是整個運算過程： 分析：行走路線，從開始到最后不停留（在沒有就營的情況下），考慮完整轉(zhuǎn)彎，在轉(zhuǎn)折點不浪費時間，采用中間散開方

20、法，保證營救速度和節(jié)省時間。函數(shù)式和圖（八）如下：如圖（八）同理函數(shù)求：對隊員行程進行c語言編程：c /* note:your choice is c ide */#define n 15#include stdio.hoid main() int i,j,k,b,a,t,f,an; int c=n-1; k=0; printf(please input %d numbers:n,n); for(i=0;in;i+) scanf(%d,&a); printf(n); for(i=1;ik;j-) if(ajaj-1) t=aj;aj=aj-1;aj-1=t; f=1;b=j; k=b;j=c;

21、 if(!f) break; else f=0; for(a=k;aaa+1) t=aa;aa=aa+1;aa+1=t; f=1;c=a; if(!f) break; printf(the sorted number:n); for(i=0;igetdc(); int v; for(v=0;vm_pointnum;v+) visiv=false; for(v=0;vgetdc(); visiv=true; pathk=v; /記錄當(dāng)前路徑 int w,i,j,c,d,e; arcnode *p; for(p=g.verticesv.firstarc;p;p=p-nextarc) w=p-adj

22、vex; if(!visiw) dfs(g,w,k+1); else /發(fā)現(xiàn)了一條回路 for(i=0;pathi!=w;i+); /找到回路的起點 for(j=0;pathi+j;j+) thiscyclej=pathi+j;/把回路復(fù)制下來 if(!exist_cycle() for(c=0;c=j;c+) cyclescycountc=thiscyclec;/如果該回路尚未被記錄過,就添加到記錄中 cycount+; if(j=m_pointnum-1) for(e=0;etextout(150+e*10,500+cycount*20,g.verticescyclescycounte.d

23、ata); for(d=0;dm_pointnum;d+) thiscycled=0; /清空目前回路數(shù)組 /else /for pathk=0; visik=false;/注意只有當(dāng)前路徑上的結(jié)點visited為真.因此一旦遍歷中發(fā)現(xiàn)當(dāng)前結(jié)點visited為真,即表示發(fā)現(xiàn)了一條回路 int circle:exist_cycle() int i,j,k,m,n,c,ab; int tempmax_vertex_num; for(i=0;icycount;i+) /判斷已有的回路與thiscycle是否相同 /也就是,所有結(jié)點和它們的順序都相同 j=0;c=thiscycle 0 ; /例如,1

24、42857和857142是相同的回路 for(k=0;cyclesik!=c&cyclesik!=0;k+);/在cycles的一個行向量中尋找等于thiscycle第一個結(jié)點的元素 if(cyclesik) /有與之相同的一個元素 for(m=0;cyclesik+m;m+) tempm=cyclesik+m; for(n=0;nk;n+,m+) tempm=cyclesin; /調(diào)整cycles中的當(dāng)前記錄的循環(huán)相位并放入temp數(shù)組中 for(ab=0;ab=m;ab+) if(tempab=thiscycleab) /if(!temp.compare(thiscycle) /與this

25、cycle比較 return true; /完全相等 for(m=0;mm_pointnum;m+) tempm=0; /清空這個數(shù)組 /for return false; /所有現(xiàn)存回路都不與thiscycle完全相等 我輸入四個點1,2,3,4,邊是1-2,2-3,3-4,4-1 可是出來的結(jié)果是: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 從事中我們可以看出我們還用到了哈密頓圖及原理，和上道題一樣我們分析的問題都是路徑行走，這次同樣還是走完每邊角，試圖借得到回應(yīng)，多以這正是哈密頓原理圖解。通過哈密頓函數(shù)，哈密頓算子，哈密頓量，把原題解釋的很清楚，加上c語言編程，最后得到最短時間的路徑編程。主要定義：如果圖中存在一條通過圖中個邊一次且僅一次的回路，則稱此回路為歐拉回路，具有歐拉回路的圖稱為歐拉圖。如果圖中存在一條通過圖中各邊一次且僅一次的通路，則稱此回路為歐拉通路，具有歐拉通路的