建模機器人避路障問題

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

2、短路徑869.8523。對于O到C，與前者的區(qū)別是障礙物大圓視為半徑較大的轉折弧，為了到達目標點，依舊建立圓圓結構與線圓結構模型，經(jīng)MATLAB程序解得最短路徑為1011.3。對于OABCO的路徑問題，除了用了上述提到的圓圓，線圓結構外，還建立了圓心偏移的模型（即點ABC在相對應的弧上），A點偏以后的坐標為（290.9,304.1），B點偏以后的坐標為（108.23,694.32），C點偏以后的坐標為（707.26,633.12），將OABCO分為兩部分，一部分為OABCN（730,520）的距離，另一部分為由N回到O的距離，兩部分結果之和即為所求路徑。OABCN的距離1.7691e+003,

3、N到O為880.7744，總長為2649,6744對于問題二，我們將路線問題轉化為規(guī)劃問題，求的最短時間，目標函數(shù)為由LINGO有最短時間為94.22822，切點坐標（69.80,211.98）（77.75,220.14）圓心（82.14,207.92）。關鍵詞: 最短路徑最優(yōu)化模型避障路徑規(guī)劃問題線圓結構一 問題重述機器人從原點O出發(fā)且他只能在圖中所給出的800*800正方平面場景圍活動。且平面場景圍的12個不同形狀的區(qū)域是機器人不能與之發(fā)生碰撞的障礙物。在平面場景中，障礙物外指定一點為機器人要到達的目標點（要求目標點與障礙物的距離至少超過10個單位）。規(guī)定機器人的行走路徑由直線段和圓弧組成

4、，其中圓弧是機器人轉彎路徑。機器人不能折線轉彎，轉彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個或多個相切的圓弧路徑組成，但每個圓弧的半徑最小為10個單位。為了不與障礙物發(fā)生碰撞，同時要求機器人行走線路與障礙物間的最近距離為10個單位，否則機器人將無法完成行走。機器人直線行走的最大速度為個單位/秒。機器人轉彎時，最大轉彎速度為，其中是轉彎半徑。請建立機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑的數(shù)學模型。對4個點O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計算：(1) 機器人從O(0, 0)出發(fā)，OA、OB、OC和OABCO的最短

5、路徑。(2) 機器人從O (0, 0)出發(fā)，到達A的最短時間路徑。 800800平面場景圖二問題分析1、問題一中要求定點機器人按照一定的行走規(guī)則繞過障礙物到達目標點的最短路徑，由于機器人不能折線拐彎，所以拐彎處必然是一圓弧，我們采用線圓結構的方法建立模型，用這種方法尋找可能的最短路徑，然后采用窮舉法列出O到目標點的最短路徑。這其中我們不能僅僅考慮是經(jīng)過障礙物拐點的問題（例如由OABCO路徑的計算)，也應該考慮經(jīng)過路徑中的目標點處轉彎的問題，這是簡單的線圓結構就不能解決這種問題，我們在拐點與途中目標點處采用最小轉彎半徑的形式，使機器人能夠沿直線通過途中的目標點，然后建立優(yōu)化模型對此問題進行優(yōu)化，

6、最終求得最短路徑。2、問題二中涉與到機器人的速度問題，這樣就不能以最短路徑來進行計算，因為拐彎速度與直線速度不一樣，這時就需要在加入速度因素，來求得最佳結果。三模型假設1 假設機器人能夠抽象成點來處理。2 假設機器人在直線上或弧上均勻速行走。四 符號說明符號符號含義L出發(fā)點到目標點的路徑長度r轉彎半徑R經(jīng)過障礙物圓2處的轉彎半徑五 模型的建立與求解我們?nèi)菀椎弥?，起點到目標點無論中間障礙物有多少，最短路徑都應該是若干個線圓結構組成。在本題中存在障礙物的狀況，我們易知，在求兩點之間的最短路徑中的拐彎半徑我們應該按照最小的轉彎半徑來計算才能達到最優(yōu)，所以我們理解為在拐點處的危險區(qū)域是一個半徑為10的

7、圓弧。以下圖為例，1） 點圓模型 如上圖，設A（ QUOTE * MERGEFORMAT 錯誤！未找到引用源。為起點，B（ QUOTE * MERGEFORMAT 錯誤！未找到引用源。為目標點，C（ QUOTE * MERGEFORMAT 錯誤！未找到引用源。和D（ QUOTE * MERGEFORMAT 錯誤！未找到引用源。分別為機器人經(jīng)過拐點分別于隔離危險線拐角小圓弧的切點，圓心為O（ QUOTE * MERGEFORMAT 錯誤！未找到引用源。，圓的半徑為r，AB的長度為a，AO的長度為b，BO的長度為c，角度= QUOTE * MERGEFORMAT 錯誤！未找到引用源。, = QUO

