2数学建模-非线性规划

数学建模—规划模型2定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题．一般形式：非线性规划的基本概念min()()012..6.1()012ijfXgXilsthXjm，，，，，，，，，．3定义1把满足问题（1）中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即问题(1)可简记为．njiEXXhXgXD,0,0|XXfDXmin定义2对于问题(1)，设，若存在,使得对一切，且都有，则称X*是f(X)在D上的局部极小值点（局部最优解）．特别地当时，若，，则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）．DX*0,XD*XX*XXXfXf*XfXf*定义3对于问题(1),设,对任意的,都有则称X*是f(X)在D上的全局极小值点（全局最优解）．特别地当时，若，则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）．DX*DXXfXf**XXXfXf*非线性规划的基本概念Matlab优化工具箱简介MATLAB求解优化问题的主要函数类型模型基本函数名一元函数极小MinF（x）s.t.x1xx2x=fminbnd(‘F’,x1,x2)无约束极小MinF(X)X=fminunc(‘F’,X0)X=fminsearch(‘F’,X0)线性规划MinXcTs.t.AX=bX=linprog(c,A,b)二次规划Min21xTHx+cTxs.t.Ax=bX=quadprog(H,c,A,b)约束极小（非线性规划）MinF(X)s.t.G(X)=0X=fmincon(‘FG’,X0)达到目标问题Minrs.t.F(x)-wr=goalX=fgoalattain(‘F’,x,goal,w)极小极大问题Minmax{Fi(x)}X{Fi(x)}s.t.G(x)=0X=fminimax(‘FG’,x0)一、用Matlab解无约束优化问题1.一元函数无约束优化问题:minf（x）21xxx其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。常用格式如下：（1）x=fminbnd(fun,x1,x2)（2）x=fminbnd(fun,x1,x2，options)（3）[x，fval]=fminbnd（...）（4）[x，fval，exitflag]=fminbnd（...）（5）[x，fval，exitflag，output]=fminbnd（...）运行结果：xmin=3.9270ymin=-0.0279xmax=0.7854ymax=-0.6448例:求f=2xexsin在0x8中的最小值与最大值f='2*exp(-x).*sin(x)';fplot(f,[0,8]);%作图语句[xmin,ymin]=fminbnd(f,0,8)f1='-2*exp(-x).*sin(x)';[xmax,ymax]=fminbnd(f1,0,8)命令格式为:（1）x=fminunc（fun,X0）；或x=fminsearch（fun,X0）（2）x=fminunc（fun,X0，options）；或x=fminsearch（fun,X0，options）（3）[x，fval]=fminunc（...）；或[x，fval]=fminsearch（...）（4）[x，fval，exitflag]=fminunc（...）；或[x，fval，exitflag]=fminsearch（5）[x，fval，exitflag，output]=fminunc（...）；或[x，fval，exitflag，output]=fminsearch（...）2、多元函数无约束优化问题标准型为：minF(X)例:minf(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)1、编写M-文件fun1.m:functionf=fun1(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);2、输入M文件wliti3.m如下:x0=[-1,1];x=fminunc(‘fun1’,x0);y=fun1(x)3、运行结果:x=0.5000-1.0000y=1.3029e-10考虑一般的约束最优化问题，其数学模型为求解约束优化问题，就是要在可行域中，找一个可行点使目标函数取得最小值．此时称为问题（1）的最优解．},,2,1,0)(;,,2,1,0)(|{mjXhliXgXDji*X，)(Xf))(,(**XfX二、有约束非线性规划()012..()012ijgXilsthXjm，，，，，，，，，．外点罚函数法对于问题（1），本节所述方法的基本策略是，根据约束特点（等式或不等式）构造某种“罚函数”，然后把它加到目标函数中去，使得对约束最优化问题的求解转化为对一系列无约束问题极小点或者无限地向可行域靠近，或者一直保持在可行集内移动，直到收敛于原来约束最优化问题极小点．一、外点罚函数法基本原理对问题（1），构造一函数为其中)()(),(XMXfMXFkk2211()[()][()](())2nljiijiXhXgXugX•在式（2）中，又称为惩罚函数)(X0,()0,0()0(())121()0iiiXDXXDgXugXilgX当时，当时．，当时，，，，，当时，•在式（2）中，又称为惩罚函数是一个逐渐增大的参数，称为惩罚因子．又称为问题（1）的增广目标函数．•显然，增广目标函数是定义在上的一个无约束函数．由增广目标函数的构造知：)(X0,()0,0()0(())121()0iiiXDXXDgXugXilgX当时，当时．，当时，，，，，当时，0kM，),(kMXF),(kMXFnR),(kMXF当时，此时的最优解就是问题（1）的最优解；而当时,的最优解就不一定是问题（1）的最优解.但是研究当时,的最优解我们是不感兴趣的,为此规定:当时,在X点处的函数值迅速变大,换句话说,可行域外的任一点X处的函数值都相当大.此时要求在中的最优解，只能让点X回到D内才有可能求得在中的最优解,然而一旦当点X回到D内,即,此时与问题（1）就有相同的最优解．),(kMXFDX),(kMXFDX),(kMXFDX),(kMXF),(kMXF),(kMXFnR),(kMXFnRDX),(kMXFDX)()(XfMXFk，•当时，迅速变大是通过罚因子M来实现．简言之，外点罚函数法的思想是：•当点时，设法加大不可行点处的函数值，使不可行点不能成为在中的最优解．•一般，在用外点罚函数法求解问题（1）时，我们首先构造增广目标函数，然后按照无约束优化方法求解．如果求出的最优解为，则判断是否属于D.如果,则是问题（1）的最优解；如果，则不是问题（1）的最优解，此时说明原来的罚因子给小了，需加大罚因子，使得，然后再重新计算的最优解．DX),(kMXFDX),(kMXFnR),(kMXFMXMXDMXMXDkkMM1),(kMXF),(kMXF151.首先建立M文件fun.m,定义目标函数F（X）:functionf=fun(X);f=F(X);一般非线性规划标准型为：minF(X)s.tAX=bbeqXAeqG(X)0Ceq(X)=0VLBXVUB其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：2.若约束条件中有非线性约束:G(X)0或Ceq(X)=0,则建立M文件nonlcon.m定义函数G(X)与Ceq(X):function[G,Ceq]=nonlcon(X)G=...Ceq=...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文件迭代的初值参数说明变量上下限171、写成标准形式：s.t.00546322121xxxx2100xx22212121212minxxxxf22212121212minxxxxf2x1+3x26s.tx1+4x25x1,x202、先建立M-文件fun3.m:functionf=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^23、再建立主程序youh2.m：x0=[1;1];A=[23;14];b=[6;5];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB)4、运算结果为：x=0.76471.0588fval=-2.0294应用实例：供应与选址某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？工地位置（a，b）及水泥日用量d123456a1.258.750.55.7537.25b1.250.754.7556.57.25d3547611一、建立模型记工地的位置为(ai，bi)，水泥日用量为di，i=1,…,6;料场位置为(xj，yj)，日储量为ej，j=1,2；从料场j向工地i的运送量为Xij。目标函数为：216122)()(minjiijijijbyaxXf约束条件为：2,1,6,,2,1,6121jeXidXjiijijij当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。二、使用临时料场的情形使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划模型为：2161),(minjiijXjiaaf2,1,6,,2,1,s.t.6121jeXidXjiijijij其中22)()(),(ijijbyaxjiaa，i=1,2,…,6,j=1,2,为常数。设X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12编写程序gying1.m22计算结果为：x=[3.00005.00000.00007.00000.00001.000