公园道路问题设计--数学建模案例选讲论文
数 学 建 模 案 例 选 讲
课 程 论 文
公园内道路设计问题
2012年5月21日
《数学建模案例选讲》课程论文题目和要求
方式：综合性作业 题目：公园内道路设计问题 要求：
(1) 根据题目要求，完成一篇完整的论文。论文包括模型的假设、建立和求解、计算方法的设计和计算机实现、结果的分析和检验、模型的改进等内容。
(2) 格式请参照下面给出的模版(语言表述与排版格式均计入成绩)。 (3) 凡抄袭的论文成绩为不及格。
《数学建模案例选讲》课程论文评语及成绩
摘 要
本题是一个道路设计最优化问题，讨论如何设计道路使矩形公园内道路总路程最短。且满足条件： (1) 第一问中，公园的所有入口和亭子都连通，并且用4个亭子作为道路的交叉点； (2) 任意两个入口之间的最短道路长度不大于两点连线的1.4倍。
第一问要求设计道路最短方案，先不考虑环路问题，构造最小生成树，再用贪婪算法，对不满足条件的路径进行替换，使新路径满足条件。得到最后的最短路设计方案。
第二问要求对任意位置的四个亭子，找出新的最短路径设计方案，可利用第一问方案，用1个亭子替换原来的4个亭子，再有2个亭子替换1个亭子，最后用新的4个亭子替换2个亭子。 关键词：最短路问题，最小生成树，贪婪算法，替换
1. 问题重述
学校准备修建一个长200米、宽100米的矩形公园。按照规划，将在公园的四周上设置8个入口、在公园内修建4个亭子。已知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)，4个亭子的坐标分别为：T1(50, 75)，T2(40, 40)，T3(120, 40)，T4(115, 70)，如图1所示。
图1 公园及入口示意图
现在需要你设计公园内的道路，使得：
(1) 公园的所有入口和亭子都连通，并且用4个亭子作为道路的交叉点； (2) 任意两个入口之间的最短道路长度不大于两点连线的1.4倍。
问题一：如何设计可使公园内道路的总路程最短？要求建立模型、给出算法、画出道路设计图，并计算出公园内道路的总路程。图2是一种满足要求的设计，但不是最优的。
图2 一种可能的道路设计图
问题二：如果公园内4个亭子的位置待定，如何设计可使公园内道路的总路程最短？要求建立模型、给出算法、给出道路交叉点(亭子)的坐标、画出道路设计图，并计算出公园内道路的总路程。
注：(1) 设计道路时，可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，但此道路不计入道路总长。
(2) 以上问题中都要求公园内修建的道路与四周的连接只能与8个入口相通，而不能连接到四周的其它点。
2. 基本假设与符号约定
为了简化问题和方便讨论，除问题中给出的假设外，我们进一步做如下的假设和说明：
(1) 假设目标公园平坦，没有湖泊等不能修建道路的区域，也没有丘陵、盆地等使道路弯曲、延长道路长度的区域。
(2) 假设目标公园内环境相同，除了4个亭子外，没有道路必须经过或必须不经过的特殊区域。 (3) 假设目标公园是一个矩形，公园门之间、亭子之间没有大小之分，全部可以视为点。 (4) 假设目标公园内和四周的道路没有宽窄之分，全部可以视为直线。 在此，我们也约定文中所用符号如下：
(1) Pi(i=1,2,3,4,5,6,7,8 表示公园入口1~8。 (2) Ti（xi，yi）（i=1,2,3,4）表示亭子1~4的坐标。 (3) Ai（i=1，2，…,11,12）表示公园入口与亭子共同的编号。
x11
x21(4) 0-1矩阵：Xxijxn1x12x1n
x22x2n
表示两点间是否有路径相通，其中
xn2xnn
xij
0,表示第i个和第j个点之间无连线1,表示第i个和第j个点之间有连线。
s12s1n
s22s2n
，sij表示在设计中第i个和第j个点间最短路
sn2snn
s11s21s(5) 最短路径矩阵：S=ijsn1
径长度。
d11d21(6) 限制矩阵：D = dijdn1
和第j个入口的直线距离的1.4倍。
d12d1n
d22d2n
（i，j=1,2,3,4,5,6,7,8）表示图中第i个入口
dn2dnn
3. 问题的分析
本题是一个道路设计最优化问题，讨论如何设计道路使公园内道路总路程最短，但要求满足条件
(1) 第一问中，公园的所有入口和亭子都连通，并且用4个亭子作为道路的交叉点； (2) 任意两个入口之间的最短道路长度不大于两点连线的1.4倍。
因为题目中默认矩形的四条边上存在已经建好的道路，因此可先利用四周道路，找出那些仅通过四周道路相连则不满足条件（2）的路径，在后续讨论中可优先考虑这些路径，使问题简化。通过计算，不满足条件（2）的路径有 P1-P5 , P1-P6 , P1-P8 , P2-P5, P2-P6 , P2-P7 , P3-P4 , P3-P5 , P3-P6 , P3-P7 。再根据各问题的具体要求进行讨论求解。
4. 模型的建立与求解
4.1 问题一的模型的建立与求解 4.1.1 模型的建立
建立连通网，8个入口和4个亭子就是网的顶点，道路就是两点之间的连线，道路长度就是连线的权值。因为在此题中有环路存在，因此不能直接用最小生成树法来求解，可结合贪婪算法求解。
求解过程分为四部步：
(1) 首先，不考虑环路问题，使用最小生成树法，得到一个初步道路设计方案。 (2) 然后，由得到的初步方案计算出任意两点间最短路径长度，做出最短路径矩阵。
(3) 接着，把最短路径矩阵与任意两入口直线距离的1.4倍的矩阵进行比较，得到不满足条件的路径。 (4) 最后，对不满足条件的路径进行替换，使得新路径满足条件，替换后的路径可以存在环路。
4.1.2 模型的求解
现有入口与交叉点共同的编号及其坐标：A1(20,0), A2(50,0), A3(160,0), A4(200,50), A5(120,100), A6(35,100), A7(10,100), A8(0,25), A9(50,75), A10(40,40), A11(120,40), A12(115,7).
现在分四步进行模型的求解：
(1) 利用MATLAB，根据克鲁斯卡尔算法，求得最小生成树，为了直观表示，做出网内各点是否有道路相连的0-1矩阵（0表示没有连线，1表示有连线）。
0
10000X
010000
[1**********]0
[1**********]0
[1**********]0
[1**********]1
[1**********]0
[1**********]0
[1**********]0
[1**********]1
[1**********]0
[1**********]1
000010 001010
同时用MATLAB绘制出对应的初步设计方案：
(2) 针对上面假设不存在环路而得到的初步设计方案，计算出目前8个入口最短路径长度，做出最短路径矩阵S88：
S88
0 30 260 324
203137 162 32
30 0 230 294 173 107 132 62 260 230 0 64 117 181 206 292 324 294 64 0 181 245 270 356 203 173 117 181 0 125 150 235
137 107 181
245
125 0
25 169
(3) 将上述最短路径矩阵与限制矩阵进行比较，限制矩阵表示任意两入口直线距离的1.4倍。
发现部分入口间最短路径不满足条件(2)（Sij≤Dij为符合条件，反之不符合），如下表中突出显示数据（由于路径无向，因此下三角不显示）：
对于部分入口，连接它们的园内最短路径比四周路径要长得多，园内最短路径不符合条件但四周路径符合条件吗，上表中已经对这些路径进行替换。
(4) 设计到的路径中可替换的边是有限的，利用穷举法，进一步得出满足条件的最优解，对应道路设
计方案图如下：
4.1问题二的模型的建立与求解
4.1.1 模型的建立
根据分析，当没有交叉点的时候，不满足条件（2）的路径有 P1-P5 , P1-P6 , P1-P8 , P2-P5, P2-P6 , P2-P7 , P3-P4 , P3-P5 , P3-P6 , P3-P7，因此它们之间必有园内路径。亭子位置、道路设计未定，可通过替换的方法，用1个亭子替换问题一中的4个亭子，再用2个亭子替换1个亭子，最后用4个亭子替换2个亭子，就得到新的亭子位置和最短路径设计。
4.1.2 模型的求解
根据分析，P1-P8、P3-P4之间必有园内的路径，下面不再进行分析。
（1）
亭子数为1时，设该亭子坐标为T1（x,y）。编写C语言程序（见附录1），令x从0至200，y从0至100变化（每次变化间隔为1），求得T1-P2，T1-P3，T1-P5，T1-P6路径总长最短的亭子坐标，同时要求满足条件（2）。得到结果为：没有满足条件的T1.
（2）
亭子数为2时，设亭子坐标为T1（x1,y1）和T2（x2,y2）。用2个亭子替换第一题中的4个亭子，显然，路径P2-T1-P6和P3-T2-P5都应该向中心凹，如图形状：
T1，T2限制在P6和P3之间，因此x1，x2应限制在[35,160],y1,y2限制在[0,100]之间。假设T1在T2左侧，编写C语言程序（见附录2），令x1，x2从35到160变化，y1，y2从0到100变化（每次变化间隔为1），求得T1-P2，T2-P3，T2-P5，T1-P6,T1-T2路径总长最短的T1，T2坐标，同时要求满足条件（2）。得到坐标T1(66,55),T2(107,63)。如图：
（3） 用新的4个亭子替换上面的2个亭子，假设这4个新亭子为T1（x1,y1）,T2(x2,y2),T3(x3,y3),T4(x4,y4)，且在图中为顺时针排序。显然，新的T1在T1-P6
（此处T1为上面2个亭子时的T1）路径附近，新的T2在T2-P5（此处T2为上面2个亭子
时的T2）路径附近，新的T3在T2-P3（此处T2为上面2个亭子时的T2）路径附近，新的
T4在T1-P2（此处T1为上面2个亭子时的T1）路径附近。于是有x1,y1,x2,y2,x3,y3,x4,y4
的移动范围为：
35≤x1≤66,55≤y1≤100; 107≤x2≤120,63≤y2≤100;
107≤x3≤160,0≤y3≤63; 50≤x4≤66,0≤y4≤55;
因此可编写C语言程序（附录3），令x1,y1,x2,y2,x3,y3,x4,y4在相应范围变化（每次变
化间隔为1）求得T1-P6，T2-P5，T3-P3，T4-P2，T1-T2，T2-T3，T3-T4，T4-T1路径总长
最短的T1，T2，T3，T4坐标，同时要求满足条件（2）。得到坐标T1（45，80）,T2（115,85），
T3（120,32），T4（55,40），此时园内路径总长为266.176。应认识到，这是没算上P1-P8、
P3-P4路径的，加上它们后得到路径总长为372.652.最短路径设计如图所示
：
5. 评价
本题是一个道路设计最优化问题，讨论如何设计道路使矩形公园内道路总路程最短。且满足条件：
(1) 第一问中，公园的所有入口和亭子都连通，并且用4个亭子作为道路的交叉点；
(2) 任意两个入口之间的最短道路长度不大于两点连线的1.4倍。
第一问要求设计道路最短方案，先不考虑环路问题，构造最小生成树，再用贪婪算法，对不满足条件的路径进行替换，使新路径满足条件。得到最后的最短路设计方案。
第二问要求对任意位置的四个亭子，找出新的最短路径设计方案，可利用第一问方案，用1个亭子替换原来的4个亭子，再有2个亭子替换1个亭子，最后用新的4个亭子替换2个亭子。
相对于整体考虑，先忽略部分问题进行求解，再把被忽略的问题考虑进去，修正方案，以及先用少量替换多量，再进行替换，都更为简便。
但是通过编写C语言程序来进行计算，编写有些复杂。
6. 附录
附录1：亭子数为1时求T1坐标的C语言源程序
#include
#include
void main()
{ int m,n,x,y,t=0;//(m，n)为移动中的T1坐标，（x,y）为T1的最终确定坐标，t用来确定是否存在满足条件的T1；
double s2,s3,s5,s6,s,l=1000;//s2,s3,s5,s6 为T1到P2,P3,P5,P6的最短路径,s为移动中他们的和,l为最终确定时他们的和
for(n=0;n
for(m=0;m
{
s2=sqrt((m-50)*(m-50)+n*n);
s3=sqrt((m-160)*(m-160)+n*n);
s5=sqrt((m-120)*(m-120)+(100-n)*(100-n));
s6=sqrt((m-35)*(m-35)+(100-n)*(100-n));
if((50+s2+s5
{
s=s2+s3+s5+s6;
if(s
{l=s;x=m;y=n;t=1;}
}
}
if(t==1)
printf(
else
} printf(
附录2：亭子数为2时求T1，T2坐标的C语言源程序
#include
#include
void main()
{ int m,n,p,q,x1,y1,x2,y2,t=0;//（m,n）,（p,q）为移动中T1，T2的坐标，（x1,y1）(x2,y2)为最终确定的T1，T2坐标，t用来确定是否存在满足条件的T1，T2
double s2,s3,s5,s6,s12,s,l=1000;//s2,s3,s5,s6,分别是T1-P2，T2-P3，T2-P5，T1-P6的路径长度，s是移动中他们的和，l是最终确定的他们的和
for(m=35;m
for(n=0;n
for(p=35;p
for(q=0;q
{ s2=sqrt((m-50)*(m-50)+n*n);
s3=sqrt((p-160)*(p-160)+q*q);
s5=sqrt((p-120)*(p-120)+(100-q)*(100-q));
s6=sqrt((m-35)*(m-35)+(100-n)*(100-n));
s12=sqrt((m-p)*(m-p)+(n-q)*(n-q));
if((30+s2+s12+s5
{ s=s2+s3+s5+s6+s12;
if(s
}
}
if(t==1)
printf(
else
printf(
}
附录3：亭子数为4时求T1，T2，T3，T4坐标的C语言源程序
#include
#include
void main()
{ int a,b,c,d,e,f,g,h,x1,y1,x2,y2,x3,y3,x4,y4,t=0;//(a,b)(c,d)(e,f)(g,h)为移动中T1，T2，T3，T4坐标，(x1,y1)(x2,y2)(x3,y3)(x4,y4)为最后确定的T1，T2，T3，T4坐标，t用来确定是否存在满足条件的点T1，T2，T3，T4
double s2,s3,s5,s6,s12,s23,s34,s41,s25,s36,s,l=1000;//s2对应T4-P2，s3对应T4-P3，s5对应T2-P5，s6对
应T1-P6，s12,s23,s34,s41为T1，T2，T3，T4彼此路径，s25对应P2-P5，s36对应P3-P6
for(a=35;a
for(b=55;b
for(c=107;c
for(d=63;d
for(e=107;e
for(f=0;f
for(g=50;g
for(h=0;h
{ s2=sqrt((g-50)*(g-50)+h*h);
s3=sqrt((e-160)*(e-160)+f*f);
s5=sqrt((c-120)*(c-120)+(100-d)*(100-d));
s6=sqrt((a-35)*(a-35)+(100-b)*(100-b));
s12=sqrt((a-c)*(a-c)+(b-d)*(b-d));
s23=sqrt((c-e)*(c-e)+(d-f)*(d-f));
s34=sqrt((e-g)*(e-g)+(f-h)*(f-h));
s41=sqrt((a-g)*(a-g)+(b-h)*(b-h));
if(s34+s23>s41+s12)
s25=s2+s41+s12+s5;
else
s25=s2+s34+s23+s5;//找出P2-P5最短路径
if(s34+s41>s12+s23)
s36=s3+s12+s23+s6;
else
s36=s3+s34+s41+s6;//找出P3-P6最短路径
if((30+s25
{ s=s2+s3+s5+s6+s12+s23+s34+s41;
if(s
{ l=s;t=1;
x1=a;y1=b;
x2=c;y2=d;
x3=e;y3=f;
x4=g;y4=h;
}
}
}
if(t==1)
printf(
printf(
}