公园道路设计.doc

2012高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B
我们的参赛报名号为（如果赛区设置报名号的话）： J2035
所属学校（请填写完整的全名）： 西安财经学院
参赛队员 (打印并签名) ：1. 史亚峰
2. 马芳
3. 汪妮
指导教师或指导教师组负责人 (打印并签名)： 向新银

日期： 2012 年 9 月 10 日

赛区评阅编号（由赛区组委会评阅前进行编号）
2012高教社杯全国大学生数学建模竞赛

编 号 专 用 页

赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

评
阅
人

评
分

备
注

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

摘 要
西安某大学要求在校园内建立公园来美化环境，同时为大学生提供良好的学习氛围。公园内有8个入口，要求8个入口之间两两连通且任意两点之间的路程不大于其直接连线长的1.4倍，针对这个问题，本论文作出如下解决方案：
问题一中题设给出4个固定的道路交点，结合8个入口，得出12个点的距离矩阵，利用克鲁斯卡尔算法绘制出最小生成树，根据题设的限制条件对其进行优化，最终求出最短路径为394.55米。
问题二中没有具体给出道路交点，首先应r1的要求，8个入口中以任意两个入口为焦点，两入口直线距离的1.4倍为长轴长绘制椭圆，由多个椭圆的公共区域确定道路在公园内部的交点存在的范围，编写C++程序解出公园内道路交点分别为F1（60,78）、F2（173,44），最短路径和为358米。
问题三在问题二的限制条件上加入新的限制条件，即在公园内部增设一个矩形湖。经分析可知，矩形湖的存在仅影响了P3、P4、P5三个入口之间的连通。构造函数，得到入口P5、P4、P3与矩形湖的交点坐标，求得最短路径和为342.72米。

关键字：公园道路设计 最短路径 克鲁斯卡尔 椭圆域
目 录
1. 问题重述 3
2. 问题分析 3
3. 基本假设 4
4. 符号说明 4
5. 模型建立与求解 5
5.1 给出固定交叉点的问题求解 5
5.1.1 克鲁斯卡尔模型的建立 5
5.1.2 用Matlab求最小生成树 5
5.1.3 根据条件优化 7
5.2 没有固定交叉点的问题求解 8
5.2.1 椭圆域模型建立 8
5.2.2 交叉点的求解 9
5.3 增加湖后的问题求解 11
6. 模型评价 13
6.1 模型的优点 13
6.2 模型的缺点 13
7. 模型推广 13
8. 参考文献 14
9. 附录 14

1. 问题重述
西安某大学为了美化校园，并为学生提供更好的生活学习环境，计划在校园内建设一个形状为矩形或其他不规则图形的公园。公园设计有若干入口，需要建立模型设计道路，使得任意两个入口相连总路程最小。设计过程中的限制条件为：任意的两个入口之间的最短道路长度不大于两点直接连线的1.4倍。如图1所示的长200米宽100米矩形框内，存在8个入口，p1（20,0），P2（50,0),P3（160,0），P4(200,50)，P5（120,100），P6（35,100），P8（0,25），需解决道路设计问题如下：
问题一:题设要求公园内只有4个道路交叉点，分别为：A（50,75），B（40,40），C（120,40），D（115,70）。设计道路使公园内的道路总长最短，建立模型给出算法，画出道路设计，并计算新修道路的总路程。
问题二：公园内可以任意修建道路，求在满足条件的同时使总路程最短的道路设计，建立模型并给出算法，得出道路交叉点的坐标，画出道路设计，计算新修道路的总路程。
问题三：如图3所示，当公园内有一条矩形湖时（新修的道路不能通过，但可以到达湖四周的边），重复完成问题二的任务。矩形湖中各点坐标分别为：R1（140,70），R2（140,45），R3（165,45），R4（165,70）。
注：以上问题都要求公园内新修的道路与四周的连接只能与8个路口联通，而不能连到四周的其他点。
2. 问题分析
经分析发现该问题是一个在图论的基础上求最小距离的问题。距离最短是为了使修建公园工程费用最小。而公园内人类的活动方式不求路程最小。最主要考虑工程代价，次之考虑人类活动的路程。
公园四周道路已建好，我们尽可能的利用这些道路以节约工程费用。但是这些路可使各点连通，考虑到建设公园的意义，我们不能将道路造价降到“0”。所以我们必须在园内修建道路。
针对该问题我们做出如下具体分析：
问题一：公园内只有4个道路交叉点，且各个入口可以直接或间接到达。所以求最短距离时我们可将8个入口和4个交叉口结合形成一个12×12的矩阵，用Matlab求出各点到其他点的最短距离。根据所求得的最小距离绘制成图，依照所需满足的条件如：
1.利用公园四周可节约费用
2.园内不形成其他新的交叉点
3.任意两点连通
4.任意的两个入口之间的最短道路长度不大于两点直接连线的1.4倍。
问题二：当没有确定的交叉点及交叉点数目时，我们应该围绕交叉点展开讨论，建立多少个交叉点合理？交叉点建在那里合理？这些问题就要求结合一系列的约束条件找到合理的交叉点坐标，绘制出设计图。根据限制条件对其进行优化，得出最终结果。
问题三：利用第二问的结果找到受影响的点。要求道路可到达湖，且距离最短，所以湖边上一定存在一个点使得它们满足条件。所以我们可以将问题转化成求这个点坐标的问题。求出坐标后计算出总路程，总路程中应该包括绕湖边的路程和修建的路程，不包括利用公园四周边的道路。

