最优化计算方法(工程优化)复习_new

1、 12,0,1 ,x xD 12(1),0,1,xxD D,nDR空集和单元素集也是凸集。空集和单元素集也是凸集。 三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都是凸的。是凸的。设设 若集合若集合 中任意两点的连线都属于中任意两点的连线都属于 ，则称，则称 为凸集。为凸集。因为两点因为两点 连线上任一点可以表示为连线上任一点可以表示为 12(1) ,0,1.xxx 12,x xDDD凸集的几何特征凸集的几何特征凸集的代数特征凸集的代数特征称集合称集合 为凸集为凸集 。恒有恒有 证明集合证明集合 S = x Ax = b 是凸集，其中

2、是凸集，其中A为为 m n矩阵，矩阵，b为为m维向量。维向量。0,1 , 1212(1)(1)(1),AxxAxAxbbb 12,x xS12,Axb Axb即即12(1),xxS所以所以即即S是凸集。是凸集。,nTHx xRc xb 集合集合是凸集是凸集, 称为超平面，称为超平面，c为为n维向量。维向量。邻域邻域00,|,0N xx x x 是凸集。是凸集。设设 那么称那么称 是是 的凸组合。的凸组合。 121,.,0,1,mmniiix xxRS 是凸集是凸集 S 中任意有限个点的凸组合属于中任意有限个点的凸组合属于 S。1miiix12,.,mx xx 设设 是凸集，则是凸集，则 也是凸

3、集。也是凸集。,AB AB AB,nA BR: :,: :,.ABab aA bBABa b aA bB 不一定是凸集。不一定是凸集。AB 设集合设集合 D Rn 为凸集，函数为凸集，函数 f :DR, 若若 x, y D, (0 , 1) ，均有，均有 f( x+(1- ) y ) f(x)+(1- )f(y) ，则称则称 f(x)为凸集为凸集 D 上的凸函数。上的凸函数。 若进一步有上面不等式以严格不等式成立，则称若进一步有上面不等式以严格不等式成立，则称 f(x)为凸集为凸集 D 上的上的严格凸函数严格凸函数。 当当-f(x)为凸函数为凸函数(严格凸函数严格凸函数)时，则称时，则称 f(

4、x)为为凹函数凹函数 (严格凹函数严格凹函数)。严格凸函数严格凸函数凸函数凸函数严格凹函数严格凹函数 设设D Rn 为非空凸集，函数为非空凸集，函数 f :DR 在在 D 上可微，则上可微，则 (1) f在在D上为凸函数上为凸函数 任意任意x，y D，恒有，恒有 f (y) f (x)+ f T(x)(y-x) (1) (2) f在在D上为严格凸函数上为严格凸函数 任意任意xy D，恒有，恒有 f (y) f (x)+ f T(x)(y-x) . (2)证明证明 设设D Rn 为含有内点的非空凸集，为含有内点的非空凸集，函数函数 f :DR在在 D 上二次可微，则上二次可微，则 a) f在在D

5、上为凸函数上为凸函数 x D， 2f (x) 半正定；半正定； b) 若若 x D， 2f (x) 正定，则正定，则f在在D上为严格凸函数。上为严格凸函数。回忆：回忆：设二次函数设二次函数 (1)：若：若 为半定矩阵，为半定矩阵， 在在 中为凸函数中为凸函数 ； (2)：若若 为正定矩阵，为正定矩阵， 在在 中为严格凸函数。中为严格凸函数。判断判断f(x)=5x12-6x1x2+5x22在凸集在凸集D上是否是凸函数？上是否是凸函数？ 的顺序主子式都是正的，所以正定，因此的顺序主子式都是正的，所以正定，因此f(x)在凸集在凸集D上是严格凸函数。上是严格凸函数。 2106( )6 10f x Tf

6、 xx AxA( )f xnRnR( )f xA 考虑如下非线性规划考虑如下非线性规划当当 都是凸函数时都是凸函数时,称规划称规划 为凸规划为凸规划( ),( )(1,2, )if x g x im(1) min(1). .0,1,2,if xst gxim 设设(1)为凸规划，则为凸规划，则 i) (1)的可行集的可行集R是凸集；是凸集； ii) (1)的最优解集是凸集；的最优解集是凸集； iii) (1)的任何局部极小点都是全局极小点。的任何局部极小点都是全局极小点。 设设(1)为凸规划，若为凸规划，若f(x)在非空可行集在非空可行集R上是严格凸函上是严格凸函 数，则数，则(1)的全局极小

7、点是唯一的。的全局极小点是唯一的。见书中见书中(P24)定理定理 3.11. 非线性规划的局部最优解不一定是非线性规划的局部最优解不一定是 全局最优解全局最优解,其可行解和最优解集也其可行解和最优解集也 不一定是凸集不一定是凸集,甚至不是连通集甚至不是连通集.如如 果是凸规划果是凸规划, 就有很多好的性质。就有很多好的性质。见书中见书中(P23)定理定理 3.9、3.10.n=1时，是一维无约束优化问题时，是一维无约束优化问题-n1时，是多维无约束优化问题时，是多维无约束优化问题-n元函数元函数求解无约束优化问题求解无约束优化问题min( )nx Rf x:nf RR找初始点找初始点判断当前点