8、TE * MERGEFORMAT 錯誤！未找到引用源。, = QUOTE * MERGEFORMAT 錯誤！未找到引用源。，.求A QUOTE * MERGEFORMAT 錯誤！未找到引用源。B的長度，設為L.解法如下：如上圖可得有以下關系：在：在中：所以：從而可得：我們就可以這樣認為，起點到目標點無論中間障礙物有多少，最短路徑都應該是若干個點圓結構所組成。在本題中存在障礙物的狀況，且障礙物在拐點處的危險區(qū)域是一個半徑為10的圓弧，所以結合上述結論，我們易知，求兩點之間的最短路徑中的轉彎半徑我們應該按照最小的轉彎半徑來算才能達到最優(yōu)。2）線圓模型 而對于下圖兩種情況我們不能直接采用線圓的結構來

9、解決，需要做簡單的變換。 情況一（同向）：這里我們依然設圓心坐標分別為和,半徑均為r，這樣我們可以得到：此段路徑就是由兩段狐與兩段直線的組合加圓心距的總長。這樣我們就可以利用1）中的方法，先求A到E，再求D到B,最后減去DE的長度，這樣分兩段就可以求解。同理如果有更多的轉彎，我們同樣可以按照此種方法分解。情況二（反向）： 我們假設兩圓心坐標分別為和,半徑均為r，M點坐標為，那么我們很容易可以求得:M點坐標利用M將圖上分解成兩個線圓結構，利用上述方法進行計算，易得出結果。3）圓心偏移模型在處理路徑中，由于需要使處在路徑上，所以尋找所對應弧的圓心，建立模型如圖所示，E為O1O2的中點，圖中的E為題

10、中的ABC，O1為各點所在弧的圓心，利用LINGO找出使點落在最短路徑上所對應的圓心，利用此圓心為拐點，用上述的方法進行計算。問題一以下給出了機器人到個目標點的可能路徑的最短路徑：如下圖就是機器人由O到目標點的最短路線 1）O到目標點A的最短路徑求解，通過計算，機器人從障礙物5的上方走的最短路徑大于機器人從障礙物5下方走的最優(yōu)路徑，機器人行走的最優(yōu)路線的可能性已經(jīng)列出，附錄中給出兩種方案的求解結果。 最小結果對應的行走路路線乃是黑線所示，就是O到A的最短路徑471.0372。 2）O到目標點B的最短路徑求解，我們在附錄中給出三種路徑的求解過程，分別為：（1）由O路過障礙物5,8到達B，如圖中虛

11、線所示由O路過障礙物6的上端，到7,8最后到達B點，如圖中黑實線所示（3）由O路過障礙物6的下端，到7,8最后到達B點，圖中間隔線所示。附錄中給出三種方案的結果，最終比較得到最短路徑為路徑（2）即圖中黑實線所示路徑長度為869.8523。O到目標點C的最短路徑求解，我們在附錄中給出三種路徑的求解過程，分別為：（1）由O路過障礙物5的上端,3,2,11到達C，黑線所示；（2）由O路過障礙物5的下端，到3,2,11最后到達C點，如圖中虛線所示。 由附錄中給出的結果，最終比較得到最短路徑為路徑（1），圖中黑實線所示，路徑長度為1.0113e+003。4）OABCO的最短路徑求解，通過計算OA,OC,

12、OB，我們?nèi)菀椎贸鯫ABCO的最短路徑如下圖所標，求解過程有兩部分組成，先計算由O到N點的距離，再求N到O點的距離，最終結果為二者之和，結果為2649,6744。問題二設目標函數(shù)為由LINGO可得出所求，最短時間為94.22822，切點坐標（69.80,211.98）（77.75,220.14）圓心（82.14,207.92）。六、模型評價一、模型優(yōu)點 1、模型優(yōu)化后用解析幾何，三角形中各個之間的關系進行求解，精確度較高。2、模型簡單易懂，便于實際檢驗與應用。3、二、模型缺陷 1、此模型適于全局規(guī)劃，獲得精確解卻失去了效率。2、在障礙物較多時，且形狀不規(guī)則時，模型需要進一步改進。 3、在程序設

