最优化方法课程设计.doc

1、课程设计报告2016年6月14日摘要最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决策等各个领域，而最优化模型与方法广泛应用于工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各个部门及各个领域。伴随着计算机技术的高速发展，最优化理论与方法的迅速进步为解决实际最优化问题的软件也在飞速发展其中，MATLAB软件已经成为最优化领域应用最广的软件之一。有了MATLAB这个强大的计算平台，既可以利用MATLAB优化工具箱(OptimizationToolbox)中的函数，又可以通过算法变成实现相应的最优化计算。关键词：优化、线性规划，黄金分割法、最速下降法、MATLAB、算法A

2、bstractOptimizationtheoryandmethodsandmoreattention,havepenetratedintotheproduction,management,business,military,decision-makingandotherfields,andoptimizationmodelsandmethodswidelyusedinindustry,agriculture,transportation,commerce,defense,construction,students,governmentvariousdepartmentsandagencies

3、andotherfields.Withtherapiddevelopmentofcomputertechnology,optimizationtheoryandmethodsfortherapidprogressoftheoptimizationproblemtosolvepracticalsoftwareisalsodevelopingrapidly.Which,MATLABsoftwarehasbecomethemostoptimizationsoftwareisoneofthemostwidelyused.WiththispowerfulcomputingplatformMATLAB,e

4、itherusingMATLABoptimizationtoolbox(OptimizationToolbox)inthefunction,butalsocanachievetheappropriatealgorithmtooptimizeintothecalculation.Keywords:Optimization、Goldensectionmethod、steepestdescentmethod、MATLAB、algorithm第一章单纯形算法的基本思想与原理1.1 单纯形算法的基本思路单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到

5、另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。求解步骤：（1）确定初始基可行解 从线性规划标准形的系数矩阵中能直接找出m个线性独立的单位向量； 对约束条件全为“<=”连接的LP,化为标准形，左端添加松弛变量后即形成一个单位子矩阵； 约束条件中含有“<=”或“=”连接的方程，在插入剩余变量后找不到单位矩阵，则必须采用“人造基”法，也称“人工变量”法。（2）最优性检验及解的判别准则 最优性判定准则 多重最优解判定准则 无界最优解判定准则（3）换基迭代 确定换入变量 确定换出变量

