2012数学建模通识第十讲优化MATLAB

1优化模型（MATLAB）史加荣西安建筑科技大学理学院[e-mail]禁止在网上传播公共邮箱：[e-mail]优化模型四要素决策变量目标函数（尽量简单、光滑）约束条件（建模的关键）求解方法（MATLAB,LINDO/LINGO）优化模型分类线性规划模型（目标函数和约束条件都是线性函数的优化问题）非线性规划模型（目标函数或者约束条件是非线性的函数）整数规划（决策变量是整数值得规划问题）多目标规划（具有多个目标函数的规划问题）目标规划（具有不同优先级的目标和偏差的规划问题）动态规划（求解多阶段决策问题的最优化方法）线性规划任务分配问题某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？单位工件所需加工台时数单位工件的加工费用车床类型工件1工件2工件3工件1工件2工件3可用台时数甲0.41.11.013910800乙0.51.21.311128900minzxxxxxx12345613910111286,,2,1,09003.12.15.08001.14.0500600400x..654321635241ixxxxxxxxxxxxtsi设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型组成:目标函数Maxf或Minf约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素一般形式2222mins.t.(,)(,)(,)0nnnnnnmmmnnmnzcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx1122111122111122112212，，，求解方法：单纯形法和内点法用MATLAB优化工具箱解线性规划形式1:minz=cxs.t.Ax=b命令：x=linprog(c，A，b)形式2minz=cxs.t.Ax=bAeqx=beq命令：x=linprog(c，A，b，Aeq,beq)注意:若没有不等式：Ax=b存在，则令A=[],b=[]形式3minz=cxs.t.Ax=bAeqx=beqVLB≤X≤VUB命令:[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：[1]若没有等式约束,则令Aeq=[],beq=[].[2]其中X0表示初始点形式4命令：[x,fval]=linprog(…)返回最优解ｘ及ｘ处的目标函数值fval解编写M文件如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];Aeq=[];beq=[];vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)例max6543216.064.072.032.028.04.0xxxxxxz85003.003.003.001.001.001.0..654321xxxxxxts70005.002.041xx10005.002.052xx90008.003.063xx6,2,10jxj二次规划用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]=quaprog(...);7.[x,fval,exitflag]=quaprog(...);8.[x,fval,exitflag,output]=quaprog(...);mins.t.TTeqeqzxHxcxAxbAxbvlbxulb12标准型为min(,)s.t.,fxxxxxxxxxxxxxx2212121122121212262222200等价形式-1min(,)21s.t.2Txxzxxxxxxxx11122212121216121200输入命令：H=2*[1-1;-12];c=[-2;-6];A=[11;-12];b=[2;2];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,z]=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)非线性规划基本概念如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题一般形式min()s.t.(),,,...,(),,,...,ijfxgximhxjl012012其中x为n维列向量,f,gi,hj为实值函数.把满足问题中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即D={x|gi(x)=0,hj(x)=0,i=1,…,m,j=1,…,l}对于优化问题,有局部最有解和全局最有解之分.非线性规划的基本解法1.罚函数法2.近似规划法标准型为Minf(x)s.t.Ax=bAeqx=beqG(x)=0Ceq(x)=0VLB=x=VUB其中x为n维变元向量，G(x)与Ceq(x)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：1.首先建立M文件fun.m,定义目标函数f(x):functionf=fun(X);f=f(x);2.若约束条件中有非线性约束:G(x)或Ceq(x),则建立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(...)注意[1]fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为’on’），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。[2]fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。[3]fmincon函数可能会给出局部最优解，这与初值x0的选取有关先建立M文件fun2.m,functionf=fun2(x);f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);再建立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];ceq=[]；1221212212121212min()(42421)s.t.+=01.5+--0--100xfxexxxxxxxxxxxxx=++++££例非线性规划的网格搜索二元函数举例Minf(x1,x2)s.t.ax1bcx2d其中f(x1,x2)为连续函数。求解思路先建立目标函数的m函数文件，名字可记为fun。N1=1000；N2=1000;h1=（b-a）/N1;h2=（d-c）/N2;f0=inf;xo=[ac];fori=0:N1forj=0:N2f=fun(a+i*h1,b+j*h2);ifff0,xo=[a+i*h1,b+j*h2];f0=f;endendEnd此种方法不易用于较高维函数优化问题。多目标优化12min()((),(),...,())nxXfxfxfxfxX为连续型决策空间01230123f1f2Pareto解，非劣解(4).转化为单目标minf1(x)s.t.fi(x)ki极大极小与极小极大问题12minmax((),(),...,())s.t.mins.t.(),1,...,nifxfxfxxXaxXfxain12maxmin((),(),...,())s.t.maxs.t.(),1,...,nifxfxfxxXaxXfxain应用实例1:投资的收益和风险问题提出：市场上有n种资产Si(i=1,2,…,n)可以选择,现用数额为M的相当大的资金作一个时期的投资。这n种资产在这一时期内购买Si的平均收益率为ri，风险损失率为qi，投资越分散，总的风险越小，总体风险可用投资的Si中最大的一个风险来度量。购买Si时要付交易费(费率pi)，当购买额不超过给定值ui时，交易费按购买ui计算。另外，假定同期银行存款利率是r0，既无交易费又无风险。（r0=5%）Siri（%）qi（%）pi（%）ui（元）S1282.51103S2211.52198S3235.54.552S4252.66.540试给该公司设计一种投资组合方案，即用给定达到资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。基本假设：1.投资数额M相当大,为了便于计算，假设M=1；2．投资越分散，总的风险越小；3．总体风险用投资项目is中最大的一个风险来度量；4．n种资产is之间是相互独立的；5．在投资的这一时期内,ri,pi,qi，r0为定值，不受意外因素影响；6．净收益和总体风险只受ri,pi,qi影响，不受其他因素干扰.符号规定：Si——第i种投资项目，如股票，债券ri,pi,qi----分别为Si的平均收益率,交易费率，风险损失率ui----Si的交易定额0r-------同期银行利率xi-------投资项目Si的资金a-----投资风险度Q----总体收益ΔQ----总体收益的增量模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max{qixi|i=1，2,…,n}2．购买Si所付交易费是一个分段函数,即pixixiui交易费=piuixi≤ui而题目所给定的定值ui(单位:元)相对总投资M很小,piui更小,可以忽略不计,这样购买Si的净收益为(ri-pi)xi3．要使净收益尽可能大，总体风险尽可能小,这是一个多目标规划模型:目标函数maxniiiixpr0)(Minmax{qixi}约束条件1(1)0,1,2,...,niiiipxMxin4．模