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

《Exp08姜启源数学建模课件第八章约束优化.ppt》由会员分享，可在线阅读，更多相关《Exp08姜启源数学建模课件第八章约束优化.ppt（48页珍藏版）》请在三一办公上搜索。

1、大学数学实验,Mathematical Experiments,实验8 约束优化,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,当最优解在可行域边界上取得时不能用无约束优化方法求解,约束优化的分类,线性规划(LP)目标和约束均为线性函数 非线性规划(NLP)目标或约束中存在非线性函数 二次规划(QP)目标为二次函数、约束为线性 整数规划(IP)决策变量(部分)为整数 整数线性规划(ILP)整数非线性规划(INLP)0-1规划整数决策变量只取或,连续优化,离散优化,数学规划(Math.Prog.),本实验基本内容,2.基本原理和算法,3.MATLAB实现,1.问题与模型,NL

2、P,LP,QP,连续优化,制订生产计划，使每天净利润最大,15元可增加1桶牛奶，应否投资？,50桶牛奶,480小时,至多100公斤A1,B1，B2的获利经常有10%的波动，对计划有无影响？,实例1:奶制品生产销售计划,聘用临时工人增加劳动时间，工资最多每小时几元？,出售x1 千克 A1,x2 千克 A2，,x3千克 B1,x4千克 B2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x5千克 A1加工B1，x6千克 A2加工B2,附加约束,LP,50万元基金用于投资三种股票A、B、C：A每股年期望收益5元(标准差2元)，目前市价20元；B每股年期望收益8元(标准差

3、6元)，目前市价25元；C每股年期望收益10元(标准差10元)，目前市价30元；股票A、B收益的相关系数为5/24;股票A、C收益的相关系数为0.5;股票B、C收益的相关系数为0.25。,实例2：投资组合问题,如期望今年得到至少20%的投资回报，应如何投资？投资回报率与风险的关系如何？,假设：1、基金不一定要用完（不用不计利息或贬值）2、风险通常用收益的方差或标准差衡量,决策变量 x1、x2和 x3 分别表示投资A、B、C的数量（国内股票通常以“一手”（100股）为最小单位出售，这里以100股为单位，期望收益以百元为单位）,实例2：投资组合问题,A、B、C每手(百股)的收益分别记为S1,S2和

4、S3(百元)：ES1=5,ES2=8,ES3=10，DS1=4,DS2=36,DS3=100，r12=5/24,r13=-0.5，r23=-0.25,总收益 S=x1S1+x2S2+x3S3：是一个随机变量,投资风险（总收益的方差）为,实例2：投资组合问题,总期望收益为 Z1=ES=x1ES1+x2ES2+x3ES3=5x1+8x2+10 x3,总收益 S=x1S1+x2S2+x3S3：是一个随机变量,二次规划（QP）模型,实例2：投资组合问题,s.t.5x1+8x2+10 x3 1000 20 x1+25x2+30 x3 5000 x1，x2，x3 0,通过试探发现 从0.00010.1以0