6、 枢运算（旋转运算）1.2 算法流程图是(Yes刿断得到棊本可行解是否最优结栗求出使日标得到改薔的呈本可行解求出一个初始基本可行解¥1.3用matlab编写源程序Functionx,f=zuiyouhua(A,b,c)Size(A)=m,n;i=n+1:n+m;N=1:n;B=eye(m,m);xb=b'xn=zeros(m,1);f1=0;w=zeros(1,m);z=-c;flag=1;while(1)a,k=max(z);Ifa<=0flag=0;breakelsey=inv(B)*A(:,k)ify<=0flag=0;fprintf('不存在最优解

7、')breakendt=find(y>0);a,rl=min(bl(t)/y(t)r=t(rl);i(:,k)=kB(:,k)=A(:,k);cb=C(:,i);xb=inv(B)*b;b0=xb;x=zeros(1,n+m)x(:,i)=xb'f=cb*xbz=cb*inv(B)*A-C;endend1.4 单纯形算法应用举例线性规划问题：minf(x)=0.1x+0.3x+0.9x+0x+1.1x+0.2x+0.8x+1.4x123456782x+x+x+x>10012342x+x+3x+2x+x>100s.t<23567x+x+3x+2x+3x+4

8、x>100134678x,x,x,x,x,x,x,x>012345678在matlab的命令窗口输入：A=2,1,1,1,0,0,0,0;0,2,1,0,3,2,1,0;1,0,1,3,0,2,3,4;b=100,100,100'c=0.1,0.3,0.9,0,1.1,0.2,0.8,1.4;x,f=zuiyouhua(A,b,c)Matlab输出内容：x=10500300000f=-16第二章黄金分割法的基本思想与原理2.1 黄金分割法的基本思路黄金分割法适用于b,a区间上的任何单股函数求极小值问题，对函数除要求“单峰”外不做其他要求，甚至可以不连续。因此，这种方法的适应

9、面非常广。黄金分割法也是建立在区间消去法原理基础上的试探方法，即在搜索区间a,b内适当插入两点a1,a2,并计算其函数值。1用2，将区间分成三段，应用函数的单峰性质，通过函数值大小的比较，删去其中一段，是搜索区间得以缩小。然后再在保留下来的区间上作同样的处理，如此迭代下去，是搜索区间无限缩小，从而得到极小点的数值近似解。2.2算法流程图2.3用matlab编写源程序a=input（'请输入初始区间下端点:na='）;b=input（'请输入初始区间上端点:nb='）;e=input（'请输入计算精度:ne='）;t=b-a;whilet>e

10、a1=a+0.382*(b-a);a2=a+0.618*(b-a);f1=question2(a1);f2=question2(a2);iff1<f2b=a2;elsea=a1;endt=b-a;endX1=(b+a)/2;F1=question2(X1);fprintf('最优解为：nX1=%8.6f,nF1=%8.6f',X1,F1);2.4 黄金分割法应用举例自定义函数：functiony=koko(x)y=x*(x+2);运行结果：请输入初始区间下端点:a=-3请输入初始区间上端点:b=5请输入计算精度:e=0.3最优解为：X1=-0.973876,F1=-0.9

11、99318第三章最速下降法的基本思想与原理3.1 最速下降法的基本思路最速下降法的基本思想是：从当前点xk出发，取函数f(x)在点xk处下降最快的方向作为我们的搜索方向Pk.由f(x)的Taylor展式知f(xk)f(xk+tpk)=-tVf(xk)Tpk+o(|tpk|)略去t的高阶无穷小项不计，可见取Pk=Vf(xk)时，函数值下降得最多。于是，我们可以构造出最速下降法的迭代步骤。解无约束问题的的最速下降法计算步骤第1步选取初始点X0，给定终止误差£>0，令k:二0；第2步计算Vf(xk)，若IlYf(xk)|<8，停止迭代输出xk.否则进行第三步；第3步取pk=-V

12、f(Xk)；第4步进行一维搜索，求t，使得=minf(xk+tpk)t>0kf(Xk+tpk)k令xk+i=xk+1pk，k:=k+1，转第2步。k由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点3.2算法流程图3.3用matlab编写源程序functionR,n=steel(x0,y0,eps)symsx;symsy;f=(x-2)A2+(y-4)A2;v=x,y;j=jacobian(f,v);T=subs(j(1),x,x0),subs(j(2),y,y0);temp=sqrt(T(1)A2+(T(2)A2);x1=x0;y1=y0;n=0;symskk;

13、while(temp>eps)d=-T;f1=x1+kk*d(1);f2=y1+kk*d(2);fT=subs(j(1),x,f1),subs(j(2),y,f2);fun=sqrt(fT(1)A2+(fT(2)A2);Mini=Gold(fun,0,1,0.00001);x0=x1+Mini*d(1);y0=y1+Mini*d(2);T=subs(j(1),x,x0),subs(j(2),y,y0);temp=sqrt(T(1)A2+(T(2)A2);x1=x0;y1=y0;n=n+1;endR=xO,yO%调用黄金分割法：functionMini=Gold(f,a0,b0,eps)s

14、ymsx;formatlong;symskk;u=a0+0.382*(b0-a0);v=a0+0.618*(b0-a0);k=0;a=a0;b=b0;array(k+1,1)=a;array(k+1,2)=b;while(b-a)/(b0-a0)>=eps)Fu=subs(f,kk,u);Fv=subs(f,kk,v);if(Fu<=Fv)b=v;v=u;u=a+0.382*(b-a);k=k+1;else%if(Fu>Fv)a=u;u=v;v=a+0.618*(b-a);k=k+1;endarray(k+1,1)=a;array(k+1,2)=b;endMini=(a+b)

15、/2;3.4 最速下降法应用举例函数f=(x-2)八2+(y-4)八2;在命令窗口输入R,n=steel(0,1,0.00001)运行结果如下：R=1.9999999999828113.999999999974216R=1.9999999999828113.999999999974216第四章惩罚函数法的基本思想与原理4.1 惩罚函数法的基本思路罚函数法求解带约束的非线形规划问题的基本思想是：利用问题的目标函数和约束函数构造出带参数的所谓增广目标函数，把约束非线形规划问题转化为一系列无约束非线形规划问题来求解。增广目标函数由两个部分构成，一部分是原问题的目标函数，另一部分是由约束函数构造出的“

16、惩罚”项，“惩罚”项的作用是对“违规”的点进行“惩罚”。罚函数法主要有两种形式。一种称为外部罚函数法，或称外点法，这种方法的迭代点一般在可行域的外部移动，随着迭代次数的增加，“惩罚”的力度也越来越大，从而迫使迭代点向可行域靠近；另一种成为内部罚函数法，或称内点法，它从满足约束条件的可行域的内点开始迭代，并对企图穿越可行域边界的点予以“惩罚”，当迭代点越接近边界，“惩罚”就越大，从而保证迭代点的可行性。4.2 算法流程图给定X(0)、M(0)、c、£k=0k=k+lX(o)二X*(M(k)M(k+1)二cM(k)i=0X*(M(k)X*(M(k)二X(i)e(X,M(k)we(x(i)

17、ii<£fX*(M(k-1)-Y4.3 用matlab编写源程序globallamada%主程序main2.m，惩罚数方法x0=11;lamada=2;c=10;e=1e-5;k=1;whilelamada*q4_fun2p(x0)>=ex0=fminsearch('q4_fun2min',x0);lamada=c*lamada;k=k+1;enddisp('最优解'),disp(xO)Kfunctionr=q4_fun2p(x)%罚项函数r=(x(1)-1)A3-x(2)*x(2)A2;functionr=q4_fun2min(x)%辅助函数globallamadar=x(1)A2+x(2F2+lamada*q4_fun2p(x);4.4 惩罚函数法应用举例求解非线性规划问题：min(x1A2+x2A2)S.t.(x1-1)A3-x2A2