第2章优化设计第二部分_约束最优化方法(补充全20111203)

*a.约束随机方向搜索法b.复合形法c.罚函数法(1)外点罚函数法(2)内点罚函数法等*1、线性规划与二次规划问题2、一般非线性规划第二章Part2优化设计（补充全）一、线性规划引例：某车间生产A和B两种产品。为了生产A和B，所需的原料分别为每台2与3个单位，所需工时分别为每台4和2个单位。现在可以应用的原料为100个单位，工时为120个单位。每生产一台A和B分别可得利润6元和4元。应当安排生产A、B各多少台，才能获得最大的利润？解：设A、B产品的台数各生产x1,x2台。目标函数－利润函数12Z=64xx限制条件：12121223100421200xxxxxx、§2－1线性规划与二次规划问题原问题表述为：12121212max64S.t.23100421200zxxxxxxxx、标准化后：12121212min64S.t.23100421200zxxxxxxxx、线性规划问题－目标函数与约束函数均是线性的线性规划问题相关定理1、线性规划问题的可行域D是凸集。2、若线性规划问题存在最优解，则目标函数的最优值可在某个极点（顶点）达到。12121212min64S.t.23100421200zxxxxxxxx、x1x2Dz减小的方向最优解最优解：x1=x2=20二、线性规划问题的单纯形求解算法介绍1947年提出，后有许多改造，形成许多变种。应用较广，具权威性。现举例说明该算法的基本思想1212121212min4S.t.24231230zxxxxxxxxxx-、例：x1x2z下降的方向123451212121212min4S.t.24231230zxxxxxxxxxx-、极点1－2－3－4？极点1－5－4？极点1－4？思想：从一个基本可行解（极点）出发，求另一个使目标函数值下降的基本可行解…..3451122342512112min4S.t.24231230zxxxxxxxxxxxxxxxx、、、、-引入松弛变量x3、x4、x5，原式化成标准形式1212121212min4S.t.24231230zxxxxxxxxxx-、3451122342512112min4S.t.24231230zxxxxxxxxxxxxxxxx、、、、-TminS.t.0zCxAx=bxT12344TT[][41000][4123]121002301011001xxxxxx=C=b=A=其中Ax=b在中若令其中的两个未知量为零，则剩余的三个可由其解出。12345121002301011001PPPPPA=12345PPPPPA=T12344[,,,,]xxxxxx=1）如另x1=x2=0，则有T345345PPP[4123]Txxx345[4123]xxxx1x212345上面的解是可行解，x1=x2=0对应于点1——基本可行解——基变量2）通过某些判定条件。令x5=x2=0T341341PPP[4123]Txxx341[763]xxx有新的解是可行解，x1=3，x2=0对应于点5——另一基本可行解x1x212345——基变量——非基变量3）通过某些判定条件。令x5=x4=0T321321PPP[4123]Txxx32129621555xxx有x1x212345新的解是可行解，x1=4.2，x2=5.2对应于点5——最优基本解——基变量关键点：每次取三个基变量，根据一些判定条件选择。前后两次迭代的基变量相差一个。极点1－5－4——非基变量一般形式的线性规划问题eqeqminS.t.TbbCxAxbAxbLxU其中三、利用MATLAB求解线性规划问题eq,NnmnAAAATT1212TTeq1212TT1212[,,,],[,,,][,,,],[,,,][,,,],[,,,]nneqeqeqNmbbbbnbbbbnxxxcccbbbbbbLLLUUUCx==b=b=L=U=1212121212min4S.t.24231230zxxxxxxxxxx例-、TT12[,],[4,1]eqeqxx,[][]x=C=AbT-1223,[4123]11A=b=bb[0,0],[]TL=U=1231231212123min3S.t.8222100xxxxxxxxxxxxx例2、、TT123[,,],[1,3,1]xxxx=C=T-2-10,[210]120A=b=bb[000],[]TL=U=eqeq[2-11],8AbeqeqminS.t.TbbCxAxbAxbLxUlinprog(C,A,b,Aeq,beq，Lb,Ub)1231231212123min3S.t.8-222100xxxxxxxxxxxxx例2、、C=[1;-3;1];Aeq=[2-11];beq=8;A=[-2-10;120];b=[-2;10];Lb=[0;0;0];x=linprog(C,A,b,Aeq,beq,Lb,[])Optimizationterminatedsuccessfully.x=0.80824.595910.97941212121212min4S.t.24231230xxxxxxxxxx例-、TT12[,],[4,1]eqeqxx,[][]x=C=AbT-1223,[4123]11A=b=bb[0,]0],[TL=U=C=[-4;-1];A=[-12231-1]b=[4;12;3];Lb=[0;0];x=linprog(C,A,b,[],[],Lb,[])Optimizationterminatedsuccessfully.x=4.20001.2000引例：某车间生产A和B两种产品。为了生产A和B，所需的原料分别为每台2与3个单位，所需工时分别为每台4和2个单位。现在可以应用的原料为100个单位，工时为120个单位。每生产一台A和B分别可得利润6元和4元。应当安排生产A、B各多少台，才能获得最大的利润？12121212min64S.t.23100421200zxxxxxxxx、标准化后MATLAB求解1220.0000xx四、二次规划问题TTeqeq1min2S.t.bbxx+fxHAxbAxbLxUTT1212TTeq1212TT1212[,,,],[,,,][,,,],[,,,][,,,],[,,,]nneqeqeqNmbbbbnbbbbnxxxcccbbbbbbLLLUUUfx==b=b=L=U=其中eq,nnNnmnH=H,AAAA11122212121211111min26122S.t.222220xxxxxxxxxxxxxx例、-Tb26,[222]1111,12122100,=[],=[]TTeqeqHAAbfbLquadprog(H,f,A,b,Aeq,beq，Lb,Ub)TTeqeq1min2S.t.bbxx+fxHAxbAxbLxU11122212121211111min26122S.t.222220xxxxxxxxxxxxxx例、-f=[-2;-6];H=[1-1;-12];A=[11;-12;21];b=[2;2;2];Lb=[0;0];x=quadprog(H,f,A,b,[],[],Lb)Optimizationterminatedsuccessfully.x=0.40001.200022121121211min44S.t.+20100xxxxxxxxx、习题：用Matlab求解下列优化问题123123123123min542S.t.6+82+41031200xxxxxxxxxxxx-123n012=012****[,,,],()(,,,)()(,,,),min()min()(),()nuvXxxxxgXumhXvpfXXfXfXXfX约束最优化问题：求维设计变量受约束于，使目标函数为；如果存在，使得＝则称为最优点，为最优值。§2－2约束最优化方法概述在工程实际中，所有设计问题几乎都是约束非线性规划问题。目前对于约束非线性最优化问题的解法较多，可以分为两大类。直接法：用原来的目标函数限定在可行域内进行搜索，且在搜索的过程中一步步的降低目标函数值，直到求出在可行域内的一个最优解。主要方法有：有约束变量轮换法、随机试验法、随机方向搜索法、复合形法、可行方向法等。间接法：将约束最优化问题通过变换，转成为无约束最优化问题，然后再用无约束最优化方法来求得最优解。主要方法有：消元法、拉格朗日乘子法、罚函数法等。目前约束最优化问题的算法收敛速度的判断比无约束最优化问题困难，约束最优化问题的研究和进展情况远不如无约束最优化问题。在本章将主要介绍随机方向搜索法、复合形法、罚函数法。§2－2约束随机方向搜索法一、基本原理约束随机方向搜索法是解决小型约束最优化问题的一种较为有效的直接求解方法。约束随机方向搜索法是一种数值迭代解法，其基本思想可用二维最优化问题来进行说明。约束随机搜索方向法的几何图0()XAC1()SDB1()X2()S2()X3()X*X等值线等值线等值线000101012D()()()()())(()(()()XSXXSfXfXXXDXXSS任意选择一个初始点随机方向取得探索点=+同时符合（即在约束可行域内，（1）、；（）以给定的初始步长沿着某种方法产生的，（3）若该点，则表示点探索成功。并把它作为新的探索起始点，继续按上面的迭代公式在方向上获取新的探索成功点。重复上述步骤下降性可行性，迭代和要求点可沿（）111)()()SX方向前进，直至到达某搜索点不能同时符合下降性和可行性要求时停止。此时废弃该搜索点，并退回到前一个搜索成功点作为作为方向搜索中的最终成功点，记为。01ACBD()()XX若在初始点或某个换向转折点处（如图中的点），沿某随机方向的探索点目标函数值增大（如图中的点、点）或者越出可行域（如点、点），则应相应弃掉该随机方向，重新产生另一随机方向作为进行搜索。搜索成功继续前进，搜索失败再重新产生随机方向。D0()XAC1()SDB1()X2()S2()X3()X*X等值线等值线等值线23505()()XXmaxmaxmax若在某个换向转折点处（如图中的点），沿N个随机方向以步长进行搜索均失败，可以反映以此点为中心，为半径的圆周上各点都难以同时满足下降性和可行性条件。此时，可将搜索步长减半后继续试探，直到已缩减到预定的精度以下，且沿N个随机方向都搜索失败时，则以最后一个成功点（如图中的点作为达到预定精度要求的的约束最优点，结束迭代。N一般可取为至00，对目标函数性态不好的应取较大的值，以提高解题的成功率。二、初始点的选择001212()()(,,,)DuXgXum随机方向搜索法的初始点必须是一个可行点，即必须满足所有的约束条件，确定这一点通常有两种方法：（）即在设计的可行域内，人为的确定一个可行的初始点。（约束条件较为简单时，人为给定随机选定通常这样处理）（）0()X即利用计算机产生的伪随机数来选择一个可行的初始点。12111222121201111102222200012i010101(i=12()()()()()[,],,()()[,]TTXxxax