最优化问题的MATLAB求解.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Matlab 最优化工具箱,Name:曾泰山,E-mail:zengtsh,最优化问题的一般数学模型,最优化问题的一般算法,f(X),局部最优解,整体最优解,Matlab优化工具箱简介,1.MATLAB求解优化问题的主要函数,3.优化函数的输出变量下表:,模型输入时需要注意的问题,（1）目标函数最小化,优化函数fminbnd、fminsearch、fminunc、fmincon、fgoalattain、fminmax和lsqnonlin都要求目标函数最小化。,（2）约束非正,优化工具箱要求非线性不等式约束的形式为Ci(x)0，通过对不等式取负可以达到使大于零的约束形式变为小于零的不等式约束形式的目的。,最优化问题的求解,一、无约束最优化问题求解,问题的描述：求,x,=,x,1,x,2,x,n,最优化变量,f,(,x,),目标函数,该求解问题就是要求取,x,的值，使目标函数,f,(,x,)为最小。即求函数,f,(,x,)的最小值。,除满足函数定义域的要求外，对自变量,x,无其他约束条件。因此称为无约束最优化问题。,若要计算一个函数,f,(,x,)的最大值，可根据“,f,(,x,)的最大值=-,f,(,x,)的最小值,”得到。,目前所有的最优化算法均不能保证求出全局最优解，即整个定义域上的最值，以下介绍的命令实际上是求极小值（局部最小值）点。,命令：,fminsearch,或,fminunc,用于求解无附加条件的极小值点。两命令的语法相同。,语法：,x=fminsearch（fun,x0）,最简形式,x0,向量，指搜索点初值，表示为列向量。x0较难确定，所以最好使用flag参数来把握求解过程的有效性。,fun,用内联函数，或M-函数文件（被引用时必须用单引号括住函数名），或直接以单引号括起的函数表达式给出的方程（组）。,在求多元函数最值时，需在fun的编写过程中将各变量写成一个向量的各分量的形式，即x(1),x(2),，并且方程组要以多行一列的矩阵形式来表示。,例1：求一元函数,y,=,e,x,x,3,4,x,2,的（局部）最小值点。,格式1,x=fminsearch(exp(x)-x3-4*x2,1),可使用ezplot 命令作出函数图象来验证上述结果。与fsolve 的情况类似，由于极值不一定唯一，改变初始搜索点位置可能会得到不同的结果。,格式2,首先编写M-函数文件如下：,function y=ff1(x),y=exp(x)-x3-4*x2;,之后在命令窗口输入命令：,x=fminsearch(ff1,1),格式3,使用内联函数,g=inline(exp(x)-x3-4*x2,x);x=fminsearch(g,1),x=,4.6123,ezplot(exp(x)-x3-4*x2,-10,10),执行结果：,结合函数图像来检验初始搜索点的确定是否合理：,x=fminsearch(exp(x)-x3-4*x2,-2),从函数图像看，如果初始搜索点改为负数，我们可能得到另一个结果。如：,得：,x=,-2.6752,格式2,首先编写M-函数文件如下：,function y=ff2(x),y=(x(1)2-2*x(1)*exp(-x(1)2-x(2)2-x(1)*x(2);,之后在命令窗口输入命令：,x=fminsearch(ff2,1,1),x=fminsearch(x(1)2-2*x(1)*exp(-x(1)2-x(2)2-x(1)*x(2),1,1),例2：求二元函数的 （局部）最小值点（曲面的最低点）,格式1,格式3,使用内联函数,g=inline(x(1)2-2*x(1)*exp(-x(1)2-x(2)2-x(1)*x(2),x,);,x=fminsearch(g,1,1),得：,x=,0.6111 -0.3055,x=0:0.2:5;y=0:0.2:5;xx,yy=meshgrid(x,y);,zz=(xx.2-2*xx).*exp(-xx.2-yy.2-xx.*yy);mesh(xx,yy,zz),可事先绘制图像，来获得初始搜索点。首先较为随意地给出一个绘图区域：,x=-3:0.2:3;y=-3:0.2:3;xx,yy=meshgrid(x,y);,zz=(xx.2-2*xx).*exp(-xx.2-yy.2-xx.*yy);mesh(xx,yy,zz),根据上图，重新确定一个更为合理的绘图区域：,通过改变观察视角，可以看出极小值点的横纵坐标的大致值。,2、线性规划问题的求解,线性规划问题是一种最简单的有约束最优化问题，其,目标函数,和,约束函数,都是线性的，约束函数包括线性不等式和线性等式。,问题的描述：求,x,自变量，是由若干分量组成的列向量；,f,x,的各分量前的系数构成的向量；,f,x,目标函数（即求该函数的最小值），是,f,与,x,的,数量积,。,以下为约束函数：,Ax,B,对目标函数的自变量x的线性不等式约束；,对“”的情况，需要通过两边同乘以-1改成标准的“”的形式；,Cx,=,D,对目标函数的自变量,x,的线性等式约束；,x,m,x,x,M,x,的取值范围，,x,m,和,x,M,分别为下界向量和上界向量。,命令：,linprog,语法：,x,f,opt,flag,c=linprog(f,A,B,C,D,xm,xM,x0,OPT,p1,p2,),含义见前面的“问题描述”,初始搜索点,控制选项，包含若干分量，用于对求解过程进行控制。可省略。,附加参数，可省略,求解结果（令目标函数取得最优解的x）,目标函数的最优解,反映求解过程中的迭代次数等信息,该值若为正，说明求解成功，否则表明求解出现问题。,最简形式：,x=linprog(f,A,B,C,D,xm,xM,x0),注意：各参数的参数名可以变，但位置必须跟上述格式对牢。若相应的约束不存在，应该用空矩阵 占位。,由于输入变量较多且往往较复杂，一般需事先定义。,用MATLAB优化工具箱解线性规划,min,z=fX,1、模型：,命令：,x=linprog（f，A，b）,2、模型,：min,z=fX,命令：,x=linprog（f，A，b，Aeq,beq）,注意：若没有不等式：存在，则令A=，b=.,3、模型,：min,z=fX,VLBXVUB,命令：,1,x=linprog（f，A，b，Aeq,beq,VLB，VUB）,2,x=linprog（f，A，b，Aeq,beq,VLB，VUB,X,0,）,注意：1 若没有等式约束:,则令Aeq=,beq=.,2其中X,0,表示初始点,4、命令：,x,fval=linprog(),返回最优解及处的目标函数值fval.,解:,编写M文件如下：,c=-7-5;,A=3 2;4 6;0 7;,b=90;200;210;,Aeq=;,beq=;,vlb=0,0;,vub=inf,inf;,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),问题2解答,例3：求,编写M-脚本文件如下：,f=-2-1-4-3-1;,%线性的目标函数的系数向量（行、列均可）,A=0 2 1 4 2;3 4 5-1-1;B=54;62;,%线性不等式约束的系数矩阵,C=;D=;,%线性等式约束的系数矩阵。,%因题中无等式约束，所以该处用空矩阵占位。,xm=0;0;3.32;0.678;2.57;xM=;x0=;,%这三个向量写成行向量列向量均可,x,fopt,flag,c=linprog(f,A,B,C,D,xm,xM,x0),执行结果：,Optimization terminated.,x=,19.7850,0.0000,3.3200,11.3850,2.5700,fopt=,-89.5750,flag=,1,%表明求解成功,c=,iterations:6,algorithm:large-scale:interior point,cgiterations:0,message:Optimization terminated.,练：若,x,要求满足,试写出,x,的下、上界向量,x,m,和,x,M,。,xm=-1;-inf;-inf;1;-inf;xM=inf;2;5;2;inf;,解：,Exiting:One or more of the residuals,duality gap,or total relative error,has stalled:,the dual appears to be infeasible(and the primal unbounded).,(The primal residual x0=4;5;6;,lb=zeros(3,1);,x,fval,exitflag,output,lambda,=fmincon(-x(1)*x(2)*x(3),x0,lb,Ex1c),应用实例：供应与选址,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。,（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。,（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？,（一）、建立模型,记工地的位置为(a,i,，b,i,)，水泥日用量为d,i,，i=1,6;料场位置为(x,j,，y,j,)，日储量为e,j,，j=1,2；从料场j向工地i的运送量为X,ij,。,当用临时料场时决策变量为：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,（三）改建两个新料场的情形,改建两个新料场，要同时确定料场的位置(x,j,y,j,)和运送量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,x,1,=X,13,y,1,=X,14,x,2,=X,15,y,2,=X,16,（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.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)若再取刚得出的结果为初值,却计算不出最优解.,(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函数在选取初值上的重要性.,4、0-1（线性）规划问题的求解,自变量只能取0或1的最优化问题称为0-1规划问题，是整数规划的一种。MATLAB提供的bintprog函数可用于求解线性的0-1规划问题。,问题的描述：求,命令：,bintprog,语法：,x,=bintprog(,f,A,B,C,D,),各变量含义与前面的相同。,例：求,编写M-脚本文件：,f=-3 2 5;,A=1 2-1;1 4 1;1 1 0;0 4 1;B=2;4;3;6;,%线性不等式约束,C=;D=;,%无线性等式约束,x0=1 0 1;,x=bintprog(f,A,B,C,D),Optimization terminated.,x=,1,0,0,执行结果：,主要参考书：,高等应用数学问题的MATLAB求解 薛定宇 陈阳泉 著 清华大学出版社,精通MATLAB科学计算 王正林等编著 电子工业出版社,科学计算引论基于MATLAB的数值分析 美Shoichiro Nakamura 电子工业出版社,MATLAB与科学计算 王谟然 编著 电子工业出版社,谢谢！,