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

《Exp08姜启源数学建模课件第八章约束优化.ppt》由会员分享，可在线阅读，更多相关《Exp08姜启源数学建模课件第八章约束优化.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、大学数学实验大学数学实验Mathematical Experiments 实验实验8 8 约束优化约束优化1优化问题三要素：优化问题三要素：决策变量决策变量；目标函数目标函数；约束条件约束条件约约束束条条件件决策变量决策变量优化问题的一般形式优化问题的一般形式当最优解在可行域边界上取得时当最优解在可行域边界上取得时不能用无约束优化方法求解不能用无约束优化方法求解目标函数目标函数2约束优化的分类约束优化的分类 线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数 非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数 二次规划二次规划(QP)目标为二次

2、函数、约束为线性目标为二次函数、约束为线性 整数规划整数规划(IP)决策变量决策变量(部分部分)为整数为整数 整数整数线性线性规划规划(ILP)整数整数非线性非线性规划规划(INLP)0-1规划规划整数决策变量只取或整数决策变量只取或连连续续优优化化离离散散优优化化数学规划数学规划(Math.Prog.)3本实验基本内容本实验基本内容2.基本原理和算法基本原理和算法3.MATLAB实现实现1.问题与模型问题与模型NLPNLPLPLPQPQP连续优化连续优化41桶桶牛奶牛奶 3千克千克A1 12小时小时 8小时小时 4千克千克A2或或获利获利12元元/千千克克获利获利8元元/千克千克 0.8千克

3、千克B12小时小时,1.5元元1千克千克获利获利22元元/千千克克 0.75千克千克B22小时小时,1.5元元1千克千克获利获利16元元/千千克克 制订生产计划，使每天净利润最大制订生产计划，使每天净利润最大 15元可增加元可增加1桶牛奶，应否投资？桶牛奶，应否投资？50桶牛奶桶牛奶,480小时小时 至多至多100公斤公斤A1 B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？实例实例1:奶制品生产销售计划奶制品生产销售计划 聘用临时工人增加劳动时间，工资最多每小时几元？聘用临时工人增加劳动时间，工资最多每小时几元？51桶桶牛奶牛奶 3千克千克 A1 12

4、小时小时 8小时小时 4千克千克 A2 或或获利获利12元元/千克千克 获利获利8元元/千克千克 0.8千克千克 B12小时小时,1.5元元1千克千克获利获利22元元/千克千克 0.75千克千克 B22小时小时,1.5元元1千克千克获利获利16元元/千克千克 出售出售x1 千克千克 A1,x2 千克千克 A2，x3千克千克 B1,x4千克千克 B2原料原料供应供应 劳动劳动时间时间 加工能力加工能力 决策决策变量变量 目标目标函数函数 利润利润约束约束条件条件非负约束非负约束 x5千克千克 A1加工加工B1，x6千克千克 A2加工加工B2附加约束附加约束 LP650万元基金用于投资三种股票万元

5、基金用于投资三种股票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%20%的投资回报，应如何投资？的投资回报，应如何

6、投资？投资回报率与风险的关系如何？投资回报率与风险的关系如何？假设：假设：1、基金不一定要用完（不用不计利息或贬值）、基金不一定要用完（不用不计利息或贬值）2、风险通常用收益的方差或标准差衡量、风险通常用收益的方差或标准差衡量7决策变量决策变量 x1、x2和和 x3 分别表示投资分别表示投资A、B、C的数量的数量（国内股票通常以（国内股票通常以“一手一手”（100股）为最小单位出售，股）为最小单位出售，这里以这里以100股为单位，期望收益以百元为单位）股为单位，期望收益以百元为单位）实例实例2：投资组合问题：投资组合问题A、B、C每手每手(百股百股)的收益分别记为的收益分别记为S1,S2和和S

7、3(百元百元)：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 +8

8、x2+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 加权加权模型模型10 实例实例3 3：供应与选址：供应与选址某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）假设：假设：料场和工地之间有直线道路料场和工地之间有直线道路11线性规划模型线性规划模型决策变量：决策变量：ci j 12维维

