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

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

1）给定维数n，允许误差ε₁＞0，ε₂＞0，压缩系数λ（0＜λ＜1，但λ≠0.5，一般取为0.25或0.75），扩张系数μ（一般μ=1.2～2）。

2）计算初始单纯形顶点X_i^（0）及其函数值f（X_i^（0））：

先选定一个初始点X₀^（0），初始步长h＞0，其余顶点为

X_i^（0）=X^（0）+he_i（i=1，2，…，n） （4-19）

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

3）比较各顶点函数值的大小，选出最好点X_L，最差点X_H和次差点X_G，即

4）检查是否满足收敛准则：

若满足，则输出X_L=X^*和f（X_L）=f（X^*）；否则进行5）。

5）计算除X_H点外n个顶点的几何中心：

由上式求出反射点：

6）若f（X_R）≥f（X_G），则压缩步长，令

X_S=（1-λ）X_H+λX_R （4-22）

计算f（X_S），转向7）；若f（X_R）＜f（X_G），则加大步长，令

X_S=（1-μ）X_H+μX_k （4-23）

计算f（X_E），转向8）。

7）若f（X_S）＜f（X_G），则转向9）；否则将单纯形向X_L点缩小一半，并计算除X_L点外各点的坐标：

X_i=（X_i+X_L）/2（i=1，2，…，n）

组成缩小了的单纯形，转向10）。

8）若f（X_E）＜f（X_R），则X_E⇒X_S，f（X_E）⇒f（X_S）；否则X_R⇒X_S，f（X_R）⇒f（X_S）。

9）舍弃X_H点，以X_S点和其余n个顶点构成新的单纯形。

10）置k+1⇒k，返回3）。(https://www.daowen.com)

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

【例4-6】 试用单纯形法求目标函数f（X）=60-10x₁-4x₂+x²₁+x²₂-x₁x₂的极小值。

解（1）给定ε=0.001，λ=0.75，μ=2。

（2）计算初始单纯形顶点X_i（0）及其函数值f（X_i（0））。

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

设X，初始步长h=2，则

于是 f（X_H）=f（X₀^（0））=60，f（X_G）=f（X₂^（0））=56

f（X_L）=f（X₁^（0））=44

（3）检查停机准则：

因为

所以进行（4）。

（4）求反射点X_R：

（5）因为f（X_R）＜f（X_G），所以加大步长：

则

舍弃原来的X_H=X₀^（0）点，取X_S、X₁^（0）和X₂^（0）组成新的单纯形，其为：

重复上述步骤，迭代至第13次得到：

因为

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