理论教育 复合形法迭代步骤与停机准则

复合形法迭代步骤与停机准则

时间:2023-06-17 理论教育 版权反馈
【摘要】:复合形法的迭代步骤如下:确定初始可行点 对于问题较简单的情况,如找不到k个可行点,可凭经验选出。图5-2 复合形法程序框图检验停机准则≤ε(i=1,2,…若满足,则认为目标函数已经收敛,可终止迭代,返回。依次重复上述步骤,直至满足预定的计算精度为止,取复合形各顶点函数值最小值为最优解。

复合形法迭代步骤与停机准则

复合形法的迭代步骤如下:

(1)确定初始可行点 对于问题较简单的情况,如找不到k个可行点,可凭经验选出。但对复杂(变量较多)的问题,要用随机方法产生初始可行点,即

978-7-111-29617-1-Chapter05-4.jpg

式中 978-7-111-29617-1-Chapter05-5.jpg——在区间[0,1]内均匀分布随机数

X(1)为可行点,则进行(2)。

(2)随机产生其他顶点

978-7-111-29617-1-Chapter05-6.jpg

式中 i——点数,i=2,3,…,k

j——点的坐标,j=1,2,…,n

(3)构成复合形 若已经产生了的k个顶点中有L个可行点,其余k-L个顶点为不可行点,则继续产生第L+1个点,如果这个点为可行点,再继续产生新点,即第L+2个点;否则,将该点取为

978-7-111-29617-1-Chapter05-7.jpg

式中 978-7-111-29617-1-Chapter05-8.jpg——分别为第L+1个点的新点和旧点;

XB——前L个点的中心点。

978-7-111-29617-1-Chapter05-9.jpg

重复此过程直至XL+1)点成为可行点。

按上述方法产生的k个可行点即构成了复合形。

(4)寻求映射点 计算复合形所有顶点的函数值,取其中最大者为最差点XH,最小者为最好点XL

978-7-111-29617-1-Chapter05-10.jpg

计算除XH外的k-1个顶点的形心XC,即

978-7-111-29617-1-Chapter05-11.jpg

如果XC不是可行点,则以k个顶点中最好点XL下界,以XC为上界重新利用随机数选点,构成复合形,重复(1)~(4)的过程。

如果XC是可行点,则在由XHXC点的方向上,取一映射点XR,即

978-7-111-29617-1-Chapter05-12.jpg

式中 α——映射系数,一般可取α=1.3。

XR为不可行点,则须将XR点收缩回来,即使α减半,重算XR,直至XR是可行点为止。

(5)比较目标函数值 若fXR)<fXH),则以XR代替XH,构成新复合形,返回进行(4)。

fXR)>fXH),则将α减半,直至fXR)<fXH),返回(4)。若α虽不断减半,直到小于预先给定的ξ时,fX)仍无改进,则将(4)选择的XH改成次差点XC,即

978-7-111-29617-1-Chapter05-13.jpg

这样,由次差点出发求映射点,重复上述过程。

978-7-111-29617-1-Chapter05-14.jpg

图5-2 复合形法程序框图

(6)检验停机准则

978-7-111-29617-1-Chapter05-15.jpgεi=1,2,…,k)或978-7-111-29617-1-Chapter05-16.jpgfXL)≤ε是否满足。若满足,则认为目标函数已经收敛,可终止迭代,返回(4)。

复合形法的迭代过程如图5-2所示。

【例5-1】 试用复合形法求解目标函数f978-7-111-29617-1-Chapter05-17.jpg的极小值,已知约束条件为(www.daowen.com)

978-7-111-29617-1-Chapter05-18.jpg

解 取复合形的顶点数k=2n=4,用随机法产生初始复合形的顶点,取随机数

r11=0.1,r21=0.2,r31=0.3,r41=0.4

r12=0.1,r22=0.2,r32=0.3,r42=0.4则初始复合形4个顶点的X1坐标分量为[式(5-2)]

978-7-111-29617-1-Chapter05-19.jpg

4个顶点的X2坐标分量为[式(5-2)]

978-7-111-29617-1-Chapter05-20.jpg

则初始复合形4个顶点的坐标为

978-7-111-29617-1-Chapter05-21.jpg

检验各顶点是否可行:将各顶点的坐标值代入各约束方程,均满足约束条件。

1)计算各顶点的函数值并比较它们的大小:

978-7-111-29617-1-Chapter05-22.jpg

2)求除最差点外其余三点的形心[式(5-5)]:

978-7-111-29617-1-Chapter05-23.jpg

代入约束条件,证明在可行域内。

3)求最差点的反射点,按式(5-6),α=1.3:

978-7-111-29617-1-Chapter05-24.jpg

(可证明在可行域内)

4)计算fXR(0))并与fXH(0))比较:

978-7-111-29617-1-Chapter05-25.jpg

故可用新点XR(0)替换X1(0),构成新的复合形:

978-7-111-29617-1-Chapter05-26.jpg

5)计算新复合形中除978-7-111-29617-1-Chapter05-27.jpg外各顶点的形心978-7-111-29617-1-Chapter05-28.jpg

978-7-111-29617-1-Chapter05-29.jpg

代入约束方程知,978-7-111-29617-1-Chapter05-30.jpg在可行域内。

6)计算978-7-111-29617-1-Chapter05-31.jpg的反射点978-7-111-29617-1-Chapter05-32.jpg,取α=1.3:

978-7-111-29617-1-Chapter05-33.jpg

代入约束条件,表明不满足第二个约束条件,故应将α减半,即取α=0.65,重算反射点978-7-111-29617-1-Chapter05-34.jpg

978-7-111-29617-1-Chapter05-35.jpg

代入约束条件,表明符合约束要求。

7)计算新反射点978-7-111-29617-1-Chapter05-36.jpg的函数值:

978-7-111-29617-1-Chapter05-37.jpg

故可用978-7-111-29617-1-Chapter05-38.jpg替换978-7-111-29617-1-Chapter05-39.jpg,构成新的复合形。依次重复上述步骤,直至满足预定的计算精度为止,取复合形各顶点函数值最小值为最优解。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