3. 基本假设
1、假设公园内任何地方都适合修路；
2、假设所有点间的道路均修建为直线；
3、交叉点的修建不影响道路总长。

4. 符号说明
r1
满足两点之间直接距离的1.4倍不大于连着两点之间总长度的条件
r2
满足最短距离的条件
S
最短路径的矩阵
D
两点之间直接距离的1.4倍的矩阵
Pi
第i点
Pj
第j个点
Vij
第i点和第j点之间的路径长
5. 模型建立与求解
5.1 给出固定交叉点的问题求解
5.1.1 克鲁斯卡尔模型的建立
题目中给出4个固定的交叉点，我们最终要达到的目的是设计出满足条件r1和r2的图，所以我们分为一下三步：
第一步：我们要将点与点之间的坐标关系转化成线的连接关系，所以我们首先必须求出任意两点之间的距离。由于4个交叉点是固定且不能新增加交叉点，所以我们需要将8个入口和4个交叉点结合，用Matlab软件输入12个点坐标，求出一个12×12的距离矩阵。
第二步：距离矩阵中的数据是一个点到其他11个点的距离，但是任何一点都会存在另外一点使得到达它的距离最短，所以在这一步中我们将要完成的是找到最短路径绘制出最小生成树，基于这一目的，我们根据第一步得到的距离矩阵采用克鲁斯卡尔（Kruskal）算法做出最小生成树。由于做出的是最小生成树，所以任意两点之间的距离就是最短距离，所以到这一步的设计是满足r2的。
第三步：由于受到r1的限制且我们找到的最短路径中有可能存在不满足r1的路。所以我们要生成8个入口最短路径矩阵S和它们之间直接距离的1.4倍的矩阵D，通过这两个矩阵的比对找出不满足r1的路径作为需要优化的路径。最后利用穷举法找到最短路的优化方法，绘制成最后的图并算出总长度。
5.1.2 用Matlab求最小生成树
首先，用Matlab输入12个点的坐标，分别是p1（20,0），P2（50,0),P3（160,0），P4(200,50)，P5（120,100），P6（35,100），P8（0,25），A（50,75），B（40,40），C（120,40）生成距离矩阵（代码如附录1所示），如下图表1示：
表1： 距离矩阵

接着，用克鲁斯卡尔算法找出最短路径及其之间的距离，矩阵如表2所示：
表2 最小生成树
入口1
入口二
距离
P1
P2
30
P2
B
41.23
B
A
36.4
A
P6
29.15
P6
P7
25
A
D
65.19
D
C
30.41
C
P3
56.57
P3
P4
64.03
D
P5
30.51
P1
P8
32.02
根据上表利用几何画板画出如图1所示的最小生成树：

图1 最小生成树
注：图中较粗的线条为设计的道路，细线条表示公园周围的路，下同。
5.1.3 根据条件优化
最后，由于需要判断各路线是否符合r1的要求则要根据图一的最小生成树求出最短路径的矩阵S：

利用最小生成树的矩阵与入口之间的直接距离的1.4倍作对比，所以生成矩阵D：

通过对比得出P2到P5的直接距离的1.4倍小于最短路径距离所以需要优化。
通过穷举法计算出应该以P5—>A优化A—>D使之满足条件r1。
所以最终画出的最优设计如图2所示：

