数学建模第6讲-非线性规划课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学建模,*,实验目的,实验内容,2,掌握用数学软件求解优化问题,1,直观了解非线性规划的基本内容,1,非线性规划的基本理论,4,实验作业,2,用数学软件求解非线性规划,3,钢管订购及运输优化模型,11/12/2024,1,数学建模,*,非线性规划的基本解法,非线性规划的基本概念,非线性规划,返回,11/12/2024,2,数学建模,定义,如果目标函数或约束条件中至少有一个是非线性函数,则最优化问题就叫做,非线性规划问题,非现性规划的基本概念,一般形式,:,（,1,）,其中 ，是定义在,R,n,上的实值函数，简记,:,其它情况,:,求目标函数的最大值，或约束条件小于等于零两种情况，都可通过取其相反数化为上述一般形式,1,n,j,1,n,i,1,n,R,:,h,R,:,g,R,:,R,R,R,f,(,),n,T,n,R,x,x,x,X,=,2,1,L,(,),(,),=,=,=,.,.,2,1,0,m,;,1,2,.,0,.,.,l,j,X,h,i,X,g,t,s,j,i,11/12/2024,3,数学建模,定义,1,把满足问题（,1,）中条件的解 称为,可行解,（或可行,点,），,所有可行点的集合称为,可行集,（或,可行域,）,记为,D,即,问题,(1),可简记为 ,定义,2,对于问题,(1),设,若存在,使得对一切,且,都有,则称,X,*,是,f,(,X,),在,D,上的,局部极小值点,（,局部最优解,）,特别地,当 时，若,则称,X,*,是,f,(,X,),在,D,上的,严格局部极小值点,（,严格局部最优解,）,定义,3,对于问题,(1),设,若对任意的,都有,则称,X,*,是,f(X,),在,D,上的,全局极小值点,（,全局最优解,）,特别地,当,时，若,则称,X,*,是,f,(,X,),在,D,上的,严格全局极小值点,（,严格全局最优解,）,返回,),(,n,R,X,(,),(,),n,j,i,R,X,X,h,X,g,X,D,=,=,0,0,|,(,),(,),X,f,X,f,*,11/12/2024,4,数学建模,非线性规划的基本解法,SUTM,外点法,SUTM,内点法（障碍罚函数法）,1,罚函数法,2,近似规划法,返回,11/12/2024,5,数学建模,罚函数法,罚函数法,基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为,序列无约束最小化方法,简称为,SUMT,法,其一为,SUMT,外点法,，其二为,SUMT,内点法,11/12/2024,6,数学建模,其中,T,(,X,M,),称为,罚函数,，,M,称为,罚因子,，,带,M,的项称为,罚项,，,这里的罚函数只对不满足约束条件的点实行惩罚,:,当 时，满足各 ，故罚项为,0,，不受惩罚当 时,必有约束条件 ，故罚项大于,0,，要受惩罚,SUTM,外点法,11/12/2024,7,数学建模,罚函数法的,缺点,：每个近似最优解,X,k,往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着,M,k,的增大，可能导致错误,1,任意给定初始点,X,0,，取,M,1,1,，,给定允许误差 ，令,k,=1,；,2,求无约束极值问题 的最优解，设,X,k,=,X,(,M,k,),，,即,；,3,若存在 ，使,则取,M,k,M,(),令,k,=,k,+1,返回（,2,），否则，停止迭代得最优解 ,计算时也可将收敛性判别准则 改为 ,SUTM,外点法,(,罚函数法,),的,迭代步骤,11/12/2024,8,数学建模,SUTM,内点法（,障碍函数法,）,(,),(,),(,),(,),(,),(,),(,),为障碍因子,.,为障碍项，,或,其中称,或,：,构造障碍函数,r,X,g,r,X,g,r,X,g,r,X,f,r,X,I,X,g,r,X,f,r,X,I,r,X,I,m,i,i,m,i,i,m,i,i,m,i,i,=,=,=,=,+,=,+,=,1,1,1,1,1,ln,1,),(,),(,ln,11/12/2024,9,数学建模,内点法的迭代步骤,11/12/2024,10,数学建模,近似规划法的基本思想,：将问题,(3),中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为,(3),的解的近似,近似规划法,每得到一个近似解，都从这点出发，重复以上步骤,这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解,11/12/2024,11,数学建模,近似规划法的,算法步骤如下：,11/12/2024,12,数学建模,返回,11/12/2024,13,数学建模,用,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,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,二次规划,11/12/2024,14,数学建模,例,1,min,f,(,x,1,x,2,)=-2,x,1,-6,x,2,+,x,1,2,-2,x,1,x,2,+2,x,2,2,s.t,.,x,1,+,x,2,2,-,x,1,+2,x,2,2,x,1,0,x,2,0,MATLAB,（,youh1,）,1,写成标准形式,：,2,输入命令,：,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,运算结果,为：,x=0,6667 1,3333 z=-8,2222,s.t,.,11/12/2024,15,数学建模,1,首先建立,M,文件,fun.m,用来定义目标函数,F,（,X,）,:,function f=fun(X);,f=F(X);,2,一般非线性规划,其中,X,为,n,维变元向量，,G(X,),与,Ceq,(,X,),均为非线性函数组成的向量，其他变量的含义与线性规划、二次规划中相同用,MATLAB,求解上述问题，基本步骤分三步：,11/12/2024,16,数学建模,3,建立主程序,.,求解非线性规划的函数是,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,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,文件,迭代的初值,参数说明,变量上下限,11/12/2024,17,数学建模,注意：,1,fmincon,函数提供了大型优化算法和中型优化算法默认时,:,若在,fun,函数中提供了梯度（,options,参数的,GradObj,设置为,on,），,并且只有上下界存在或只有等式约束，,fmincon,函数将选择大型算法当既有等式约束又有梯度约束时，使用中型算法,2,fmincon,函数的中型算法使用的是序列二次规划法在每一步迭代中求解二次规划子问题，并用,BFGS,法更新拉格朗日,Hesse,矩阵,3,fmincon,函数可能会给出局部最优解，这与初值,X0,的选取有关,11/12/2024,18,数学建模,1,写成标准形式,：,s.t,.,2,x,1,+3,x,2,6,s.t,.,x,1,+4,x,2,5,x,1,x,2,0,例2,11/12/2024,19,数学建模,2,先建立,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,再建立主程序,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,运算结果为：,x=0,7647 1,0588,fval=-2,0294,11/12/2024,20,数学建模,1,先建立,M,文件,fun4,m,定义目标函数,:,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,定义非线性约束：,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;,11/12/2024,21,数学建模,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),4,运算结果为,：,x=-1,2250 1,2250,fval=1,8951,11/12/2024,22,数学建模,例,4,1,先建立,M,文件,fun,m,定义目标函数,:,function f=fun(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;,11/12/2024,23,数学建模,3,主程序,fxx,m,为,:,x0=3;2,5;,VLB=0 0;VUB=5 10;,x,fval,exitflag,output,=fmincon(fun,x0,VLB,VUB,mycon2),MATLAB(fxx(fun),11/12/2024,24,数学建模,4,运算结果为,:,x=,4,0000,3,0000,fval=-11,0000,exitflag=1,output=,iterations:4,funcCount:17,stepsize:1,algorithm:1x44 char,firstorderopt,:,cgiterations,:,返回,11/12/2024,25,数学建模,应用实例：供应与选址,某公司有,6,个建筑工地要开工，每个工地的位置（用平面坐标系,a,，,b,表示，距离单位：,km,）及水泥日用量,d,(t,),由下表给出目前有两个临时料场位于,A,(5,1),，,B,(2,7),，,日储量各有,20t,假