改进单纯形范文

改进单纯形范文（精选9篇）

改进单纯形 第1篇

为叙述方便,设讨论的线性规划问题为

线性规划约束方程组的系数矩阵A=(aij)mn=(P1,P2,,Pn)的m(m

在线性规划约束方程组中,对某一基B,令其非基变量为0,解其相应的m阶方程组,得基变量的惟一值,将此值加上非基变量的0值,得到一个满足线性规划问题约束方程组的一个解,称此解为线性规划问题的基解。基解中若各分量满足非负约束,则称此基解为基可行解。2个基可行解相邻,当且仅当它们之间变换一个基变量。

单纯形法求解线性规划,即在基可行解中找其最优解,而线性规划问题的基可行解可能有Cnm个,所以,单纯形法求解线性规划非常繁琐,计算工作量大,特别是迭代计算过程中,进基变量或出基变量有2个及以上时,进基变量、出基变量确定处理不一样,计算工作量就不一样,有时相差很大。那么,怎样才能使迭代计算工作量尽可能小?迭代次数尽可能少?

1 进基变量的确定

由线性规划的单纯形法迭代原理,线性规划的单纯形法迭代求解过程中,取大于0的最大检验数对应变量作进基变量[1,2,3]。但当大于0的最大检验数有2个及以上时,为避免迭代陷入循环,由Bland法则,取下标最小的变量做进基变量[1,2,3]。而一般情况下,单纯形迭代是不会陷入循环,因此,理论上任取一个大于0的最大检验数对应变量作进基变量即可。但是,若大于0的最大检验数对应各变量作进基变量时取值不一样,则得到的新基可行解接近最优解的程度就不一样,即求得最优解的迭代次数就不一样。在这种情况下,按法则1确定进基变量,可使得到的新基可行解目标函数值最接近最优解,从而使求得最优解的迭代次数达到最少[4]。

法则1线性规划的单纯形法迭代中,若大于0的最大检验数有2个及以上时,则以各大于0的最大检验数对应变量作进基变量时取值最大的对应变量作迭代的进基变量。

证明假设线性规划问题式(1)的基可行解为X(0)=(b1,b2,,bm,0,,0)T,其目标函数值

设对应该基可行解有N(N≥2)个非基变量xk1,xk2,,xk N的检验数为大于0的最大检验数,即σk1=σk2==σk N=σ*。

将式(1)的目标函数以X(0)的非基变量表示

其中,为非基变量xj的检验数。

由式(2)明显看出,大于0的检验数对应的非基变量作进基变量,可使目标函数值z增加。

若以xki(i=1,2,,N)作进基变量,则新基可行解中,进基变量取值为:,由式(2),目标函数值z增加△z=σkixki=σ*θi(i=1,2,,N)。

因此,以θ=max{θ1,θ2,,θN}对应变量xk作进基变量,目标函数值z增加△z=σ*θ最多,从而使得到的新基可行解目标函数值最接近最优解的目标函数值,由此,使求得最优解的迭代次数最少。

2 出基变量的确定

线性规划的单纯形法迭代求解中,进基变量xk确定以后,以单纯形表中基变量取值列元素与进基变量xk对应列大于0的对应元素之比的最小值对应基变量作出基变量。即以对应变量xl作出基变量。若最小比值θ对应基变量有2个或以上,为避免循环,Bland法则取下标最小的变量作出基变量[1,2,3]。一般情况下,单纯形迭代不会陷入循环,常取最小θ对应的任一基变量作出基变量。但若最小θ对应的各基变量的目标函数系数不一样,以其不同基变量作出基变量,由此而得的新基可行解接近最优解的程度就不一样。在这种情况下,按法则2确定出基变量,可使后续迭代得到的新基可行解目标函数值最接近最优解,从而使求得最优解的迭代次数达到最少[4]。

法则2线性规划的单纯形法迭代中,若对应最小比值θ有2个及以上基变量时,则以目标函数系数最小的基变量作出基变量。

证明设基可行解X(0)对应最小θ的基变量有M(M≥2)个,即:xl1,xl2,,xl M。则取其中一个基变量xlj(j=1,2,,M)作出基变量,可得与X(0)相邻的且使目标函数值增大的基可行解X(1)

其对应的目标函数值

因此,以xl1,xl2,,xl M中任一变量作出基变量进行迭代,而导致的目标函数值增加相同,为σkθ。

若以cl M=min{cl1,cl2,,cl M}对应变量clm为出基变量,会使后续迭代目标函数值增加更快。因为,单纯形法迭代中,最小θ对应的基变量在下一新的基可行解中取值始终为0。但在再下一次迭代中,本次最小θ对应的还保留在基可行解中的基变量可能:(1)成为出基变量,在新基可行解中,其变为非基变量,取值仍为0,由其成为非基变量而导致目标函数改变量为0(因为此次迭代中的最小θ为0);(2)仍保留在基变量中,在新基可行解中,其取值可能为0,也可能大于0,无论哪种情况,由此导致的目标函数值不会减少,反而,若出现后者,会使目标函数值增加更快。又由于单纯形迭代总是朝目标函数值增加的方向进行。因此,综合而论,按法则2确定的出基变量,会使单纯形法后续迭代中目标函数值增加更快,从而减少求得最优解的迭代次数,使求得最优解的总的迭代次数达到最小。

例用单纯形法求解下列线性规划

解化为标准形

按本文提出法则进行迭代,如表1所示,只需一次迭代即可得最优解:。若用Bland法则迭代需迭代4次,一般法则迭代至少需迭代2次,才能得最优解。

3 结论

求解线性规划的单纯形法无论是理论上或是实际应用上均较成熟。但其计算工作量较大,较繁琐,并且迭代过程中,进基变量、出基变量处理不当,会增加迭代次数,加大计算工作量。若迭代计算中,在遵循单纯形法迭代计算的基本原则基础上,对有2个及以上变量可作进基变量或出基变量的情况下,按本文提出的法则确定进基变量或出基变量,则会使迭代次数明显减少,从而大大简化计算工作。

摘要：根据单纯形法的基本原理,针对单纯形法迭代计算的繁琐,在可作进基变量或出基变量有2个及以上的情况下,分别提出了能使迭代次数明显减少的进基变量和出基变量的确定法则,并从理论上和实例上分别证明和说明了该法则的合理性和有效性。

关键词：线性规划,单纯形法,优化,基变量

参考文献

[1]胡运权,郭耀煌.运筹学教程[M].3版.北京:清华大学出版社,2007:6-36.

[2]运筹学教材编写组.运筹学[M].北京:清华大学出版社,1998:8-37.

[3]韩伯棠.管理运筹学[M].北京:高等教育出版社,2000:3-97.

单纯形法理论 第2篇

单纯形法不用计算函数的导数，只需要计算目标函数的函数值，因此计算比较简单，几何概念也比较清晰，属于直接法的无约束最优化方法。所谓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

基于单纯形射线追踪法的研究 第3篇

基于单纯形的射线追踪方法是一种新提出的射线追踪方法, 该方法的核心是将三维空间剖分成多个无缝且互不重叠的四面体单元, 将发射源等效为若干根从源点发出的射线, 通过在三维空间建立矢量模型, 利用射线和单纯形单元之间的空间矢量关系求得所有射线的轨迹, 再利用新提出的接受方法辨认出所有对接受点有贡献的射线, 最终可求得到达接受点的所有射线的相干合成结果。这种方法不需要对反射面做相交测试, 从而提高了程序运行的效率。文献[2]分别给出了二维和三维环境射线追踪的矢量代数模型。

一、方法和原理

一个理想的波前是单位球的表面。为了增加射线的分辨力, 波前必须再分, 并且为了保持所有射线操作的程序化, 再分后的每个波前在离发射机距离r处应有相同的形状和大小。在球坐标系中, 我们可以均分θ/φ对整个波前不断再分、在靠近球的两极方向上的射线之间角度间隔则会减小。解决方法可以通过Gmsh对球进行剖分, 剖分效果如图1。

3-D情况下传统的接受球会引入双计误差, 双计误差可以用一种算法来解决。该算法检验每一条接受的射线是否有任何其他先前已接受的, 如果有的话, 新射线是多条的, 必须不予考虑。判定条件如下:

首先求得所有射线反射的数据, 包括射线反射次数、射线发射的俯仰角和方位角、反射面的信息、总路径的长度。

根据以下四点判断接受射线是否为多余射线:1、判断射线反射次数是否为同一次。2、判断射线每次反射的反射面是否为同一个反射面。3、Gmsh剖分后计算出相邻射线之间的角度lk。4、判断射线的总路径d是否在可控制范围。如果同时满足上述条件, 则判定此射线是多余射线, 必须不予考虑。

二、仿真结果与分析

仿真所采用的时域入射波形为高斯脉冲的二阶导数波形。

脉冲宽度τ=0.11ns, 波形延迟Tc=0.5ns。仿真环境如文献[4], 发射天线高1.6m坐标[1.5, 4, 1.6], 接受天线高1.0坐标[1.5, 1, 1][3]。

图2为垂直极化3次反射仿真结果。将它与参考文献[4]中的Figure14 (a) 、 (b) 的接受波形和功率延迟做比较, 结果与文献吻合非常好, 从而证明了此方法的有效性。

摘要：单纯形射线追踪相比传统的射线追踪不需要对射线和多面体面做相交测试, 从而算法的效率得到了提高, 本文改进了射线接受方法, 并对一个室内超宽带的信道模型进行了仿真, 仿真结果验证了该方法的有效性。

关键词：通信技术,传播模型,射线追踪,超宽带

参考文献

[1]吴志忠.移动通信无线电波传播[M].北京:人民邮电出版社, 2002:258-261

[2]杨大成.移动传播环境[M].北京:机械工业出版社, 2003:121-122

[3]YUN ZQ.A Ray-Tracing Method Based on the Triangular Grid Approach and Application to Propagation Prediction in Urban Environments.IEEE Transactions on Antennas and Propagation[J], Vol.50, NO.5, May2002:750-758.

[4]Richard Yao“, An efficient time-domain ray model for UWB indoor multipath propagation channel”, IEEE Global Telecommunications Conference.

运筹学单纯形法matlab程序 第4篇

if sgm(i)>0

h=1;

end end

while h>0

[msg,mk]=max(sgm);

for i=1:m

sta(i)=b(i)/A(i,mk);

end

[mst,mr]=min(sta);

zy=A(mr,mk);

for i=1:m

if i==mr

for j=1:n

A(i,j)=A(i,j)/zy;

end

b(i)=b(i)/zy;

end

end

for i=1:m

if i~=mr

for j=1:n

A(i,j)=A(i,j)-A(i,mk)*A(mr,j);

end

b(i)=b(i)-A(i,mk)*b(mr);

end

end

B1=A(:,1:m);

cb(mr)=c(mk);

xx(mr)=mk;

sgm=c-cb*B1*A;

for i=m+1:n

if sgm(i)>0

h=1;

end

end

单纯形法两种形式的区别与联系 第5篇

关键词：单纯形法,有限改进法,灵敏度分析,单纯形表

线性规划是现代管理中应用最为广泛的一种数学模型, 它是解决经营管理中如何有效利用现有人力、物力、财力完成更多的任务, 或在预定的任务目标下, 如何使耗用的人力、物力、财力最少, 以实现目标的问题. 1947年美国数学家G. B. Dantzig提出的单纯形法 (simplex method) 是解线性规划问题最为有效的方法. 作为运筹学的一个重要分支, 线性规划的应用极其广泛, 很多学者对单纯形法做了改进和补充. 线性规划问题的单纯形法一直是运筹学课程教学的重点和难点, 一些学者也做了单纯形法教学方面的研究, 为单纯形法的教学提供了新的思路. 单纯形法是一种迭代算法, 它求解线性规划问题的基本思想是:首先找出一个初始基可行解, 判断其是否为最优解;如果为否, 则转换到使得目标值不断增大, 并且与其相邻的基可行解, 直到找到最优解为止.

目前不同的教材在介绍单纯形法时采用的列表形式不一样, 鉴于这种情况, 本文就教材上两种常见的形式进行比较分析得出结果明显, 并且便于做灵敏度分析的形式, 通过算例说明这种形式既便于计算又便于教学.

1. 线性规划问题的标准型

为了叙述方便, 设讨论的线性规划模型为

其标准型为

max z = CX + 0XS, s. t. AX + IXS= b, X≥0, XS≥0. (2)

对于选定的可行基B, 不妨设B = (P1, P2, , Pm) , N = (Pm + 1, Pm + 2, , Pn) 是非基变量的系数矩阵, 则记A = (B, N) , 其中Pj (j = 1, 2, 3, , m) 表示矩阵A的第j列. 相应的, 记

2. 单纯形法的两种形式

形式一式 (2) 的初始单纯形表通过单纯形法得到最优单纯形表为表1.

形式二 (有限改进法) 见参考文献[2].

3. 通过算例比较两种形式

下面通过用单纯形法两种形式求解一个一般的线性规划问题, 找出它们的区别与联系, 得出结论.

算例某塑料车间可以生产以下三种管状产品, 生产一个单位的甲管道需要塑料1 kg, 工时1个单位, 利润为2元;生产一个单位的乙管道需要塑料1 kg, 工时4个单位, 利润为3元;生产一个单位的丙管道需要塑料1 kg, 工时7个单位, 利润为11/3元. 问:

(1) 如何组织生产使总利润最大?

(2) 现有丁产品, 设生产1 m丁需塑料3 kg和工时5小时, 每m利润为7元. 问:是否应该生产丁产品? 如投产, 该车间最优生产计划有何变化?

解 (1) 设甲、乙、丙的产量分别为x1, x2, x3, 由题目所给数据可以建立以下数学模型:

将上述问题转化为标准型, 再采用单纯形法形式一求解, 最优单纯形表2所示.

由上表可得 此线性规 划问题的 最优解为: X = (45, 90, 0, 0, 0) T, 所以目标函数的最优解为max Z = 360.

采用第二种形式表3中进行求解:

由上表可得 此线性规 划问题的 最优解为: X = (45, 90, 0, 0, 0) T, 所以目标函数的最优解为max Z = 360.

对于形式二有限改进法, 根据参考文献[2]以上计算过程可以得出:

上述 (3) 中所得到的信息对也是进行灵敏度分析时的重要工具.

(2) 法一:采用形式一设丁产品的产量为x6, 其系数向量为p6= (3, 5) T, 其检验数为. 所以判定丁产品值得生产. 则其在最终单纯形表中对应的列向量为

在最优单纯形表中添加x6一列, 再按单纯形法计算可得最优值.

法二:采用形式二.

在最优单纯形表中添加x6一列:

再按单纯形法计算可得最优值.

4. 结论

从上一节的解题过程比较单纯形法两种形式, 归纳如下:

(1) 通过以上推导式 (3) 过程可以看出, 矩阵D中的第一列是 (1, 0, 0) T, 这是因为第一行是检验数行, 第一列的数都是表示指归形式中的运算符号与Ⅰ0的关系, 故第一例始终为 (1, 0, 0) T. B- 1是形式二的矩阵D中元素1的代数余子式.

推广到一般, 形式二用 于做灵敏 度分析的 矩阵

(2) 在灵敏度分析方面, 通过例题可以看出, 形式二用于做灵敏度分析一步到位, 用于其他类型的灵敏度分析也是一样的, 只需要用到矩阵D. 而形式一要分步骤完成灵敏度分析, 并且在分析过程中还要将表中的数字反号. 即形式二比形式一简单方便.

(3) 在表格构造上, 第一种形式与第二种形式的列表形式不同, 第二种要比第一种简单明了. 由于表格造的不同, 形式一在每一步计算σj时需要单独计算, 比较麻烦, 而形式二不存在这样的问题.

(4) 比起第一种形式, 在第二种形式的最优单纯形表中可以直接读出取最优解和最优值的信息.

线性规划单纯形法教学改革探讨 第6篇

1947年, 美国数学家G.B.丹齐克提出了一种求解线性规划 (以下简称LP) 的通用解法单纯形法.至今, 该方法仍然是行之有效且被广泛应用的最基本方法.通常, 求解LP模型时, 常用的基本单纯形法、大M法、两阶段法等, 都需要在系数矩阵中构造一个单位矩阵作为初始可行基, 然后用单纯形法进行逐步迭代, 进而判断解的类型以及解的存在与否.在教学中, 我们发现手算练习可以加深学生对单纯形法的理解, 同时使得学生对基、基变量、非基变量、基可行解等基本概念有更准确的把握, 但在实际操作中, 我们发现, 大部分同学对于单纯形算法的掌握仅限于基本的计算, 对其中的迭代原理没有深刻的理解, 同时, 逐步迭代产生的大量运算也容易使学生觉得枯燥, 进而产生排斥情绪, 使整个学习过程显得非常被动, 学习积极性不高, 不利于学生对于学习内容的把握, 影响教学效果.因而考虑能否利用单纯形法的算法逻辑性, 在教学过程中, 组织学生用C语言来编程实现该算法, 旨在一方面促使学生更深刻地理解单纯形法的算法步骤, 简化运算过程, 更主要的是, 通过C语言编程, 使得运筹学和C程序设计两门课程得到有效的衔接和贯通, 增强学生对课程相关内容的把握, 并能逐步强化对学生逻辑思维能力以及编程能力的培养, 从而提高学生的综合分析能力和解决问题的能力.

二、单纯形法算法步骤

设LP模型为

$\begin{array}{l}\max {\rm Z}=CX‚\\ \text{s}.\text{t}.\{\begin{array}{l}AX=b,\\ X\ge 0.\end{array}\end{array}$

其中, C= (c1, c2, , cn) , b= (b1, b2, , bm) T, A= (aij) mn, 且b≥0.

由LP问题的性质可知, 如果LP问题存在最优解, 一定有一个基可行解是最优解.因此, 单纯形法迭代的基本思路是:先找出一个基可行解, 并使目标函数值不断增大, 一直找到最优解为止.

用单纯形法求解LP步骤如下:

step1 确定初始基可行解

在系数矩阵A中, 确定单位阵为初始可行基B, 并确定初始基变量xB和非基变量xN, 令xN=0, 解出初始可行解.

step2 判断

(1) 若所有检验数σj=cj-zj0, 则基B为最优基, 所得基可行解为最优解, 迭代停止;

(2) 若存在某个检验数σk>0, 并且所对应的系数列向量Pk0, 则该LP无界, 迭代停止;否则转step3.

step3 换基迭代

(1) 确定入基变量:选择检验数最大的非基变量为入基变量, 即若max (σj|σj>0) =σk, 则xk为入基变量;

(2) 确定出基变量:根据θ原则确定出基变量, 其中

$\theta =\min \left(\frac{b{}_i}{a{}_{ik}}|a{}_{ik}>0\right)=\frac{b{}_l}{a{}_{lk}},$

则所对应的基变量xl为出基变量, 元素alk为主元素.

step4 主元变换

利用矩阵的初等行变换, 把主元素alk所在的列化为单位向量, 重新计算检验数, 得到新的单纯形表, 再转step2.

三、LP问题的C语言程序实现

利用上述单纯形算法, 我们求解一个LP问题, 举例如下:

例 用单纯形法解下列线性规划:

$\begin{array}{l}(\text{l}\text{p})\{\begin{array}{l}\max {\rm Z}=2x{}_1+x{}_2,\\ \text{s}.\text{t}.\{\begin{array}{l}x{}_{1}4,\\ x{}_{2}3,\\ x{}_1+2x{}_{2}8,\\ x{}_1,x{}_2\ge 0.\end{array}\end{array}\\ (\text{l}\text{p}1)\{\begin{array}{l}\max {\rm Z}=2x{}_1+x{}_2+0x{}_3+0x{}_4+0x{}_5‚\\ \text{s}.\text{t}.\{\begin{array}{l}x{}_1+x{}_3=4,\\ x{}_2+x{}_4=3,\\ x{}_1+2x{}_2+x{}_5=8,\\ x{}_j\ge 0(j=1,2,3,4,5).\end{array}\end{array}\end{array}$

解 将原问题化为标准形式 (如上lp1) , 则可取B1= (P3, P4, P5) =I, 相应基变量为x3, x4, x5, X0= (0, 0, 4, 3, 8) T, 列单纯形表求解如下:

所以最优解为X*= (4, 2, 0, 1, 0) T, 最优值为Z*=10.

从算法过程中可看出, T (B1) , T (B2) , T (B3) 三个表分别代表一个基可行解, 从每一个基可行解的判断, 到出基变量、进基变量的选取以及新的基可行解的求解方法, 都是采用统一的一个原理和一种固定的计算模式, 这种固定模式的不断循环迭代非常符合C程序编写的特点.但是在教学中, 如果我们要求学生各自独立地去实现整个算法, 对于大部分同学来说还是一件比较困难的事情, 因而我们可考虑采取让学生分组分别对各个步骤编写一些子程序块.比如, 标准形式中初始信息的输入 (包括变量个数、约束条件的个数、增广矩阵以及初始可行解的输入等) , 解的判断及输出, 出基和进基变量的选取, 新的基可行解的生成等, 每一个模块实际代表了算法的其中一个步骤, 如果学生可以完成这样的目标, 那么把每个子程序综合成一个整体程序用于对单纯形法的求解就不再是个难题了.

我们将例题所示的线性规划, 用C语言程序实现结果如下:

在单纯形法教学中, 引入C程序的编程训练, 对学生而言, 是一个全新的挑战.这首先要求学生必须对算法整体有更深刻的思考和把握, 理解算法每个步骤的原理, 并能将诸个步骤形成一个系统而有机的整体.只有在这样的基础之上, 才可以将该算法用C语言来编程实现.在日常教学中, 我们进行了小规模的教学实践, 总结发现, 这样的模式在教学中可大大提高学生学习的积极性和主动性, 提高学习效率, 并能很好地将C程序运用到所学课程中去, 在逐步提高学生逻辑分析能力和编程能力的同时, 也很好地巩固了当前所学的课程内容, 对于学生而言, 确能受益匪浅.

参考文献

[1]胡运权.运筹学教程 (第三版) [M].北京:清华大学出版社, 2007:19-35.

[2]运筹学教材编写组.运筹学 (第三版) [M].北京:清华大学出版社, 2007:20-31.

[3]张长海, 陈娟.C程序设计[M].北京:高等教育出版社, 2004:23-56.

改进单纯形 第7篇

关键词：参数计算,抽水试验数据,单纯形法,差分进化算法,混合算法

0引言

含水层参数是进行地下水资源评价和开发利用的基本数据,诸如导水系数和储水系数等都是含水层重要参数。目前,主要通过分析非稳定流抽水试验数据来获得含水层参数。泰斯公式[1]具有形式简单和能够在一定程度上反映在抽水过程中的地下水水位变化规律等优点,因而一直被作为分析非稳定流抽水试验数据,确定含水层参数的基本公式。由于泰斯公式是待求含水层参数的隐函数,不能够直接进行求解,为了便于应用,已经提出了多种基于泰斯公式的确定含水层参数的计算方法,如标准曲线配线法[1]、Jacob直线图解法[1]、非线性最小二乘法[2]和改进直线解析法[3]等。这些方法都有其自身的优点,但在应用中也存在着一定的局限性。近年来,人们已经将属于智能优化算法的模拟退火法[4]、粒子群优化算法[5]和混沌序列优化算法[6]等方法应用于求解分析抽水试验资料,确定含水层参数的函数优化问题。

差分进化算法[7](Differential Evolution,DE)是1995年Storn和 Pricel提出的一种并行随机性搜索算法。它是通过群体内个体间的合作和竞争产生的群体智能优化算法,其具有操作简单,算法控制参数较少和全局搜索能力较强等优点,然而,其也存在着运算后期进化收敛速度较慢,计算结果精度较低等不足之处;单纯形法[8]是一种多维直接搜索的局部优化方法,属于确定性的算法,与其他的确定性优化方法相比,其具有不需要计算目标函数的梯度,只是针对一定的图形的顶点,直接进行搜索,具有运算过程简单,计算量小,局部搜索能力强等优点,但是其存在着对参数初始值的依赖性较强且易于陷入局部极值点等弱点。鉴此,文中尝试将具有确定性运算特征的单纯形法和具有随机性运算特征的差分进化算法有机地结合起来,构成一种混合优化算法,即单纯形差分进化优化算法,并将其分别应用于分析在满足泰斯假设条件的无限含水层和存在直线隔水边界含水层两种情况下进行的非稳定流抽水试验数据,确定含水层参数,且与其他方法进行运算精度和收敛性等方面的比较。

1单纯形差分进化混合算法

1.1单纯形法和差分进化算法简介

单纯形法[8](Simple Method,SM)也可称为可变多面体搜索方法,是一种传统的无约束最优化直接算法,其搜索速度快、计算量小、具有较强的局部搜索能力。其基本原理是:在 维空间中,用 个顶点构成一个多面体,求出各顶点的适应值,并确定其中的最优点、次优点和最差点,然后通过反射、延伸、压缩或收缩等操作找出一个较好点,取代最差点,从而构成一个新的多面体,这样重复迭代可以找到或逼近一个最优点。

差分进化算法[9](Differential Evolution,DE)是一种全局并行优化算法,具有记忆个体最优解和种群内部信息共享的特点,这种算法主要包括交叉、变异和选择等操作算子。其基本思想是运用当前种群个体的差分变异和交叉重组得到的中间种群,然后基于贪婪选择策略对父代种群和中间种群中的个体进行选择操作得到具有更佳适应度的子代个体。

1.2单纯形差分进化混合算法的构造

由于单纯形法能够在局部进行快速寻优,可以克服差分进化法在后期收敛较慢的缺点,而差分法则能够把握大局,全局搜索能力强,可以弥补单纯形易受参数初值大小影响且易于陷入局部极值点的缺陷。因此,文中采取差分与单纯形法的交叉搜索策略。单纯形差分进化混合算法(SMDE)的主要步骤如下。

Step1:初始化种群规模N、交叉因子CR、输入求解参数的上界和下界、最大迭代次数kmax以及满足精度要求的次数ks。

Step2:随机产生由N个位于搜索空间内的候选解个体组成的初始种群P0。

Step3:将种群P0当前各个体位置设定为其历史最优位置,再找出当代全局最优适应度及其位置。

Step4:初始化迭代次数k和k1,若k<kmax且满足防止早熟所设置的迭代次数k1<ks时进入循环。

Step5:由差分进化算法得到变异向量、试验向量和下一代个体,比较试验向量所对应的适应度得到个体历史最优值,将其赋给历史最优值,再在各个历史最优值中找到全局最优值。

Step6:由单纯形法从当前群体中获取局部最优值,再将其随机赋给群体中某个个体,k1=k1+1。

Step7:迭代步数k=k+1并且返回Step4,直到k1达到设定的ks时,迭代停止同时输出最优解、位置及其迭代次数。

图1给出了以上运算过程的流程图。

2含水层参数识别问题

为了检验单纯形差分进化混合算法的适用性和可靠性,本文将其应用于无限边界含水层和有直线隔水边界含水层2种情况下的含水层参数计算问题。

2.1井函数值计算

(1)泰斯公式与井函数值的计算。

含水层为均质各向同性并无限延伸时,若以定流量Q进行抽水,那么在抽水开始后 时刻,在含水层中距抽水主井水井距离为r的点处的水位降深可以表示为[1]:

式中:S表示水头降深;Q表示抽水流量;T表示含水层的导水系数;W(u)为泰斯井函数,其表达式为:

式中:u为无量纲时间,其表达式为:

式中:μ为含水层的储水系数,无量纲。

从式(2)可以看出,在计算水头降深时,要计算广义积分数值。在此采用R.Srivastava在文献[10]中给出的近似表达式进行计算。

常数值分别为:a0 =-0.577 72,a1=0.999 99,a2=-0.249 91,a3=0.055 19,a4=-0.009 76,a5=0.001 08,b0=0.267 77,b1=8.634 76,b2=18.059 02,b3=8.573 30,c0=3.958 50,c1=21.099 65,c2=25.632 96和c3=9.573 32。

(2)直线隔水边界条件下的降深计算公式。

在含水层存在直线隔水边界,而其他条件与无限边界含水层情况相同的情况下,抽水试验过程中的观测孔中的水头降深可以表示为[1]:

式中:ρ表示观测孔到映射井间的距离。

2.2目标函数的构成

在应用单纯形差分进化混合算法时,要求预估的含水层参数值能使下列表达式的目标函数达到极值为:

式中:s${}_j^0$表示在抽水开始后第j时刻观测到的实际水位降深值;sj为利用式(1)计算的第j时刻的水头降深;在无限含水层情况下,利用式(1)计算sj的值;对于具有隔水层边界含水层情况,运用式(6)计算sj的值;θ为待估参数向量;j=1,2,,n为抽水试验过程中水位降深观测时间的序列号。

目标函数式的意义为选取适当的参数θ值,使降深观测值与其计算值之间的离差平方和的均值达到极小。此时对应的含水层参数值,即为问题所求。对于函数优化问题(7)而言,设含水层的导水系数T为θ1,储水系数μ为θ2,在有直线隔水边界情况下,设观测井到映射井间的距离ρ为θ。

3数值实验

3.1抽水试验数据

为了验证文中方法的适用性和可靠性,引用文献[11]中给出的2种含水层边界条件下的实际抽水试验数据进行数值实验。表1中给出的是无限边界含水层条件下,在抽水开始后距抽水主井距离为30.48 m处观测孔中的实际水头降深观测数据,试验中的抽水流量为4 612.8 L/min,抽水持续时间为800 min;表2中给出的是具有直线隔水边界含水层条件下,在抽水开始后距抽水主井距离为30.48 m处观测孔中的水头降深观测数据,试验中的抽水流量为4 581.7 L/min,抽水持续时间为840 min。

3.2结果与讨论

3.2.1实验条件与不同方法的计算结果

根据图1所示的算法流程图,利用Matlab编写了SMDE算法的程序,在计算机上进行数值实验。表3中给出了利用SMDE算法以及文献中采用其他方法在无限含水层条件下数据的含水层参数计算结果。从表3中可知,文中方法和其他方法得到的计算结果非常接近,SMDE混合算法的计算结果是可靠的;同时还可以看出,由SMDE混合算法计算得到的含水层参数使得目标函数值φ达到了3.46210-6,由此可知,由SMDE混合算法得到的计算结果精度明显高于其他方法。

3.2.2在有隔水边界条件下的参数计算

采用表2的数据,由文中的SMDE算法得到的3个含水层参数分别为T =3.014 m2/min,μ=0.0663,ρ=107.433 m,对应的目标函数值为φ=3.82410-6。为了验证含水层参数计算结果的可靠性,将计算得到的含水层参数代入式(6),计算了水头降深s随时间的变化过程,如图2所示。由图2可以看出,

计算的水头降深随时间变化过程与实际观测的吻合非常良好。由此可以表明,文中方法同样适用于分析存在隔水边界含水层情况下的抽水试验数据,而且含水层参数的计算结果是可靠的。

3.2.3与其他算法的比较

(1)与单纯形算法的比较。

对于第2个算例,文中采用了待估参数初值的上限分别为含水层参数真值的2～8倍之间的4种初值取值范围方案,分别由单纯形法和单纯形差分进化混合算法进行100次运算。当目标函数值φ小于或等于4.010-6认为运算是收敛的,由收敛次数与总运算次数的比值作为算法的寻优率。表4中给出了不同情况下的寻优率。从表4明显可以看出,随着待估参数范围的扩大,单纯形算法易陷入局部最优的缺陷是非常明显的,而文中构造的混合算法能够很好地改善单纯形算法的此缺点,具有非常良好的收敛性。

(2)与差分进化算法的比较。

对于差分进化算法和单纯形差分进化混合算法的比较,文中采用待估参数初值的上限分别为含水层参数真值的2～10倍之间的4种初值取值范围方案,分别由连续进行100次运算,以得到的寻优率、平均最优值、平均参数来作为算法的优劣性衡量标准。

表5给出了通过Matlab编程分别采用2种算法得到的计算结果。从表5中可以看出待估参数初值的不同选取方案,对于DE算法有较大影响,随着待估参数范围的扩大,其寻优率降低较快,平均最优值也增加到1.810-5,且寻优率也降低到72% ;文中算法相对比较稳定,其计算的目标函数值均没有超过1.010-5,并且寻优率也都不低于90%;由此可以看出SMDE算法收敛性较好,而且计算结果精度也比较高。

4结语

通过对算法的构造思路和运算流程的介绍以及2种含水层条件下抽水试验数据分析,计算含水层参数的数值实验结果的讨论可知,文中构造的单纯形差分进化混合算法具有:①文中构造的单纯形差分进化混合算法能够有效地运用于求解分析抽水试验数据,确定含水层参数的函数优化问题,且能够使得目标函数值达到3.46210-6,计算结果精度明显高于其他方法的。②在2种不同含水层条件、不同的参数初值范围下,文种方法的寻优率均在90%以上,其明显高于单独的单纯形法或差分法的。因此,单纯形差分进化混合算法不失之为分析抽水试验资料,确定含水层参数的有效方法。

参考文献

[1]陈崇希,林敏.地下水动力学[M].武汉:中国地质大学出版社,1999:70-120.

[2]齐学斌.非稳定流抽水试验参数的迭代算法及计算机模拟[J].水利学报,1995,(5):67-71,66.

[3]郭建青,周宏飞,李彦,等.分析非稳定流抽水试验数据的改进直线解析法[J].中国农村水利水电,2009,(4):18-21.

[4]张娟娟,郭建青,韩淑敏,等.基于改进模拟退火算法反演水文地质参数[J].中国农村水利水电,2005,(9):8-11.

[5]郭建青,李彦,王洪胜,等.粒子群优化算法在确定含水层参数中的应用[J].中国农村水利水电,2008,(4):4-7.

[6]郭建青,李彦,王洪胜,等.确定含水层参数的混沌序列优化算法[J].中国农村水利水电,2006,(12):26-29.

[7]Stroll R,Prince K.Different final evolution:A survey of the state-of-the-art[J].IEEE Transaction on Evolutionary Computation,2011,15(1):4-31.

[8]张智星,孙春在.神经-模糊和软计算[M].西安:西安交通大学出版社,2000.

[9]谭跃,谭冠政,涂立.一种新的混沌差分进化算法[J].计算机工程学报,2009,35(11):216-218.

[10]R Srivastava.Implications of using approximation expressions for well function[J].Journal of Irrigation and Drainage Engineering,1995,121(6):459-462.

改进单纯形 第8篇

目前最主要的冷链物流业务有控温贮藏、冷藏运输和冷藏配送。如图2所示。

冷藏加工:包括鱼类、肉禽类和蛋类的冷却与冷冻,以及在低温状态下的加工作业过程;也包括蔬菜的预冷,各种速冻食物和奶制品的低温加工等;控温贮藏:包括食品的冷却储藏和冻结储藏,以及水果蔬菜等食品的气调储藏。冷藏运输及配送:包括食品的中、长途运输及短途配送等。它主要涉及铁路冷藏车、冷藏汽车、冷藏船、冷藏集装箱等低温运输工具。冷藏销售:包括各种冷链食品进入批发零售环节的冷冻冷藏和销售,它由生产厂家、批发商和零售商共同完成。

1 文献回顾

文献[1][2][3]对国际集装箱运输的发展趋势做了分析,指出目前国际冷藏货运量一直保持高速增长的趋势,并估计这一高速增长趋势将保持到2015年,未来冷藏集装箱的发展空间巨大。同时文献[10]中还提到英国德鲁里公司对全球冷藏货物运量的预测,并指出冷藏集装箱将在未来冷藏运输发展过程中扮演越来越重要的角色。

文献[4][5][6]总结了我国易腐货物的生产和运输情况,对市场需求的变化趋势做了分析,并指出我国冷链物流水平一直处于较为低下的水平,冷藏运输率太低,造成损耗大,每年导致的损失就达上千亿元。

文献[7][81[9]对我国铁路冷藏运输的市场竞争力及适应情况进行了分析,并指出了铁路冷藏运输存在的问题,同时给出了我国发展冷藏运输应该采取的措施。

文献[8]还对我国铁路易腐货物的冷藏运输运量进行了分析和预测。文献[19]分析了德国装运易腐货物的冷藏运输车辆基本情况。

文献[11][12][13]对冷藏集装箱的分类做了探讨,其中还包括对冷藏集装箱的发展现状及船舶冷藏箱的运行管理进行了详细分析,可为铁路冷藏集装箱的发展运营提供一定的参考。

上述文献中,对我国冷链物流运输定性的研究较多,缺少定量研究方法和算例,所以本文的研究具有一定的理论和实际意义。

2 基本模型

2.1 模型的构建

令O(k),k∈K,代表起运地的冷链运输集装箱空箱k,其中K代表不同类型的集装箱空箱(药品冷链空箱、食品冷链空箱、鲜花冷链空箱等);D(k),k∈K,表示目的地的集装箱空箱k;T(k),k∈K,表示转运地冷链集装箱空箱k;oundefined,i∈O(k),k∈K,冷链集装箱堆场i对冷链集装箱空箱k供应量;dundefined,i∈D(k),表示集冷链装箱堆场对冷链集装箱空箱k的需求量;uij,(i,j)∈A,表示弧(i,j)的容量(即弧(i,j)能承担的最大运量);uundefined,(i,j)∈A,表示在弧(i,j)冷链集装箱空箱k的最大运量。变量xundefined,(i,j)∈A,k∈K,表示集装箱空箱k在弧(i,j)的运量。令Cundefined(xundefined),(i,j)∈A,k∈K,表示弧(i,j)运输xundefined单位流量冷链集装箱空箱k的成本。

下述的模型即为多种冷链集装箱空箱最小成本的模型。

Minimize

undefined

Subject to

undefined

目标函数(1)是总的费用,约束条件(2)是对集装箱堆场i∈V和每一类货物k∈K的运量限制。约束条件(3)表示每一类货物k∈K通过每一条弧(i,j)的流量不超过容量uundefined。约束条件(4)(流量约束),表示对于每一条弧(i,j)∈A,通过弧(i,j)的总运量不大于运量uundefined。

对于任意的oundefined,k∈K,i∈O(k)和dundefined,满足下面的条件:

undefined

否则问题是行不通的。

虽然冷链集装箱有不同的类别,但是冷链物流公司使用的冷链集装箱大部分仍然是普通集装箱加装冷冻机。鉴于此,在实际应用中,构建单一品种的冷链集装箱空箱线性最小成本流模型。根据单种商品的线性最小成本流的原理,构建下面单一品种的冷链集装箱空箱线性最小成本流问题模型,同时,为了便于后面相关算例的验证,模型必须满足如下假设:

假设1:相同运输线路上几家独立的冷链物流公司,在运输线和时间间隔固定、一定计划周期内所有航运输班次都正好完成1次运输、每班次的运载工具容量已知的情形下,开展单一品种的冷链集装箱空箱的调运。

假设2:计划期开始时各堆场单一品种的冷链集装箱空箱的供给量和需求量已知,且据此可确定本期的供给地和需求地。

假设3:当客户对单一品种的冷链集装箱空箱的需求仅仅依靠调运已不能满足时,冷链物流公司将从其它冷链物流公司租用空箱。

假设4:冷链物流公司在各运输线路上的空箱运输费率、在各地的租箱费等成本参数已知。所以假设冷链物流公司各方面情况接近且计划期长度有限,任何城市都没有数量限制,并且能够即刻得到。因此认为在特定地方的同一计划期内租箱费用相同、恒定。

undefined

Subject to

undefined

单一品种的冷链集装箱空箱线性最小成本流问题模型,可以通过网络单纯形算法或其它的线性规划算法来求解。

2.2 网络单纯形法算法步骤

步骤1:找到一个初始的基本合适的结果x(0)。设h=0。

步骤2:确定与x(h)相关的减少成本。

步骤3:如果cundefined≥0,(i,j)∈A,停止运算,x(h)就是最优的结果;否则,选择变量xvw使xundefined<0。

步骤4:从基础变量中选择一个变量xpq,是xpq作为替代xvw的中间变量;令h=h+1,返回步骤2。

3 算例

某公司是一冷链物流运输承运商,当客户将货物从起运地运至目的地时,该公司提供一个或多个冷链空集装箱来装货。一旦到达目的地,货物卸下,空箱运至新接货点的客户。该公司的管理只需要周期性的重新分配空集装箱(实际中是一周一次)。空箱的运输费用是很高的(是总的运作费用的35%)。几十个空的冷链集装箱空箱需要在堆场1,堆场2,堆场3,堆场4,堆场5,堆场6,堆场7堆放。各个堆场的数量和需要的数量和运费,见图3。

基于运用网络单纯形法的理论,结合lingo数据包的计算,最优的结果可以在图4中获得,图中虚线部分表示没有冷链集装箱空箱运输,实线部分表示有冷链集装箱空箱。具体的空箱流如表1所示。可以明晰的看出各种堆场之间冷链集装箱空箱的流量。根据各堆场之间的空箱流,可以得出最优解是3900,即最小运输成本是3900。

4 结论

基于网络线性规划的冷链集装箱空箱调运优化模型,解决了冷链物流运输公司在不同的时期内,在不同的地点之间集冷链集装箱空箱的调运成本最低的问题,所以其也是基于时间延迟的动态模型,本文建立了冷链集装箱空箱的调运成本最低的模型,所列举的算例验证了同一种冷链集装箱空箱调运成本最低的优化模型,虽然做了一定的简化处理, 但是仍能证明冷链集装箱空箱调运优化定量分析的可操作性。

摘要：冷链物流运输的特殊性使得从事冷链物流运输的企业支付了高额的成本,针对目前的现实情况,从降低冷链物流运输过程中成本的角度,对冷链物流运输问题进行优化,使用线性规划的方法,对冷链物流运输过程中空箱的进出、中转构建模型,结合所构建的模型,给出相关的算例,根据给定的数据计算出结果验证了所构建模型的合理性,使冷链物流运输货物成本最低问题的研究又多了一种新的定量分析的方法。

改进单纯形 第9篇

关键词：单纯形,临界滑面,高速公路

边坡极限平衡分析非常重要的一步是寻找最小安全系数所对应的临界滑裂面。搜索临界滑裂面的方法主要包括三大类:枚举法, 数值分析法 (模式搜索法和牛顿法) 以及诸如模拟退火、遗传算法、神经网络等非数值算法。

W.Fellenius及D.W.Talor的研究成果指出:均质简单土坡, 其滑裂面为规则的圆弧, 且该圆弧通过坡脚[1]。对于这样的滑裂面, 寻找最危险滑面, 实际就是寻找安全系数函数的最小值:

其中, F (Xi) 为潜在的滑面安全系数;Xi为关于圆弧圆心坐标的二维向量, 即Xi= (xi, yi) T。

采用单纯形法构造一个三角形便可快速寻找到临界滑面。本文首先推导了以圆心坐标为参数的均质简单边坡的Bishop计算式, 并编写了基于单纯性法的临界滑面搜索程序, 将其运用于海南横线万宁—儋州—洋浦高速公路某深挖路堑边坡设计中。

1 以滑面圆心坐标为参数的安全系数求解

1.1 边坡计算模型

以坡脚处为原点, 建立如图1所示直角坐标系。边坡几何物理力学条件如下:圆弧滑面圆心坐标为 (X0, Y0) ;高度为H, 坡角为β;均布荷载为q, 距坡顶起点距离为B1, 作用宽度为B2;假设浸润线由几条直线连接而成, 各条浸润线端点坐标为 (XJi, YJi) , 其中第一条浸润线第一个端点为 (0, 0) 。

采用Bishop法计算滑面安全系数, 需要将上述已知条件转化为式 (2) 所需参数。

其中, 下标i表示任一土条;下标j为土层;γj为土层重度H (i, j) 为土条每一土层的高度;Bi为土条宽度;αi为土条重力与圆弧法线夹角;Ui为土条底部水压力;ci, φi分别为滑面粘聚力、内摩擦角;F为安全系数。

1.2 参数转换

在直角坐标系中求出圆弧、坡面线、坡顶线以及各条浸润线的方程。

圆弧方程:

坡面线方程:

坡顶线方程:

浸润线方程:

得到方程后, 按下述方法进行参数转换。

1) 将圆弧方程与坡顶线方程联立求解滑面与坡顶交点坐标 (XD, H) , 并求出坡面起点坐标 (Xs, H) 。2) 根据划分的土条数n将各土条设置为同一宽度Bi=XD/n, 并计算各分界线横坐标XFi=XFi-1+Bi, 将XFi代入圆弧方程取较小值求得YFi。3) 计算土条中线与滑面交点坐标 (XHi, YHi) 。XHi= (XFi+XFi-1) /2, 将XHi代入圆弧方程取较小值求得YHi。4) 计算土条中线与坡面交点坐标 (XPi, YPi) 。XPi=XHi;当XPi<Xs时, 将XPi代入坡面线方程求得YPi, 当XPi≥Xs时, YPi=H。5) 计算土条高度Hi。Hi=YPi-YHi。6) 计算土条分界线与浸润线交点纵坐标YJFi。根据土条分界线横坐标XFi与浸润线端点横坐标XJi+1, XJi的大小关系, 判断分界线与哪条浸润线相交, 然后将XFi代入该浸润线方程求得YJFi。7) 计算重力与圆弧法线夹角αi。根据土条中线横坐标与圆心横坐标的关系有三种情况:XHi<X0, αi=arctan[ (Y0-YHi) / (X0-XHi) ]-π/2。XHi=X0, αi=0。XHi>X0, αi=π/2-arctan[ (Y0-YHi) / (X0-XHi) ]。8) 计算土条底部水压力Ui。分界线上水面到滑面的高度Hwi=YJFi-YFi, 水压力Ui= (Hwi+Hwi-1) ·Bi/ (2cosαi) 。9) 计算外荷载Qi。根据分界线坐标与荷载左右边界的关系求得各土条上的外荷载Qi。

