页脚. 铺路问题的最优化模型 摘 要 本文采用了两种方法，一种是非线性规划从而得出最优解，另一种是将连续问题离散化利用计算机穷举取最优的方法。 根据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，确定最便宜的管线铺设路线。）

(2) 铺设管线时，如果要求管线转弯时，角度至少为0160，确定最便宜的管线铺设路线。 (3) 铺设管线时，如果要求管线必须通过位于沙石地质带或岩石地质带中的某一已知点P（位于A地正南面18km和正东30km交汇处）时，确定最便宜的铺设路线。

二.模型假设 1、修建费用仅与管线长度和不同地质的造价有关，不含其他费用； 2、在无特殊要求情况下，管线可以向任意方向延伸； 3、不考虑管线宽度； 4、所有管线都铺设在同一水平面上； 页脚.

三.符号说明 xf 为修建总费用

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 问题二 本问题与问题一相比，增加了约束条件“要求管线转弯时，角度至少为0160”，我们在问题一所建立的两种模型的基础上均增加相应约束条件，通过求出管线转弯处的管线角度的正切值，并利用反正切函数得出管线角度，从而对管线的铺设方向加以限制，得出最少花费的管线铺设线路。

4．3 问题三 本问题要求铺设管线一定要经过一确定点P，因此可以将此问题分为两步，即从A到P的路径为第一步，从P到B的路径为第二步。因为从A到P的路径选择及其花费与从P到B的路径选择及其花费无关，所以求出第一步从A到P的最优解，以及第二步求从P到B的最优解，这两的最优解之和便为整个管线铺设的最优解。

五.模型建立与求解 5．1 问题一 5．1．1 方案一.

根据题意，在第i个土层中的管线长度为

22iiicxd

所以，在该层中的修建花费为

iiidpS 则总花费为 页脚.

5122)(iiiicxpxf

因此得到目标函数 5122)(:miniiiicxpxf

然后所要修建的地区为A地正南面26km和正东40km所表示的区域，在每个土层中管线在东西方向的投影长度应大于0km小于40km，且所有土层中管线在东西方向上的投影长度之和小于40km，因此可确定约束条件：

400ix

4051iix 运用MATLAB软件编程，得到计算结果为总费用最小为748.6244万元，管线在各土层中在东西方向上的投影长度分别为15.6786km，3.1827 km，2.1839 km，5.8887km，13.0661km。

5．1．2方案二 先在每两种不同土层的交界线上每隔0.1km确定一个点，然后在每条交界线上都任取一点，并连线，得出一条可能路径。再将每一条可能的路径按公式

5122)(iiiicxpxf

逐一计算花费，找到花费的最小值和其对应的点，确定最优路径。在此方案中，采用C语言编程进行遍历，所得最优解为最小花费为748.625602万元，管线在各土层中在东西方向上的投影长度分别为15.70km,3.20km,2.20km,5.90km,13.00km。

5．2 问题二 本题也为确定最便宜的管线铺设路线，所以与问题一有相同的目标函数

5122)(:miniiiicxpxf

及约束条件： 400ix;

4051iix;

根据本题中所要求的管线转弯角度大于0160，利用管线在各土层中在东西方向上的 页脚.

投影长度与相应土层宽度得出管线转弯所形成的角的正切值，即iicx，再利用反正切函数算出具体角度。由此得到新的约束条件： 0arctanarctan21807011iiiicxcx; 4,3,2,1i

0180110arctanarctan211iiii

cxc

x; 4,3,2,1i

在问题立的模型的基础上，依据本题中新增非线性约束条件，建立新的模型，利用MATLAB编程，所得计算结果为最小花费为750.6084万元，管线在各土层中在东西方向上的投影长度分别为14.4566km,4.3591km,2.5984km,6.5387km,12.0472km。 利用相同的约束条件，利用C语言编程遍历，所得最优解为最小花费为750.821154万元，管线在各土层中在东西方向上的投影长度分别为14.10km,4.30km, 2.70km,6.70km,12.20km。

5．3 问题三 根据本题中管线必须通过已知点P（位于A地正南面18km和正东30km交汇处）的约束条件，我们将整个区域依据P点位置分成两部分，即以A点正东30km处为界，将沙土层分成两部分，使整个修建区域变成6个土层。在问题一所建立的模型上加以改进，使目标函数变为：

6122)(:miniiiicxpxf

并将约束条件改为： 300ix; 4,3,2,1i

;100ix 6,5i

3041iix;

1065iix;

利用非线性规划模型，MATLAB编程，所得最优解为:最小花费为752.6432万元，管线在各土层中在东西方向上的投影长度分别为21.2613km,3.3459km,2.2639km, 3.1288km,2.4102km,7.5898km 利用遍历模型，C语言编程，所得最优解为：最小花费为752.649007万元，管线在各土层中在东西方向上的投影长度分别为21.30km,3.30km,2.30km,3.10km,2.40km, 7.60km。