8、是否满判断当前点是否满足终止条件足终止条件下一个迭代点下一个迭代点 最优解最优解(a) 找初始点找初始点(b) 终止条件终止条件(c) 迭代格式迭代格式是是否否循循环环kkd1kxkdkdmin( )nx Rf x()kkf xdk求目标函数求目标函数 f(x) 的极小：的极小：由于这项工作是求以由于这项工作是求以 为变量的一元函数为变量的一元函数的极小点的极小点，故常称这一过程为，故常称这一过程为（精确）一维搜索或（精确）一维搜索或（精确）线搜索或一维最优化（精确）线搜索或一维最优化，确定的步长为最佳步长。，确定的步长为最佳步长。: argmin ()kkkf xd( )f x1kx1min

9、 ()kkkkkkkf xdxxd1 T()0.kkf xd 设目标函数设目标函数具有一阶连续偏导数，具有一阶连续偏导数，规则产生规则产生则有则有按下述按下述函数函数 ，则得，则得( )()kkf xd min kT+1 T0( )()()().kkkkkkkkf xddf xd ( ) k基本思想：一种试探法：从一点出发，按一定步长搜索新点，基本思想：一种试探法：从一点出发，按一定步长搜索新点，若搜索成功，加大步长继续搜索；若搜索失败，缩小步长小若搜索成功，加大步长继续搜索；若搜索失败，缩小步长小步后退。步后退。步骤步骤1：选取初始点选取初始点 xR , 初始步长初始步长 h 0 及精度及精

10、度 0，步骤步骤2：计算：计算步骤步骤3：若：若 搜索成功搜索成功, 转步骤转步骤4；否则，搜索失败，；否则，搜索失败， 转步骤转步骤5。步骤步骤4：令：令 x:= x + h, 转步骤转步骤 2。步骤步骤5：判断：判断 若若 停止迭代，停止迭代， ；否则令；否则令 转步骤转步骤 2。缺点：效率低。优点：可以求缺点：效率低。优点：可以求搜索区间搜索区间。1( ).f x2().f xh21,12:,:2hh?hh ，*xx,4hh 注意：初始步长不能选得太小注意：初始步长不能选得太小：设给定初始点：设给定初始点为为 a 及初始步长为及初始步长为 h, 求搜索区间求搜索区间c, d 1) 前进运

11、算前进运算首先计算首先计算 f (a), f (a+h), 如果如果 f (a) f (a+h), 则步长加倍则步长加倍, 计计算算f (a+3h). 若若 f (a+h)= f (a+3h), 则则c=a, d=a+3h; 否则将步否则将步长再加倍，并重复上面运算长再加倍，并重复上面运算. 2) 后退运算后退运算如果如果 f (a) f (a+h), 则将步长缩为原来的则将步长缩为原来的1/4并改变符号，即并改变符号，即将步长改为将步长改为-h/4, 如果如果 f (a) f (a-h/4),则则c=a-h /4,d=a+h; 否则否则将步长加倍，并继续后退。将步长加倍，并继续后退。注意注意

12、: 1. h 选择要适当选择要适当.(太大含多个单峰区间太大含多个单峰区间,太小迭代次数多太小迭代次数多)； 2. f (x)单调时无结果单调时无结果, (加迭代次数限制加迭代次数限制)； ：利用利用“成功成功-失败失败”法求函数法求函数 的搜索区间，的搜索区间， 取初始点取初始点 ，步长，步长取初始点取初始点 ，步长，步长3( )21f xxx115 ( )(),28f xf( )()f xf xh因为，12x 1.2h 12x 1,2h 11 ()()(0)1,22f xhff搜索成功，步长加倍；11 (+2 )(3 )(3)(1)0,22f xhhf xhff计算()(3 )f xhf

13、xh因为， 搜索成功，步长加倍；11 (3 +4 )(7 )(7)(3)22,22f xhhf xhff计算(3 )(7 )f xhf xh因为， 搜索失败，停止迭代；,7 0,3.xh xh得到搜索区间为得到搜索区间为 0.618法是求单峰函数极值的一种试探法，有的书上也称为区法是求单峰函数极值的一种试探法，有的书上也称为区间收缩法。间收缩法。 在搜索区间在搜索区间a,b上插入两个点，将分为三个子区间，通过比较上插入两个点，将分为三个子区间，通过比较2个插入点的函数值的大小，可删去左边或者右边区间，使搜索个插入点的函数值的大小，可删去左边或者右边区间，使搜索区区间缩短。重复上述过程，使搜索区

