最优化在数学建模中的应用_毕业论文.doc

最优化在数学建模中的应用海 南 大 学毕 业 论 文（设计）题 目： 最优化在数学建模中的应用 学 号： 20081605B008 年 级： 2009级 学 院： 信息科学技术学 系 别： 数学系 专 业： 数学与应用数学 完成日期： 2013 年 4 月 19 日 摘 要最优化方法是一种崭新的技术，它在自动控制、物质运输、机械设计、采矿冶金、工程规划等科学技术领域中有广泛应用，关键词：最优化方法、线性规划，目标函数、约束条件、决策变量AbstractIn the daily life and work we often encounter a variety of data need to 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 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 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.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选题背景及意义从理论上讲，通过学习最优化方法，不仅使我们处理实际问题更加方便快捷，而且可以训练我们的逻辑思维方式，体会最优化方法在数学建模中的巨大的实际意义，了解通过建模来解决实际问题的全过程，更可以使我们对最优化方法以及对Matlab软件的使用予以熟悉和巩固。在现实生活中，由于越来越趋于多元化发展的经济，使得数学的应用越来越广泛，其中越来越多的实际问题需要我们使用数学建模的思想来予以解决，而为了获得最优化的解决方式，从而获得最好的收益，最优化方法在数学建模中的应用也一步一步的被人们所了解，重视。人们通过对最优化思想的研究为今后处理各种各样实际问题，特别是愈来愈火的经济问题打下坚实的理论基础。1.2 国内外研究进展最优化问题的发展历史相当长久，最早开始于牛顿、拉格朗日时代，由于牛顿等对微积分的重要贡献，才使得差分方程法解决最优化问题的方法变成可行，先锋者包括贝诺利(Bemot)，欧拉(Eller)和拉格郎日等。20世纪50年代出现了高速计算机，最优化的发展进入蓬勃发展期，出现了大量的新型算法。Dantzig提出了解决线性规划问题的simplex方法；Bellman提出了动态规划的最优化最优性原理，使得约束最优化变为可能性；Kuhn和Tucher提出的最优化规划问题的充分和必要条件开创了非线性规划优化技术的基础。构成现代优化理论的相关技术是遗传算法GA、模拟退火SA、禁忌搜索、蚁群算法、神经网络、EDA、CMA-ES等现代启发式最优化算法，他们均是从上世纪60年代发展起来的，这些算法同样是建模产生的.1.3本文探讨的内容追求最优化目标基于人类的理想,最优化方法就是从众多可能方案中选择最佳者,以达到最优目标的科学方法。随着现代化生产的发展和科学技术的进步，人们越来越重视最优化方法。当求解一个实际的最优化问题时，首先要把这个问题进行转化，即建立数学模型，使得问题得到最优化的解决。而其中最难进行的就是模型的建立，万事开头难，建立一个好的模型是解决问题的关键，而好的模型的构造是一种创造，成功的模型往往是科学和艺术的结晶。本文就是通过对最优化方法和数学模型的学习与建立，浅谈最优化的一些实际问题如何通过数学模型的建立来解决，以及建模过程中遇到的问题如何解决，从而提高对所学知识的认识和理解能力。二、理论知识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=（x1，.，xn），称为问题的可行解，所有的可行点组成的集合称为问题的可行区域，记为D。由现行代数和微积分中求条件极值可以知道，当D为空集时，称该问题无解，D不是空集，但目标函数在D上面无界时，该问题无界，当D不是空集，且目标函数有有限个最优值，此时该问题有最优解。求一个线性规划问题就是判断该问题是否有最优解，当有最优解时，还需要在可行区域中求出使目标函数打到最小值的点，也就是目标函数的最优值。2.2线性规划的几种解法2.2.1图解法如果一个线性规划只有两个变量，则它的可行区域在平面上具体的能够被画出，便于直接观察，同事又可以快捷的使用目标函数与可行区域的关系，那么我们采用图解法解决该问题例：解线性规则 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实矩阵，我们知道，如果他有最优解，则必可以在某一点达到，因而只需要在基本可行解集合中寻找即可，单纯形方法主要思想就是先找一个基本可行解，判别它是否最优，不是就继续找，直到找到或者判定无界。直接用公式进行单纯形法是很不方便的，其中最复杂的就是进行基变换，但施行基变换所用的实际上是消元法，我们可以将单纯形法的全部过程在一个类似增广矩阵的数表上进行，这种表格称为单纯形表，利用单纯形表解决单纯形问题是非常简化的方法，这里就不赘述了。2.3 灵敏度分析在设计实际的线性规划模型时，所收集的数据不是很精确，另一方面在市场经济大环境下，信息瞬息万变，当研究数据发生变化时，考虑解的变化情况是很重要的，因此，灵敏度分析就相当重要。改变价值向量，或者是改变右端向量，在同样的约束条件下求解，当原问题只有个别数据改变，特别是变化幅度不大的时候，用灵敏度分析要比对原问题从头求解简便许多，而这正是很多具体问题在修改数据时候经常碰到的。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一维搜索法一维搜索问题又称为线性搜索问题，它是指目标函数为单位变量的非线性规划问题，其数学模型为其中t，对于t的取值为t的问题称为一维搜索问题，当t取值为0时的问题称为有效一维搜索问题。按照求解问题不同原则，算法分为两大类：精确一维搜索或者最优一维搜索，以及非精确一维搜索。其中精确搜索的两种重要方法：不用倒数的0.618法和使用倒数的Newton法，这里就不详述了。2.6无约束最优化模型N元函数的无约束非线性规划问题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,而其余的不等式约束有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=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(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;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*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. 易操作性，一方面公交公司的时刻表比较合理可行，另一方面驾驶员能容易记住自己的上班时间，以避免时间表混乱而引起误车现象。不足之处是用光滑曲线拟合的方法无法模拟真实的客流量曲线。3.3 资金最优使用方案设有400万元资金，要求在4年内使用完，若在一年内使用资金万元，则可获得效益万元（设效益不再投资），当年不用的资金可存入银行，年利率为10%，试制定出这笔资金的使用方案，以使4年的经济效益总和为最大。3.3.1 模型的建立针对现有的资金400万元，对于不同的使用方案，4年内所获得的效益的总和是不相同的。例如，第一年就将400万元全部用完，这获得的效益总和为万元；若前三年均不用这笔资金，而将它存入银行，则第四年时的本息和为万元，再将它全部用完，则效益总和为23.07万元，比第一种方案效益多3万元。所以用最优化方法可以制定出一种最优的使用方案，以使4年的经济效益总和为最大。设表示第年所使用的资金数，表示4年的效益总和，则目标函数为：决策变量的约束条件：每一年所使用资金数既不能为负数，也不能超过当年所拥有的资金数，即第一年使用的资金数，满足：第二年资金数，满足：（第一年末使用资金存入银行一年后的本利之和）；第三年资金数，满足：第四年资金数，满足：因此，资金使用问题的数学模型为：3.3.2 模型的求解上述建立的模型属于非线性规划模型，因此可以调用Matlab中的fmincon函数进行求解，即x,fval=fmincon(fun,x0,a,b,Aeq,beq,lb,ub)。首先，用极小化的形式将目标函数改写为：其次，将约束条件表示为：其中各输入参数为：然后编写目标函数的M文件，并将其保存为g.m。如下所示：其次在命令窗口中编写主程序： A=1.1 1 0 0;1.21 1.1 1 0;1.331 1.21 1.1 1;b=440 484 532.4;lb=0 0 0 0;ub=400 1000 1000 1000;x0=100 100 100 100;x,fval=fmincon(g,x0,A,b,lb,ub)将其运行就可以得到以下结果：即如表7所示。表7 资金最优使用方案年数第一年第二年第三年第四年现有资金/万元400347.4263.8148.2使用资金/万元84.2107.6128.9148.24年效益总和最大值为T=43.08万元，这是第一年用完全部资金效益20.0万元的两倍多，这也反映出进行定量的优化计算的作用。所以一些业内人士称最优化方法为“不需要增加投入就能增加产出的手段”。四、总结本文的整体构造主要分为两部分，第一部分主要讲述了两种优化模型的基本思想和解决方法，第二部分主要是给出了两个具体例子以说明优化模型在实际问题中的应用。课本中的各类优化问题均是实际问题的高度抽象，因为实际问题比较复杂，伴随着各种约束，这些都必须要认真考虑到，基础的理论为我们解决实际优化问题提供了可能。计算过程将借助软件求解，主要有Matlab，Maple，Lingo和Excel等，文中也采用了Excel解决了土方的运输问题。Matlab是功能很强大的一款软件，但是在解决优化问题上，编程显得繁琐，因此在本文也没有采用此软件，Lingo之所以得到广泛应用，是取决于它在解决优化问题方面的良好特性，简单易操作，结果可靠等。本文主要采用了Lingo和Excel解决文中的两个应用实例，结果符合实际，让人比较满意。致 谢在本论文的写作过程中，我的导师林彩霞老师倾注了大量的心血，从选题到开题报告，从写作提纲，到一遍又一遍地指出每稿中的具体问题，严格把关，循循善诱，在此我表示衷心感谢。同时我还要感谢在我学习期间给我极大关心和支持的各位老师以及关心我的同学和朋友。写作毕业论文是一次系统的学习过程，毕业论文的完成，同样也意味着新的学习生活的开始。参考文献1 刘立群.土方调配优化中运筹方法的改进J.I,Ik技术经济,2001(4):6163.2 李时椿.运输问题表上作业法的改进研究J.南京航空航天大学学报,2000,32(3):324329.3 贾春玉.运输问题新解法的探讨J.系统工程学报,2005,19(2):208217.4 郑文魁,徐胜春.“规划求解”在土方调配计算中的应用J.水利科技与经济,2006,12(10):678686.5 叶其孝.大学生数学建模竞赛辅导教材(一) , (二) , (三) , (四) M.长沙:湖南教育出版社, 1999.6 卢开澄,单目标.多目标与整数规划M.北京:清华大学出版社,1999.7 周义仓,赫孝良.数学建模实验M.西安:西安交通大学出版社,1999.8 叶其孝.数学建模教育与国际数学建模竞赛M.长沙:湖南教育出版社,1994.9 姜启源.数学模型(第二版) M.北京:高等教育出版社,1991.10 刘来福,曾文艺.数学模型与数学建模M.北京:北京师范大学出版社,1999.11 张继伟.车床管理优化模型J.数学的实践与认识,2000,(1):30-34.12 柳承茂.MATLAB5.x入门与应用M.北京:科学出版社,1999.13 张飞舟.公交车辆智能调度研究J.交通运输系统工程与信息,2001,(1).14 戴连责,刘正东.公交调度发车间隔多目标组合优化模型J.交通运输系统工程与信息,2007,7(4):43-46.15 吕鹏.公交车调度J.工程数学学报,2002,(19):75-80.16 薄立军,要尉鹏,王艳辉.公交车调度的规划教学模型J.工程数学学报,2002:67-74.附 录附录1 上下行各时段发车时间间隔调整表：时间段序号上行总车次数平均发车时间间隔(分钟)调整后的发车时间间隔1(分钟)车次数调整后的发车时间间隔2(分钟)车次数下行总车次数平均发车时间间隔(分钟)调整后的发车时间间隔1(分钟)车次数调整后的发车时间间隔2(分钟)车次数1610106/320203/2252.421531096.763763421.4124218232.6293144232.629314272.2221365134.64558163.8344126106610/106610/7125512/96.763768106610/78.68394996.7637687.574841087.5748496.763761187.57484115.5566512183.3312461935212312311.9122291487.57484212.82331815415154/106610/1