建模机器人避路障问题

1、建模机器人避路障问题机器人避障问题摘要：本文根据题目要求，主要研究了在一个区域内有障碍物的最短路径问题。依题意我们可以认为最短路径一定是由线和最小圆弧组成，圆心在障碍物的顶点。对于问题一首先讨论由egUA的距离，为了到达目标点，我们建立了圆线模型。将路线分为两部分：一部分是平面上的自然最短路径(即直线段)，另一部分是限定区域的部分边界的半径至少十个单位以外的圆弧，得到其路径长度为L旧产4c2r，并用MATLAB序解得最短路径471.0372对于egUb的距离问题，为了到达目标点，我们需要建立圆与点圆模型，其中由于圆与圆之间的不同的位置关系，又可以分为同向相切与异向相切，同向相切时LJ：r2Jc

2、2r2rir2QQ,异向相切时L4br2Ccr2r1r2”(号)2r2。由MATLAB序解得最短路径869.8523。对于egUC,与前者的区别是障碍物大圆视为半径较大的转折弧，为了到达目标点，依旧建立圆圆结构与线圆结构模型，经MATLAB序解得最短路径为1011.3。对于OABCO路径问题，除了用了上述提到的圆圆，线圆结构外，还建立了圆心偏移的模型(即点ABCS相对应的弧上)，A点偏以后的坐标为(290.9,304.1),B点偏以后的坐标为(108.23,694.32),C点偏以后的坐标为(707.26,633.12),将OABCO为两部分，一部分为OABCN730,520)的距离，另一部分

3、为由N回到O的距离，两部分结果之和即为所求路径。OABCN距离1.7691e+003,N至|劭880.7744,总长为2649,6744对于问题二，我们将路线问题转化为规划问题，求的最短时间，目标函数为TACBDrV0V1由LINGOt最短时间为94.22822,切点坐标(69.80,211.98)(77.75,220.14)圆心(82.14,207.92)。关键词：最短路径最优化模型避障路径规划问题线圆结构一问题重述机器人从原点OB发且他只能在图中所给出的800*800正方平面场景范围内活动。且平面场景范围内的12个不同形状的区域是机器人不能与之发生碰撞的障碍物。在平面场景中，障碍物外指定一

4、点为机器人要到达的目标点(要求目标点与障碍物的距离至少超过10个单位)。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则机器人将无法完成行走。机器人直线行走的最大速度为v05个单位/秒。机器人转弯时，最大转弯速度为vv()一然丁，其中是转弯半径。1e请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对4个点0(0,0),A(300,300)

5、,B(100,700),C(700,640),具体计算：(1)机器人从0(0,0)出发，0-A、C-B、0-C?口0A-B-C-O勺最短路径。(2)机器人从0(0,0)出发，到达刖勺最短时间路径800X800平面场景图二问题分析i、问题一中要求定点机器人按照一定的行走规则绕过障碍物到达目标点的最短路径，由于机器人不能折线拐弯，所以拐弯处必然是一圆弧，我们采用线圆结构的方法建立模型，用这种方法寻找可能的最短路径，然后采用穷举法列出o到目标点的最短路径。这其中我们不能仅仅考虑是经过障碍物拐点的问题（例如由OABCO路径的计算），也应该考虑经过路径中的目标点处转弯的问题，这是简单的线圆结构就不能解决

6、这种问题，我们在拐点及途中目标点处采用最小转弯半径的形式，使机器人能够沿直线通过途中的目标点，然后建立优化模型对此问题进行优化，最终求得最短路径。2、问题二中涉及到机器人的速度问题，这样就不能以最短路径来进行计算,因为拐弯速度与直线速度不相同，这时就需要在加入速度因素，来求得最佳结果。三模型假设1假设机器人能够抽象成点来处理。2假设机器人在直线上或弧上均匀速行走四符号说明7H勺符号含义L出发点到目标点的路径长度r转弯半径R经过障碍物圆2处的转弯半径五模型的建立与求解我们容易得知，起点到目标点无论中间障碍物有多少，最短路径都应该是若干个线圆结构组成。在本题中存在障碍物的状况，我们易知，在求两点之

