數(shù)學(xué)建模d題.doc

2012高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽承 諾 書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們授權(quán)全國大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì)，可將我們的論文以任何形式進(jìn)行公開展示（包括進(jìn)行網(wǎng)上公示，在書籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等）。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫）：D我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）：所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜? 參賽隊(duì)員(打印并簽名) ：1. 2 3 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期：2012年9月9日 賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2012高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽題目編 號(hào) 專 用 頁賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄：評(píng)卷人評(píng)分備注 全國統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國前編號(hào)）：機(jī)器人避障問題摘要二十一世紀(jì)科技發(fā)展迅速，機(jī)器人作業(yè)逐漸興盛。本文研究了機(jī)器人避障最短路徑和最短時(shí)間的問題。主要研究了在一個(gè)區(qū)域中存在12個(gè)障礙物，由出發(fā)點(diǎn)到達(dá)目標(biāo)點(diǎn)以及由出發(fā)點(diǎn)經(jīng)過途中的若干目標(biāo)點(diǎn)到達(dá)最終目標(biāo)點(diǎn)的兩種情形。我們通過證明具有圓形限定區(qū)域的最短路徑是由兩部分組成的：一部分是平面上的自然最短路徑（即直線段），另一部分是限定區(qū)域的部分邊界，這兩部分是相切的，互相連接的。依據(jù)這個(gè)結(jié)果，我們可以認(rèn)為最短路徑一定是由線和圓弧做組成，因此我們建立了線圓結(jié)構(gòu)，這樣無論路徑多么復(fù)雜，我們都可以將路徑劃分為若干個(gè)這種線圓結(jié)構(gòu)來求解。一、問題重述圖1是一個(gè)800800的平面場(chǎng)景圖，在原點(diǎn)O(0, 0)點(diǎn)處有一個(gè)機(jī)器人，它只能在該平面場(chǎng)景范圍內(nèi)活動(dòng)。圖中有12個(gè)不同形狀的區(qū)域是機(jī)器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述如下表：編號(hào)障礙物名稱左下頂點(diǎn)坐標(biāo)其它特性描述1正方形(300, 400)邊長(zhǎng)2002圓形圓心坐標(biāo)(550, 450)，半徑703平行四邊形(360, 240)底邊長(zhǎng)140，左上頂點(diǎn)坐標(biāo)(400, 330)4三角形(280, 100)上頂點(diǎn)坐標(biāo)(345, 210)，右下頂點(diǎn)坐標(biāo)(410, 100)5正方形(80, 60)邊長(zhǎng)1506三角形(60, 300)上頂點(diǎn)坐標(biāo)(150, 435)，右下頂點(diǎn)坐標(biāo)(235, 300)7長(zhǎng)方形(0, 470)長(zhǎng)220，寬608平行四邊形(150, 600)底邊長(zhǎng)90，左上頂點(diǎn)坐標(biāo)(180, 680)9長(zhǎng)方形(370, 680)長(zhǎng)60，寬12010正方形(540, 600)邊長(zhǎng)13011正方形(640, 520)邊長(zhǎng)8012長(zhǎng)方形(500, 140)長(zhǎng)300，寬60在圖1的平面場(chǎng)景中，障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)（要求目標(biāo)點(diǎn)與障礙物的距離至少超過10個(gè)單位）。規(guī)定機(jī)器人的行走路徑由直線段和圓弧組成，其中圓弧是機(jī)器人轉(zhuǎn)彎路徑。機(jī)器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個(gè)或多個(gè)相切的圓弧路徑組成，但每個(gè)圓弧的半徑最小為10個(gè)單位。為了不與障礙物發(fā)生碰撞，同時(shí)要求機(jī)器人行走線路與障礙物間的最近距離為10個(gè)單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機(jī)器人無法完成行走。機(jī)器人直線行走的最大速度為個(gè)單位/秒。機(jī)器人轉(zhuǎn)彎時(shí)，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。如果超過該速度，機(jī)器人將發(fā)生側(cè)翻，無法完成行走。請(qǐng)建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和最短時(shí)間路徑的數(shù)學(xué)模型。對(duì)場(chǎng)景圖中4個(gè)點(diǎn)O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計(jì)算：(1) 機(jī)器人從O(0, 0)出發(fā)，OA、OB、OC和OABCO的最短路徑。(2) 機(jī)器人從O (0, 0)出發(fā)，到達(dá)A的最短時(shí)間路徑。注：要給出路徑中每段直線段或圓弧的起點(diǎn)和終點(diǎn)坐標(biāo)、圓弧的圓心坐標(biāo)以及機(jī)器人行走的總距離和總時(shí)間。圖1 800800平面場(chǎng)景圖二、問題分析本題可以用AutoCAD作圖軟件完成部分路線及線段、弧線、坐標(biāo)的標(biāo)注等。問題一O點(diǎn)到A點(diǎn)理論上是直線最短，但不能折點(diǎn)轉(zhuǎn)彎（必須切線轉(zhuǎn)彎）、必須與障礙物保持10單位的距離，轉(zhuǎn)彎弧線半徑最短為10個(gè)單位，則可以以障礙物5的左上角和右下角點(diǎn)位圓心畫半徑為10單位的圓，并在障礙物4的左下角畫同樣的圓，那么我們可以用拉繩子的方法模擬機(jī)器人行走路線，求出到達(dá)目標(biāo)點(diǎn)的最短距離。 O到B與O到CO到B與O到C最短路線求解分析原理與O到A一樣不再重述。O到A到B到C再到O要求機(jī)器人到達(dá)各目標(biāo)點(diǎn)在回到原點(diǎn)，此時(shí)不但要考慮障礙物的問題還要考慮從以目標(biāo)點(diǎn)到另一目標(biāo)點(diǎn)的轉(zhuǎn)彎問題，此時(shí)簡(jiǎn)單的拉線一不滿足。問題二時(shí)間與路程和速度的關(guān)系，速度與轉(zhuǎn)彎半徑的關(guān)系，根據(jù)此公式不難得出半徑與速度的關(guān)系，即半徑越大速度約接近5，但半徑越大路程越長(zhǎng)，消耗時(shí)間也越多。三、模型假設(shè)與約定1、假設(shè)機(jī)器人無體積。2、假設(shè)切線轉(zhuǎn)彎時(shí)速度變化為瞬間，即沒有加速度。3、做題所用的數(shù)據(jù)全部保留兩位小數(shù)4、用AutoCAD軟件作圖過程不予描述，例舉兩條路線進(jìn)行分析。四、符號(hào)說明及名詞定義V:機(jī)器人行走速度V():機(jī)器人弧線行走速度:機(jī)器人直線行走最大速度：機(jī)器人轉(zhuǎn)彎半徑T：機(jī)器人行走時(shí)間S：機(jī)器人行走路程五、模型建立模型建立1、先來證明一個(gè)猜想：猜想一：具有圓形限定區(qū)域的最短路徑是由兩部分組成的：一部分是平面上的自然最短路徑（即直線段），另一部分是限定區(qū)域的部分邊界，這兩部分是相切的，互相連接的。（即問題分析中的拉繩子拉到最緊時(shí)的狀況）證明：假設(shè)在平面中有A（a，0）和B（-a，0）兩點(diǎn)，中間有一個(gè)半圓形的障礙物，證明從A到B的最路徑為AEFB。平面上連接兩點(diǎn)最短的路徑是通過這兩點(diǎn)的直線段，但是連接兩點(diǎn)的線段于障礙物相交，所以設(shè)法嘗試折線路徑。在y軸上取一點(diǎn)C（0，y），若y適當(dāng)大，則折線ACB與障礙物不相交，折線ACB的長(zhǎng)度為： 顯然隨著y的減小而減小，減小y得，即,使得與與障礙物相切，切點(diǎn)分別為E和F,顯然是這種折線路徑中最短的。由于滿足的角滿足,所以易知弧度EF小于的長(zhǎng)， 即,從而,記線段AE、弧度EF、線段FB為AEFB,那么AEFB比任何折線路徑都短。下面在考察一條不穿過障礙物的任何一條路徑，設(shè)其分別于OE和OF的延長(zhǎng)線交與P、Q兩點(diǎn)，記A和P之間的路徑長(zhǎng)度為，顯然,又由AEEO,所以|,從而,同理可得。再來比較PQ之間路徑長(zhǎng)度和圓弧EF的長(zhǎng)度的大小。若PQ之間的路徑可有極坐標(biāo)方程,則有,可得： 亦即路徑APQB的長(zhǎng)度超過路徑AEFB的長(zhǎng)度。以上證明足以說明了AEFB是滿足條件A到B的最短路徑。猜想二:如果一個(gè)圓環(huán)可以繞著環(huán)上一個(gè)定點(diǎn)轉(zhuǎn)動(dòng)，那么過圓環(huán)外兩定點(diǎn)連接一根繩子，并以該圓環(huán)為支撐拉緊繩子，達(dá)到平衡狀態(tài)時(shí)，圓心與該頂點(diǎn)以及兩條切線的延長(zhǎng)線的交點(diǎn)共線。 圖3證明猜想：如圖4.31所示，E點(diǎn)就是圓環(huán)上的一個(gè)頂點(diǎn)，就是拉緊的繩子，就是切線AC和BD的延長(zhǎng)線的交點(diǎn)，證明、E、三點(diǎn)共線。我們可以用力學(xué)的知識(shí)進(jìn)行證明，因?yàn)槭抢o的繩子，所以兩邊的繩子拉力相等，設(shè)為，它們的合力設(shè)為，定點(diǎn)對(duì)圓環(huán)的作用力設(shè)為。那么由幾何學(xué)的知識(shí)我們可以知道一定與共線，而又由力的平衡條件可知：=即與共線。綜上所述、和三點(diǎn)一定共線。2、有了以上這個(gè)定理我們可以建立以下模型：如圖4，要求求出機(jī)器人從A繞過障礙物經(jīng)過M點(diǎn)到達(dá)目標(biāo)點(diǎn)B的最短路徑，我們采用以下方法：用一根釘子使一個(gè)圓環(huán)定在M點(diǎn)，使這個(gè)圓環(huán)能夠繞M點(diǎn)轉(zhuǎn)動(dòng)。然后連接A和B的繩子并以這些轉(zhuǎn)彎處的圓弧為支撐（這里轉(zhuǎn)彎處圓弧的半徑均按照最小轉(zhuǎn)彎半徑來計(jì)算），拉緊繩子，那么繩子的長(zhǎng)度就是A到B的最短距離。我們可以把路徑圖抽象為以下的幾何圖形。下面我們對(duì)這段路徑求解：圖4如圖，A是起點(diǎn)，B是終點(diǎn)，和是兩個(gè)固定的圓， 是一個(gè)可以繞M(p，q)點(diǎn)轉(zhuǎn)動(dòng)的圓環(huán)，三個(gè)圓的半徑均為r，C、D、E、F、G、H均為切點(diǎn)。a、b、c、e，f分別是A、A、A、的長(zhǎng)度。A、B、均是已知點(diǎn)，是未知點(diǎn)。那么最短路徑就可以表示為：因?yàn)辄c(diǎn)的坐標(biāo)未知，所以我們就不能用模型一中的線圓結(jié)構(gòu)對(duì)其進(jìn)行求解。故得先求出點(diǎn)的坐標(biāo)。設(shè)坐標(biāo)為（m，n），、分別為（=1、2、3、4、5），、分別為、。這樣便有以下關(guān)系：在中：在中：在中：在中：則：又因?yàn)橐欢〞?huì)在的角平分線上，所以滿足：我們采用向量的形式來求，易知的一個(gè)方向向量：而與垂直，故其一個(gè)方向向量：而：所以：綜合以上式子可以求得的坐標(biāo)，從而可以得出路徑的長(zhǎng)為：=+HB，這可以采用模型一中的線圓結(jié)構(gòu)來求解。建立模型繩子套在一個(gè)環(huán)上，環(huán)套在一個(gè)定圓上。如圖5圖5可證明此路線為最短路徑。六、模型求解問題一用AutoCAD軟件對(duì)機(jī)器人的行走路徑進(jìn)行作圖分析。1、O點(diǎn)到A點(diǎn)(OA)目測(cè)從O點(diǎn)到A點(diǎn)比較短的路線有兩條，即從障礙物5頂部繞和從其底部繞（如圖6）。用AutoCAD軟件對(duì)路線進(jìn)行標(biāo)注（如圖7），計(jì)算兩條路線的長(zhǎng)度。路線1：線路2：兩條路線進(jìn)行比較可知線路1最短。2、O點(diǎn)到B點(diǎn)(OB)目測(cè)可知從O點(diǎn)到B點(diǎn)的最短路線必從O點(diǎn)到B點(diǎn)線路1（如圖8）和O點(diǎn)到B點(diǎn)線路2（如圖9）中產(chǎn)生，分別對(duì)兩條路進(jìn)行標(biāo)注，線路1標(biāo)注圖（如圖6），線路2標(biāo)注圖（如圖10），計(jì)算兩條路線的長(zhǎng)度。圖4圖5圖6圖7線路1：線路2：對(duì)和進(jìn)行比較可知（），線路1為最短線路。3、O點(diǎn)到C點(diǎn)(OC)作圖分析可得出兩條路線距離比較近，線路1（如圖11）和線路2（如圖12）。分別對(duì)兩條路進(jìn)行標(biāo)注，線路1標(biāo)注圖（如圖13），線路2標(biāo)注圖（如圖14），計(jì)算兩條路線的長(zhǎng)度。圖8圖9圖10圖11線路1： 線路2：對(duì)、進(jìn)行比較可知,線路1最短。4、OABCO若使此路徑最短，則取OA和OC的最短路線,AB和BC的最短線路不難看出, OABCO的最短線路如圖15，對(duì)此線路進(jìn)行標(biāo)注，如圖16。問題二此問題可以用模型二解決，根據(jù)公式可知弧線速度與轉(zhuǎn)彎半徑的關(guān)系，即隨著的增大的增長(zhǎng)幅度逐漸最終趨近與0（弧度線的行走速度趨近與5）。根據(jù)公式可知弧線長(zhǎng)度與轉(zhuǎn)彎半徑的關(guān)系。由此可知機(jī)器人行走距離與行走速度和時(shí)間的關(guān)系。最短時(shí)間路線如圖17，標(biāo)注層如圖18.七、模型檢驗(yàn)和模型評(píng)價(jià)一、模型優(yōu)點(diǎn)1、運(yùn)用AutoCAD作圖軟件，方便快捷的標(biāo)注出各線段，各點(diǎn)的相關(guān)信息。2、小數(shù)點(diǎn)保留兩位，精確度較高。3、模型簡(jiǎn)單易懂，便于實(shí)際檢驗(yàn)及應(yīng)用。二、模型缺陷1、問題二求解精確度不高。沒有相關(guān)程序作支持。2、在障礙物較多時(shí)，且形狀不規(guī)則時(shí)，模型需要進(jìn)一步改進(jìn)。八、參考文獻(xiàn)1尤承業(yè)，解析幾何，北京，北京大學(xué)出版社，20042邦迪，圖論及其應(yīng)用，西安，西安科學(xué)出版社 19843譚永基，數(shù)學(xué)模型，上海，復(fù)旦大學(xué)出版社，20114周培德，計(jì)算幾何算法與設(shè)計(jì)，北京清華大學(xué)出版社，20055胡海星，RPG游戲中精靈的移動(dòng)問題，雜志程序員 2011；九、附錄各路線的相關(guān)信息（O到A、O到B、O到C的最短路線，OABCO的最短路線，O到A的最短時(shí)間路線）O到B最短距離路線O到A最短距離路線行走路線1110987654321321序號(hào)直線弧線直線弧線直線弧線直線弧線直線弧線直線直線弧線直線類型(140.69,596.35)(144.5,591.65)(225.0,538.35)(230.63,530)(230.63,470)(222.52,459.82)(147.96,444.79)(141.68,440.55)(51.8,305.5)(50.04,301.04)(0,0)(76.61,219.41)(70.51,213.14)(0,0)起始坐標(biāo)(100,700)(140.69,596.35)(144.5,591.65)(225.5,538.35)(230.63,530)(230.63,470)(222.52,459.82)(147.96,444.79)(141.68,440.55)(51.8,305.5)(50.04,301.4)(300,300）(76.61，219.41）(70.51,213.14）終點(diǎn)坐標(biāo)111.366.1596.959.896013.6676.417.78162.254.23305.78237.499.05224.5長(zhǎng)度(150,600)(220,530)(220,470)(150,435)(60,300)（80,210）圓心坐標(biāo)800.46471.04總距離180.6596.02總時(shí)間OC最短距離路線行走路線1110987654321序號(hào)直線弧線直線弧線直線弧線直線弧線直線弧線直線類型(727.65,606.44)(730,600)(730,520)(727.94,513.92)(492.06,206.08)(491.66,205.51)(417.82,94.83)(412.17,90.24)(232.17,50.24)(232.11,50.23)(0,0)起始坐標(biāo)(700.640)(727.65,606.44)(730,600)(730,520)(727.94,513.92)(492.06,206.08)(491.66,205.51)(417.82,94.83)(412.17,90.24）(232.17,50.24）(232.11,50.23）終點(diǎn)坐標(biāo)43.596.89806.54387.810.7133.047.69184.390.06237.49長(zhǎng)度(720,600)(720,520)(500,200)(410,100)（230,60）圓心坐標(biāo)1088.2總距離228.01總時(shí)間OABCO行走路線1413121110987654321序號(hào)弧線直線弧線直線弧線直線弧線直線弧線直線弧線直線弧線直線類型(368,670.2)(272,689.8)(270.88,689.96)(109.06,704.22)(99.04,690.2)(140.86595.94)(144.5,591.65)(225.5,538.35)(229.54,532.99)(300.43,307.11)(294.15,294.66)(76.73,219.45)(70.51,213.14)(0,0)起始坐標(biāo)(370,670)(368,670.2)(272,689.8)(270.88,689.96)(109.06,704.22)(99.04,690.2)(140.86,595.94)(144.5,591.65)(225.5,538.35)(229.54,532.99)(300.43,307.11)(294.15,294.66）(76.61，219.41）(70.51,213.14）終點(diǎn)坐標(biāo)2.0197.981.13162.4420.76103.115.7196.956.85236.7515.42230.069.05224.5長(zhǎng)度(370,680)(270,680)(108.18,694.25)(150,600)(220,530)(290.88,304.11)（80,210）圓心坐標(biāo)2730總距離568.66總時(shí)間OABCO最短距離路線行走路線2827262524232221201918171615序號(hào)弧線直線弧線直線弧線直線弧線直線弧線直線弧線直線弧線直線類型(492.06，206.08)(727.94,513.92)(730,520)(730,600)(727.65,606.44)(701.59,637.39)(641.7,699.47)(679.77,732.13)(740,670)(540,740)(534.41,738.29)(435.59,671.7