[工学]公园内道路设计问题.doc

承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 西安培华学院 参赛队员 (打印并签名) ：1. 胡斌斌 2. 罗丹 3. 白桂兴 指导教师或指导教师组负责人 (打印并签名)： 李艳 日期： 2012 年 8 月 11 日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：公园内道路设计问题摘要 最短路问题是现实生活中常见的问题，在商业利润估算、生产生活、运输路线选择等方面都有重要意义。本文讨论的是公园道路最优设计问题:在满足任意两入口之间最短道路长不大于两点连线的1.4倍的条件下，建立相应最短道路模型，使得修建总道路长度最短。又因公园边界已经存在修建好的道路，且不计入修建总总长度，所以应尽量利用边界道路。对于问题一，首先：利用1.4倍的约束条件排除可利用边界的入口点，选出需要通过交叉点设计路线的入口点。然后：依据Kruskal算法，构造最小生成树。最后：运用MATLAB软件编程，在满足要求的情况下，得到最优道路设计方案。使得公园新修路的总路程最小为394.5596米。 对于问题二，首先：取问题一中不可利用边界的入口点，分析出满足条件下的可行最短路线。然后：引入费马点，确定费马点个数，运用LINGO和MATLAB分别求解费马点坐标。最后：运用费马点优化可行最短路线，在满足要求的情况下，得到最优道路设计方案。使得公园新修路的总路程最小为358.4320米。对于问题三，首先：取问题二的最优道路设计方案，添加一矩形人工湖。针对人工湖对路线的破坏段进行局部优化。然后：给出2个可行局部优化方案，对局部区域分别引入费马点，运用LINGO和MATLAB分别求解费马点坐标。最后：运用费马点优化可行方案，分别得到2个方案的最优道路设计方案。对比2个方案，得到最优的道路设计方案。使得公园新修路的总路程最小为360.5758米。关键词：Kruskal算法 最小生成树 费马点 MATLAB LINGO一、问题重述1.1、问题背景西安某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更好的生活条件。要求：公园计划有若干个入口，需建立一个模型去设计道路让任意两个入口相连（可以利用公园的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，且任意两个入口之间的最短道路长不大于两点连线的1.4倍。题目已知：矩形公园的长为200米，宽为100米，1至8各入口的坐标分别为：P1(20，0) , P2(50，0) , P3(160，0) , P4(200，50) , P5(120，100) , P6(35，100) , P7(10，100) , P8(0，25)，见图1。（附录一.Fun1）。（图1）1.2、需要解决的问题问题一：假定公园内确定要使用4个道路交叉点为：a(50，70) , b(40，40) , c(120，40) , d(115，70) ，见图2（附录一.Fun2）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法，画出道路设计，计算新修路的总工程。（图2）问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法，画出道路设计和道路交叉点的坐标，计算新修路的总工程。问题三：若公园内有一条矩形的湖，新修的路不能通过，但可以到达湖四周的边，已知矩形的湖为R1(140,70) , R2(140，45) , R3(165，45) , R4(165，70)，见图3（附录六.Fun1）。重复完成问题二的任务。（图3）注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连接到四周的其它点。二、问题分析2.1、问题一的分析 先计算出“8个入口点两两之间的直线距离”，然后计算出“8个入口点两两之间的边界路径距离”。 “8个入口点两两之间的边界路径距离8个入口点两两之间的直线距离1.4”-不需要通过交叉点设计路线。 “8个入口点两两之间的边界路径距离8个入口点两两之间的直线距离1.4”-需要通过交叉点设计路线。表2.1-1入口点两两之间的直线距离表P1P2P3P4P5P6P7P8P1030140186.8141.4101.1100.532P20110158.1122.1101.1107.755.9P3064107.7160.1180.3161.9P4094.3172.4196.5201.6P5085110141.5P602582.8P7075.7P80表2.2-2入口点两两之间的边界路径距离表P1P2P3P4P5P6P7P8P10P2300P31401100P4230200900P53603302201300P6155185295215850P7130160270240110250P84575185275195105850 通过计算：“P1P5、P1P6、P1P8、P2P5、P2P6、P2P7、P3P4、P3P5、P3P6、P3P7”需要通过交叉点设计路线。2.2、问题二的分析 在本问题中，设计原则：尽可能地利用好公园的边界，不能利用边界的再采取内部新修路的方式。 在第一个问题中，已经知道“P1P5、P1P6、P1P8、P2P5、P2P6、P2P7、P3P4、P3P5、P3P6、P3P7”需要通过交叉点设计路线。因此，将上述两点之间用直线相连，得到图像如下图2.2-1所示。（附录四.Fun1）（图2.2-1）图2.2-1中线段长度，如下表2.2-1所示： 两点间直线段长度P1-P5141.4214P1-P6101.1187P1-P832.0156P2-P5122.0656P2-P6101.1187P2-P7107.7033P3-P464.0312P3-P5107.7033P3-P6160.0781P3-P7180.2776在图2.2-1中寻找“P1P5、P1P6、P1P8、P2P5、P2P6、P2P7、P3P4、P3P5、P3P6、P3P7”的最短路径（可利用边界）。最短路径需满足：入口点两两之间的最短路径距离入口点两两之间的直线距离1.4 通过逐步检验分析可知“P1-P8、P2-P5、P2-P6、P3-P4、P3-P5”满足要求，故简化为下图2.2-2.（附录四.Fun2）（图2.2-2）再通过交叉点设计“P1-P8、P2-P5、P2-P6、P3-P4、P3-P5”的最短路径。2.3、问题三的分析 本问题中，设计原则：在问题二设计的路线的基础上，公园内部新加入一人工湖，见图2.3-1（附录六.Fun2），故对原设计的方案进行局部优化。（图2.3-1） 可知：由于加入了人工湖，原方案中的P5-Q1路线将不再可行。 故：我们只需修改P5-Q1路线，对Q2所在的区域路线进行局部优化。修改P5-Q1路线，对Q2区域局部优化方案： 方案一：连接P5-R4，求R4P4P3的费马点，设计最短路径。 方案二：连接P5-R2，求R2P4P3的费马点，设计最短路径。 方案三：连接P5-R1，求R1P4P3的费马点，设计最短路径。 方案四：连接P5-R3，求R3P4P3的费马点，设计最短路径。方案分析：我们可以发现方案三、四将需要人工湖中有路段通过，这与题目不符。 故：可实行的方案只有方案一、二.三、模型假设1、假设公园四周已修建好道路，且该道路不计如新修路总长。2、根据距离模型可知距离与入口大小无关，故可将各入口均视为点。3、假设所有点之间修建道路均为直线；交叉点不影响道路的修建。4、公园内新修的道路与四周的连接只能与8个路口相通，而不能连接到四周的其他点。5、除题目要求外，道路规划不考虑任何其他客观因素。4、 符号说明P1 P2 P3 P4 P5 P6 P7 P8入口点a b c d交叉点R1 R2 R3 R4人工湖顶点Qi(xi,yi)三角形费马点Si费马点到三角形3个顶点的距离和Diji到j的路程S S S 新修路的总路程L L新修路的总路程五、模型的建立与求解5.1、模型一的建立与求解针对P1、P2、P8及公园4个固定道路交叉点a、b、c、d，求出这12个点两两之间的直线距离，如下表5.1-1所示：表5.1-1（distance.xls）入口点及道路交叉点两两之间的直线距离表（小数部分已做处理）P1P2P3P4P5P6P7P8abcdP1030140187141101100328145108118P23001101581221011085675418196P31401100641081601801621331265783P4187158640941721962021521608187P514112210894085110142741006030P61011011601728502583296010485P7100108180196110250764767125109P83256162202142837607143121123a8175133152742947710367865b45411261601006067433608081c108815781601041251217880030d11896838730851091236581300 以表5.1-1所示的矩阵为公园道路设计连通图的邻接矩阵。 根据Kruskal算法，运用matlab软件编程。（附录二） MATLAB运行后的结果如下表5.1-2所示：表5.1-2 Kruskal算法的程序运行结果表252930303032364157646566151119233979212128101011412由表5.1-2的结果可画出最小生成树如下图5.1-1所示。（附录一.Fun3）（图5.1-1）针对“P1P5、P1P6、P1P8、P2P5、P2P6、P2P7、P3P4、P3P5、P3P6、P3P7”需要通过交叉点设计路线，故在上述最小生成树图内，求这些点间的最短路径、最短路径长度、最短路径长度/两点间直线距离。（附录三）MATLAB运行后的结果如下表5.1-3所示： 表5.1-3通过交叉点最短路径表点最短路径最短路径长度最短路径/两点间的直线距离P1-P5203.23741.4371P1-P6136.78641.3527P1-P832.01561P2-P5173.23741.4192P2-P6106.78641.0560P2-P7131.78641.2236P3-P464.03121P3-P5117.39611.0900P3-P6181.32911.1328P3-P7206.32911.1445由表5.1-3可知：“P1-P5”、“P2-P5”的“最短路径/两点间的直线距离1.4”。故通过逐步分析比较发现，可以改变ad这条路径来调整路径P1-P5和P2-P5。 调整后的最终方案如下图5.1-2所示。（附录一.Fun4）（图5.1-2）经数据检验：（任意）两点之间的最短路径两点间的直线距离1.4 结果：新修路的总路程S: S=D18+D2b+Dba+Da6+Da5+D5d+Ddc+Dc3+D34 =32.0156+41.2311+36.4005+29.1548+74.3303+30.4138+30.4138+56.5685+64.0312 =394.5596(米)5.2、模型二的建立与求解5.2.1、引入费马点：费马点性质：在一个三角形中，到3个顶点距离之和最小的点叫做这个三角形的费马点。费马点定义：(1)若三角形ABC的3个内角均小于120，那么费马点即为三角形三个内角角平分线交点。 ( 2)若三角形有一内角不小于120度，则此钝角的顶点就是费马点。5.2.2、引用费马点：为引用费马点将图2.2-2中P4、P5用虚线连接，如图2.2-1所示.（附录四.Fun3）（图2.2-1） 可知：P2P6P5和P3P4P5的3个内角均小于120， 故：P2P6P5和P3P4P5的费马点，即为其三个内角角平分线交点。5.2.3、求解费马点： 建立的非线性规划模型： 非线性规划模型： 非线性规划模型： 运用LINGO和MATLAB分别求解：(1) LINGO求解结果：（附录五.Fun1）值： Local optimal solution found. Objective value: 175.7767 Infeasibilities: 0.000000 Extended solver steps: 5 Total solver iterations: 75 Variable Value Reduced Cost X1 62.33373 0.000000 Y1 77.86494 0.000000 Row Slack or Surplus Dual Price 1 175.7767 -1.000000 2 480.2694 0.000000 3 421.7172 0.000000 4 22.13506 0.000000值： Local optimal solution found. Objective value: 150.6397 Infeasibilities: 0.000000 Extended solver steps: 5 Total solver iterations: 74 Variable Value Reduced Cost X2 173.0980 0.000000 Y2 43.64328 0.6062958E-08 Row Slack or Surplus Dual Price 1 150.6397 -1.000000 2 109.0830 0.000000 3 185.3637 0.000000 4 152.7767 0.000000结果：；(2) MATLAB求解结果：（附录五.Fun2）结果：；5.2.3、运用费马点：根据做为交叉点设计路线，如下图2.3-1所示。（附录四.Fun4）（图2.3-1） 调整后的最终方案如下图2.3-2所示。（附录四.Fun5）（图2.3-2） 结果：新修路的总路程S=S1+S2+D18 =175.7767+150.6397+32.0156= 358.4320(米)5.3、模型三的建立与求解5.3.1、求解方案方案一：在R4P4P3中，设其费马点为。 非线性规划模型： 方案二：在R2P4P3中，设其费马点为。 非线性规划模型： 运用LINGO和MATLAB分别求解： LINGO求解结果：（附录七.Fun1）值： Local optimal solution found. Objective value: 98.70020 Infeasibilities: 0.000000 Extended solver steps: 2 Total solver iterations: 30 Variable Value Reduced Cost X3 181.1422 0.000000 Y3 47.94938 0.000000 Row Slack or Surplus Dual Price 1 98.70020 -1.000000 2 86.08664 0.000000 3 248.0411 0.000000 4 89.78565 0.000000值： Local optimal solution found. Objective value: 99.62300 Infeasibilities: 0.000000 Extended solver steps: 5 Total solver iterations: 90 Variable Value Reduced Cost X4 161.7519 0.000000 Y4 30.73196 0.000000 Row Slack or Surplus Dual Price 1 99.62300 -1.000000 2 114.1684 0.000000 3 138.6949 0.000000 4 192.9684 0.000000结果：； MATLAB求解结果：（附录七.Fun2）结果：； 5.3.2方案设计图根据分别设计方案一、方案二路线：方案一设计图：见图3.2-1（附录六.Fun3）（图3.2-1） 新修路的总路程L=D18+S1+D(P5R4)+S3 =32.0156+175.7767+ 54.0833+98.7002 =360.5758(米)方案二设计图：见图3.2-2（附录六.Fun4）（图3.2-2）新修路的总路程L=D18+S1+D(P5R2)+S4 = 32.0156+175.7767+58.5235+99.6230 =365.9388（米）5.3.3方案结果分析 经分析：方案一、方案二均满足条件： 入口点两两之间的最短路径距离入口点两两之间的直线距离1.4 新修建的道路不可通过人工湖，但可到达湖四周的边界。由于Lx(1,j)a=x(1,i);x(1,i)=x(1,j);x(1,j)=a;a=x(2,i);x(2,i)=x(2,j);x(2,j)=a;a=x(3,i);x(3,i)=x(3,j);x(3,j)=a;endendend%给各点标号赋初值for i=1:nl(i)=i;end%初始时选e1加入集合EE(1,1)=x(1,1); %E矩阵的第一行记录最小生成树的边长E(2,1)=x(2,1); %E矩阵的第二行记录边的起点E(3,1)=x(3,1); %E矩阵的第三行记录边的终点a=min(l(E(2,1),l(E(3,1);l(E(2,1)=a;l(E(3,1)=a;b=1;%记录E中边数 for i=2:k if b=n-1 %如果树中边数达到n-1break %算法终止end if l(x(2,i)=l(x(3,i) %如果两顶点标号不同b=b+1; %将这条边加入EE(1,b)=x(1,i);E(2,b)=x(2,i);E(3,b)=x(3,i); for j=1:n %对于所有顶点if l(j)=max(l(E(2,b),l(E(3,b)%如果该顶点的标号,等于=,新加入边中的顶点标号较大的值l(j)=min(l(E(2,b),l(E(3,b);%将其改为较小的那一个以避圈endendendend附录三：Fun1：求“P1-P5最短路径S15”及“最短路径S15与两点间直线L比例”D12=30;D2b=41.2311;Dba=36.4005;Da6=29.1548;D65=85;Dad=65.1920;Dd5=30.4138;D23=110;D3c=56.5685;Dcd=30.4138;D34=64.0312;D45=130;D18=32.0156;D87=85;D76=25;L= 141.4214; X15=D12+D2b+Dba+Da6+D65;Y15=D12+D2b+Dba+Dad+Dd5;Z15=D12+D23+D3c+Dcd+Dd5;M15=D12+D23+D34+D45;N15=D18+D87+D76+D65; S1=min(X15,Y15);S2=min(Z15,M15);S3=min(S1,S2);S15=min(S3,N15); Z=X15,Y15,Z15,M15,N15S15 r=S15/LFun2：求“P1-P6最短路径S16”及“最短路径S16与两点间直线L比例”D12=30;D2b=41.2311;Dba=36.4005;Da6=29.1548;D18=32.0156;D87=85;D76=25;L= 101.1187; X16=D12+D2b+Dba+Da6;Y16=D18+D87+D76; S16=min(X16,Y16); Z=X16,Y16S16 r=S16/LFun3：求“P1-P8最短路径S18”及“最短路径S18与两点间直线L比例”D18=32.0156;L=32.0156; S18=D18;S18 r=S18/LFun4：求“P2-P5最短路径S25”及“最短路径S25与两点间直线L比例”D2b=41.2311;Dba=36.4005;Da6=29.1548;D65=85;Dad=65.1920;Dd5=30.4138;D23=110;D3c=56.5685;Dcd=30.4138;D34=64.0312;D45=130;D21=30;D18=32.0156;D87=85;D76=25;L=122.0656; X25=D2b+Dba+Da6+D65;Y25=D2b+Dba+Dad+Dd5;Z25=D23+D3c+Dcd+Dd5;M25=D23+D34+D45;N25=D21+D18+D87+D76+D65; S1=min(X25,Y25);S2=min(Z25,M25);S3=min(S1,S2);S25=min(S3,N25); Z=X25,Y25,Z25,M25,N25S25 r=S25/LFun5：求“P2-P6最短路径S26”及“最短路径S26与两点间直线L比例”D2b=41.2311;Dba=36.4005;Da6=29.1548;D21=30;D18=32.0156;D87=85;D76=25;L=101.1187; X26=D2b+Dba+Da6;Y26=D21+D18+D87+D76; S26=min(X26,Y26); Z=X26,Y26S26 r=S26/LFun6：求“P2-P7最短路径S27”及“最短路径S27与两点间直线L比例”D2b=41.2311;Dba=36.4005;Da6=29.1548;D67=25;D21=30;D18=32.0156;D87=85;L=107.7033; X27=D2b+Dba+Da6+D67;Y27=D21+D18+D87; S27=min(X27,Y27); Z=X27,Y27S27 r=S27/LFun7：求“P3-P4最短路径S34”及“最短路径S34与两点间直线L比例”D34=64.0312;L=64.0312; S34=D34;S34 r=S34/LFun8：求“P3-P5最短路径S35”及“最短路径S35与两点间直线L比例”D3c=56.5685;Dcd=30.4138;Dd5=30.4138;D23=110;D34=64.0312;D45=130;L=107.7033; X35=D3c+Dcd+Dd5;Y35=D23+D34+D45; S35=min(X35,Y35); Z=X35,Y35S35 r=S35/LFun9：求“P3-P6最短路径S36”及“最短路径S36与两点间直线L比例”D3c=56.5685;Dcd=30.4138;Dd5=30.4138;D56=85;Dda=65.1920;Da6=29.1548;D32=110;D2b=41.2311;Dba=36.4005;D34=64.0312;D45=130;L= 160.0781; X36=D3c+Dcd+Dd5+D56;Y36=D3c+Dcd+Dda+Da6;Z36=D32+D2b+Dba+Da6;M36=D34+D45+D56; S1=min(X36,Y36);S2=min(Z36,M36); S36=min(S1,S2); Z=X36,Y36,Z36,M36S36 r=S36/LFun10：求“P3-P7最短路径S37”及“最短路径S37与两点间直线L比例”D34=64.0312;D45=130;D56=85;D67=25;D3c=56.5685;Dcd=30.4138;Dd5=30.4138;Dda=65.1920;Da6=29.1548;D3