《机械优化设计（第7版）》课件 孙靖民 第5章线性规划；第6章约束优化方法；第7章多目标及离散变量优化

机械优化设计第五章线性规划×第一节线性规划的标准形式与基本性质§第二节基本可行解的转换§第三节单纯形方法§

第五章线性规划

第四节单纯形法应用举例§第五节修正单纯形法§

目标函数和约束条件都是线性的，像这类约束函数和目标函数都是为线性函数的优化问题，称作线性规划问题。它的解法在理论和方法上都很成熟，实际应用也很广泛。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。

第五章线性规划

解：设生产A、B两产品分别为x1,x2台，则该问题的优化数学模型为：例5-1：某工厂要生产A、B两种产品，每生产一台产品A可获产值2万元；需占用一车间工作日3天，二车间工作日6天；每生产一台产品B可获产值1万元；需占用一车间工作日5天，二车间工作日2天。现一车间可用于生产A、B产品的时间15天，二车间可用于生产A、B产品的时间24天。试求出生产组织者安排A、B两种产品的合理投资产数，以获得最大的总产值。§第一节线性规划的标准形式与基本性质一、线性规划实例例5-2：生产甲种产品每件需使用材料9kg、3个工时、4kw电，获利润60元。生产乙种产品每件需用材料4kg、10个工时、5kw电，可获利120元。若每天能供应材料360kg，有300个工时，能供200kw电。试确定两种产品每天的产量，使每天可能获得的利润最大？

分析：每天生产的甲、乙两种产品分别为件（工时约束）（电力约束）（材料约束）(利润最大)将其化成线性规划标准形式：求使且满足例5-3：某厂生产甲、乙两种产品，已知：①两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；②该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；③产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？日利润最大生产能力限制劳动力限制变量非负解:

设甲、乙两种产品的日产件数分别为s.t.建模例1：某公司有钢材、铝材、铜材1200t，800t和650t，拟调往物资紧张的地区甲、乙、丙。已知甲、乙、丙对上述物资的总需求分别为：900t，800t和1000t。各种物资在各地销售每吨的获利如下表所示。试问公司应如何安排调运计划，才能获利最大？建立该问题的数学模型。钢材铝材铜材甲260300400乙210250550丙180400350物资获利地区建模例2：某工厂生产A、B、C三种产品，现根据订货合同以及生产状况制定5月份的生产计划，已知合同甲为：A产品1000件，单件价格为500元，违约金为100元/件；合同乙为：B产品500件，单件价格为400元，违约金为120元/件；合同丙为：B产品600件，单件价格为420元，违约金为130元/件；C产品600件，单件价格为400元，违约金为90元/件；有关各产品生产过程所需工时以及原材料的情况见下表。试以利润为目标，建立该工厂的生产计划线性规划模型。工序1工序2工序3原材料1原材料2其他成本产品A/件2323410产品B/件1132310产品C/件2124210总工时或原材料460040006000100008000工时或原材料成本（元）1510102040建模例3：成批生产企业年度生产计划的按月分配。在成批生产的机械制造企业中，不同产品劳动量的结构上可能有很大差别。如：某种产品要求较多的车床加工时间，另一种产品的劳动量可能集中在铣床和其他机床上。因此，企业在按月分配年度计划任务时，应考虑到各种设备的均衡且最大负荷。在年度计划按月分配时一般要考虑:1）从数量和品种上保证年度计划的完成；2）成批的产品尽可能在各个月内均衡生产或集中在几个月内生产；3）由于生产技术准备等方面原因，某些产品要在某个月后才能投产；4）根据合同要求，某些产品要求在年初交货；5）批量小的产品尽可能集中在一个月或几个月内生产出来，以便减少各个月的品种数量等等。如何在满足上述条件的基础上，使设备均衡负荷且最大负荷。线性规划数学模型的一般形式：求使且满足说明：1）m=n,唯一解2）m>n,无解3）m<n,无穷解二、线性规划的标准形式将一般形式的线性规划化为标准形式的方法x3为松弛变量约束条件为“

”时：约束条件包括两部分：一是等式约束条件，二是变量的非负要求，它是标准形式中出现的唯一不等式形式x3为剩余变量约束条件为“

”时：(2)变量3x1'-3x1"+2x28x1'

-x1"-4x2

14x1',x1",

x2

01、x

0，令x’＝-x。3x1+2x28x1-4x2

14x202、x取值无约束，令x=x'-x"3x1'-3x1"+2x2+x3=8

x1'

-x1"-4x2+x4=14x1',x1",x2,x3,x40例如：x1'

+x211x1'

16x1',x20（3）x两边有约束的情况。x1+x25-6

x110x20-6+6x1+6

10+6

令x1'

=x1+6

0

x1'

16(4)右端常数右端项b＜0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零。三、线性规划的基本性质图5.1线性规划的几何意义图5.1线性规划的几何意义通过顶点Ｃ的直线满足上述条件，故点Ｃ是该问题的最优解。序号123456变量值x10005415/4x20312003/4x3150-45030x424180-600图5.1中对应的顶点ODEBAC可行域可行解：同时满足所有约束条件的任何一个解x=[x1,x2,…,xn]T。例：多边形OACD域中任意一个解。基本可行解：如果基本解还满足非负条件xj≥0(j=1,2,…,n),则称之为基本可行解（既是基本解，又是可行解）。例：表5-1中列出的4个解(或图6.1对应的4个顶点A、C、D、O)。基本解：令线性规划标准形式中任意(n-m)个变量等于零，若剩余的m个变量构成的m个线性方程有唯一解，则称由此得到的n个变量的解为基本解。例：表5-1中列出的６个解(或图6.1对应的６个顶点A、B、C、D、E、O)。基、基向量、基变量与非基变量基：在系数矩阵A中，选择m列线性无关向量构成m×m阶非奇异子矩阵B,则称B为线性规划的一个基。基向量：组成基B的列向量pj(j=1,2,…,m)。基变量：与基向量对应的变量xj(j=1,2,…,m)。用xB表示。非基变量：除基变量外的其余(n-m)个变量。用xN表示。最优解：使目标函数达到最小值的基本可行解。例：图5.1中的点C为最优解，对应的目标函数值为-33/4.基变量和非基变量是相对于基而言的。线性规划问题的以上几个解的关系，可用下图来描述：基本解共10个,每个基本解中有n-m＝2变量取零值。基本可行解5个线性规划的两个重要性质线性规划可行解的集合构成一个凸集，且这个凸集是凸多面体，它的每一个顶点对应于一个基本可行解，即顶点与基本可行解相当。线性规划的最优解如果存在，必然在凸集的某个顶点（即某个基本可行解）上达到。图5.2线性规划解的特殊情形因此，线性规划的最优解不必在可行域整个区域内搜索，只要在它的有限个基本可行解（顶点）中去寻找即可。

