机械优化设计习题参考答案 第五版

#5.特点作业：1min-f(x)=x2+25x212x二(2,2)作业：1min-f(x)=x2+25x212x二(2,2)T0121212x二(0,0)T0(六)变尺度法1.引言坐标变换-二次函数f(x')=x'tGx'+bTx+c2令x'=QxQ为尺度变换矩阵-x'tGx'=丄xtQtGQx^2^2因h为正定对称矩阵，存在Q，使得QtGQ二IQQtG二1；QQt=G-1二H尺度矩阵变尺度矩阵的建立•牛顿法

x=x-aG-igk+1kkkkx二x-aHgk+1kkkkH沁G-1--不用求逆得到，在迭代中逐步趋近。kkEk--校正矩阵Ek--校正矩阵H=H+E。k+1kk满足拟牛顿条件G-G-1(g—g)=xk+1kk+1H(g—g)H(g—g)k+1k+1k迭代公式xk+1Hy二sk+1kky二g—g；kk+1kk+y二g—g；kk+1kk+1TgTH二IT00-a0gTH=H+ETx110023.框图p774.DFP(Davidon—Fletcher--Powell)算法E=auut+pvVt--待定

kkkkkkk代入拟牛顿条件(auUt+pvVt).ykkkkkkk二s—HykkkauUT.y+pvVT.y=s一Hykkkkkkkkkkk因为待定，可取auUT.y=skkkkkPvVt.y二—Hykkkkkk又因UT.y，-VT.y是数量，可取

kkkku二s；v二Hykkkkkkks.STHy.yTH得E=_——^-kkkkst.yyTHykkkkk例题p78BFGS法p80统一公式u=aks+akHyk11k12kkv=aks+akHyk21k22kkE=SUT+HyVTkkkkkk6.框图

