建模機器人避路障問題

1、建模機器人避路障問題機器人避障問題摘要：本文根據(jù)題目要求，主要研究了在一個區(qū)域內(nèi)有障礙物的最短路徑問題 依題意我們可以認為最短路徑一定是由線和最小圓弧組成，圓心在障礙物的頂 點。對于問題一首先討論由O到A的距離，為了到達目標點，我們建立了圓線模型。將路線 分為兩部分：一部分是平面上的自然最短路徑(即直線段)，另一部分是限定區(qū)域的部分邊界的半徑至少十個單位以外的圓弧，得到其路徑長度為Lr yjc r r ,并用MATLA程序解得最短路徑471.0372對于O到B的距離問題，為了到達目標點，我們需要建立圓與點圓模型，其 中由于圓與圓之間的不同的位置關(guān)系，又可以分為同向相切與異向相切，同向相切時LJ

2、br2Jc2r21r 2 qq，異向相切時LJbr2Jc2r2r 1r 2彳(罟)2r2。由MATLA程序解得最短路徑869.8523。對于O到C,與前者的區(qū)別是障礙物大圓視為半徑較大的轉(zhuǎn)折弧，為了到達 目標點，依舊建立圓圓結(jié)構(gòu)與線圓結(jié)構(gòu)模型，經(jīng)MATLA程序解得最短路徑為1011.3。對于OABC的路徑問題，除了用了上述提到的圓圓，線圓結(jié)構(gòu)外，還建立了圓心偏移的模型(即點ABC在相對應(yīng)的弧上)，A點偏以后的坐標為(290.9,304.1)，B點偏以后的坐標為(108.23,694.32)，C點偏以后的坐標為(707.26,633.12)，將 OABC分為兩部分，一部分為 OABCN 730,

3、520 )的距離,另一部分為由N回到O的距離，兩部分結(jié)果之和即為所求路徑。OABC的距離1.7691e+003,N 到C為880.7744，總長為 2649,6744對于問題二，我們將路線問題轉(zhuǎn)化為規(guī)劃問題，求的最短時間，目標函數(shù) 為T AC BD rVow由 LINGOt最短時間為 94.22822，切點坐標(69.80,211.98 )(77.75,220.14) 圓心(82.14,207.92 )。關(guān)鍵詞：最短路徑最優(yōu)化模型避障路徑規(guī)劃問題線圓結(jié)構(gòu)一問題重述機器人從原點C出發(fā)且他只能在圖中所給出的800*800正方平面場景范圍內(nèi) 活動。且平面場景范圍內(nèi)的12個不同形狀的區(qū)域是機器人不能與

4、之發(fā)生碰撞的 障礙物。在平面場景中，障礙物外指定一點為機器人要到達的目標點(要求目標點 與障礙物的距離至少超過10個單位)。規(guī)定機器人的行走路徑由直線段和圓弧 組成，其中圓弧是機器人轉(zhuǎn)彎路徑。機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線 路徑相切的一段圓弧組成，也可以由兩個或多個相切的圓弧路徑組成，但每個 圓弧的半徑最小為10個單位。為了不與障礙物發(fā)生碰撞，同時要求機器人行走 線路與障礙物間的最近距離為10個單位，否則機器人將無法完成行走。機器人直線行走的最大速度為V。5個單位/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎 速度為v v( )V，其中 是轉(zhuǎn)彎半徑。1 e請建立機器人從區(qū)域中一點到達另一點的避障最短路徑和

5、最短時間路徑的 數(shù)學(xué)模型。對 4個點 0(0, 0)，A(300, 300) ，B(100, 700)，C(700, 640)，具體 計算：(1)機器人從0(0, 0)出發(fā)，OA、OB、OC和OA B-C-O勺最短路 徑。 機器人從O (0, 0)出發(fā)，到達A的最短時間路徑平面場景圖二問題分析1、問題一中要求定點機器人按照一定的行走規(guī)則繞過障礙物到達目標點的 最短路徑，由于機器人不能折線拐彎，所以拐彎處必然是一圓弧，我們采用線 圓結(jié)構(gòu)的方法建立模型，用這種方法尋找可能的最短路徑，然后采用窮舉法列 出0到目標點的最短路徑。這其中我們不能僅僅考慮是經(jīng)過障礙物拐點的問題（例如由OABCO路徑的計算）