图2.最优设计
最后得出最短路的总道路长度是394.55米。
5.2 没有固定交叉点的问题求解
5.2.1 椭圆域模型建立
在这一问中没有确定的交叉点，我们必须找到交叉点，而交叉点集中在哪几个区域就应该有几个交叉点，最后在交叉点集中的区域里进行线性规划，以最短距离为目标函数找到交叉点的坐标。在这一问中我们可分为两步：
第一步：目标是用r1条件限制来缩小交叉点所在的区域的大小。
因为所有点都应该满足r1，设出交叉点F，所以交叉点应该满足到任意两点的距离满足和不大于1.4倍的两点的直接距离，则用公式表示为：
|FPi|+|FPj|≤1.4|PiPj| （1）
而从这一公式中看出交叉点F的轨迹满足椭圆的概念，此椭圆是以任意两点之间的直接距离的1.4倍为椭圆的长轴，以直接距离为焦距。椭圆轨迹上的点集合和椭圆内部的点都满足r1的。所以用matlab作2C=|PiPj|，2a=1.4|PiPj|的椭圆（i=1,2，3，……，8；j=1,2,3，……,8）,它们所交的公共区域的点定满足r1。
第二步：目的在于用线性规划的思想确定出交叉点的坐标。
在第一步中，利用椭圆的思想缩小了交叉点的区域，接下来，我们就在这几个区域内以区域边界为约束条件，以r2条件作为目标函数，规划出交叉点的坐标。但是，区域不唯一，在不同区域内并行线性规划。在这一步中运算量大，我们借助计算机，利用C程序将其运算出来。
5.2.2 交叉点的求解
第一步：通过对8个入口坐标的分析，得出有的点是在同一边上的一对点，有的是可以通过公园外边的线路，除去这些线路，保留的线路有：P1->P6,P1->P8,P2->P5,P2->P6,P2->P7,P3->P4,P3->P5,P3->P6,P3->P7,P4->P5,所以需要10个椭圆，找出公园内部中相交区域多的区域作为下一步规划的区域。如下图3所示：

图3.椭圆的相交区域显示图
第二步：经过分析推测，可以得出两种优化方案，如图所示，分别对两种情况利用C程序进行对比论证。
H形算法：此时1-8，3-4这两组点已为定值，则计算V15，V16,V25,V26,V27,V35,V36,V37这些点之间的路径长。其中V36有3-10-5-6,3-10-9-6,3-2-9-6这三种路径，V37有3-10-5-6-7,3-10-9-6-7,3-2-9-6-7这三种路径。利用公式：
(2)
且满足两个入口之间的最短道路长不大于两点连线的1.4倍这个条件。编写程序，将已固定的区域范围划分为无数个极微小的点，使交叉点在这些点上依次运算一遍，最后由程序比较获得最短路径长及此时的两交叉点近似坐标。（代码及其结果见附录3）
此时1-8组点已为定值，则计算V25，V26,V35,V36,V37这些点之间的路径长。其中V36有3-10-5-6,3-2-9-6两种路径。套用H形的方法编写程序后进行运算求解出最短路径及此时的交叉点坐标。
编辑程序可获得交叉点坐标为（60,78），（173,44）。

图4.问题二的最优设计
经计算得出的最优路径的最短路程为358米。
5.3 增加湖后的问题求解
结合问题二中的优化结果与问题三提出的要求，得图5：

图5.存在湖后的图4
从图中可以看出，湖的存在使得道路P5->F2受阻，因而影响到F2->P3和F2->P4，即影响了P3、P4、P5三个入口的连通而对其他入口没有影响。所以只需对P3、P4、P5点之间的道路重新进行优化。
优化本着边优先原则，以及满足题中所给出的限制条件r1、r2，利用两点之间线段最短的原理对其进行优化，优化构成如下：
现在，我们应该做出即可以到达湖而且满足r1和r2的路径。
所以在湖边上存在点使得到达湖边的距离L于绕湖走的距离之和最短。设边R1R4上存在一点（x，70）使得P5到达只一点的距离在[140,165]的范围内存在最小值，存在的函数关系是:
，x∈[140,165] (3)
求得最优解得坐标是（165,70）即R4点。同理，在R3R4上存在一点（70，y），存在函数关系:
,y∈[45,70] (4)
求得最优解的坐标为（165,70），即为R4.
所以结果如图6所示：