但是，在实际的线性规划问题中，其变量的个数n和约束方程的个数m都是很大的，其基本可行解的数目非常多，即使采用计算机也难以实现；同时，仅仅考察基本可行解，也不能确定问题何时有无界解。故没有必要找出所有的基本可行解以求得最优解，而是采用一定的方法如单纯形法来解决这个问题。一、从一个基本解转到另一个基本解把约束条件展开：§第二节基本可行解的转换采用高斯-约当法(Gauss-Jordan)进行消元：此过程称作对变量xk进行转轴运算，xk称为转轴变量，alk称为转轴元素。选取另一变量作为转轴变量进行第二次转轴运算，并反复此过程，我们将得到：这一方程组称为正则方程组（高斯-亚当消元过程）。从而得到一组基本解(基本解中所有基本变量的全体称为基)：基本变量如果此时继续对上述形式的方程组进行附加的一次转轴运算，例如选取作（(t>m)为转轴元素，此时xt进入基，

xs出基。这样就完成了从一个基本解到另一个基本解的转换解：用a11,

a22作为轴元素进行两次转轴运算：例：给定如下方程组，试进行基本解的转换运算。得到一组基本解：

x1=-12

x2=-20

x3=x4=x5=0用a25作为轴元素进行第三次转轴运算：又得到一组基本可行解：

x1=3

x5=5

x2=x3=x4=0此时x5进入基，x2出基。二、从一个基本可行解转到另一个基本可行解当已经得到一组基本可行解，若要求把xk选进基本变量，并使下一组基本解是可行解的话，则在第k列要选取不为任何负值的元素作为转轴元素alk作为转轴元素进行转轴运算：方程组第一行发生的变化：alk作为轴元素，xk选进基本变量后，xk的取值由零变成了一个正值，则原来各基本变量的取值变为:

若是基本可行解,应该保证各差值最小者为零:决定了离基变量为xi若想用xk取代xl成为可行解中的基本变量，就应该选所对应的行成为转轴行，即所选取的行要满足条件:规则例：基本可行解：

x1=3

x5=5

x2=x3=x4=0基本变量x1、x5

基本可行解的转换：

1）x2、x4系数全部为负，只能选取x3所在的第3列为转轴行

2）,由于，则取第一行为转轴行,

于是取a'13=2为转轴元素，使x3取代x1成为基本变量。经转轴运算得：得基本可行解：

结论：可把松驰变量作为初始基本可行解中的一部分基本变量。三、初始基本可行解的求法原始约束条件:引入松驰变量:可得一组基本可行解：一、单纯形法的基本思想从一个初始基本可行解X0出发，寻找目标函数有较大下降的一个新的基本可行解X1,代替原来的基本可行解X0，如此完成一次迭代。随后作出判断，如果未达到最优解，则继续迭代下去。因为基本可行解的数目有限，所以经过有限次迭代一定能达到最优解。§第三节单纯形方法采用单纯形法求解线性规划问题，主要应解决以下三个问题：（1）如何确定初始基本可行解；（2）如何由一个基本可行解迭代出另一个基本可行解，同时保证目标函数的下降性；（3）如何判断一个基本可行解是否为最优解。二.最优解规则对应一组基本可行解：前m个变量组成基本可行解的基本变量相应的目标函数值为:经过转轴运算得到另一组基本可行解为:其中：进基变量xk出基变量xs对应的目标函数为:由于要求∴结论:一旦所有的,即可停止转轴运算,对应的可行解就是最优解。r是对线性规划问题的解进行最优性检验的标志，称之为检验数。∵∴具体计算时应选取:由于有可能同时有几组都为负值最速变化规则1）最速变化规则决定进基的非基本变量结论：2）规则决定了出基的基本变量3）若对基本可行解X，所有检验数rk≥0，则X为最优解。例5-3某建筑单位拟盖一批二人、三人和四人的宿舍单元，要确定每一种宿舍单元的数目，以获得最大利润。其限制条件如下：1）预算不能超过9000千元。2）宿舍单元总数不得少于350套。3）每类宿舍单元的百分比为：二人的不超过总数的20%，三人的不超过总数的60%，四人的不超过总数的40%（百分比总和超过100，这是上限）。4）建造价格为：二人的宿舍单元是20千元，三人的宿舍单元是25千元，四人的宿舍单元是30千元。5）净利润为：二人的宿舍单元是2千元，三人的宿舍单元是3千元，四人的宿舍单元是4千元。解：略§第四节单纯形法应用举例修正单纯形法的迭代过程如下：§第五节修正单纯形法（1）根据问题的需要，加入松弛变量或人工变量，写出初始基方阵E，求E-1和基本解（2）计算和，对应于非基本变量计算相应的。若所有（对极小化问题），则x为最优解；否则转至步骤（3）。（3）选取进入新的基方阵的，找出，计算。若所有，则无解；否则转至步骤（4）。修正单纯形法的迭代过程如下：§第五节修正单纯形法（4）计算，选取离开基方阵的，形成新的基方阵，转至步骤（5）。（5）计算新的矩阵的逆矩阵和。每迭代一次，就构成一个新的逆矩阵。然后转至步骤（1）重复计算，直到求得最优解和相应的目标函数值（极小值或极大值）。END?机械优化设计第六章约束优化方法×6.1概述6.2随机方向法

