《城区公路选址问题.doc》由会员分享，可在线阅读，更多相关《城区公路选址问题.doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、城区公路选址问题_学院 第三届大学生数学建模竞赛 （201_年5月17日14时5月23日14时） 参赛题目 A B （在所选题目上打勾） 参赛队员1 参赛队员2 参赛队员3 姓名 学号 学院 一卡通号 手机 Email 教学部 _第三届大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的【参考文献】：p 的表述方
2、式在正文引用处和【参考文献】：p 中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A 我们的参赛报名号为（如果赛区设置报名号的话）： 参赛队员 (打印并签名_) ：1.2.3.指导教师或指导教师组负责人 (打印并签名_)： 日期： 201_ 年 05 月 23 日 赛区评阅编号（由赛区组委会评阅前进行编号）： _大学_学院第三届大学生数学建模竞赛 编 号 专 用 页 评阅编号（由组委会评阅前进行编号）： 评阅记录（可供评阅时使用）： 评 阅 人 评 分 备 注 城区公
3、路选址问题 摘 要 根据AB之间地的不同区域不同造价的特点，本文采用了两种方法，一种是将连续问题离散化利用穷举法取最优的方法。另一种是在穷举法的所求结果的基础上利用极限定义无限逼近的思想缩小最优转弯点的存在的可能区域，进而再利用非线性规划从而得出最优解。 问题一：用穷举法建立了一个模型，所得最优转弯点为（5,6）、（6，5）（最小花费为14.7068百万元）。 问题二：通过在问题一的基础分析p ，再次利用穷举法建立了模型逐步计算关于CD对称的两个转弯网格点的建设费用，通过比较得出（4，7），（7，4）两点，为所最小建设费用的转弯点。最小费用为14.624百万元。 问题三：本问题要求铺设线路落在
4、网格线上，利用Matlab求出 f(_) 在各个网络线的最小值，再通过比较，找出最优转弯点（4.5719，6）、（6,4.5719），最小费用为14.6989百万元。 问题四：同问题三模型思想方法，得出关于建设总费用的目标函数二元方程f(_，y)，再利用Matlab求出 目标函数在可能区域的最小值，得到最优转弯点，最小费用为14.6989百万元。 问题五：将路线分成无数小段，利用积分的思想模型，求出建设费用。 【关键词】：p ： 穷举法 无限逼近 非线性规划 一 问 题 重 述 城区公路选址问题 某区政府计划在下列区域（见图1）修建一条从A（0,9）到B（9,0）的直线型公路，由于涉及路面拆迁
5、等因素，各地段建设费用有所不同，图1中的数字代表该区域公路单位建设费用（单位：百万元）。未标数字的任何地方单位建设费用均为1。图1的每个网格长与宽都是1个单位。每个网格的边界上建设费用按该地区最小单位费用计算。 请你按建设部门的如下具体要求，从建设费用最省的角度，给出最优的方案。 （1）公路至多只能有1个转弯点，且转弯点只能建在图1所示的网格点上。 （2）公路至多可以有2个转弯点，且转弯点只能建在图1所示的网格点上。 （3）公路至多只能有1个转弯点，且转弯点只能建在图1所示的网格线上。 （4）公路至多只能有1个转弯点，转弯点可以建在图1所示区域的任何位置。 （5）如果各区域的单位建设费用为（百
6、万元），公路至多只能有1个转弯点，转弯点可以建在图1所示区域的任何位置。 二 问题分析p 本问题主围绕由A点到B点公路选址展开，要求建设费用最少。根据各个区域的费用不同，确定转弯点的位置。我们采用了两种方法求得最少的花费，分别为非线性规划模型和逐点遍历模型。 问题一 我们利用穷举法建立模型一，用来确保结果是最小值，根据图像的对称性以及单位区域建设费用的分布规律 ，着重对AB上方区域点采用枚举分析p 计算，得出结果。 问题二 本问题与问题一相比,增加一个转弯点，通过对问题的分析p 可以得到符合条件的两个转弯点，应该对称的分布在直线y=_的两侧。我们在问题一所建立的两种模型的基础上均增加相应约束条
7、件，通过对比分析p 得出最少花费的铺设线路（即两个转弯点的位置）。 问题三 本问题要求铺设线路落在网格线上，在问题1、2的基础上通过分析p 归纳缩小符合该条件的网络线的分布位置。利用非线性规划求解，建立模型二，可以得出一个关于建设总费用的目标函数f(_)，而且可知f(_)在整个区域连续且可微，利用Matlab求出 f(_)符合在某一点有局部极小点的条件，再通过比较符合条件的各个网络线的最小值，找出最优解。 问题四 类似于问题三的分析p 方法，找出符合条件的最小区域。利用非线性规划求解，可以得出一个关于建设总费用的目标函数f(_,y)，而且可知f(_，y)在整个区域连续且可微，利用Matlab求
8、出 f(_，y)，找出最优解。 问题五 将路线分成无数小段，利用积分的思想模型，求出建设费用 三.符号说明 ， 为建设总费用 _ 为选取转弯点的横坐标 y 为选取转弯点的纵坐标 为选取转弯点和A点连线与直线y=9的夹角 为选取转弯点和B点连线与直线_=9的夹角 d1 为选取点转弯点与A点之间的距离 d2 为选取点转弯点与B点之间的距离 五.模型建立与求解 D A 1.1 1.1 1.1 1.1 1.1 1.1 1.1 1.1 1.1 1.2 1.2 1.2 1.2 1.2 1.2 1.1 1.1 1.2 C 1.3 1.3 1.3 1.3 1.2 1.1 1.1 1.2 1.3 1.4 1.4
9、 1.3 1.2 1.1 1.1 1.2 1.3 1.4 1.4 1.3 1.2 1.1 1.1 1.2 1.3 1.3 1.3 1.3 1.2 1.1 1.1 1.2 1.2 1.2 1.2 1.2 1.2 1.1 1.1 1.1 1.1 1.1 1.1 1.1 1.1 1.1 B 问题一: 通过观察图形分析p 得到图形关于直线AB对称，但由于下侧单位区域建设费用相对较大，故而最优转弯点必然在AB上侧。AB上侧又关于直线CD对称，故而只要分析p CD上方区域即可。 依次将该区域各个点求解建设费用，通过比较得出（5，6）为网格点上最优的转弯点，最小费用为14.7068百万元。再有对称性可得（6
10、，5）也为网格点上最优的转弯点，最小费用为14.7068百万元。 问题二: 通过在问题一的基础分析p 可知，所选的两个最优转弯点必然关于直线CD对称。逐步计算对称的两个转弯网格点的建设费用，通过比较得出 （4，7），（7，4）两点，为所最小建设费用的转弯点。最小费用为14.624百万 元。 问题三: 通过问题一二的求解，利用无限逼近思想可以知道最优转弯点网格线必然在问题一所求到的转弯点的附近，利用Matlab软件求解附近的各个网格线上的建设费用最小的点。 1.左边网格线 （4 fy=inline(1.1_sqrt(_2+9)+sqrt(9-_)2+36)/(9-_)_(11.1-1.3_);
11、_min,fmim=fminbnd(fy,4,5) _min = 4.5719 fmim = 14.6989 右边的网格线最优造价函数求解代码： fy=inline(1.1_sqrt(_2+9)+sqrt(36+(9-_)2)_(11.1-1.3_)/(9-_); _min,fmim=fminbnd(fy,5,6) _min = 5.0001 fmim = 14.7068 上边的网格线最优造价函数求解代码： fy=inline(10.5-1.2_y)_sqrt(9-y)2+25)/(9-y)+(1.05+0.6/y)_sqrt(y2+16); ymin,fmim=fminbnd(fy,6,7)
12、 ymin = 6.0001 fmim = 14.7068 下边的网格线最优造价函数求解代码： fy=inline(1.15_sqrt(y2+16)+sqrt(25+(9-y)2)_(11.1-1.3_y)/(9-y); ymin,fmim=fminbnd(fy,5,6) ymin = 5.8286 fmim = 14.7066 附件二： 问题四的Matlab语言代码： 符合最优转弯点区域最优造价函数求解代码： syms _ y; z=(11.1-1.3y)_sqrt(_2+y2)/(9-y)+(11.1-1.3_)_sqrt(9-_)2+y2)/(9 -_); diff(z,_) ans =
13、 (13_(_ - 9)2 + y2)(1/2)/(10_(_ - 9) - (13_)/10 - 111/10)_(_ - 9)2 + y2)(1/2)/(_ - 9)2 + (_(13_y)/10 - 111/10)/(_2 + y2)(1/2)_(y - 9) + (2_ - 18)_(13_)/10 - 111/10)/(2_(_ - 9)2 + y2)(1/2)_(_ - 9) diff(z,y) ans = (13_(_2 + y2)(1/2)/(10_(y - 9) - (_2 + y2)(1/2)_(13_y)/10 - 111/10)/(y - 9)2 + (y_(13_)/
14、10 - 111/10)/(_ - 9)2 + y2)(1/2)_(_ - 9) + (y_(13_y)/10 - 111/10)/(_2 + y2)(1/2)_(y - 9) _,y=solve(13_(_ - 9)2 + y2)(1/2)/(10_(_ - 9) - (13_)/10 - 111/10)_(_ - 9)2 + y2)(1/2)/(_ - 9)2 + (_(13_y)/10 - 111/10)/(_2 + y2)(1/2)_(y - 9) + (2_ - 18)_(13_)/10 - 111/10)/(2_(_ - 9)2 + y2)(1/2)_(_ - 9)=0,(13_(_2 + y2)(1/2)/(10_(y - 9) - (_2 + y2)(1/2)_(13_y)/10 - 111/10)/(y - 9)2 + (y_(13_)/10 - 111/10)/(_ - 9)2 + y2)(1/2)_(_ - 9) + (y_(13_y)/10 - 111/10)/(_2 + y2)(1/2)_(y - 9)=0,_,y) _min = 4.6215 ymin = 5.9127 第 6 页 共 6 页