14、间不断缩短，当区间缩短到一间缩短。重复上述过程，使搜索区间不断缩短，当区间缩短到一定程度时，区间上各点都可以作为极小点的近似。定程度时，区间上各点都可以作为极小点的近似。 仅适用于求解单峰函数仅适用于求解单峰函数：设设 f(x) 是定义在是定义在a, b上的函数，若上的函数，若 1） x* a, b 是是在在a, b上的最小点上的最小点 ， 2） 若对任意若对任意 x1 , x2, a x1 f (x2); 2 若若x1 x* ，则，则 f (x1) f (x2).则称则称 f(x) 为为a, b上的单峰函数。上的单峰函数。 设设 f：RR 在在a, b 上是单峰函数，上是单峰函数， a x1

15、 x2 b 。 那么那么 1若若 f (x1) f (x2)，则，则 x* x1 , b ,如左下图如左下图 2若若 f (x1) f (x2) ，则，则 x* a, x2 , 如右下图如右下图 a x1 x2 b a x1 x2 b考虑条件：考虑条件： 2对称原则：对称原则： x1 a = b- x2 （使（使“坏坏”的情况去掉，区间长度不小于的情况去掉，区间长度不小于“好好”的情况）的情况） 3保持缩减比原则保持缩减比原则 t =(保留的区间长度原区间长度保留的区间长度原区间长度) 不变。不变。 （使每次保留下来的节点，（使每次保留下来的节点， x1或或 x2 ，在下一次的比较中成，在下一

16、次的比较中成 为一个相应比例位置的节点为一个相应比例位置的节点 ）。）。 推导缩减比推导缩减比 t : 如图设第一次保留如图设第一次保留a, x2 (去掉去掉x2 , b), 第二次第二次保留的长度为保留的长度为, x1 , 则则 x1 x2 b212(2)xxtbx整理整理 ： x2 = a + t ( b - ) x1 = a + t ( x2 -)结合式：结合式：t 2 + t 1 = 0 故故 t0.618注意注意: 上式有上式有 t 2 = 1-t , 故有故有 x1 = a+(1-t)(b-a)=a+0.328(b-a) x2 = a+t(b-a)= a+0.618(b-a)(25

17、1舍去负值t 优点：不要求函数可微，且每次迭代只需计算一优点：不要求函数可微，且每次迭代只需计算一 个函数值，计算量小，程序简单个函数值，计算量小，程序简单缺点：收敛速度慢。缺点：收敛速度慢。黄金分割法（黄金分割法（0.618 法）的优缺点法）的优缺点 ：试用试用0.618法求目标函数法求目标函数 的最优解。的最优解。 给定初始区间给定初始区间0,2，收敛精度，收敛精度第一次区间缩短计算过程：第一次区间缩短计算过程：计算两点及对应函数值：计算两点及对应函数值： 作数值比较，可见作数值比较，可见 ,再做置换：再做置换：3( )21f xxx2:1.236,bx=0.002.0,2ab10.382

18、()0.764,xaba1 ()0.0821, f x20.618()1.236,xaba2()0.4162,f x12()()f xf x1.2360.002ba20.764,x2 ()0.0821, f x , 0,1.236,a b第二次区间缩短计算过程：第二次区间缩短计算过程： 作数值比较，作数值比较， , ,再做置换：再做置换：10.382()0.472,xaba1 ()0.1612,f x12()()f xf x1:0.472,ax0.7880.002;ba第三次区间缩短计算过程：第三次区间缩短计算过程： 作数值比较，作数值比较， , ,再做置换：再做置换：2:0.944,bx20

19、.618()0.944,xaba2 ()0.0468, f x12()()f xf x0.4720.002ba22 , 0,1.236,0.764,()0.0821,a bxf x , 0.472,1.236,a b 110.764,( )0.0821,xf x 220.764,()0.0821,xf x , 0.472,0.944,a b 各次的迭代结果如下：各次的迭代结果如下：迭代次数迭代次数x1x2f (x1)f (x2)a,b|b-a|第第1次次0.7641.236-0.08210.41260,1.2361.236第第2次次0.4720.7640.1612-0.0821 0.472,1

20、.236 0.788第第3次次0.7640.944-0.0821 -0.0468 0.472,0.944 0.472第第4次次0.6520.764-0.0268 -0.0821 0.652,0.944 0.292第第5次次0.7640.832-0.0821 -0.0881 0.764,0.944 0.230第第6次次0.8320.906-0.0881 -0.0683 0.764,0.906 0.124缺点：收敛速度慢缺点：收敛速度慢优点：不要求函数可微，且每次迭代只需计算一个函数优点：不要求函数可微，且每次迭代只需计算一个函数 值，计算量小值，计算量小 设设 f (x)在在 a ,b上可微，求

21、函数上可微，求函数f在在a,b的极小点，就是求的极小点，就是求函数导数为零的点。如果函数导数为零的点。如果 ，则在，则在(a,b)内一定存在一点内一定存在一点x，使得，使得 。为求极小点，可取。为求极小点，可取 ，若，若 , x 为最小点为最小点, x= x0 ; , x0 在上升段在上升段, x* x0，去掉，去掉a, x0 .00fx00fx00fx 0,0,fafb 0fx02abx用用 或者或者 作新的区间作新的区间a,b，继续这个过程，继续这个过程，逐步将区间逐步将区间a,b缩小，缩小，当区间当区间a,b的长度充分小时，可将的长度充分小时，可将a,b的中点取做极小的中点取做极小点的近

22、似点的近似点。点。 0, a x0,x b优点：计算量较少，而且总能收敛到一个局部极小点。优点：计算量较少，而且总能收敛到一个局部极小点。缺点：收敛速度较慢缺点：收敛速度较慢0=2abx步骤步骤1：计算：计算步骤步骤2：若：若 ，令，令 ，转步骤，转步骤3； 若若 ，令，令 ，转步骤，转步骤3； 若若 ，停止，停止， 。步骤步骤3：若：若 ，则，则 ，停止，否则，转步骤，停止，否则，转步骤1.0ax00fx00fx00fx0bx0*xx|b a *2abx ：试用二分法求目标函数试用二分法求目标函数 的最优解。的最优解。 给定初始区间给定初始区间0,2，收敛精度，收敛精度在在0,2内有极小点。

23、内有极小点。3( )21f xxx0:1,bx故=0.004.(0)=2,(2)=10,ff01,2abx10.004;ba , 0,1,a b 第一次区间缩短计算过程：第一次区间缩短计算过程：2( )32,fxx因为因为所以函数所以函数3( )21f xxx0()= (1)10fxf ，第二次区间缩短计算过程：第二次区间缩短计算过程：第三次区间缩短计算过程：第三次区间缩短计算过程：2 , 0,1,( )32,a bfxx1 , ,1,2a b 01:,2ax故01,22abx10.004;2ba015()= ()024fxf ，3 , ,1,4a b 03:,4ax故03,24abx10.0

24、04;4ba035()= ()0416fxf ，各次的迭代结果如下：各次的迭代结果如下：迭代迭代9次后，次后，|b-a|=0.003910.004, 故故迭代次数迭代次数x0=(a+b)/2f(x0)a,b|b-a|第第1次次x0=110,11第第2次次x0=1/2-5/41/2,11/2第第3次次x0=3/4-5/163/4,11/4第第4次次x0=7/819/643/4,7/81/8第第5次次x0=13/16-0.019513/16,7/81/16第第6次次x0=27/320.013613/16,27/321/32第第7次次x0=53/640.057413/16,53/641/64第第8次

25、次x0=105/1280.018413/16,105/1281/128第第9次次x0=209/256-0.0004209/256,105/1281/256*0.81836.x 对对 f (x) 在在 x k 点二阶泰勒展开：点二阶泰勒展开：略去高阶项得略去高阶项得两边对两边对x求导，求导，令令 ，得到，得到 牛顿法是一种函数逼近法，牛顿法是一种函数逼近法，基本思想是：基本思想是：在极小点附近用在极小点附近用函数的二阶泰勒多项式近似代替目标函数，从而求得目标函数函数的二阶泰勒多项式近似代替目标函数，从而求得目标函数的极小点的近似值。的极小点的近似值。221( )()()()()()() )2kk

