数学建模讲义——---非线性规划

单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数学建模讲义,最优化模型,-,非线性规划,非线性规划问题,1,、非线性规划模型,2,、非线性规划的性质,3,、,非线性规划,的主要算法。,4,、用数学软件包求解无约束最优化问题,5,、建模案例选讲,定义,1:,如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,1,非线性规划模型,一般形式,:,其中,是定义在,E,n,上的实值函数，简记,:,定义,1,把满足问题,(1),中条件的解 称为可行解,(,或可行点,),，所有可行点的集合称为可行集（或可行域）记为,D,即,问题,(1),可简记为,定义,2,对于问题,(1),设,若存在,使得对一切,，且 ，都有 ，则称,x,*,是,f,(,x,),在,D,上的,局部极小值点,(,局部最优解,),特别地当 时,若 ，则称,x,*,是,f,(,x,),在,D,上的,严格局部极小值点（严格局部最优解）,2,非线性规划的性质,定义,3,对于问题,(1),设,对任意的,都有,.,则称,x,*,是,f,(,x,),在,D,上的,全局极小值点（全局最优解）,特别地当 时，若 ，则称,x,*,是,f,(,x,),在,D,上的,严格全局极小值点（严格全局最优解）,2.2,求解非线性规划的基本算法,罚函数法,内点法，外点法，,Lagrange,乘子法,序列线性规划法,序列二次规划法,信赖域法,可行方向法,罚函数法,罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法简称为,SUMT,法,其一为,SUMT,外点法，其二为,SUMT,内点法,SUTM,外点法,其中,T,(,x,M),称为罚函数，,M,称为罚因子，带,M,的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚,:,当 时，满足 的约束条件，故罚项,=0,不受惩罚,当 时,必有 ，故罚项,0,，要受惩罚,1,、,任意给定初始点,x,0,，取,M,1,1,，,给定允许误差 ，令,k=1,；,2,、,求无约束极值问题 的最优解，设为,x,k,=,x,(M,k,),，,即,；,3,、,若存在,使 ，则取,M,k,M,(,),令,k=k+1,返回,(2),，否则，停止迭代得最优解,.,计算时也可将收敛性判别准则 改为,.,SUTM,外点法,(,罚函数法,),的迭代步骤,罚函数法的缺点是：每个近似最优解,x,k,往往不是可行解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着,M,k,的增大，可能导致错误,SUTM,内点法（障碍函数法）,内点法的迭代步骤,近似规划法的基本思想：,将问题,(3),中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为,(3),的解的近似,序列线性规划法,每得到一个近似解后，都从这点出发，重复以上步骤,这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解,。,序列线性规划法的算法步骤如下,返回,序列二次规划法,信赖域法,1,、二次规划,用,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:,min f,(,x,1,x,2,)=-2,x,1,-,6x,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,1,、,写成标准形式,：,s.t.,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,2,、一般非线性规划,其中,x,为,n,维变元向量，,G(x),与,Ceq,(x),均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同,.,用,Matlab,求解上述问题，基本步骤分三步：,1.,首先建立,M,文件,fun.m,定义目标函数,F,（,X,）,:,function f=fun(x);,f = f(x);,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,fmincon,函数提供了大型优化算法和中型优化算法。默,认时,若在,fun,函数中提供了梯度（,options,参数,GradObj,设置为,on),，,并且只有上下界存在或只有等式约束,fmincon,函数将选择大型算法。当既有等式约束又有梯,度约束时，使用中型算法。,2,fmincon,函数的中型算法使用的是序列二次规划法。在,每一步迭代中求解二次规划子问题，并用,BFGS,法更新,拉格朗日,Hessian,矩阵。大型算法采用的是较高级的信,赖预算法,.,3,fmincon,函数可能会给出局部最优解，这与初值,x,0,的选,取有关。,注,:,1,、,写成标准形式,：,s.t.,2,x,1,+3,x,2,6,s.t,x,1,+ 4,x,2,5,x,1,x,2,0,例,2,2,、,先建立,M-,文件,fun3.m:,function,f,=fun3(,x,);,f,=-,x,(1)-2*,x,(2)+(1/2)*,x,(1)2+(1/2)*,x,(2)2,3,、再建立主程序,youh2.m,：,x,0,=1;1;,A=2 3 ;1 4;,b=6;5;,Aeq,=;,beq,=;,VLB=0;0; VUB=;,x,fval,=,fmincon,(fun3,x,0,A,b,Aeq,beq,VLB,VUB),4,、,运算结果为：,x,= 0.7647 1.0588,fval,= -2.0294,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;,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,),3.,运算结果为,：,x = -1.2250 1.2250,fval,= 1.8951,例,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;,3.,主程序,fxx,.m,为,:,x0=3;2.5;,VLB=0 0;VUB=5 10;,x,fval,exitflag,output,=,fmincon,(fun,x0,VLB,VUB,mycon2),4.,运算结果为,:,x =,4.0000,3.0000,fval,=-11.0000,exitflag,= 1,output =,iterations: 4,funcCount,: 17,stepsize,: 1,algorithm: 1x44 char,firstorderopt,: ,cgiterations,: ,注：,NLP,虽然可用现成的数学软件求解,(,LINGO,MATLAB,),，,但是其结果常依赖于初值的选择。而且所求得点也仅仅是一个局部最优点（凸规划除外），对于实际问题往往不能得到满意的结果,.,这就要求建模的时候尽量不要建成一个很复杂的非线性规划模型。适当的时候还要对模型进行建化分析，或采用一些局部调整的方法已得到更好的近似解,.,应用实例： 供应与选址,某公司有,6,个建筑工地要开工，每个工地的位置（用平面坐标系,a,，,b,表示，距离单位：千米 ）及水泥日用量,d(,吨,),由下表给出。目前有两个临时料场位于,A(5,1),，,B(2,7),，,日储量各有,20,吨。假设从料场到工地之间均有直线道路相连。,（,1,）试制定每天的供应计划，即从,A,，,B,两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。,（,2,）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为,20,吨，问应建在何处，节省的吨千米数有多大？,（一）、建立模型,记工地的位置为,(,ai,，,bi),，,水泥日用量为,di,，,i=1,6;,料场位置为,(,xj,，,yj,),，,日储量为,ej,，,j=1,2,；,从料场,j,向工地,i,的运送量为,Xij,。,当用临时料场时决策变量为：,X,ij,，,当不用临时料场时决策变量为：,X,ij,，,x,j,，,y,j,。,（二）使用临时料场的情形,使用两个临时料场,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,计算结果为：,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,（三）改建两个新料场的情形,改建两个新料场，要同时确定料场的位置,(,xj,yj,),和运送量,Xij,，,在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：,设,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,定义目标函数。,MATLAB,（,liaoch,）,(2),取初值为线性规划的计算结果及临时料场的坐标,:,x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;,编写主程序,gying2.m.,MATLAB,（,gying2,）,function f=,liaoch,(x),a=1.25 8.75 0.5 5.75 3 7.25; b=1.25 0.75 4.75 5 6.5 7.75;,d=3 5 4 7 6 11; e=20 20; f1=0;,for i=1:6,s(i)=,sqrt,(x(13)-a(i)2+(x(14)-b(i)2);,f1=s(i)*x(i)+f1;,end,f2=0;,for i=7:12,s(i)=,sqrt,(x(15)-a(i-6)2+(x(16)-b(i-6)2);,f2=s(i)*x(i)+f2;,end,f=f1+f2;,clear,%x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;,%x0= 3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867;,%x0= 3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852;,x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499;,A=1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0,；,0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0;,B=20;20;,Aeq,=1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0,0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0,0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0,0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0,0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0,0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0;,beq,=3 5 4 7 6 11;,vlb,=zeros(12,1);-,inf,;-,inf,;-,inf,;-,inf,;,vub,=;,x,fval,exitflag,=,fmincon,(,liaoch,x0,A,B,Aeq,beq,vlb,vub,),(3),计算结果为：,x= 3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000,10.0707 6.3875 4.3943 5.7511 7.1867,fval,= 105.4626,exitflag,= 1,(4),若修改主程序,gying2.m,取初值为上面的计算结果,:,x,0,= 3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867,得结果为,:,x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852,fval,=103.4760,exitflag,= 1,总的吨千米数比上面结果略优,.,(5),若再取刚得出的结果为初值,却计算不出最优解,.,MATLAB,（,gying2,）,MATLAB,（,gying2,）,(6),若取初值为,:,x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499,则计算结果为,:,x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7.2500 7.7500,fval,=89.8835,exitflag,= 1,总的吨千米数,89.8835,比上面结果更好,.,通过此例可看出,fmincon,函数在选取初值上的重要性,.,MATLAB,（,gying2,）,返回,钢管订购及运输优化模型,2000,年“网易杯”全国大学生数学建模竞赛,B,题,符号说明：,1,、铺设总费用：,2,、成本及运输总费用：,总费用,=,铺设总费用,+,成本及运输总费用,=,C+W,模型的分析与建立,建立模型,模型求解,利用,MATLAB,软件包求解得：,订购和运输方案表,返回,某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货,40,台、,60,台、,80,台每季度的生产费用为 （元），其中,x,是该季生产的台数若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度,c,元已知工厂每季度最大生产能力为,100,台，第一季度开始时无存货，设,a=50,、,b=0.2,、,c=4,，,问工厂应如何安排生产计划，才能既满足合同又使总费用最低讨论,a,、,b,、,c,变化对计划的影响，并作出合理的解释,练习,1,练习,2,返回,谢 谢！,