非线性规划推选优秀ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,非线性规划(guhu),第一页，共44页。,1,实验(shyn)目的,实验(shyn)内容,2、掌握(zhngw)用数学软件求解优化问题。,1、直观了解非线性规划的基本内容。,1、非线性规划的基本理论。,4、实验作业。,2、用数学软件求解非线性规划。,3、钢管订购及运输优化模型,第二页，共44页。,2,*非线性规划(guhu)的基本解法,非线性规划(guhu)的基本概念,非线性规划(guhu),返回,第三页，共44页。,3,定义 如果(rgu)目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,非现性规划(guhu)的基本概念,一般形式,:,（1）,其中 ，是定义在 E,n,上的实值函数，简记:,其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般(ybn)形式,第四页，共44页。,4,定义1,把满足问题（1）中条件的解 称为,可行解,（或可行,点,），,所有可行点的集合称为,可行集,（或,可行域,）,记为D即,问题(1)可简记为 ,定义2,对于问题(1)，设 ，若存在 ,使得对一切,，且 ，都有 ，则称X,*,是f(X)在D上的,局部极小值点,（,局部最优解,）,特别地当 时，若 ，则称X,*,是f(X)在D上的,严格局部极小值点,（,严格局部最优解,）,定义3,对于问题(1),设 ,对任意的 ,都有 则称X,*,是f(X)在D上的,全局极小值点,（,全局最优解,）,特别地当,时，若 ，则称X,*,是f(X)在D上的,严格全局极小值点,（,严格全局最优解,）,返回(fnhu),第五页，共44页。,5,非线性规划(guhu)的基本解法,SUTM外点法,SUTM内点法（障碍(zhng i)罚函数法）,1、罚函数法,2、近似(jn s)规划法,返回,第六页，共44页。,6,罚函数法,罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解(qi ji)这类方法称为序列无约束最小化方法简称为SUMT法,其一为SUMT外点法，其二为SUMT内点法,第七页，共44页。,7,其中T(X,M)称为,罚函数,，M称为,罚因子,，,带M的项称为,罚项,，,这里的罚函数只对不满足约束条件的点实行惩罚：当 时，满足各 ，故罚项=0，不受惩罚当 时，必有 的约束条件，故罚项0，要受惩罚,SUTM外点法,第八页，共44页。,8,罚函数法的缺点是：每个近似(jn s)最优解Xk往往不是容许解，而只能近似(jn s)满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误,1、任意给定初始点X0，取M11，给定允许误差 ，令k=1；,2、求无约束极值问题 的最优解，设为Xk=X(Mk)，即,；,3、若存在(cnzi)，使 ，则取MkM()令k=k+1返回（2），否则，停止迭代得最优解 .,计算时也可将收敛性判别准则 改为 .,SUTM外点法(罚函数法)的迭代(di di)步骤,第九页，共44页。,9,SUTM内点法（障碍(zhng i)函数法）,第十页，共44页。,10,改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。,第四十一页，共44页。,M文件(wnjin),SUTM外点法(罚函数法)的迭代(di di)步骤,function g,ceq=mycon(x),f=exp(x(1),6798 0 0 3.,x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);,(8)x,fval,exitflag,output=fmincon(.,algorithm:1x44 char,第三十四页，共44页。,内点法的迭代(di di)步骤,第十一页，共44页。,11,近似规划法的基本思想：将问题(3)中的目标函数 和约束条件 近似为线性函数，并对变量(binling)的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为(3)的解的近似,近似(jn s)规划法,每得到一个近似解后，都从这点出发(chf)，重复以上步骤,这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。,第十二页，共44页。,12,近似(jn s)规划法的算法步骤如下,第十三页，共44页。,13,返回(fnhu),第十四页，共44页。,14,用MATLAB软件求解,其输入(shr)格式如下:,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,X0);,5.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);,6.x,fval=quaprog(.);,7.x,fval,exitflag=quaprog(.);,8.x,fval,exitflag,output=quaprog(.);,1、二次规划(guhu),第十五页，共44页。,15,例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,MATLAB（youh1）,1、写成标准(biozhn)形式：,2、输入(shr)命令：,H=1-1;-1 2;,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、运算(yn sun)结果为：,s.t.,第十六页，共44页。,16,1.首先建立M文件fun.m,定义目标(mbio)函数F（X）:,function f=fun(X);,f=F(X);,2、一般(ybn)非线性规划,其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它(qt)变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：,第十七页，共44页。,17,3.建立主程序.非线性规划求解(qi ji)的函数是fmincon,命令的基本格式如下：,(1)x=fmincon(fun,X0,A,b),(2)x=fmincon(fun,X0,A,b,Aeq,beq),(3)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB),(4)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon),(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options),(6)x,fval=fmincon(.),(7)x,fval,exitflag=fmincon(.),(8)x,fval,exitflag,output=fmincon(.),输出(shch)极值点,M文件(wnjin),迭代的初值,参数说明,变量上下限,第十八页，共44页。,18,注意：,1 fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置(shzh)为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。,2 fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。,3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关。,第十九页，共44页。,19,1、,写成标准形式,：,s.t.,2x,1,+3x,2,6,s.t x,1,+4x,2,5,x,1,x,2,0,例2,第二十页，共44页。,20,罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解(qi ji)这类方法称为序列无约束最小化方法简称为SUMT法,其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当 时，满足各 ，故罚项=0，不受惩罚当 时，必有 的约束条件，故罚项0，要受惩罚,总的吨千米数比上面(shng min)结果略优.,exitflag=1,MATLAB(youh2),1 fmincon函数提供了大型优化算法和中型优化算法。,x=quadprog(H,C,A,b,Aeq,beq);,计算时也可将收敛性判别准则 改为 .,9293 0 6.,*非线性规划(guhu)的基本解法,求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.,f=exp(x(1),2、一般(ybn)非线性规划,3主程序youh3.,VLB=0 0;VUB=5 10;,g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;,2、先建立(jinl)M-文件 fun3.m:,function f=fun3(x);,f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,MATLAB(youh2),3、再建立(jinl)主程序youh2.m：,x0=1;1;,A=2 3;1 4;b=6;5;,Aeq=;beq=;,VLB=0;0;VUB=;,x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB),4、运算(yn sun)结果为：,第二十一页，共44页。,21,1先建立M文件 fun4.m,定义(dngy)目标函数:,function f=fun4(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定义(dngy)非线性约束：,function g,ceq=mycon(x),g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;,第二十二页，共44页。,22,3主程序youh3.m为:,x0=-1;1;,A=;b=;,Aeq=1 1;beq=0;,vlb=;vub=;,x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon),MATLAB(youh3),3.运算(yn sun)结果为：,第二十三页，共44页。,23,例4,1先建立M-文件fun.m定义目标(mbio)函数:,function f=fun(x);,f=-2*x(1)-x(2);,2再建立M文件(wnjin)mycon2.m定义非线性约束：,function g,ceq=mycon2(x),g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;,第二十四页，共44页。,24,3.主程序fxx.m为:,x0=3;2.5;,VLB=0 0;VUB=5 10;,x,fval,exitflag,output,=fmincon(