优化设计第二部分约束最优化方法补充全ppt.pptx

优化设计第二部分约束最优化方法优化设计第二部分约束最优化方法补充全补充全原问题表述为原问题表述为:标准化后标准化后:线性规划问题目标函数与约束函数均就是线性得线性规划问题目标函数与约束函数均就是线性得线性规划问题相关定理线性规划问题相关定理1、线性规划问题得可行域、线性规划问题得可行域D就是凸集。就是凸集。2、若线性规划问题存在最优解、若线性规划问题存在最优解,则目标函数得则目标函数得 最优值可在某个极点最优值可在某个极点(顶点顶点)达到。达到。x1x2Dz 减小得方向最优解最优解最优解:x1=x2=20二、线性规划问题得单纯形求解算法介绍二、线性规划问题得单纯形求解算法介绍1947年提出年提出,后有许多改造后有许多改造,形成许多变种。应用较形成许多变种。应用较广广,具权威性。具权威性。现举例说明该算法得基本思想现举例说明该算法得基本思想x1x2z下降的方向下降的方向12345极点极点1234？极点极点154？极点极点14？思想思想:从一个基本可行解从一个基本可行解(极点极点)出发出发,求另一个使求另一个使目标函数值下降得基本目标函数值下降得基本可行解可行解、引入松弛变量引入松弛变量 x3、x4、x5,原式化成标准形式原式化成标准形式其中在中若令其中的两个未知量为零，则剩余的三个可由其解出。1)如另x1=x2=0,则有x1x212345上面得解就是可行解上面得解就是可行解,x1=x2=0对应于点对应于点1基本可行解基本可行解基变量基变量2)通过某些判定条件。令x5=x2=0新得解就是可行解新得解就是可行解,x1=3,x2=0对应于点对应于点5另一基本可行解另一基本可行解x1x212345基变量基变量非基变量非基变量3)通过某些判定条件。令x5=x4=0 x1x212345新得解就是可行解新得解就是可行解,x1=4、2,x2=5、2对应于点对应于点5最优基本解最优基本解基变量基变量关键点关键点:每次取三个基每次取三个基变量变量,根据一些判定条根据一些判定条件选择。前后两次迭代件选择。前后两次迭代得基变量相差一个。得基变量相差一个。极点极点154非基变量非基变量一般形式得线性规划问题一般形式得线性规划问题其中其中三、利用三、利用MATLAB求解线性规划问题求解线性规划问题12大家应该也有点累了，稍作休息大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流linprog(C,A,b,Aeq,beq,Lb,Ub)C=1;-3;1;Aeq=2-1 1;beq=8;A=-2-1 0;1 2 0;b=-2;10;Lb=0;0;0;x=linprog(C,A,b,Aeq,beq,Lb,)Optimization terminated successfully、x=0、8082 4、5959 10、9794 C=-4;-1;A=-1 2 2 3 1-1 b=4;12;3;Lb=0;0;x=linprog(C,A,b,Lb,)Optimization terminated successfully、x=4、2000 1、2000引例引例:某车间生产某车间生产A与与B两种产品。为了生产两种产品。为了生产A与与B,所所需得原料分别为每台需得原料分别为每台2与与3个单位个单位,所需工时分别为每所需工时分别为每台台4与与2个单位。现在可以应用得原料为个单位。现在可以应用得原料为100个单位个单位,工时为工时为120个单位。每生产一台个单位。每生产一台A与与B分别可得利润分别可得利润6元与元与4元。应当安排生产元。应当安排生产A、B各多少台各多少台,才能获得最才能获得最大得利润？大得利润？标准化后标准化后MATLAB求解求解四、二次规划问题四、二次规划问题其中其中quadprog(H,f,A,b,Aeq,beq,Lb,Ub)f=-2;-6;H=1-1;-1 2;A=1 1;-1 2;2 1;b=2;2;2;Lb=0;0;x=quadprog(H,f,A,b,Lb)Optimization terminated successfully、x=0、4000 1、2000习题习题:用用Matlab求解下列优化问题求解下列优化问题222 2 约束最优化方法概述约束最优化方法概述 在工程实际中,所有设计问题几乎都就是约束非线性规划问题。目前对于约束非线性最优化问题得解法较多,可以分为两大类。直接法:用原来得目标函数限定在可行域内进行搜索,且在搜索得过程中一步步得降低目标函数值,直到求出在可行域内得一个最优解。主要方法有:有约束变量轮换法、随机试验法、随机方向搜索法、复合形法、可行方向法等。间接法:将约束最优化问题通过变换,转成为无约束最优化问题,然后再用无约束最优化方法来求得最优解。主要方法有:消元法、拉格朗日乘子法、罚函数法等。目前约束最优化问题得算法收敛速度得判断比无约束最优化问题困难,约束最优化问题得研究与进展情况远不如无约束最优化问题。在本章将主要介绍随机方向搜索法、复合形法、罚函数法。222 2 约束随机方向搜索法约束随机方向搜索法 约束随机方向搜索法就是解决小型约束最优化问题得一种较为有效得直接求解方法。约束随机方向搜索法就是一种数值迭代解法,其基本思想可用二维最优化问题来进行说明。等值线等值线等值线等值线等值线等值线等值等值线线等值等值线线等值等值线线随机方向搜索法计算框图随机方向搜索法计算框图随机方向搜索法计算框图随机方向搜索法计算框图(续续)一维搜索过程一维搜索过程例、用随机方向法求解下列优化问题例、用随机方向法求解下列优化问题取取迭代迭代13次次,求得求得kx1x2f(x)0-2、02、06、01-0、1681、1171、1964-0、0331、0241、02510-0、077-2、998-2、99813-0、00247-3、0-3、0迭代过程显示迭代过程显示一维搜索说明一维搜索说明简单过程简单过程搜索方向搜索方向 x1x201234不可行点不可行点 223 3 复合形法复合形法x1x2K=3K=4n=2K=6K=4n=3x1x2x3复合形法计算框图复合形法计算框图复合形法计算框图复合形法计算框图(续续)复合形法计算框图复合形法计算框图(续续)次数复合形顶点及目标函数值迭代终止判别值初始12270、015955280、009021224 4 罚函数法罚函数法一系列无约束优化问题得解一系列无约束优化问题得解逼近原问题得最优解逼近原问题得最优解对罚函数得进一步说明对罚函数得进一步说明总结求解过程总结求解过程化成标准形式化成标准形式外点法外点法:罚函数得无约束最优解在可行域外部。罚函数得无约束最优解在可行域外部。外点罚函数法计算框图理论最优解理论最优解X*数值最优解数值最优解X*外点法外点法内点罚函数法计算框图内点罚函数法计算框图内点形式得混合罚函数法内点形式得混合罚函数法可直接令可直接令注注:初始迭代点应在严格满足不等式约束得区域内。初始迭代点应在严格满足不等式约束得区域内。*2*25 MATLAB5 MATLAB求解非线性规划问题求解非线性规划问题与应用实例与应用实例考虑如下约束优化问题考虑如下约束优化问题A线性不等式约束得系数矩阵线性不等式约束得系数矩阵b 线性不等式约束得右端向量线性不等式约束得右端向量Aeq线性等式约束得系数矩阵线性等式约束得系数矩阵beq线性等式约束得右端向量线性等式约束得右端向量C(X)与与 Ceq(X)就是非线性约束就是非线性约束函数返回得向量。函数返回得向量。Lb与与Ub就是变量得上下限。就是变量得上下限。x=fmincon(fun,x0,A,b,Aeq,beq,Lb,Ub,nonlcon)求解上述约束优化问题求解上述约束优化问题得得MATLAB函数函数非线性约束函数非线性约束函数,需要定义外部函数需要定义外部函数,计算并返回计算并返回C(X)与与Ceq(X)向量向量例例其中其中x=fmincon(fun,x0,A,b,Aeq,beq,Lb,Ub,nonlcon)在在Matlab命令窗口中输入命令窗口中输入A=-1-2-2;1 2 3;b=0;72;x0=10;10;10;x,fval=fmincon(-x(1)*x(2)*x(3),x0,A,b)结果结果:x*=24,12,8T fval=-2、3040e+003例例定义两个外部函数定义两个外部函数,分别计算目标函数值与约束函分别计算目标函数值与约束函数值。数值。约束函数化成标准形式约束函数化成标准形式目标函数与约束函数均为非线性目标函数与约束函数均为非线性function C,Ceq=fcon(x)g1=1、5+x(1)*x(2)-x(1)-x(2);g2=-x(1)*x(2)-10;C=g1;g2;Ceq=;function y=fobj(x)y=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);x=fmincon(fun,x0,A,b,Aeq,beq,Lb,Ub,nonlcon)x,fevl=fmincon(fobj,x0,fcon)得解得解:x*=-9、5474,1、0474T,f(x*)=0、0236x=fmincon(fun,x0,A,b,Aeq,beq,Lb,Ub,nonlcon)例例与前题得区别与前题得区别:多了一个等式约束。多了一个等式约束。function C,Ceq=fcon(x)g1=1、5+x(1)*x(2)-x(1)-x(2);g2=-x(1)*x(2)-10;C=g1;g2;Ceq=-x(1)2+x(2);function y=fobj(x)y=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);x,fevl=fmincon(fobj,x0,fcon)得解得解:x*=-1、1121,1、2367T,f(x*)=1、9660 C,Ceq=fcon(x)C=0 -8、6246Ceq=0最优解满足等式约束最优解满足等式约束,且在第一个不等式约束得边界上。且在第一个不等式约束得边界上。例例 与前题得区别与前题得区别:多了设计变量下限得约束。多了设计变量下限得约束。计算目标函数与非线性约束函数值得外部函数不变。计算目标函数与非线性约束函数值得外部函数不变。x,fevl=fmincon(fobj,x0,Lb,fcon)Lb=-2;2;得解得解:最优解最优解 x*=-1、4142,2、000T 最优值最优值 f(x*)=2、3549x,feval=fmincon(fobj,x0,Lb,fcon)轮式车辆前轮转向梯形四杆机构得优化设计轮式车辆前轮转向梯形四杆机构得优化设计后轮（驱动）后轮（驱动）前轮（转向）前轮（转向）直直线线行行驶驶梯形转向机构梯形转向机构一般轮式车辆多为后轮驱动一般轮式车辆多为后轮驱动,前轮导向。前轮导向。工程实例工程实例转向中心转向中心O当车辆绕转向中心当车辆绕转向中心O作等角速转向时作等角速转向时,要求全部车要求全部车轮作无侧向滑动得纯滚动。轮作无侧向滑动得纯滚动。转向臂转向臂0转向臂转向臂连杆连杆固连在一起，绕铰点转动固连在一起，绕铰点转动0梯形机构形状改变梯形机构形状改变,实现转向实现转向转向中心转向中心O M L与分别为外导向轮、内导向轮轮轴线之偏转角。若取若取为自变量为自变量,则则可由上式解出可由上式解出 M问题描述问题描述:设计一梯形转向机构,当在一定范围内变动(030)时,能按式(1)变化转向臂转向臂0转向臂转向臂连杆连杆0l1l2l3M取l1与0为设计参数,则 l2不再独立给定给定,p为多少？为多少？根据连杆长度根据连杆长度l2不变来不变来解出。解出。p0p0外转向臂与水平轴得夹角内外转向臂与水平轴得夹角13根据连杆长度根据连杆长度l2不变来解出不变来解出p013希望得结果希望得结果p013l130E030E p?若将得变化范围分布很多等分点,如30个等分点30E0?要求在这些等分点上要求在这些等分点上,p与与E得差值小得差值小,于就是于就是,可可构造下面得函数构造下面得函数0l1l2l3M受到得限制条件受到得限制条件Ll1M0.6L0受到得限制条件受到得限制条件M0+30l1l1l2ed总结总结l1M0.6L0L以以212吉普车数据为例吉普车数据为例:M148cm,L296cm其中目标函数得计算重新改写为其中目标函数得计算重新改写为