数学规划问题.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,最优化计算方法,一、实验目的,第一节 线性规划问题的计算方法,1,、了解线性规划问题及可行解、最优解的概念,；,2,、掌握,Matlab,软件关于求解线性规划的语句和方法。,二、实验原理和方法：,在生活实践中，很多重要的实际问题都是线性的（至少能,够用线性函数很好的近似表示），所以我们一般把这些问,题化为线性的目标函数和约束条件进行分析，通常将目标,函数和约束都是线性表达式的规划问题称为线性规划。,它的一般形式是：,也可以用矩阵形式来表示：,线性规划的可行解是满足约束条件的解；线性规划的最优解是使目标函数达到最优的可行解。,线性规划关于解的情况可以是：,1,、无可行解，即不存在满足约束条件的解；,2,、有唯一最优解，即在可行解中有唯一的最优解；,4,、有可行解，但由于目标函数值无界而无最优解。,3,、有无穷最优解，即在可行解中有无穷个解都可使目,标函数达到最优；,一般求解线性规划的常用方法是单纯形法和改进,的单纯形法，这类方法的基本思路是先求得一个可行,解，检验是否为最优解；若不是，可用迭代的方法找,到另一个更优的可行解，经过有限次迭代后，可以找,到可行解中的最优解或者判定无最优解。,三、内容与步骤：,在,Matlab,优化工具箱中，,linprog,函数是使用单纯形法求解,下述线性规划问题的函数。,它的命令格式为：,其中：,A,为约束条件矩阵，,b,c,分别为目标函数的系数向量和,约束条件中最右边的数值向量；也可设置解向量的上界,vlb,和,下界,vub,，即解向量必须满足,vlb,=x=,vub,；还可预先设置,初始解向量,x0,。,如果没有不等式，只有等式时，,A=,b=;,输出的结果：,x,表示最优解向量；,fval,表示最优值。,【,例,1】,求解线性规划问题：,解：考虑到,linprog,函数只解决形如,的线性规划。所以先要将线性规划,变为如下形式：,然后建立,M,文件如下：,c=-3;1;1;A=1-2 1;4-1-2;b=11;-3;,aeq,=2 0-1;beq=-1;vlb=0;0;0;,x,fval,=,linprog(c,A,b,aeq,beq,vlb,),以,lianxi1,作为文件名保存此,M,文件后，在命令窗口,输入,lianxi1,后即可得到结果：,x=4.0000,1.0000,9.0000,同时返回,fval,=-2,对应到原来的线性规划中即知目标函数的最大值为,2,，此时,x1=4,x2=1,x3=9,。,第二节 无约束规划计算方法,一、实验目的,1,、了解无约束规划问题的求解原理与方法,；,2,、会用,Matlab,软件求解无约束规划问题。,二、实验原理和方法,无约束规划问题的解法一般按目标函数的形式分为两大类：,一类是一元函数的一维搜索法，如黄金分割法、插值法等；,另一类是求解多元函数的下降迭代法。,迭代的基本思想和步骤大致可分为以下四步：,三、实验内容与步骤,在,Matlab,软件中，求解无约束规划的常用命令是：,x=fminunc(fun,x0),其中，,fun,函数应预先定义到,M,文件中，并设置初始,解向量为,x0,。,【,例,2】,求解,取,解：首先建立函数文件,fun1.m,以,fun1,为文件名保存此函数文件。,在命令窗口输入：,x0=-2;4;,x=fminunc(fun1,x0),结果显示：,f=,-1.0000,x=,1.0000,1.0000,即极小值为,-1,，是,x1=1,x2=1,时取得。,【,例,3】,解非线性方程组,解：解此非线性方程组等价于求解无约束非线性规划问题：,然后建立函数文件,fun2.m,在命令窗口输入：,x0=0;0;,x=fminunc(fun2,x0),结果显示：,f=5.2979e-011,x=1.0673,0.1392,则非线性方程组的解为,x1=1.0673,x2=0.1392,。,第三节,约束非线性规划计算方法,一、实验目的,1,、,了解约束非线性规划问题的求解原理与方法,；,2,、,会用,Matlab,软件求解约束非线性规划问题。,二、实验原理和方法,对于约束非线性规划，随着目标函数和约束条件的不同，,解法也不同，一般来说，有两类方法：,（,1,）将约束问题化为无约束问题的求解方法；,（,2,）用线性规划来逼近非线性规划；,三、实验内容与步骤,约束非线性规划的一般形式为：,其中，,f(x,),为多元实值函数,;,g(x,),为向量函数,并且,f(x),g(x,),中至少有一个函数是非线性函数的（否则成为线性规划问题）。,x=fmincon(,fun,x0,A,b),x=fmincon(,fun,x0,A,b,aeq,beq),x=fmincon(,fun,x0,A,b,aeq,beq,lb,ub),x=fmincon(,fun,x0,A,b,aeq,beq,lb,ub,nonlcon),在,Matlab,优化工具箱中，,fmincon,函数是用,SQP,算法来,解决一般的约束非线性规划的函数，它的命令格式为：,【,例,4】,求解约束非线性规划：,(,初值为,1;1),解,:,首先建立一个,m,文件,fun3.m,function y=fun3(x),y=-exp(x(1)*x(2)2*(3-exp(x(1)-x(2)2);,存储为,fun3.m,首先将问题转化为,matlab,要求的格式,;,即求出,fun,A,b,aeq,beq,X0,Lb,Ub,然后建立一个,m,文件,fun4.m,function,c,cep,=fun4(x),c=;,%c,为非线性不等式,且为,c=0,cep,=exp(x(1)+x(2)2-3;,%,cep,为非线性等式,然后存储为,fun,4.m,最后在命令窗口中输入：,A=;b=;,aeq,=;,beq,=;Lb=;,Ub,=;,x,f,=fmincon(,fun3,1;1,fun4,),-f,因题目中有非线性约束条件，所以建立非线性约束,m-,文件。,结果为,:,x=0.8852,0.7592,f=6.2043e-016,ans,=-6.2043e-016,最后的结果为,:,-6.2043e-016,【,例,5】,求解约束非线性规划：,解：首先建立一个,m,文件,fun5.m,function y=fun5(x),y=(x(1)-1)2+(x(2)-2)2+(x(3)-3)2+(x(4)-4)2;,存储为,fun5.m,文件,.,x0=1;1;1;1;A=1 1 1 1;3 3 2 1;,B=5;10;aeq=;,beq,=;,Lb=0;0;0;0;,x,g,=fmincon(,fun5,x0,A,B,aeq,beq,Lb),答案为,:,x=0.0000,0.6667,1.6665,2.6668,g=,6.3333,非现性规划的基本概念,定义,如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,一般形式,:,（,1,）,其中 ，是定义在,E,n,上的实值函数，简记,:,其它情况,:,求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式,用,MATLAB,软件求解,其输入格式如下,:,1.x=,quadprog(H,C,A,b,);,2.x=,quadprog(H,C,A,b,Aeq,beq,);,3.x=,quadprog(H,C,A,b,Aeq,beq,VLB,VUB,);,4.x=,quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X,0,);,5.x=,quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X,0,options);,6.,x,fval,=,quaprog,(.);,7.,x,fval,exitflag,=,quaprog,(.);,8.,x,fval,exitflag,output,=,quaprog,(.);,1,、二次规划,例,1,min f(x,1,x,2,)=-2x,1,-6x,2,+x,1,2,-2x,1,x,2,+2x,2,2,s.t,.x,1,+x,2,2,-x,1,+2x,2,2,x,1,0,x,2,0,1,、写成标准形式：,2,、输入命令：,H=2-2;-2 4;,c=-2;-6;A=1 1;-1 2;b=2;2;,Aeq,=;,beq,=;VLB=0;0;VUB=;,x,z,=,quadprog(H,c,A,b,Aeq,beq,VLB,VUB,),3,、运算结果为：,x=0.8 1.2 z=-7.2,s.t,.,1.,首先建立,M,文件,fun.m,定义目标函数,F,（,X,）,:,function f=,fun(X,);,f=F(X);,2,、一般非线性规划,其中,X,为,n,维变元向量，,G(X),与,Ceq(X,),均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同,.,用,Matlab,求解上述问题，基本步骤分三步：,3.,建立主程序,.,非线性规划求解的函数是,fmincon,命令的基本格式如下：,(1),x=,fmincon,(fun,X,0,A,b),(2),x=,fmincon,(fun,X,0,A,b,Aeq,beq),(3),x=,fmincon,(fun,X,0,A,b,Aeq,beq,VLB,VUB,),(4),x=,fmincon,(fun,X,0,A,b,Aeq,beq,VLB,VUB,nonlcon),(5),x=,fmincon,(fun,X,0,A,b,Aeq,beq,VLB,VUB,nonlcon,options),(6),x,fval,=,fmincon,(.),(7),x,fval,exitflag,=,fmincon,(.),(8)x,fval,exitflag,output=,fmincon,(.),输出极值点,M,文件,迭代的初值,参数说明,变量上下限,1,、写成标准形式：,s.t,.,2x,1,+3x,2,6,s.t,x,1,+4x,2,5,x,1,x,2,0,例,2,2,、先建立,M-,文件,fun6.m:,function f=fun6(x);,f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,3,、再建立主程序,youh1.m,：,x0=1;1;,A=2 3;1 4;b=6;5;,Aeq,=;,beq,=;,VLB=0;0;VUB=;,x,fval,=fmincon(fun6,x0,A,b,Aeq,beq,VLB,VUB),4,、运算结果为：,x=0.7647 1.0588,fval,=-2.0294,1,先建立,M,文件,fun7.m,定义目标函数,:,function f=fun7(x);,f=exp(x(1),*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,x,1,+x,2,=0,s.t,.1.5+x,1,x,2,-x,1,-x,2,0,-x,1,x,2,10,0,例,3,2,再建立,M,文件,mycon.m,定义非线性约束：,function,g,ceq,=,mycon(x,),g=1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;,ceq,=,3,主程序,youh2.m,为,:,x0=-1;1;,A=;b=;,Aeq,=1 1;beq=0;,vlb,=;,vub,=;,x,fval,=fmincon(fun7,x0,A,b,Aeq,beq,vlb,vub,mycon),4.,运算结果为：,x=-1.2247 1.2247,fval,=1.8951,例,4,1,先建立,M-,文件,fun8.m,定义目标函数,:,function f=fun8(x);,f=-2*x(1)-x(2);,2,再建立,M,文件,mycon2.m,定义非线性约束：,function,g,ceq,=mycon2(x),g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;,ceq,=;,3.,主程序,youh3.m,为,:,x0=3;2.5;,VLB=0 0;VUB=5 10;,x,fval,=fmincon(fun8,x0,VLB,VUB,mycon2),4.,运算结果为,:,x=,4.0000,3.0000,fval,=-11.0000,