6.3复合形方法

6.4可行方向法

6.5惩罚函数法

6.6增广乘子法

6.11遗传算法简述6.10结构优化法简述

6.9二次规划法

6.8广义简约梯度法

6.7非线性规划问题的线性化解法—线性逼近法

机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为§第一节

概述§第一节

概述

直接解法：随机方向搜索法、复合形法、可行方向法

间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法一.有约束问题解法分类：二.直接解法的基本思想：

合理选择初始点，确定搜索方向，在可行域中寻优，经过若干次迭代，收敛至最优点。

xk+1=xk+αkdkdk::

可行搜索方向。即设计点沿该方向作微量移动时,目标函数值将下降,且不会超出可行域直接解法通常适用于仅含不等式约束的问题§第一节

概述特点：①由于求解过程在可行域内进行；无论迭代计算何时终止,都可以获得一个比初始点好的设计点;②若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。凸可行域非凸可行域§第一节

概述原理：将有约束优化问题转化为无约束优化问题来解决。方法：以原目标函数和加权的约束函数共同构成一个新的

目标函数Φ(x,r1,r2)，成为无约束优化问题。通

过不断调整加权因子，产生一系列Φ函数的极小点

序列x(k)*(r1(k),r2(k))k=0,1,2…，逐渐收敛到原目标

函数的约束最优解。其中：新目标函数：三.间接解法的基本思想：

惩罚因子：r1,r2§第二节随机方向法一.基本思想：随机产生初始点，随机产生若干个搜索方向dk，并从中选择一个能使目标函数值下降最快的方向作为可行搜索方向进行搜索。确保：①新迭代点在可行域中②目标函数值的下降性。x(0)x(L)x(1)x*二.初始点的选择

随机方向法的初始点x0必须是一个可行点，既满足全部

不等式约束条件。初始点可以通过随机选择的方法产生。1）输入设计变量的下限值和上限值，即2）在区间（0，1）内产生n个伪随机数3）计算随机点x的各分量4）判别随机点x是否可行，若随机点可行，用x0←x

为初始点；若非可行点，转到步骤2）重新产生随

机点，直到可行为止。§第二节随机方向法三.可行搜索方向的产生从k个随机方向中，选取一个较好的方向。1）在(-1,1)区间内产生伪随机数，得随机单位向量2)取一试验步长a0，按下式计算k个随机点§第二节随机方向法3）检验k个随机点是否为可行点，除去非可行点，计算余下的可行点的目标函数值，比较其大小，选出目标

函数最小的点xL

。4)比较xL

和x0两点的目标函数值:①若f(xL)<f(x0)，则取xL

和x0连线方向为可行搜索方向；

②若f(xL)≥f(x0)，则缩小步长α0

，转步骤1）重新计算，

直至f(xL)<f(x0)为止。③α0

缩小到很小仍然找不到一个xL，使f(xL)<f(x0),则

说明x0是一个局部极小点，更换初始点转步骤1）。§第二节随机方向法产生可行搜索方向的条件为：则可行搜索方向为：四、搜索步长的确定步长由加速步长法确定：τ为步长加速系数，一般取1.3§第二节随机方向法五.计算步骤1)选择一个可行的初始点x0;2)产生k个n维随机单位向量ej(j=1,2,…,k);3)取试验步长

0，计算出k个随机点xj;4)在k个随机点中，找出可行的的随机点xL,产生可行搜索方向d=xL

x0.5)从初始点x0出发，沿可行搜索方向d以步长

进行迭代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点x。6)若收敛条件满足，停止迭代。否则，令x0

x转步骤2例6-1求下列约束优化问题的最优解

解：用随机方向法程序，在计算机上运行，迭代13次，求得约束最优解：x*=[0.00273.0]T,f(x*)=3

迭代次数设计变量x1设计变量x1目标函数值0-2.02.06.01-0.01681.1171.1964-0.0331.0241.0257-0.1140.7170.73010-0.077-2.998-2.99713-0.002-3.0-3.0一.单纯形法：基本思想：以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点，组成新的单纯形，不断地迭代，逐渐逼近最优点。

二维空间中映射法比较单纯形x(1)x(2)x(3)的顶点，f(x(1))>f(x(2))>f(x(3)),

x(1)为最坏点，称为x(H)，通过映射得到新点x(R)，x(R)＝x(S)＋a(x(S)-x(H))以x(R)来代替x(H)，组成新的单纯形x(R)x(2)x(3)。其中f(x(R))<f(x(H));

a>1；称为映射因子；X(1)=X(H)X(2)X(3)X(S)X(R)=X(4)X(5)X(6)定义：在n维空间中，由n+1个点组成的图形称单纯形。X*除x(H)外，其它顶点的几何中心§第三节复合形法二.复合形法：定义：在n维空间中，由k≥n+1个点组成的多面体称为复合形。基本思想：

以一个较好的新点，代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。说明：

单纯形是无约束优化方法，复合形用于约束优化的方法。因为顶点数较多，所以比单纯形更灵活易变。复合形只能解决不等式约束问题。因为迭代过程始终在可行域内进行，运行结果可靠。三.迭代方法：1.映射法：

