运筹学非线性规划.ppt

1、第三章第三章 非线性规划非线性规划 请回顾线性规划:,其目标与约束函数均为线性的。线性规划具有相对完美的理论与方法，应用也很广泛，但它终究不能穷尽各种优化问题，因为世界是非线性的。非线性规划（Nonlinear Programming）研究具有非线性构成函数的优化问题，是运筹学中相对活跃的重要研究分支。0.XbAXtsCXMaxz第一节第一节 基本概念基本概念一、非线性规划问题与模型1.问题问题生产计划问题max()()()()0.()0ijf xxP xxC xg xsth xx:产量;P(x):价格;C(x)成本 投资决策问题1111:max().0jjjijnnnjjijjijnjjjj

2、xjPjBjijf xxx xP xBstx第 种股票的购买量；第 种股票的价格总资金；第 种股票的每股平均收益风险系数；第 种与第 种股票收益的协方差 2.模型模型1nn min()()0,1,().()0,1,|()0,()0min()DNLPDRNLPDRNLPijTnnijXDf Xh XimNLP stgXjlXxxDXRh XgXNLPf X其中记则（）也可以表示为其中 称为（）的约束集或可行域。当 时，（）称做无约束极值问题；当时，（）称做约束极值问题。二、模型的解及相关概念1.可行解与最优解可行解与最优解可行解：约束集D中的X。最优解：如果有 ，对于任意的 ，都有 ，则称 为（

3、NLP）的最优 解，也称为全局最小值点。*XDXD*()()f Xf X*X 局部最优解：如果对于 ，使得在 的邻 域 中的任意 都有 ，则称 为（NLP）的局部最 优 解，也称为局部最小值点。0XD0XXD0()()f Xf X00(,)|B XXXX0X例1：考虑非线性问题221212min()(2)(2).6f Xxxstxx2 x1 x6633如果约束改为 呢？126xx2.梯度、海塞阵与泰勒公式梯度、海塞阵与泰勒公式 梯度00000001()()()()()()()Tnf XXf XXf XXf Xf Xf Xf Xxx若在 的邻域内有连续一阶偏导数，则称在点对n个变元的偏导数组成的

4、向量为在 的梯度，记为，即，00()Xf XX几何意义：梯度是过点且与在的切平面垂直的向量，梯度向量的方向是函数值在该点增加最快的方向。海塞阵00000000110012222222()()()()()()()()()()ijnnnn nf XXf XXnf XXf XH XH Xx xf Xf Xxx xf Xf Xx xx 若在 的邻域内有连续二阶偏导数，则称在点对个变元两两组合的二阶偏导数组成的矩阵为在 的海赛阵，记为，即=泰勒公式000000002022000()()()()()1()()()2 ()()TTf XXf XXf Xf Xf XXXXXH XXXoXXoXXXXXX若在的

5、邻域内有连续二阶偏导数，则可写出在点的（二阶）泰勒展开式：（）其中：是当时的高阶无穷小。例2：写出 在 点的二阶泰勒展开式212()3sinf Xxx00,0TX12002()6()0 1 cos,6060(),()0sin00TTf Xxf XxH XH Xx解:2111222()0 0 160 1()002xxf XxxoXxx20212()()3()f Xf XxoXXx如果忽略了在，则点的近似表达式为+3.极值的条件极值的条件对于无约束极值问题，可以利用微积分的知识给出局部极值点的条件。将n(n1)元函数 与一元函数 的极值条件加以对比并归纳如下：()f X()f x00()Xx或是极

6、小点()f x一元函数()f Xn元函数0()0fx0()0f X00()0,()0fxfx且00()0()0f XH X且 充分条件 必要条件0()0H X注：表示海赛阵正定。如果一个方阵的各阶主子式均大于零，则可以判定该方阵是正定的。例3：求 的极小值点221122()228420f Xxxxx解12120()()0 48 442 1TTTfff Xxxf XXxx，解得驻点令0040(),()004H XH XX又故是极小值点。4.凸规划凸规划凸函数：f(X)是定义在凸集D上且满足对任意 有下式成立的函数：1212()(1)(1)()fXf XXf X12,X XD0,1若不等式中严格不

