城区公路选址问题.doc

CXXY学院第三届大学生数学建模竞赛(201X年5月17日14时-5月23日14时)参赛题目AB(在所选题目上打勾)参赛队员1参赛队员2参赛队员3姓名王姜杨学号学院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