例：二维空间中，k=4，复合形是四面体x(1)x(2)x(3)x(4)，计算得：f(x(1))<f(x(2))<f(x(3))<f(x(4)),确定最坏点x(H)=x(4)，次坏点x(G)=x(3)，最好点x(L)=x(1)。x(S)为除x(H)以外，各点的几何中心。映射迭代公式：x(R)=x(S)+α(x(S)-x(H))搜索方向：沿x(H)→x(S)的方向。步长因子（映射系数）α：α>1，建议先取1.3。若求得的x(R)在可行域内，且f(x(R))<f(x(H))，则以x(R)代替x(H)组成新复合形，再进行下轮迭代。●X(S)X(R)X(H)变形法一

——扩张：若f(x(R))<f(x(L))，则可沿此方向扩张取若f(x(E))<f(x(L))，则扩张成功，以x(E)代替x(H)组成新复合形若f(x(E))>f(x(L))，则扩张失败，以x(R)代替x(H)组成新复合形●X(S)X(R)X(H)X(E)变形法二

——收缩：若在映射法中f(x(R))>f(x(H)),则以a＝0.5a重复采用映射法若直至a<10-5仍不成功，考虑采用收缩法

取

若f(x(K))<f(x(H)),则成功，以x(K)代替x(H)组成新复合形。●X(S)X(R)X(H)X(K)4.变形法三

——压缩：如采用上述方法均无效，还可以将复合形各顶点向最好点

x(L)靠拢，即采用压缩的方法改变复合形的形状。

取

X(L)四.初始复合形的形成：人工选择初始复合形2.随机产生初始复合形：

①先在可行域内确定一个初始顶点；②确定xi的上下界：ai、bi；③产生区间[0,1]中的k-1组伪随机数ri(j)；④产生k-1个顶点，xi(j)=αi+ri(j)

(bi-ai)⑤检查k-1个顶点的可行性，若有q个顶点满足约束，求q个顶点的几何中心：

⑥以x(q+1)=x(t)+α(x(q+1)-x(t)),a=0.5将不满足约束的顶点移向可行域若可行域是非凸集，可能失败，需减小上、下界再进行。步骤：

1.形成初始复合形

2.计算各顶点的函数值,找到最坏点x(H)

、次坏点x(G)和最好点x(L)

3.计算除最坏点外，其余顶点的形心:

检查形心是否在可行域内

4.则可行域为非凸集，取ai＝min[ai

(L),

ai(S)],

bi＝max[ai

(L),

ai(S)]作为上下界；计算xi(j)=αi+ri(j)(bi-ai)，重新构成复合形，转步骤2

5.计算映射点：

x(R)=x(S)+a(x(S)-x(H))

检查是否在可行域内是，a=1.3,转步骤5否，转步骤4是，转步骤6否，a=0.5a,重新计算反射点6.计算f(x(R))，若

7.若a>

:

检查终止准则

若f(x(R))<f(x(H))，以x(R)代替x(H)重构复合形后转步骤2f(x(R))≥f(x(H))，转步骤7是，则a=0.5a，转步骤5否，则调用收缩法或压缩法，重构复合形后转步骤2是，则迭代结束，以此复合形的x(L)为x＊否，则以重构的复合形转步骤2六.方法评价：

计算简单，不必求导，占内存小；随着维数的增加，效率大大下降；不能解含等式约束的问题；建议：①初始α取1.3。②n+1≤k≤2n，当n≤5时，k取值接近2n；当n>5时，k取值可小些。一.基本思想：在可行域内选择一个初始点x(0)，确定了一个可行方向和适当的步长后，按照下式进行迭代计算：

x(k+1)=x(k)+ad通过不断的调整可行方向，使迭代点逐步逼近约束最优点。§第四节可行方向法二.搜索策略：

根据目标函数和约束函数的不同性态，选择不同的搜索策略。

①边界反弹法：第一次搜索为负梯度方向，终止于边

界。以后各次搜索方向均为适用可行方向，以最大

步长从一个边界反弹到另一个边界，直至满足收敛

条件。x(1)x(2)x(3)x*x(0)§第四节可行方向法

②最优步长法：第一次搜索为负梯度方向，终止于边

界。第二次搜索沿适用可行方向作一维搜索以最优

步长因子求得最优点。反复以上两步，直至得到最

优点x*。x(1)x(2)x(3)x*x(0)§第四节可行方向法

③贴边搜索法：第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个约束面，经过有限的几步就可以收敛到最优点。x(1)x(2)x*x(0)§第四节可行方向法

若约束面是非线性时，从x(k)点沿切线（面）方向d(k)

搜索，会进入非可行域。容差带δ：

建立约束面的容差带+δ，从x(k)

出发，沿d(k)方向搜索到d(k)方向与g(x)+δ=0的交点x’后，再沿适时约束的负梯度方向返回约束面的x(k+1)点。x(k)x(k+1)g(x)g(x)+

δx’-▽g(x)d(k)§第四节可行方向法调整步长因子α1

：

x(k+1)=x’-a1▽g(x’)将g(x)在x’点泰勒展开，取一阶近似式：

g(x)≈g(x’)+[▽g(x’)]T(x-x’)进而得到：

g(x(k+1))≈g(x’)+[▽g(x’)]T[-a1▽g(x’)]为了让x(k+1)到达约束面，令g(x(k+1))=0得:§第四节可行方向法三.可行方向的确定可行方向应该满足设计点可行及目标函数值下降两个条件

①可行条件:

[▽gj(xk)]T

dk≤0

j=1,2,…J(起作用约束的个数)▽g(xk)dk▽g1(xk)▽g2(xk)dk§第四节可行方向法三.可行方向的确定

②目标函数值下降条件:

[▽f(xk)]T

dk<0

▽f(xk)dk§第四节可行方向法三.可行方向的确定[▽gj(xk)]T

dk≤0

保证在可行域内[▽f(xk)]T

dk<0

保证目标函数值下降

可行方向§第四节可行方向法①优选方向法四.可行方向产生方法式中：d为求解变量，▽gj(xk)]T