2 单纯形法搜索临界滑面的基本原理

2.1 单纯形法的基本思想

单纯形是指在n维向量空间具有n+1个顶点的多面体。对于本文所讨论的问题, 初始向量为关于圆心坐标的二维向量x0= (X0, Y0) T, 则以下述3个向量构成二维空间的三角形:x1=x0= (X0, Y0) T。x2= (X0+pl, Y0+ql) T。x3= (X0+ql, Y0+pl) T。其中, 。首先求出3个顶点的目标函数值F (xi) , 找出其中的最大值F (xh) , 最小值F (xl) 和中间值F (xm) , 对应顶点为xh, xl和xm。从这一个单纯形出发, 每次迭代都设法构造新的单纯形, 用新单纯形的一个顶点替换掉原单纯形具有最大安全系数F (xh) 的顶点, 以此逐步逼近目标函数的极小点。

2.2 单纯形的基本算法

单纯形主要包括反射、扩大、收缩和缩边四种操作。在操作前先求出除xh外两个顶点的中心xc, 以及中心的函数值F (xc) 。

1) 反射。将最大函数值顶点通过中心xc反射到对面xr, 并计算反射点的函数值F (xr) 。

其中, 通常取反射系数α=1。

2) 扩大。若F (xr) <F (xl) , 反射成功, 并表明沿着xcxr方向函数值有可能进一步下降, 因此将xr扩大到xe, 计算扩大点的函数值F (xe) 。