7、间的最短路径中的拐弯半径我们应该按照最小的转弯半径来计算才能达到最优，所以我们理解为在拐点处的危险区域是一个半径为10的圆弧。以下图为例,1）点圆模型如上图，设A（错误！未找到引用源。为起点，B（错误！未找到引用源。为目标点，C（错误！未找到引用源。和D（错误！未找到引用源。分别为机器人经过拐点分别于隔离危险线拐角小圆弧的切点，圆心为0（错误！未找到引用源。，圆的半径为r,AB的长度为a,AO的长度为b,B0的长度为c,角度AOB=f误！未找到引用源。，AOC=错误！未找到引用源。，BOD=错误！未找到引用源。，COD.求A错误！未找到引用源。B的长度，设为L.解法如下：如上图可得有以下关系：

8、a(xxi)&yi)b(xxi)2ayi)2c.(X5x2)2(ysy2)2在AOB中：arccosE2bc2-)在RtAOC：r=arccos-b在RtAOC中：rarccos-c所以：2从而可得：L后r2vc2r2r我们就可以这样认为，起点到目标点无论中间障碍物有多少，最短路径都应该是若干个点圆结构所组成。在本题中存在障碍物的状况，且障碍物在拐点处的危险区域是一个半径为10的圆弧，所以结合上述结论，我们易知，求两点之间的最短路径中的转弯半径我们应该按照最小的转弯半径来算才能达到最优。2)线圆模型而对于下图两种情况我们不能直接采用线圆的结构来解决，需要做简单的变换。情况一(同向)：这

9、里我们依然设圆心坐标分别为O(xi,yi)和O(x2,y2),半径均为r,这样我们可以得到：此段路径就是由两段狐与两段直线的组合加圆心距的总长。这样我们就可以利用1）中的方法，先求A到E,再求D到B,最后减去DE的长度，这样分两段就可以求解。同理如果有更多的转弯，我们同样可以按照此种方法分解。情况二（反向）：我们假设两圆心坐标分别为O（xi,yi）和O（X2,y2）,半径均为r,M点坐标为（X3,y3）,那么我们很容易可以求得：M点坐标X3y3yiy223）圆心偏移模型在处理OABC路径中，由于需要使ABC处在路径上，所以寻找所对应弧的圆心，建立模型如图所示，E为O1O2勺中点，图中的E为题中

10、的ABCO1为各点所在弧的圆心，利用LINGO找出使点落在最短路径上所对应的圆心，利用此圆心为拐点，用上述的方法进行计算。问题一一、以下给出了机器人到个目标点的可能路径的最短路径：如下图就是机器人由O到目标点的最短路线1 )O到目标点A的最短路径求解，通过计算，机器人从障碍物5的上方走的最短路径大于机器人从障碍物5下方走的最优路径，机器人行走的最优路线的可能性已经列出，附录中给出两种方案的求解结果。最小结果对应的行走路路线乃是黑线所示，就是O到A的最短路径471.037208006004002002 )O到目标点B的最短路径求解，我们在附录中给出三种路径的求解过程,分别为：(1)由O路过障碍物

11、5,8到达B,如图中虚线所示(2)由O路过障碍物6的上端，至U7,8最后到达B点，如图中黑实线所示(3)由O路过障碍物6的下端，至U7,8最后到达B点，图中间隔线所示。附录中给出三种方案的结果，最终比较得到最短路径为路径(2)即图中黑实线所示路径长度为869.8523o4006008003） O到目标点C的最短路径求解，我们在附录中给出三种路径的求解过程，分别为：（1）由O路过障碍物5的上端,3,2,11到达C,黑线所示；（2）由O路过障碍物5的下端，至U3,2,11最后到达C点，如图中虚线所示。由附录中给出的结果，最终比较得到最短路径为路径（1）,图中黑实线所示，路彳长度为1.0113e+0

