公园内道路设计问题..docVIP

2012A公园内道路设计问题 西安某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更的生活条件。公园计划有若干个入口，现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的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即是一种满足要求的设计，但不是最优的。 现完成以下问题： 问题一：假定公园内确定要使用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个路口相通，而不能连到四周的其它点。 图 1 公园及入口示意图 图 2 一种可能的道路设计图 图3 有河的示意图 问题1结果 S=394.56米 问题2 1) 在问题1中结果中,可将A-P2和P3-P5直接连接,则显然依然,满足要求,且总距离减小.为382.24米. 2)在P2,P5和P6之间优化A(x1,y1)点,使AP6+AP5+AP2最小. 在P4-P3-P5之间加入一点B(x2,y2) 使BP3+BP4+BP5最小 问题1中直接连接A-P2和P3-P5的结果 S=382.24 设,目标函数为: 满足约束: 计算结果:Lingo优化得到的结果A(59.70986,77.62929),总长度为S=379.62米 设,目标函数为: 满足约束: 计算结果,优化B点,得到B(173.0980,43.64328),总长度为S=358.53米. 总长度S= 358.53 Lingo程序: model: sets: number/1..8/; xy/1..2/; Biao(number,xy):P; endsets data: P=20,0, 50,0, 160,0, 200,50, 120,100, 35,100, 10,100, 0,25; enddata min=Z1+Z2; !A点结果?; Z1=A2+A5+A6; A2=((x1-P(2,1))^2+(y1-P(2,2))^2)^0.5; A5=((x1-P(5,1))^2+(y1-P(5,2))^2)^0.5; A6=((x1-P(6,1))^2+(y1-P(6,2))^2)^0.5; d15=p12+A2+A5; !p1,p5最短距离; d16=p12+A2+A6; !p1,p6最短距离; d25=zx2+zx5; !p2,p5最短距离; d26=zx2+zx6; !p2,p6最短距离; d15=1.4*p15; d16=1.4*p16; d25=1.4*p25; d26=1.4*p26; p12=((P(1,1)-P(2,1))^2+(P(1,2)-P(2,2))^2)^0.5; p15=((P(1,1)-P(5,1))^2+(P(1,2)-P(5,2))^2)^0.5; p16=((P(1,1)-P(6,1))^2+(P(1,2)-P(6,2))^2)^0.5; p25=((P(2,1)-P(5,1))^2+(P(2,2)-P(5,2))^2)^0.5; p26=((P(2,1)-P(6,1))^2+(P(2,2)-P(6,2))^2)^0.5; !B点结果; p34=((P(3,1)-P(4,1))^2+(P(3,2)-