《最优化在数学建模中的应用.doc》由会员分享，可在线阅读，更多相关《最优化在数学建模中的应用.doc（30页珍藏版）》请在金锄头文库上搜索。
1、最优化在数学建模中的应用海 南 大 学毕 业 论 文（设计）题 目： 最优化在数学建模中的应用 学 号： 20081605B008 年 级： 2009级 学 院： 信息科学技术学 系 别： 数学系 专 业： 数学与应用数学 完成日期： 2013 年 4 月 19 日 摘 要最优化方法是一种崭新的技术，它在自动控制、物质运输、机械设计、采矿冶金、工程规划等科学技术领域中有广泛应用，关键词：最优化方法、线性规划，目标函数、约束条件、决策变量AbstractIn the daily life and work we often encounter a variety of data need to
2、be processed, we usually take the mathematical modeling approach to abstraction, the actual problems by using mathematical knowledge, mathematical model is established, and then by using the method of mathematics and computer technology to solve. So the complex practical problems are simplified, so
3、that the practical problem can be solved.The optimization method plays a more and more important role in solving practical problems, this paper through several practical to introduce how to through the establishment of mathematical model, to get the results. Through the establishment of mathematical
4、 model of the actual problem, and the optimal treatment method to explain and elaborate practical life, great to do with optimization method. Keywords: optimization, linear programming, objective function, constraint condition, the decision variables目 录一、引言51.1选题背景及意义51.2国内外研究进展51.3本文探讨的内容5二、理论知识62.
5、1线性规划模型62.2线性规划的几种解法62.2.1图解法62.2.2单纯形法72.3灵敏度分析82.4非线性规划模型82.5一维搜索法82.6无约束最优化模型92.7约束最优化模型9三、应用实例103.1工程施工的土方运输问题103.11 模型的建立113.1.2数据的处理123.1.3运用Excel求解的具体操作步骤1331.4模型的求解143.2公交车调度问题173.2.1模型的建立183.2.2模型的求解193.2.3小结223.3 资金最优使用方案223.3.1 模型的建立223.3.2 模型的求解23四、总结24附录127附录228一、 引言1.1选题背景及意义从理论上讲，通过学习
6、最优化方法，不仅使我们处理实际问题更加方便快捷，而且可以训练我们的逻辑思维方式，体会最优化方法在数学建模中的巨大的实际意义，了解通过建模来解决实际问题的全过程，更可以使我们对最优化方法以及对Matlab软件的使用予以熟悉和巩固。在现实生活中，由于越来越趋于多元化发展的经济，使得数学的应用越来越广泛，其中越来越多的实际问题需要我们使用数学建模的思想来予以解决，而为了获得最优化的解决方式，从而获得最好的收益，最优化方法在数学建模中的应用也一步一步的被人们所了解，重视。人们通过对最优化思想的研究为今后处理各种各样实际问题，特别是愈来愈火的经济问题打下坚实的理论基础。1.2 国内外研究进展最优化问题的
7、发展历史相当长久，最早开始于牛顿、拉格朗日时代，由于牛顿等对微积分的重要贡献，才使得差分方程法解决最优化问题的方法变成可行，先锋者包括贝诺利(Bemot)，欧拉(Eller)和拉格郎日等。20世纪50年代出现了高速计算机，最优化的发展进入蓬勃发展期，出现了大量的新型算法。Dantzig提出了解决线性规划问题的simplex方法；Bellman提出了动态规划的最优化最优性原理，使得约束最优化变为可能性；Kuhn和Tucher提出的最优化规划问题的充分和必要条件开创了非线性规划优化技术的基础。构成现代优化理论的相关技术是遗传算法GA、模拟退火SA、禁忌搜索、蚁群算法、神经网络、EDA、CMA-ES
8、等现代启发式最优化算法，他们均是从上世纪60年代发展起来的，这些算法同样是建模产生的.1.3本文探讨的内容追求最优化目标基于人类的理想,最优化方法就是从众多可能方案中选择最佳者,以达到最优目标的科学方法。随着现代化生产的发展和科学技术的进步，人们越来越重视最优化方法。当求解一个实际的最优化问题时，首先要把这个问题进行转化，即建立数学模型，使得问题得到最优化的解决。而其中最难进行的就是模型的建立，万事开头难，建立一个好的模型是解决问题的关键，而好的模型的构造是一种创造，成功的模型往往是科学和艺术的结晶。本文就是通过对最优化方法和数学模型的学习与建立，浅谈最优化的一些实际问题如何通过数学模型的建立
9、来解决，以及建模过程中遇到的问题如何解决，从而提高对所学知识的认识和理解能力。二、理论知识2.1线性规划模型线性规划问题的一般形式为： min z =c1x1+.+cnxn st ai1x1+ai2x2+.+ainxn=bi ，i=1，.，p ai1x1+ai1x2+.+ainxnbi i=p+1，m xj0 ， j=1，.q xj0, j=q+1,.n其中xj，j=1，n，为待定的决策变量，已知的系数aij组成的矩阵 a11 a12 . a1n A= a21 a22 . a2n . am1 am2 . amn目标函数：z= ，如果原问题是求目标函数最大值，可等价转换为求 的最小值。一个满足所
10、有约束条件的向量x=（x1，.，xn），称为问题的可行解，所有的可行点组成的集合称为问题的可行区域，记为D。由现行代数和微积分中求条件极值可以知道，当D为空集时，称该问题无解，D不是空集，但目标函数在D上面无界时，该问题无界，当D不是空集，且目标函数有有限个最优值，此时该问题有最优解。求一个线性规划问题就是判断该问题是否有最优解，当有最优解时，还需要在可行区域中求出使目标函数打到最小值的点，也就是目标函数的最优值。2.2线性规划的几种解法2.2.1图解法如果一个线性规划只有两个变量，则它的可行区域在平面上具体的能够被画出，便于直接观察，同事又可以快捷的使用目标函数与可行区域的关系，那么我们采用
11、图解法解决该问题例：解线性规则 max z=-x1+x2 st 2x1-x2 x1-2x2 x1+x2 x1 x2解这一问题的可行区域如图所示，变量x1，x2的非负约束决定了图形在第一象限内，由3个不等式决定了可行区域的范围，即图上阴影部分，当移动到A2时，继续移动就不再相交，则A2为最优解，最优值为Z=-1+4=3.求解上述过程的方法即为图解法图1 图解法2.2.2单纯形法考虑标准形式的LP问题 min z =cTx st Ax=b x仍假设D非空，秩（A）=mn，A为-m实矩阵，我们知道，如果他有最优解，则必可以在某一点达到，因而只需要在基本可行解集合中寻找即可，单纯形方法主要思想就是先找
12、一个基本可行解，判别它是否最优，不是就继续找，直到找到或者判定无界。直接用公式进行单纯形法是很不方便的，其中最复杂的就是进行基变换，但施行基变换所用的实际上是消元法，我们可以将单纯形法的全部过程在一个类似增广矩阵的数表上进行，这种表格称为单纯形表，利用单纯形表解决单纯形问题是非常简化的方法，这里就不赘述了。2.3 灵敏度分析在设计实际的线性规划模型时，所收集的数据不是很精确，另一方面在市场经济大环境下，信息瞬息万变，当研究数据发生变化时，考虑解的变化情况是很重要的，因此，灵敏度分析就相当重要。改变价值向量，或者是改变右端向量，在同样的约束条件下求解，当原问题只有个别数据改变，特别是变化幅度不大
13、的时候，用灵敏度分析要比对原问题从头求解简便许多，而这正是很多具体问题在修改数据时候经常碰到的。2.4非线性规划模型关于非线性规划问题，这里举个简单的例子进行说明。令x=（x1，xn）T是n维欧式空间Rn中的一个点，f（x），gi（x），i=1，.，p和j=1，.q是定义在Rn上的实值函数，我们称如下的模型为数学规划。 min f（x） st gi（x），i=1，p hj（x）=0 ，j=1，.，q 令X=称X为（MP）的约束集，当目标函数f（x），约束函数gi（x），i=1，.，p和hj（x），j=1，.，q皆为x的线性函数时，数学规划（MP）就是线性规划，若其中的目标函数和约束函数中至少有一个是x的非线性函数，则（MP）的可行域为非线性。当p=0，q=0，时，将可行域简记为minf（x）称其为无约束非线性规则或无约束最优化问题，如（MP）中X，则对应的称为约束非线性规划或约束最优化问题。2.5一维搜索法