6、，也應(yīng)該考慮經(jīng)過路徑中的目標點處轉(zhuǎn)彎的問題， 這是簡單的線圓結(jié)構(gòu)就不能解決這種問題，我們在拐點及途中目標點處采用最 小轉(zhuǎn)彎半徑的形式，使機器人能夠沿直線通過途中的目標點，然后建立優(yōu)化模 型對此問題進行優(yōu)化，最終求得最短路徑。2、問題二中涉及到機器人的速度問題， 這樣就不能以最短路徑來進行計算, 因為拐彎速度與直線速度不相同，這時就需要在加入速度因素，來求得最佳結(jié) 果。三模型假設(shè)1假設(shè)機器人能夠抽象成點來處理。2假設(shè)機器人在直線上或弧上均勻速行走四符號說明付號符號含義L出發(fā)點到目標點的路徑長度r轉(zhuǎn)彎半徑R經(jīng)過障礙物圓2處的轉(zhuǎn)彎半徑五模型的建立與求解我們?nèi)菀椎弥瘘c到目標點無論中間障礙物有多少，

7、最短路徑都應(yīng)該是 若干個線圓結(jié)構(gòu)組成。在本題中存在障礙物的狀況，我們易知，在求兩點之間 的最短路徑中的拐彎半徑我們應(yīng)該按照最小的轉(zhuǎn)彎半徑來計算才能達到最優(yōu)， 所以我們理解為在拐點處的危險區(qū)域是一個半徑為10的圓弧。以下圖為例,1）點圓模型如上圖，設(shè)A （錯誤！未找到引用源。為起點，B （錯誤！未找到引用源。為 目標點，C （錯誤！未找到引用源。和 D （錯誤！未找到引用源。分別為機器人 經(jīng)過拐點分別于隔離危險線拐角小圓弧的切點，圓心為（錯誤！未找到引用源。， 圓的半徑為r，AB的長度為a，AO的長度為b，B0的長度為c,角度 AOB=g 誤！未找到引用源。, AOC二錯誤！未找到引用源。,BO

8、D=錯誤！未找到 引用源。，COD.求A錯誤！未找到引用源。B的長度，設(shè)為L.解法如下：如上圖可得有以下關(guān)系：a,(X2X1)2(y2Yi)2b、(X5X1)2(YsYi)2c.(X5X2)2(ysY2)2在AOB中：,2 2 2 arccos(-c )2bc在 Rt AOC : 在Rt AOC中:所以：從而可得：r=arccos-barccos cLr我們就可以這樣認為，起點到目標點無論中間障礙物有多少，最短路徑都應(yīng)該 是若干個點圓結(jié)構(gòu)所組成。在本題中存在障礙物的狀況，且障礙物在拐點處的 危險區(qū)域是一個半徑為10的圓弧，所以結(jié)合上述結(jié)論，我們易知，求兩點之間 的最短路徑中的轉(zhuǎn)彎半徑我們應(yīng)該按

9、照最小的轉(zhuǎn)彎半徑來算才能達到最優(yōu)。2）線圓模型而對于下圖兩種情況我們不能直接采用線圓的結(jié)構(gòu)來解決，需要做簡單的變 換。情況一（同向）：這里我們依然設(shè)圓心坐標分別為 0（洛,力）和O（X2, y2）,半徑均為r，這樣我們可以得到：此段路徑就是由兩段狐與兩段直線的組合加圓心距的總長。這樣我們 就可以利用1）中的方法，先求A到E,再求D到B,最后減去DE的長度，這樣 分兩段就可以求解。同理如果有更多的轉(zhuǎn)彎，我們同樣可以按照此種方法分解。情況二（反向）：我們假設(shè)兩圓心坐標分別為O（xi, yi）和0 （X2, y2）,半徑均為r， M點坐標為 （X3, y3），那么我們很容易可以求得：M點坐標X3X

