《最优化在数学建模中的应用毕业论文.doc》由会员分享，可在线阅读，更多相关《最优化在数学建模中的应用毕业论文.doc（28页珍藏版）》请在三一办公上搜索。
1、海 南 大 学毕 业 论 文（设计）题 目： 最优化在数学建模中的应用 学 号： 20081605B008 年 级： 2009级 学 院： 信息科学技术学 系 别： 数学系 专 业： 数学与应用数学 完成日期： 2013 年 4 月 19 日 摘 要最优化方法是一种崭新的技术，它在自动控制、物质运输、机械设计、采矿冶金、工程规划等科学技术领域中有广泛应用，关键词：最优化方法、线性规划，目标函数、约束条件、决策变量AbstractIn the daily life and work we often encounter a variety of data need to be processed
2、, 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 that the pra
3、ctical 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 model of th
4、e 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.1线性规划模型62.2线
5、性规划的几种解法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= ，如果原问题是求目标函数最大值，可等价转换为求 的最小值。一个满足所有约束条件的向量x=（x
10、1，.，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的非线性函数，则
14、（MP）的可行域为非线性。当p=0，q=0，时，将可行域简记为minf（x）称其为无约束非线性规则或无约束最优化问题，如（MP）中X，则对应的称为约束非线性规划或约束最优化问题。2.5一维搜索法一维搜索问题又称为线性搜索问题，它是指目标函数为单位变量的非线性规划问题，其数学模型为其中t，对于t的取值为t的问题称为一维搜索问题，当t取值为0时的问题称为有效一维搜索问题。按照求解问题不同原则，算法分为两大类：精确一维搜索或者最优一维搜索，以及非精确一维搜索。其中精确搜索的两种重要方法：不用倒数的0.618法和使用倒数的Newton法，这里就不详述了。2.6无约束最优化模型N元函数的无约束非线性规划
15、问题min f（x）的求解，其中x=（x1，xn）T ，f：Rn 。这些方法通常称为无约束最优化方法。无约束最优化方法大体上分为两类：解析法与直接法，解析法就是在计算中要用到函数的一阶导数，或者二阶导数，直接法就是在计算过程中仅使用函数值的方法。其中两种解析法应用较为简单，最速下降法和共轭方向法。在这里不做过多叙述。2.7约束最优化模型设（MP）问题的可行域为 gi（x），i=1，.，p X= x hj（x）=0 ，j=1，q对该问题的一个可行点x* ，它满足所有的等式约束，若令j=，则hj（x*）=0，j但它所满足的全部不等式约束则可能有两种情况，对某些不等式约束有gi(x*)=0,而其余的
16、不等式约束有gi（x*）=6;c2=12;c3=12;c4=12;c5=6;c6=6;c7=6;c8=6;c9=6;c10=6;c11=6;c12=6;c13=6;c14=6;c15=6;c16=6;c17=6;50*c1=701;50*c2=2943;50*c3=5018;50*c4=2705;50*c5=1528;50*c6=1193;50*c7=1355;50*c8=1200;50*c9=1040;50*c10=881;50*c11=871;50*c12=2133;50*c13=2772;50*c14=897;50*c15=464;50*c16=410;50*c17=701;120*c2
17、=2943;120*c3=5018;120*c4=2705;120*c5=1528;120*c6=1193;120*c7=1355;120*c8=1200;120*c9=1040;120*c10=881;120*c11=871;120*c12=2133;120*c13=2772;120*c14=897;120*c15=464;120*c16=410;120*c17=275;gin(c1);gin(c2);gin(c3);gin(c4);gin(c5);gin(c6);gin(c7);gin(c8);gin(c9);gin(c10);gin(c11);gin(c12);gin(c13);gin(
18、c14);gin(c15);gin(c16);gin(c17);End(2)下行程序：Model: Min=z;z=c1+c2+c3+c4+c5+c6+c7+c8+c9+c10+c11+c12+c13+c14+c15+c16+c17;c1=6;c2=12;c3=12;c4=12;c5=6;c6=6;c7=6;c8=6;c9=6;c10=6;c11=6;c12=6;c13=6;c14=6;c15=6;c16=6; 图3 下行程序求解结果c17=6;50*c1=1039;50*c2=2752;50*c3=3223;50*c4=1822;50*c5=1093;50*c6=986;50*c7=860;
19、50*c8=891;50*c9=1017;50*c10=1302;50*c11=2196;50*c12=3612;50*c13=2417;50*c14=1091;50*c15=781;50*c16=774;50*c17=1039;120*c2=2752;120*c3=3223;120*c4=1822;120*c5=1093;120*c6=986;120*c7=860;120*c8=891;120*c9=1017;120*c10=1302;120*c11=2196;120*c12=3612;120*c13=2417;120*c14=1091;120*c15=781;120*c16=774;120
20、*c17=337;gin(c1);gin(c2);gin(c3);gin(c4);gin(c5);gin(c6);gin(c7);gin(c8);gin(c9);gin(c10);gin(c11);gin(c12);gin(c13);gin(c14);gin(c15);gin(c16);gin(c17);End3.2.3小结1. 普适性，模型对任意客流量调查和运营资料都可以给出较优的调度方案。2. 模型不仅接触了较优的调度，而且还得出了该方案照顾到乘客和公交车公司双方利益的程度（即灵敏度）。3. 该模型较稳定，不随某一控制量的微小变化而导致方案的较大改变。4. 易操作性，一方面公交公司的时刻表
21、比较合理可行，另一方面驾驶员能容易记住自己的上班时间，以避免时间表混乱而引起误车现象。不足之处是用光滑曲线拟合的方法无法模拟真实的客流量曲线。3.3 资金最优使用方案设有400万元资金，要求在4年内使用完，若在一年内使用资金万元，则可获得效益万元（设效益不再投资），当年不用的资金可存入银行，年利率为10%，试制定出这笔资金的使用方案，以使4年的经济效益总和为最大。3.3.1 模型的建立针对现有的资金400万元，对于不同的使用方案，4年内所获得的效益的总和是不相同的。例如，第一年就将400万元全部用完，这获得的效益总和为万元；若前三年均不用这笔资金，而将它存入银行，则第四年时的本息和为万元，再将它全部用完，则效益总和为23.07万元，比第一种方案效益多3万元。所以用最优化方法可以制定出一种最优的使用方案