7、等号成立，则称f(X)为严格凸函数注：判断一个可导函数f(X)是否是凸函数的方法一元函数f(x)：二阶导大于等于零;多元函数f(X)：海塞阵半正定。凸规划性质：约束集是凸集；最优解集是凸集；任何局部最优解也是全局最优解；若目标函数是严格凸函数，且最优解存在，则 其最优解是唯一的。在非线性规划模型（NLP）中，若目标函数f（X）是凸函数，不等式约束函数 为凹函数，等式约束函数 为仿射函数，则称（NLP）是一个凸规划。()1,jg Xjl()1,ih Xim 例4：判断下面的非线性规划是否为凸规划12221212max()1.,0f Xxxxxstx x12221122132min()()10.(

8、)0()0f Xxxg Xxxstg Xxg Xx 标准化123()00200,()0000200()()000fgggHXHXHXHX123()()()()f XgXgXgX说明是凸函数，、是凹函数因此，本模型是凸规划。第二节第二节 无约束极值问题无约束极值问题一般模型：min()nf XXR其中求解（f(X)可微）：应用极值条件求解，往往得到一个非线 性的方程组，求解十分困难。因此，求 解无约束问题一般 采用迭代法，称为下降类算法。一、下降类算法的基本步骤与算法收敛性1.基本思想基本思想00112()f XXPXPX基本思想是使逐步下降，逐渐趋近其最小值。迭代方式是从一个初始点出发，选取某