、[▽f(xk)]T为定值，可用线性规划方法求解§第四节可行方向法②梯度投影法：可行方向:

其中:p为投影算子J-起作用的约束个数§第四节可行方向法①取最优步长五.步长的确定若x(k+1)为可行点，a＊作为本次迭代步长

x(k+1)=x(k)+a＊da＊dx(k+1)

§第四节可行方向法②取最大步长aM五.步长的确定a＊daMdx(k+1)

x(k+1)=x(k)+a＊d§第四节可行方向法收敛条件2）设计点xk满足库恩-塔克条件1）设计点xk及约束允差满足例用可行方向法求约束优化问题的约束最优解。Minf(x1,x2)=x12+2x22-10x1-x1x2-4x2+60s.t.g1(x)=x10

g2(x)=x20g3(x)=x160g4(x)=x280g5(x)=x1+x2110解：取初始点x0=[01]T，为约束边界g1(x)=0上的一点。第一次迭代用优选方向法确定可行方向。首先计算x0点的目标函数f(x0)和约束函数g1(x0)的梯度为在可行下降扇形区内寻找最优方向，需求解一个以可行方向d=[d1d2]T为设计变量的线性规划问题，其数学模型为：最优方向是d*=[0.9840.179]T，它是目标函数等值线（直线束）和约束函数d12+d22=1（半径为1的圆）的切点。第一次迭代的可行方向为d0=d*。第一次迭代的可行方向为d0=d*。若步长取

0=6.098，则

可见第一次迭代点x1

在约束边界g3(x1)=0上。

第二次迭代用梯度投影法来确定可行方向。迭代点x1的目标函数负梯度-

f(x1)=[0.0925.818]T，不满足方向的可行条件。现将f(x1)投影到约束边界g3(x)=0上，

计算投影算子P本次迭代的可行方向为显然，d1为沿约束边界g3(x)=0的方向。若取1=2.909，则本次迭代点即为该问题的约束最优点x*则得约束最优解

将有约束的优化问题转化为无约束优化问题来求解。前提：一是不能破坏约束问题的约束条件，二是使它归结到原约束问题的同一最优解上去。

构成一个新的目标函数：§第五节

惩罚函数法惩罚项惩罚因子惩罚函数从而保证惩罚项必须具有以下极限性质：根据惩罚项的不同构成形式，惩罚函数法又可分为内点惩罚函数法、外点惩罚函数法和混合惩罚函数法§第五节

惩罚函数法一.内点惩罚函数法基本思想内点法将新目标函数Φ(x,r)构筑在可行域D内，随着惩罚因子r(k)的不断递减，生成一系列新目标函数Φ(xk,

r(k))，在可行域内逐步迭代，产生的极值点xk*(r(k))序列从可行域内部趋向原目标函数的约束最优点x*。例：min.f(x)=x

s.t.g(x)=1-x≤0X1*X2*X*2.惩罚函数的形式

①

②其中：惩罚（加权）因子

降低系数c：0<c<1当x在可行域内远离约束边界时：当x由可行城内靠近约束边界时：障碍项3.几个参数的选择惩罚因子初始值r(0)

的选择：

过大、过小均不好，建议考虑选择r(0)=1或者：2.降低系数c的选择：c的典型值为0.1～0.7。3.初始点x(0)

的选择：要求：①在可行域内；②不要离约束边界太近。方法：①人工估算，需要校核可行性；②计算机随机产生，也需校核可行性。

③搜索方法：

任意给出一个初始点；判断其可行性，若违反了S个约束，求出不满足约束中的最大值：

应用优化方法减少违反约束：

以求得的设计点作为新初始点，继续其判断可行性，若仍有不满足的约束，则重复上述过程，直至初始点可行。④

判断是否收敛：4.步骤：①选取合适的初始点x(0)

，以及r(0)、c、计算精度ε1、ε2

，令k=0；

②

构造惩罚（新目标）函数；③调用无约束优化方法，求新目标函数的最优解xk*和

Φ(xk,r(k))；若均满足，停止迭代，有约束优化问题的最优点为x*=xk*；若有一个准则不满足，则令并转入第3步，继续计算。例：用内点法求下列问题的最优解：构造惩罚函数112二.外点惩罚函数法1.基本原理外点法将新目标函数Φ(x,r)构筑在可行域D外，随着惩罚因子r(k)的不断递增，生成一系列新目标函数Φ(xk,r(k))，在可行域外逐步迭代，产生的极值点xk*(r(k))序列从可行域外部趋向原目标函数的约束最优点x*。新目标函数：例：求下述约束优化问题的最优点。

min.f(X)=x

x∈R1s.tg(X)=1-x≤0惩罚函数可取为2)惩罚因子1)当设计点在可行域内时,惩罚项为0,不惩罚;当设计点在可行域外

时,惩罚项大于0,有惩罚作用.外点法可以用来求解含不等式和等式约束的优化问题。衰减项3.几个参数的选择①r(0)

的选择:r(0)

过大，会使惩罚函数的等值线变形或偏心，求极

值困难。r(0)

过小，迭代次数太多。r(0)

＝1或者②x(0)

的选择：基本上可以在可行域内外，任意选择。③递增系数c的选择：通常选择5～10，可根据具体题目，进行试算调整。内点法特点：

（1）初始点必须为严格的可行点

（2）不适于具有等式约束的数学模型

（3）迭代过程中各个点均为可行设计方案

（4）一般收敛较慢

（5）初始惩罚因子要选择得当

（6）惩罚因子为递减，递减率c有0<c<1

外点法特点：

（1）初始点可以任选

（2）对等式约束和不等式约束均可适用

（3）仅最优解为可行设计方案

（4）一般收敛较快

（5）初始罚因子要选择得当

（6）罚因子为递增，递增率c有c>1三.

