最优化方法课程设计

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

2、速下降法、MATLAB、算法AbstractOptimization theory and methods and more attention, have penetrated into the production, management, business, military, decision-making and other fields, and optimization models and methods widely used in industry, agriculture, transportation, commerce, defense, construction,

3、students, government various departments and agencies and other fields. With the rapid development of computer technology, optimization theory and methods for the rapid progress of the optimization problem to solve practical software is also developing rapidly. Which, MATLAB software has become the

4、most optimization software is one of the most widely used. With this powerful computing platform MATLAB, either using MATLAB optimization toolbox (OptimizationToolbox) in the function, but also can achieve the appropriate algorithm to optimize into the calculation.Key words: Optimization、Golden sect

5、ion method、steepest descent method、 MATLAB、algorithm第一章单纯形算法的基本思想与原理1.1单纯形算法的基本思路单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优 解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是， 则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出 问题的最优解。如果问题无最优解也可用此法判别。求解步骤：（1）确定初始基可行解从线性规划标准形的系数矩阵中能直接找出m个线性独立的单位向量；对约束条件全为“二”连接的LP，化为标准形，左端添加松弛变量后即形成 一个单位子

6、矩阵；约束条件中含有“二”或仁”连接的方程，在插入剩余变量后找不到单位矩 阵，则必须采用“人造基”法，也称“人工变量”法。（2）最优性检验及解的判别准则最优性判定准则多重最优解判定准则无界最优解判定准则（3）换基迭代确定换入变量确定换出变量枢运算（旋转运算）1.2算 法 流 程 图求出一个初始基本可行解I字断得到基*可行解是否乒无结束 否求H4便目标得到改善的基本可行解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=zer

7、os(1,m);z=-c;flag=1;while(1)a,k=max(z);If a=0flag=0;breakelsey=inv(B)*A(:,k)if y0);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)=xbf=cb*xbz=cb*inv(B)*A-C;endend1.4单纯形算法应用举例线性规划问题：min f (X = 0.1x + 0.3x + 0.9 x + 0 x + 1.1x + 0.2 x + 0.8 x +1.4 x123

8、456782x + x + x + x 10012342x + x + 3x + 2x + x 100s.t 23567x + x + 3 x + 2 x + 3 x + 4 x 100 x , 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,100c=0.1,0.3,0.9,0,1.1,0.2,0.8,1.4;x,f=zuiyouhua(A,b,c)Matlab输出内容：x=10 50 0 30 0 0 0 0f=-16第

9、二章黄金分割法的基本思想与原理2.1黄金分割法的基本思路黄金分割法适用于b,a 区间上的任何单股函数求极小值问题,对函数除要求“单 峰”外不做其他要求，甚至可以不连续。因此，这种方法的适应面非常广。黄金 分割法也是建立在区间消去法原理基础上的试探方法，即在搜索区间a,b内适当 插入两点a1,a2,并计算其函数值a1,a2,将区间分成三段，应用函数的单峰性质， 通过函数值大小的比较，删去其中一段，是搜索区间得以缩小。然后再在保留下 来的区间上作同样的处理，如此迭代下去，是搜索区间无限缩小，从而得到极小 点的数值近似解。2.2算法流程图2.3用matlab编写源程序a=input（请输入初始区间下

10、端点:na=）;b=input（请输入初始区间上端点:nb=）;e=input（请输入计算精度:ne=）;t=b-a;while tea1=a+0.382*(b-a);a2=a+0.618*(b-a);f1=question2(a1);f2=question2(a2);if f1 0,令k ：= 0 ；第2步 计算w (xk)，若IIW (xk)IMg，停止迭代.输出xk .否则进行第三步；第 3 步取pk =-Vf (xk)；=min f (xk + tpk)t 0第4步 进行一维搜索，求tk，使得f (Xk + t pk )令 Xk+1 = Xk + k，k := k +1，转第 2 步。

11、由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。3.2算法流程图开始求人使其满足3.3用matlab编写源程序function R,n=steel(x0,y0,eps) syms x;syms y;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;syms kk;while (tempeps)d=-T;f1=x1+kk*d(1);f2=y1+kk*d(2);fT=subs(j(1),x,

12、f1),subs(j(2),y,f2);fun=sqrt(fT (1)八2+(仃(2)八2);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=x0,y0%调用黄金分割法：function Mini=Gold(f,a0,b0,eps)syms x;format long;syms kk;u=a0+0.382*(b0-a0);v=a0+0.618*(b0-a0);k

13、=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(FuFv)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)/2;3.4最速下降法应用举例函数 f=(x-2)A2+(y-4)A2;在命令窗口输入R,n=steel(0,1,0.00001) 运行结果如下：R =1.9999999999828113.999999999974216R = 1.99

14、99999999828113.999999999974216第四章惩罚函数法的基本思想与原理4.1惩罚函数法的基本思路罚函数法求解带约束的非线形规划问题的基本思想是：利用问题的目标函数和约 束函数构造出带参数的所谓增广目标函数，把约束非线形规划问题转化为一系列 无约束非线形规划问题来求解。增广目标函数由两个部分构成，一部分是原问题 的目标函数，另一部分是由约束函数构造出的“惩罚”项，“惩罚”项的作用是 对“违规”的点进行“惩罚”。罚函数法主要有两种形式。一种称为外部罚函数 法，或称外点法，这种方法的迭代点一般在可行域的外部移动，随着迭代次数的 增加，“惩罚”的力度也越来越大，从而迫使迭代点向可

15、行域靠近；另一种成为 内部罚函数法，或称内点法，它从满足约束条件的可行域的内点开始迭代，并对 企图穿越可行域边界的点予以“惩罚”，当迭代点越接近边界，“惩罚”就越大， 从而保证迭代点的可行性。4.2算法流程图给定X（。）、啤（。）、c、Y4.3用mat lab编写源程序global lamada %主程序main2.m，惩罚数方法 x0 = 1 1;lamada = 2;c = 10;e = 1e-5;k = 1;while lamada*q4_fun2p(x0) = ex0 = fminsearch(q4_fun2min,x0);lamada = c*lamada;k = k+1;enddisp(最优解),disp(x0)Kfunction r = q4_fun2p(x)%罚项函数r = (x(1)-1)A3-x(2)*x(2)A2;function r = q4_fun2min(x)%辅助函数global lamadar = x(1)A2+x(2)A2+lamada*q4_fun2p(x);4.4惩罚函数法应用举例求解非线性规划问题：min (x1八2+x2八2)S.t. (x1-1)八3-x2八2=0运行结果如下：最优解1.00012815099