10、X22y % y2y3 V利用M將圖上分解成兩個線圓結(jié)構(gòu)，利用上述方法進行計算，易得出結(jié)果。3）圓心偏移模型在處理OAEC路徑中，由于需要使ABC處在路徑上，所以尋找所對應(yīng)弧的 圓心，建立模型R如圖所示，E為0102的中點，圖中的E為題中的ABC 01為各點所在弧的圓心， 利用LINGO找出使點落在最短路徑上所對應(yīng)的圓心，利用此圓心為拐點，用上 述的方法進行計算。問題一一、以下給出了機器人到個目標點的可能路徑的最短路徑：如下圖就是機器人由0到目標點的最短路線1) 0到目標點A的最短路徑求解，通過計算，機器人從障礙物 5的上方走的 最短路徑大于機器人從障礙物 5下方走的最優(yōu)路徑，機器人行走的最優(yōu)

11、路線的 可能性已經(jīng)列出，附錄中給出兩種方案的求解結(jié)果。最小結(jié)果對應(yīng)的行走路路線乃是黑線所示，就是0到A的最短路徑471.0372。8009B86002400632005200600S(M)6A2005200600S(M)11:4004002 ） O到目標點B的最短路徑求解，我們在附錄中給出三種路徑的求解過程, 分別為：（1）由0路過障礙物5,8到達B,如圖中虛線所示（2）由0路過障礙物6的上端，至V 7,8最后到達B點，如圖中黑實線所示（3）由0路過障礙物6的下端，至V 7,8最后到達B點，圖中間隔線所示。 附錄中給出三種方案的結(jié)果，最終比較得到最短路徑為路徑（2）即圖中黑實線所示路徑長度為

12、869.8523。3） O到目標點C的最短路徑求解，我們在附錄中給出三種路徑的求解過程， 分別為：（1）由0路過障礙物5的上端,3,2,11到達C,黑線所示；（2）由0路過障礙物5的下端，至V 3,2,11最后到達C點，如圖中虛線所示。 由附錄中給出的結(jié)果，最終比較得到最短路徑為路徑（1 ），圖中黑實線所示，路徑長度為1.0113e+003。800B94002004) OABC的最短路徑求解，通過計算 OA,OC,OB我們?nèi)菀椎贸鯫ABC的最短 路徑如下圖所標，求解過程有兩部分組成，先計算由 O到N點的距離，再求N到O 點的距離，最終結(jié)果為二者之和，結(jié)果為 2649,6744。10c60011

13、26r31258400200問題二設(shè)目標函數(shù)為VoViD Xi,yi Cgy ）,O（Xo,y。）0x180;0 y1240;80x2300;210y2300;v05; v1v10 0.1* 2 eBD . X12 y2 ; AC22.300 x2300 y2 ;cBOAOBO AO AB2 a cos a cos a cos;由LINGO可得出所求， 最短時間為94.22822，切點坐標 (69.80,211.98 ) (77.75,220.14 )圓心(82.14,207.92 )。六、模型評價模型優(yōu)點、模型優(yōu)化后用解析幾何，三角形中各個之間的關(guān)系進行求解，精確度較2、模型簡單易懂，便于實

14、際檢驗及應(yīng)用。3、模型缺陷、此模型適于全局規(guī)劃，獲得精確解卻失去了效率。2、在障礙物較多時，且形狀不規(guī)則時，模型需要進一步改進。3 、在程序設(shè)計時，較復(fù)雜，需要繁瑣的編輯過程。七、參考文獻【1】韓新社，高等數(shù)學(xué)，合肥：中國科學(xué)技術(shù)大學(xué)出版社2009.7【2】姜啟源，數(shù)學(xué)模型M，北京：高等教育出版社，2003.【3】謝金星 薛毅，優(yōu)化建模與LINGO，北京：清華大學(xué)出版社，2005年【4】劉來福 曾文藝，數(shù)學(xué)模型與數(shù)學(xué)建模，北京：北京師范大學(xué)出版社2003.八、附錄附錄一：問題一中用matlab解一 OA長度求解1) %求解一次轉(zhuǎn)彎所經(jīng)路線總長1 %O初始點E:轉(zhuǎn)彎圓弧圓心A:到達點fun ct