混合惩罚函数法1.基本思想采用内点法和外点法相结合的混合惩罚函数法，以发挥内点法和外点法的特点，处理既有等式约束，又有不等式约束的优化设计问题。2.惩罚函数的形式一般既包括障碍项，也包括衰减项。惩罚函数法优点：原理简单，算法易行，适应范围广，可利用无约束最优化方法资源。缺点：（1）初始惩罚因子r(0)取值不当可导致惩罚函数变得病态，

使无约束优化计算困难。（2）理论上讲，只有惩罚因子r

(k)

0（内点法）或

r(k)

趋于无穷（外点法）时，算法才收敛，因此序

列迭代过程收敛速度慢。增广乘子法外点惩罚函数＋拉格朗日函数

计算过程稳定，计算效率超过惩罚函数法拉格朗日函数一、拉格朗日乘子法（升维法）§第六节

增广乘子法l+n个方程l+n个未知变量具有相同的最优解X*例:用拉格朗日乘子法求下列问题的最优解解构造拉格朗日函数令▽L=0,得到求解得：构造拉格朗日函数构造外点惩罚函数二.等式约束的增广乘子法

采用拉格朗日乘子法时求解有难度,而罚函数法当迭代点接近边界时函数常有病态,此法的思路是把两者结合起来。其增广拉格朗日函数为:等式约束增广乘子法不论r(k)取何值，增广乘子函数与原函数具有相同的约束极值点X*，与拉格朗日函数有相同的拉格朗日乘子向量。等式约束增广乘子法等式约束增广乘子法增广乘子法中的乘子迭代等式约束增广乘子法参数选取没有其它信息情况下，初始乘子向量

增广乘子函数和外点惩罚函数形式相同；从第二次迭代开始，乘子向量按式子进行校正。惩罚因子初始值r(0)按照外点法取。从第二次迭代开始，惩罚因子按下式递增：惩罚因子递增系数，C=10判别数，通常取0.25等式约束增广乘子法计算步骤：

选取设计变量的初始点x0，惩罚因子初值r0，增长系数β，判别数δ，收敛精度ε，乘子向量λp0=0

(p=1,2,…l),迭代次数k=0；构造增广乘子函数M(x,λ,r)，并用无约束方法求

min

M(x,λ,r)，得无约束最优解xk=x*(λk,rk)计算校正乘子向量如果，迭代终止，约束最优解为x*=xk，λ*=λk+1;否则转步骤6计算惩罚因子再令k=k+1，转步骤2例:用拉格朗日乘子法求下列问题的最优解解构造增广乘子函数确定初始参数：

C＝2,

λ0=0,

r0=0.1，利用解析法求min

M(X,λ,r)，令▽M(X,λ,r)＝0，可得最优解：

krkλkxk10.10(0.0714,0,2142)20.20.0714(0.1507,0.4523)30.40.1507(0.2118,0.6355)40.80.2118(0.3409,0.7227)51.60.2409(0.2487,0.7463)63.20.2487(0.2499,0.7497)76.40.2499(0.2499,0.7499)迭代6次得到最优解,迭代结果如下:精确解:

X*=[0.25,0.75],

