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

大学数学实验,Mathematical Experiments,实验8 约束优化,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,当最优解在可行域边界上取得时不能用无约束优化方法求解,约束优化的分类,线性规划(LP)目标和约束均为线性函数 非线性规划(NLP)目标或约束中存在非线性函数 二次规划(QP)目标为二次函数、约束为线性 整数规划(IP)决策变量(部分)为整数 整数线性规划(ILP)整数非线性规划(INLP)0-1规划整数决策变量只取或,连续优化,离散优化,数学规划(Math.Prog.),本实验基本内容,2.基本原理和算法,3.MATLAB实现,1.问题与模型,NLP,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元(标准差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和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.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)的基本原理,基本模型,二维线性规划的图解法一般线性规划的单纯形算法一般线性规划的内点算法,二维线性规划的图解法,起作用约束：L2;L3,最优解（4，1），最优值zmax=13,L1L2L3,求解LP的基本思想,从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。,LP的约束和目标函数均为线性函数,2维,可行域 线段组成的凸多边形,目标函数 等值线为直线,最优解 凸多边形的某个顶点,n维,超平面组成的凸多面体,等值线是超平面,凸多面体的某个顶点,算法：怎样从一点转到下一点，尽快找到最优解。,求解LP的特殊情形,L1L2L3,无可行解,无最优解(无界),最优解不唯一,线性规划的标准形和基本性质,标准形,加入松弛变量/剩余变量将不等式变为等式,一般还假定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),内点算法(Interior 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乘子，维数等于约束个数，非零分量对应于起作用约束 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”时，采用单纯形算法。只有有效集方法可以由用户提供初始解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.ineqlin,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:奶制品生产销售计划,聘用临时工人增加劳动时间，工资最多每小时几元？,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，重新计算发现最优解和最优值均发生了变化若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正定时，称凸二次规划,凸二次规划性质：最优点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乘子法求解:,基本步骤,得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+2230=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)的解法,可行方向法、罚函数法、梯度投影法.,逐步二次规划法(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，当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 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,上下界约束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,布置实验内容,