铺路问题的最优化模型
摘要
本文采用了两种方法，一种是非线性规划从而得出最优解，另一种是将连续问题离散化利用计算机穷举取最优的方法。
根据A地与B地之间的不同地质有不同造价的特点，建立了非线性规划模型和穷举取最优解的模型，解决了管线铺设路线花费最小的难题。
问题一：在本问题中，我们首先利用非线性规划模型求解，我们用迭代法求出极小值（用Matlab实现），计算结果为总费用最小为748.6244万元，管线在各土层中在东西方向上的投影长度分别为15.6786km，3.1827 km，2.1839 km，5.8887km，13.0661km。然后，我们又用穷举法另外建立了一个模型，采用C语言实现，所得最优解为最小花费为748.625602万元，管线在各土层中在东西方向上的投影长度分别为15.70km,3.20km,2.20km,5.90km,13.00km。
问题二：本问题加进了一个非线性的约束条件来使转弯处的角度至少为160度，模型二也是如此。非线性规划模型所得计算结果为最小花费为750.6084万元，管线在各土层中在东西方向上的投影长度分别为14.4566km,4.3591km,2.5984km,6.5387km,12.0472km。遍历模型所得最优解为最小花费为750.821154万元，管线在各土层中在东西方向上的投影长度分别为14.10km,4.30km, 2.70km,6.70km,12.20km。
问题三：因为管线一定要经过一确定点P，我们将整个区域依据P点位置分成两部分，即以A点正东30km处为界，将沙土层分成两部分。非线性规划模型最小花费为752.6432万元，管线在各土层中在东西方向上的投影长度分别为21.2613km,3.3459km,2.2639km,3.1288km,2.4102km,7.5898km。遍历模型最小花费为752.649007万元，管线在各土层中在东西方向上的投影长度分别为21.30km,3.30km,2.30km,3.10km,2.40km,7.60km。
关键词：非线性规划逐点遍历穷举法
一．问题重述
准备在A地与B地之间修建一条地下管线，B地位于A地正南面26km和正东40km 交汇处，它们之间有东西走向岩石带。地下管线的造价与地质特点有关，下图给出了整个地区的大致地质情况，显示可分为三条沿东西方向的地质带，其宽度分别为：沙土地质带宽C1，C5；沙石地质带宽C2；沙石土地质带宽：C4；岩石地质带宽C3。
在给定三种地质条件上每千米的修建费用的情况如下：
地质条件沙土沙石土沙石岩石
费用(万元/千米) 12 16 18 28
试解决以下几个问题：
(1) 图中直线AB显然是路径最短的，但不一定最便宜；而路径ARSB过岩石和沙石的路径最短，但是否是最好的路径呢？试建立一个数学模型，确定最便宜的管线铺设路线。（若C1=6，C2=4，C3=5，C4=6，C5=5，确定最便宜的管线铺设路线。）
160，确定最便宜的管线铺设路线。
(2) 铺设管线时，如果要求管线转弯时，角度至少为0
(3) 铺设管线时，如果要求管线必须通过位于沙石地质带或岩石地质带中的某一已知点P（位于A地正南面18km和正东30km交汇处）时，确定最便宜的铺设路线。
二.模型假设
1、修建费用仅与管线长度和不同地质的造价有关，不含其他费用；
2、在无特殊要求情况下，管线可以向任意方向延伸；
3、不考虑管线宽度；
4、所有管线都铺设在同一水平面上；
三.符号说明
()x f 为修建总费用
1x 为管线与沙土层1c 中东西方向上的投影长度
2x 为管线与沙石层2c 中东西方向上的投影长度 3x 为管线与岩石层3c 中东西方向上的投影长度
4x 为管线与沙石土层4c 中东西方向上的投影长度（在问题三中指在过P 点的东西方
向的直线上的P 点以西的投影长度）
5x 为管线与沙土层5c 中东西方向上的投影长度（在问题三中指在过P 点的东西方向
的直线上的P 点以东的投影长度）
6x 为管线与沙土层5c 中东西方向上的投影长度
1p 为沙土层1c 每千米的修建费用 2p 为沙石层2c 每千米的修建费用 3p 为岩石层3c 每千米的修建费用
4p 为沙石土层4c 每千米的修建费用
5p 为沙土层5c 每千米的修建费用(在问题三中指在沙石土层每千米的修建费用) 6p 为问题三中沙土层6c 每千米的修建费用
4c 在问题一、二中指沙石土层的宽度，在问题三中指沙石土层P 点以上的半层的宽
度
5c 在问题一、二中指沙石土层的宽度，在问题三中指沙石土层P 点以下的半层的宽
度
6c 问题三中最下面的沙土层的宽度
四.问题分析
4．1 问题一:
本问题主要围绕由A 点到B 点铺设管线展开，要求花费最少。根据不同地质条件的花费，确定在某一土层中铺设管线的长度。我们采用了两种方法求得最少的花费，分别为非线性规划模型和逐点遍历模型。
4．1．1 方案一
我们首先利用非线性规划求解，可以得出一个关于工程总造价的目标函数f(x)，而且可知f(x)在整个区域连续且可微，f(x)符合在某一点有局部极小点的条件。因此我们用迭代法求出极小值（用Matlab 实现），我们分别选用了几组不同的初始值来保证所得到的极小值也是整个区域上的最小值。
4．1．2 方案二
我们又用穷举法另外建立了一个模型，用来确保模型一的结果是最小值，采用C 语言实现，我们先在每两种不同地质间的交界线上每隔0.1km 确定一个点，然后每条交界线都任取一点，连线，得出一条路径。之后将每一条可能的路径都遍历一遍，将最小值和对应的点保存，得出结果。
4．2 问题二
本问题与问题一相比，增加了约束条件“要求管线转弯时，角度至少为0
160”，我们在问题一所建立的两种模型的基础上均增加相应约束条件，通过求出管线转弯处的管线角度的正切值，并利用反正切函数得出管线角度，从而对管线的铺设方向加以限制，得出最少花费的管线铺设线路。
4．3 问题三
本问题要求铺设管线一定要经过一确定点P ，因此可以将此问题分为两步，即从A 到P 的路径为第一步，从P 到B 的路径为第二步。因为从A 到P 的路径选择及其花费与从P 到B 的路径选择及其花费无关，所以求出第一步从A 到P 的最优解，以及第二步求从P 到B 的最优解，这两的最优解之和便为整个管线铺设的最优解。
五.模型建立与求解
5．1 问题一
5．1．1 方案一.
根据题意，在第i 个土层中的管线长度为
22i i i c x d +=
所以，在该层中的修建花费为
i i i d p S ⨯=
则总花费为