9、(料场料场j到到工地工地i运量）运量）122）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。决策变量：决策变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型13求解线性规划求解线性规划(LP)的基本原理的基本原理基基本本模模型型二维线性规划的图解法二维线性规划的图解法一般线性规划的单纯形算法一般线性规划的单纯形算法一般线性规划的内点算法一般线性规划的内点算法14二维线性规划的图解法二维线性规划的图解法x2x10L1L2L3z1=0z2=2z3=6z4=10z5=13grad zx*起作用约束：起作用约束：L2;L3最优解（最优解

10、（4，1），最优值），最优值zmax=13L1L2L315求解求解LP的基本思想的基本思想从可行域的某一顶点开始，只需在有限多个顶点中从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到一个一个找下去，一定能得到最优解最优解。LP的约束和目标函数均为线性函数的约束和目标函数均为线性函数2维维可行域可行域 线段组成的凸多边形线段组成的凸多边形目标函数目标函数 等值线为直线等值线为直线最优解最优解 凸多边形的某个顶点凸多边形的某个顶点n维维超平面组成的凸多面体超平面组成的凸多面体等值线是超平面等值线是超平面凸多面体的某个顶点凸多面体的某个顶点算法：怎样从一点转到下一点，尽快找到最

11、优解。算法：怎样从一点转到下一点，尽快找到最优解。16x2x10L1L2L3x2x10L1L2L3x2x10L1L2求解求解LPLP的特殊情形的特殊情形L1L2L3无可行解无可行解无最优解无最优解(无界无界)最优解不唯一最优解不唯一x2x10L1L2L3z=c17线性规划的标准形和基本性质线性规划的标准形和基本性质标标准准形形加入松弛变量加入松弛变量/剩余变量将不等式变为等式剩余变量将不等式变为等式一般还假定一般还假定b0rank(A)=m18对标准形求解对标准形求解先求可行解先求可行解再在有限个可行解中寻找最优解再在有限个可行解中寻找最优解19x2x1OO点点Q点点R点点QR基本可行解基本可

12、行解x：Ax=b,x 0(xB 0，xN=0)P点点PB:基基(矩阵矩阵)x:基基(本本)解解20可行域存在时，必是凸多面体可行域存在时，必是凸多面体(可能无界可能无界)；最优解存在时，必在可行域的顶点取得最优解存在时，必在可行域的顶点取得(可能无界可能无界)；基本可行解对应于可行域的顶点基本可行解对应于可行域的顶点(极点极点)。LPLP基本性质基本性质最优解只需在有限个可行解（基本可行解）中寻找最优解只需在有限个可行解（基本可行解）中寻找单纯形法的基本思路单纯形法的基本思路从一个顶点转换到另一个顶点（即构成从一个顶点转换到另一个顶点（即构成xB和和xN的的向量向量pi间的转换），使目标函数逐

13、步下降。间的转换），使目标函数逐步下降。LP的通常解法是单纯形法的通常解法是单纯形法(G.B.Dantzig,1947)21内点算法内点算法(Interior point method)20世纪世纪80年代人们提出的一类新的算法年代人们提出的一类新的算法内点算法内点算法也是迭代法，但不再从可行域的一个顶点转换到另一个也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。顶点，而是直接从可行域的内部逼近最优解。LPLP其他算法其他算法有效集有效集(Active Set)方法方法 LP是是QP的特例（只需令所有二次项为零即可）的特例（只需令所有二次项为零即可）可以

14、用可以用QP的算法解的算法解LP(如如:有效集方法，详见下节有效集方法，详见下节)22x,fval,exitflag,output,lambda=linprog(c,A1,b1,A2,b2,v1,v2,x0,opt)MATLAB MATLAB 求解求解 LP LP输入：输入：x0 x0初始解初始解(缺省时一般为缺省时一般为0)0)opt opt MATLAB MATLAB控制参数控制参数中间所缺参数项补中间所缺参数项补输出：输出：lambda lambda LagrangeLagrange乘子，乘子，维维数等于约束个数，非零分量对数等于约束个数，非零分量对应于起作用约束应于起作用约束 lamb