图6问题三的最优设计
经检验，这种优化方式满足r1和r2
所以得出最短道路总长为：
P1P8+P2F1+F1P6+F1P5+P5R4+R4P4+P4P3=32+78.64+33.09+63.91+30.74+40.31+64.03=342.72米
6. 模型评价
6.1 模型的优点
(1)利用了现成的软件计算，设计结果准确，运算方便。
(2)不仅适用于存在不确定性和主观信息的情况，还以合乎逻辑的方式运用经验和直觉给不同的因素赋权，建立了外界作用，通过使权值改变来影响总长度的的机制。
(3)能将相关性不大的两个指标通过中间层的过渡连接起来，使问题分析变得有条理，有根据。
(4)穷举方法少，用函数的方法经过计算得结果，降低了穷举法所带来的数据量大、计算复杂的缺点。
6.2 模型的缺点
因为计算结果大多是通过计算机软件得出的，从而使得数学的计算方法变少，给人以缺少说服力的感觉。而Matlab就是一个数学软件，采用的就是数学的思想，所以在这个问题里就不用过多的考虑这一点了。
7. 模型推广
最短路径法是一种常见的设计方法，它可以利用于建筑选址，车辆安排，公路系统设计，网络路由等方面，主要是通过改变带权求出最小带权值的方法实现。而应用的领域就在于带权值的意义。
椭圆的思想也是一个比较巧妙，应用范围广泛的模型思想，可以用在建筑测量，地质定点等需要选择合适范围的应用中，是一个对象为离散型数据的模型思想。能帮不规律出现的数据找到它们的共同点，从而缩小数据范围。

8. 参考文献
[1]百度百科吧 http//
[2]赵静、但琦，《数学模型与数学是实验》第二版，北京高等教育出版社，2003.06.02
[3]耿国华，《数据结构-C语言描述》第二版，西安电子科技大学出版社，2008.07
[4]刘振航，梁邦助，《数学建模》，中国人民大学出版社，2004.05
9. 附录
附录1：问题一中Matlab编程实现距离矩阵
clear;
n=input('请输入点的个数：');
x=zeros(1,n);
y=x;
for i=1:n
disp(['请输入第',num2str(i),'个点的坐标']);
x(i)=input('x=?');
y(i)=input('y=?');
end
r=zeros(n,n);
for j=1:n
for k=1:n
r(j,k)=sqrt((x(k)-x(j))^2+(y(k)-y(j))^2);
end
end
附录2:题二中有关椭圆的文献资料
椭圆的定义：平面内与两点F1、F2的距离和等于常数2a.
|PF1|+|PF2|=2a，2a为长半轴

附录3：问题二中的实现代码与运行结果
#include <stdio.h>
#include<math.h>
void main()
{
double x0,y0,x1,y1,x01,y01,x11,y11,d15=197.96,d16=141.54,d25=170.94,d26=141.54,d27=150.78,d34=89.6,d35=150.78,d36=224.14,d37=252.28,
v15,v16,v25,v26,v27,v34,v35,v36,v361,v362,v37,v371,v372,s=10000,f,s1,s2,s3,s4,s5,s6,s7,s8;
for(x0=0.5;x0<=120.0;x0=x0+1)
{
for(y0=0.5;y0<=80.0;y0=y0+1)

for(x1=120;x1<180;x1=x1+1)
{
for(y1=0.5;y1<100;y1=y1+1)
{
s1=sqrt((x0-50)*(x0-50)+y0*y0);
s2=sqrt((x0-35)*(x0-35)+(y0-100)*(y0-100));
s3=sqrt((x0-120)*(x0-120)+(y0-100)*(y0-100));
s4=sqrt((x1-160)*(x1-160)+y1*y1);
s5=sqrt((x1-120)*(x1-120)+(y1-100)*(y1-100));
s6=sqrt((x1-200)*(x1-200)+(y1-50)*(y1-50));
v25=s1+s3;
v26=s1+s2;
v27=v26+25;
v15=v25+30;
v16=v26+30;
v35=s4+s5;
v361=v35+85;
v362=v26+110;
v36=v361>v362?v362:v361;
v37=v36+25;
v34=s4+s6;
if(v25>d25||v26>d26||v27>d27||v15>d15||v16>d16||v35>d35||v36>d36||v37>d37||v34>d34)
continue;
f=s1+s2+s3+s4+s5+s6;
if(f<s)
{
s=f;
x01=x0;
y01=y0;
x11=x1;
y11=y1;
s7=s1;
s8=s2;
}
}
}
}
}
printf("the min distance is%f,x1=%f,y1=%f,x2=%f,y2=%f\n",s+32,x01,y01,x11,y11);
}

附录4：题目参考图形

图 1 公园及入口示意图

图 2 一种可能的道路设计图

图3 有湖的示意图

19