Exp08姜启源数学建模第八章约束优化.ppt

*,大学数学实验,Mathematical Experiments,实验8 约束优化,1,优化问题三要素：,决策变量,；,目标函数,；,约束条件,约束条件,决策变量,优化问题的一般形式,当最优解在可行域边界上取得时,不能用无约束优化方法求解,目标函数,2,约束优化的分类,线性规划,(LP),目标和约束均为线性函数,非线性规划,(NLP),目标或约束中存在非线性函数,二次规划,(QP),目标为二次函数、约束为线性,整数规划,(IP),决策变量,(,部分,),为整数,整数,线性,规划,(ILP),整数,非线性,规划,(INLP),0-1,规划,整数决策变量只取或,连续优化,离散优化,数学规划(Math.Prog.),3,本实验基本内容,2.基本原理和算法,3.MATLAB,实现,1.,问题与模型,NLP,LP,QP,连续优化,4,1桶牛奶,3千克A,1,12小时,8小时,4千克A,2,或,获利12元/千克,获利8元/千克,0.8千克B,1,2小时,1.5元,1千克,获利22元/千克,0.75千克B,2,2小时,1.5元,1千克,获利16元/千克,制订生产计划，使每天净利润最大,15,元可增加,1,桶牛奶，应否投资？,50桶牛奶,480小时,至多100公斤A,1,B,1,，,B,2,的获利经常有,10%,的波动，对计划有无影响？,实例1:奶制品生产销售计划,聘用临时工人增加劳动时间，工资最多每小时几元？,5,1桶牛奶,3千克 A,1,12小时,8小时,4千克 A,2,或,获利12元/千克,获利8元/千克,0.8千克,B,1,2小时,1.5元,1千克,获利22元/千克,0.75千克 B,2,2小时,1.5元,1千克,获利16元/千克,出售,x,1,千克 A,1,x,2,千克 A,2,，,x,3,千克 B,1,x,4,千克 B,2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x,5,千克 A,1,加工B,1,，,x,6,千克 A,2,加工B,2,附加约束,LP,6,50万元基金用于投资三种股票A、B、C：,A每股年期望收益5元(标准差2元)，目前市价20元；,B每股年期望收益8元(标准差6元)，目前市价25元；,C每股年期望收益10元(标准差10元)，目前市价30元；,股票A、B收益的相关系数为5/24;,股票A、C收益的相关系数为0.5;,股票B、C收益的相关系数为0.25。,实例2：投资组合问题,如期望今年得到至少,20%,的投资回报，应如何投资？,投资回报率与风险的关系如何？,假设：,1、基金不一定要用完（不用不计利息或贬值）,2、风险通常用收益的方差或标准差衡量,7,决策变量,x,1,、,x,2,和,x,3,分别表示投资A、B、C的数量（国内股票通常以“一手”（100股）为最小单位出售，这里以100股为单位，期望收益以百元为单位）,实例2：投资组合问题,A、B、C每手(百股)的收益分别记为,S,1,S,2,和,S,3,(百元)：,ES,1,=5,ES,2,=8,ES,3,=10，,DS,1,=4,DS,2,=36,DS,3,=100，,r,12,=5/24,r,13,=-0.5，,r,23,=-0.25,总收益,S,=,x,1,S,1,+,x,2,S,2,+,x,3,S,3,：是一个随机变量,8,投资风险（总收益的方差）为,实例2：投资组合问题,总期望收益为,Z,1,=,ES,=,x,1,ES,1,+,x,2,ES,2,+,x,3,ES,3,=5,x,1,+8,x,2,+10,x,3,总收益,S,=,x,1,S,1,+,x,2,S,2,+,x,3,S,3,：是一个随机变量,9,二次规划（QP）模型,实例2：投资组合问题,s.t.,5,x,1,+8,x,2,+10,x,3,1000,20,x,1,+25,x,2,+30,x,3,5000,x,1,，,x,2,，,x,3,0,通过试探发现,从0.00010.1以0.0001的步长变化就可以得到很好的近似结果,Min,Z,=,Z,2,-,Z,1,s.t.,20,x,1,+25,x,2,+30,x,3,5000,x,1,，,x,2,，,x,3,0,加权,模型,10,实例3：供应与选址,某公司有6个建筑工地，位置坐标为(a,i,b,i,)(单位：公里),水泥日用量d,i,(单位：吨）,假设：,料场和工地之间有直线道路,11,线性规划模型,决策变量：,c,i j,12维,(,料场,j,到,工地,i,运量）,12,2）,改建两个新料场，需要确定新料场位置(,x,j,y,j,)和运量,c,ij,，在其它条件不变下使总吨公里数最小。,决策变量：,c,i j，,(,x,j,y,j,)16维,非线性规划模型,13,求解线性规划(LP)的基本原理,基本模型,二维线性规划的图解法,一般线性规划的单纯形算法,一般线性规划的内点算法,14,二维线性规划的图解法,x,2,x,1,0,L,1,L,2,L,3,z,1,=0,z,2,=2,z,3,=6,z,4,=10,z,5,=,13,grad,z,x,*,*,起作用约束：L,2,;L,3,最优解（4，1），最优值,z,max,=13,L,1,L,2,L,3,15,求解LP的基本思想,从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到,最优解,。,LP的约束和目标函数均为线性函数,2维,可行域,线段组成的凸多边形,目标函数,等值线为直线,最优解,凸多边形的某个顶点,n维,超平面组成的凸多面体,等值线是超平面,凸多面体的某个顶点,算法：怎样从一点转到下一点，尽快找到最优解。,16,x,2,x,1,0,L,1,L,2,L,3,x,2,x,1,0,L,1,L,2,L,3,x,2,x,1,0,L,1,L,2,求解LP的特殊情形,L,1,L,2,L,3,无可行解,无最优解(无界),最优解不唯一,x,2,x,1,0,L,1,L,2,L,3,z=c,17,线性规划的标准形和基本性质,标准形,加入松弛变量/剩余变量将不等式变为等式,一般还假定,b,0,rank(,A,)=,m,18,对标准形求解,先求可行解,再在有限个可行解中寻找最优解,19,x,2,x,1,O,O,点,Q,点,R,点,Q,R,基本可行解,x,：,Ax=b,x,0(,x,B,0，,x,N,=0),P,点,P,B,:基(矩阵),x,:基(本)解,20,可行域存在时，必是凸多面体(可能无界)；,最优解存在时，必在可行域的顶点取得(可能无界)；,基本可行解对应于可行域的顶点(极点)。,LP基本性质,最优解只需在有限个可行解（基本可行解）中寻找,单纯形法的基本思路,从一个顶点转换到另一个顶点（即构成,x,B,和,x,N,的向量,p,i,间的转换），使目标函数逐步下降。,LP的通常解法是单纯形法(G.B.Dantzig,1947),21,内点算法(Interior point method),20,世纪,80,年代人们提出的一类新的算法,内点算法,也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。,LP其他算法,有效集(Active Set)方法,LP,是,QP,的特例（只需令所有二次项为零即可）,可以用,QP,的算法解,LP(,如,:,有效集方法，详见下节,),22,x,fval,exitflag,output,lambda=,linprog(c,A1,b1,A2,b2,v1,v2,x0,opt),MATLAB 求解 LP,输入：,x0,初始解(缺省时一般为0),opt,MATLAB控制参数,中间所缺参数项补,输出：,lambda,Lagrange乘子，,维数等于约束个数，非零分量对应于起作用约束,lambda.ineqlin,:,对应,A,1,x,b,1,lambda.,eqlin,:,对应,A,2,x,=,b,2,lambda.lower:,对应,v,1,x,lambda.upper:,对应,x,v,2,Exam0802.m,23,MATLAB 求解 LP,opt,MATLAB控制参数:,三种,算法选择,缺省时采用大规模算法（是一种内点算法）；,当,opt,中“,LargeScale,”,参数设置为“,off”,时，采用中规模算法，该模式下缺省的算法是二次规划的算法（一种有效集方法）；,当,opt,中“,LargeScale,”,参数设置为“,off”,，并且“,Simplex”,参数设置为“,on”,时，采用单纯形算法。,只有有效集方法可以由用户提供初始解,x0,，其他两个算法则不需要（即使提供了也会被,MATLAB,忽略）。,Exam0801.m,x,fval,exitflag,output,lambda=,linprog(c,A1,b1,A2,b2,v1,v2,x0,opt),24,c=12 8 22 16-1.5-1.5;,A1=4 3 0 0 4 3;2 1 0 0 3 2;1 0 0 0 1 0;,b1=600 240 100;,A2=0 0 1 0-0.8 0;0 0 0 1 0-0.75;,b2=0 0;,v1=0 0 0 0 0 0;,x,z0,ef,out,lag=linprog(-c,A1,b1,A2,b2,v1),lag.ineqlin,lag.eqlin,实例1:奶制品生产销售计划,x=(0,168,19.2,0,24,0);,z,=-z0=1730.4;,lag.ineqlin=(1.58;3.26;0.00);,25,15,元可增加,1,桶牛奶，应否投资？,实例1:奶制品生产销售计划,x=(0,168,19.2,0,24,0);,z,=-z0=1730.4,lag.ineqlin=(1.58;3.26;0.00);,601,z1=1731.98,dz=z1-z=1731.98-1730.4=1.58,dz=lag.ineqlin(1),dz*12=1.58*12=18.9615,应该投资！,“影子价格”,26,实例1:奶制品生产销售计划,聘用临时工人增加劳动时间，工资最多每小时几元？,x=(0,168,19.2,0,24,0);,z,=-z0=1730.4,lag.ineqlin=(1.58;3.26;0.00);,lag.ineqlin(2)=3.26，,所以1小时劳动时间的影子价格应为3.26/2=1.63，,即单位劳动时间增加的利润是1.63(元),27,B,1,，,B,2,的获利经常有,10%,的波动，对计划有无影响？,实例1:奶制品生产销售计划,x=(0,168,19.2,0,24,0);,z,=-z0=1730.4,lag.ineqlin=(1.58;3.26;0.00);,若每公斤B1的获利下降10%,应将目标函数中,x,3,的系数改为19.8，重新计算发现最优解和最优值均发生了变化,若B2的获利向上波动10%，原计划也不再是最优的,MATLAB没有给出这种,敏感性分析,的结果(LINDO/LINGO可以),28,非线性规划(NLP)基本原理,g,1,d,g,2,=0,g,1,=0,g,3,=0,g,j,0,o,x,设,x,为可行解，位于约束边界,J,1,起作用约束,(j=1),J,2,不起作用约束,(j=2,3),可行方向,下降方向,(G),不等式约束,29,x,为最优解,不存在满足(1),(2)的,d,g,3,(,x,)=0,g,1,(,x,)=0,g,2,(,x,)=0,G,(,g,j,0),x,O,g,1,(,x,),g,2,(,x,),f,(,x,),x,0,g,1,(,x,0,),d,f,(,x,)=,c,c,g,1,(,x,0,),若,x,沿,d,方向既可行又下降，则,x,不是最优解,观察,f,的梯度能表示成,g,1,和,g,2,的梯度的非负线性组合!,最优解的必要条件,30,KKT,条件,互补性条件,且,线性无关，则存在,若x为最优解，,最优解的必要条件,31,KKT条件的几何解释,Q,P,f,-,g,1,-,g,2,f,-,g,1,-,g,2,x,2,x,1,0,最优解在P(3,1),取得,P(3,1)是KKT点,其它点(如Q)均不是,(7,3),32,二次规划(QP)及有效集方法,当H为对称阵，称二次规划,当H正定时，称凸二次规划,凸二次规划性质,：,最优点,KKT点；,局部最优解,全局最优解,；,最优解方程,L函数,等式约束 下,的Lagrange,乘子法,33,解二次规划的有效集方,法,基本思想：,对于不等式约束的二次规划，在某可行点,处,将不起作用约束去掉，,起作用约束视为等式约束,，,通过求解等式约束的二次规划来改进可行点。,若,x,为,(1),的最优解，则它也是,(2),的最优解,若,x,为,(1),的可行解，又是,(2),的,KKT,点，且,L,乘子非负，则它必是,(1),的最优解。,(1),(2),基本原理,34,若,d,*,0，且,x,*+,d,*可行则继续;否则,确定步长,*(1)使,a,p,(,x,*+,*,d,*)=,b,p,，,p,J*,，则有效集修正为,J,*,p,。,设(1)的可行点为,x*,，有效集记作,J*,，用L乘子法求解:,基本步骤,得,d,*,*,若,d,*=0,则,x,*,为,(2),最优解,;,当,*,非负时,x,*,是,(1),最优解,若,d,*=0,且(,*),q,1,g=.%gradient of the function,if,nargout,2,H=.%Hessian,end,41,nlcon.m给出约束,GradConstr=on时还给出梯度,形式为,function c1,c2,GC1,GC2=nlcon(x),c1=.%nonlinear inequalities at x,c2=.%nonlinear equalities at x,if,nargout,2,GC1=.%gradients of c1,GC2=.%gradients of c2,end,MATLAB求解,约束NLP,例4,Exam0804.m,42,MATLAB优化工具箱,能求解的优化模型,优化工具箱3.0(MATLAB 7.0 R14),连续优化,离散优化,无约束优化,非线性,极小,fminunc,非光滑(不可,微)优化,fminsearch,非线性,方程(组),fzero,fsolve,全局,优化,暂缺,非线性,最小二乘,lsqnonlin,lsqcurvefit,线性规划,linprog,纯0-1规划 bintprog,一般IP,(暂缺),非线性规划,fmincon,fminimax,fgoalattain,fseminf,上下界约束,fminbnd,fmincon,lsqnonlin,lsqcurvefit,约束线性,最小二乘,lsqnonneg,lsqlin,约束优化,二次规划,quadprog,43,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型,决策变量：,c,i j,(,料场j,到,工地i的运量）12维,Shili0803lin.m,实例3:供应与选址,44,结果：,总吨公里数为85.3，比使用原料场减少了50.9。,初始点的选择,实例3:供应与选址,决策变量：,c,i j，,(,x,j,y,j,)16,维,用现料场总吨公里数为136.2,改建两个新料场,局部最优解问题,Shili0803.m;shili083fun.m,45,决策变量：,c,i，,(,x,j,y,j,)10,维,计算方法的改善,局部最优解问题有所改进,Shili0803n.m;shili083fun1.m,46,+为工地,数字为用量;,*,为新料场,数字为供应量。,47,实验目的,1）掌握用MATLAB优化工具包解线性规划和非线性规划(包括二次规划)的方法；,2）练习建立实际问题的线性规划和非线性规划模型。,实验内容,4（5）；8；10,布置实验内容,48,