铺路问题的最优化模型

《铺路问题的最优化模型》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、贵州工程应用技术学院（数学建模论文）题目:铺路问题的最优化模型专业班级：2013级数学与应用数学学生姓名：袁敏学号：39241113125【摘要】本文采用了两种方法，一种是非线性规划从而得出最优解，另一种是将连续问题离散化利用计算机穷举取最优的方法。根据A地与B地之间的不同地质有不同造价的特点，建立了非线性规划模型和穷举取最优解的模型，解决了管线铺设路线花费最小的难题。问题一：在本问题中，我们首先利用非线性规划模型求解，我们用迭代法求出极小值（用Matlab实现），计算结果为总费用最小为748.6244万元，管线在各土

2、层中在东西方向上的投影长度分别为15.6786km,3.1827km,2.1839km,5.8887km,13.0661km。然后，用穷举法另外建立了一个模型，采用C语言实现，所得最优解为最小花费为748.625602万元，管线在各土层中在东西方向上的投影长度为15.70km,3.20km,2.20km,5.90km,13.00kmo问题二：本问题加进了一个非线性的约束条件来使转弯处的角度至少为160度，模型二也是如此。非线性规划模型所得计算结果为最小花费为750.6084万元，管线在各土层中在东西方向上的投影长度分别

3、为14.4566km,4.3591km,2.5984km,6.5387km,12.0472kmo遍历模型所得最优解为最小花费为750.821154万元，管线在各土层中在东西方向上的投影长度分别为14.10km,4.30km,2.70km,6.70km,12.20kmo问题三：因为管线一定要经过一确定点P,我们将整个区域依据P点位置分成两部分，即以A点正东30km处为界，将沙土层分成两部分。非线性规划模型最小花费为752.6432万元，管线在各土层中在东西方向上的投影长度分为21.2613km,3.3459km,2.26

4、39km,3.1288km,2.4102km,7.5898kmo遍历模型最小花费为752.649007万元，管线在各土层中在东西方向上的投影长度分别为21.30km,3.30km,2.30km,3.10km,2.40km,7.60kmo【关键词】非线性规划，逐点遍历，穷举法一.问题重述准备在A地与B地之间修建一条地下管线，B地位于A地正南面26km和正东40km交汇处，它们之间有东西走向岩石带。地下管线的造价与地质特点有关，下图给出了整个地区的大致地质情况，显示可分为三条沿东西方向的地质带，其宽度分别为：沙土地质带宽C

5、l,C5；沙右地质带宽C2；沙石土地质带宽：C4；岩石地质带宽C3。Ci66C4C5B在给定三种地质条件上每千米的修建费用的情况如下:地质条件沙土沙石土沙石ULi费用（万元/千米）12161828试解决以下几个问题:(1)图中直线AB显然是路径最短的，但不一定最便宜；而路径ARSB过岩石和沙石的路径最短，但是否是最好的路径呢？试建立一个数学模型，确定最便宜的管线铺设路线。(若C1二6,C2=4,C3=5,C4=6,C5=5,确定最便宜的管线铺设路线。)(2)铺设管线时，如果要求管线转弯时，角度至少为160。，确定最便宜

6、的管线铺设路线。(3)铺设管线时，如果要求管线必须通过位于沙石地质带或岩石地质带中的某一已知点P(位于A地正南面18km和正东30km交汇处)时，确定最便宜的铺设路线。一.模型假设1、修建费用仅与管线长度和不同地质的造价有关，不含其他费用；2、在无特殊要求情况下，管线可以向任意方向延仲；3、不考虑管线宽度；4、所有管线都铺设在同一水平面上；二.符号说明/(%)为修建总费用X,为管线与沙土层C,中东西方向上的投影长度x2为管线与沙石层C2中东西方向上的投影长度心为管线与岩石层5中东西方向上的投影长度x4为管线与沙石土层"

7、中东西方向上的投影长度(在问题三中指在过P点的东西方向的直线上的P点以西的投影长度）x5为管线与沙土层C5中东西方向上的投影长度（在问题三中指在过P点的东西方向的直线上的P点以东的投影长度）耳为管线与沙土层C5中东西方向上的投影长度Pi为沙土层C

8、每千米的修建费用p2为沙石层5每千米的修建费用p3为岩石层C3每千米的修建费用久为沙石土层©每千米的修建费用p5为沙土层C5每千米的修建费用（在问题三中指在沙石土层每千米的修建费用）几为问题三中沙土层C6每千米的修建费用c4在问题一、二中指沙石土层的宽度，在问题三中指沙石土层

9、P点以上的半层的宽度c5在问题一、二中指沙石土层的宽度，在问题三中指沙石土层P点以下的半层的宽度Q问题三中最下面的沙土层的宽度四•问题分析4.1问题一：本问题主要围绕由A点到B点铺设管线展开，要求花费最少。根据不同地质条件的花费，确定在某一土层中铺设管线的长度。我们采用了两种方法求得最少的花费，分别为非线性规划模型和逐点遍历模型。