15、i onresult=z on gcha ng(O,E,A,r)0E=sqrt(0(1)-E(1)F2+( O( 2)-E(2)A2);AE=sqrt(A(1)-E(1)A2+(A (2)七(2)八2);0A=sqrt(0(1)-A(1)F2+(0 (2)-A(2)A2);alpha1=acos(OEA2+AEA2-OAA2)/(2*AE*OE);alpha2=acos(r/AE);alpha3=acos(r/OE);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4 為轉(zhuǎn)彎圓心角result=sqrt(AEA2-rA2)+sqrt(OEA2-rA2)+r*alp

16、ha4;將(0,0 ), (80,210 ), (300 , 300 )代入 求得長度為ans =471.03722 %0初始點F:轉(zhuǎn)彎圓弧圓心A:到達點fun cti onresult=z on gcha ng(O,E,A,r)0E=sqrt(0(1)-F(1)A2+( 0( 2)-F(2)F2);AF=sqrt(A(1)-F(1)A2+(A (2)-F(2)F2);0A=sqrt(0(1)-A(1)A2+(0 (2)-A(2)A2);alpha仁acos(0FA2+AFA2-0AA2)/(2*AF*0F);alpha2=acos(r/AF);alpha3=acos(r/0F);alpha4

17、=2*pi-alpha1-alpha2-alpha3;%alpha4 為轉(zhuǎn)彎圓心角result=sqrt(AEA2-rA2)+sqrt(0EA2-rA2)+r*alpha4;將(0,0)，( 230,60)，( 300，300 )代入 求得長度為ans =498.42592) 計算0B路徑1%0初始點 E,F,G,H,D :轉(zhuǎn)彎圓弧圓心M,N:為距離中點B:到達點fun ctio nresult=zo ngcha ng(0,E,F,G,H,D,M,N,B,r)0E=sqrt(0(1)-E(1)A2+( 0( 2)七(2)八2);0F=sqrt(0(1)-F(1)A2+( 0( 2)-F(2)F

18、2);EF=sqrt(E(1)-F(1)A2+(E (2)-F (2)八2);MF=sqrt(M(1)-F(1)A2+( M( 2)-F(2)F2);ME=sqrt(M(1)-E(1)A2+( M( 2)-E(2)F2);MG=sqrt(M(1)-G(1)A2+( M( 2)-G(2)F2);GH=sqrt(G(1)-H(1)F2+(G (2)-H(2)A2);GN=sqrt(G(1)-N(1)F2+(G (2)-N(2)F2);MH=sqrt(M(1)-H(1)A2+( M( 2)-H(2)F2);NH=sqrt(N(1)-H(1)A2+(N (2)-H(2)A2);BN=sqrt(B(1)

19、-N(1)A2+(B (2)-N(2)A2);DN=sqrt(D(1)-N(1)A2+(D (2)-N(2)A2);BD=sqrt(B-D(1)F2+(B (2)-D(2)F2);alpha仁acos(OEA2+EFA2-OFA2)/(2*OE*EF);alpha2=acos(r/OE);alpha3=1.5*pi-alpha1-alpha2;alpha4=acos(EFA2+MFA2-MEA2)/(2*EF*MF);alpha5=acos(r/MF);alpha6=1.5*pi-alpha4-alpha5;alpha7=acos(MGA2+GHA2-MHA2)/(2*MG*GH);alpha

20、8=acos(r/MG);alpha9=1.5*pi-alpha7-alpha8;alpha10=acos(N 屮 2+GHA2-GNA2)/(2*NH*GH);alpha11=acos(r/NH);alpha12=1.5*pi-alpha10-alpha11;alpha13=acos(BDA2+DNA2-BNA2)/(2*BD*DN);alpha14=acos(r/BD);alpha15=acos(r/DN);alpha16=2*pi-alpha13-alpha14-alpha15;TS1= sqrt(OEA2-rA2);TS2=EF;TS3=sqrt(MFA2-rA2);TS4=GH;TS

21、5=sqrt(NHA2-rA2);TS6=sqrt(DNA2-rA2);TS7=sqrt(BDA2-rA2);S1S1hu=r*alpha3;S1S2hu=r*alpha6;S1S3hu=r*alpha9;S1S4hu=r*alpha12;S1S5hu=r*alpha16;result=TS1+TS2+2*TS3+TS4+TS5+TS6+TS7+S1S2hu+S1S4hu+S1S3hu+S1S1hu+S1S5hu;將0,0,160,300,150,435,220,470,220,530,150,600,185,452.5,175,565,100,700,10)代入可求得ans =869.852

22、3 2%O初始點E F:轉(zhuǎn)彎圓弧圓心B:到達點fun cti onresult=z on gcha ng(O,E,F,B,r)OE=sqrt(O(1)-E(1)F2+( O(2)-E(2)A2);OF=sqrt(O(1)-F(1)A2+( O( 2)-F(2)F2);FE=sqrt(F(1)-E(1)A2+(F (2)-E (2)八2);FB=sqrt(F(1)-B(1)A2+(F (2)-B(2)A2);BE=sqrt(B(1)-E(1)A2+(B (2)七(2)八2);alpha仁acos(OEA2+FEA2-OFA2)/(2*OE*FE); alpha2=acos(r/OE);alpha

23、3=1.5*pi-alpha1-alpha2;alpha4=acos(FBA2+FEA2-BEA2)/(2*FB*FE); alpha5=acos(r/FB);alpha6=1.5*pi-alpha4-alpha5;TS1= sqrt(OEA2-rA2);S2W=sqrt(FBA2-rA2);S1S2hu=r*alpha3;S3W=FES1S3hu=r*alpha6; result=TS1+S2W+S1S2hu+S3W+S1S3hu;代入將(0,0,230,60,270,680,100,700,10)可求的ans =1.0584e+0033%O初始點 E,F,G,H,D : 轉(zhuǎn)彎圓弧圓心M,N

24、:為距離中點 B:到達點fun ctio nresult=zo ngcha ng(O,E,F,G,H,M,N,B,r)OE=sqrt(O(1)-E(1)A2+( O( 2)-E(2)F2);OM=sqrt(O(1)-M(1)A2+(O (2)-M(2)F2);ME=sqrt(M(1)-E(1)A2+( M( 2)-E(2)F2);MF=sqrt(M(1)-F(1)A2+( M( 2)-F(2)F2);FG=sqrt(F(1)-G(1)A2+(F (2)-G(2)A2);NF=sqrt(N(1)-F(1)A2+( N( 2)-F(2)F2);NG=sqrt(N(1)-G(1)A2+(N (2)-

25、G(2)A2);MG=sqrt(M(1)-G(1)A2+( M( 2)-G(2)F2);BN=sqrt(B(1)-N(1)A2+(B (2)-N(2)A2);NH=sqrt(N(1)-H(1)A2+(N (2)-H(2)A2);BH=sqrt(B-H(1)F2+(B (2)-H(2)A2);EF=sqrt(E(1)-F(1)F2+(E (2)-F (2)八2);GH=sqrt(G(1)-H(1)A2+(G (2)-H(2)A2);alpha仁acos(OEA2+MEA2-OMA2)/(2*OE*ME); alpha2=acos(r/OE);alpha3=acos(r/ME);alpha4=2*

26、pi-alpha1-alpha2-alpha3;alpha5=acos(FGA2+MFA2-MGA2)/(2*FG*MF);alpha6=acos(r/MF);alpha7=1.5*pi-alpha5-alpha6;alpha8=acos(FGA2+NGA2-NFA2)/(2*FG*NG);alpha9=acos(r/NG);alpha10=1.5*pi-alpha8-alpha9;alpha11=acos(NHA2+BHA2-BNA2)/(2*NH*BH);alpha12=acos(r/NH);alpha13=acos(r/BH);alpha14=2*pi-alpha11-alpha12-a

27、lpha13;TS1= sqrt(OEA2-rA2);S1W=0.5*EF;S2W=0.5*GH;TS2=sqrt(S1WA2-rA2);TS3=sqrt(S1WA2-rA2);TS4=FG;TS5=sqrt(S2WA2-rA2);TS6=sqrt(BNA2-rA2);S1Shu=r*alpha4;S2Shu=r*alpha7;S3Shu=r*alpha10;S4Shu=r*alpha14;result=TS1+TS2+TS3+TS4+2*TS5+TS6+S1Shu+S2Shu+S3Shu+S4Shu; 將(0,0,230,60,235,600,220,470,220,530,150,600,

28、185,565,100,700,10)代入可求得ans =1.2170e+0033) 計算OC路徑1%O初始點 E,F,G,H,D :轉(zhuǎn)彎圓弧圓心M,N:為距離中點 C:到達點fun ctio nresult=zo ngcha ng(O,E,F,G,H,D,M,N,C,r,R)0E=sqrt(0(1)-E(1)F2+( 0(2)-E(2)A2);0M=sqrt(0(1)-M(1)F2+(0 (2)-M(2)F2);EM=sqrt(E(1)-M(1)A2+(E (2)-M(2)F2);MF=sqrt(M(1)-F(1)A2+( M( 2)-F(2)F2);FN=sqrt(F(1)-N(1)F2+

29、(F (2)-N(2)F2);MN=sqrt(M(1)-N(1)A2+( M( 2)-N(2)F2);GH=sqrt(G(1)-H(1)F2+(G (2)-H(2)F2);GN=sqrt(G(1)-N(1)A2+(G (2)-N(2)A2);DH=sqrt(D(1)-H(1)A2+(D (2)-H(2)A2);NH=sqrt(N(1)-H(1)A2+(N (2)-H(2)A2);CD=sqrt(C-D(1)F2+(C (2)-D(2)F2);CH=sqrt(C(1)-H(1)A2+(C (2)-H(2)A2);GD=sqrt(G(1)-D(1)A2+(G (2)-D(2)A2);alpha仁a

30、cos(0EA2+EMA2-0MA2)/(2*0E*EM); alpha2=acos(r/0E);alpha3=acos(r/EM);alpha4=2*pi-alpha1-alpha2-alpha3;alpha5=acos(FNA2+MFA2-MNA2)/(2*FN*MF);alpha6=acos(r/MF);alpha7=acos(r/FN);alpha8=2*pi-alpha5-alpha6-alpha7;alpha9=acos(GNA2+GHA2-NHA2)/(2*GN*GH);alpha10=acos(R/GN);alpha11=acos(R-r)/GH);alpha12=2*pi-a

31、lpha9-alpha10-alpha11;alpha13=acos(G 屮 2+DHA2-GDA2)/(2*GH*DH);alpha14=pi-alpha11;alpha15=1.5*pi-alpha14-alpha13;alpha16=acos(CDA2+DHA2-CHA2)/(2*CD*DH);alpha17=acos(r/CD);alpha18=1.5*pi-alpha16-alpha17;TS1= sqrt(0EA2-rA2);TS2=2*sqrt(EMA2-rA2);TS3=sqrt(FNA2-rA2);TS7=sqrt(GNA2-RA2)TS4=sqrt(G 屮 2-(R-rF2

32、);TS5=DH;TS6=sqrt(CDA2-rA2);S1S1hu=r*alpha4;S1S2hu=r*alpha8;S1S3hu=r*alpha15;S1S4hu=R*alpha12;S1S5hu=r*alpha18;result=TS1+TS2+TS5+TS6+S1S1hu+S1S2hu+S1S3hu+S1S5hu+TS4+S1S4hu+TS3+TS7;將(0,0,230,60,400,330,550,450,720,520,720,600,代入315,195,416.67,343.33,700,640,10,80)可求得ans =1.1444e+0032%O初始點 E,F,G,H,D

33、:轉(zhuǎn)彎圓弧圓心N:為距離中點 C:到達點fun ctio nresult=zo ngcha ng(O,E,F,G,H,D,N,C,r,R)OE=sqrt(O(1)-E(1)A2+( 0(2)-E(2)A2);OF=sqrt(O(1)-F(1)A2+( 0(2)-F(2)F2);EF=sqrt(E(1)-F(1)A2+(E (2)-F (2)八2);EN=sqrt(E(1)-N(1)A2+(E (2)-N(2)F2);FN=sqrt(F(1)-N(1)A2+(F (2)-N(2)A2);GH=sqrt(G(1)-H(1)A2+(G (2)-H(2)F2);GN=sqrt(G(1)-N(1)A2+

34、(G (2)-N(2)F2);DH=sqrt(D(1)-H(1)A2+(D (2)-H(2)A2);NH=sqrt(N(1)-H(1)A2+(N (2)-H(2)A2);CD=sqrt(C(1)-D(1)A2+(C (2)-D(2)A2);CH=sqrt(C(1)-H(1)A2+(C (2)-H(2)A2);GD=sqrt(G(1)-D(1)A2+(G (2)-D(2)A2);alpha仁acos(OEA2+EFA2-OFA2)/(2*OE*EF); alpha2=acos(r/OE);alpha3=1.5*pi-alpha1-alpha2;alpha4=acos(EFA2+FNA2-ENA2

35、)/(2*EF*FN);alpha5=acos(r/FN);alpha6=1.5*pi-alpha4-alpha5; alpha7=acos(GNA2+GHA2-NHA2)/(2*GN*GH); alpha8=acos(R/GN);alpha9=acos(R-r)/GH);alpha10=2*pi-alpha9-alpha7-alpha8;alpha11=acos(G 屮 2+DHA2-GDA2)/(2*GH*DH); alpha12=pi-alpha11;alpha13=1.5*pi-alpha11-alpha12; alpha14=acos(CDA2+DHA2-CHA2)/(2*CD*DH

36、); alpha15=acos(r/CD);alpha16=1.5*pi-alpha14-alpha15;TS1= sqrt(OEA2-rA2);TS2=EF;TS3=sqrt(FNA2-rA2);TS7=sqrt(GNA2-RA2);TS4=sqrt(G 屮 2-(R-rF2);TS5=DH;TS6=sqrt(CDA2-rA2);S1S1hu=r*alpha3;S1S2hu=r*alpha6;S1S3hu=r*alpha13;S1S4hu=R*alpha10;S1S5hu=r*alpha16;result=TS1+TS2+TS5+TS6+S1S1hu+S1S2hu+S1S3hu+S1S5hu

37、+TS4+S1S4hu+TS3將(0,0,80,210,400,330,550,450,720,520,720,600,416.67,343.33,700,640,10,80)代入可求得ans =1.0113e+003所以應(yīng)采取2路線3)計算OABC路徑將此路線分為兩段進行計算之前 需要找到可以使ABC落于圓上的圓心坐標 使用LINGO軟件進行最優(yōu)化處理輸入Min=sqrt (x-80)A2+(y-210)A2)+sqrt(x-220)A2+(y-530)A2);(x-300)A2+(y-300)A2=100;可得Local optimal solution found.Objective v

38、alue:467.6803Exte nded solver steps:5Total solver iteratio ns:105VariableValueReducedCostX290.88340.000000Y304.10950.000000Row Slackor Surplus DualPrice1 467.6803 -1.0000002 0.000000 0.6650490E-01再次輸入Min=sqrt(x-150)A2+(y-600)A2)+sqrt(x-370)A2+(y-680)A2);5(x-100)A2+(y-700)A2=100;可得Local optimal solut

39、ion found.Objective value:Exte nded solver steps:Total solver iteratio ns:Variable ValueCostX0.000000Y0.000000Row SlackPrice1-1.00000020.8527221E-01最后輸入min =sqrt (x-670)A2+(y-730F2)+J(x-700)A2+(y-640)A2=100;可得 Local optimal soluti on found.Objective value:Exte nded solver steps:365.31625133Reduced10

40、8.2292694.3184or Surplus Dual365.31620.000000sqrt (x-720)A2+(y-600)A2)139.2839Total solver iteratio ns:91VariableValue ReducedCostX707.26030.000000Y633.12330.000000Row Slackor Surplus DualPrice1 139.2839 -1.0000002 0.000000 0.000000所以取得三個坐標(290.9 , 304.1) ,(108.23694.32)(707.26633.12)第一部分長度輸入%初始值cle

41、ar allclcA= 0 0 0;80 210 0;290.9 304.1 2;220 530 1;150 600 2;108.23 694.32 1;270 680 1;370 680 2;430 680 1;540 730 2;670 730 1;707.26 633.12 2;720 600 2;720 530 3;%230 60 0;%410 100 1;%500 200 2;%720 520 2;%720 600 1;%700 640 3;r=10;m, n=size(A);i=1;while i=m-2p仁 A(i,1:2);p2=A(i+1,1:2);p3=A(i+2,1:2)

42、;p12=norm(p1-p2);p23=norm(p2-p3);p13=norm(p1-p3);alpha3=acos(p12A2+p23A2-p13A2)/(2*p12*p23); if i=1alpha仁acos(10/p12);L1= p12*si n(al phal);endif A(i+2,3)=1alpha2=pi/2; sita=2*pi-alpha1-alpha2-alpha3;L2=p23+10*sita;%外切圓-同側(cè)elseif A(i+2,3)=2alpha2=acos(2*r/p23);%內(nèi)切圓-兩側(cè)sita=2*pi-alpha1-alpha2-alpha3;L2

43、=r*sita+p23*si n(al pha2);else alpha2=acos(r/p23);%點sita=2*pi-alpha1-alpha2-alpha3;L2=p23*si n(al pha2)+r*sita;endL=L1+L2;L仁L;alpha仁alpha2;i=i+1;endL可得結(jié)果L =1.7691e+003第二部分輸入 functionresult=zongchang(O,E,F,G,H,D,N,C,r,R)0E=sqrt(0(1)-E(1)F2+( 0(2)-E(2)A2);0F=sqrt(0(1)-F(1)F2+( 0(2)-F(2)F2);EF=sqrt(E(1

44、)-F(1)A2+(E (2)-F (2)八2);EN=sqrt(E(1)-N(1)A2+(E (2)-N(2)F2);FN=sqrt(F(1)-N(1)A2+(F (2)-N(2)A2);GH=sqrt(G(1)-H(1)F2+(G (2)-H(2)F2);GN=sqrt(G(1)-N(1)F2+(G (2)-N(2)F2);DH=sqrt(D(1)-H(1)A2+(D (2)-H(2)F2);NH=sqrt(N(1)-H(1)A2+(N (2)-H(2)A2);CD=sqrt(C-D(1)F2+(C (2)-D(2)F2);CH=sqrt(C(1)-H(1)A2+(C (2)-H(2)A2

45、);GD=sqrt(G(1)-D(1)A2+(G (2)-D(2)A2);alpha仁acos(0EA2+EFA2-0FA2)/(2*0E*EF);alpha2=acos(r/0E);alpha3=1.5*pi-alpha1-alpha2;alpha4=acos(EFA2+FNA2-ENA2)/(2*EF*FN);alpha5=acos(r/FN);alpha6=1.5*pi-alpha4-alpha5;alpha7=acos(GNA2+GHA2-NHA2)/(2*GN*GH);alpha8=acos(R/GN);alpha9=acos(R-r)/GH);alpha10=2*pi-alpha9-alpha7-alpha8;alpha11=acos(G 屮 2+DHA2-GDA2)/(2*GH*DH);alpha12=pi-alpha11;alpha13=1.5*pi-alpha11-alpha12;alpha14=acos(CDA2+DHA2-C