对铺路问题建立的最优化模型.doc

对铺路问题建立的最优化模型摘要：非线性最优化方法是研究在众多解决变量间关系为非线性依存关系的问题的方案中，什么样的方案最优以及如何找出最优方案的一门科学。本文采用了两种方法，一种是非线性规划从而得出最优解，另一种是将连续问题离散化利用计算机穷举取最优的方法。根据A地与B地之间的不同地质有不同造价的特点，建立了非线性规划模型和穷举取最优解的模型，解决了管线铺设路线花费最小的难题。关键词：非线性最优化 目标函数 约束条件一、 最优化方法的概述1.1 发展简史公元前 500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。例如阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最优化方法真正形成为科学方法则在17世纪以后。17世纪，I.牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法。以后又进一步讨论具有未知函数的函数极值，从而形成变分法。这一时期的最优化方法可以称为古典最优化方法。第二次世界大战前后，由于军事上的需要和科学技术和生产的迅速发展，许多实际的最优化问题已经无法用古典方法来解决，这就促进了近代最优化方法的产生。近代最优化方法的形成和发展过程中最重要的事件有： 以苏联.康托罗维奇和美国G.B.丹齐克为代表的线性规划；以美国库恩和塔克尔为代表的非线性规划；以美国R.贝尔曼为代表的动态规划；以苏联.庞特里亚金为代表的极大值原理等。这些方法后来都形成体系，成为近代很活跃的学科，对促进运筹学、管理科学、控制论和系统工程等学科的发展起了重要作用。12 概念最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。本章将介绍最优化方法的研究对象、特点，以及最优化方法模型的建立和模型的分析、求解、应用。主要是线性规划问题的模型、求解（线性规划问题的单纯形解法）及其应用运输问题；以及动态规划的模型、求解、应用资源分配问题1.3 数学意义为了达到最优化目的所提出的各种求解方法。从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。1.4 模型的意义最优化模型一般包括变量、约束条件和目标函数三要素:变量:指最优化问题中待确定的某些量。变量可用x=(x1，x2,xn)T表示。约束条件:指在求最优解时对变量的某些限制,包括技术上的约束、资源上的约束和时间上的约束等。列出的约束条件越接近实际系统，则所求得的系统最优解也就越接近实际最优解。约束条件可用gi(x)0表示i=1,2，m，m 表示约束条件数；或xR(R表示可行集合)。目标函数：最优化有一定的评价标准。目标函数就是这种标准的数学描述，一般可用f(x)来表示，即f(x)=f(x1，x2,xn)。要求目标函数为最大时可写成；要求最小时则可写成。目标函数可以是系统功能的函数或费用的函数。它必须在满足规定的约束条件下达到最大或最小。1.5工作的步骤用最优化方法解决实际问题，一般可经过下列步骤：提出最优化问题，收集有关数据和资料；建立最优化问题的数学模型,确定变量,列出目标函数和约束条件；分析模型，选择合适的最优化方法；求解，一般通过编制程序，用计算机求最优解；最优解的检验和实施。上述 5个步骤中的工作相互支持和相互制约，在实践中常常是反复交叉进行1.6 最优化方法的应用最优化一般可以分为最优设计、最优计划、最优管理和最优控制等四个方面。最优设计:世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使许多设计优化问题得到解决。一个新的发展动向是最优设计和计算机辅助设计相结合。电子线路的最优设计是另一个应用最优化方法的重要领域。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用,并向计算机辅助搜索最佳配方、配比方向发展。最优计划:现代国民经济或部门经济的计划，直至企业的发展规划和年度生产计划，尤其是农业规划、种植计划、能源规划和其他资源、环境和生态规划的制订,都已开始应用最优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策。最优管理：一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和决策支持系统的建立和使用，使最优管理得到迅速的发展。最优控制：主要用于对各种控制系统的优化。例如，导弹系统的最优控制，能保证用最少燃料完成飞行任务,用最短时间达到目标;再如飞机、船舶、电力系统等的最优控制，化工、冶金等工厂的最佳工况的控制。计算机接口装置不断完善和优化方法的进一步发展，还为计算机在线生产控制创造了有利条件。最优控制的对象也将从对机械、电气、化工等硬系统的控制转向对生态、环境以至社会经济系统的控制。二、 铺路问题最优化模型2.1问题重述准备在A地与B地之间修建一条地下管线，B地位于A地正南面26km和正东40km交汇处，它们之间有东西走向岩石带。地下管线的造价与地质特点有关，下图给出了整个地区的大致地质情况，显示可分为三条沿东西方向的地质带，其宽度分别为：沙土地质带宽C1，C5；沙石地质带宽C2；沙石土地质带宽：C4；岩石地质带宽C3。在给定三种地质条件上每千米的修建费用的情况如下：地质条件沙土沙石土沙石岩石费用(万元/千米)12161828试解决以下几个问题：(1) 图中直线AB显然是路径最短的，但不一定最便宜；而路径ARSB过岩石和沙石的路径最短，但是否是最好的路径呢？试建立一个数学模型，确定最便宜的管线铺设路线。（若C1=6，C2=4，C3=5，C4=6，C5=5，确定最便宜的管线铺设路线。）(2) 铺设管线时，如果要求管线转弯时，角度至少为，确定最便宜的管线铺设路线。(3) 铺设管线时，如果要求管线必须通过位于沙石地质带或岩石地质带中的某一已知点P（位于A地正南面18km和正东30km交汇处）时，确定最便宜的铺设路线。2.2 模型假设1、修建费用仅与管线长度和不同地质的造价有关，不含其他费用；2、在无特殊要求情况下，管线可以向任意方向延伸；3、不考虑管线宽度；4、所有管线都铺设在同一水平面上；2.3符号说明 为修建总费用 为管线与沙土层中东西方向上的投影长度 为管线与沙石层中东西方向上的投影长度 为管线与岩石层中东西方向上的投影长度 为管线与沙石土层中东西方向上的投影长度（在问题三中指在过P点的东西方向的直线上的P点以西的投影长度） 为管线与沙土层中东西方向上的投影长度（在问题三中指在过P点的东西方向的直线上的P点以东的投影长度） 为管线与沙土层中东西方向上的投影长度 为沙土层每千米的修建费用 为沙石层每千米的修建费用 为岩石层每千米的修建费用 为沙石土层每千米的修建费用 为沙土层每千米的修建费用(在问题三中指在沙石土层每千米的修建费用) 为问题三中沙土层每千米的修建费用 在问题一、二中指沙石土层的宽度，在问题三中指沙石土层P点以上的半层的宽度 在问题一、二中指沙石土层的宽度，在问题三中指沙石土层P点以下的半层的宽度 问题三中最下面的沙土层的宽度2.4 问题分析2.4.1问题一: 本问题主要围绕由A点到B点铺设管线展开，要求花费最少。根据不同地质条件的花费，确定在某一土层中铺设管线的长度。我们采用了两种方法求得最少的花费，分别为非线性规划模型和逐点遍历模型。方案一：我们首先利用非线性规划求解，可以得出一个关于工程总造价的目标函数f(x)，而且可知f(x)在整个区域连续且可微，f(x)符合在某一点有局部极小点的条件。因此我们用迭代法求出极小值（用Matlab实现），我们分别选用了几组不同的初始值来保证所得到的极小值也是整个区域上的最小值。方案二：我们又用穷举法另外建立了一个模型，用来确保模型一的结果是最小值，采用C语言实现，我们先在每两种不同地质间的交界线上每隔0.1km确定一个点，然后每条交界线都任取一点，连线，得出一条路径。之后将每一条可能的路径都遍历一遍，将最小值和对应的点保存，得出结果。2.4.2问题二 本问题与问题一相比，增加了约束条件“要求管线转弯时，角度至少为”，我们在问题一所建立的两种模型的基础上均增加相应约束条件，通过求出管线转弯处的管线角度的正切值，并利用反正切函数得出管线角度，从而对管线的铺设方向加以限制，得出最少花费的管线铺设线路。2.4.3问题三 本问题要求铺设管线一定要经过一确定点P，因此可以将此问题分为两步，即从A到P的路径为第一步，从P到B的路径为第二步。因为从A到P的路径选择及其花费与从P到B的路径选择及其花费无关，所以求出第一步从A到P的最优解，以及第二步求从P到B的最优解，这两的最优解之和便为整个管线铺设的最优解。2.5 模型建立与求解2.5.1 问题一方案一:根据题意，在第个土层中的管线长度为所以，在该层中的修建花费为则总花费为因此得到目标函数 然后所要修建的地区为A地正南面26km和正东40km所表示的区域，在每个土层中管线在东西方向的投影长度应大于0km小于40km，且所有土层中管线在东西方向上的投影长度之和小于40km，因此可确定约束条件： 运用MATLAB软件编程，得到计算结果为总费用最小为748.6244万元，管线在各土层中在东西方向上的投影长度分别为15.6786km，3.1827 km，2.1839 km，5.8887km，13.0661km。方案二:先在每两种不同土层的交界线上每隔0.1km确定一个点，然后在每条交界线上都任取一点，并连线，得出一条可能路径。再将每一条可能的路径按公式逐一计算花费，找到花费的最小值和其对应的点，确定最优路径。在此方案中，采用C语言编程进行遍历，所得最优解为最小花费为748.625602万元，管线在各土层中在东西方向上的投影长度分别为15.70km,3.20km,2.20km,5.90km,13.00km。2.5.2 问题二 本题也为确定最便宜的管线铺设路线，所以与问题一有相同的目标函数及约束条件：;根据本题中所要求的管线转弯角度大于，利用管线在各土层中在东西方向上的投影长度与相应土层宽度得出管线转弯所形成的角的正切值，即，再利用反正切函数算出具体角度。由此得到新的约束条件： ;在问题一建立的模型的基础上，依据本题中新增非线性约束条件，建立新的模型，利用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。2.5.3问题三根据本题中管线必须通过已知点P（位于A地正南面18km和正东30km交汇处）的约束条件，我们将整个区域依据P点位置分成两部分，即以A点正东30km处为界，将沙土层分成两部分，使整个修建区域变成6个土层。在问题一所建立的模型上加以改进，使目标函数变为：并将约束条件改为：;利用非线性规划模型，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。2.6 模型的评价与改进对于模型一，存在的缺点是用Matlab中的fmincon函数所求最优解可能只是局部最优解，必须代入几组不同的初始迭代值，来确定所求解为全局最优解，但仍有可能遗漏。对于模型二，缺点是精度不够小，当精度取到0.1时，计算机要用几分钟才能得出结果，精度更小