全国大学生数学建模竞赛承诺书.doc

2012高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从a/b/c/d中选择一项填写）： d 我们的参赛报名号为（如果赛区设置报名号的话）： 20122118 所属学校（请填写完整的全名）： 常州纺织服装职业技术学院 参赛队员 (打印并签名) ：1. 王铭 2. 赵一名 3. 陈清 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 9 月 9 日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：机器人行走避障优化模型一：摘要随着科技不断的进步，人类能造出的机器人也越来越智能，未来机器人会在建筑、勘探、医学、生产等多个领域中发挥重要作用，因此如何解决机器人在行走中的避障问题显得尤为重要。本文主要研究了机器人行走避障最短路径和最短时间路径的问题。问题中给定区域中存在十二个不同形状、不同尺寸的障碍物，且最终路线不能碰到障碍物周围10个单位的界定区域，在对各种行走路径分析中，我们发现虽然路线有无数条，但是我们用穷举法给出若干种可能存在最短路径的方案并进行比对。在对oa最短路径的求解中，我们利用了机械绘图solidworks软件仿真模拟结合手工计算得到可能存在的最短路径，在对oa最短路径的分析中，我们有了一个猜想并进行证明，即通过证明具有圆形限定区域的最短路径是由两部分组成：一部分是平面上的自然最短路径（即直线段），另一部分是限定区域的部分边界，这两部分是相切的，互相连接的。依据这个结果，我们可以认为最短路径一定是由线和圆弧所组成的，因此我们建立了线圆结构，这样无论路径多么复杂，我们都可以将路径划分为若干个这种线圆结构来求解。同理，我们对于ob，oc都采用了先利用solidworks软件进行仿真模拟得出最短路径方案的方法，特别是由o出发经过a、b、c的再到达o点的状况，我们采用分段方式求解，即使用oa最短路径、ab最短路径、bc最短路径、co最短路径所组成的，然后建立了最优化模型对总体求解。最后，为了更好地验证solidworks软件仿真模拟所得出的结论，我们采用了lingo12软件对路径的方程进行了最值的求解，最终lingo12软件的操作结果很好地验证了之前所得到各种结论。在第一问结论的基础上，我们先针对第二问列出目标函数，再次利用solidworks软件对目标函数的所有自变量给出了合理的范围，最后用ling12计算出目标函数的最值，即得到了最短时间路径的模型。最终得到的结论总结如下：问题一，我们使用穷举法把所有可能路径的最短路径用机械绘图软件solidworks2010表示出来，读出这若干个线圆组合的具体长度并制出表格，并使用lingo9进行编程验证，最后得出：oa最短路径长度为：471.0375 ob最短路径长度为：853.6995 oc最短路径长度为：1088.1969 oabco最短路径长度为：2730.0075问题二，我们方案都进行优化，求得最终结果：oa最短时间为：94.20804s关键字：避障最短，时间最短，线圆组合，solidworks2010，lingo9二：问题重述图1是一个800800的平面场景图，在原点o(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：编号障碍物名称左下顶点坐标其它特性描述1正方形(300, 400)边长2002圆形圆心坐标(550, 450)，半径703平行四边形(360, 240)底边长140，左上顶点坐标(400, 330)4三角形(280, 100)上顶点坐标(345, 210)，右下顶点坐标(410, 100)5正方形(80, 60)边长1506三角形(60, 300)上顶点坐标(150, 435)，右下顶点坐标(235, 300)7长方形(0, 470)长220，宽608平行四边形(150, 600)底边长90，左上顶点坐标(180, 680)9长方形(370, 680)长60，宽12010正方形(540, 600)边长13011正方形(640, 520)边长8012长方形(500, 140)长300，宽60在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中4个点o(0, 0)，a(300, 300)，b(100, 700)，c(700, 640)，具体计算：(1) 机器人从o(0, 0)出发，oa、ob、oc和oabco的最短路径。(2) 机器人从o (0, 0)出发，到达a的最短时间路径。注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。图1 800800平面场景图三：问题分析 问题要求我们建立数学模型，找出从区域中一点到另一点的避障最短路径和最短时间路径。考虑最短路径时规划出了oa的四种极限位置(圆弧最长和圆弧最短)的路径，但由于题目中12个障碍物周围10个单位是危险区域，不能靠近，这些因素将对我们接下来考虑更为复杂的ob、oc的路径造成很大困难，所以我们画出平行于障碍物边的线段和半径为10的圆弧（圆心各为障碍物的顶角），使用线段和圆弧限制出这些区域，这样问题就得以简化。对于最短避障路径问题，我们都知道两点之间直线最短，由于有障碍物的存在，我们只能找出最贴近两点连线的路径，在路径的选取时我们采用了穷举法。具体方法为使用solidworks2010软件模拟拉绳法寻找可能的最短路径（假设平面上有a、b两点，我们将a、b两点以橡皮筋连接，我们从旁边推入一棱为圆弧状的立方体，则橡皮筋必被撑拉，那么此橡皮筋的路径为一条可能的最短路径），为了验证结果的准确性，我们用lingo12软件对列出的目标函数进行最值求解，最终发现lingo12的计算结果很好的验证了之前所得到的结论。对最短时间路径问题，由于机器人在圆弧上的速度随着圆弧的半径变化而变化，则我们猜想最短时间路径可能不是最短避障路径。我们也找到一个不为10的半径，其总耗时比最短避障路径用时短验证了我们的猜想。所以我们采用lingo12软件并给出相关约束条件，建立最优化数学模型。四：模型假设1、 假设障碍物为规则图形。2、 假设机器人为质点。3、 假设机器人速度为瞬间变化，不考虑加速度。五：模型的建立问题一：5.1：方法我们采用solidworks人工模拟拉绳找出第一问中oa的所有存在可能的一些路径，并对数据进行筛选分析，找出最有可能的最短路径，然后通过对oa最短路径的求解规律分析后建立猜想并证明猜想，最终验证我们的路径，然后推广到ob，oc，oabco。5.1.1：oa我们通过solidworks 2010软件模拟出o点到a点可能的路径，然后从中选取了四种极限的方案，如下图所示： a方案 b方案 c方案 d方案 （注：图中蓝色路径即为仿真模拟得到的机器人行走路径）数据见如下表所示：o点到a点的四种方案方案名线段长弧度线段长直线总长度总弧长总长a方案41.891681.15（246.86）92.2161134.1077349.6367483.7444b方案224.499451.86237.4868461.98629.0513471.0375c方案138.336779.57（153.09）158.5467296.8834212.6049509.4883d方案237.486863.82249.7999487.286711.1387498.4254（注：线段长和弧度数据由solidworks2010软件直接读出，弧长由matlab软件计算得出。）四种方案分别走正方形的上方和下方，每路均为圆弧最长和圆弧最短两种方案，通过数据比对，不难发现在同一路径中，圆弧最长路线的总路程要比圆弧最短的总路程要长，即a方案比b 方案长，c方案比d方案长。所以我们猜想o到a最短路线必须满足圆弧最短，即当半径r=10的时候，为我们所要找的最短路径方案。通过上述分析，我们做出一个猜想：对于任意给定两点ab，在ab间存在一不可逾越的圆形障碍物，有如下结论：a到b最短路径为am+nb+ 证明如下： 由切线定理与三角形全等知识易证p点位中点 设半圆半径为r，设 则cn=，则弧长=，令cn= =y=对y进行求导，得cn +nb即证：最短避障路径必由线段和最小半径构成的圆弧组成。5.1.2：ob对于o b，我们的中心思想与oa相同，可以选择从障碍物5上方和下方分两条路径，其中路径均由solidworks2010软件得到。因为ob之间障碍物不是太多，我们并不需要选取公共点来筛选掉相关方案，直接使用穷举法我们共得6种可能存在最短路径的方案，并通过solidworks2010软件绘制出了所有路径图形（见附录2）。o b的c方案（最短路径）路径图 （注：图中蓝色路径即为仿真模拟得到的机器人行走路径）方案名总线段长总弧长总长方案c812.000141.6994853.6995最短路径由以下各数据构成：（注：其他方案相关详细数据见附录3。）5.1.3：oc对于到，我们我们也找出了多种可能路径，但由于o到c中间障碍物过多，所以我们采用选取节点的方法分段分析：p点p点 p点p点 p点 （注：p点即为障碍物11右边界定线与右下角界定圆弧的交点，图中蓝色路径即为机器人行走路径）o到p点由若干个线圆组合，但p点是一个公共的中间点，所以我们只需比较各种方案中o到p点的路径长度即可筛选出最优方案，其他方案其他公共点筛选方法同理，最终我们找出一条最短路径，如下图所示：（注：图中蓝色路径即为仿真模拟得到的机器人行走路径）其他相关路径方案见附录2。最短路径由以下各数据构成：方案名总线段长总弧长总长方案a1066.322421.87251088.1949（注：其他方案相关详细数据见附录3。） 5.1.4：oabco对于o abco，这种路径很特殊，因为我们必须途径a、b、c三个中间点才能到达目标点，我们采用了分段的方式一一求解，分别求出oa，ab，bc，co最短路径的方案，结合起来即为oabco的最短路径方案。在寻找oa最短路径时，我们直接引用了前面的结论，但在寻找的最短路径时发现了问题。因为题目规定机器人在a点不能直接拐弯，也需要走圆弧，所以我们假设在a、b、c三个中间点附近各有一可以旋转的半径为10的圆环，且abc三点均在圆环上。为了更好地解决特殊路径中的最短路径问题，我们猜想可固定该圆环。下面我们来证实此猜想。猜想：如果一个圆环可以绕着环上一个定点转动，那么过圆环外两定点连接一根绳子，并以该圆环为支撑拉紧绳子，达到平衡状态时，圆心与该顶点以及两条切线的延长线的交点共线。 证明：如图4.31所示，e点就是圆环上的一个顶点，acdb就是拉紧的绳子，就是切线ac和bd的延长线的交点，证明、e、三点共线。我们可以用力学的知识进行证明，因为是拉紧的绳子，所以两边的绳子拉力相等，设为，它们的合力设为，定点对圆环的作用力设为。那么由几何学的知识我们可以知道一定与共线，而又由力的平衡条件可知：=-即与共线。所以我们可以说：oabco最短路径方案必然满足这样一条件： 即a、b、c均为转弯圆弧的中间点。据此，我们结合之前oa、ab、bc、co中各最短路径方案，最终给出最短路径，如下图所示：（其中ab、bc中各种路径方案见附件2，各种方案的具体数据见附件3）。（注：图中蓝色路径即为仿真模拟得到的机器人行走路径）5.2验证5.2.1 oa为了说明我们数据的严谨性，我们采用lingo12软件验证我们的模型。设变量如下： 圆心坐标（x，290-x），圆弧的角度为y，o点到a点的总距离为s：有s=需求o到a的最短路径，即为求解s的最小值。通过分析路径的极限形式，可得到约束条件：，51.86通过lingo软件编程（程序见附录4）求解得：x=80 y=51.86 即圆心坐标（80，,210） 圆弧角度为51.86lingo软件与solidworks的出的数据对比如下表所示：方法圆心坐标圆弧角度弧长solidworks(80,210)51.869.05lingo(80,210)51.869.051278误差几乎为0，可见lingo软件很好地验证了之前的最短路径方案。由solidworks2010软件结合手工计算所得的模型为最优模型，总体很好。5.2.2 ob 由于ob、oc、oabco的最短路径都比较复杂，我们不在一一对其验证过程进行叙述，仅对ob的最短路径验证过程进行详细描述。我们给出如下假设：第一个圆心坐标和其对应的圆心角，第二个圆心坐标和其对应的圆心角，第三个圆心坐标和其对应的圆心角，第四个圆心坐标和其对应的圆心角，第五个圆心坐标和其对应的圆心角，故ob的总距离l=求l的最小值，即为o到b路径最小值。通过分析路径的极限形式可得到约束条件如下： ， ， ， ， ， ，通过lingo12软件编程（程序见附录4）求解得：第一个圆心坐标和其对应的圆心角24.25第二个圆心坐标和其对应的圆心角44.55第三个圆心坐标和其对应的圆心角78.24第四个圆心坐标和其对应的圆心角56.66第五个圆心坐标和其对应的圆心角35.22lingo软件与solidworks的出的数据对比如下表所示：solidworks第一圆第二圆第三圆第四圆第五圆圆心坐标圆弧角度24.2544.5578.2456.6635.22lingo第一圆第二圆第三圆第四圆第五圆圆心坐标圆弧角度24.2544.5578.2456.6635.22误差几乎为0。由此可知我们的方法一的模型为最优化模型，总体较好。由于lingo12软件是我们用来验证最短路径的工具，且上述oa、ob方程的解（由lingo12得出）与方法一的数据吻合度极高，oa、ob两种方程复杂程度完全不同，具有很高的代表性，则我们完全可以认为我们方法一得到的oc、oabco的数据完全正确。 问题二在对问题：寻找oa、ob、oc、oabco最短避障路径我们发现lingo12软件和solidworks2010软件在上述问题中有着很好地求解作用，我们对问题二考虑将两软件lingo12和solidworks2010相结合，具体方法为使用solidworks2010软件模拟仿真并给出约束条件，在使用lingo12软件对方程进行求解。最后得出最优化模型。由公式易知机器人转弯时的速度与机器人转弯圆弧的半径有关，且半径越大，速度越快，因为oa最短时间路径仍由线圆组合构成，所以需要考虑机器人在行走过程中尽可能保证避障路径长度尽可能短。因此，机器人转弯的圆弧与障碍物危险区域的圆弧相内切。故我们设参数：圆弧所对圆心坐标为任意一点（x，y），圆弧半径为z。圆弧所对圆心角度为w，oa的机器人行走时间为t，且t满足方程t=根据solidworks2010软件拉出极限形式oa的区间。我们在后面的计算中发现用lingo12软件找出的约束条件优越性远大于用手工计算，给出如下约束条件：，由lingo12软件编程可求得：x=80.08210 y=209.9198 z=10.11474 w=51.8此时可以得出。将上述x、y数据带入solidworks可验证出： 由此可以说明我们计算的结论正确，再次使用solidworks2010软件进行仿真模拟，路径如下图所示：（注：图中蓝色路径即为仿真模拟得到的机器人行走路径） 由图可看出该路径符合题中各项要求 。综上，我们以找出问题的所有模型，其中所有最短路径的各个坐标见附录1。六：模型的评价与推广本模型最大特色和优点就是以solidworks2010软件仿真模拟与验证结合，求解过程简单明了，尤其是两软件结合使用非常好的保证了模型中各数据的准确性和精确度。易于操作，且便于给出各个点具体坐标，成功的解决了问题一和问题二。模型的缺点在于使用solidworks2010软件仿真过程中对数据的处理要求比较高，为了能够得到最佳模型，在使用solidworks2010软件过程中对数据的处理非常细致，万一模拟过程发生失误则必须从头再来，容错率较低。在现实生活中，本模型的应用性较强，在各个领域都有涉及，比如机器人在地震灾区、核辐射地区等某些危险区域内躲避障碍物并帮助人类完成救援工作；中国对周边岛屿的巡查等 七：参考文献1赵静 但琦，数学建模与数学实验，高等教育出版社，20092杨启帆等，数学建模竞赛，浙江：浙江大学出版社，20053朱道远，数学建模案例精选，北京：科学出版社，20034汪晓银，数学软件与数学实验，科学出版社，20085黄海英，solidworks入门与提高，清华大学出版社，2005附录四：1、o到a最短路径程序：model:min=a+b+c;a=sqrt(x2+(290-x)2-102);b=sqrt(300-x)2+(10+x)2-102);c=3.14159265358979323846*10*y/180;bnd(0,x,80);bnd(51.86,y,90);end程序local optimal solution found. objective value: 471.0376 infeasibilities: 0.000000 extended solver steps: 5 total solver iterations: 104 model class: nlp total variables: 5 nonlinear variables: 1 integer variables: 0 total constraints: 4 nonlinear constraints: 2 total nonzeros: 9 nonlinear nonzeros: 2 variable value reduced cost a 224.4994 0.000000 b 237.4868 0.000000 c 9.051278 0.000000 x 80.00000 -1.126465 y 51.86000 0.1745329 row slack or surplus dual price 1 471.0376 -1.000000 2 0.000000 -1.000000 3 0.000000 -1.000000 4 0.000000 -1.0000002、o到b的最短路径的程序：model:min=a+b+c+d+e+f+g;a=sqrt(x12+y12-100);b=sqrt(x2-x1)2+(y2-y1)2);c=sqrt(x3-x2)2+(y3-y2)2-400);d=sqrt(x4-x3)2+(y4-y3)2);e=sqrt(x5-x4)2+(y5-y4)2-400);f=sqrt(100-x5)2+(700-y5)2-100);g=3.14159265358979323846*(z1+z2+z3+z4+z5)/18;y4=x4+310;y5=2/3*x5+500;y3=-x3+690;bnd(24.25,z1,90);bnd(44.55,z2,90);bnd(78.24,z3,90);bnd(56.66,z4,90);bnd(35.22,z5,90);bnd(0,x1,60);bnd(0,x2,150);bnd(220,x3,280);bnd(220,x4,280);bnd(0,x5,150);bnd(300,y1,310);bnd(435,y2,450);bnd(470,y3,490);bnd(530,y4,550);bnd(600,y5,620);endobjective value: 853.6995 infeasibilities: 0.000000 total solver iterations: 23 model class: nlp total variables: 22 nonlinear variables: 10 integer variables: 0 total constraints: 11 nonlinear constraints: 6 total nonzeros: 45 nonlinear nonzeros: 20 variable value reduced cost a 305.7777 0.000000 b 162.2498 0.000000 c 75.66373 0.000000 d 60.00000 0.000000 e 96.95360 0.000000 f 111.3553 0.000000 g 41.69941 0.000000 x1 60.00000 -0.3584792 y1 300.0000 0.1490546 x2 150.0000 -0.3704458 y2 435.0000 0.3694773 x3 220.0000 1.462573 y3 470.0000 0.000000 x4 220.0000 1.000000 y4 530.0000 0.000000 x5 150.0000 -0.3903360 y5 600.0000 0.000000 z1 24.25000 0.1745329 z2 44.55000 0.1745329 z3 78.24000 0.1745329 z4 56.66000 0.1745329 z5 35.22000 0.1745329 row sl