26、kkkkf xf xfxxxfxxxo xx21( )()()()()()2kkkkkf xf xf xxxfxxx( )()()()kkkf xf xfxxx( )=0f x()()kkkf xxxfx取取 作为新的迭代点，继续迭代，直到达到精度，这样就得到了作为新的迭代点，继续迭代，直到达到精度，这样就得到了函数函数 f 的一个驻点的一个驻点 。1()=()kkkkf xxxfx*x步骤步骤1：给定初始点：给定初始点 令令 。步骤步骤2：计算：计算 。步骤步骤3：若：若 ，停止，停止， ，否则转步骤，否则转步骤4。步骤步骤4：计算：计算 令令 ，转步骤，转步骤2。10,xR，1k (),(

27、)kkf xfx()kf x*kxx1()=()kkkkf xxxfx1kk 特点：收敛速度快，局部二阶收敛。特点：收敛速度快，局部二阶收敛。缺点：须计算二次导数，工作量大；对初始点要求高，要求初缺点：须计算二次导数，工作量大；对初始点要求高，要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点；局部收敛小点；局部收敛。 ：试用试用Newton法求函数法求函数 的最优解。的最优解。432( )46164f xxxxx206,10 x0100()()fxxxfx(6)89664.75(6)69ff1211()()fxxxfx(4.

28、75)84.944.75=4.75=4.163(4.75)144.75ff21()(4.75)84.9410,fxf继续迭代；22()(4.163)14.66610,fxf继续迭代；32( )4121216,fxxxx2( )122412,fxxx2322()()fxxxfx(4.163)14.6664.1634.1634.010(4.163)96.055ff3433()()fxxxfx(4.010)0.84364.010=4.010=4.00004(4.010)84.7212ff24.163x 33()(4.010)0.843610,fxf继续迭代；24()(4.00004)0.003410

29、,fxf得到近似解得到近似解*4.00004.x 用用 在在2 个或个或3 个点的函数值或导数值，构造个点的函数值或导数值，构造2 次或次或3次多项式作为次多项式作为 的近似值，以这多项式的极小点作为新的的近似值，以这多项式的极小点作为新的迭代点。包含迭代点。包含3点点2次，次，2点点2次，次，4点点3次，次，3点点3次，次，2点点3次等次等插值法插值法. 下面以下面以3点点2次插值法（二次插值法）为例：次插值法（二次插值法）为例：利用利用 在区间在区间 的函数值的函数值123xxx yf x 123fxfxfx作出如下的二次插值多项式作出如下的二次插值多项式 2012P xaa xa x它应

