Exp08姜启源数学建模课件第八章约束优化[高等教学].ppt

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

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

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

3、标准差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,决策变量 x1 、x2和 x3 分别表示投资A、B、C的数量（国内股票通常以“一手”（100股）为最小单位出售，这里以100股为单位，期望收益以百元为

4、单位）,实例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 ：是一个随机变量,8,投资风险（总收益的方差）为,实例2：投资组合问题,总期望收益为 Z1=ES= x1ES1+x2ES2+x3ES3=5x1+8x2+10 x3,总收益 S=x1S1+x2S2+x3S3 ：是一个随机变量,9,二次规划（QP）模型,实例2：投资组合问题,s.t. 5x1 +8x2+10 x3 1

5、000 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,加权 模型,10,实例3：供应与选址,某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里),水泥日用量di (单位：吨）,假设：料场和工地之间有直线道路,11,线性规划模型,决策变量： ci j 12维 (料场j到 工地i运量）,12,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij ，在其它条件不变下使总

6、吨公里数最小。,决策变量： ci j，(xj,yj)16维,非线性规划模型,13,求解线性规划(LP)的基本原理,基本模型,二维线性规划的图解法 一般线性规划的单纯形算法 一般线性规划的内点算法,14,二维线性规划的图解法,起作用约束：L2;L3,最优解（4，1），最优值zmax=13,L1 L2 L3,15,求解LP的基本思想,从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。,LP的约束和目标函数均为线性函数,2维,可行域 线段组成的凸多边形,目标函数 等值线为直线,最优解 凸多边形的某个顶点,n维,超平面组成的凸多面体,等值线是超平面,凸多面体的某个顶点,算法

7、：怎样从一点转到下一点，尽快找到最优解。,16,求解LP的特殊情形,L1 L2 L3,无可行解,无最优解(无界),最优解不唯一,17,线性规划的标准形和基本性质,标准形,加入松弛变量/剩余变量将不等式变为等式,一般还假定 b0 rank(A)=m,18,对标准形求解,先求可行解,再在有限个可行解中寻找最优解,19,O点,Q点,R点,Q,R,基本可行解x ：Ax=b, x 0 (xB0，xN=0),P点,P,B: 基(矩阵) x: 基(本)解,20,可行域存在时，必是凸多面体(可能无界)； 最优解存在时，必在可行域的顶点取得(可能无界)； 基本可行解对应于可行域的顶点(极点)。,LP基本性质,最

8、优解只需在有限个可行解（基本可行解）中寻找,单纯形法的基本思路,从一个顶点转换到另一个顶点（即构成xB和xN的向量pi间的转换），使目标函数逐步下降。,LP的通常解法是单纯形法(G. B. Dantzig, 1947),21,内点算法(Interior point method) 20世纪80年代人们提出的一类新的算法内点算法 也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。,LP其他算法,有效集(Active Set)方法 LP是QP的特例（只需令所有二次项为零即可） 可以用QP的算法解LP(如: 有效集方法，详见下节),22,x,fval,exitf

9、lag,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,23,MATLAB 求解 LP,opt MATLAB控制参数:三

10、种算法选择,缺省时采用大规模算法（是一种内点算法）； 当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

11、 -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桶牛奶，应否投资？,实例

12、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) ;

13、 ,lag.ineqlin(2)=3.26， 所以1小时劳动时间的影子价格应为3.26/2=1.63， 即单位劳动时间增加的利润是1.63(元),27,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/LIN

14、GO可以),28,非线性规划(NLP)基本原理,设x为可行解，位于约束边界,J1起作用约束(j=1),J2不起作用约束(j=2,3),可行方向,下降方向,(G),不等式约束,29,若x沿d方向既可行又下降，则x不是最优解,观察 f 的梯度能表示成g1和g2的梯度的非负线性组合!,最优解的必要条件,30,最优解的必要条件,31,KKT条件的几何解释,最优解在P(3,1)取得,P(3,1)是KKT点,其它点(如Q)均不是,32,二次规划(QP)及有效集方法,当H为对称阵，称二次规划 当H正定时，称凸二次规划,凸二次规划性质： 最优点KKT点； 局部最优解全局最优解；,最优解方程,L函数,等式约束

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

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

17、 期望收益为1325+158+2210 = 1000（百元） 风险(方差)为 68116，标准差约为261（百元）,实例2：投资组合问题,s.t. 5x1 +8x2+10 x3 1000 20 x1+25x2+30 x3 5000 x1，x2，x3 0,37,通过试探发现 从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（手）,38,非线性规划(NLP)的解法,可行方向法、罚函数法、梯度投影法

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

19、,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 = . % Hessian end,41,nlcon.m给出约束,GradConstr=on时还给出梯度,形式为,function c1,c2,GC1,GC2 = nlcon(x) c1 = . % nonlinear i

20、nequalities at x c2 = . % nonlinear equalities at x if nargout 2 GC1 = . % gradients of c1 GC2 = . % gradients of c2 end,MATLAB求解 约束NLP,42,MATLAB优化工具箱能求解的优化模型,优化工具箱3.0 (MATLAB 7.0 R14),连续优化,离散优化,无约束优化,非线性 极小 fminunc,非光滑(不可 微)优化 fminsearch,非线性 方程(组) fzero fsolve,全局 优化 暂缺,非线性 最小二乘 lsqnonlin lsqcurvefi

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