《《高级运筹学》约束非线性规划.ppt》由会员分享，可在线阅读，更多相关《《高级运筹学》约束非线性规划.ppt（149页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、约束非线性规划高级运筹学高级运筹学教学课件教学课件2015-10本章内容本章内容 第一节 最优性条件 第二节 可行方向法 第三节 惩罚函数法 第四节 复形法本章讨论如下的约束非线性规划问题本章讨论如下的约束非线性规划问题其中 f,gi,hj均为实值连续函数，且一般具有二阶连续偏导数。求解一般约束非线性规划问题，比无约束问题和线性规划问题都要复杂得多。x2x*o11可行域是一个三角形及其内部，目标函数等值线是以原点为圆心的同心圆。最优解：最优值考虑问题x1 线性规划的最优解总可以在可行域的顶点中找到，而顶点个数有限。约束非线性规划问题的困难性：约束非线性规划问题的困难性：1.最优解不一定在顶点上
2、；最优解不一定在顶点上；2.求解无约束问题的迭代法不能直接搬过来用。求解无约束问题的迭代法不能直接搬过来用。例如：对于上面的问题，如果不存在约束，从任意初始点例如：对于上面的问题，如果不存在约束，从任意初始点x(0)出发，沿出发，沿f(x)的负梯度方向进行一维搜索，便求得极小的负梯度方向进行一维搜索，便求得极小点点(0,0)T。有了约束，在进行一维搜索时，为了使求得的点是一个可有了约束，在进行一维搜索时，为了使求得的点是一个可行点，就必须对步长加以限制，这样，最远只能跑到边界行点，就必须对步长加以限制，这样，最远只能跑到边界上的一个点。上的一个点。当所取的x(0)不在直线x1-x2=0上时，x
3、(1)点就不会是最优解x*,因此还必须继续迭代下去找一个新的可行点，使目标函数取更小的值。x2x*o11x1x(1)x(0)可是，沿f(x)在x(1)处的负梯度方向已经找不到可行点，因而梯度迭代已经不能继续进行，尽管离最优解还可能很远。为了使迭代能继续下去，不仅要求搜索方向具有使目标函数下降的性质，而且要求在这个方向上有可行点。例如有一小段整个包含在可行域内，这样的方向称为可行方向。设计求解约束非线性规划的迭代法，关键是在每个迭代点处构造一个下降可行方向。求解约束非线性规划的另一个途径是：在某个近似解处，以已有较好解法的较为简单的问题近似代替原问题，用其最优解作为原来问题的新的近似解。如将目标
4、函数及约束条件中的非线性函数分别以它们的一阶泰勒多项式或二阶泰勒多项式近似代替，或以一无约束非线性规划近似代替。如何判断约束非线性规划的一个可行解是否为最优解？第一节 最优性条件一、等式约束极小化问题的最优性条件考虑下面的约束优化问题其中f,h 均为可微函数。以上问题的几何意义：在曲面上寻找函数 f(x1,x2,x3)的最小值。（1）设以上问题的最优解为在曲面上任作一条通过点x*的光滑曲线则必有显然，限于曲线 l 上 x*亦是使f(x1,x2,x3)取极小值的点，即t*是一元函数F(t)=f(x1(t),x2(t),x3(t)的极小点因此必有即梯度f(x*)垂直于曲线l在点x*处的切线，由l的
5、任意性知，f(x*)必垂直于在x*处的切平面方向。由上面的分析知f(x*)和h(x*)必在同一直线方向上，即存在数*,满足可以证明，对于一般等式约束问题在最优解x*处，必存在数值(1*,2*,l*),使为便于记忆，引进拉格朗日函数（2）定理定理1 1（等式约束问题最优解的一阶必要条件）（等式约束问题最优解的一阶必要条件）解（1）建立数学模型 取点A(x1,y1,z1),B(x2,y2,z2)，限制A在曲面上变化，B在平面上变化，则A、B 间距离S的最小值为解。问题的数学模型为：其中已把距离S最小等价地替换成S2 最小，以简化目标函数。（2）利用最优性条件求解再加约束条件由上述方程组解得相应目标
6、函数值为由问题的几何意义知最优解肯定存在，又据必要条件仅此一个解，故以上所求即为最优解和最优值。二、一般非线性规划的最优性条件考虑问题其中f,g1,g2均可微。（3）设 为（3）的最优解，且设由于x*为区域(x1,x2,x3)|g2(x1,x2,x3)0的内点，所以，对于x*而言，约束g2(x1,x2,x3)0 实际并没有起作用。称约束g1(x1,x2,x3)0为点x*处的有效约束。于是x*实际上也是问题（4）的最优解，由定理1知，必有1*，使为使形式整齐起见，引进2*=0，统一写成把和2*=0，统一写成（5）（7）（6）从几何上看，(5)式的f(x*)和 g1(x*)都通过x*且应共线。实际
7、上，由于x*是(4)的最优解，所以，当动点x由x*出发沿着g1(x)=0上的各个方向移动时，目标函数值f(x)均增加，不仅如此，而且 x由x*出发往g1(x)0的内部移动时（即下图所示箭头方向），f(x)也应增加。x*由于梯度指向函数值的增加方向，因此，f(x*)和g1(x*)不仅共线，而且应该是同方向的。即（6）中的总之，(4)的最优解x*应满足条件(6)(7)(8)（8）x*g1(x*)f(x*)考虑一般不等式约束问题g2(x)=0 x*g1(x)=0g1(x*)=0,g1为有效约束不等式约束问题的不等式约束问题的K-T点的点的几何意义几何意义对于一般约束非线性规划问题（9）构造拉格朗日函
8、数（10）定理2（Kuhn-Tucher必要条件，简称K-T条件）对于非线性规划（9），若f,gi,hj 均可微且gi(x*),iI(x*),hj(x*),j=1,l线性无关，则x*为（9）的最优解的必要条件为：存在相应的拉格朗日乘子*和*使（9）K-TK-T条件条件条件条件是多元函数取得约束极值的是多元函数取得约束极值的必要条件必要条件必要条件必要条件,可以用来可以用来作为约束极值的判断条件。作为约束极值的判断条件。对于目标函数和约束函数都是凸函数的情况，对于目标函数和约束函数都是凸函数的情况，对于目标函数和约束函数都是凸函数的情况，对于目标函数和约束函数都是凸函数的情况，符合符合符合符合K
9、-TK-T条件的点一定是全局最优点。条件的点一定是全局最优点。条件的点一定是全局最优点。条件的点一定是全局最优点。这种情况这种情况K-T条件即为多条件即为多元函数取得约束极值的充分必要条件。元函数取得约束极值的充分必要条件。满足满足K-T条件的可行点称为条件的可行点称为K-T点，最优性条件指在梯度线点，最优性条件指在梯度线性无关的条件下，最优点必定是性无关的条件下，最优点必定是K-T点。点。在实际应用中，很难验证所得的点是否为非线性规划的在实际应用中，很难验证所得的点是否为非线性规划的最优解，若能验证其是最优解，若能验证其是K-T点，就已经满足了。有时构点，就已经满足了。有时构造算法也是以得到
10、造算法也是以得到K-T点为目标的。点为目标的。例例2求以下非线性规划的求以下非线性规划的K-T点点解：非线性规划的解：非线性规划的K-T条件为条件为再加上约束（11）（12）（13）（14）（15）（16）x1f(x1)x1x2解解：在x1=(2,1)T 点，I=1,2且，g1(x1),g2(x1)线性无关。为使成立，只要取即可。所以，x1是K-T点。在x2=(0,0)T 点，I=3,4且，g3(x2),g4(x2)线性无关。为使成立，只有取由于30,40，使对任意，使对任意t(0,)均有均有x+td D,则称则称d为从为从x点出发的可行方向。点出发的可行方向。d为可行方向为可行方向d1不是可
11、行方向不是可行方向xdd1D第二节第二节 可行方向法可行方向法基本思想基本思想：在每一个迭代点处，寻找一个下降可行方向，在每一个迭代点处，寻找一个下降可行方向，沿下降可行方向进行一维搜索。沿下降可行方向进行一维搜索。如何寻找可行方向？如何寻找可行方向？可行方向：设可行域DRn是非空集，xD.若对于某非零向量，d Rn,存在0，使对任意t(0,)均有x+td D,则称d为从点x出发的可行方向。例例7在由约束在由约束所确定的可行域内，任求一个在点x=(0,1,2,3)T处的可行方向。解解：首先检查在点x处哪些约束为有效约束，经检查，约束（1）（2）（3）和x10为有效约束。设所求可行方向为根据可行
12、方向的定义，应存在，使对任意 t(0,)有也能满足所有有效约束，即整理得整理得满足上述不等式的 均为可行方向。现只求一个可行方向，可令不等号改为等号，求解得得为使d10，可取d3=1得一可行方向利用可行方向的概念，典型的策略是：由可行点x(k)出发，找一下降可行方向d(k)作搜索方向，然后确定沿此方向移动的步长，得下一迭代点x(k+1).这类方法称可行方向法。搜索方向的选择方式不同就形成不同的可行方向法。Zoutendijk可行方向法考虑(1)上述问题的约束是线性的，仅目标函数是非线性的，在迭代点x(k)附近，可以用f(x)的一阶泰勒展开式近似代替f(x).假设x(k)满足于是得到线性规划(2
13、)注意到d=0为上述线性规划(2)的可行点，其对应的目标函数值为0，所以若d*为问题(2)的最优解，则若则d*为问题(1)在x(k)处的下降可行方向；若则x(k)为问题(1)的K-T点。(证明略)(2)(1)Zoutendijk可行方向法的具体步骤可行方向法的具体步骤1.任选可行点x(0)作初始点，令k=0;2.根据x(k)的有效约束把A分解为A1，A2，相应地把b分解为b1,b2,使3.求解线性规划设其最优解为d(k)。解：取x(0)=(0,2)T,注意在x(0)点，有效约束仅x10一个，故A2=(1,0),b2=0.设所求的下降可行方向d(0)=(d1,d2)T,其相应的线性规划为求得最优
14、解 d(0)=(0,-1)T.因还需继续迭代。求搜索区间。计算在t0,4/5中求作第二次迭代关于x(1)的有效约束为求得最优解 d(1)=(2/3,-1)T.因还需继续迭代。在t0,3/5中求作第三次迭代关于x(2)的有效约束为还需继续迭代。求得最优解 d(2)=(1,-1)T.因在t0,3/5中求作第四次迭代关于x(3)的有效约束为求解得即得本题的最优解为由于用Zoutendijk可行方向法解下列问题（1）取初始点 x(1)=(0,0)T（2）取初始点 x(1)=(2,0)T（3）取初始点 x(1)=(1,2)T第三节第三节惩罚函数法惩罚函数法 基本思想基本思想：通过构造罚函数把约束优化问题
15、转：通过构造罚函数把约束优化问题转化为化为一系列无约束最优化问题一系列无约束最优化问题，进而用无约束最优，进而用无约束最优化方法去求解。化方法去求解。又称为序列无约束最小化方法。又称为序列无约束最小化方法。考虑一般约束非线性规划问题考虑一般约束非线性规划问题根据约束的特点，构造某种根据约束的特点，构造某种“惩罚惩罚”项，然后把它加到项，然后把它加到目标函数中去，使得约束问题的求解，转化成一系列无目标函数中去，使得约束问题的求解，转化成一系列无约束问题的求解。约束问题的求解。“惩罚惩罚”策略：对于无约束问题求解过程中企图违反约策略：对于无约束问题求解过程中企图违反约束的那些迭代点，给以很大的目标
16、函数值，迫使这一系束的那些迭代点，给以很大的目标函数值，迫使这一系列无约束问题的极小点或者不断的向可行域靠近，或者列无约束问题的极小点或者不断的向可行域靠近，或者一直保持在可行域内部移动，直到收敛于原约束问题的一直保持在可行域内部移动，直到收敛于原约束问题的极小点。极小点。常用的惩罚函数法有三种：一、外部惩罚函数法（外点法）一、外部惩罚函数法（外点法）对违反约束的点在目标函数中加入相应的对违反约束的点在目标函数中加入相应的“惩罚惩罚”，而对可行点不予惩罚。此法的迭代点一般在可行域外部移而对可行点不予惩罚。此法的迭代点一般在可行域外部移动。动。二、内部惩罚函数法（内点法）二、内部惩罚函数法（内点
17、法）对企图从内部穿越可行域边界的点在目标函数中加入对企图从内部穿越可行域边界的点在目标函数中加入相应的相应的“障碍障碍”，距边界越近，障碍越大，在边界上给以，距边界越近，障碍越大，在边界上给以无穷大的障碍，从而保障迭代一直在可行域内部移动。无穷大的障碍，从而保障迭代一直在可行域内部移动。三、乘子法三、乘子法 在拉格朗日函数中加入相应的惩罚。在拉格朗日函数中加入相应的惩罚。一、外点法基本原理：外点法是从可行域的外部构造一个基本原理：外点法是从可行域的外部构造一个极小点序列极小点序列去去逼近逼近原约束问题的原约束问题的最优解最优解。对于等式约束问题：对于等式约束问题：定义辅助函数参数是很大的正数。
18、（1）（2）当求解无约束问题当求解无约束问题（3）得到的最优解得到的最优解x*，满足，满足hj(x*)=0,j=1,2,l 时，显然时，显然x*就是原问题就是原问题(1)的最优解。的最优解。在求解问题在求解问题(3)的过程中，若的过程中，若x(k)不满足不满足hj(x(k)=0,则则(2)中中第二项将是很大的正数，限制它成为极小点，以迫使无第二项将是很大的正数，限制它成为极小点，以迫使无约束问题约束问题(3)的最优解满足（或接近满足）的最优解满足（或接近满足）hj(x)=0(j=1,2,l).可见，求解问题可见，求解问题(3)能够得到问题能够得到问题(1)的近似解。的近似解。对于不等式约束问题
19、对于不等式约束问题构造辅助函数这样可以将问题（4）转化为无约束问题（4）（5）（6）对于一般约束问题对于一般约束问题可以定义辅助函数这样约束问题（7）转化为无约束问题（7）（8）（9）其中，1，通常取=2（10）（9）（10）（7）当当x为问题为问题(7)的可行点时，的可行点时，P(x)=0，从而从而F(x,)=f(x);当当x不是问题不是问题(7)的可行点时，的可行点时，P(x)是很大的正数，可视为是很大的正数，可视为对对x脱离可行域的一种惩罚，其作用是在极小化问题脱离可行域的一种惩罚，其作用是在极小化问题(10)的的过程中迫使迭代点靠近问题过程中迫使迭代点靠近问题(7)的可行域。因此，求解
20、问题的可行域。因此，求解问题(10)能得到问题能得到问题(7)的近似解，而且的近似解，而且 越大，近似程度越好。越大，近似程度越好。通常将通常将 P(x)称为惩罚项，称为惩罚项，称为惩罚因子，称为惩罚因子，F(x,)称为惩称为惩罚函数。罚函数。例例9求解非线性规划问题求解非线性规划问题解：定义罚函数用解析法求解minF(x,)，有x*恰为所求非线性规划问题的最优解用此法求得的无约束问题最优解往往是不满足约束条件的，它是从可行域外部，随着的增大而趋于x*的，故称此法为外点法。惩罚因子 的选择策略：选取一个趋于无穷大的严格递增正数列k，逐个求解而得到一个极小点序列xk*，在适当条件下，这个序列将收
21、敛于约束问题的最优解。通过一系列无约束问题来获得约束问题最优解的方法称为序列无约束极小化方法，简称SUMT方法(Sequential Unconstrained Minimization Techniques)外点法的计算步骤1.给定初始点x(0)，初始惩罚因子1，放大系数c1,允许误差 0；2.以x(k-1)为初始点，求解无约束问题设其极小点为x(k)；3.若kP(x(k)0，初始参数r10,缩小系数(0,1),k=1。2.以x(k-1)为初始点，求解问题设求得极小点为x(k)；3.若rkB(x(k)，则停，得近似解x(k)；否则，令rk+1=rk,k=k+1,回2。例例12用内点法求解用内
22、点法求解解：首先构造内点罚函数（障碍函数）解：首先构造内点罚函数（障碍函数）用解析法求解用解析法求解根据极值存在的必要条件得求解得考虑约束 x1-10,应舍去。无约束问题的极值点为取r1=4,=0.3 得x(r1)x(r2)最优点图解最优点图解例例13用内点法求解用内点法求解定义障碍函数定义障碍函数用解析法求解用解析法求解令解得内点法注意事项：内点法注意事项：1.初始点选取：尽量选择离约束边界较远的可行点初始点选取：尽量选择离约束边界较远的可行点可以采用随机生成的方法产生可以采用随机生成的方法产生2.惩罚因子惩罚因子r初值的选取：初值的选取：过大：迭代次数多过大：迭代次数多太小：惩罚函数形态恶
23、劣太小：惩罚函数形态恶劣通常选取初始惩罚因子为通常选取初始惩罚因子为150之间的数之间的数3.缩小系数缩小系数 通常选取：通常选取：0.10.7之间的数之间的数例例14用内点法求解用内点法求解解：构造障碍函数用解析法求解根据极值存在的必要条件得解得内点法和外点法的简单比较内点法和外点法的简单比较 内点法的特点：内点法的特点：（1 1）初始点必须为严格内点）初始点必须为严格内点 （2 2）不适于具有等式约束的优化问题）不适于具有等式约束的优化问题 （3 3）迭代过程中各个点均为可行解）迭代过程中各个点均为可行解 （4 4）初始罚因子要选择得当）初始罚因子要选择得当 （5 5）罚因子递减）罚因子递
24、减(0)(0)，递减率，递减率 有有00 111 外点法和内点法使用序列无约束极小化技巧，方法简单，外点法和内点法使用序列无约束极小化技巧，方法简单，使用方便，并且能用来求解目标函数和约束函数导数不存使用方便，并且能用来求解目标函数和约束函数导数不存在的问题，因此，这种算法得到了广泛的应用。在的问题，因此，这种算法得到了广泛的应用。固有缺点：随着惩罚因子趋向其极限，惩罚函数的固有缺点：随着惩罚因子趋向其极限，惩罚函数的Hessen矩阵的条件数无限增大，因而越来越变得病态。惩罚函数矩阵的条件数无限增大，因而越来越变得病态。惩罚函数的这种性态给无约束极小化带来很大的困难。的这种性态给无约束极小化带
25、来很大的困难。为了克服这个困难，为了克服这个困难，Hestenes和和Powell于于1969年年各自独立各自独立地提出了乘子法。地提出了乘子法。练习：练习：用内点法求解下列问题用内点法求解下列问题三、乘子法三、乘子法1.等式约束的情形等式约束的情形考虑问题考虑问题其中f,hj(j=1,2,l)为二次连续可微函数，xRn运用乘子法，需要定义增广拉格朗日函数（乘子惩罚函数）其中乘子惩罚函数(x,)与拉格朗日函数的区别在于增加了惩罚项与惩罚函数的区别在于增加了乘子项这种区别使得增广拉格朗日函数与拉格朗日函数及惩罚函数具有不同的性态。对于(x,)，只要取足够大 的惩罚因子，不必趋向无穷大，就可以通过
26、极小化(x,)求得原问题的局部最优解。（1）若x*是问题(1)的局部最优解，*是相应的最优拉格朗日乘子，且对每个满足dThj(x*)=0(j=1,2,l)的非零向量d，均有二阶充分条件成立，即则存在00,使得对所有 0,x*是(x,*,)的严格局部极小点。根据上述结论，如果知道最优乘子*，那么只要取充分大的惩罚因子，不需趋向无穷大，就能通过极小化(x,*,)求出问题（1）的解。问题：如何确定最优乘子*？方法:先给定充分大的和拉格朗日乘子的初始估计，然后在迭代过程中修正，力图使趋向*。修正的迭代公式：如果(k)不收敛，或者收敛太慢，则增大参数，再进行迭代。收敛快慢的衡量标准乘子法的计算步骤例例1
27、5用乘子法求解用乘子法求解解：构造广义拉格朗日函数（乘子惩罚函数）解：构造广义拉格朗日函数（乘子惩罚函数）修正，得再解得如此继续，一般地，在第k次迭代时，(x,(k),2)的极小点为将的递推公式展开得非线性规划问题的最优乘子和最优解分别为2.不等式约束的情形对于只有不等式约束的问题利用等式约束的结果，引入变量yi,把(2)化为等式约束问题（2）定义增广拉格朗日函数从而把问题（2）转化为求解（2）为此，将变形得将 代入 可以消去yi，因此定义增广拉格朗日函数从而将问题（2）转化为无约束问题 对于既含不等式又含等式约束的问题定义增广拉格朗日函数以充分大的参数，并通过下列公式对迭代过程中的乘子进行修
28、正。计算步骤与等式约束相同。例例16问题问题的最优解为x*=(0.25,0.75)T,分别用惩罚函数法和乘子法求它的迭代点列。解：解：1.惩罚函数法，对于 可求得最优解为2.乘子法，对于可求得最优解为所得迭代点列见下表kx(k)(惩罚函数法)x(k)（乘子法）0(0.0714,0.2142)(0.0714,0.2142)1(0.1111,0.3333)(0.1507,0.4523)2(0.1538,0.4615)(0.2118,0.6355)3(0.1904,0.5714)(0.2409,0.7227)4(0.2162,0.6486)(0.2487,0.7463)5(0.2318,0.6956
29、)(0.2499,0.7497)6(0.2406,0.7218)(0.2499,0.7499)7(0.2452,0.7356)8(0.2475,0.7427)9(0.2487,0.7463)10(0.2492,0.7481)11(0.2496,0.7490)12(0.2498,0.7495)13(0.2499,0.7497)14(0.2499,0.7498)15(0.2499,0.7499)由上表可见，用乘子法迭代6次就达到惩罚函数法迭代15次的效果。惩罚因子在惩罚函数法中要增大到15=3276.8,而在乘子法中只要增大到6=6.4.因此乘子法不需过分增大惩罚因子，因此，乘子法比惩罚函数法有效
30、。第四节第四节复形法复形法无论是无约束最优化还是约束最优化问题，前面介绍的方法无论是无约束最优化还是约束最优化问题，前面介绍的方法均是利用梯度作为工具的。在实际应用中还有一类方法，它均是利用梯度作为工具的。在实际应用中还有一类方法，它在迭代时仅仅涉及目标函数及约束函数的函数值计算。在迭代时仅仅涉及目标函数及约束函数的函数值计算。复形法是求解约束非线性最优化问题的一种重要的直接方法。复形法是求解约束非线性最优化问题的一种重要的直接方法。复形法既可以用于无约束最优化问题，也可以用于约束最优复形法既可以用于无约束最优化问题，也可以用于约束最优化问题。化问题。引例引例求解求解基基基基本本本本思思思思想
31、想想想：在在在在可可可可行行行行域域域域内内内内构构构构造造造造一一一一个个个个具具具具有有有有kk(k(k n+1n+1)个个个个顶顶顶顶点点点点的的的的初初初初始始始始复复复复形形形形。对对对对该该该该复复复复形形形形各各各各顶顶顶顶点点点点的的的的目目目目标标标标函函函函数数数数值值值值进进进进行行行行比比比比较较较较，找找找找到到到到目目目目标标标标函函函函数数数数值值值值最最最最大大大大的的的的顶顶顶顶点点点点(称称称称最最最最坏坏坏坏点点点点)，然然然然后后后后按按按按一一一一定定定定的的的的法法法法则则则则求求求求出出出出目目目目标标标标函函函函数数数数值值值值有有有有所所所所下
32、下下下降降降降的的的的新新新新可可可可行行行行点点点点，并并并并用用用用此此此此点点点点代代代代替替替替最最最最坏坏坏坏点点点点，构构构构成成成成新新新新的的的的复复复复形形形形，复复复复形形形形的的的的形形形形状状状状每每每每改改改改变变变变一一一一次次次次，就就就就向向向向最最最最优优优优点点点点移移移移动动动动一步，直至逼近最优点。一步，直至逼近最优点。一步，直至逼近最优点。一步，直至逼近最优点。在可行域内随机选取在可行域内随机选取k k个点构成初始复形。个点构成初始复形。找出坏点找出坏点x(l)。求求x(l)关于关于x(0)的的 倍反射倍反射点点x()=x(0)+(x(0)-x(l)x
33、()为反射点，为反射点，=1.3。计算除最坏点以外的其余点的中点为计算除最坏点以外的其余点的中点为x(0)。在在迭迭代代过过程程中中，若若反反射射点点不不满满足足可可行行性性和和适适用用性性，将将反反射射系系数数减减小小，重重新新求求x()，使使它它满满足足可可行行性性和和适用性。适用性。复形的顶点复形的顶点k通常取通常取n+1k2n个。个。方法方法1 1：设计者确定；：设计者确定；方法方法2 2：随机产生：随机产生：1、产生产生k个随机点个随机点 xi=ai+i(bi-ai)i=1,2,.,ni i为为(0，1)区间内产生的均匀分布的随机数，需要区间内产生的均匀分布的随机数，需要n个随机数产
34、个随机数产生一个点生一个点 x(1)。同样，产生其它的随机点。同样，产生其它的随机点x(2)、x(3)、x(K)。初始复形的构成初始复形的构成2、将非可行点调入可行域、将非可行点调入可行域判断产生的判断产生的k个随机点是否在可行域内，并重新排列，将个随机点是否在可行域内，并重新排列，将可行点依次排在前面，如有可行点依次排在前面，如有q个顶点个顶点x(1)、x(2)、x(q)是是可行点，其它可行点，其它k-q个为非可行点。对个为非可行点。对x(q+1)，将其调入可行，将其调入可行域的步骤是：域的步骤是：（1）计算）计算q个点集的中心个点集的中心x(s)；（2）将第）将第q+1点朝着点点朝着点x(
35、s)的方向的方向移动，按下式产生新的移动，按下式产生新的x(q+1)，即即x(q+1)=x(s)+0.5(x(q+1)x(s)这个新点这个新点x(q+1)实际就是实际就是x(s)与原与原x(q+1)两点连线的中点，如两点连线的中点，如图。若新的图。若新的x(q+1)点仍为非可行点，按上式再产生点仍为非可行点，按上式再产生x(q+1)，使，使它更向它更向x(s)靠拢，最终使其成为可行点。靠拢，最终使其成为可行点。按照这个方法，同样使按照这个方法，同样使x(q+2)、x(q+3)、x(K)都变为可行都变为可行点，这点，这k个点就构成了初始复形个点就构成了初始复形例例17求解约束非线性规划问题求解约
36、束非线性规划问题随机产生点(2,0)T,(0,2)T,(3,3)T.说明调入可行域的过程。复形法的计算步骤1.构成初始复形2.形成反射点 计算各点的目标函数值，比较出最坏的点x(l),即3.检查可行性4.形成新的复形5.返回2。常用的停机准则有如下两种1.在第二步中，若则停机。2.在第四步中，若则停机，停机时所得到的最好点即作为所求的近似最优点。例例19用复形法求解用复形法求解解：任取解：任取k=4个点构成初始复形个点构成初始复形分别计算相应的函数值比较得最坏点计算由x(1),x(2),x(3)构成的三角形的形心。计算x(4)关于x(0)的反射点（取=1）和相应函数值比较出最坏点x(l)=(5
37、,6)T,计算由(3,5)T,(4,7)T,(2,9)T构成的三角形形心计算(5,6)T关于(3,7)T的反射点和相应函数值继续迭代可以求出满足精度要求的近似最优解。例例20用复形法求解下列约束最优化问题用复形法求解下列约束最优化问题解解:(1)任取任取k=4个点构成初始复形个点构成初始复形验证满足约束条件。验证满足约束条件。(2)计算函数值，找出最坏点比较得最坏点(3)计算其余各点的形心(4)检查形心的可行性(5)求反射点并检查可行性（取=1.3）经验证，反射点满足约束条件。(6)比较反射点与坏点的目标函数值替换坏点，构成新复形：进行第二轮迭代，找出坏点（要求学生接着做）（要求学生接着做）（
38、1 1）复形法是求解约束非线性最优化问题的一种直接方）复形法是求解约束非线性最优化问题的一种直接方法，仅通过选取各顶点并比较各点处函数值的大小，就可法，仅通过选取各顶点并比较各点处函数值的大小，就可寻找下一步的探索方向。但复形各顶点的选择和替换，不寻找下一步的探索方向。但复形各顶点的选择和替换，不仅要满足目标函数值下降的要求，还应当满足所有的约束仅要满足目标函数值下降的要求，还应当满足所有的约束条件。条件。（2 2）复形法适用于仅含不等式约束的问题。）复形法适用于仅含不等式约束的问题。复形法的特点：练习题：用复形法求解下列约束非线性规划问题练习题：用复形法求解下列约束非线性规划问题（1）初始复形初始复形顶顶点取点取：(2,1)T；(4,1)T；(3,3)T；（2）