f(X*)=0.125不等式约束增广乘子法用于求解不等式约束优化问题。引入松弛变量Z＝[z1,

z2

,

…,

zm]T,并且令则不等式约束优化问题转化为等式优化问题不等式约束增广乘子法构造增广乘子函数由于引入松弛变量Z，使原有的n维极值问题扩充为n+m维问题，计算工作量和求解难度增大，可简化。不等式约束增广乘子法同时具有等式和不等式约束的增广乘子法第七节非线性规划问题的线性化解法——线性逼近法一、序列线性规划法这个方法的基本思想：在某个近似解处将约束函数和目标函数进行泰勒展开，只保留一次项，从而将非线性规划问题变成线性规划问题。求解此线性规划，并将其最优解作为原来问题新的近似解，再展开成新的线性规划问题，再求解。如此重复下去，一直到相邻两次最优解足够接近时为止。缺点：序列线性规划法收敛较慢，且最后的近似解不满足非线性约束，有时还会出现不收敛的情况。为了获得较好的收敛性而采用一些改进的方法，如割平面法、小步梯度法等。第七节非线性规划问题的线性化解法——线性逼近法二、割平面法割平面法主要用于不等式约束的非线性规划问题。若问题是凸规划问题，则这种方法将收敛于问题的最优解。对于非凸规划问题，某些约束的线性近似可能把原问题可行域切掉一些，可能最优点恰好就在这些被切去的区域里。因为这种方法实际上是用线性近似约束把原问题可行域切掉一部分，所以称为“割平面法”。第七节非线性规划问题的线性化解法——线性逼近法三、小步梯度法线性逼近法求解是指按下面的迭代公式对设计点进行修改，从而获得新的设计点的方法。当把上式写成而是一个小数值时，可把此式作为一个约束列入原问题中去求解。当用梯度法求解时，这种方法就是用一个小数值限制各寻优方向步长的方法，可称为小步梯度法。只有当是可行解时，此法收敛较快，否则过程收敛较慢。第七节非线性规划问题的线性化解法——线性逼近法四、非线性规划法对于灯饰和不等式约束的给线性规划问题，有一种解法是把最速下降法（梯度法）和线性规划法结合起来求解。它的解法步骤如下：第一步，当是不可行点时，用最速下降法把它拉到满足约束集内。此时的函数形式取为：第二步，再用线性规划法。每次线性规划阶段移步后，要进行一次判别，看是否满足此法的使用效果好于前两种方法。第七节非线性规划问题的线性化解法——线性逼近法四、非线性规划法对于线性规划问题，也可以通过泰勒级数展开的方法把约束取成线性的，目标函数取成二次函数。这种约束为线性而目标函数是二次函数的最优问题。有多种求解二次规划问题的方法，其中一种实际上可以看成是线性规划问题中单纯形法的推广。因此，用这样的处理办法来解决非线性规划问题可以称为二次规划问题的线性规划解法。第八节广义简约梯度法广义简约梯度法也称GRG法。它是简约梯度法推广到求解具有非线性约束的优化问题的一种方法。这种方法是目前求解一般非线性优化问题的最有效的算法之一。一、简约梯度法简约梯度法仅用来求解具有线性等式约束的优化问题。算法的基本思想是设法处理约束函数，将原问题转化成仅具有变量边界约束的优化问题，然后求解。第八节广义简约梯度法二、广义简约梯度法广义简约梯度法可以用来求解具有非线性等式约束和变量界限约束的优化问题，其数学模型为式中的为变量的下界和上界值。第八节广义简约梯度法三、不等式约束函数的处理和换基问题1.不等式简约梯度法求解的处理方法用广义简约梯度法求解具有不等式约束函数的优化问题时，需引进新变量，将不等式约束函数转化成等式约束函数，即将该问题转化成与式（6-107）相同的形式，然后按前述方法求解。第八节广义简约梯度法三、不等式约束函数的处理和换基问题2.基变量的选择和换基问题按广义简约梯度法原理，首先应将涉及变量分成基变量和非基变量，对于只具有等式函数的问题，应在n设计变量中选择m个变量作为基变量，对于具有不等式约束函数的问题，应在n+l个变量中选择m+l个变量作为基变量（l为松弛变量数），其余的变量为非基变量。为了使基变量的变化尽量少，应选择远离其边界的变量为基变量。同时，为了保证基矩阵非奇异及求逆计算的稳定，要求基矩阵的主元不能太小以及同列中的其他元素与主元之比不能太大。在迭代过程中，若某一基变量等于0，或等于边界值时，应换基变量，即选择一非基变量来代替该基变量。第九节二次规划法二次规划法的基本原理是将元问题转化为一系列二次规划的子问题。求解子问题，得到本次迭代的搜索方向，沿搜索方向寻优，最终逼近问题的最优点，因此，这种方法又称为序列二次规划法。另外，算法是利用拟牛顿法（变尺度法）来近似构造海塞矩阵，以建立二次规划子问题，故又可称为约束变尺度法，这种方法被认为是目前最先进的非线性规划计算方法。第九节二次规划法二次规划法的迭代步骤如下：1.给定初始值，令（单位矩阵）。2.计算原问题的函数值、梯度值，构造二次规划子问题。3.求解二次规划子问题，确定新的乘子矢量和搜索方向。4.沿进行一维搜索，确定步长，得到新的近似极小点。5.若满足收敛精度则停止计算，否则转至下步。6.采用拟牛顿公式（如BFGS公式）对进行修正，得到，返回步骤2.第十节结构优化简述在工程结构设计中，通常要在保证性能约束条件下，满足结构体积尽量小以减轻重量或节约材料。在进行结构设计时，性能约束一般是取结构固有频率禁区约束、振型约束、结构变形或许用应力约束。以准则法思想为基础的优化准则法，对于结构优化来说，它是一种收敛速度快、求解目标函数和约束函数次数少的一种方法。准则法思想是由“满应力设计”和“同步失效准则”原则，且主要是针对桁架结构的最轻设计发展起来的。第十节结构优化简述一、准则方程二、迭代乘子C三、优化准则法和数学规划法的相似性质四、形状优化和拓扑布局优化五、小结第十节结构优化简述一、准则方程任何一个设计方案是否是最优的基本检验方法就是看它是否满足K-T条件。优化问题的准则方程是由所讨论的优化问题的最优解应满足K-T条件推导出来的。这时的迭代公式用来寻求满足K-T条件的极小值点（设计点）。第十节结构优化简述二、迭代乘子C考虑到结构性能约束函数常是隐含设计变量的非线性方程，对式（6-127）的准则方程的求解可采用线性迭代的方法。这种求解从某个初始设计变量开始，按迭代公式反复进行线性迭代，直到求出满足准则方的设计变量。这种优化准则就具有数学规划法的性质，是准则思想和数学规划的结合，故称为优化准则法。第十节结构优化简述三、优化准则法和数学规划法的相似性质虽然在满应力设计的一类准则设计中，不考虑目标函数值，因而其解不是最优解。这反映了它和数学规划法的不同，这是它的特点。但是，在优化准则法中，由于准则方程是目标函数梯度换和诸约束梯度的线性组合，所以已经失去了原来的满应力类设计与目标函数无关的特点，而具有数学规划法的性质。它实际上已经把准则法和数学规划法结合起来了。第十节结构优化简述四、形状优化和拓扑布局优化一种以极大值原理为基础——把优化问题表示为泛函极值形式的求解结构形式的理论和方法的应用，实现了从有限维的参数优化向无限维的形状优化和拓扑及布局优化的跨越。这种无限维的优化方法是一种连续型的分析方法，它是基于结构的弹性力学模型和泛函极值的求解方法。连续体的形状和拓扑及布局优化设计需要建立研究对象的几何和分析模型，这既涉及用相应的优化设计变量对边界形状和布局进行有效的描述，也需要处理与有限元分析相关的敏度分析和网络生成等问题。第十节结构优化简述五、小结求解非线性规划问题可概括为如下三种迭代格式：1）（搜索格式）2）（替代格式）3）（收敛格式）前两种属于数学规划类方法，后一种属于优化准则方法。第十节结构优化简述五、小结总得策略：一是在可行域内直接搜索最优设计点；二是把非线性问题转化为线性问题，采用线性规划方法求解；三是把约束问题转化为无约束问题，采用无约束方法求解。具体方法是：1）直接方法——以约束条件为界面，形成一个解的可行域，在可行域范围内直接采用无约束优化方法求解。2）线性逼近法——把非线性函数在现行点线性化，采用较成熟的线性规划方法。3）简接方法——先把约束问题转化为无约束问题，再采用无约束优化方法求解。这种方法可以分为两类，即降维方法和升维方法。Powell法、梯度法随机方向法、复合形法、惩罚函数法常规优化算法启发式算法(现代优化计算方法)