13、計時，較復雜，需要繁瑣的編輯過程。七、參考文獻1新社 ，高等數(shù)學 ， ： 中國科學技術大學 2009.72啟源，數(shù)學模型，：高等教育，2003.3金星 薛毅 ，優(yōu)化建模與LINGO ，：清華大學，2005年4來福 曾文藝 ，數(shù)學模型與數(shù)學建模， ：師大學 2003.八、附錄附錄一：問題一中用matlab解一 OA長度求解1）%求解一次轉彎所經(jīng)路線總長1 %O：初始點 E:轉彎圓弧圓心 A:到達點 function result=zongchang(O,E,A,r)OE=sqrt(O(1)-E(1)2+(O(2)-E(2)2);AE=sqrt(A(1)-E(1)2+(A(2)-E(2)2);OA

14、=sqrt(O(1)-A(1)2+(O(2)-A(2)2);alpha1=acos(OE2+AE2-OA2)/(2*AE*OE);alpha2=acos(r/AE);alpha3=acos(r/OE);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4為轉彎圓心角result=sqrt(AE2-r2)+sqrt(OE2-r2)+r*alpha4;將（0,0），（80,210），（300，300）代入求得長度為ans = 471.03722 %O：初始點 F:轉彎圓弧圓心 A:到達點 function result=zongchang(O,E,A,r)OE=sqrt

15、(O(1)-F(1)2+(O(2)-F(2)2);AF=sqrt(A(1)-F(1)2+(A(2)-F(2)2);OA=sqrt(O(1)-A(1)2+(O(2)-A(2)2);alpha1=acos(OF2+AF2-OA2)/(2*AF*OF);alpha2=acos(r/AF);alpha3=acos(r/OF);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4為轉彎圓心角result=sqrt(AE2-r2)+sqrt(OE2-r2)+r*alpha4;將（0,0），（230,60），（300，300）代入求得長度為ans = 498.42592）計算OB

16、路徑1%O：初始點 E,F,G,H,D :轉彎圓弧圓心 M,N：為距離中點 B:到達點 function result=zongchang(O,E,F,G,H,D,M,N,B,r)OE=sqrt(O(1)-E(1)2+(O(2)-E(2)2);OF=sqrt(O(1)-F(1)2+(O(2)-F(2)2);EF=sqrt(E(1)-F(1)2+(E(2)-F(2)2);MF=sqrt(M(1)-F(1)2+(M(2)-F(2)2);ME=sqrt(M(1)-E(1)2+(M(2)-E(2)2);MG=sqrt(M(1)-G(1)2+(M(2)-G(2)2);GH=sqrt(G(1)-H(1)2

17、+(G(2)-H(2)2);GN=sqrt(G(1)-N(1)2+(G(2)-N(2)2);MH=sqrt(M(1)-H(1)2+(M(2)-H(2)2);NH=sqrt(N(1)-H(1)2+(N(2)-H(2)2);BN=sqrt(B(1)-N(1)2+(B(2)-N(2)2);DN=sqrt(D(1)-N(1)2+(D(2)-N(2)2);BD=sqrt(B(1)-D(1)2+(B(2)-D(2)2);alpha1=acos(OE2+EF2-OF2)/(2*OE*EF);alpha2=acos(r/OE);alpha3=1.5*pi-alpha1-alpha2;alpha4=acos(E

18、F2+MF2-ME2)/(2*EF*MF);alpha5=acos(r/MF);alpha6=1.5*pi-alpha4-alpha5;alpha7=acos(MG2+GH2-MH2)/(2*MG*GH);alpha8=acos(r/MG);alpha9=1.5*pi-alpha7-alpha8;alpha10=acos(NH2+GH2-GN2)/(2*NH*GH);alpha11=acos(r/NH);alpha12=1.5*pi-alpha10-alpha11;alpha13=acos(BD2+DN2-BN2)/(2*BD*DN);alpha14=acos(r/BD);alpha15=ac

19、os(r/DN);alpha16=2*pi-alpha13-alpha14-alpha15;TS1=sqrt(OE2-r2);TS2=EF;TS3=sqrt(MF2-r2);TS4=GH;TS5=sqrt(NH2-r2);TS6=sqrt(DN2-r2);TS7=sqrt(BD2-r2);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;將

20、0,0,160,300,150,435,220,470,220,530,150,600,185,452.5,175,565,100,700,10)代入可求得ans = 869.85232%O：初始點 E F:轉彎圓弧圓心 B:到達點 function result=zongchang(O,E,F,B,r)OE=sqrt(O(1)-E(1)2+(O(2)-E(2)2);OF=sqrt(O(1)-F(1)2+(O(2)-F(2)2);FE=sqrt(F(1)-E(1)2+(F(2)-E(2)2);FB=sqrt(F(1)-B(1)2+(F(2)-B(2)2);BE=sqrt(B(1)-E(1)2+

21、(B(2)-E(2)2);alpha1=acos(OE2+FE2-OF2)/(2*OE*FE);alpha2=acos(r/OE);alpha3=1.5*pi-alpha1-alpha2;alpha4=acos(FB2+FE2-BE2)/(2*FB*FE);alpha5=acos(r/FB);alpha6=1.5*pi-alpha4-alpha5;TS1=sqrt(OE2-r2);S2W=sqrt(FB2-r2);S1S2hu=r*alpha3;S3W=FES1S3hu=r*alpha6;result=TS1+S2W+S1S2hu+S3W+S1S3hu;將(0,0,230,60,270,680

22、,100,700,10)代入可求的ans = 1.0584e+0033%O：初始點 E,F,G,H,D :轉彎圓弧圓心M,N：為距離中點 B:到達點 function result=zongchang(O,E,F,G,H,M,N,B,r)OE=sqrt(O(1)-E(1)2+(O(2)-E(2)2);OM=sqrt(O(1)-M(1)2+(O(2)-M(2)2);ME=sqrt(M(1)-E(1)2+(M(2)-E(2)2);MF=sqrt(M(1)-F(1)2+(M(2)-F(2)2);FG=sqrt(F(1)-G(1)2+(F(2)-G(2)2);NF=sqrt(N(1)-F(1)2+(N

23、(2)-F(2)2);NG=sqrt(N(1)-G(1)2+(N(2)-G(2)2);MG=sqrt(M(1)-G(1)2+(M(2)-G(2)2);BN=sqrt(B(1)-N(1)2+(B(2)-N(2)2);NH=sqrt(N(1)-H(1)2+(N(2)-H(2)2);BH=sqrt(B(1)-H(1)2+(B(2)-H(2)2);EF=sqrt(E(1)-F(1)2+(E(2)-F(2)2);GH=sqrt(G(1)-H(1)2+(G(2)-H(2)2);alpha1=acos(OE2+ME2-OM2)/(2*OE*ME);alpha2=acos(r/OE);alpha3=acos(

24、r/ME);alpha4=2*pi-alpha1-alpha2-alpha3;alpha5=acos(FG2+MF2-MG2)/(2*FG*MF);alpha6=acos(r/MF);alpha7=1.5*pi-alpha5-alpha6;alpha8=acos(FG2+NG2-NF2)/(2*FG*NG);alpha9=acos(r/NG);alpha10=1.5*pi-alpha8-alpha9;alpha11=acos(NH2+BH2-BN2)/(2*NH*BH);alpha12=acos(r/NH);alpha13=acos(r/BH);alpha14=2*pi-alpha11-alp

25、ha12-alpha13;TS1=sqrt(OE2-r2);S1W=0.5*EF;S2W=0.5*GH;TS2=sqrt(S1W2-r2);TS3=sqrt(S1W2-r2);TS4=FG;TS5=sqrt(S2W2-r2);TS6=sqrt(BN2-r2);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,185,56

26、5,100,700,10)代入可求得ans = 1.2170e+0033）計算OC路徑1%O：初始點 E,F,G,H,D :轉彎圓弧圓心 M,N：為距離中點 C:到達點 function result=zongchang(O,E,F,G,H,D,M,N,C,r,R)OE=sqrt(O(1)-E(1)2+(O(2)-E(2)2);OM=sqrt(O(1)-M(1)2+(O(2)-M(2)2);EM=sqrt(E(1)-M(1)2+(E(2)-M(2)2);MF=sqrt(M(1)-F(1)2+(M(2)-F(2)2);FN=sqrt(F(1)-N(1)2+(F(2)-N(2)2);MN=sqrt

27、(M(1)-N(1)2+(M(2)-N(2)2);GH=sqrt(G(1)-H(1)2+(G(2)-H(2)2);GN=sqrt(G(1)-N(1)2+(G(2)-N(2)2);DH=sqrt(D(1)-H(1)2+(D(2)-H(2)2);NH=sqrt(N(1)-H(1)2+(N(2)-H(2)2);CD=sqrt(C(1)-D(1)2+(C(2)-D(2)2);CH=sqrt(C(1)-H(1)2+(C(2)-H(2)2);GD=sqrt(G(1)-D(1)2+(G(2)-D(2)2);alpha1=acos(OE2+EM2-OM2)/(2*OE*EM);alpha2=acos(r/OE

28、);alpha3=acos(r/EM);alpha4=2*pi-alpha1-alpha2-alpha3;alpha5=acos(FN2+MF2-MN2)/(2*FN*MF);alpha6=acos(r/MF);alpha7=acos(r/FN);alpha8=2*pi-alpha5-alpha6-alpha7;alpha9=acos(GN2+GH2-NH2)/(2*GN*GH);alpha10=acos(R/GN);alpha11=acos(R-r)/GH);alpha12=2*pi-alpha9-alpha10-alpha11;alpha13=acos(GH2+DH2-GD2)/(2*GH

29、*DH);alpha14=pi-alpha11;alpha15=1.5*pi-alpha14-alpha13;alpha16=acos(CD2+DH2-CH2)/(2*CD*DH);alpha17=acos(r/CD);alpha18=1.5*pi-alpha16-alpha17;TS1=sqrt(OE2-r2);TS2=2*sqrt(EM2-r2);TS3=sqrt(FN2-r2);TS7=sqrt(GN2-R2)TS4=sqrt(GH2-(R-r)2);TS5=DH;TS6=sqrt(CD2-r2);S1S1hu=r*alpha4;S1S2hu=r*alpha8;S1S3hu=r*alph

30、a15;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 :轉彎圓弧圓心 N：為距離中點 C:到達點 function result=zongchang(O,E,F,G,H,D,N,C,r,R)OE=

31、sqrt(O(1)-E(1)2+(O(2)-E(2)2);OF=sqrt(O(1)-F(1)2+(O(2)-F(2)2);EF=sqrt(E(1)-F(1)2+(E(2)-F(2)2);EN=sqrt(E(1)-N(1)2+(E(2)-N(2)2);FN=sqrt(F(1)-N(1)2+(F(2)-N(2)2);GH=sqrt(G(1)-H(1)2+(G(2)-H(2)2);GN=sqrt(G(1)-N(1)2+(G(2)-N(2)2);DH=sqrt(D(1)-H(1)2+(D(2)-H(2)2);NH=sqrt(N(1)-H(1)2+(N(2)-H(2)2);CD=sqrt(C(1)-D(

32、1)2+(C(2)-D(2)2);CH=sqrt(C(1)-H(1)2+(C(2)-H(2)2);GD=sqrt(G(1)-D(1)2+(G(2)-D(2)2);alpha1=acos(OE2+EF2-OF2)/(2*OE*EF);alpha2=acos(r/OE);alpha3=1.5*pi-alpha1-alpha2;alpha4=acos(EF2+FN2-EN2)/(2*EF*FN);alpha5=acos(r/FN);alpha6=1.5*pi-alpha4-alpha5;alpha7=acos(GN2+GH2-NH2)/(2*GN*GH);alpha8=acos(R/GN);alph

33、a9=acos(R-r)/GH);alpha10=2*pi-alpha9-alpha7-alpha8;alpha11=acos(GH2+DH2-GD2)/(2*GH*DH);alpha12=pi-alpha11;alpha13=1.5*pi-alpha11-alpha12;alpha14=acos(CD2+DH2-CH2)/(2*CD*DH);alpha15=acos(r/CD);alpha16=1.5*pi-alpha14-alpha15;TS1=sqrt(OE2-r2);TS2=EF;TS3=sqrt(FN2-r2);TS7=sqrt(GN2-R2);TS4=sqrt(GH2-(R-r)2

34、);TS5=DH;TS6=sqrt(CD2-r2);S1S1hu=r*alpha3;S1S2hu=r*alpha6;S1S3hu=r*alpha13;S1S4hu=R*alpha10;S1S5hu=r*alpha16;result=TS1+TS2+TS5+TS6+S1S1hu+S1S2hu+S1S3hu+S1S5hu+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所以應采取2路線3）計算OABCO路徑將此路線分為兩段進行計算

35、之前需要找到可以使ABC落于圓上的圓心坐標使用LINGO軟件進行最優(yōu)化處理輸入Min=sqrt（x-80)2+(y-210)2)+sqrt(x-220)2+(y-530)2);(x-300)2+(y-300)2=100;可得Local optimal solution found. Objective value: 467.6803 Extended solver steps: 5 Total solver iterations: 105 Variable Value Reduced Cost X 290.8834 0.000000 Y 304.1095 0.000000 Row Slack

36、or Surplus Dual Price 1 467.6803 -1.000000 2 0.000000 0.6650490E-01再次輸入Min=sqrt（x-150)2+(y-600)2)+sqrt(x-370)2+(y-680)2);(x-100)2+(y-700)2=100;可得 Local optimal solution found. Objective value: 365.3162 Extended solver steps: 5 Total solver iterations: 133 Variable Value Reduced Cost X 108.2292 0.000

37、000 Y 694.3184 0.000000 Row Slack or Surplus Dual Price 1 365.3162 -1.000000 2 0.000000 0.8527221E-01最后輸入min=sqrt(x-670)2+(y-730)2)+sqrt(x-720)2+(y-600)2);(x-700)2+(y-640)2=100;可得Local optimal solution found. Objective value: 139.2839 Extended solver steps: 5 Total solver iterations: 91 Variable Val

38、ue Reduced Cost X 707.2603 0.000000 Y 633.1233 0.000000 Row Slack or Surplus Dual Price1 139.2839 -1.000000 2 0.000000 0.000000所以取得三個坐標（290.9， 304.1）,(108.23 694.32)(707.26 633.12)第一部分長度輸入% 初始值clear 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;

39、 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-2p1=A(i,1:2); p2=A(i+1,1:2); p3=A(i+2,1:2); p12=norm(p1-p2); p23=norm(p2-p3); p13=norm(p1-p3); alpha3=acos(p122+p232-p132)/(2*

40、p12*p23);if i=1 alpha1=acos(10/p12); L1=p12*sin(alpha1);endif A(i+2,3)=1 alpha2=pi/2; sita=2*pi-alpha1-alpha2-alpha3; L2=p23+10*sita;%外切圓-同側elseif A(i+2,3)=2 alpha2=acos(2*r/p23);%切圓-兩側 sita=2*pi-alpha1-alpha2-alpha3;L2=r*sita+p23*sin(alpha2);else alpha2=acos(r/p23);%點 sita=2*pi-alpha1-alpha2-alpha3

41、; L2=p23*sin(alpha2)+r*sita;end L=L1+L2;L1=L; alpha1=alpha2; i=i+1;endL可得結果L = 1.7691e+003第二部分輸入function result=zongchang(O,E,F,G,H,D,N,C,r,R)OE=sqrt(O(1)-E(1)2+(O(2)-E(2)2);OF=sqrt(O(1)-F(1)2+(O(2)-F(2)2);EF=sqrt(E(1)-F(1)2+(E(2)-F(2)2);EN=sqrt(E(1)-N(1)2+(E(2)-N(2)2);FN=sqrt(F(1)-N(1)2+(F(2)-N(2)2

42、);GH=sqrt(G(1)-H(1)2+(G(2)-H(2)2);GN=sqrt(G(1)-N(1)2+(G(2)-N(2)2);DH=sqrt(D(1)-H(1)2+(D(2)-H(2)2);NH=sqrt(N(1)-H(1)2+(N(2)-H(2)2);CD=sqrt(C(1)-D(1)2+(C(2)-D(2)2);CH=sqrt(C(1)-H(1)2+(C(2)-H(2)2);GD=sqrt(G(1)-D(1)2+(G(2)-D(2)2);alpha1=acos(OE2+EF2-OF2)/(2*OE*EF);alpha2=acos(r/OE);alpha3=1.5*pi-alpha1-

43、alpha2;alpha4=acos(EF2+FN2-EN2)/(2*EF*FN);alpha5=acos(r/FN);alpha6=1.5*pi-alpha4-alpha5;alpha7=acos(GN2+GH2-NH2)/(2*GN*GH);alpha8=acos(R/GN);alpha9=acos(R-r)/GH);alpha10=2*pi-alpha9-alpha7-alpha8;alpha11=acos(GH2+DH2-GD2)/(2*GH*DH);alpha12=pi-alpha11;alpha13=1.5*pi-alpha11-alpha12;alpha14=acos(CD2+DH2-CH2)/(2*CD*DH);alpha15=acos(r/CD);alpha16=1.5*pi-alpha14-alpha15;TS1=sqrt(OE2-r2);TS2=EF;TS3=sqrt(FN2-r2);TS7=sqrt(GN2-R2);TS4=sqrt(GH2-(R-r)2);TS5=DH;TS6=sqrt(CD2-r2);S1S1hu=r*alpha3;S1S2hu=r*al