理论教育 单纯形法优化迭代步骤及实现

单纯形法优化迭代步骤及实现

时间:2023-06-17 理论教育 版权反馈
【摘要】:单纯形法的迭代步骤如下:1)给定维数n,允许误差ε1>0,ε2>0,压缩系数λ,扩张系数μ。单纯形法的迭代过程如图4-7所示。求反射点XR:因为f<f,所以加大步长:则舍弃原来的XH=X0点,取XS、X1和X2组成新的单纯形,其为:重复上述步骤,迭代至第13次得到:因为故满足了停机准则,最优解为

单纯形法优化迭代步骤及实现

单纯形法的迭代步骤如下:

1)给定维数n,允许误差ε1>0,ε2>0,压缩系数λ(0<λ<1,但λ≠0.5,一般取为0.25或0.75),扩张系数μ(一般μ=1.2~2)。

2)计算初始单纯形顶点Xi(0)及其函数值fXi(0)):

先选定一个初始点X0(0),初始步长h>0,其余顶点为

Xi(0)=X(0)+heii=1,2,…,n) (4-19)

式中,ei为第i个单位坐标向量。H一般取为0.5≤h≤15。置0⇒k

3)比较各顶点函数值的大小,选出最好点XL,最差点XH和次差点XG,即

978-7-111-29617-1-Chapter04-93.jpg

4)检查是否满足收敛准则

978-7-111-29617-1-Chapter04-94.jpg

若满足,则输出XL=X*fXL)=fX*);否则进行5)。

5)计算除XH点外n个顶点的几何中心:

978-7-111-29617-1-Chapter04-95.jpg

由上式求出反射点:

978-7-111-29617-1-Chapter04-96.jpg

6)若fXR)≥fXG),则压缩步长,令

XS=(1-λXH+λXR (4-22)

计算fXS),转向7);若fXR)<fXG),则加大步长,令

XS=(1-μXH+μXk (4-23)

计算fXE),转向8)。

7)若fXS)<fXG),则转向9);否则将单纯形向XL点缩小一半,并计算除XL点外各点的坐标:

Xi=(Xi+XL)/2(i=1,2,…,n

组成缩小了的单纯形,转向10)。

8)若fXE)<fXR),则XEXSfXE)⇒fXS);否则XRXSfXR)⇒fXS)。

9)舍弃XH点,以XS点和其余n个顶点构成新的单纯形。

10)置k+1⇒k,返回3)。(www.daowen.com)

单纯形法的迭代过程如图4-7所示。

【例4-6】 试用单纯形法求目标函数fX)=60-10x1-4x2+x21+x22-x1x2的极小值。

解(1)给定ε=0.001,λ=0.75,μ=2。

(2)计算初始单纯形顶点Xi(0)及其函数值fXi(0))。

978-7-111-29617-1-Chapter04-97.jpg

图4-7 单纯形法程序框图

X978-7-111-29617-1-Chapter04-98.jpg,初始步长h=2,则

978-7-111-29617-1-Chapter04-99.jpg

于是 fXH)=fX0(0))=60,fXG)=fX2(0))=56

fXL)=fX1(0))=44

(3)检查停机准则:

因为 978-7-111-29617-1-Chapter04-100.jpg

所以进行(4)。

(4)求反射点XR

978-7-111-29617-1-Chapter04-101.jpg

(5)因为fXR)<fXG),所以加大步长:

978-7-111-29617-1-Chapter04-102.jpg

978-7-111-29617-1-Chapter04-103.jpg

舍弃原来的XH=X0(0)点,取XSX1(0)X2(0)组成新的单纯形,其为:978-7-111-29617-1-Chapter04-104.jpg978-7-111-29617-1-Chapter04-105.jpg

重复上述步骤,迭代至第13次得到:

978-7-111-29617-1-Chapter04-106.jpg

因为 978-7-111-29617-1-Chapter04-107.jpg

故满足了停机准则,最优解为

978-7-111-29617-1-Chapter04-108.jpg

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

我要反馈