其中, 通常取扩大系数γ=2。

若F (xe) <F (xl) , 表明扩大成功, 用xe替换xh构成新的单纯形。若F (xe) ≥F (xl) , 表明扩大失败, 用xr替换xh构成新的单纯形, 进行收敛判定, 如图2所示。

3) 收缩。若F (xm) ≥F (xr) ≥F (xl) , 用xr替换xh, 构成新的单纯形, 进行收敛判定。若F (xh) >F (xr) >F (xm) , 用xr替换xh, 构成新的单纯形, 进行收敛判定。若F (xr) ≥F (xh) , 必须进行收缩操作, 将反射点收缩至xt, 并计算反射点的函数值F (xt) 。

其中, 通常取收缩系数β=0.5。

若F (xh) >F (xt) , 用xt替换xh, 构成新的单纯形, 进行收敛判定, 否则进行缩边操作。单纯形收缩操作见图3。

4) 缩边。当F (xt) ≥F (xh) 时进行缩边, 保持xl不变, 对其他顶点进行缩边操作, 得到新的单纯形, 进行收敛判定。单纯形缩边操作见图4。

5) 收敛准则。

其中, ε为足够小的数。

3 工程运用

3.1 工程及工点概况

海南横线万宁—儋州—洋浦高速公路, 路线全长164.1 km, 是《国务院关于推进海南国际旅游岛建设发展的若干意见》确定的交通基础设施项目, 是列入《海南国际旅游岛建设发展规划纲要》及《海南省公路交通“十二五”发展规划》的重点项目, 在完善海南岛路网结构, 充分发挥博鳌亚洲论坛及洋浦国家级经济开发区的区位优势, 以及促进中部市县快速发展等方面具有如下重要功能和作用。其主要技术标准为:四车道高速公路, 设计速度100 km/h, 路基宽26 m。