1.共轭方向的生成（八）1.共轭方向的生成（八）Powell方法•二次函数xtHx+btx+c2从不同两点沿同一方向d得到两极小点x,x，则连线方向d为共轭方向。k因dT•g=0，dT•g=0，贝ydT•（g-g）=0TOC\o"1-5"\h\zjkjk+1jk+1k因g=Hx+b,g=Hx+bkkk+1k+1则（g—g）二h（x—x）,k+1kk+1kdt•（g一g）=dt•H（x一x）=0jk+1kjk+1k2.基本算法1）二维问题x0T坐标轮换法e,eTxo,xoT沿新方向d=xo—x0Tx1T012121200沿eT得x1T沿共轭方向dTx1T沿共轭方向d=x1一x1Tx*21122202）多维问题（自做）改进算法每轮产生的新沿共轭向量代替原向量中最坏的向量。框图p85算例p86s2JX0（九）单形替换法1.原理单（纯）形一n+1个顶点构成的封闭图形。二维问题设f（和〉f（口〉f（①）中点X422),反射点中点X422),反射点(X4-X)=2X14D扩张若f(X5)<f(X3)=X+a=X+a(X44X),1a=1.2T2.0若f（X6）＜f（X3），保留X6。f(X)〉f(X)〉f(X)保留X。TOC\o"1-5"\h\z26352)收缩若f(X)〉f(X)〉f(X)152=X+B(X—X),54f(X1)〉f(X7)保留X7否则3）缩边2.多元函数1)2)3)4)5)6)7)),3x10选初始单纯形(i=0,1,2,・・・n)二f6)i计算各顶点值fi比较得f二maxGi丰H检查精度计算重心xn+1扩张收缩外缩内缩反射点不动:xn+3n+3x二2x—xn+2n+1Hn+2<fG二xn+1+a(xn+2—x)n+1xn+1+0(xn+2n+1—x)否则x+0(x—x)n+1Hn+18)缩边x=-(x+x)i2iL3.框图4.算例5.特点总结：无约束优化方法只算函数值方法坐标轮换法：小规模，收敛慢(无耦合问题快)单形替换法：中小规模，收敛较快；格点法：非凸问题；MonteCarlo法：非凸问题。计算一阶导数方法梯度法：中小规模，开始快；共轭梯度法：中大规模，收敛快，程序简单；变尺度法：中大规模，收敛快；Powell方法：中大规模，收敛快。计算二阶导数方法Newton方法：收敛快，计算难度大；共轭方向法：收敛快，计算难度大。五线性规划(一)标准形式1.示例max.f(x)=60x+120x利润129x+4x<360材料约束123x+10x<300__工时约束124x+5x<200--一电力约束12x,x>0选值约束12标准化：最小，等式，选值非负。min.f(x)=-60x一120x129x+4x+x=360TOC\o"1-5"\h\z123x+10x+0+x=300124x+5x+0+0+x=200125x>0,.(i=1,2,3,4,5)i2.线性规划的标准模型•设计变量x=(x,x,…,x)12n•目标函数min•f(x)=cTx•约束方程s.t.Ax=b(b>0)，(n>m)mxnnx1mx1非标准问题转为标准问题max.f(x)s.t._g(x)<0,引入松弛变量x，有g(x)+x二0,T(x>0)n+1n+1n+1s.t._g(x)>0，引入松弛变量x，有g(x)-x二0,T(x>0)n+1n+1n+1非零约束x>h，引入新变量x'=x—h代替它jjjjj5)x可正可负，另x=x'-x"，x'>0,x">0。jjjjjj4.图解p96基本解一m个方程，n个未知数，得不定解。可设m-n个未知数为0,得到的解称基本解。个数为n!Cm=Cn-m=—nnm!x(n-m)!可行域一约束允许的区域。基本可行解一满足非负要求的基本解。它是可行域的顶点。(二)基本可行解的转换1.基本可行解的形成•Gauss消去法a11a21a12a22•…a1n•…a2nVx1x2=\b]1b：2>aa•…axbm1m2mnmm转轴运算例2a幕a'…...0...…a'11121na'a'…a':21222n::0:a'a'1a'.i1l2lklna'a'0a'm1m2mn其中xma第l行a'=j,ljabb'上llklkaa'二a-aj,ijijikalkr、x1b'1xb':2:2<>=<>xb'kk（j=1,2,…，n）bb'=b———（i丰l,.j=1,2,…,n）iialk5x+4x+13x—2x+x=2012345..x—..x+.5x..—...x+x12345=8*x2不是基本可行解(因系数是负的);「x5是基本可行解’但不一定是最优解。2.基本可行解的转换已选好一组基本变量(x,x,…x),想转换到另12mxx…x…xx…x…12lmm+1k10…0…0a；,1,m+1…a'…1k01…0…0a'…a'…••••2,m+12k00…1…0a'…a'…••••l,m+1lk00…0…1a'…a'…m,m+1mk，有s•a'>0时才能做转轴元素;lk•将x（入基）代替x（出基）后得klx=0>0kx=b'—a'0>0，（i=1,2,…,l，…,m）iiik因xl是出基元素，应有min.x=b'一a'0=0

lllkb'

—i

