山地平整问题.doc

12015高教社杯杭电大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：杭州电子科技大学参赛队员(打印并签名)：1.徐一鸣2.刘帅3.汪君军指导教师或指导教师组负责人(打印并签名)：数模组日期：2015年8月4日2赛区评阅编号（由赛区组委会评阅前进行编号）：32015高教社杯杭电大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：4山地平整问题摘要本文围绕着山体平整问题，在合理假设的基础上，通过大量的数据及证明，并给出了克里金插值算法。而后通过线性规划、最小二乘法，针对题目所给的特定要求在满足标准和规范的情况下尽可能的应用技术指标进行建模，实现和分析。针对问题1：根据所给的山地海拔数据，利用克里金插值法对离散数据进行内插。考虑空间属性在空间位置上的变异分布，确定对一个待插点值有影响的距离范围，然后利用此范围内的采样点来估计待插点的属性。结合所给的球状模型绘出土地的三维图形与等高线图。针对问题2：首先利用坐标系旋转方法简化判断离散点是否在800m×600m的长方形内的过程，然后利用方格网法将该长方形区域等分成20m20m的方块，并求取每个方块的平均高度，采用积分的思想最终求得该区域所对应的体积，最后使平整该区域最小化总的土方量为目标函数，建立线性规划模型。根据问题所给数据量不多的特点，本文通过正交枚举法计算求解出总的土方量最优的情况下，开挖的位置、方向和海拔高度。而对于数据量很多的情况，本文最后也对用遗传算法解决该问题做了简单的描述。针对问题3：根据题目要求需平整出的土地为二层的台阶状地块，本文首先根据实际的填挖平衡的需求计算出选定区域的设计标高（海拔高度）0H。然后将平整土地的平面视作由该区域的离散点所拟合出来的，即函数hHHZ00，并与方格网法相结合将两块平面区域等分成20m20m的方块，并求取每一个方块的平均高度作为函数Z在该点时所对应离散点的值。根据最小二乘法原理，要使填挖的土方量最少，也就是平面上各方块所对应的体积与该方块下平面的体积之差的平方和最小，以此为目标函数建立数学模型。求解该模型时，可以看作是将该函数上下左右平移来计算各个位置、长宽下，利用最小二乘法求解最优的0H和h，最终根据各位置上的土方量求出全局最优的位置、长宽和海拔高度。对于函数平移到的位置和长宽的确定，本文根据贪婪的思想，长度和宽度从满足要求的最小值开始枚举，当有结果土方量最小又满足填挖平衡时即停止，选择此时的开挖位置和海拔高度最为最优解。本文所使用的方法有效地建立了空间三维的山地图形和山地的等高线图的参数模型，得到了精确的坐标轨迹，分析出了系统误差。但部分方法存在求解复杂，结果不太稳定的缺点。关键词：克里金插值算法线性规划最小二乘法方格网络法遗传算法5一、问题的重述随着社会经济的快速发展，土地资源日益趋于紧张。对于山区城市，向山要地是发展的一个必然的选择趋势。为了更好的确定平整地的起始点，做到节约成本的目的，如何在一片山地之间选择合适的方位与开挖深度，从而使总的土石方量最小是山区城市规划设计的基础工作。山区厂房地基的设计，在满足标准和规范的情况下，应尽可能地灵活运用技术指标，做到具体问题具体分析。在满足设计标准的前提下，应充分考虑结合其他因素，使得地形均衡，经济最优。在实际工程中，在考虑填挖平衡的前提下，用来减少土石方数量的方法之一就是使设计线尽可能地贴近地面线。分析结合工程造价如何合理的设计山区厂房基地就具有重要的意义。本文拟解决以下问题：(1)分析附件1中的数据画出工厂的这片土地的三维图形与等高线图。(2)建立坐标三维坐标系，根据线性规划的思路。结合工程实际选择恰当的海拔高度平整一块800米600米的连片土地使得土石放量最小。(3)分析综合考虑要平整出来的土地为二层的台阶块，且要求各块地的长、宽不少于60米，选择恰当的海拔高度开挖，方能使得总的土石方量最小。二、问题的分析2.1问题一本题要求利用附件1中的数据画出工厂的这片土地的三维图形与等高线图。观察数据可得，离散点分布比较稀疏，为了更精确地描述该区域地形，本文采用地质学常用的克里金插值法对离散的数值间进行内插，再根据插值后的散点画出三维图形和登高线图，并从中提取曲线、曲面等中间几何信息。2.2问题二本题要求在在问题一所建立的三维图形与等高线图的基础之上，利用其所给的初始条件值，参照数据点的坐标，在恰当合适的海拔高度平整一块800米600米的连片土地使总的土石方量最小，该问题是个普通的规划问题。在建模前首先考虑到该长方形区域与平面坐标轴X、Y轴可能不平行，因此设夹角为，则不能简单比较点的横纵坐标与长方形顶点的坐标的大小来判断点是否在长方形内，为方便计算区域内的散点，将坐标进行变换后再判断。其次，求取土方量涉及到曲面体积的求取，本文采用方格网方法，利用积分的思想求取。最后考虑到填挖平衡及工程费用的问题，在填挖土石的过程中应合理的考虑填挖平衡的实际问题使得填与挖到的土石之差越接近越好。在工程费用上又假设填土的每立方米所需的费用为挖山的每立方米土石方所需费用的1/3。根据以上的所述的条件和计算方法建立数学模型。2.3问题三本题要求如果平整出来的土地为两层的台阶状地块，利用已知的数据合适的海拔高度开挖一块长、宽不少于60米的地块，使总的土方量最少，即两块区域的长宽可变。可以将台阶状的土地看作是两个分段平面组成的分段函数，而求总的土方量最少的过程，可以看成是确定函数的定义域，并根据该区域的离散点利用最小二乘法所拟合出来的函数，以此来确定两个平面的海拔。在用以上的思想建模之前首先考虑必须使场地平土面积范围内所有微面积的土方体积的平方和6最小。再次尽量考虑到台阶上的设计高度，场地的设计高度由该点的坐标yx,决定的。最后考虑填挖时应符合实际情况，即要保证填挖平衡，而台阶的宽度及高度对填挖平衡和土方量的大小，因此台阶式土地的长度和宽度的变化也是考虑的因素。根据上述研究的定性分型和定量计算相结合的模型及解决现有的缺点又使的方案达到最优的经济效益。但同时本文在计算时有可能存在满足了约束条件，但目标函数达不到最优的情况，此时可寻求在满足约束条件下目标函数的次优解，使该模型有更宽广的应用价值，这可作为该方法下一步的研究方向。三、问题基本假设(1)假设题目中附件1中所给的数据都是真实可靠；(2)假设设计高程所占的土地面积很小，可以忽略不计；(3)假设设计高程即为所有海拔高度的平均值；(4)假设平整出来的平面与水平面平行，即平面没坡度；四、符号说明i诸权系数拉格朗日乘子hN数据的点数)(*h变异函数0C块金常数挖Q挖的土方量填Q填的土方量0H土石块的平均高度五、模型假设5.1土地三维模型的建立根据题目所提供的信息可知，假设题目中附件（1）中所给的数据均是真是可靠的，考虑的是空间属性在空间位置上的变异分布,确定对一个待插点值有影响的距离范围,然后用此范围内的采样点来估计待插点的属性值,在数学上可对所研究的对象提供一种最佳线性无偏估计(某点处的确定值)的方克里金法插值原理。设h是一个模为r=|h|,方向为的向量，则在方向上相应于向量h的实验变异函数)(*h可表示为如下形式：7)(*h=),(*ar=21)]()([21hNiiihxZhxZN(5.1.1)当获取实验变异函数之后，需要选择变异函数理论模型，然后对所选择的变异函数理论模型进行参数拟合。克里金插值法中的变异函数，其中变异函数理论模型一般分为有基台值和无基台值两大类。利用球状模型：ahCCahahahCChh0230],0()223(00)((5.1.2)相应0C=)(lim0hh称之为块金常数。则根据克里金插值原理,未采样点0x处的属性值0xZ估计值是n个已知采样点属性值的加权和,0xZ的协方差),(jixxCov存在且只有两点之间的位置有关满足0)]()([jixZxZE(5.1.3)依据无偏估计要求：)]([)]([00*xZExZE经推导可求得:11nii(5.1.4)在无偏条件下使得估计的方差达到最小，即：]})1(2)()([{100*niixZxZVarMin(5.1.5)其中：为拉格朗日乘子。可得求解权系数i（i=1,2，…,n）的方程组：nixxCovxxCovniijjinii,...,2,11),(),(101(5.1.6)求出诸权系数),...,2,1(nii后，就可以得到为采样点0x处的属性值)(0*xZ。若用变异函数),(jixx表示则形式为：nixxxxniijjinii,...,2,11),(),(101(5.1.7)由上式则易知：})]()({[21),(22121xZxZExx(5.1.8)易推导得：)()(10iniixZxZ),...2,1(nii(5.1.9)8通过已知所给的山地海拔数据，结合上述所给的条件，利用MATLAB软件使用克里金插值法绘出工厂的这片土地的三维图形与等高线图如下所示图5.1土地的三维图形图5.2土地的等高线示意图95.2平坡式场地平整的土方优化5.2.1坐标轴旋转长方形场地位置可能有如图所示的情况，即该场地可能平行于水平面的坐标轴或与其有各夹角。当出现后者的情况时，直接判断离散点是否在长方形区域内的过程比较复杂，因此本文采用将坐标系旋转即长方形长边与x轴夹角为φ(φ90̊)，坐标轴绕原点顺时针旋转φ(φ90̊)，坐标转换后再进行各顶点的求值及散点判断。坐标系旋转后，坐标的转换过程如下：设坐标轴旋转前点A的坐标为(x,y)，旋转后坐标为(x',y')，如图可知，sincosryrx，)sin()cos(ryrx(5.2.1)则已知旋转前坐标(x,y)的情况下，))(sin(tan))(cos(tan11xyryxyrx(5.2.2)其中，22xyr图5.3坐标轴旋转后坐标转换示意图图5.4800×600m长方形区域及山地俯视图5.2.2方格网法计算土方量对土方量的求取实质上是求离散点三维图的体积。在地质学中，求土方量的常用方法有断面法、等高线法、散点法、方格网法和DTM法。由第一问所描述的图形观察该地形复杂性不高但是起伏较大，根据它们各自的特点本文选择方格网法进行土方量的计算。方格网法采用积分的思想，首先将区域化整为零，即将区域分成m个一定长度的正方形方格，根据每个方格网的四个顶点采集的自然标高和输入设计标高，计算出标高差与方格网的面积相乘得到土石方体积，最后化零为整，即汇总所有方格网的土方量。其步骤如下：10(1)格网的划分：根据精度要求和场地范围的大小划分(2)确定桩点高度：利用测量仪器或内插法求出各个桩点的高度(3)求土石块的平均高程：计算公式为：nHHHHH4)432(0中拐边角(5.2.3)其中，0H是田块平均高程，角