9、一搜索方向，沿该方向搜索到下一个点。若达到与最优解误差的精度要求，则停止，否则再沿该点的某一方向 搜索下一个点。这一过程如图所示：0P1P2P0X1X3X2X2.基本步骤基本步骤0:0,0Xk选取初始点，令确定精度；(1)(),(),3kkkkXf Xf XX对于点，计算若则停止,得到近似最优解，否则转（）；(2)kkXP从出发，确定搜索方向；(3)1,:1,2)kkkkkkkkPXXPXXPkk沿 方向搜索，即由 确定搜索步长得到下一个点令转(。(4)注：不同的搜索方向，就形成了不同的算法，不 同的算法所产生的点列收敛于最优解的速度 也不一样。3.收敛性收敛性衡量标准：*1*limkkkXX

10、XX1,01,kX 则称是线性收敛的；1,0,kX则称是超线性收敛的；2,0,kX 则称是二阶收敛的。二阶收敛超线性收敛线性收敛二、一维搜索:精确搜索：一维搜索分数法近似搜索 0.168法其他方法（导数信息）0min(),kkkf XP通过求极值得到最佳步长k求上面极值的近似值得到近似最佳步长1.分数法分数法（斐波那契法）2t基本思想*tOab1t1t()f tt怎样在区间中取点最好？11()()f tf t若12()()f tf t若基本概念,0nnna b记第 次缩短后的小区间为给定的精度要求为满足绝对精度：满足相对精度：|nnba|nnbab a斐波那契数：12011nnnFFFFF55

11、3421138532119876543210nFn1(1)()nnFab aF1()nnFab aFab1t1t1111112211111121-111221132,(1-)(-),(),-1,1(-)nnnnnnnnnnnnnnnnnnnFttt bFFb aFFFFFta tFFFFbaFa tttnabFFFFb aFFF FF1若按的比例在区间中对称地取点 和，经比较后去掉则 在中所占的比例为再按比例在中取 与 对称，这样反复次后所得的小区间长缩短为(),1()11-nnnnnbabaFFnb aFF与原区间长之比为：，恰为相对精度表达式。于是，开始可由解出，步骤1;nnF由 所 给

12、精 度 和定11111111111(1-)(-)()max,nnnnnnFFtb aFFFtbattttFa b由的比例在区间a,b中对称地取点=a+和=a+，比较f()和f()，去掉f(),f()相应点以外的区间得到新区间；2112121122,()()min(),(),nnFa btFf tf tf ta b在中按的比例取点与区间中所剩的点对称比较和，去掉较大者对应点以外的区间，得到新区间；32232*1-112,nnnnFa btFFabtF在中按的比例取点 再比较、再缩短，直到取完，最后的小区间中的任意一点可作为 的近似值。例5：2()2 1,38f ttt 用分数法求在区间上的近似极

13、小点，要求缩短后的区间长度不大于原区间长的。*()20,1()21 01.752ftf tftttf t 解 由于所以（）是严格的凸函数。由 ，解得是极小点，（）561111141152211180.0812.5,6,0.081381(1)3(1)0.538,()1.75113813(1)1.462,()2.675()135 ,1,1.462,851(1)1.462(1)0.077,8()2.083(),nnFFnFFtf ttf tf tFa bFtf tf t 由知查表得故2255,0.077,1.4620.538()1.751a btf t 故依此进行，得 为近似极小点，2.0.618法

14、法区别：每次取点得比例是定值0.168，即每次区间内两 点得位置均在区间相对长度得0.328和0.168处。特点：简单，更易于应用；效果也比较好。3.近似最佳步长公式近似最佳步长公式2()1()()()()2TTkkkkkkkkf Xf XPf Xf XPP H XP设存在连续的二阶偏导数，则有泰勒展开式0()()0TTkkkkkdff XPP H XPd 对 求导，并令导数为，得()()TkkTkkkf XPP H XP解得：kf X上式即为的近似最佳步长公式。当（）为二次函数时，此公式是精确的。例6：2212()(1)(1),0 0,()Tkkkkf XxxXPf X设用近似最佳步长公式求

15、。12()2(1)2(1),()2 220()()0222 22120222 2022TTkkf Xxxf XH XH X 解 ()kf X由于是二次函数，故所求是精确的。三、梯度法和共轭梯度法1.梯度法梯度法()()()()Tkkkkkf Xf XPf Xf XP设有连续的二阶偏导数，则有泰勒展开式0,()()cos0(),()()2cos1,Tkkkkkkkkkf XPf XPf XPf XPf X由于应使其中 为向量和 的夹角。为使上式成立，应使又为使的绝对值尽量大，应使-即()()kkkPf XXf XP故 即在点的负梯度方向是使下降最快的方向。以负梯度作为搜索方向 的下降类算法称为梯

16、度法或最速下降法。()0)(kkkkf XPXpXff思想：怎样选取可使下且左边差降最额快？即使尽量大。一般步骤0:0,0Xk选取初始点，令确定精度；(1)(),(),3)kkkkXf Xf XX对于点，计算若则停止计算,得到近似最优解，否则转(；(2)1(),kkkkkkkkPf XPXXP取沿 进行一维搜索，得到 和下一个点；(3)1:1,2)kf Xkk 计算（），置转(。(4)例7:22120()(1)(1)0.10 0Tf XxxX用梯度法求的极小点，取 初始点。120220()2(1)2(1),()2 2()(2)(2)8Tf Xxxf Xf X 解：0022 22021()202

17、0222 2022H X 由近似最佳步长公式求：，100010*11 ()0 0 2 21 12 ()0 0,()0 1 1TTTTTXXf Xf Xf XXX故 上例中，目标函数是同心圆族。无论初始点选在何处，在该点的负梯度方向总是指向圆心，而圆心就是极小点，故沿负梯度方向搜索一步便可得极小点。但对于一般的函数，若每次迭代均采用负梯度方向，则由于这些方向是彼此正交的，很可能形成开头几步下降较快，但后来便产生直角锯齿状的“拉锯”现象，收敛速度很慢。可以证明，梯度法是线性收敛的。注：2.共轭梯度法共轭梯度法基本概念0,TXYnAnX AYXYAAIXY设 与 均为 维向量，是 阶对称正定阵。若，

18、则称 与 关于 共轭。当则 与 正交。关于共轭，有下述重要性质：111 11,0,1,00,01nnnniTTiiiiTiiinnnPPAPPPPRP A inP APAP APPPnnA若 个非零 维向量、关于 共轭，则、线性无关。事实上 只需考虑两边分别左乘（）则有，而正定，即故，说明、线性无关。这一性质也说明不可能有个 维向量关于 共轭。1112nTTnnPPHHf XX HXC XPPn若非零 维向量、关于共轭，则以 为二次系数阵的二次函数（）沿、（称为共轭方向）进行精确一维搜索，至多经 次便可得极小点。这一性质说明采用共轭方向作为搜索方向，对二次函数求极小可以有限步终止。由此可构造二

19、次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的性质往往与二次函数很相似，因此共轭方向算法一般也可用于其他非线性函数，并且至少是线性收敛的。一般步骤0:0,0Xk选取初始点，令确定精度；1min(),kkkkkkkkXf XPXXP对求解得 和；00Pf X取（）；*110(),1,51,2kknf XXXknknXX若则停止,否则，若转，若，重置转；（重置的原因是由于计算中的舍入误差可能造成n步未终止。）1111:1,3 kkkkTkkkTkkPf XPkkf Xf Xf Xf X 取（），置转（）（）其中：（F-R法）（）（）(),()TTff X

20、X HXC Xf XHXC1当 正定，时，有211()()()()kkkkkkkkkkf Xf XH XXH XPXHP,TkP两边同时左乘有()TTkkkkkPf XP HPkk1()0TkPHPf X可以证明，按此方向构造的 是关于共轭的，并且有()TkkkTkkPf XP HP从而有 例8：2212121031()2 2 422Tf Xxxx xxX 求的极小点，取。1112221221000311()2 0112 ()32 ()12 6,()12 6TTTxxf Xxxxxf Xxxxxf XPf X 解 000001212 6 6()531121712 6116TTPf XP HP1

21、0052638 2 412 6 171717TTTXXP 1612()1717Tf X11000661217 17 171211712289 12 6 6TTf Xf Xf Xf X（）（）（）（）1100111211 111612190210()12 6 1717289289289()17,1 110TTTTTTPf XPPf XXXPP HP 22()0 01 1TTf XX由于，故即极小点，计算经两步终止。四、牛顿法与拟牛顿法1.牛顿法牛顿法牛顿方向()()1()()()()()()()2TTkkkkkkf Xf Xf Xf Xf XXXXXH XXX设有连续的二阶偏导数，由泰勒展开式，

22、可近似表示为()()()()kkkf Xf XH XXXf 从而 当 为二次函数时，上式为精确表达式。11k1()()0 ()()()0kkkkkXf Xf Xf XH XXX取使达到极小，应有，即 1k11()()()()(),kkkkkkkH XXXH Xf XPH Xf X 当可逆，可解得 记称为牛顿方向。()1()kf XXf X对于正定二次函数，采用牛顿方向作搜索方向，步长取为，从任意点出发一步即可得极小点。对于一般函数，在一定条件下，也可采用牛顿方向，所形成的算法称为牛顿法。一般步骤0:0,0Xk选取初始点，令确定精度；11()min()kkkkkkkkkkPH Xf Xf XPX

23、XP取（）,由求出和；1:1,kf Xkk计算（），置转2。(),kkXf X对于点，若则停止,否则转3；当一维搜索是精确的，牛顿法为二阶收敛。缺点：计算海赛阵的逆的工作量很大。要求f(X)的二阶导存在且海赛阵是正定的(以保证H的逆阵存在和算法是下降的);改进：构造一个矩阵 代替牛顿方向中的 ，使 满足：kHkH X-1（）kHkH 正定 只用到f(X)的一阶导信息kH随着k的增加，充分接近于*H X-1（）kH称 为尺度阵。由于它每次都在变，故称以 代替牛顿法中的 的算法为变尺度法。1()kH XkHkH2.拟牛顿法拟牛顿法拟牛顿法是尺度阵 满足 的一类变尺度法;111()()kkkkkXX

24、Hf Xf XkH拟牛顿法一般是超线性收敛的;DFP是一种著名的拟牛顿法;当f(X)为二次函数时，DFP法是共扼方向法，且具有二 次终止性。DFP方法的一般步骤0:0,0XHHIk选取初始点，和初始对称正定阵，可取（）令确定精度；11111111111111111,kkkkkkkkkTTkkkkkkkkTTkkkkkkkkkkkPHf XPXXPXXHGGHHHXGGHGXXXGf Xf X取（）沿 进行一维搜索，得 和其中：（）-（）(),kkXf X对于点，若则停止,否则转3；1:1,kf Xkk计算（），置转2。例9:2212121031()2 2 422Tf Xxxx xxX 求的极小

25、点，取。0000001212 6 6()5 31121712 6116TTPf XPP HP一维搜索，由共轭方向最佳步长公式可得沿1112221221000000311()2 0112 ()32 ,()12 6101231 ,(),()01611TTxxf Xxxxxf Xxxxxf XHPHf XH X 解 取100 0152638 2 412 6=171717612 17 17TTTTXXPf X（）000000100000060210 10106030210901717 3017170 19017170 1101717 2100 1 603017 17179017TTTTXXHG G H

26、HHXGG HG210 102109017 17170 190173852411 241 891986010010603021090 ,17171717TTXXXGf Xf X（）-（）11169385 24111729()241 89112219861729PHf X111111961229 171721()29299173192129 2929112129TTPf XPP HP沿 一维搜索，由共轭方向最佳步长公式211 1221 1,()0 01 1TTTXXPf XX故是极小点。第三节第三节 约束极值问题约束极值问题一般模型min()()0,1,().()0,1,|()0,()0min(

27、)ijnijXDf Xh XimNLP stgXjlDXRh XgXNLPf X记则（）也可以表示为1.基本概念和性质基本概念和性质起作用约束00000,XDXXXX对于点在 点等于零的约束称为对起作用的约束，在 点不等于零的约束称为对不起作用的约束。00()0,1,()0,1,()0()Xijjh Ximg XjJlg XJXj 0在 点起作用的约的不等式约束。几何意义：束包括全体等式约束和满足位于这些约束的边界上。000()0()0()XjjgXgjXXJ0的不等式约束。几何意义：在位的不起作用的约束包于这些约束括的内部。可行下降方向0000P0,XDXn方向R 在点称为是可行的 是指存在

28、正数，使对一切都有+PD;0000()()0nPRXDXPDf XPf X方向在点称为下降的 是指存在，有*NLPXX如果是（）的极小点，则在不存在可行下降方向。可行下降方向的条件()0()0()0()0iiijh Xh Xh Xg X可以化为两个不等式约束、来表示，所以讨论约束条件时可只考虑由于等不等式约束式约束。00000()0(1,)()-()0jPXg XPjlf XPf XPX由可行下降方向的定义，某方向 在 点若满足则 是 的可行下降方向。0000000 ()()()(1,)()()()TjjjTg XPg Xg XPjlf XPf Xf XPXPD 由泰勒公式其中 是足够小的正数

29、（保证）00()0()0 TjTg XPPf XPP不难看出，只要便保证 是可行下降的。这可作为 可行下降的充分条件。00000()()()-()jjPg XPf XXPg Xf X几何意义是:与夹锐角，同时 与-也夹锐角。由此可知，如果在不存在可行下降方向，则一定不存在 同时与和夹锐角。2.最优性条件最优性条件（K-T条件）0*NLP()()NLPjf Xg XX考虑只含有不等式约束的（）。设与均为连续可微函数，是（）的最有解。*0D()0XXf X如果是 的内点，即约束对是不起作用的，则由无约束极值问题的极值必要条件，有。*1*11*()0()0()()PPXg Xg XXg Xf XX如

30、果是某一个约束的边界点，即对起作用，则必有与-反向，否则必有 与二者同夹锐角，即 是 的可行下降方向，矛盾。1()g X*1()g X*()f X-*X*11()()()()g Xf Xf Xg X11故与同向，即存在0，使。*12*12*12*12()0()0()0()0()()()P()()()PXg Xg Xg Xg XXf Xg Xg Xf Xg Xg X如果位于某两个约束和的交点，即和均对起作用，则必有位于和的夹角内部，否则也会有 与、和同夹锐角，即存在可行下降方向，矛盾。*X1()g X2()gX*()f X*1()g X*2()gX12*112212()()(),0f Xg Xg

31、 X 故有 和 使下式成立：*()0()()0jjjj JjXg XjJf Xg XjJ依此类推，若点起作用约束为，则有 ，*()0jjg XX其中条件是为了在梯度组合式中去掉不起作用约束，称为松紧条件。这时要求点各起作用约束的梯度线性无关。*1*()()()0 (1,)0 (1,)ljjjjjjf Xg Xg Xjljl或表示为定理定理(K-T条件)*11*11*()(1,)()()()()()0 1,01,ijmlmliijjijjjjXNLPXh Ximg XjJf Xh Xg Xg Xjljl 设是（）的最有解，且在点各起作用约束的梯度和，线性无关，则存在向量和使下式成立：（），（）*

32、11mlK-T条件中的、和、称为广义拉格朗日乘子或K-T乘子。满足K-T条件表达式的可行点称为K-T点。可以证明K-T条件对凸规划是充要的。例10：利用KT条件求解下面的非线性规划2min()(3).05f Xxstx 212 min()(3).()0 ()50f Xxstg XxgXx解 原问题可写为 1212()20,()()0()()()fXgXgXf Xg XgX因为故解为凸函数，和均为凹函数，此问题为凸规划。为解此方程组，可分几种情况考虑：12121212()23()1,()12300 (5)0,0f Xxg Xg XK Txxx（）,条件表达式为（）*3()0 xf x由于此问题为

33、凸规划，故是最有解，相应最优值。1200且，无解；1203,xKT，解得满足约束，是 点；122005,4,xKT且，解得 不是 点；121000,6,xKT且，解得 不是 点；例11:考虑非线性规划并验证它为凸规划，用KT条件求解121212 max()ln(1)23 .,0f Xxxxxstx x 121122122 min()ln(1).()320 ()0 ()0f Xxxstg XxxgXxgXx 解 原问题可写为 计算目标和约束函数的海赛阵12131()1()2 1,()1 0,(1)()0 1-TTTTf Xg Xg Xxg XK T，表达式为：123211 00 0(1)()0,

34、()()()00 0 0 0fgggxHXHXHXHX故此问题是凸规划。111213003 2000 xxx，则无解，于是，有令 ，若，则有12120130 x12 0（）12120 xxT0，3，显然0 3是可行点，从而解得是极小点。121121122 13212312(1)13 2000,0 xxxxx -（）3.二次规划二次规划一般模型 min()120 .0,TTf XX HXC XAXbstXA m nbmCn 其中 为阶矩阵；为维非负向量；为 维向量。0K-TH 由于二次规划的约束是线性的，从而是凸集，故当目标的二次项系数矩阵（半正定）时为凸规划，可用条件求解。1122 ()()0

35、 ()0f XHXCg XAgAXbmg XIgXn 则梯度：与约束（个）相对应，与约束（个）相对应。min()120 .0TTf XX HXC XAXbstX111221()-()-,-TmTmm nggXK TYyyXK TYyyK T记相应于的乘子为，相应于的乘子为 则由条件及约束条件，有：121212 0 00 ,0TTTTTHXCAYIYYAXbY XAXbX YY（）上面的一组式子中，若不考虑两个松紧条件，则其余均为线性表达式，即：1212 0 ,0TTTHXACYIYAXbX YY 思考:能否在此基础上构想基于线性规划求解的方法?10TnZzz如果在上面第一式中增加人工变量（为使

36、出现单位阵），并增加使人工变量之和极小化的目标函数（为使人工变量最后均为），则可构造一个线性规划：11212 minsgn().,0sgn()nTsTTssHXACzzzYIYC ZstAXXbX YYZ XC ZZCX其中表示 中各分量的符号与 中相应分量的符号相同，是为了保证出现单位阵；是松弛变量。用单纯形法求解该规划的单纯形初表为下表。BX1B bXsX1Y2YZZCH0TAIsgn()C IsXbAI000121212 ,0 0TsTsX Y YY XY XYXYX为使所求得的还满足松紧条件应在每次单纯形表的迭代中保证与 以及与的相应分量不同时为基变量。例12:求解二次规划221212

37、1212min()1(22)81026 320.0,0f Xxxxxxxstxx112232 0 ,3 2,8 10,60 2 ,0,K-TTTHACbYy YyyH 显然有故此问题是凸规划。可用条件求解。解122111322132sgn()2 0380 22103 26TsHXAYIYC ZyxzyCyxzxAXXxbx1211212132123123123121 32 13 2223 min38210 .26,000,0 xxxzzzyyzyyzstxxx x x y y y z zy xy xy x相应的线性规划为求解时还要满足松紧条件、。1 1 3/13-2/13-4/39 1 4/1

38、3 0 9/26-3/13-9/26 3/13 2/13 133/13 0 132/13 0 2/3 1-2/3-4/9-26/9 3 1/3 2/3 1 2 033/13 1-2/3 -1 2/3 4/9 26/9 22/3 1 1/3-1/3 1-2/9-4/9 4/3 0 1 1 -5 1/3-2/3 1/3 2/3 1 2 0 5 1 -1 2 2 10 1 4/3 1 -1 3-2/3-4/3 4 1 1 1 -5 -2 -2 2 1 2 3 6 0 1 -1 2 2 10 1 4 1 -1 3 2 8 1 1 1 0 0 0 0 0 0BCBX1B b1x1x1x1x2x2x3x3

39、x1y1y1y2y3y1z1z1z2z2z2z2z求得的结果是：12312343332,0,0,0131313xxxyyy13131*433 13 13TyxyxxX 在每一次单纯行表迭代中都考虑了松紧条件，如在第一张表中，按通常规则应让 进基，但考虑到与它构成松紧式的 已在基中，并且 进基也不会使 出基，故选择 进基，从而所得解满足松紧条件，是原来二次规划的最优解。4.罚函数罚函数基本思想：将约束与目标组合在一起，化为无约束 极值问题求解。内点法：从可行域的内部逐步逼近最优解。外点法：从可行域的外部逐步逼近最优解。外点法的关键是基于（NLP）构造一个新的目标函数P（X，M），称为罚函数。22

40、11(,)()min(0,()()lmjijiP X Mf XMg XMh XMM式中 是一个充分大的正数，称做罚因子。含 的项称为罚项。当X是可行点时，罚项为0当X不是可行点时，罚项是很大的整数。对P（X，M）求极小，可采用无约束优化方法，罚项能保证X逐步趋近可行域。一般步骤：0,:1,0Mk1选取初始罚因子令；min(,),kkkMP X MX对于，求解无约束极值问题得；1|()|(1,)()(1,)NLP,1,2kikikkkkXh Ximg XjlXMMkk若满足可行性的精度要求 则停止，即为（）的近似最优解，否则，取置 转。,P X MM 用罚函数法求解一些简单的非线性规划时，可先求

41、出（）的驻点，然后令。例13：求解非线性规划31212min()1(1)31 0.0f Xxxxstx 32212121(,)(1)min(0,1)min(0,)3P X MxxMxMx解 构造罚函数211122 (1)2min(0,1)0 1 2min(0,)0PxMxxPMxx 令1121 01,01 0 xxx 当，不可行；当，由第二式有，矛盾，说明可行域内无驻点。122121 0,0,4112xxxMMMxM 对于可行域外的点（满足）可解得驻点 12(1)20002xMHM在该点，海赛阵 说明该驻点是极小点。T121M,0 xx令则，而 1 0满足约束，是最优解。例14：求解非线性规划22212121(,)min(0,)min(0,)P X MxxMxxMx解 构造罚函数2121112122 1 2min(0,)(2)2min(0,)0 1 2min(0,)0PMxxxMxxPMxxx 考察其驻点，令122121min()0.0f Xxxxxstx12212112121 0,0,1 2()(2)201 2()0 xxMxxxMxMxx 对于可行域外的点（满足）可解得驻点 T120,0 xMx令则，而 0 0 是可行点，故是最优解。12212(1)114(1)2xMxMM解得