a'=0=xk得minle法则一取l行中口里最小的定为入基元素x。k3.初始基本可行解的求法—令松弛变量等于右端项，其余为零(三)单纯形法1.从基本可行解最后转换到最优解对一组基本可行解，有f(x)=ctx=£cb'lll=1转换到另一基本可行解后，得x'、b'-a'01iikxb'-a'0.222k=>xb'-a'0iiikx0kj丿对应的目标函数为f(X)=区c(b'-a')+0+c0+0=迓cb'-迓iiikkii=1i=1ca'0+c0llkkl=1i丰kf(a)=区ca'kllkl=1i丰kf(x)=f(x)+・k一f"=f(x)+r0r=ck一f(ak)--相对价值系数要求f(x)下降(越多越好)，希望r为负(越小越好),minC一f(aJ=c一f(a)jjkkj2.单纯形法两规则•9规则一基本可行解转换规则b'——a'lka'>0lk•最速下降规则minCjjminl=Xk-f(aj)Lck-f(役)3.4.3.4.min.f(x)二cTxst.AX=bAX=*Emxnnx1mxmFmx(n-m)EX+FX=bE或X+E-1FXEF=E-1bTX二一E-iFXEF+E-ib对于基本可行解，有XX=E-ib>0E目标函数f(X)=Ctx=!ctCtJ_E|=Ctx+CtXEFIXIEEFEF=CT(E-1b—E-1FX)+CTXEIFFlFFF=CtE-ib-CE-1F-CttXFFE六非线性规划（约束优化）（一）引言1.约束规划问题min.f(X)(j=1,2,,m)h(x)=0(k=1,2,…,l)k2.方法a.直接方法b.间接方法(二)数学基础消元法(降维法)--等式约束2.Lagrange乘子法—等式约束min.f(x)h(x)=0(k=1,2,…,l)k新目标函数min.F(x,兀)=f(x)+兀t•h=f(x)+£九h(x)kkk=1极值条件dF,=0,(i=1,2,…,n)oxioF=0,(k=1,2,…,l)--i个约束方程0九k说明：因为满足l个约束方程，此时F(x,厂)=f(x)，则极值相同。例题：p39,1483.Kuhn—Tucker条件问题min.f(x)=0s.t._g.(x)<0(j=1,2,…,m)jKuhn—Tucker条件说明引入松弛因子g(x)+x2=0(j=1,2,…,m)jn+jmin.F(x,x,圧)=f(x)+£卩[g(x)+x2]jjn+jj=1求极值dFdxif+im免二odxdxij=1i=2卩x=0dxjn+jn+j=g(x)+x2=0dyjn+jj(3)—满足约束方程；(i=1,2,…,n)(j=1,2,…,m)(j=1,2,…，m)(1)(2)(3)(2)--y丰0-》x=0—>gjn+jj

