常用无约束最优化方法-单纯形.ppt

§5.8 单纯形法;目录;;一、单纯形法基本原理 ;;算出X5 的函数值f(X5 ),可能有下列情形: ⑴ f(X5)f(X3). 搜索方向正确,可进一步扩张,继续沿X1X5向前搜索(扩张). , 其中α为扩张因子,可取 如f(X6)f(X5),则扩张有利,以X6代替X1构新单纯形{X2,X3,X6}.如f(X6)f(X5),则扩张不利,舍去X6,以X5代替X1构新单纯形{X2,X3,X5}. ;⑵ f(X3)f(X5)f(X2). 这说明搜索方向正确,无须扩张,以X5代替 X1构成新的单纯形{X2,X3,X5}. ⑶ f(X2)f(X5)f(X1). 这表示X5走得太远,应缩回一些.若以β表示压缩因子, 则有 常取β为0.5,以X7代替X1构成新的单纯形{X2,X3,X7}. ;⑷ f(X5)f(X1). ;;二、单纯形法迭代步骤 ;;⑶计算XH之外各点的“重心” 求出反射点 ⑷扩张 当f(Xn+2)f(XL),需扩张,令 如f(Xn+3)f(Xn+2),则以Xn+3代替XH形成一新单纯形;否则,以代Xn+2替XH构成新单纯形.转(8). ⑸无扩缩 当f(XL)≤f(Xn+2)f(XG),以代Xn+2替XH构成新单纯形.转(8). ;⑹收缩. 当f(XG)≤f(Xn+2)f(XH)时,则需收缩,令 以代Xn+4替XH构成新单纯形.并转(8). ⑺缩边. 当f(XH)≤f(Xn+2),令 ,如果f(XH)≤f(Xn+5),则将单纯形缩边,可将向量Xi-XL的长度缩小一半,即 这样可得一新单纯形.否则,以Xn+5代替XH形成一新单纯形.转(8). ;⑻收敛性检验 每次得新单纯形后,即应进行收敛性检验,如满足收敛指标,则迭代停止,XL即为所求的近似解.否则,继续进行迭代计算.常用的收敛准则是 或 ε1和ε2为预先给定的允许误差. ;单纯形法的流程如图;试用单纯形法求 的极小值. 解 选X0=(8,9)T,并取 X1=(10,11)T和X2=(8,11)T.这三点不共线,它们作为初始单纯形的顶点(如图所示). 然后计算各顶点的函数值: ，可知X1为最差点, X0为最好点. 以X3表示 X0和 X2的重心,则 ;续解例5.6;因为f(X5)f(X4),故以X5代替X1,由X5,X0和X2构成新单纯形,然后进行下一个循环.该问题的最优解为X*=(5,6)T,f(X *)=0.经32次循环,可把目标函数f(X)减小到1?10-6.在图中给出了前几次迭代的情形. ;三、单纯形法有关说明 ;四.习题;