12、03o4） OABCO最短路径求解，通过计算OA,OC,OB我们容易得出OABCO最短路径如下图所标，求解过程有两部分组成，先计算由OiUN点的距离,再求NSJO点的距离，最终结果为二者之和，结果为2649,6744800问题二ACBDrT设目标函数为V0ViDXi,yi,C(X2,y2),O(X0,y。)0x180;0y1240;80x2300;210y2300;v05;v1V000.1*2eBD.x2y2;AC.300x22300y22;CBOAOBOAOAB2acosacosacos由LINGO可得出所求，最短时间为94.22822,切点坐标(69.80,211.98)(77.75,22

13、0.14)圆心(82.14,207.92)。六、模型评价一、模型优点1 、模型优化后用解析几何，三角形中各个之间的关系进行求解，精确度较Mi。2、模型简单易懂，便于实际检验及应用。3、二、模型缺陷1 、此模型适于全局规划，获得精确解却失去了效率。2、在障碍物较多时，且形状不规则时，模型需要进一步改进。3、在程序设计时，较复杂，需要繁琐的编辑过程。七、参考文献11韩新社，高等数学，合肥：中国科学技术大学出版社2009.72姜启源，数学模型M，北京：高等教育出版社，2003.【3】谢金星薛毅，优化建模与LINGO，北京：清华大学出版社，2005年【4】刘来福曾文艺，数学模型与数学建模，北京：北京师

