建模学习讲座基于图论的公园道路设计方案

公园内的道路进行设计，这样有利于改善学校环境，同时为学校节约大量（0修道路的最短总路394.55968m。：模型二点最小树距离的逐步调优法。我们在没有确定交叉点的情况下，利用避圈法求出8个正则点的最小树，通过在公园矩形内增加6个辅助点来大致确定交叉点的位置再采用最小树的逐步调优法来逐步确定交叉点的G（65.94,71.59，H（168.96,40.25（117.26，87.72，357.6918m。：R2,R4R2(140,45),358.946m：最小生成树逐步调优法一、问题重长度和最小，前提要求是任意的两个之间的最短道路长不大于两点连线1.4100米，1至8各的坐标分别为P5(120,100),P6(35,100),P7(10,100),P8(0,25C(120,40)，D(115,70的边，示意图见图3。重复完成问题二的任务。其中矩形的湖为R1(140,70),R2(140,45),R3=(165,45),R4=(165,70

二、问题假设和符号假设每个都可以看成是一个点 交叉xA,xB,xC,

A,B,C,DyA,yB,yC,

A,B,C,D三、问题分（道路不计入总长，并且要求满足任意的两个之间的最短道路长不大于两点1.4法，用编程画出最小生成树。再在考虑公园四周的道路不计入总长（0的路程选择满足任意的两个之间的最短道路长不大于两点连线的1.4倍算最后确定的方案的总路程，并画出设计图。公园内总路程最短。我们首先利用避圈法求出8个正则点的最小树，通过在公园矩形内增加6个辅助点来确定交叉点的位置再采用最小树的逐步调优[2]来逐步确定交叉点的位置，找出最短总路程。最后，在满足任意的两个间的最短道路长不大于两点连线的1.4倍的道路的条件下，进行手动修正，画出四、模型建立与求基于避圈法[1]的公园里道路的最短总路生（2通过编程画出公园内部最小生成树如图ADB1则在考虑公园四周的道路计入总长的情况下，公园内部最短路道路为0),则公园内部的最短路385.4214m。但是题目要求任意的两个之间的最短道路长不大于两点连线的1.4P1P5P2P5ADB2394.55968m。基于点最小树距离的逐步调优（1）点的坐标计算点的定义[3：要在ABCF,F形的三顶点的距离之和最小，则称F点为点。xBxBxC，可得如下结论，证明见文献[4]EEADFBC图 点的几何作当点A段BC之上方，即

y(xAxByCyB) xxxAxB

3(2

AyB)

yE

yAyB2

32

AxB

xxAxC

3(2

AyC)

yyAyC

32

AxC

当点A段BC之下方，即

y(xAxByCyB)x xC BCBxxAxB

3(

yB)

yE

yAyB2

3

xB

xxAxC

(2

AyC)

yyAyC

32

AxC

x然后求线段CE与BD的交点就得点F的坐标。若分别用kCE与kBDxCEBD

yCyE,

yB

则易求 点F的坐

xC

B

x(kBDxByB)(kCExCyC

，yy (xx

kFk

利用（6）（2）树的性质1、树上任何一个顶点v的度至多是3，即d(v)32、树上每个辅助点都是点3、若树的正则点共有n个，则点的数目至多是n-2个4、树的每个点都必定包含在全部正则点的最小凸包内5、树的每个1度点都是正则点1Z的最小生成树T0 图4公园的8个所构成的最小生成2、依次让k16，在矩形R[0,200[0,100]内随机投放kFF,然后用避圈法计算出F

Tk3

1Sk1

nSj

(k1,2,,n

kkqkPi,(k1,2,,ni4、产生一个[0,1]均匀分布的随机数r，若满足qk1rqk，则对Tk的要好，则替换它，否则Tk不变。5重复步骤3和4，直到达到预设的最大迭代次数为止此时的最好解记为T6、统计T中各辅助点的度7T12边。若有3度辅助点，一般它不是点，需要校正，调整后得到新的T。0867，10TT，则输出T0出T0经过编程，得到在没有给出交叉点的情况下公园内总路程最短5（168.96,40.25（117.2687.72路357.6918m。6图66K-HK-H计。若借助湖边的道路来使K到达H，由假设若沿湖建路，则所修道路的长度要计入路程总长，故需四条直线才使K到达H，不符合两点之间直线最短，故考虑R4、R2KH，K、HR45K-R4-HG-K-5R4-K-5G-5-R4的坐标为(x4,y4在△P4P3R4H-R4H-4、H-3d(x4min(x40

LINGO（8）H(184.09,48.95)所连之后的任意两之间的最短道路长全满足不大于两连线点之间的1.4361.4300m7图7R4R25，K-R2-HG-K-5、R2-K-5G-5-的距离近似相等，故可将K5H点的坐标为(x5y5，可以利用模型一的方法在△P4P3R2(x160)2(x160)2y555x34y38004x37y3115014x3y32240

(x(x200)2(50y55(x140)2(45y55图8R2M

(x6y6。GH进行确定，设调整后的GH(x7y7

(x8,y8

进方案，建立非线性规划模型，然后根 日原理建立出如下等式(xx)2(xx)2(yy (x50)2y77(x(x200)2(50y88(x140)2(45y66(x(x120)2(y66(x35)2(y77(x(x160)2y88(x35)2(y77

利用LINGOM,G,H(69.07,63.96)G，(112.32,74.27)M,(161.75,30.73)H99在图9不存在三角形可继续优化在此方案下最短路程长为358.946。经过比较最短路程长，最终选择模型二作为最后方案，四个交叉点分别为(69.07,63.96)G,(112.32,74.27)M,(161.75,30.73)H,2(140,45)R，总路程长358.946m。

五、模型评价与推1Kruskal2、在模型二中采用点的扩展点，优化解决问题的方式，应用逐步仓库、急救中心、消防站、处理中心、物流中心、仓库的选址等。2、最小生成树可以网络设计，城市高速公路，电子线路设计应用六、参考文[1]，建模的数学方法和数学模型..科学[2]，，，.求解欧氏距离最小树的逐步调优法.2011.年青年通信国际会议（ICY2011） [3].数学模型 高等教育.2004,5:46-[4]，关于点的几点注解[J].华南理工大学学报，2004,32（193-七、附第一问生成最小生成树的程序functionx=[20 1005040120y=[0005010010010025754040fori=1:nfor%KruskalM-格式 顶点Wt为最小生成树的权,Pp(:,1:2)为最小生成树边的两顶点%Pp(:,3)为最小生成树的边权,Pp(:,4)为最小生成树边的序号%%%%%%Byqinyuanw=W(tmpa);e=[tmpb,tmpc];%wWinf元素按列构成的向量[nE,mE]=size(E);%sort数组排列while(rank(E)>0)forif(E(i,1)==temp1),E(i,1)=temp2;if(E(i,2)==temp1),E(i,2)=temp2;end;iffori=1:length(P(:,3));%viejdisp(['','e',num2str(P(i,4(v',...num2str(P(i,1)),'','v',num2str(P(i,2)),')']);axisequal;holdon[x,y]=cylinder(1,n);xm=min(x(1,:));ym=min(y(1,:));xx=max(x(1,:));yy=max(y(1,:));yy+abs(yy)*0.15]);plot(x(1,:),y(1,:),'ko')fori=1:n;temp=['text(x(1,i),y(1,i),temp);fori=1:nE;plot(x(1,e(i,:)),y(1,e(i,:)),'b');end;fori=1:length(P(:,4));text(-0.