K130+180~K130+560段, 路线翻越垭口, 其中心挖深最大为12 m, 路堑边坡高度最高为28 m, 为深挖路堑, 需进行单独设计。

3.2 工点工程地质条件

垭口地形标高在131 m~169 m之间, 地貌单元属花岗岩残丘, 由印支期花岗岩及其残积土组成。覆盖层砂质粘土较厚, 基岩埋藏较深, 边坡属于均质土坡。其地下水埋深在路面以下3 m~4 m, 对边坡稳定性影响较小。与边坡稳定性计算相关的物理力学性质指标如表1所示。

3.3 稳定性分析

采用编制的单纯性临界滑面搜索程序对最大边坡高度的K130+500断面进行稳定性计算, 根据规范要求, 分别进行三种工况下的计算:正常工况Ⅰ, 暴雨或连续降雨工况Ⅱ, 地震作用工况Ⅲ。经过对边坡坡率的多次修改, 边坡稳定性计算结果符合规范要求, 如表2及图5所示, 表2对应的该横断面布置如表3所示。

3.4 防护工程设计

两侧路堑均为稳定边坡, 因此, 只采用一般的防护措施, 即拱形骨架和喷草植灌防护。

4 结语

均质简单边坡滑裂面为规则圆弧, 但其最危险滑面很难通过经验判断, 搜索最小安全系数临界滑面是正确评价边坡安全的关键。本文将单纯性算法搜索最危险滑面用于高速公路深挖路堑边坡, 通过该方法快速准确的对边坡稳定性进行评价, 从而合理的对边坡进行设计。

参考文献

[1]高大钊.土力学与基础工程[M].北京:中国建筑工业出版社, 1999.

[2]陈祖煜.土质边坡稳定分析——原理·方法·程序[M].北京:中国水利水电出版社, 2003.