陇东学院第二届大学生数学建模竞赛

承 诺 书

我们仔细阅读了陇东学院数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属院系（请填写完整的全名）： 数学与统计学院 参赛队员 (打印并签名) ：1. 刘红蕊

指导教师或指导教师组负责人 (打印并签名)：

日期： 2012 年 5 月 27 日

校园景观道路设计

摘 要：本题是一个道路优化问题。着重对道路入口和园内交叉点的分析，选取更优道路。利用三角形外接圆圆心，确定园内的交叉点的个数，再利用所给数据和实际情况进行分析，去掉不必要的路段，选定景观园内的交叉点，由此获得园内更优道路图。

问题一回答：通过对道路的入口点以及园内道路的交叉点的数据分析，依据题目所给的要求，从而得出园内不必要存在的路段，为最终的优化提供依据。 问题二回答：通过对道路入口构造三角形，确定其外接圆圆心，由此得到园内道路的交叉点，从图中绘出具体位置，再依照数据和实际情况进行更优道路的选取。

本文对模型的求解主要进行了数据分析和对实际情况的考虑，对园内交叉点的位置确定。

关键词：道路优化；数据分析；外接圆圆心；优化选取。

一、问题重述

我校计划在逸夫教学楼与信息楼之间建一个形状为矩形或其他不规则图形的校园文化景观中心，不仅为了美化校园环境，也是想为其学生提供更的生活条件。该中心计划有若干个入口，现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的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，其中图2即是一种满足要求的设计，但不是最优的。

图 1 公园及入口示意图

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

现完成以下问题：

问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。

问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。

注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。

二、符号说明

O1：为三角形P3P4P5的外接圆圆心；

O2：为三角形P1P3P8的外接圆圆心；

O3：为三角形P5P7P8的外接圆圆心；

O4：为三角形P1P2P8的外接圆圆心；

O5：为三角形P6P7P8的外接圆圆心；

O6：为三角形P2P3P8的外接圆圆心；

O7：为三角形P5P6P8的外接圆圆心；

S18：为为P1到P8的距离；

S13=S14=S15：分别为O1到P3、P4、P5的距离；

S21=S23=S28：分别为O2到P1、P3、P8的距离；

S26：为O2到P6的距离；

O12：为O1到O2的距离；

O13：为O1到O3的距离；

S32：为O3到P2的距离；

S36：为O3到P6的距离；

S1：为景观园内所有道路距离的总和；

S2：为景观园内所有道路距离的总和。

三、模型假设

1.假设校园景观中心为矩形；

2.园内道路没有弯曲；

3.对所构造的三角形外接圆圆心的确定能够实现。

四、问题分析

本题是一个实际问题的优化。首先，利用数据和实际问题的分析以及题目的要求，在景观园入口和园内交叉点之间进行优化选取道路。其次，利用入口所构造的三角形进行三角形外接圆圆心位置的确定，然后在图中标出具体的位置，再利用数据和实际情况进行分析和选取园内相应的交叉点，进行连接和计算。最终，得到优化道路示意图。

一、问题一的关键

1.以题目的要求，任意的两个入口之间的最短道路长不大于两点连线的1.4倍，由此分析得出园内不必要存在的道路。

2.再在所剩的道路中进行更优选取，连接入口和交叉点，得到景观园内道路

示意图。

二、问题二的关键

1.确定景观园内的交叉点。利用三角形的外接圆圆心坐标进行具体定位；

2.依据实际情况和数据分析，对交叉点和入口进行选择性连接；

3.对数据进行计算，选取更优的景观园内道路示意图。

五、模型建立与求解

一、问题一的回答

利用数据进行分析八个入口之间的最经路段，

P7-P6 P7-A-P6=76.33>1.4P6-P7

故只能从P6-P7 (因A距P6P7最近，估值考虑A点)

P6-P5 P6-A-P5=103.49<1.4P5P6

故可以从P6-A-P5

P6-P5 P6-D-P5=115.85<119

故可以考虑P6-D-P5

因为P6-A-P5<P6-D-P5 所以选点A

P5-P4 P5-D-P4=117.73<132.08

故可以考虑从P5-D-P4

P4-P3 P4-C-P3=172.61>89.64

故 只能P3-P4 (由于D距P3P4最近，故只考虑D)

P3-P2 P3-C-P2=152.73>151

故只能从P3-P2

P2-P1 P2-B-P1=85.75>42

故只能从P2-P1

P1-P8 P1-B-P8=85.03>56.43

故只能从P1-P8

P7-P8 P7-A-P8=117.89>92.08

故只能从P8-P7 (由于边长不计入总路长，故P7-P8不修景观园内道路)

由此分析得图3如下：

图 3

考虑线路最短只能连接P1-B,或P2-B，或P3-B，

因为P8-B、P1-B、P2-B最短为P2-B 所以选择P2-B

对于P5、P4、D，由于D为交点，故P4-D和P5-D至少选一个

因为P5-D=30.41 P4-D=87.32 P4-C=100.50 P4-P3=64.03

所以选取P5-D和P3-P4

由此，得到图4：

图 4

因此，全长S=421.51

故最短路长为：421.51。

二、问题二的回答：

经过数据的分析计算（由两点所在的直线得其斜率，再由垂直直线的斜率关

系及两点的中点坐标得到两点所在的垂直平分线，利用两条垂直平分线的交点得到外接圆的圆心），分别得到相应的三角形外接圆的圆心坐标数据，如图5：

利用图5的数据，在坐标图中标出具体的圆心位置，如图6： 图 6

1.经数据分析和实际道路的选取，以及图6中所有点的位置推测得到一种可能的景观园内道路示意图，如图7。在O2P1和O2P8的选取中O2P8更符合实际情况（这样更利于入口得到均衡分配，其中：O2P1=O2P8）。

图 7

经分析计算得出景观园内道路的总长S1（园内所有连接点利用两点之间的距离公式求得），数据如图8所示：

故 S1=S13+S14+S15+O12+S26+S28+S18=534.93

2.经数据分析和实际道路的选取，以及图6中所有点的位置推测得到另一种可能的景观园内道路示意图，如图9所示。在O3P2、O2P8、O3P1中选取O3P2所在的道路（因为：O3P2<O2P8<O3P1）。

图 9

经分析计算得出景观园内道路的总长S2（园内所有连接点利用两点之间的距离公式），数据如图10所示：

故 S2=S13+S14+S15+O13+S36+S32+S18=399.84

六、误差分析

1.到三角形三顶点的距离最近的点不一定是三角形的外接圆圆心；

2.在实际确定三角形的外接圆圆心的过程中存在误差；

3.数据的计算过程中存在误差； 七、模型推广

对问题二的分析中，是在假定三角形的外接圆圆心到三顶点的距离最短的情况下进行分析的，由此分析计算出的路径不能达到最优。

八、模型的应用

本模型可适用于景观园内道路的设计规划，以及城市内的道路设计规划；也可作为外出旅游和生活中最优路径的选取。

九、模型评价

模型的优点：应用了三角形的外接圆圆心，从而直接确定了景观园内道路的

交叉点，避免了由一点到多点的逐个排除。

模型的缺点：在分析问题一的时候进行逐个判断，增加了问题的繁杂度，给数据的处理带来了一定困难；在分析问题二的时候，三点之间的最短距离的确定不够精确，使模型的结果不能达到最优。

十、参考文献

[1] 胡运权，《运筹学教程》第三版，清华大学出版社。

[2] 李长明 周焕山，《初等数学研究》，高等教育出版社。