非线性规划及matlab实现.ppt

非线性规划,非现性规划的基本概念,定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题．,一般形式: （1） 其中 ， 是定义在 En 上的实值函数，简记:,其它情况: 求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式．,用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]=quadprog(...); 7.[x,fval,exitflag]=quaprog(...); 8.[x,fval,exitflag,output]=quaprog(...);,1、二次规划,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x2≤2 -x1+2x2≤2 x1≥0, x2≥0,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.,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’,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(...),输出极值点,,M文件,,迭代的初值,,参数说明,,变量上下限,,,注意：[1] fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为’on’），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。[2] fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。[3] fmincon函数可能会给出局部最优解，这与初值X0的选取有关。,,,1、写成标准形式： s.t.,2x1+3x2 6 s.t x1+4x2 5 x1,x2 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： 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,,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);,x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 –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.0000fval =-11.0000exitflag = 1output = iterations: 4 funcCount: 17 stepsize: 1 algorithm: [1x44 char] firstorderopt: [] cgiterations: [],应用实例： 供应与选址,某公司有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。,当用临时料场时决策变量为：xij，当不用临时料场时决策变量为：xij，xj，yj。,（二）使用临时料场的情形,使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题. 线性规划模型为：,设X11=X1, X21= X 2,, X31= X 3, X41= X 4, X51= X 5,, X61= X 6X12= X 7, X22= X 8,, X32= X 9, X42= X 10, X52= X 11,, X62= 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，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：,设 X11=X1, X21= X 2,, X31= X 3, X41= X 4, X51= X 5,, X61= X 6 X12= X 7, X22= X 8,, X32= X 9, X42= X 10, X52= X 11,, X62= X 12 x1=X13, y1=X14, x2=X15, y2=X16,（1）先编写M文件liaoch.m定义目标函数。,(2) 取初值为线性规划的计算结果及临时料场的坐标: x0=[3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7]';编写主程序gying2.m.,(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.4626exitflag = 1,(4) 若修改主程序gying2.m, 取初值为上面的计算结果: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]’,得结果为: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.4760exitflag = 1,总的吨千米数比上面结果略优.,(5) 若再取刚得出的结果为初值, 却计算不出最优解.,(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.8835exitflag = 1总的吨千米数89.8835比上面结果更好.,通过此例可看出fmincon函数在选取初值上的重要性.,某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60台、80台．每季度的生产费用为 （元），其中x是该季生产的台数．若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度c元．已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4，问工厂应如何安排生产计划，才能既满足合同又使总费用最低．讨论a、b、c变化对计划的影响，并作出合理的解释．,练习,