30、满足条件它应满足条件 210112111P xaa xa xffx（1） P x P x 220122222P xaa xa xffx 230132333P xaa xa xffx（2）（3）从极值的必要条件从极值的必要条件 求得求得 1220Pxaa x 12/ 2xaa 求出系数求出系数 和和 ，就可得到极小点的表达式。，就可得到极小点的表达式。1a2a 222222231312123122313121231/ 22xxfxxfxxfxaaxxfxxfxxf 11213212113121213231/ 2()2,.cxaaxxcffcffxxccxxxx 1. 寻找满足如下条件的点（成功失

31、败法寻找），成为两头大寻找满足如下条件的点（成功失败法寻找），成为两头大中间小的点：中间小的点： x 1 x 2 f (x2 ), f (x2 ) 0 , 则则 为为g(x)的极小值点，且的极小值点，且3.若若 ，则迭代结束，取，则迭代结束，取 ，否则在点，否则在点 中中，选取使，选取使f (x) 最小的点作为新的最小的点作为新的x2，并使新的并使新的x 1 ， x3各是新的各是新的x2近旁的左右两点，继续进行迭代，直到满近旁的左右两点，继续进行迭代，直到满足终止准则。足终止准则。x13,xx x2xx*xx123,x x x x算法思路：算法思路：2）用二次插值法逼近极小点）用二次插值法逼近

32、极小点(1) 相邻三点及其函数值相邻三点及其函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 1121321/ 2()2cxaaxxc ,例用二次插值法求函数例用二次插值法求函数f(x)=3x3-4x+2的极小点，的极小点， 给定给定 x0=0, h=1, =0.2。解：解：1）确定初始搜索区间）确定初始搜索区间初始区间初始区间a,b=0,2, 另有一中间点另有一中间点x2=1。1211312121323,ffcffxxccxxxx0 5550 292xf x.,( ).,根据公式计算差值多项式的极小点根据公式计算差值多项式的极小点 (2) 在新区间，相邻三点

33、及其函数值在新区间，相邻三点及其函数值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1.故新区间故新区间a,b=a,x2=0,1， 应继续迭代。应继续迭代。0 5550 292xf x.,( ).,x1=0, x2=1, x3=2; f1=2, f2=1, f3=18220 2921,0.5551,f xfxx( ).由于由于210.5550.4450.2,xx 1121321/ 2()2cxaaxxc ,1211312121323,ffcffxxccxxxx0 6070 243xf x.,( ).,根据公式计算差值多项式的极小点根据公式计算差值多项式的

