城区公路选址问题

.../CXXY学院第三届大学生数学建模竞赛〔201X年5月17日14时－5月23日14时参赛题目AB〔在所选题目上打勾参赛队员1参赛队员2参赛队员3姓名王姜杨学号015105450151030501510550学院CXXYCXXYCXXY一卡通号201510545201510305201510550手机EmailCXXY教学部CXXY第三届大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白,在竞赛开始后参赛队员不能以任何方式〔包括电话、电子邮件、网上咨询等与队外的任何人〔包括指导教师研究、讨论与赛题有关的问题。我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料〔包括网上查到的资料,必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违反竞赛规则的行为,我们将受到严肃处理。我们参赛选择的题号是〔从A/B/C/D中选择一项填写：A 我们的参赛报名号为〔如果赛区设置报名号的话：参赛队员<打印并签名>：1.王2.姜3.杨指导教师或指导教师组负责人<打印并签名>：日期：201X年05月23日赛区评阅编号〔由赛区组委会评阅前进行编号：东南大学成贤学院第三届大学生数学建模竞赛编号专用页评阅编号〔由组委会评阅前进行编号：评阅记录〔可供评阅时使用：评阅人评分备注城区公路选址问题摘要根据AB之间地的不同区域不同造价的特点,本文采用了两种方法,一种是将连续问题离散化利用穷举法取最优的方法。另一种是在穷举法的所求结果的基础上利用极限定义无限逼近的思想缩小最优转弯点的存在的可能区域,进而再利用非线性规划从而得出最优解。问题一：用穷举法建立了一个模型,所得最优转弯点为〔5,6、〔6,5〔最小花费为14.7068百万元。问题二：通过在问题一的基础分析,再次利用穷举法建立了模型逐步计算关于CD对称的两个转弯网格点的建设费用,通过比较得出〔4,7,〔7,4两点,为所最小建设费用的转弯点。最小费用为14.624百万元。问题三：本问题要求铺设线路落在网格线上,利用Matlab求出f<x>在各个网络线的最小值,再通过比较,找出最优转弯点〔4.5719,6、〔6,4.5719,最小费用为14.6989百万元。问题四：同问题三模型思想方法,得出关于建设总费用的目标函数二元方程f<x,y>,再利用Matlab求出目标函数在可能区域的最小值,得到最优转弯点,最小费用为14.6989百万元。问题五：将路线分成无数小段,利用积分的思想模型,求出建设费用。关键词：穷举法 无限逼近非线性规划一问题重述城区公路选址问题某区政府计划在下列区域〔见图1修建一条从A〔0,9到B〔9,0的直线型公路,由于涉及路面拆迁等因素,各地段建设费用有所不同,图1中的数字代表该区域公路单位建设费用〔单位：百万元。未标数字的任何地方单位建设费用均为1。图1的每个网格长与宽都是1个单位。每个网格的边界上建设费用按该地区最小单位费用计算。请你按建设部门的如下具体要求,从建设费用最省的角度,给出最优的方案。〔1公路至多只能有1个转弯点,且转弯点只能建在图1所示的网格点上。〔2公路至多可以有2个转弯点,且转弯点只能建在图1所示的网格点上。〔3公路至多只能有1个转弯点,且转弯点只能建在图1所示的网格线上。〔4公路至多只能有1个转弯点,转弯点可以建在图1所示区域的任何位置。〔5如果各区域的单位建设费用为〔百万元,公路至多只能有1个转弯点,转弯点可以建在图1所示区域的任何位置。二问题分析本问题主围绕由A点到B点公路选址展开,要求建设费用最少。根据各个区域的费用不同,确定转弯点的位置。我们采用了两种方法求得最少的花费,分别为非线性规划模型和逐点遍历模型。问题一我们利用穷举法建立模型一,用来确保结果是最小值,根据图像的对称性以及单位区域建设费用的分布规律,着重对AB上方区域点采用枚举分析计算,得出结果。问题二本问题与问题一相比,增加一个转弯点,通过对问题的分析可以得到符合条件的两个转弯点,应该对称的分布在直线y=x的两侧。我们在问题一所建立的两种模型的基础上均增加相应约束条件,通过对比分析得出最少花费的铺设线路〔即两个转弯点的位置。问题三本问题要求铺设线路落在网格线上,在问题1、2的基础上通过分析归纳缩小符合该条件的网络线的分布位置。利用非线性规划求解,建立模型二,可以得出一个关于建设总费用的目标函数f<x>,而且可知f<x>在整个区域连续且可微,利用Matlab求出f<x>符合在某一点有局部极小点的条件,再通过比较符合条件的各个网络线的最小值,找出最优解。问题四类似于问题三的分析方法,找出符合条件的最小区域。利用非线性规划求解,可以得出一个关于建设总费用的目标函数f<x,y>,而且可知f<x,y>在整个区域连续且可微,利用Matlab求出f<x,y>,找出最优解。问题五将路线分成无数小段,利用积分的思想模型,求出建设费用三.符号说明,为建设总费用x为选取转弯点的横坐标y为选取转弯点的纵坐标为选取转弯点和A点连线与直线y=9的夹角为选取转弯点和B点连线与直线x=9的夹角d1为选取点转弯点与A点之间的距离d2为选取点转弯点与B点之间的距离五.模型建立与求解DADA1.11.11.11.11.11.11.11.11.11.21.21.21.21.21.21.11.11.2C1.3C1.31.31.31.21.11.11.21.31.41.41.31.21.11.11.21.31.41.41.31.21.11.11.21.31.31.31.31.21.11.11.21.21.21.21.21.21.11.11.11.11.11.11.11.11.1BB问题一:通过观察图形分析得到图形关于直线AB对称,但由于下侧单位区域建设费用相对较大,故而最优转弯点必然在AB上侧。AB上侧又关于直线CD对称,故而只要分析CD上方区域即可。依次将该区域各个点求解建设费用,通过比较得出〔5,6为网格点上最优的转弯点,最小费用为14.7068百万元。再有对称性可得〔6,5也为网格点上最优的转弯点,最小费用为14.7068百万元。问题二:通过在问题一的基础分析可知,所选的两个最优转弯点必然关于直线CD对称。逐步计算对称的两个转弯网格点的建设费用,通过比较得出〔4,7,〔7,4两点,为所最小建设费用的转弯点。最小费用为14.624百万元。问题三:通过问题一二的求解,利用无限逼近思想可以知道最优转弯点网格线必然在问题一所求到的转弯点的附近,利用Matlab软件求解附近的各个网格线上的建设费用最小的点。左边网格线〔4<=x<=5,y=6因此得到费用函数用Matlab软件解得答案：xmin=4.5719fmim=14.6989上边网格线〔x=5,6<=y<=7因此得到费用函数用Matlab软件解得答案：ymin=6.0001fmim=14.7068右边网格线〔5<=x<=6,y=6因此得到费用函数用Matlab软件解得答案：xmin=5.0001fmim=14.7068下边网格线〔x=4,5<=y<=6因此得到费用函数用Matlab软件解得答案：ymin=5.8286fmim=14.7066通过比较四条网格线上的最小费用点,得出点〔4.5719,6即所求的最优转为点,再利用图形对称性得到点〔6,4.5719也是最优转弯点。最小费用为14.6989百万元。问题四:通过问题三四个网格线上建设费用最小转弯点的分布,利用无限逼近的思想可以推测问题四的最优转弯点在〔5,5.8286以及〔4.5719,6的附近区域。综合各方面限制条件列出一下函数式,并利用Matlab软件解得答案：因此得到费用函数xmin=4.6215ymin=5.9127fmim=14.6208问题五：六.模型的评价与建议模型的主要优点：对于问题一、二所建立的模型一,利用图像的对称性以及单位区域建设费用的分布规律,减少了大量繁琐的数学计算。问题三、四在问题一、二的求解基础上,通过理论分析排除了大量的不可能区域,缩小了公路最优转弯点的可能区域大大简化了计算量,进而利用非线性规划求解,建立模型二,可以得出一个关于建设总费用的目标函数f<x>,模型原理简单明了,系统直观的反映了转弯点位置与建设费用的关系,在计算复杂求导时借助Matlab软件,提高了计算效率。模型的主要不足：模型一枚举法存在很大的局限性,需要考虑的情况较多,并且存在较大的计算量,不是最佳方案。另外通过分析归纳缩小符合问题三、四条件的最佳转弯点的分布位置的方法不是太严谨。对城区公路建设及选址的建议：直线行的公路呆板,行车单调,容易使驾驶员产生疲劳,容易发生超车和超速行驶,行车时难以估计车辆之间的距离,所以现代城区公路一般都采用环形设计。城区公路应尽量避开城市主要商业中心。城市快速路车流量大,车速快,人的流动性大,不利于商圈集聚人气,不利于商业发展。城市快速路不宜建在景观路段。特别是采用路堑式和高架式的城市快速路,在带来便利交通的同时必然对城市景观构成破坏。七.参考文献[1]姜启源,谢金星,叶俊,《数学模型》〔第三版,北京：高等教育出版社,2003.8[2]曹卫华郭正,《最优化设计方法及MATLAB的实现》,北京：化学工业出版社,2005.[3]李清波《道路规划与设计》人民交通出版社;第1版20XX1月[4]邬学军、周凯、宋军全,《数学建模竞赛辅导教程》,XX天目山路148号,XX大学出版社,20XX8月[5]王沫然,《MATLAB5.X与科学计算》,北京清华大学学研楼,清华大学出版社,20XX5月[6]李海涛、邓撄,《MATLAB6.1基础及应用技巧》,北京,国防工业出版社,20XX3月附件附件一：问题三的Matlab语言源代码：问题一所求得的最优拐弯点最近的四条最小网格线左边的网格线最优造价函数求解代码：>>fy=inline<'1.1*sqrt<x^2+9>+sqrt<<9-x>^2+36>/<9-x>*<11.1-1.3*x>'>;>>[xmin,fmim]=fminbnd<fy,4,5>xmin=4.5719fmim=14.6989右边的网格线最优造价函数求解代码：fy=inline<'1.1*sqrt<x^2+9>+sqrt<36+<9-x>^2>*<11.1-1.3*x>/<9-x>'>;>>[xmin,fmim]=fminbnd<fy,5,6>xmin=5.0001fmim=14.7068上边的网格线最优造价函数求解代码：>>fy=inline<'<10.5-1.2*y>*sqrt<<9-y>^2+25>/<9-y>+<1.05+0.6/y>*sqrt<y^2+16>'>;>>[ymin,fmim]=fminbnd<fy,6,7>ymin=6.0001fmim=14.7068下边的网格线最优造价函数求解代码：>>fy=inline<'1.15*sqrt<y^2+16>+sqrt<25+<9-y>^2>*<11.1-1.3*y>/<9-y>'>;>>[ymin,fmim]=fminbnd<fy,5,6>ymin=5.8286fmim=14.7066附件二：问题四的Matlab语言源代码：符合最优转弯点区域最优造价函数求解代码：>>symsxy;z=<11.1-1.3y>*sqrt<x^2+y^2>/<9-y>+<11.1-1.3*x>*sqrt<<9-x>^2+y^2>/<9-x>;>>diff<z,x>ans=<13*<<x-9>^2+y^2>^<1/2>>/<10*<x-9>>-<<<13*x>/10-111/10>*<<x-9>^2+y^2>^<1/2>>/<x-9>^2+<x*<<13*y>/10-111/10>>/<<x^2+y^2>^<1/2>*<y-9>>+<<2*x-18>*<<13*x>/10-111/10>>/<2*<<x-9>^2+y^2>^<1/2>*<x-9>>>>diff<z,y>ans=<13*<x^2+y^2>^<1/2>>/<10*<y-9>>-<<x^2+y^2>^<1/2>*<<13*y>/10-11