数学建模论文_公园道路的设计

园 内 道 路 设 计 小组成员 寇 绍 威 贾 栋 何 俊 辉 西安科技大学数学建模竞赛承诺书西安科技大学数学建模竞赛承诺书 我们仔细阅读了西安科技大学数学建模竞赛的竞赛规则 我们完全明白 在竞赛开始后参赛队员不能以任何方式 包括电话 电子邮件 网 上咨询等 与队外的任何人 包括指导教师 研究 讨论与赛题有关的问题 我们知道 抄袭别人的成果是违反竞赛规则的 如果引用别人的成果或其他公开的 资料 包括网上查到的资料 必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出 我们郑重承诺 严格遵守竞赛规则 以保证竞赛的公正 公平性 如有违反竞赛规 则的行为 我们将受到严肃处理 我们参赛选择的题号是 A 我们的参赛论文题目是 公园道路设计 参赛队员 队员 1 姓名 寇 绍 威 学院 计算机科学与技术学院 专业年级 信息与计算科学 1002 班 联系电话 队员 2 姓名 贾 栋 学院 计算机科学与技术学院 专业年级 信息与计算科学 1002 班 联系电话 队员 3 姓名 何 俊 辉 学院 计算机科学与技术学院 专业年级 信息与计算科学 1002 班 联系电话 参赛队员签名 1 2 3 日期 2012 年 9 月 5 日 论文编号页 1 公园道路设计 摘要 针对园内道路建设问题 本文分别采用了分析法和线性规划法进行了求解 首先尽可能利用四周已有道路 通过计算 8 个入口两两之间的路长及直线距离 筛选出不能通过已有道路到达的入口 然后针对这些入口修建道路 对于问题一 通过上述筛选 以采取当前最短道路并尽量利用边界为原则 对剩 余组合添加道路 加路后剔除满足条件的组合 并再次加路 最后得最佳方案 此时 的路长为 394 57 米 对于问题二 从交叉点的个数展开讨论并针对每种情况进行线性规划 以路长为 目标函数 以任意的两个入口之间的最短道路长不大于两点直线距离的 1 4 倍为约束条 件 建立线性规划方程 借助编程进行求解 求得 当有 3 个交叉点时 可得最Lingo 佳方案 此时的路长为 325 91 米 对于问题三 用两种方案在问题二的基础上进行修正 第一种方案以问题二最优 解修正 使通过湖部分路线调整 建立新的线性规划问题 解得最短路长为 第二种方案 由于问题二的较优方案未通过湖 故直接采取其为最后方mS73 328 案 路长为 两者比较得最短路长为 mS72 332 mS73 328 关键词 公园道路 线性规划 最优化 2 问题重述 西安某大学计划建一个形状为矩形或其他不规则图形的公园 不仅为了美化校园 环境 也是想为其学生提供更的生活条件 公园计划有若干个入口 现在你需要建立 一个模型去设计道路让任意两个入口相连 可以利用公园四周的边 即默认矩形的四 条边上存在已经建好的道路 此道路不计入道路总长 使总的道路长度和最小 前提 要求是任意的两个入口之间的最短道路长不大于两点连线的 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 公园及入口示意图公园及入口示意图 3 图图 2 一种可能的道路设计图一种可能的道路设计图 图图 3 有湖的示意图有湖的示意图 基本假设 1 假设道路宽度可以忽略不计 2 假设公园是一个平面 3 问题一 问题二中 道路可以通过公园内任意区域 4 符号说明 1 入口 1 8 8 2 1 ipi 2 从上到下 从左到右的四个道路交叉口 12 11 10 9 ipi 3 修建总道路长度S 4 的直线距离pjpis ji 到 模型建立与求解 问题一模型建立与求解 模型的目标是使 8 个入口两两之间的道路长度不大于两点间直线距离的 1 4 倍的前 提下 使所修建的道路最短 现所有需要满足的条件共有个 但根据分析发现28 2 8 C 部分组合可以利用边界道路满足条件 用 Matlab 编程计算知 详见附录 1 代码 所 有 28 个条件中只有 和不能利用边界8 6 51pppp 7 6 52pppp 7 6 5 43ppppp 道路 故要针对这些点进行添加道路 首先考虑和 从到 若不直接加路 则其要通过另 4 个交叉路口来满足 1p8p1p8p 而距最近的交叉点是 而到的距离为 42 72 大于和之间的距离8p11p11p8p1p8p 32 02 也就是说 所有通向的路中 无论是否借助其他已有道路 直接由指1p8p1p 向是最近的 所以和之间必加路 同理可得 和之间必加路 8p1p8p3p4p 在此基础上计算发现 通过已加的路满足了路长与距离的要求 此72pp 81pp 时加路所得图如图 4 此时 只剩下和 和 和 这些组合不满足边1p5p6p2p5p6p3p5p6p7p 界距离小于直线距离的 1 4 倍 从开始考虑 通过交叉点 到 都要可以到达 所有到 3p3p5p6p7p3p5p6p 之一的道路中 最短路是 通过验证 此时到 到7p510123pppp 3p6p3p 也满足了 1 4 倍要求 此时修建道路如图 5 7p 5 图 4 图 5 考虑 通过交叉点 所有到 之一的最短路是 2p2p5p6p69112pppp 通过这条路线 到满足了要求 但是通过验证 到并不满足要求 此时2p6p2p5p 继续在有上述路的基础上加路 剩余所有可行的路有 到 到 到2p12p11p10p9p 6 其中最短的路是到 此时到满足要求 5p9p5p2p5p 最后考虑 通过验证 此时到任一点是满足要求的 即满足要求的最佳方案 1p1p 此时的路长为 394 57 米 方案 如图 6 图 6 问题二模型建立与求解 对于问题二 前期讨论与问题一一致 即只需考虑和 和 1p5p6p2p5p6p 和 这 7 个组合所需要的道路总长 3p5p6p7p 在不确定道路交叉点的情况下 首先对可能出现的交叉点情况进行分类讨论 假设有一个交叉点 即在公园的中间区域所围成的四边形区域内找2p3p5p6p 到一个道路交叉点 在满足距离要求的前提下 使得其与距离之和最9p2p3p5p6p 小 示意图如图 8 亦可能存在只有一个道路交叉点 其与相连 直接与相连 可9p2p3p6p5p3p 7 归结为下述第二种情况的特殊情况 图 8 示意图 设该点的坐标为 为使总路长最短 需使得 yxp 9 最小 同时为满足到达 的总路长小于 4 38 19 59 69 39 2 ssssss 1p5p6p 5 1 s 的 1 4 倍 同时到达 的总路长小于 的 1 4 倍 以及到 6 1 s2p5p6p 5 2 s 6 2 s3p5p 的路长小于 的 1 4 倍等 可列出 7 个线性约束方程 6p7p 5 3 s 6 3 s 7 3 s 因此可以得到以下线性规划方程 7 37 66 99 3 6 36 99 3 5 35 99 3 5 25 99 2 6 26 99 2 5 15 99 22 1 6 16 99 22 1 4 38 19 59 69 39 2 4 1 4 1 4 1 4 1 4 1 4 1 4 1 min ssss sss sss sss sss ssss ssss ts ssssssS 8 上式所有距离均为已知或可由的坐标表示 则可以通过编程求解 其代9pLingo 码见附录 3 1 用求解无可行解 因而 这种情况不可行 Lingo 讨论有两个交叉点的情况 设这两个交叉点的坐标分别为 1 19yxp 其大致示意图有两种情况 如图 9 图 10 所示 因此 与只有一个交叉 2 210yxp 点的情况类似 在图 9 下 可以得到一个线性规划方程 7 37 66 99 1010 3 6 36 99 1010 3 5 35 1010 3 5 25 1010 99 2 6 26 99 2 6 15 1010 99 22 1 6 16 99 22 1 4 38 15 1010 36 910 99 2 4 1 4 1 4 1 4 1 4 1 4 1 4 1 min sssss ssss sss ssss sss sssss ssss ts sssssssS 图 9 示意图 9 图 10 示意图 由此可以通过计算出最优的 代码见附Lingo 665 31 56 59p 63 77 106 7210p 录 3 2 此时 总道路长为 371 33m S 在图 10 所示下 列出相应线性规划方程 用附录 3 3 的代码求解得此情况Lingo 无可行解 下面讨论三个交叉点的情况 在有三个交叉点时 同样分为两种情况 其示意图 如图 11 图 12 在如图 11 所示的情况下 设这 3 个道路交叉点的坐标分别为 1 19yxp 同理可以得到以下线性规划方程 2 210yxp 3 311yxp 10 3 43 1111 4 7 37 66 99 1010 1111 3 6 36 99 1010 1111 3 5 35 99 1010 1111 3 5 25 99 1010 11 2 6 26 99 1010 11 2 5 15 99 1010 1 6 16 99 1010 1 4 113 1111 109 59 69 1010 18 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 min sss ssssss sssss sssss sssss sssss ssss ssss ssssssssS 图 11 示意图 在这种情况下 求得这三个点的坐标分别为 14 77 70 869p 00 35 48 9210p 82 12 47 15711p 此时 道路的总长为 332 72m 在如图 12 的情况下 同上 可以得到线性规划方程组 11 3 43 1111 4 7 37 66 99 1010 1111 3 6 36 99 1010 1111 3 5 35 1010 1111 3 5 25 1010 99 11 2 6 26 99 11 2 5 15 1010 99 1 6 16 99 1 4 113 1111 105 106 910 99 18 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 min sss ssssss sssss ssss sssss ssss ssss sss ssssssssS 图 12 示意图 由此 通过求解 可以得出这三点的坐标为 Lingo 75 71 70 619p 在这种情况下 总道路长为 86 88 44 11710p 58 40 32 16911pmS91 325 对于某些一到三个交叉口的其他情况 均可证明路长小于上述五种情况 或可归 结为此五种情况的特殊情况 道路交叉口为四个或更多时 情况较为复杂 此处暂不讨论 综合上述多种情况 可得最短路长为 mS91 325 12 问题三的模型建立与求解 当有湖时 在问题二的基础上 经分析有以下两种方案可供选择 第一种方案 在问题二的最优解的基础上进行改进 使其避开湖 其大致图形如 图 13 图 13 示意图 在此情况下 可以得到线性规划方程组如下 3 43 1111 4 7 37 66 99 1011 22 1011 3 6 36 99 1011 22 1011 3 5 35 1011 22 1011 3 5 25 1010 99 11 2 6 26 99 11 2 5 15 1010 99 1 6 16 99 1 4 113 1111 22 105 106 911 22 109 18 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 min sss sssssss ssssss sssss sssss ssss ssss sss ssssssssssS RR RR RR RRRR 13 由此 通过求解 代码见附录 5 可以得出这三点的坐标为 Lingo 在这种情况下 总道路长为 52 63 90 639p 71 74 28 11210p 89 26 40 16611p mS73 328 第二种方案 经分析 问题二的第四种情况与最优解相差不大 如图 14 其不经 过湖所在区域 故可直接采取此方案作为问题三方案 在这种情况下 求得这三个点的坐标分别为 14 77 70 869p 00 35 48 9210p 82 12 47 15711p 可得其最短路长为 mS72 332 图 14 综合上述两种方案 可得修建的最短路长为mS73 328 模型优缺点分析 问题一模型的思想来源于图论里的算法 当交叉点个数不太多时 方案较为prim 简洁 但当交叉点个数多时 确定起来就很复杂 问题二的模型用了线性规划的方法 但是在模型中 对交叉点个数讨论是个问题 本文只在不多于 3 个交叉点的情况进行 了讨论 但运用了计算机编程 这样就可以解决多交叉点的问题 所以在实际应用中 14 有了很大的推广作用 参考文献 1 韩中庚 数学建模方法及其应用 北京 高等教育出版社 2005 2 刘卫国 Matlab 程序设计与应用 M 北京 高等教育出版社 2002 15 附录 附录 1 判断边缘道路是否已满足 1 4 倍距离要求 Matlab 代码 clear x 20 50 160 200 120 35 10 0 y 0 0 0 50 100 100 100 25 m 0 0 0 0 0 0 0 0 30 0 0 0 0 0 0 0 140 110 0 0 0 0 0 0 230 200 90 0 0 0 0 0 240 270 220 130 0 0 0 0 155 185 295 215 85 0 0 0 130 160 270 240 110 25 0 0 45 75 185 275 195 110 85 0 for i 1 8 for j 1 i 1 if sqrt x i x j 2 y i y j 2 1 4 m i j n i j 0 else n i j 1 end end end n 附录 2 计算任意两点间距离 Matlab 代码 clear x 20 50 160 200 120 35 10 0 50 115 40 120 y 0 0 0 50 100 100 100 25 75 70 40 40 for i 1 12 for j 1 i L i j sqrt x i x j 2 y i y j 2 end end 附录 3 求解过程 lingo 代码 X 形 min s1 s2 s3 s4 s5 s6 s1 x 35 2 y 100 2 1 2 s2 x 120 2 y 100 2 1 2 s3 x 50 2 y 0 2 1 2 s4 x 160 2 y 0 2 1 2 s5 20 0 2 0 25 2 1 2 1 8 s6 160 200 2 0 50 2 1 2 3 4 30 s3 s1 1 4 20 35 2 0 100 2 1 2 1 6 16 30 s2 s3 1 4 20 120 2 0 100 2 1 2 1 5 s2 s3 1 4 50 120 2 0 100 2 1 2 2 5 s1 s3 1 4 50 35 2 0 100 2 1 2 2 6 s2 s4 1 4 160 120 2 0 100 2 1 2 3 5 s1 s4 1 4 160 35 2 0 100 2 1 2 3 6 25 s1 s4 1 4 160 10 2 0 100 2 1 2 3 7 工字形 min s1 s2 s3 s4 s5 s6 s7 s1 x1 35 2 y1 100 2 1 2 6 s2 x1 120 2 y1 100 2 1 2 5 s3 x2 50 2 y2 0 2 1 2 2 s4 x2 160 2 y2 0 2 1 2 3 s5 20 0 2 0 25 2 1 2 1 8 s6 160 200 2 0 50 2 1 2 3 4 s7 x1 x2 2 y1 y2 2 1 2 x1 x2 30 s3 s1 s7 1 4 20 35 2 0 100 2 1 2 1 6 30 s2 s3 s7 1 4 20 120 2 0 100 2 1 2 1 5 s2 s3 s7 1 4 50 120 2 0 100 2 1 2 2 5 s1 s3 s7 1 4 50 35 2 0 100 2 1 2 2 6 s2 s4 s7 1 4 160 120 2 0 100 2 1 2 3 5 s1 s4 s7 1 4 160 35 2 0 100 2 1 2 3 6 25 s1 s4 s7 1 4 160 10 2 0 100 2 1 2 3 7 H 形 min s1 s2 s3 s4 s5 s6 s7 s1 x1 35 2 y1 100 2 1 2 6 s2 x2 120 2 y2 100 2 1 2 5 s3 x1 50 2 y1 0 2 1 2 2 s4 x2 160 2 y2 0 2 1 2 3 s5 20 0 2 0 25 2 1 2 1 8 s6 160 200 2 0 50 2 1 2 3 4 s7 x1 x2 2 y1 y2 2 1 2 x1 x2 30 s3 s1 1 4 20 35 2 0 100 2 1 2 1 6 30 s2 s3 s7 1 4 20 120 2 0 100 2 1 2 1 5 s2 s3 s7 1 4 50 120 2 0 100 2 1 2 2 5 s1 s3 1 4 50 35 2 0 100 2 1 2 2 6 s2 s4 1 4 160 120 2 0 100 2 1 2 3 5 s1 s4 s7 1 4 160 35 2 0 100 2 1 2 3 6 25 s1 s4 s7 1 4 160 10 2 0 100 2 1 2 3 7 双 Y 形 min s1 s2 s3 s4 s5 s6 s7 s1 x1 35 2 y1 100 2 1 2 6 s2 x1 120 2 y1 100 2 1 2 5 s3 x2 50 2 y2 0 2 1 2 2 17 s4 x3 160 2 y3 0 2 1 2 3 s5 x3 200 2 y3 50 2 1 2 4 s8 20 0 2 0 25 2 1 2 1 8 s6 x1 x2 2 y1 y2 2 1 2 x1 x2 s7 x2 x3 2 y2 y3 2 1 2 x2 x3 30 s3 s1 1 4 20 35 2 0 100 2 1 2 1 6 30 s2 s3 s6 1 4 20 120 2 0 100 2 1 2 1 5 s2 s3 s6 1 4 50 120 2 0 100 2 1 2 2 5 s1 s3 1 4 50 35 2 0 100 2 1 2 2 6 s2 s4 s7 1 4 160 120 2 0 100 2 1 2 3 5 s1 s4 s6 s7 1 4 160 35 2 0 100 2 1 2 3 6 25 s1 s4 s6 s7 1 4 160 10 2 0 100 2 1 2 3 7 L 附录 4 做示意图 Matlab 代码 clear rukou 20 50 160 200 120 35 10 0 0 0 0 50 100 100 100 25 jiaocha 50 115 40 120 75 70 40 40 X 1 linspace 0 20 100 Y 1 linspace 25 0 100 1 8 X 2 linspace 160 200 100 Y 2 linspace 0 50 100 3 4 X 3 linspace 50 120 100 Y 3 linspace 0 40 100 2 12 X 4 linspace 50 40 100 Y 4 linspace 0 40 100 2 11 X 5 linspace 40 50 100 Y 5 linspace 40 75 100