34、极小点故新区间故新区间a,b=x2,b=0.555,1， 迭代终止。迭代终止。x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1220 2430.292,0.6070.555,f xfxx( ).0, e 为全为全1的的m维列向量。维列向量。(7）是可行的）是可行的,基本可行解基本可行解 由于大由于大M是充分大的正数，在极小化目标函数的过程中，就是充分大的正数，在极小化目标函数的过程中，就会迫使人工变量离基。会迫使人工变量离基。同时修改目标函数，加上惩罚项同时修改目标函数，加上惩罚项minTTafc xMe x(7) 用单纯形法求解用单纯形法求解(7)，(ii

35、) 当当 时，时， (7)无可行解。无可行解。. .0,aAxxbstxminTTafc xMe x(7)*axx(i) 当当 时时, x*是问题是问题(*)的最优解。的最优解。*=0axmin. .(*)0Tfc xAxbstx*0ax 事实上，如果事实上，如果(*)存在可行解存在可行解 ，则，则 是是(7)的可行的可行解，对应解，对应(7)的目标函数值是的目标函数值是 x0 axxx0TTc xMe是是(7)的最优解的最优解*axxTc x*TTac xMe x在单纯形表中在单纯形表中max()0,0,Nkkjjkj Rzczcy0ax. .0,aAxxbstxminTTafc xMe x

36、(7)(i) 当当 时，时，问题问题(LP)无界无界;min. .()0Tfc xAxbstLPx(ii) 当当 时，时，即即 ，问题，问题(LP)无可行解无可行解.0ax0Tae x 利用大利用大M法求解如下的线性规划问题。法求解如下的线性规划问题。 min x1+x2 -3x3 s.t. x1 -2x2 + x3 11 2x1 + x2 - 4x3 3 x1 - 2x3 = 1 x1, x2 , x3 0解解： 1. 将问题化成标准形式将问题化成标准形式，引进松弛变量，引进松弛变量x4 ,x5min x1+x2 -3x3 s.t. x1 -2x2 + x3 + x4 = 11 2x1 +

37、x2 - 4x3 - x5 = 3 x1 - 2x3 = 1 xj,0, j=1,2,5系数矩阵系数矩阵中不包含中不包含单位矩阵单位矩阵2. 引进人工变量引进人工变量x6 ,x7 构造单位矩阵构造单位矩阵，用单纯形法求解下列问题用单纯形法求解下列问题min x1+x2 -3x3+ M(x6 +x7) s.t. x1 -2x2 + x3 + x4 = 11 2x1 + x2 - 4x3 - x5 + x 6 = 3 x1 - 2x3 + x 7 = 1 xj,0, j=1,2,73. x4 ，x6 ， x 7 对应的是单位矩阵，可选择作为基变量，建立对应的是单位矩阵，可选择作为基变量，建立单纯形

38、表，利用主元消去法，进行迭代。单纯形表，利用主元消去法，进行迭代。xB x1 x2 x3 x4 x5 x6 x7 x4x6x711 3 13M-1 M-1 -6M+3 0 -M 0 0 x4x6x1 10 1 1 0 M-1 1 0 -M 0 1-3McBb j0MM113/2 1 j - 1 - 0M 1x4x2x1 j 12 1 1011c 1 1 -3 0 0 M M1 -2 1 1 0 0 02 1 -4 0 -1 1 01 0 -2 0 0 0 1min x1+x2 -3x3+ M(x6 +x7) s.t. x1 -2x2 + x3 + x4 = 11 2x1 + x2 - 4x3

39、- x5 + x 6 = 3 x1 - 2x3 + x 7 = 1 xj,0, j=1,2,70 -2 3 1 0 0 -10 1 0 0 -1 1 -21 0 -2 0 0 0 10 0 3 1 -2 2 -50 1 0 0 -1 1 -21 0 -2 0 0 0 1 0 0 1 0 -1 1-M -1-M 4 - - 0 0 0 -1/3 -1/3 1/3-M 2/3-M 4 1 9xB x1 x2 x3 x4 x5 x6 x7 cBbx4x2x1 j12 1 1011c 1 1 -3 0 0 M M0 0 3 1 -2 2 -50 1 0 0 -1 1 -21 0 -2 0 0 0 1

40、0 0 1 0 -1 1-M -1-M 4 - -x3x2x1 j-3 1 10 0 1 1/3 -2/3 2/3 -5/30 1 0 0 -1 1 -21 0 0 2/3 -4/3 4/3 -7/34. 检验数全部小于等于检验数全部小于等于0，并且人工变量全取，并且人工变量全取0， 于是得到最优解：于是得到最优解：最优值为：最优值为： f = 9+1-3*4=- 2 x = (9,1,4)T特点：目标函数求极小值，约束条件特点：目标函数求极小值，约束条件“”，变量非负，变量非负; 目标函数求极大值，约束条件目标函数求极大值，约束条件“”，变量非负，变量非负; : min. .0TPc xs

41、tAxbx: max. .0TTTDb ys ty Acy互为对偶互为对偶b不一定是非负的 一般称不具有对称形式的一对线性规划为非对称形式的对一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。偶规划。 方法一：方法一： 对于非对称形式的线性规划，可以先化成对称形式的线性对于非对称形式的线性规划，可以先化成对称形式的线性规划，写出其对偶规划。规划，写出其对偶规划。123123123123123min284. .33305480424500,0,zxxxst xxxxxxxxxxxx无限制写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题12312354805480 xxxxxx

42、 110 xx 33333,0 xxxx x=12342450 xxx 123312331233123312331233min284(). .33()3054()8054()80424()50,0zxxxxstxxxxxxxxxxxxxxxxx x x x 123412341234123412341234max3080()50. .()4235()2834()4434()44,0wyyyystyyyyyyyyyyyyyyyyy yyy : min. .0TPc xs tAxbx: max. .0TTTDb ys ty Acy123412341234123412341234max3080()50

43、. .()4235()2834()4434()44,0wyyyystyyyyyyyyyyyyyyyyy yyy 154154154154145max308050. .423528344=4,0,wyyystyyyyyyyyyy yy无限制523=yyy无限制123434()4=4yyyy154154154154145max308050. .423528344=40,0,wyyystyyyyyyyyyyyy无限制44=0yy123123123123123max308050. .43523440,0wyyystyyyyyyyyyyyy无限制,123123123123min284. .3330548

44、042450zxxxst xxxxxxxxx 10,x 20,x 3x 无限制284原问题原问题对偶问题对偶问题123123123123123min284. .33305480424500,0,zxxxst xxxxxxxxxxxx无限制min. .0Tc xs tAxbxmax. .0TTTb ys ty Acymin. .0Tc xs tAxbAxbx min. .0Tc xAbs txAbxmax (,). . (,),0TTTTTbuvbAs tuvcAu v对偶问题对偶问题max (). . (),0TTTTTuvbs tuvAcu vyuv min. .0Tc xstAxbxmax

45、. .TTTy bsty Ac变量数：变量数：n个个第第 j 个变量个变量 0第第 j 个变量个变量 0第第 j 个变量是自由变量个变量是自由变量 约束条件：约束条件： m个个第第i个约束类型为个约束类型为“”第第i个约束类型为个约束类型为“”第第i个约束类型为个约束类型为“” 目标函数目标函数max对偶问题（原问题）对偶问题（原问题）约束条件：约束条件：n个个第第 j 个约束类型为个约束类型为“”第第 j 个约束类型为个约束类型为“”第第 j 个约束类型为个约束类型为“” 变量数：变量数： m个个第第i个变量个变量 0第第i个变量个变量 0第第i个变量是自由变量个变量是自由变量 目标函数目标

46、函数 min原问题（对偶问题）原问题（对偶问题）方法二：方法二：按照下面的对应关系直接给出其对偶规划按照下面的对应关系直接给出其对偶规划: :123123123123min284. .3354424zxxxst xxxxxxxxx10,x 20,x 3x 无限制123123123123max308050. .4352344wyyystyyyyyyyyy28480305010,y 2y 无限制，30y 变量数：变量数：n个个第第 j 个变量个变量 0第第 j 个变量个变量 0第第 j 个变量是自由变量个变量是自由变量 约束条件：约束条件： m个个第第i个约束类型为个约束类型为“”第第i个约束类型

47、为个约束类型为“”第第i个约束类型为个约束类型为“” 目标函数目标函数max对偶问题（原问题）对偶问题（原问题）约束条件：约束条件：n个个第第 j 个约束类型为个约束类型为“”第第 j 个约束类型为个约束类型为“”第第 j 个约束类型为个约束类型为“” 变量数：变量数： m个个第第i个变量个变量 0第第i个变量个变量 0第第i个变量是自由变量个变量是自由变量 目标函数目标函数 min原问题（对偶问题）原问题（对偶问题）对偶问题的对偶是原问题对偶问题的对偶是原问题min. .0Tc xs tAxbxmax. .0TTTb ys ty Acy设设 分别是原问题分别是原问题 和对偶问题和对偶问题的可

48、行解的可行解, 则则 原问题任一可行解对应的目标函数值不小于其对偶问题的任原问题任一可行解对应的目标函数值不小于其对偶问题的任一可行解对应目标函数值。一可行解对应目标函数值。min. .0Tc xs tAxbxmax. .0TTTb ys ty Acy,x y.TTc xy bTc xTy AxTy b0 x TTy Ac0y Axb设设 分别是原问题分别是原问题 和对偶问题和对偶问题的可行解的可行解, 若若 则则 分别是它们的最优解。分别是它们的最优解。min. .0Tc xs tAxbxmax. .0TTTb ys ty Acy,x y,TTc xy b,x y若原问题若原问题 有最优解，

49、则其对偶问题有最优解，则其对偶问题一定有最优解一定有最优解, 且它们的目标函数值相等。且它们的目标函数值相等。min. .0Tc xs tAxbxmax. .0TTTb ys ty Acy约束优化问题的一般形式约束优化问题的一般形式( )0( )0( )0jjjh xh xh x因为因为一般形式也可写为一般形式也可写为min( ). .( )0(*)f xst g x min( ). .( )0,1,2,.,(1)( )0,1,2,.,ijf xst g ximh xjl,xD( )0ig x ( )0ig x ( )，I x( ) |( )0,1,2, .iI xi g xim设可行解设可行

50、解，则称，则称是在是在处的处的积极积极约束约束指标集，记为指标集，记为若若x积极约束指标的全体组成的集合，称为积极约束指标的全体组成的集合，称为 处的积极约束处的积极约束xmin( ). .( )0,1,2,.,(1)( )0,1,2,.,ijf xst g ximh xjl或称紧约束、或称紧约束、起用作约束。起用作约束。处的处的,xD( )0ig x ( )0ig x ( ) |( )0,1,2,.iI xi gxim设设，则称，则称是在是在处的处的积极积极约束或称紧约束、约束或称紧约束、在在 积极约束指标集积极约束指标集若若xxmin( ). .( )0,1,2,.,(1)( )0,1,2

51、,.,ijf xst g ximh xjl222112212( )20,( )10,g xxxgxxx 2122( )2()0,22g x 22222( )()()1 0,22g x 22(,) ,22Tx 31( )0.gxx求在求在 的起作用约束集。的起作用约束集。x32( )0,2gx ( )1,2.I x令令因为因为起用作约束。起用作约束。 为为(1)的可行点，的可行点， 处可微，处可微， 在在 处连续处连续, 在在 处连续处连续 向量集向量集 线性无关。线性无关。若若 是是(1)的局部最优解，的局部最优解，使得使得x证明：参见陈宝林书证明：参见陈宝林书 P253.x( )( )0 ,

52、iI xi g x( )ig iI xx( )iw iI x(1, )jvjl ( )1( )( )( )00,( )liijji I xjif xwg xvh xwiI x( ),( )( ),1,ijg xh x iI xjl (2)min( ). .( )0,1,2,.,(1)( )0,1,2,.,ijf xst g ximh xjlxx,( )if g iI x(1,., )jhjl在在可微，可微，则存在则存在 和和x( )ig iI x( )1( )( )( )00,( )liijji I xjif xwg xvh xwiI x(2)定理中的条件定理中的条件 在在 处连续变为连续可微

53、，则处连续变为连续可微，则11( )( )( )00,1,.,( )0,1,.,mliijjijiiif xwg xvh xwimw g xim(3)当当 时，时， ，由，由(3)可知，可知， 从从(3)中自然消失中自然消失,得到得到(2).( )iI x( )0ig x 0,iw ( )0( )iwg xiI x( )1( )( )( )00,( )liijji I xjif xwg xvh xwiI x(2)11( )( )( )00,1,.,( )0,1,.,mliijjijiiif xwg xvh xwimw g xim(3) (1)的一阶必要条件是由的一阶必要条件是由Kuhn和和Tu

54、chker与与1951年提出，年提出，故一阶必要条件称为故一阶必要条件称为K-T条件，条件，互补松弛条件互补松弛条件 1939年，年，Karush也类似考虑了约束优化的最优性条件，故一也类似考虑了约束优化的最优性条件，故一阶必要条件称作阶必要条件称作K-K-T条件，将条件，将K-T点称作点称作K-K-T点。点。满足满足(2)或或(3)的点是的点是K-T点。点。11( , , )( )( )( )(4)mliijjijL x w vf xw g xv h x11( )( )( )0mliijjijf xwg xvh x与与(3)中的第一个式子密切相关的是下面一个函数：中的第一个式子密切相关的是下

55、面一个函数：0 11( )( )( )mliijjijf xwg xvh x (3)( , , )xL x w v函数函数(4)的思想可追溯到的思想可追溯到Lagrange，故常被称为，故常被称为Lagrange函数，函数，其中其中 称为称为Lagrange乘子向量。乘子向量。11(,.,) ,( ,.,)TTmlwwwvvv0,1,.,( )0,1,.,iiiwimw g xim( )1( )( )( )00,( )liijji I xjif xwg xvh xwiI x(2)11( )( )( )00,1,.,( )0,1,.,mliijjijiiif xwg xvh xwimw g xi

56、m(3)满足满足(2)或或(3)的点是的点是K-T点点 若题目要求若题目要求K-T点点 求解求解(3.1)(3.3)，的的 就是就是K-T点点; 若验证某点若验证某点 是否为是否为K-T点，求解点，求解(2.1)，它们的解中使得，它们的解中使得(2.2)成立的成立的 就是就是K-T点点 .(2.1)(2.2)(3.1)(3.2)(3.3), xxxxnm l 个未知量nm个方程它们的解中使得它们的解中使得(3.2)成立成立123( )2,3xf xx21( ),gxx32( ),gxx 求约束极值问题求约束极值问题记记的的K-T点。点。112( )4,g xxx2212121212min( )

57、6684. .00f xxxxxxxstxx则则11( ),1g x21( ),0gx 30( ),1gx 11232311003101xx 31( )( )0,iiif xg x由由K-T条件条件得到得到11( )( )( )0 (3.1)0,1,.,(3.2)( )0,1,.,(3.3)mliijjijiiif xwg xvhxwimw g xim11232311003101xx 0,( )0,1,2,3iiig xi由由K-T约束条件约束条件21( )0gxx32( )0gxx112( )40g xxx再加上问题本身的约束条件再加上问题本身的约束条件联立联立(1-1),(1-2)和和(1

58、-3),求求x和相应的乘子和相应的乘子 1122133(1 1)3xx123,0 121240,0,0(13)xxxx1122132(4)000 xxxx(12)11( )( )( )0 (3.1)0,1,.,(3.2)( )0,1,.,(3.3)mliijjijiiif xwg xvhxwimw g xim， 得到得到12(1)0:xx若1121(4)00 xx由可得123 23 20 与矛盾。:0,0)2(21 xx若若30 2112x33 22x0 22x0 20 与矛盾。2 13200 xx11221333xx112(4)0 xx121212340,0,0 xxx x 1113x33

59、13x0 31x0 30 与矛盾。2 13200 xx11221333xx112(4)0 xx121212340,0,0 xxx x :0,0)3(21 xx若若20 :0,0)4(21 xx若若230 421 xx若若10 321 xx4621 xx矛盾。矛盾。421 xx221 xx11 22 1121x3x3 11221333xx112(4)0 xx2 13200 xx121212340,0,0 xxx x 12xx是是K-T点。点。1(1,1)Tx 2(0,0)Tx 221221212min(2)6. .00 xxstxxxx22212112212( )(2)6,( ),( )f xx

60、xg xxxgxxx112222(2)11( ),( ),( )221xf xg xgxxx11112211(),(),()221f xg xgx12( )0,( )0gxgx验证点验证点是否为是否为K-T点？点？记记 在点在点处，处，都是起作用约束，都是起作用约束，则则 1(1,1)Tx 目标函数和约束函数的梯度分别是目标函数和约束函数的梯度分别是( )( )( )0(2)0,( )iii I xif xw g xwi I x1( )ljjjv h x11112211(),(),()221f xg xgx故点故点是是K-T点。点。1(1,1)Tx 设设1221102210 121220220