5、.0001的步长变化就可以得到很好的近似结果,Min Z=Z2-Z1 s.t.20 x1+25x2+30 x3 5000 x1，x2，x3 0,加权模型,实例3：供应与选址,某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）,假设：料场和工地之间有直线道路,线性规划模型,决策变量：ci j 12维(料场j到工地i运量）,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。,决策变量：ci j，(xj,yj)16维,非线性规划模型,求解线性规划(LP)的基本原理,基本模型,二维线性规划的图解法一般线性规划的单纯

6、形算法一般线性规划的内点算法,二维线性规划的图解法,起作用约束：L2;L3,最优解（4，1），最优值zmax=13,L1L2L3,求解LP的基本思想,从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。,LP的约束和目标函数均为线性函数,2维,可行域 线段组成的凸多边形,目标函数 等值线为直线,最优解 凸多边形的某个顶点,n维,超平面组成的凸多面体,等值线是超平面,凸多面体的某个顶点,算法：怎样从一点转到下一点，尽快找到最优解。,求解LP的特殊情形,L1L2L3,无可行解,无最优解(无界),最优解不唯一,线性规划的标准形和基本性质,标准形,加入松弛变量/剩余变量将不等

7、式变为等式,一般还假定b0rank(A)=m,对标准形求解,先求可行解,再在有限个可行解中寻找最优解,O点,Q点,R点,Q,R,基本可行解x：Ax=b,x 0(xB0，xN=0),P点,P,B:基(矩阵)x:基(本)解,可行域存在时，必是凸多面体(可能无界)；最优解存在时，必在可行域的顶点取得(可能无界)；基本可行解对应于可行域的顶点(极点)。,LP基本性质,最优解只需在有限个可行解（基本可行解）中寻找,单纯形法的基本思路,从一个顶点转换到另一个顶点（即构成xB和xN的向量pi间的转换），使目标函数逐步下降。,LP的通常解法是单纯形法(G.B.Dantzig,1947),内点算法(Interi

8、or point method)20世纪80年代人们提出的一类新的算法内点算法也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。,LP其他算法,有效集(Active Set)方法 LP是QP的特例（只需令所有二次项为零即可）可以用QP的算法解LP(如:有效集方法，详见下节),x,fval,exitflag,output,lambda=linprog(c,A1,b1,A2,b2,v1,v2,x0,opt),MATLAB 求解 LP,输入：x0初始解(缺省时一般为0)opt MATLAB控制参数中间所缺参数项补,输出：lambda Lagrange乘子，维数等

9、于约束个数，非零分量对应于起作用约束 lambda.ineqlin:对应 A1xb1 lambda.eqlin:对应 A2x=b2 lambda.lower:对应 v1 x lambda.upper:对应 x v2,Exam0802.m,MATLAB 求解 LP,opt MATLAB控制参数:三种算法选择,缺省时采用大规模算法（是一种内点算法）；当opt中“LargeScale”参数设置为“off”时，采用中规模算法，该模式下缺省的算法是二次规划的算法（一种有效集方法）；当opt中“LargeScale”参数设置为“off”，并且“Simplex”参数设置为“on”时，采用单纯形算法。只有有效

10、集方法可以由用户提供初始解x0，其他两个算法则不需要（即使提供了也会被MATLAB忽略）。,Exam0801.m,x,fval,exitflag,output,lambda=linprog(c,A1,b1,A2,b2,v1,v2,x0,opt),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.in

11、eqlin,lag.eqlin,实例1:奶制品生产销售计划,x=(0,168,19.2,0,24,0);z=-z0=1730.4;lag.ineqlin=(1.58;3.26;0.00);,15元可增加1桶牛奶，应否投资？,实例1:奶制品生产销售计划,x=(0,168,19.2,0,24,0);z=-z0=1730.4lag.ineqlin=(1.58;3.26;0.00);,601z1=1731.98dz=z1-z=1731.98-1730.4=1.58dz=lag.ineqlin(1),dz*12=1.58*12=18.9615应该投资！,“影子价格”,实例1:奶制品生产销售计划,聘用临时

12、工人增加劳动时间，工资最多每小时几元？,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(元),B1，B2的获利经常有10%的波动，对计划有无影响？,实例1:奶制品生产销售计划,x=(0,168,19.2,0,24,0);z=-z0=1730.4 lag.ineqlin=(1.58;3.26;0.00);,若每公斤B1的获利下降10%,应将目标函数中x3的系数改为19.8，重新计算发现

13、最优解和最优值均发生了变化若B2的获利向上波动10%，原计划也不再是最优的,MATLAB没有给出这种敏感性分析的结果(LINDO/LINGO可以),非线性规划(NLP)基本原理,设x为可行解，位于约束边界,J1起作用约束(j=1),J2不起作用约束(j=2,3),可行方向,下降方向,(G),不等式约束,若x沿d方向既可行又下降，则x不是最优解,观察f 的梯度能表示成g1和g2的梯度的非负线性组合!,最优解的必要条件,最优解的必要条件,KKT条件的几何解释,最优解在P(3,1)取得,P(3,1)是KKT点,其它点(如Q)均不是,二次规划(QP)及有效集方法,当H为对称阵，称二次规划当H正定时，称

14、凸二次规划,凸二次规划性质：最优点KKT点；局部最优解全局最优解；,最优解方程,L函数,等式约束 下的Lagrange乘子法,解二次规划的有效集方法,基本思想：对于不等式约束的二次规划，在某可行点处将不起作用约束去掉，起作用约束视为等式约束，通过求解等式约束的二次规划来改进可行点。,若x为(1)的最优解，则它也是(2)的最优解,若x为(1)的可行解，又是(2)的KKT点，且L乘子非负，则它必是(1)的最优解。,(1),(2),基本原理,若d*0，且x*+d*可行则继续;否则确定步长*(1)使ap(x*+*d*)=bp，pJ*，则有效集修正为J*p。,设(1)的可行点为x*，有效集记作J*，用L

15、乘子法求解:,基本步骤,得d*,*,若d*=0,则x*为(2)最优解;当*非负时x*是(1)最优解,若d*=0,且(*)q0,qJ*,则x*不是(1)最优解,有效集修正为J*q。,有效集修正,解二次规划的有效集方法,MATLAB求解QP,x,fval,exitflag,output,lambda=quadprog(H,c,A1,b1,A2,b2,v1,v2,x0,options),解得x=1.0e+002*（1.3111，0.1529，0.2221）如果一定要整数解，可以四舍五入到（131，15，22）如利用LINGO软件,可得整数最优解(132，15，22)用去资金为13220+1525+2

16、230=3675（百元）期望收益为1325+158+2210=1000（百元）风险(方差)为 68116，标准差约为261（百元）,实例2：投资组合问题,s.t.5x1+8x2+10 x3 1000 20 x1+25x2+30 x3 5000 x1，x2，x3 0,通过试探发现 从0.00010.1以0.0001的步长变化就可以得到很好的近似结果,实例2：投资组合问题,Min Z=Z2-Z1 s.t.20 x1+25x2+30 x3 5000 x1，x2，x3 0,加权模型,投资股票A、B、C分别为153、35、35（手）,非线性规划(NLP)的解法,可行方向法、罚函数法、梯度投影法.,逐步二

17、次规划法(Sequential Quadratic Programming),SQP的基本原理,构造NLP的拉格朗日函数,用二次函数近似 L(x,),NLP化为QP,再解一系列QP子问题。,QP子问题,求解QP子问题，得 dk；,将最优解dk作为迭代的搜索方向，令,SQP的基本步骤,确定矩阵Gk的迭代公式。,用线性搜索计算迭代步长k；,逐步二次规划法,MATLAB求解约束NLP,x,fval,exitflag,output,lambda,grad,hessian=fmincon(fun,x0,A1,b1,A2,b2,v1,v2,nlcon,options,P1,P2,.),fun.m给出函数f

18、，当GradObj=on时必须给出f的梯度，Hessian=on时还必须给出其Jacobi矩阵，形式为,function f,g,H=fun(x)f=.%objective function value if nargout 1 g=.%gradient of the function if nargout 2 H=.%Hessianend,nlcon.m给出约束,GradConstr=on时还给出梯度,形式为,function c1,c2,GC1,GC2=nlcon(x)c1=.%nonlinear inequalities at xc2=.%nonlinear equalities at

19、xif nargout 2 GC1=.%gradients of c1 GC2=.%gradients of c2end,MATLAB求解约束NLP,MATLAB优化工具箱能求解的优化模型,优化工具箱3.0(MATLAB 7.0 R14),连续优化,离散优化,无约束优化,非线性极小fminunc,非光滑(不可微)优化fminsearch,非线性方程(组)fzerofsolve,全局优化暂缺,非线性最小二乘lsqnonlinlsqcurvefit,线性规划linprog,纯0-1规划 bintprog一般IP(暂缺),非线性规划fminconfminimaxfgoalattainfseminf,

20、上下界约束fminbndfminconlsqnonlinlsqcurvefit,约束线性最小二乘lsqnonneglsqlin,约束优化,二次规划quadprog,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型,决策变量：ci j(料场j到工地i的运量）12维,Shili0803lin.m,实例3:供应与选址,结果：总吨公里数为85.3，比使用原料场减少了50.9。,初始点的选择,实例3:供应与选址,决策变量：ci j，(xj,yj)16维,用现料场总吨公里数为136.2,改建两个新料场,局部最优解问题,Shili0803.m;shili083fun.m,决策变量：ci，(xj,yj)10维,计算方法的改善,局部最优解问题有所改进,Shili0803n.m;shili083fun1.m,+为工地,数字为用量;*为新料场,数字为供应量。,实验目的,1）掌握用MATLAB优化工具包解线性规划和非线性规划(包括二次规划)的方法；2）练习建立实际问题的线性规划和非线性规划模型。,实验内容,4（5）；8；10,布置实验内容,