15、da.ineqlin:对应 A1xb1 lambda.eqlin:对应 A2x=b2 lambda.lower:对应 v1 x lambda.upper:对应 x v2Exam0802.m23MATLAB MATLAB 求解求解 LP LPopt MATLAB控制参数:三种三种算法选择 缺省时采用大规模算法（是一种内点算法）；缺省时采用大规模算法（是一种内点算法）；当当opt中中“LargeScale”参数设置为参数设置为“off”时，采用中规模算时，采用中规模算法，该模式下缺省的算法是二次规划的算法（一种有效集方法）法，该模式下缺省的算法是二次规划的算法（一种有效集方法）；当当opt中中“L

16、argeScale”参数设置为参数设置为“off”，并且，并且“Simplex”参数设置为参数设置为“on”时，采用单纯形算法。时，采用单纯形算法。只有有效集方法可以由用户提供初始解只有有效集方法可以由用户提供初始解x0，其他两个算法则不，其他两个算法则不需要（即使提供了也会被需要（即使提供了也会被MATLAB忽略）。忽略）。Exam0801.mx,fval,exitflag,output,lambda=linprog(c,A1,b1,A2,b2,v1,v2,x0,opt)24c=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

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

18、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应该投资！应该投资！“影子价格影子价格”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小

19、时劳动时间的影子价格应为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%，原计划也不

20、再是最优的原计划也不再是最优的MATLAB没有给出这种没有给出这种敏感性分析敏感性分析的结果的结果(LINDO/LINGO可以可以)28非线性规划非线性规划(NLP)(NLP)基本原理基本原理 g1dg2=0g1=0g3=0gj0ox设设x为可行解，为可行解，位于约束边界位于约束边界J1起作用约束起作用约束(j=1)J2不起作用约束不起作用约束(j=2,3)可行方向可行方向下降方向下降方向(G)不等式约束不等式约束29x为最优解为最优解不存在满足不存在满足(1),(2)的的dg3(x)=0g1(x)=0g2(x)=0G(gj0)xOg1(x)g2(x)f(x)x0g1(x0)df(x)=cc

21、g1(x0)若若x沿沿d方向既可行又下降，则方向既可行又下降，则x不是最优解不是最优解观察观察f 的梯度能表示成的梯度能表示成g1和和g2的梯度的非负的梯度的非负线性组合线性组合!最优解的必要条件最优解的必要条件30KKT条件条件互补性条件且且线性无关，则存在线性无关，则存在若若x为最优解，为最优解，最优解的必要条件最优解的必要条件31KKTKKT条件的几何解释条件的几何解释QP f-g1-g2 f-g1-g2x2x10最优解在最优解在P(3,1)取得取得P(3,1)是是KKT点点其它点其它点(如如Q)均不是均不是(7,3)32二次规划二次规划(QP)(QP)及有效集方法及有效集方法当H为对称

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

23、d*)=bp，pJ*，则有效集修正为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=.%Hessianend41nlcon.m给出约束,GradConstr=on时还给出梯度,形式为function c1,c2,GC1,GC2=nlcon(x)c1=.%nonlinear inequalities at xc2=.%nonlinear equalities at xif nar

24、gout 2 GC1=.%gradients of c1 GC2=.%gradients of c2endMATLABMATLAB求解求解约束约束NLPNLP例例4Exam0804.m42MATLABMATLAB优化工具箱优化工具箱能求解的优化模型能求解的优化模型优化工具箱优化工具箱3.0(MATLAB 7.0 R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方方程程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurve

25、fit线性规划线性规划linprog纯纯0-1规划规划 bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprog43用例中数据计算，最优解为总吨公里数为136.2线性规划模型线性规划模型决策变量：决策变量：ci j(料场料场j到到工地工地i的运量）的运量）12维维Shili0803lin.m实例实例3:3:供应与选址供应与选址44

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