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

大学 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 实验MathematicalExperiments实验8约束优化优化问题三要素：决策变量；目标 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 ；约束条件优化问题的一般形式当最优解在可行域边界上取得时不能用无约束优化 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 求解约束优化的分类线性规划(LP)目标和约束均为线性函数非线性规划(NLP)目标或约束中存在非线性函数二次规划(QP)目标为二次函数、约束为线性整数规划(IP)决策变量(部分)为整数整数线性规划(ILP)整数非线性规划(INLP)0-1规划　　　整数决策变量只取０或１连续优化离散优化数学规划(Math.Prog.)本实验基本内容2.基本原理和算法3.MATLAB实现1.问题与模型NLPLPQP连续优化制订生产计划，使每天净利润最大15元可增加1桶牛奶，应否投资？50桶牛奶,480小时至多100公斤A1B1，B2的获利经常有10%的波动，对计划有无影响？实例1:奶制品生产销售计划聘用临时工人增加劳动时间，工资最多每小时几元？出售x1千克A1,x2千克A2，x3千克B1,x4千克B2原料供应劳动时间加工能力决策变量目标函数利润约束条件非负约束x5千克A1加工B1，x6千克A2加工B2附加约束LP50万元基金用于投资三种股票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分别 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示投资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+10x3总收益S=x1S1+x2S2+x3S3：是一个随机变量二次规划（QP）模型实例2：投资组合问题s.t.5x1+8x2+10x3100020x1+25x2+30x35000x1，x2，x30通过试探发现β从0.0001~0.1以0.0001的步长变化就可以得到很好的近似结果MinZ=βZ2-Z1s.t.20x1+25x2+30x35000x1，x2，x30加权模型实例3：供应与选址某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）假设：料场和工地之间有直线道路线性规划模型决策变量：cij~12维(料场j到工地i运量）2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。决策变量：cij，(xj,yj)~16维非线性规划模型求解线性规划(LP)的基本原理基本模型　二维线性规划的图解法　一般线性规划的单纯形算法　一般线性规划的内点算法二维线性规划的图解法起作用约束：L2;L3最优解（4，1），最优值zmax=13~L1~L2~L3求解LP的基本思想从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。LP的约束和目标函数均为线性函数2维可行域线段组成的凸多边形目标函数等值线为直线最优解凸多边形的某个顶点n维超平面组成的凸多面体等值线是超平面凸多面体的某个顶点算法：怎样从一点转到下一点，尽快找到最优解。求解LP的特殊情形~L1~L2~L3无可行解无最优解(无界)最优解不唯一线性规划的标准形和基本性质标准形加入松弛变量/剩余变量将不等式变为等式一般还假定b≥0rank(A)=m对标准形求解先求可行解再在有限个可行解中寻找最优解O点Q点R点QR基本可行解x：Ax=b,x0(xB0，xN=0)P点PB:基(矩阵)　　x:基(本)解可行域存在时，必是凸多面体(可能无界)；最优解存在时，必在可行域的顶点取得(可能无界)；基本可行解对应于可行域的顶点(极点)。LP基本性质最优解只需在有限个可行解（基本可行解）中寻找单纯形法的基本思路从一个顶点转换到另一个顶点（即构成xB和xN的向量pi间的转换），使目标函数逐步下降。LP的通常解法是单纯形法(G.B.Dantzig,1947)内点算法(Interiorpointmethod)　20世纪80年代人们提出的一类新的算法——内点算法　也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。LP其他算法有效集(ActiveSet)方法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:对应A1x≤b1lambda.eqlin:对应A2x=b2lambda.lower:对应v1≤xlambda.upper:对应x≤v2Exam0802.mMATLAB求解LPopt~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=[1282216-1.5-1.5];A1=[430043;210032;100010];b1=[600240100];A2=[0010-0.80;00010-0.75];b2=[00];v1=[000000];[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.96>15应该投资！“影子价格”实例1:奶制品生产销售计划聘用临时工人增加劳动时间，工资最多每小时几元？x=(0,168,19.2,0,24,0);z=-z0=1730.4lag.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.4lag.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函数解二次规划的有效集方法基本思想：对于不等式约束的二次规划，在某可行点处将不起作用约束去掉，起作用约束视为等式约束，通过求解等式约束的二次规划来改进可行点。若x为(1)的最优解，则它也是(2)的最优解若x为(1)的可行解，又是(2)的KKT点，且L—乘子非负，则它必是(1)的最优解。基本原理若d*0，且x*+d*可行则继续;否则确定步长*(<1)使ap(x*+*d*)=bp，pJ*，则有效集修正为J*{p}。设(1)的可行点为x*，有效集记作J*，用L—乘子法求解:基本步骤得d*,*若d*=0,则x*为(2)最优解;当*非负时x*是(1)最优解若d*=0,且(*)q<0,qJ*,则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)用去资金为13220+1525+2230=3675（百元）期望收益为1325+158+2210=1000（百元）风险(方差)为68116，标准差约为261（百元）实例2：投资组合问题s.t.5x1+8x2+10x3100020x1+25x2+30x35000x1，x2，x30通过试探发现β从0.0001~0.1以0.0001的步长变化就可以得到很好的近似结果实例2：投资组合问题MinZ=βZ2-Z1s.t.20x1+25x2+30x35000x1，x2，x30加权模型投资股票A、B、C分别为153、35、35（手）非线性规划(NLP)的解法可行方向法、罚函数法、梯度投影法...　逐步二次规划法(SequentialQuadraticProgramming)SQP的基本原理构造NLP的拉格朗日函数用二次函数近似L(x,,),NLP化为QP,再解一系列QP子问题。QP子问题求解QP子问题，得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=...%objectivefunctionvalueifnargout>1g=...%gradientofthefunctionifnargout>2H=...%Hessianendnlcon.m给出约束,GradConstr=‘on’时还给出梯度,形式为function[c1,c2,GC1,GC2]=nlcon(x)c1=...%nonlinearinequalitiesatxc2=...%nonlinearequalitiesatxifnargout>2GC1=...%gradientsofc1GC2=...%gradientsofc2endMATLAB求解约束NLPMATLAB优化工具箱能求解的优化模型优化工具箱3.0(MATLAB7.0R14)连续优化离散优化无约束优化非线性极小fminunc非光滑(不可微)优化fminsearch非线性方程(组)fzerofsolve全局优化暂缺非线性最小二乘lsqnonlinlsqcurvefit线性规划linprog纯0-1规划bintprog一般IP(暂缺)非线性规划fminconfminimaxfgoalattainfseminf上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性最小二乘lsqnonneglsqlin约束优化二次规划quadprog用例中数据计算，最优解为总吨公里数为136.2线性规划模型决策变量：cij(料场j到工地i的运量）~12维Shili0803lin.m实例3:供应与选址结果：总吨公里数为85.3，比使用原料场减少了50.9。初始点的选择实例3:供应与选址决策变量：cij，(xj,yj)~16维用现料场总吨公里数为136.2改建两个新料场局部最优解问题Shili0803.m;shili083fun.m决策变量：ci，(xj,yj)~10维计算方法的改善局部最优解问题有所改进Shili0803n.m;shili083fun1.m+为工地,数字为用量;*为新料场,数字为供应量。实验目的1）掌握用MATLAB优化工具包解线性规划和非线性规划(包括二次规划)的方法；2）练习建立实际问题的线性规划和非线性规划模型。实验内容4（5）；8；10布置实验内容