2012年数学建模D题.doc

.2012高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：D我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：* 参赛队员(打印并签名) ：1. 2 3 指导教师或指导教师组负责人 (打印并签名)： 日期：2012年9月9日 赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛题目编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录：评卷人评分备注 全国统一编号（由赛区组委会送交全国前编号）：;.机器人避障问题摘要二十一世纪科技发展迅速，机器人作业逐渐兴盛。本文研究了机器人避障最短路径和最短时间的问题。主要研究了在一个区域中存在12个障碍物，由出发点到达目标点以及由出发点经过途中的若干目标点到达最终目标点的两种情形。我们通过证明具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的自然最短路径（即直线段），另一部分是限定区域的部分边界，这两部分是相切的，互相连接的。依据这个结果，我们可以认为最短路径一定是由线和圆弧做组成，因此我们建立了线圆结构，这样无论路径多么复杂，我们都可以将路径划分为若干个这种线圆结构来求解。一、问题重述图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平面场景图二、问题分析本题可以用AutoCAD作图软件完成部分路线及线段、弧线、坐标的标注等。问题一O点到A点理论上是直线最短，但不能折点转弯（必须切线转弯）、必须与障碍物保持10单位的距离，转弯弧线半径最短为10个单位，则可以以障碍物5的左上角和右下角点位圆心画半径为10单位的圆，并在障碍物4的左下角画同样的圆，那么我们可以用拉绳子的方法模拟机器人行走路线，求出到达目标点的最短距离。 O到B与O到CO到B与O到C最短路线求解分析原理与O到A一样不再重述。O到A到B到C再到O要求机器人到达各目标点在回到原点，此时不但要考虑障碍物的问题还要考虑从以目标点到另一目标点的转弯问题，此时简单的拉线一不满足。问题二时间与路程和速度的关系，速度与转弯半径的关系，根据此公式不难得出半径与速度的关系，即半径越大速度约接近5，但半径越大路程越长，消耗时间也越多。三、模型假设与约定1、假设机器人无体积。2、假设切线转弯时速度变化为瞬间，即没有加速度。3、做题所用的数据全部保留两位小数4、用AutoCAD软件作图过程不予描述，例举两条路线进行分析。四、符号说明及名词定义V:机器人行走速度V():机器人弧线行走速度:机器人直线行走最大速度：机器人转弯半径T：机器人行走时间S：机器人行走路程五、模型建立模型建立1、先来证明一个猜想：猜想一：具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的自然最短路径（即直线段），另一部分是限定区域的部分边界，这两部分是相切的，互相连接的。（即问题分析中的拉绳子拉到最紧时的状况）证明：假设在平面中有A（a，0）和B（-a，0）两点，中间有一个半圆形的障碍物，证明从A到B的最路径为AEFB。平面上连接两点最短的路径是通过这两点的直线段，但是连接两点的线段于障碍物相交，所以设法尝试折线路径。在y轴上取一点C（0，y），若y适当大，则折线ACB与障碍物不相交，折线ACB的长度为： 显然随着y的减小而减小，减小y得，即,使得与与障碍物相切，切点分别为E和F,显然是这种折线路径中最短的。由于满足的角满足,所以易知弧度EF小于的长， 即,从而,记线段AE、弧度EF、线段FB为AEFB,那么AEFB比任何折线路径都短。下面在考察一条不穿过障碍物的任何一条路径，设其分别于OE和OF的延长线交与P、Q两点，记A和P之间的路径长度为，显然,又由AEEO,所以|,从而,同理可得。再来比较PQ之间路径长度和圆弧EF的长度的大小。若PQ之间的路径可有极坐标方程,则有,可得： 亦即路径APQB的长度超过路径AEFB的长度。以上证明足以说明了AEFB是满足条件A到B的最短路径。猜想二:如果一个圆环可以绕着环上一个定点转动，那么过圆环外两定点连接一根绳子，并以该圆环为支撑拉紧绳子，达到平衡状态时，圆心与该顶点以及两条切线的延长线的交点共线。 图3证明猜想：如图4.31所示，E点就是圆环上的一个顶点，就是拉紧的绳子，就是切线AC和BD的延长线的交点，证明、E、三点共线。我们可以用力学的知识进行证明，因为是拉紧的绳子，所以两边的绳子拉力相等，设为，它们的合力设为，定点对圆环的作用力设为。那么由几何学的知识我们可以知道一定与共线，而又由力的平衡条件可知：=即与共线。综上所述、和三点一定共线。2、有了以上这个定理我们可以建立以下模型：如图4，要求求出机器人从A绕过障碍物经过M点到达目标点B的最短路径，我们采用以下方法：用一根钉子使一个圆环定在M点，使这个圆环能够绕M点转动。然后连接A和B的绳子并以这些转弯处的圆弧为支撑（这里转弯处圆弧的半径均按照最小转弯半径来计算），拉紧绳子，那么绳子的长度就是A到B的最短距离。我们可以把路径图抽象为以下的几何图形。下面我们对这段路径求解：图4如图，A是起点，B是终点，和是两个固定的圆， 是一个可以绕M(p，q)点转动的圆环，三个圆的半径均为r，C、D、E、F、G、H均为切点。a、b、c、e，f分别是A、A、A、的长度。A、B、均是已知点，是未知点。那么最短路径就可以表示为：因为点的坐标未知，所以我们就不能用模型一中的线圆结构对其进行求解。故得先求出点的坐标。设坐标为（m，n），、分别为（=1、2、3、4、5），、分别为、。这样便有以下关系：在中：在中：在中：在中：则：又因为一定会在的角平分线上，所以满足：我们采用向量的形式来求，易知的一个方向向量：而与垂直，故其一个方向向量：而：所以：综合以上式子可以求得的坐标，从而可以得出路径的长为：=+HB，这可以采用模型一中的线圆结构来求解。建立模型绳子套在一个环上，环套在一个定圆上。如图5图5可证明此路线为最短路径。六、模型求解问题一用AutoCAD软件对机器人的行走路径进行作图分析。1、O点到A点(OA)目测从O点到A点比较短的路线有两条，即从障碍物5顶部绕和从其底部绕（如图6）。用AutoCAD软件对路线进行标注（如图7），计算两条路线的长度。路线1：线路2：两条路线进行比较可知线路1最短。2、O点到B点(OB)目测可知从O点到B点的最短路线必从O点到B点线路1（如图8）和O点到B点线路2（如图9）中产生，分别对两条路进行标注，线路1标注图（如图6），线路2标注图（如图10），计算两条路线的长度。图4图5图6图7线路1：线路2：对和进行比较可知（），线路1为最短线路。3、O点到C点(OC)作图分析可得出两条路线距离比较近，线路1（如图11）和线路2（如图12）。分别对两条路进行标注，线路1标注图（如图13），线路2标注图（如图14），计算两条路线的长度。图8图9图10图11线路1： 线路2：对、进行比较可知,线路1最短。4、OABCO若使此路径最短，则取OA和OC的最短路线,AB和BC的最短线路不难看出, OABCO的最短线路如图15，对此线路进行标注，如图16。问题二此问题可以用模型二解决，根据公式可知弧线速度与转弯半径的关系，即随着的增大的增长幅度逐渐最终趋近与0（弧度线的行走速度趋近与5）。根据公式可知弧线长度与转弯半径的关系。由此可知机器人行走距离与行走速度和时间的关系。最短时间路线如图17，标注层如图18.七、模型检验和模型评价一、模型优点1、运用AutoCAD作图软件，方便快捷的标注出各线段，各点的相关信息。2、小数点保留两位，精确度较高。3、模型简单易懂，便于实际检验及应用。二、模型缺陷1、问题二求解精确度不高。没有相关程序作支持。2、在障碍物较多时，且形状不规则时，模型需要进一步改进。八、参考文献1尤承业，解析几何，北京，北京大学出版社，20042邦迪，图论及其应用，西安，西安科学出版社 19843谭永基，数学模型，上海，复旦大学出版社，20114周培德，计算几何算法与设计，北京清华大学出版社，20055胡海星，RPG游戏中精灵的移动问题，杂志程序员 2011；九、附录各路线的相关信息（O到A、O到B、O到C的最短路线，OABCO的最短路线，O到A的最短时间路线）O到B最短距离路线O到A最短距离路线行走路线1110987654321321序号直线弧线直线弧线直线弧线直线弧线直线弧线直线直线弧线直线类型(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)起始坐标(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）终点坐标111.366.1596.959.896013.6676.417.78162.254.23305.78237.499.05224.5长度(150,600)(220,530)(220,470)(150,435)(60,300)（80,210）圆心坐标800.46471.04总距离180.6596.02总时间OC最短距离路线行走路线1110987654321序号直线弧线直线弧线直线弧线直线弧线直线弧线直线类型(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)起始坐标(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）终点坐标43.596.89806.54387.810.7133.047.69184.390.06237.49长度(720,600)(720,520)(500,200)(410,100)（230,60）圆心坐标1088.2总距离228.01总时间OABCO行走路线1413121110987654321序号弧线直线弧线直线弧线直线弧线直线弧线直线弧线直线弧线直线类型(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)起始坐标(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）终点坐标2.0197.981.13162.4420.76103.115.7196.956.85236.7515.42230.069.05224.5长度(370,680)(270,680)(108.18,694.25)(150,600)(220,530)(290.88,304.11)（80,210）圆心坐标2730总距离568.66总时间OABCO最短距离路线行走路线2827262524232221201918171615序号弧线直线弧线直线弧线直线弧线直线弧线直线弧线直线弧线直线类型(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