Matlab做 非线性规划(精品)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学建模与数学实验,后勤工程学院数学教研室,非线性规划,1,实验目的,实验内容,2,、掌握用数学软件求解优化问题。,1,、直观了解非线性规划的基本内容。,1,、非线性规划的基本理论。,4,、实验作业。,2,、用数学软件求解非线性规划。,3,、钢管订购及运输优化模型,2,*,非线性规划的基本解法,非线性规划的基本概念,非线性规划,返回,3,定义,如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做,非线性规划问题,非现性规划的基本概念,一般形式,:,（,1,）,其中 ，是定义在,E,n,上的实值函数，简记,:,其它情况,:,求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式,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,上的,严格全局极小值点,（,严格全局最优解,）,返回,5,非线性规划的基本解法,SUTM,外点法,SUTM,内点法（障碍罚函数法）,1,、罚函数法,2,、,近似规划法,返回,6,罚函数法,罚函数法,基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为,序列无约束最小化方法,简称为,SUMT,法,其一为,SUMT,外点法,，其二为,SUMT,内点法,7,其中,T(X,M),称为,罚函数,，,M,称为,罚因子,，,带,M,的项称为,罚项,，,这里的罚函数只对不满足约束条件的点实行惩罚：当 时，满足各 ，故罚项,=0,，不受惩罚当 时，必有 的约束条件，故罚项,0,，要受惩罚,SUTM,外点法,8,罚函数法的,缺点,是：每个近似最优解,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,外点法,(,罚函数法,),的,迭代步骤,9,SUTM,内点法（,障碍函数法,）,10,内点法的迭代步骤,11,近似规划法的基本思想,：将问题,(3),中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为,(3),的解的近似,近似规划法,每得到一个近似解后，都从这点出发，重复以上步骤,这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。,12,近似规划法的,算法步骤如下,13,返回,14,用,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,、二次规划,(lingo,更好,),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,、,写成标准形式,：,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.,16,2,、一般非线性规划（重点）,其中,X,为,n,维变元向量,G(X),为非线性不等式组,ceq,（,X,）为非线性等式组，,A*x=b,为线性的不等式约束，,A,为系数矩阵,Aeq,*x=,beq,为线性的等式约束，,Aeq,为系数矩阵,17,基本步骤分三步：,1.,首先建立,M,文件,fun.m,定义目标函数,F,（,X,）,:,function f=,fun(X,);,f=F(X);,18,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,文件,迭代的初值,参数说明,变量上下限,19,注意：,1,fmincon,函数提供了大型优化算法和中型优化算法。默认时，若在,fun,函数中提供了梯度（,options,参数的,GradObj,设置为,on,），,并且只有上下界存在或只有等式约束，,fmincon,函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。,2,fmincon,函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用,BFGS,法更新拉格朗日,Hessian,矩阵。,3,fmincon,函数可能会给出局部最优解，这与初值,X,0,的选取有关。,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=1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;,ceq,=;,21,3,主程序,youh3.m,为,:,x0=-1;1;,A=;b=;,Aeq,=1 1;beq=0;,vlb,=;,vub,=;,x,fval,exitflag,=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon),MATLAB(youh3),3.,运算结果为,：,x=-1.2250 1.2250,fval,=1.8951,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;,ceq,=;,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,),24,4.,运算结果为,:,x=,4.0000,3.0000,fval,=-11.0000,exitflag,=1,output=,iterations:4,funcCount,:17,stepsize,:1,algorithm:1x44 char,firstorderopt,:,cgiterations,:,返回,25,应用实例：供应与选址,某公司有,6,个建筑工地要开工，每个工地的位置（用平面坐标系,a,，,b,表示，距离单位：千米）及水泥日用量,d(,吨,),由下表给出。目前有两个临时料场位于,A(5,1),，,B(2,7),，,日储量各有,20,吨。假设从料场到工地之间均有直线道路相连。,（,1,）试制定每天的供应计划，即从,A,，,B,两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。,（,2,）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为,20,吨，问应建在何处，节省的吨千米数有多大？,26,（一）、建立模型,记工地的位置为,(,ai,，,bi),，,水泥日用量为,di,，,i=1,6;,料场位置为,(,xj,，,yj,),，,日储量为,ej,，,j=1,2,；,从料场,j,向工地,i,的运送量为,Xij,。,当用临时料场时决策变量为：,X,ij,，,当不用临时料场时决策变量为：,X,ij,，,x,j,，,y,j,。,27,（二）使用临时料场的情形,使用两个临时料场,A(5,1),，,B(2,7).,求从料场,j,向工地,i,的运送量为,X,ij,，,在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题,.,线性规划模型为：,设,X,11,=X,1,X,21,=X,2,X,31,=X,3,X,41,=X,4,X,51,=X,5,X,61,=X,6,X,12,=X,7,X,22,=X,8,X,32,=X,9,X,42,=X,10,X,52,=X,11,X,62,=X,12,编写程序,gying1.m,MATLAB（gying1）,28,计算结果为：,x=3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000,0.0000 4.0000 0.0000 6.0000 10.0000,fval,=136.2275,29,（三）改建两个新料场的情形,改建两个新料场，要同时确定料场的位置,(,xj,yj,),和运送量,Xij,，,在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：,30,设,X,11,=X,1,X,21,=X,2,X,31,=X,3,X,41,=X,4,X,51,=X,5,X,61,=X,6,X,12,=X,7,X,22,=X,8,X,32,=X,9,X,42,=X,10,X,52,=X,11,X,62,=X,12,x,1,=X,13,y,1,=X,14,x,2,=X,15,y,2,=X,16,（,1,）先编写,M,文件,liaoch.m,定义目标函数。,M