机器人避障问题的解题分析建模集训

机器人避障问题的解题分析摘要：本文对2012年全国大学生数学建模竞赛D题机器人避障问题进行了全面分析，对最短路的设计进行了理论分析和证明，建立了机器人避障最短路径的几何模型，对最短时间路径问题通过建立非线性规划模型，有效地解决了转弯半径、圆弧圆心位置和行走时间等问题。关键词：机器人避障；最短路径；Dijkstra算法；几何模型；非线性规划模型1 引言随着科学技术的进步和计算机技术的发展，机器人的应用越来越广泛，在机器人的应用中如何使机器人在其工作范围内为完成一项特定的任务寻找一条安全高效的行走路径，是人工智能领域的一个重要问题。本文主要针对在一个场景中的各种静态障碍物，研究机器人绕过障碍物到达指定目的地的最短路径问题和最短时间问题。本文以2012年“高教社”杯全国大学生数学建模竞赛D题“机器人避障问题”为例进行研究。假设机器人的工作范围为800800的平面正方形区域（如图1），其中有12个不同形状的静态障碍物，障碍物的数学描述（如表1）：图1 800800平面场景图表1编号障碍物名称左下顶点坐标其它特性描述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在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动，机器人不能与障碍物发生碰撞，障碍物外指定一点为机器人要到达的目标点。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为（是转弯半径）。如果超过该速度，机器人将发生侧翻，无法完成行走。场景图中有4个目标点O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，下面我们将研究机器人从O(0, 0)出发，求OA、OB、OC和OABCO的最短路径，以及机器人从O(0, 0)出发，到达A的最短时间路径问题。2 静态避障问题中机器人行走最短路径的分析2.1 行走路径的设计在本例中障碍物有4种不同形状：矩形、平行四边形、三角形和圆形。考虑到机器人本身的形状和大小，为研究方便起见，将机器人视为一个点。机器人与障碍物之间的距离至少为10个单位，因此可以先用包络线画出机器人行走的危险区域（如图2），包络线内是机器人的禁入区。图2 障碍物包络图对障碍物的一个角点来说，其禁入区的边界应由两条直线和一条圆弧组成，两条直线分别平行于角点的两条边，间距为10个单位，圆弧是以障碍物角点为圆心，半径为10个单位的四分之一圆弧。可以证明具有圆形限定区域的最短路径由两部分组成，一部分是平面上的自然最短路径（直线段），另一部分是限定区域的部分边界（即绳子拉到最紧时的圆弧部分），这两部分是相切的，互相连接（如图3所示）。由A绕过半圆形障碍物到达B点的路径有多条，其中最短路径为(E、F为切点)，其他路径与AB直线围成的区域都覆盖这一路径与AB直线围成的区域，由此证明1。图3由此可以确定机器人的行走路径应为线圆结构，那么是否是转弯半径越小，行走路径就越短呢？为此需要求在已知两个固定点和圆弧圆心坐标的情况下，圆弧半径r为何值，才能使机器人的行走路径最短。图4如图4，已知两个固定点，圆心，可以求得两切点坐标，设半径为，圆弧所对的圆心角为，的路径长度为,则 将路径函数对求导，得因为,，所以.，则函数为单调递增函数，因此当圆弧半径逐渐增加时，机器人的行走路径会增大，逐渐降低时，机器人的行走路径会减小2，本题规定转弯半径最小为10个单位，所以在路径设定时应将转弯半径设定为最小值10个单位。根据以上分析，对于静态障碍物机器人的行走路径应遵循以下三个原则：原则一：机器人的行走路径为线圆结构，由两条切线和一段圆弧组成；原则二：每个路口至多发生一次转弯，并以障碍物顶点为转弯圆弧的中心；原则三：机器人转弯圆弧半径为最小允许半径10个单位。2.2 最短路径的选择 从起点到达目标点有多条路径，根据Dijkstra算法可以找出从起点到达每一个目标点的最短路径。本文采用带权的有向图表示机器人的行走路径，途中节点为障碍物的角点，边表示障碍物之间的联系，权表示线路的长度（节点之间的直线距离）。从顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径就是所求最短路径，Dijkstra算法就是按路径的长度递增次序产生最短路径的算法3。 下面以 为例，确定的最短路径。如图5所示，根据障碍物的形状和位置，本文给出了机器人从O(0, 0)出发避过障碍物到达目标B点的4条较优路径。 图5画出的非循环网络图（如图6）：B621306O230601121712259921647017978162238B5B3B6B2B4B1B9B77B8017111299569237399705159508329图6运用Dijkstra算法算出的最短路径，最短路算法如下：1、 起点O记为,终点B记为；2、 从网络的终点开始，令它的标号为零，并用方框记录在图6中；3、 计算结点的标号，设结点已标号，结点指向，则的标号可按算式：求出，其中是的标号，是结点与之间的直线距离；4、 重复上述计算，直到求得起点的标号为止，此标号即为最短路的长度；5、 确定最短路径，从起点开始，顺网络的箭线前进，若有几条箭线，则选取箭线所指标号最小且满足条件的结点为最短路径所经过的结点。在图6中，最短路径为：.应用上述算法可得到从点出发，分别到达各目标点的最短路径：图7的最短路径为： （如图7）图8的最短路径为：（如图8）图9的最短路径为:3 最短路径计算模型3.1 单个目标点的最短路径根据前面制定的行走路径原则，起点到目标点无论中间障碍物有多少，最短路径都应该是若干个线圆结构所组成，圆弧中心为障碍物的顶点，半径为机器人转弯最小半径10个单位。观察这四条路径，发现所有行走路径都可归结为以下三种类型：类型一 图10 线圆结构1如图10，设O（）为起点，A（）为目标点，C和D分别为直线与转弯圆弧的切点，障碍物的顶点（即转弯圆弧的圆心），圆的半径为，的长度为，的长度为，的长度为，设的长度为L，则，由图10可得以下关系： 在中： 在中： 在中： 所以： 从而可得： 这个模型运算简洁，只需将起点、目标点和障碍物顶点坐标输入模型，MATLAB就能很快计算出来4，计算程序见附录1。类型二：对于图11这种线圆结构，需要做简单的变换，才能求出的路径长度。 图11 线圆结构2 假设两圆心坐标分别为和,M点为两圆心连线和两圆公切线的交点，坐标为，那么很容易可以求得:这样就可以利用类型一中的方法，先求A到M的长度，再求M到B的长度，分两段就可以求解。同理如果有更多的转弯，同样可以按照此种方法分解。 类型三图12 线圆结构3如图12，如果两圆弧的公切线平行于两圆圆心连线，求的路径长度。设各点坐标分别为起点A (,),目标点B(),障碍物顶点,障碍物顶点),半径为分别是的长度，设的长度为,则解法如下：由图12，可以得到以下关系：a=,b=,c =, , 在中，由余弦定理可得：在中,=arccos所以： 同理：；=arccos；则 运用MATLAB进行计算，MATLAB计算程序见附录2.3.2 多个目标点的最短路径 机器人从起点出发，依次经过指定的中间目标点最后到达终点，是多个目标点的最短路径问题。比如的最短路径的计算。由于机器人的行走路线为线圆结构，不能折线转弯，因此中间目标点应位于某个半径为的圆周上，这里我们仍按照最小允许半径为10个单位，则只需计算出过A、B、C三点的圆心位置即可，这样就将多目标点的最短路径问题转化成了单目标点的最短路径问题。求过A、B、C三点的圆心位置的问题可通过建立非线性规划模型求得。（1） 过A点圆弧的圆心图13如图13，障碍物顶点,顶点,，切点，过A的圆弧圆心，最短路径为,则建立非线性规划模型s.t. 运用LINGO13编程计算，计算程序见附录3.（2） 过B点圆弧的圆心图14如图14，障碍物顶点,顶点,，过B的圆弧圆心，最短路径为,则建立非线性规划模型运用LINGO13编程计算，计算程序见附录4.（3） 过C点圆弧的圆心图15如图15，障碍物顶点,顶点,，过C的圆弧圆心，圆与圆的公切线为,切点，圆与圆的公切线为,切点，最短路径为,则 建立非线性规划模型 运用LINGO13编程计算，计算程序见附录5.运用LINGO对模型求解，过A、B、C的圆弧圆心坐标计算结果(如表2)：表2 过A、B、C的圆弧圆心坐标经过点圆弧的圆心坐标A（290.8854，304.1140）B（107.3884，693.2612）C（709.6622，637.4229） 3.3 切点坐标的计算模型要准确计算出机器人行走路径的长度，必须要知道每一段圆弧的起点和终点，即切点坐标，通过观察上述三种线圆结构的切点主要有两种类型，一种是两圆圆心连线与公切线相交，另一种是两圆圆心连线与公切线平行。（1） 第一种类型的切点两圆圆心连线与公切线相交，则圆心连线的中点在切线上，可由两圆圆心坐标确定中点坐标，此问题就可以转化为求圆弧外的点与障碍物的转弯圆弧形成的切线的切点（如图16）图16设切点,起点O(,),圆心M(,)，求切点C的坐标在中由勾股定理可得：，即又因为切点C在圆M上，故联立方程组运用MATLAB解方程，求出切点的坐标, MATLAB程序见附录6。 （2） 第二种类型的切点图17两圆连线与公切线平行（如图17），设切点,圆心,圆心()，半径为,求切点的坐标。解法如下：直线的斜率为，的直线方程为，因为,所以DE的直线的斜率也为在DE直线上找一点，则DE直线方程为,即，又因为切点D在圆上，满足圆的方程，故，建立方程组，解方程可求得D点的坐标, MATLAB程序见附录7。 如果公切线在障碍物中心连线的下方，模型需要做以下变换再计算。根据以上模型可计算出、以及的所有切点坐标，直线段长度和圆弧长度，计算结果见附录8。4 最短时间路径模型的建立和求解机器人的行走速度与转弯半径有关，假设行走速度与转弯半径之间满足（其中为直线行走速度），那么与最短路径问题不同，转弯半径不再是越小越好，转弯半径越小，虽然行走的距离也越短，但是速度会变慢，这样行走速度反而可能会增加，因此，应选择一个适当的转弯半径，使得行走时间最短5。 以为例，研究最短时间路径问题。以机器人从原点出发到达点的时间最少为目标建立优化模型。转弯半径越大速度越快，走最短距离的时间不一定是最短的到达时间，因此应对转弯半径、转弯所走的圆弧的圆心进行重新搜素，建立非线性规划模型6。图18如图18，起点，目标点，障碍物5的顶点，切点，转弯圆弧的圆心，圆心角为，半径为，的路径为，时间为.则 建立目标函数编写LINGO程序，应用LINGO13求解，计算程序见附录9，计算结果（如表3）：表3 的最短时间路径路径起点坐标终点坐标圆弧圆心坐标圆弧半径总路程总时间0.00000.000069.8049212.7391469.896894.340569.8049212.739176.9877220.117880.9394209.085611.718676.9877220.1178300.0000300.00005 模型的评价与推广5.1 模型的优点（1）将机器人避障行走路线用若干个线圆结构组成建立的模型各点坐标和长度都能直接得出结果，用解析几何方法进行计算，精确度较高。（2）运用多个方案进行优化，在相对优化中能取得最优解。（3）模型简单易懂，便于实际检验及应用。5.2 模型的缺点（1）此模型需要全局优化来求解，求解结果往往因为迭代产生一定的误差，但是这个误差在可允许的范围内。（2）在障碍物较多时，且形状不规则时，模型显得较为繁琐。非线性变量越来越多会导致求解时间越来越长，解的可求性也越来越差。5.3 模型的改进及推广本题只涉及12个障碍物，如果障碍物较多，到达目标点的路径就较多，这时可应用网络模型计算最短路。如果障碍物形状较复杂，单纯用解析几何知识计算较困难，模型需要进一步改进。机器人避障模型可以应用于货物运输、管道输送等领域，应用此模型能较好地解决运输线路最短、输送管道最短等问题。参考文献1 百度文库.行走机器人避障问题:2012-09-0865677232f60ddcca17b.html.2 百度文库.关于机器人避障行走问题的研究:2013-02-28 1f07bed5b9f3f90f1c4b.html.3 邦迪.图论及其应用M.西安:西安科学出版社,1984.4 章栋恩，马玉兰.MATLAB高等数学实验M.北京：电子工业出版社，2010.5蔡志杰.机器人避障问题J.数学建模及其应用,2013,2(1):53-59.6 王琦.线性-二次双层规划的满意解与基于LP与NLP过程的算法J.系统工程理论与实践,2007,27(8).7 周志明.LINGO及其在化工过程优化中的应用J.计算机与应用化学, 2010, 27(7).8 夏伯男.基于最短时间的公交乘车路径查询模型J.大连工业大学学报,2011, 30(2).9 谭永基.数学模型.上海:复旦大学出版社，2011.附录1、线圆结构类型一的MATLAB程序例如：求图7中的最短路径，为，半径，起点，目标点,障碍物顶点，运用MATLAB计算得的最短距离为471.0372，MATLAB算法如下：在MATLAB中编写M文件：fun.mfunction L=fun(x1,y1,x2,y2,x3,y3)a=sqrt(x2-x1)2+(y2-y1)2);b=sqrt(x3-x1)2+(y3-y1)2);c=sqrt(x3-x2)2+(y3-y2)2);alpha1=acos(b2+c2-a2)/(2*b*c);alpha2=acos(10/b);alpha3=acos(10/c);theta=2*pi-alpha1-alpha2-alpha3;L=sqrt(b2-102)+sqrt(c2-102)+10*theta;在命令窗口键入：fun(0,0,300,300,80,210)ans = 471.03722、线圆结构类型三的MATLAB程序比如图9中计算从起点绕过障碍物5，障碍物4，到障碍物4与障碍物12的中点的路径长度，起点,障碍物5的顶点（230，60），障碍物4的顶点（410,100），障碍物4与障碍物12的中点（455,150）。编写MATLAB程序输入起点、目标点、两障碍物顶点坐标及半径，即可计算出路径长度为496.8696。 编写M文件：fun1.mFunction L=fun1(x1,y1,x2,y2,x3,y3,x4,y4) a=sqrt(x4-x1)2+(y4-y1)2); b=sqrt(x4-x3)2+(y4-y3)2); c=sqrt(x3-x1)2+(y3-y1)2); d=sqrt(x3-x2)2+(y3-y2)2); e=sqrt(x4-x2)2+(y4-y2)2); alpha1=acos(b2+c2-a2)/(2*b*c);beta1=acos(10/c);theta1=3*pi/2-alpha1-beta1; alpha2=acos(b2+e2-d2)/(2*b*e); beta2=acos(10/e);theta2=3*pi/2-alpha2-beta2;L=sqrt(c2-102)+10*theta1+b+10*theta2+sqrt(e2-102);在命令窗口输入 fun1(0,0,455,150,230,60,410,100)结果为ans =496.8696 3、过A点圆心编写LINGO程序5,6model:min=(m-80)2+(n-210)2-400)(1/2)+(m-220)2+(n-530)2)(1/2)+10*(acos(-1)+atan(n-530)/(m-220)-atan(y2-y1)/(x2-x1);(x2-x1)2+(y2-y1)2)(1/2)=(m-80)2+(n-210)2-400)(1/2);(x1-80)2+(y1-210)2=100;(x2-m)2+(y2-n)2=100;(n-y2)/(m-x2)*(y2-y1)/(x2-x1)=-1;(300-m)2+(300-n)2=100;n=y2;y1210;end运行结果： Objective value: 482.2310 Variable Value Reduced Cost M 290.8854 0.000000 N 304.1140 0.000000 Y2 294.6634 0.000000 Y1 219.4505 0.000000 X2 294.1546 0.000000 X1 76.73080 0.0000004、过B点圆心编写LINGO程序model:min=(m-150)2+(n-600)2)(1/2)+(m-180)2+(n-680)2)(1/2)+10*(acos(-1)-atan(680-n)/(270-m)-atan(600-n)/(150-m);(m-100)2+(n-700)2=100;end运行结果: Objective value: 219.9993Variable Value Reduced CostM 107.3884 0.000000N 693.2612 0.0000005、过C点圆心编写LINGO程序model:min=(m-670)2+(n-730)2-400)(1/2)+(m-720)2+(n-600)2-400)(1/2)+10*(atan(y2-y1)/(x2-x1)-atan(y4-y3)/(x4-x3);(x1-720)2+(y1-600)2=100;(x3-670)2+(y3-730)2=100;(x2-m)2+(y2-n)2=100;(x4-m)2+(y4-n)2=100; (700-m)2+(640-n)2=100;(n-y4)/(m-x4)*(y4-y3)/(x4-x3)=-1;(n-y2)/(m-x2)*(y2-y1)/(x2-x1)=-1;(y2-y1)/(x2-x1)(n-600)/(m-720);(y4-y3)/(x4-x3)700;y4=640;y2670;y1600;end运行结果： Objective value: 130.7340 Model Class: NLP Variable Value Reduced Cost M 709.6622 0.000000 N 637.4229 0.000000 Y2 634.6639 0.000000 Y1 600.0000 0.000000 X2 700.0503 0.000000 X1 710.0000 0.000000 Y4 641.3609 0.000000 Y3 733.9381 0.000000 X4 718.8542 0.000000 X3 679.1919 0.0000006、 第一种类型的切点例如求起点O绕过障碍物5到达A点的第一个切点坐标.编写M文件，保存为“切点1.m”:syms x y x1 y1 x2 y2f1=(x2-x)2+(y2-y)2=100); f2=(x2-x1)2+(y2-y1)2-100=(x-x1)2+(y-y1)2);x,y=solve(f1,f2,x,y);在命令窗口输入 x1=0;y1=0;x2=80;y2=210; eval(x,y)ans = 70.5060 213.1406 89.1772 206.0277根据题意取障碍物左侧的点，得第一个切点坐标为（70.5060，213.1406）。7、 第二种类型的切点例如求从A点到障碍物7的切点，运用MATLAB求解.编写M文件，保存为“切点2.m”:syms x y x1 y1 x2 y2f1=(x1-x)2+(y1-y)2=100);f2=(y=y1+10*sqrt(1+(y2-y1)/(x2-x1)2)+(y2-y1)/(x2-x1)*(x-x1);x,y=solve(f1,f2,x,y);在命令窗口输入： x1=290.8814;y1=304.1051;x2=220;y2=530; eval(x,y)ans = 300.4227 307.0990 公切线的切点的坐标为（300.4227，307.0990），同样算法，只需交换一下坐标就可得到另一切点的坐标为（229.5413，532.9939）. 8、最短路径计算结果汇总：的最短路径路径起点坐标终点坐标圆心坐标圆弧半径直线或圆弧长线段0.00000.000070.5060213.1406224.4995圆弧70.5060213.140676.6064219.406680.0000210.000010.00009.0510线段76.6064219.4066300.0000300.0000237.4868总路程：471.0373 总时间：96.0177的最短路径路径起点坐标终点坐标圆心坐标圆弧半径直线或圆弧长线段0.00000.000050.1353 301.6396305.7776圆弧50.1353301.639651.6795305.547060.0000300.000010.00004.2330线段51.6795305.5470141.6795440.5470162.2498圆弧141.6795440.5470147.9621444.7901150.0000435.000010.00007.7756线段147.9621 444.7901222.0379460.209975.6637圆弧222.0379 460.2099230.0000470.0000220.0000470.000010.000013.6557线段230.0000470.0000230.0000530.000060.0000圆弧230.0000530.0000225.4967538.3538220.0000530.000010.0000.9.8883线段225.4967 538.3538144.5033591.646296.9537圆弧144.5033 591.6462140.6916596.3458150.0000600.000010.00006.1474线段140.6916 596.3458100.0000700.0000111.3553总路程：853.7001 总时间：179.0800的最短路径路径起点坐标终点坐标圆心坐标圆弧半径直线或圆弧长线段0.00000.0000232.1149 50.2262237.4868圆弧232.1149 50.2262232.1693 50.2381230.000060.000010.00000.7860线段232.1693 50.2381412.1693 90.2381184.3909圆弧412.1693 90.2381418.3448 94.4897410.0000100.000010.00007.6852线段418.3448 94.4897491.6552 205.5103133.0413圆弧491.6552 205.5103492.0623 206.0822500.0000200.000010.00003.3127线段492.0623 206.0822727.9377 513.9178387.8144圆弧727.9377 513.9178730.0000520.0000720.0000520.000.10.00006.5381线段730.0000520.0000730.0000600.000080.0000圆弧730.0000600.0000727.7178 606.3589720.0000600.000010.00006.8916线段727.7178 606.3589700.0000640.000043.5889总路程：1091.5359 总时间：223.3499的最短路径路径起点坐标终点坐标圆心坐标圆弧半径直线或圆弧长线段0.00000.000070.5060213.1406224.4995圆弧70.5060,213.140676.7308 219.450580.0000210.000010.00009.1704线段76.7308 219.4505294.1546 294.6635230.9169圆弧294.1546 294.6635300.4266 307.1081290.8854304.114010.000015.4315线段300.4266 307.1081229.5412 532.9941236.7619圆弧229.5412 532.9941225.4967 538.3538220.0000530.000010.00006.8481线段225.498538.3538144.5033 591.646296.9590圆弧144.5033 591.6462140.9044 595.8442150.0000600.000010.00005.6022线段140.9044 595.844298.2928 689.1054102.5349圆弧98.2928 689.1054108.2012 703.2281107.3884693.261210.000020.8073线段108.2012 703.2281270.8128 689.9669163.1514圆弧270.8128 689.9669272.0000 689.7980270.0000680.000010.00005.2668线段272.0000 689.7980368.0000 670.202097.9778圆弧368.0000 670.2020370.0000670.0000370.0000680.000010.00002.0136线段370.0000670.0000430.0000670.000060.0000圆弧430.0000670.0000435.5878 671.7068430.0000680.000010.00005.9291线段435.5878 671.7068534.4122 738.2932119.1638圆弧534.4122 738.2932540.0000740.0000540.0000730.000010.00005.9291线段540.0000740.0000670.0000740.0000130.0000圆弧670.0000740.0000679.7899732.0390670.0000730.000010.000013.6359线段679.7909 732.0343699.8713 635.388698.6230圆弧699.8713 635.3886702.7722 630.1753709.6622637.422910.00003.3580线段702.7722 630.1753726.8900 607.247633.3854圆弧726.8900 607.2476730.0000600.0000720.0000600.000010.00005.2082线段730.0000600.0000730.0000520.000080.0000圆弧730.0000520.0000727.9377 513.9178720.0000520.000010.00006.5381线段727.9377 513.9178492.0623 206.0822387.5900圆弧492.0623 206.0822491.6552 205.5103500.0000200.000010.00003.3127线段491.6552 205.5103418.3448 94.4897126.2100圆弧418.3448 94.4897412.1693 90.2381420.0000100.000010.00007.6852线段412.1693 90.2381232.1693 50.2381184.3909圆弧232.1693 50.2381232.1149 50.2262230.000060.000010.00000.7860线段232.1149 50.22620.00000.0000237.4868总路程：2727.1735 总时间：568.93919、最短时间路径的计算编写LINGO程序，应用LINGO13求解model:min=(x12+y12)(1/2)+(300-x2)2+(300-y2)2)(1/2)/5+r*(atan(y1/x1)-atan(300-y2)/(300-x2)/(5/(1+exp(10-0.1*(r2);y1/x1=210/80;(300-y2)/(300-x2)=10+(m-80)2+(n-210)2;(m-x1)2+(n-y1)2=r2;(m-x2)2+(n-y2)2=r2;(m2+n2-x12-y12)1/2=10;(m-x1)2+(n-y1)2=(m-x2)2+(n-y2)2;(y1/x1)*(n-y1)/(m-x1)=-1;(300-y2)/(300-x2)*(n-y2)/(m-x2)=-1;End运行结果： Objective value: 94.34054 Variable Value Reduced Cost X1 69.80490 0.000000 Y1 212.7391 0.000000 X2 76.98770 0.000000 Y2 220.1178 0.000000 R 11.71858 0.000000 M 80.93940 0.000000 N 209.0856 0.000000