单纯形法理论_单纯形法原理

单纯形法理论由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“单纯形法原理”。

单纯形法

单纯形法不用计算函数的导数，只需要计算目标函数的函数值，因此计算比较简单，几何概念也比较清晰，属于直接法的无约束最优化方法。所谓n维欧氏空间E中的单纯形，是指在n维空间中由n1个线性独立的点构成的简单图形或凸多面体。

基本思想：根据问题的维数n选取n1个线性独立的点，然后计算这n1个点的函数值并进行比较，确定其中的最大值的点及函数的下降方向，再设法找到一个新的好点替换函数值最大的点，从而构成新的单纯形。这个过程不断进行，新的单纯形将向极小点收缩。经过若干次迭代后，即可得到满足收敛条件的极小点。

基本过程包括：反射、扩张和压缩。下面以二维问题为例来说明单纯形法的求优过程。设二维函数f(X)在平面上有线性独立的三个点Xh，Xl，Xg，构成单纯形（三角形），计算这三个点的函数值，若

nf(Xh)f(Xg)f(Xl)

则说明Xh是最差点，Xl是最好点，Xg为次差点，迭代应该找出好的点Xr来替换最差点Xh，构成新的单纯形。Xr在Xh与除去最差点Xh以后所有顶点的形心点Xc连线的延长线上进行选取。

XrXc(XcXh)

式中：——反射系数，一般取1。

这个步骤称为反射。通常，反射点Xr的取法是使Xr点Xr点称为最差点Xh的反射点，至Xc点的距离等于Xc点到Xh的距离。

反射点Xr对新单纯形构造的影响，有以下几种情况：（1）扩张

1若反射点的函数值f(Xr)小于最好点的函数值f(Xl)，即当 ○f(Xr)f(Xl)

时，说明所取的方向是正确的，可进一步扩大效果，继续沿XhXr向前进行扩张，在更远处取一点Xe，并满足 XeXc(XrXc)

式中：——扩张系数，1.2~2.0，一般取2.0。

如果f(Xe)f(Xl)，说明扩张有利，就用Xe代替最差点Xh，构成新的单纯形。否则，说明扩张不利，舍弃Xe，仍以Xr代替最差点Xh，构成新的单纯形。

2若f(Xr)f(Xl)不成立，则不能进行扩张，此时如果 ○f(Xr)f(Xg)

则用反射点Xr替换最差点Xh，构成新的单纯形。（2）压缩

1若反射点的函数值f(Xr)小于最差点的函数值f(Xh)，但大于次差点的函数值○f(Xg)，即当

f(Xg)f(Xr)f(Xh)

时，则表示Xr点走得太远，需缩回一些，即进行压缩，并且得到的压缩点应为

XsXc(XrXc)

式中：——压缩系数，常取0.5。这时若f(Xs)f(Xh)

则用压缩点Xs代替最差点Xh，构成新的单纯形。

2若反射点的函数值f(Xr)大于最差点的函数值f(Xh)，即当 ○f(Xr)f(Xh)

时，应当压缩更加多些，即将新点压缩至Xh与Xc之间，这时所得的压缩点应为

XsXc(XcXh)Xc(XhXc)

如果f(Xs)f(Xh)，说明不能沿Xh的反射方向搜索，应进行缩边。（3）缩边

使单纯形向最好点进行收缩，即使最好点Xl不动，其余各顶点皆向Xl移近为原距离的一半。

XiXiXl

i0,1,,n 2从以上各步得到新的单纯形后，再重复开始各步，逐渐缩小单纯形直至满足精度要求为止。

初始单纯形的形成：

构成单纯形的顶点应是线性独立的，否则，如二维问题，三个点在一条直线上，就变成二维问题了，即在一条直线上找极小点的问题，称为退化。为防止退化，一般取成等边三角形，因为它是周长一定前提下包围面积最大的布点方式。