适于求解高非线性、多约束、多极值问题遗传算法（Geneticalgorithms）神经网络优化算法（Neuralnetworksoptimization）混合优化算法（Hybridoptimization）§第十一节

遗传算法简述一.背景：生物进化基本循环图

依据生物进化论的“适者生存”规律而提出：§第十一节

遗传算法简述

遗传算法的主要生物进化特征体现在：（1）进化发生在解的编码（染色体）上。（2）自然选择规律决定优秀的染色体产生超过平均数的后代。遗传算法通过优化目标构造适应函数以达到好的染色体超过平均数的后代。（3）染色体结合时，双亲的遗传基因结合使得子女保持父母的特征。（4）当染色体结合后，随机变异会造成子代与父代不同。§第十一节

遗传算法简述二.基本思想：

遗传算法在求解优化问题时首先对求解空间的各个解进行编码。在寻优过程中，通过对染色体

进行结合（选择、交配和变异），不断产生新的解，进而根据适应函数在新解中选择部分染色体继续进行结合，直至最终找到最好的解。§第十一节

遗传算法简述

例用遗传算法求minf(x1,x2)=x1+x2

，当x1和x2为整数时的整数解，且解：若用4位二进制编码表示一个设计变量xi，则一个解(x1,x2)需用8位二进制编码表示：一个解（个体的染色体）适应函数f(x1,x2)N1：1011001114N2：1101111027N3：1000110121N4：0110010111N4：01100101交配N1：10110011N4：01100101交配N3：10001101N1’：01110111=14N2’：10100001=11N3’：01000101=9N4’：10101101=23遗传算法4个组成部分：编码和解码、适应函数、遗传算子和控制参数若以这4个个体为群体，按求解的要求，适应函数值小的染色体的生存概率较大，则能竞争上的是N1、N3和N4点，其交配方式如下：通过分别交换基因，实现了交配，得到了4个新个体N1’、N2’、N3’和N4’。若对某个个体（例如N2’）进行基因变异（1→0），可得N2”:00100001(=3)三.算法的基本步骤：S.1选择优化问题求解的一种编码；S.2随机产生N个染色体的初始群体{pop(k),k=0}；S.3对群体中的每个染色体popi(k)计算适应函数

fi=fitness(popi(k))S.4若满足终止规则，则转向S.9，否则计算概率S.5以概率pi从pop

(k)中随机选一些染色体构成一个新群体（其中可以重复选pop

(k)中的元素）

newpop(k+1)={popi(k),i=1,2,···,N}§第十一节

遗传算法简述三.算法的基本步骤：S.6通过交配，按交配概率pc得到一个有N个染色体的交配群体crosspop(k+1)；S.7以一个较小的变异概率pm，使得一个染色体的基因发生变异，形成变异群体mutpop(k+1)；S.8令k=k+1和popi(k)=mutpop(k+1)，返回S.3；S.9终止计算，输出最优结果。§第十一节

遗传算法简述四.算法实现的几个技术问题——编码和解码编码——由设计空间向编码空间的映射。将设计解用字符串表示的过程。编码的选择是影响算法性能和效率的重要因素。解码——由编码空间向设计空间的映射。§第十一节

遗传算法简述几种常见的编码方式四.算法实现的几个技术问题——编码和解码

编码方式示例说明二进制编码染色体中的基因值只能是二值符号集｛0，1｝中一个实数编码染色体的基因值是设计变量的真实值符号编码每一位基因只能有代码含义，无数值含义序列编码例如在旅行商问题中，此编码表示按顺序”1→3→5→7→9→2→4→6→8→1”依次访问各个城市110100115.806.702.183.56ABCDEF13579246§第十一节

遗传算法简述对于求极大化的目标函数（max

f(x)），可通过下面转换建立与fitness(x)的映射关系:四.算法实现的几个技术问题——适应函数fitness(x)

对于求极小化的目标函数（min

f(x)），可通过下面转换建立与fitness(x)的映射关系:Cmin和Cmax为可调参数，所取的值应使适应函数fitness(x)恒大于0。适应函数——用于对个体进行评价，即反映个体对环境适应能力。是优化进程发展的依据。其值必须大于等于零§第十一节

遗传算法简述群体规模N——是影响算法性能和效率的因素之一。规模太小，不能提供足够多的采样点；规模太大，计算量大，耗时长。通常取N介于n（编码长度）和2n之间，或依据经验在范围内取值。四.算法实现的几个技术问题——算法参数

交配概率pc

——用于控制交配操作的频率，通常取0.4~0.9之间。概率太大，种群更新过快，会使高适应函数值的个体过快被破坏；概率太小，交配操作很少进行，搜索速度慢，耗时长。变异概率pm

——加大种群多样性的重要因素，通常取0.001~0.1之间。概率太大，则使遗传算法退化成随机搜索算法；概率太小，产生新个体的机会太小。§第十一节

遗传算法简述复制、交配、变异四.算法实现的几个技术问题——遗传算子

复制(选择)

—选择用于繁殖后代的双亲。体现“适者生存”，适应度高，生存概率大。依据选择概率pi=fi/Σfi进行。交配(交叉)

—两个相互配对的染色体（双亲）按某种方式相互交换其部分基因而生成两个新的个体。§第十一节

遗传算法简述四.算法实现的几个技术问题——遗传算子

双亲A100100交配B010010后代A’100010B’010100双亲A1011001

交配B0010110后代A’1010101B’0011010一点交配（二进制）：多点交配（二进制）：§第十一节

遗传算法简述四.算法实现的几个技术问题——遗传算子

0101010变异0101110变异

—在交配之后进行。将个体染色体编码字符中的某些基因用其他等位基因