城区公路选址问题.docx

城区公路选址问题

XX学院第三届大学生数学建模竞赛（201X年5月17日14时－5月23日14时）参赛题目AB（在所选题目上打勾）参赛队员1参赛队员2参赛队员3姓名学号学院一卡通号手机Email教学部XX第三届大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A我们的参赛报名号为（如果赛区设置报名号的话）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：201X年05月日赛区评阅编号（由赛区组委会评阅前进行编号）：XX大学XX学院第三届大学生数学建模竞赛编号专用页评阅编号（由组委会评阅前进行编号）：评阅记录（可供评阅时使用）：评阅人评分备注城区公路选址问题摘要根据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)，找出最优解。问题五将路线分