把二维等边三角形推广到n维的情况是n1个点中任两个点的距离都相等，这种单纯形就称为正规单纯形。选取正规单纯形作初始单纯形的方法如下：

给定一个初始点X0[x1,x2,,xn]T，其余n个点可取为：

X1[x1p,x2q,x3q,xnq]T



Xn[x1q,x2q,x3q,xnp]T

即第i个顶点的第i个坐标分量比初始点增加p，其他分量增加q。设正规单纯形任意两顶点的距离等于c，这时p，q的公式推导如下。对于点X2和X1，有X2X1c即

(x1qx1p)2(x2px2q)2(x3qx3q)2(xnqxnq)2c

2化简得

(qp)2(pq)22(pq)2c2

对于X1和X0，有X1X0c，即

(x1px1)2(x2qx2)2(x3qx3)2(xnqxn)2c2

化简得

p2(n1)q2c2

联立求解得 p(n1n1)c

n2(n11)c

n2q初始单纯形也可以采用下面的方法：设目标函数f(X)为n维向量，因此单纯形应有n1个顶点X1，X2，，Xn1。构造单纯形时，现在n维空间中选取初始点X1(0)（尽量靠近最优点），从X1(0)出发沿各坐标轴方向ei、以步长h找到其余n个顶点X(0)j（j2，3，…，n1）：

(0)X(0)Xj1hei

式中：ei——第i个坐标轴的单位向量；

h——步长，一般取值范围为0.5~15.0，接近最优点时要减小。构成初始单纯形的步长可取1.6~1.7。

构成初始单纯形后，可按以下步骤进行：

(k)(k)（1）计算各顶点的函数值并进行比较，找出最好点Xl(k)，最差点Xh，次差点Xg，(k)(k)(k)以及除最差点外其它各点的形心Xn2。求Xh对形心点Xn2的反射点：

(k)(k)(k)(k)Xn3Xn2(Xn2Xh)

(k)(k)(k)(k)（2）比较Xn，如果反射点Xn还好，即进行扩张，得扩张点3和Xl3比最好点Xl为：

(k)(k)(k)(k)Xn4Xn2(Xn3Xn2)

(k)(k)(k)(k)(k)得到扩张点Xn，否则4后，若f(Xn4)f(Xl)，用Xn4代替Xh，并转步骤（5）(k)(k)用Xn代替。X3h后转入步骤（5）(k)(k)若f(Xn3)f(Xl)，即反射点比最好点差，则转下一步。

(k)(k)（3）将反射点Xn3与次差点Xg比较，如果f(Xn3)f(Xg)，则用Xn3代替最(k)(k)(k)差点Xh，并转步骤（5）；若f(Xg)f(Xn3)f(Xh)，则用Xn代替X3h后进行

(k)(k)(k)(k)(k)(k)压缩，否则直接进行压缩，得压缩点为：(k)(k)(k)(k)Xn5Xn2(XhXn2)

(k)(k)(k)(k)(k)（4）求得压缩点Xn后与最差点比较，若，则用Xf(X)f(X)X5hn5hn5代替(k)以后转下一步；否则使单纯形向最好点Xl(k)收缩，收缩后的单纯形顶点为： XhX(jk)Xl(k)0.5(X(jk)Xl(k))

j1，2，…，n1

然后转下一步。

（5）进行收敛性检验。若

1n12(k)(k)f(X)f(X)jn2 n1j1则停止迭代并输出Xl(k)及f(Xl(k))，否则使kk1后转第1步。式中为任意的小(k)数，Xn2为形心。

12例

试用单纯形法求解目标函数f(X)4(x15)2(x26)2的极小值。

Function f=fun(x)syms

x1

x2

f = 4*(x1-5)^2+(x2-6)^2;clear

x1= 0 x2= 0 z=0 e= [1;1] h=1.6 X0=[x1;x2] X1=X0 + h* e X2=X0 + h*e X3=X0 + h*e