14、范大学出版社2003.八、附录附录一：问题一中用matlab解一OA长度求解1)就解一次转弯所经路线总长1 %O初始点E:转弯圆弧圆心A:到达点functionresult=zongchang(O,E,A,r)OE=sqrt(O(1)-E(1)A2+(O(2)-E(2)A2);AE=sqrt(A(1)-E(1)A2+(A(2)-E(2)A2);OA=sqrt(O(1)-A(1)A2+(O(2)-A(2)A2);alpha1=acos(OEA2+AEA2-0AA2)/(2*AE*OE);alpha2=acos(r/AE);alpha3=acos(r/OE);alpha4=2*pi-alpha1-

15、alpha2-alpha3;%alpha4为转弯圆心角result=sqrt(AEA2-rA2)+sqrt(OEA2-rA2)+r*alpha4;将(0,0),(80,210),(300,300)代入求得长度为ans=471.03722 %O初始点F:转弯圆弧圆心A:到达点functionresult=zongchang(O,E,A,r)OE=sqrt(O(1)-F(1)A2+(O(2)-F(2)A2);AF=sqrt(A(1)-F(1)A2+(A(2)-F(2)A2);OA=sqrt(O(1)-A(1)A2+(O(2)-A(2)A2);alpha1=acos(OFA2+AFA2-OAA2)/

16、(2*AF*OF);alpha2=acos(r/AF);alpha3=acos(r/OF);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4为转弯圆心角result=sqrt(AEA2-rA2)+sqrt(OEA2-rA2)+r*alpha4;将(0,0),(230,60),(300,300)代入求得长度为ans=498.42592)计算OB路径1%O初始点E,F,G,H,D:转弯圆弧圆心M,N:为距离中点B:到达点functionresult=zongchang(O,E,F,G,H,D,M,N,B,r)OE=sqrt(O(1)-E(1)A2+(O(2)-E(2

17、)A2);OF=sqrt(O(1)-F(1)A2+(O(2)-F(2)A2);EF=sqrt(E(1)-F(1)A2+(E(2)-F(2)A2);MF=sqrt(M(1)-F(1)A2+(M(2)-F(2)A2);ME=sqrt(M(1)-E(1)A2+(M(2)-E(2)A2);MG=sqrt(M(1)-G(1)A2+(M(2)-G(2)A2);GH=sqrt(G(1)-H(1)A2+(G(2)-H(2)A2);GN=sqrt(G(1)-N(1)A2+(G(2)-N(2)A2);MH=sqrt(M(1)-H(1)A2+(M(2)-H(2)A2);NH=sqrt(N(1)-H(1)A2+(N(

18、2)-H(2)A2);BN=sqrt(B(1)-N(1)A2+(B(2)-N(2)A2);DN=sqrt(D(1)-N(1)A2+(D(2)-N(2)A2);BD=sqrt(B(1)-D(1)A2+(B(2)-D(2)A2);alpha1=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+GH

19、A2-MHA2)/(2*MG*GH);alpha8=acos(r/MG);alpha9=1.5*pi-alpha7-alpha8;alpha10=acos(NHA2+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=sq

20、rt(MFA2-rA2);TS4=GH;TS5=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,70

21、0,10)代入可求得ans=869.85232%0初始点EF:转弯圆弧圆心B:到达点functionresult=zongchang(O,E,F,B,r)OE=sqrt(O(1)-E(1)A2+(O(2)-E(2)A2);OF=sqrt(O(1)-F(1)A2+(O(2)-F(2)A2);FE=sqrt(F(1)-E(1)A2+(F(2)-E(2)A2);FB=sqrt(F(1)-B(1)A2+(F(2)-B(2)A2);BE=sqrt(B(1)-E(1)A2+(B(2)-E(2)A2);alpha1=acos(OEA2+FEA2-OFA2)/(2*OE*FE);alpha2=acos(r/O

22、E);alpha3=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:转弯圆弧圆心M,

23、N:为距离中点B:到达点functionresult=zongchang(O,E,F,G,H,M,N,B,r)OE=sqrt(O(1)-E(1)A2+(O(2)-E(2)A2);OM=sqrt(O(1)-M(1)A2+(O(2)-M(2)A2);ME=sqrt(M(1)-E(1)A2+(M(2)-E(2)A2);MF=sqrt(M(1)-F(1)A2+(M(2)-F(2)A2);FG=sqrt(F(1)-G(1)A2+(F(2)-G(2)A2);NF=sqrt(N(1)-F(1)A2+(N(2)-F(2)A2);NG=sqrt(N(1)-G(1)A2+(N(2)-G(2)A2);MG=sqrt

24、(M(1)-G(1)A2+(M(2)-G(2)A2);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(1)-H(1)A2+(B(2)-H(2)A2);EF=sqrt(E(1)-F(1)A2+(E(2)-F(2)A2);GH=sqrt(G(1)-H(1)A2+(G(2)-H(2)A2);alpha1=acos(OEA2+MEA2-OMA2)/(2*OE*ME);alpha2=acos(r/OE);alpha3=acos(r/ME);alpha4=2*pi-alpha1-alpha2-alp

25、ha3;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-alpha13;TS1=sqrt(OEA2

26、-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,185,565,100,700,10)代入可

27、求得ans=1.2170e+0033)计算OC路径1%O初始点E,F,G,H,D:转弯圆弧圆心M,N:为距离中点C:到达点functionresult=zongchang(O,E,F,G,H,D,M,N,C,r,R)OE=sqrt(O(1)-E(1)A2+(O(2)-E(2)A2);OM=sqrt(O(1)-M(1)A2+(O(2)-M(2)A2);EM=sqrt(E(1)-M(1)A2+(E(2)-M(2)A2);MF=sqrt(M(1)-F(1)A2+(M(2)-F(2)A2);FN=sqrt(F(1)-N(1)A2+(F(2)-N(2)A2);MN=sqrt(M(1)-N(1)A2+(M

28、(2)-N(2)A2);GH=sqrt(G(1)-H(1)A2+(G(2)-H(2)A2);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(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);alpha1=acos(OEA2+EMA2-OMA2)/(2*OE*EM);alpha2=acos(

29、r/OE);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-alpha9-alpha10-alpha11;alpha13=acos(GHA2+DHA

30、2-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(OEA2-rA2);TS2=2*sqrt(EMA2-rA2);TS3=sqrt(FNA2-rA2);TS7=sqrt(GNA2-RA2)TS4=sqrt(GHA2-(R-r)A2);TS5=DH;TS6=sqrt(CDA2-rA2);S1S1hu=r*alpha4;S

31、1S2hu=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:转弯圆弧圆心N:为距离中点C:到达点functionresult=zongchang(O,E,

32、F,G,H,D,N,C,r,R)OE=sqrt(O(1)-E(1)A2+(O(2)-E(2)A2);OF=sqrt(O(1)-F(1)A2+(O(2)-F(2)A2);EF=sqrt(E(1)-F(1)A2+(E(2)-F(2)A2);EN=sqrt(E(1)-N(1)A2+(E(2)-N(2)A2);FN=sqrt(F(1)-N(1)A2+(F(2)-N(2)A2);GH=sqrt(G(1)-H(1)A2+(G(2)-H(2)A2);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)

33、-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);alpha1=acos(OEA2+EFA2-OFA2)/(2*OE*EF);alpha2=acos(r/OE);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=a

34、cos(GNA2+GHA2-NHA2)/(2*GN*GH);alpha8=acos(R/GN);alpha9=acos(R-r)/GH);alpha10=2*pi-alpha9-alpha7-alpha8;alpha11=acos(GHA2+DHA2-GDA2)/(2*GH*DH);alpha12=pi-alpha11;alpha13=1.5*pi-alpha11-alpha12;alpha14=acos(CDA2+DHA2-CHA2)/(2*CD*DH);alpha15=acos(r/CD);alpha16=1.5*pi-alpha14-alpha15;TS1=sqrt(OEA2-rA2);

35、TS2=EF;TS3=sqrt(FNA2-rA2);TS7=sqrt(GNA2-RA2);TS4=sqrt(GHA2-(R-r)A2);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+TS4+S1S4hu+TS3将(0,0,80,210,400,330,550,450,720,520,720,600,416.67,343.33

36、,700,640,10,80)代入可求得ans=1.0113e+003所以应采取2路线3)计算OABC舔径将此路线分为两段进行计算之前需要找到可以使ABC落于圆上的圆心坐标使用LINGO软件进行最优化处理输入Min=sqrt(x-80)A2+(y-210)A2)+sqrt(x-220)A2+(y-530)A2);(x-300)A2+(y-300)A2=100;可得Localoptimalsolutionfound.Objectivevalue:467.6803Extendedsolversteps:5Totalsolveriterations:105VariableValueReducedCo

37、stX290.88340.000000Y304.10950.000000RowSlackorSurplusDualPrice1467.6803-1.00000020.0000000.6650490E-01再次输入Min=sqrt(x-150)A2+(y-600)A2)+sqrt(x-370)A2+(y-680)A2);(x-100)A2+(y-700)A2=100;可得Localoptimalsolutionfound.Objectivevalue:Extendedsolversteps:Totalsolveriterations:VariableValueCostX0.000000Y0.00

38、0000RowSlackPrice1-1.00000020.8527221E-01最后输入min=sqrt(x-670)A2+(y-730)A2)+；(x-700)A2+(y-640)A2=100;可得Localoptimalsolutionfound.Objectivevalue:Extendedsolversteps:365.31625133Reduced108.2292694.3184orSurplusDual365.31620.000000sqrt(x-720)A2+(y-600)A2)139.28395Totalsolveriterations:91VariableValueRedu

39、cedCostX707.26030.000000Y633.12330.000000RowSlackorSurplusDualPrice1139.2839-1.00000020.0000000.000000所以取得三个坐标(290.9,304.1),(108.23694.32)(707.26633.12)第一部分长度输入%初始值clearallclcA=000;802100;290.9304.12;2205301;1506002;108.23694.321;2706801;3706802;4306801;5407302;6707301;707.26633.122;7206002;7205303;

40、%230600;%4101001;%5002002;%7205202;%7206001;%7006403;r=10;m,n=size(A);i=1;whilei<=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(p12A2+p23A2-p13A2)/(2*p12*p23);ifi=1alpha1=acos(10/p12);L1=p12*sin(alpha1);endifA(i+2,3)=1alpha2=pi/2;sita=2*pi-

41、alpha1-alpha2-alpha3;L2=p23+10*sita;%#切圆-同侧elseifA(i+2,3)=2alpha2=acos(2*r/p23);%内切圆-两侧sita=2*pi-alpha1-alpha2-alpha3;L2=r*sita+p23*sin(alpha2);elsealpha2=acos(r/p23);%点sita=2*pi-alpha1-alpha2-alpha3;L2=p23*sin(alpha2)+r*sita;endL=L1+L2;L1=L;alpha1=alpha2;i=i+1;endL可得结果L=1.7691e+003第二部分输入functionres

42、ult=zongchang(O,E,F,G,H,D,N,C,r,R)OE=sqrt(O(1)-E(1)A2+(O(2)-E(2)A2);OF=sqrt(O(1)-F(1)A2+(O(2)-F(2)A2);EF=sqrt(E(1)-F(1)A2+(E(2)-F(2)A2);EN=sqrt(E(1)-N(1)A2+(E(2)-N(2)A2);FN=sqrt(F(1)-N(1)A2+(F(2)-N(2)A2);GH=sqrt(G(1)-H(1)A2+(G(2)-H(2)A2);GN=sqrt(G(1)-N(1)A2+(G(2)-N(2)A2);DH=sqrt(D(1)-H(1)A2+(D(2)-H(

43、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);alpha1=acos(OEA2+EFA2-OFA2)/(2*OE*EF);alpha2=acos(r/OE);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(GHA2+DHA2-GDA2)/(2*GH*DH);alpha12=pi-alpha11;alpha13=1.5*pi-alpha11-alpha12;alpha14=acos(CDA2+DHA2-CHA2)/(2*CD*DH);alpha15=acos(r