(x)=0T极值点在边界上;y=0Tx丰0Tg(x)<0T极值点不在边界上，在可行域内，可作jn+jj为无约束问题处理。(1)可写为Vf(元)+区yVg(x)=0--表示各梯度向量和“平衡”jji=j或—Vf(x)=^yVg(x)jji=j可以证明，y>0jKuhn—Tucker条件定义：J—起作用的约束的集合。df(x*df(x*)

dxi+YyjwJdg(x*)/=0

dxiy>0j(i=1,2,…,n)(jeJ)Vf(x*)+YVg(x*)=0jjeJy>0j证明：图例题p45

1.内点法惩罚函数(三)1.内点法惩罚函数(三)惩罚函数法(penaltyfunctionmethod)min.f(x)s.t..g(x)<O(j二1,2,,m)jJlj=1r一惩罚因子，有r>r>rT0012惩罚项一函数永远在可行域内，越靠近边界，惩罚值越大，保证不能越过边界。例：min.f(x)=x2+x212解:0(x,r)=x2+x2一rln(x一1)2.外点法2.外点法惩罚函数0(x,r)=f(x)+£maxj=1惩罚因子r<r<rTg012例：前例0(元,r)=x12+号+r(1-x1)2

3.混合法min.f(x)问题s.t..g(x)<O(j=1,2,…,m)h(x)=0(k=1,2,…,l)k惩罚函数0(x,r)=f(x)-g(x)Jrkj=1jk=1例：求球A和圆柱B的最小距离。已知Ax2+x2+x2<5123B(x-3》+x2<14<x<8TOC\o"1-5"\h\z456数学模型min.f(x)=(x-x\+(x-x\+(x-x142536s.t.g=x2+x2+x2-5<0123g=(x-3》+x2-1<045g=x-8<036g=4-x<046用内点法或混合法，取r=1T0,x=C1,1,3丄5》00直接方法（一）随机方向法在可行域产生一个初始点x，因a<x<b（约束），贝y0iiix=a+q（b一a）i=1,2,—,n0iiiiiq--（0，1）的随机数。i找k个随机方向，每个方向有n个方向余弦，要产生kn个随机数r,i=1,2,…,n，ijj=1,2,…,k，随机方向的单位向量为i=1r2

i=1r2

ijC,r，…,r1j2jnjj=1,2,…,k取一试验步长a，计算每个方向的最优点0X=x+aej=1,2,—,kj100j找出可行域中的最好点X得搜索方向d=X-X。以X为起点，d为搜索方向得X。LL0L1最优点必须在可行域内或边界上，为此要逐步增加步长。方法框图p126（二）复合形法复合形--k＞n+1个顶点构成的封闭图形，它是由若干个单纯形组成的。初始复合形的产生在可行域内产生k个随机点X=a+rTG-a)j=1,2,—,kjj若可行域为凸集，则k个顶点在可行域内。否则内缩pl28。3.搜索•计算各顶点目标函数，得f(X)=minf(X)Ljf(X)=maxf(X)Hjf(X)=maxf(X)Ljj丰H计算重心zXk—1jj=1j丰H反射点=X+a(X-X)ccHf(X)>f(X)>f(X)--不动GRLf(X)<f(X)--扩张X=X+Y(X-X)LERRcf即＜f9）＜f6L收缩（内缩、外缩）X=X+0(XkH缩边=X—缩边=X—0.50—X)LLj（三）可行方向法可行方向一约束允许的、函数减小的方向。（图）约束边界的切线与函数等高线的切线方向形成的区域。1．搜索策略：初始点沿负梯度方向；好点在可行域内，选之；好点在可行域外，缩至边界；在边界沿可行方向。多目标优化方法1.引言•汽车设计：速度快，耗油少，成本低，结构轻，舒适性好（振动、噪声）•主目标法，统一目标法。2.主目标法min.f(x)i=1,2,,li选第k个为主目标，有min.f(x)kf<f(x)<fi丰ki,minii,max3.统一目标法•线性加权法minF(x)=工wf(x)miniii=1iii,s理想点法设f分目标乘除法为f.（x）的单目标优化点，则有分目标乘除法iiminU(x)=1［牛-2或加权minU(x)=工w(f(x)一f或加权iiii=1

minf(x)i=1,2,…,limaxf.6)j二1,2,…,kjRf(x)minU(x)=RfG)jj=1专题：动态规划引言多阶段决策问题，1951年R.Bellman提出最优性原理；重点：离散确定性问题。目标：在每个阶段采取合适的策略，使整个过程最优。例最优路线问题例：图11.1由A到B有20条路线，走那条最省？枚举法：计算100次加法，19次比较。动态规划举例图11图11」巔优路线冋题末一级：IO=2,.・I=1p末二级：I末二级：Il=min+1O8+1p」末三级：I=3+1=10；IHL

+1I=minl=8:i4+1I=minJ2+1m=62+1N末四级：IE=min2+1H1+I=minJ2+1m=62+1N末四级：IE=min2+1H1+1II=minF1+11=82+1JI=minG+1J=11+1K末五级：I=minC5+1E=12:4+1FI=minD7+1f=143+1G末六级：I=minA1+1C=130+1D动态规划：24次加法，9次比较。最优原理从A到C的最优轨线是ABC(I+11),则从该轨线上任一点B到C的最优轨线II是原轨线BC。证明：如果存在最优轨线II,则I+II，是A到C的最优轨线，与前提矛盾。动态规划递推公式时间离散系统的系统方程x(k+1)=f[x(k),u(k),k]x(0)=x0其中x--n维状态向量；u(k)--m维控制向量；k--时间变量或阶段变量。性能指标(目标函数)：JN=£Ck[x(k)，u(k)，k]k=0C--第k阶段的性能指标(泛函)，或代价函数k定义：.k[x(k)，k]--由k级达到末级(N)的最小性能指标(泛函)。I[x(k)k]=minN-kIjj=k分解得动态规划递推公式I[x(k),k]=minC[x(k),k]+1[x(k+1),k+1]}N-kkN-(k+1)通常从末级开始，有u(N)=0则I[x（N）,N]C[x（N）,N]0N遗传算法简介近年来，发展了一种模拟生物进化的优化方法，称为“遗传算法（Geneticalgorithm—GA）”。它是在1975年由美国教授J.Holland提出的一种人工智能方法，是在计算机上按生物进化过程进行模拟的一种搜索寻优算法。我们在介绍随机方向法时，提到了可以通过计算机产生的一个随机数列做为一个可行的初始方向（一个向量），然后按一定条件在搜索空间内对函数进行寻优。类似地，按照遗传算法的思路，它是把函数的搜索空间看成是一个映射的遗传空间，而在此空间进行寻优搜索的可行解看成是由一个向量染色体（个体）组成的集合（群体）。染色体（chromosome）是由基因（gene）（元素）组成的向量。在遗传算法中，目标函数被转化成对应各个个体的适应度（fitness）,适应度是根据预定的目标函数对每个个体（染色体）进行评价的一个表述，可用F表示，它反映个体对目标适应的概率。相应的第i个个体的适应度用F表示，它可用来表示各个个体的适应性能，i并据此指导寻优搜索。F值越大，说明其性能越好。计算开始时，就是要从随机产生的一系i列染色体（个体）中选择那些适应度高（性能好）的染色体（个体）组成初始的寻优群体（初始可行解），称为“种群”（reproduction）。遗传算法先把优化问题的一组基本可行解（染色体）用二进制（或十进制）的字符串进行编码，例如二进制的字符串001101和100111就可分别表示两个染色体。其中的一位或几位字符的组合称为一个基因（元素）。这两个染色体就可表示二维遗传空间的两个可行解,可作为二维遗传空间中的一个寻优的初始点（种群）。当然，维数越高，要求遗传空间内染色体的群体个数越多，即和它的维数相对应。而且，遗传空间内的可行解会有多种组合，它们组成了可行解的空间。改变染色体中某个基因所处的位置，例如，把001101和100111中的后三位字符（基因组）进行交换，即得001111和100101的另外两个染色体（可行解），它可以作为遗传空间中的一组新的寻优试探点。这种基因交换称为“杂交”或“交叉”（crossover），它体现了自然界信息交换的思想。通过这样不断杂交和不断选择适应度好的染色体的过程,可以实现从一个染色体种群（可行解）向另一个更优的种群的转换。或者说，通过杂交可以使一个染色体种群向另一个比上一代更优秀的种群（可行解）进化。从而可以实现在遗传空间内进行大范围的寻优，直到满意终止为止。当然，我们这里所列的两个字符串001101和100111所代表的染色体，需要从计算机产生的随机数列进行选择,择其优秀者组成寻优的初始点。这一步称为“选择”（selection）。…为了提高遗传算法搜索全局最优解的能力，还须扩大基因组合，这就是“变异”（mutation）。变异过程是对某一染色体字符串的某个基因在繁殖过程中实现1-0或0-1的转变，以确保染色体群体中遗传基因的多样性，保证搜索能在尽可能大的空间中进行，避免丢失搜索中有用的遗传信息而导致“过早收敛”，陷入局部解，从而提高优化解的质量。通过上面的简单介绍，可知遗传算法是由：选择、杂交和变异三个过程组成的。还可以看出，遗传算法和前述多种优化方法的区别在于：遗传算法是多点搜索，而不是单点寻优；遗传算法直接利用从目标函数转化成的适应函数，而不采用导数等信息；遗传算法采用编码方法而不是参数本身；遗传算法是以概率原则指导搜索，而不是确定性的转化原则。

目前，遗传算法还存在一些问题，主要是计算时要求种群规模较大（一般为50—100），耗费机时太多，难以解决大型结构优化问题，一般多用于系统优化问题。其次是在求解过程中，有时会发生过早收敛于局部最优解。为此需对选择、杂交和变异三个过程进行仔细分析研究。具体算法请参阅相关文献资料。群体(population)f竞争淘汰(competition)f种群(reproduction)f婚配(crossoverf子群(subpopulation)f变异(mutation)f新群体…个体（individual）—解（设计方案）；染色体（chromosome）—解的编码（字符串，向量）；基因（gene）—解的一个分量，可用染色体的一个或几个元素来表示。适应度（fitness）—适应函数值（与目标有关）。例1：求f(x)二x2,.O<x<31,x为最大整数的解。解：初始种群(随机)x=(00000)t0,x=(11001)t