《武汉工程大学学报》 2008年01期
122-124
出版日期：2008-01-30
ISSN:1674-2869
CN:42-1779/TQ
单纯形法中确定主元素的两个新法则
0引言单纯形法中确定主元素的最好策略是什么?这个问题迄今尚未完全解决［1］．确定主元素是单纯形法求解过程中的一个重要环节，因为主元素选择的好坏直接影响到收敛速度与迭代次数．经典的做法是按照“最大σ法则”［2］，并结合“θ法则”［2］来确定主元素，这种做法的明显缺陷是，不能保证迭代次数尽量少和收敛速度尽量快．文献［3］中提出的算法不失为解决这一问题的一个较好的方案.如果按使目标函数值增加得最多的原则来确定主元素或按使目标函数值增加得最快的原则来确定主元素，则可以在一定程度上克服这种缺陷，从而提高单纯形法的效率．1使目标函数值增加得最多的原则设线性规划问题经过k步迭代后的单纯形表如表1.表1经k步迭代后的单纯形表
Table 1Simplex table after iteration step of k
cjc1…ci…cm…cj…cnCB基βx1…xi…xm…xj…xnc1x1β11…α1j…α1ncixiβi1αij…αincmxmβm1…αmj…αmnσj0…0…0…σj…σn若某个检验数σj>0，且至少有一个αsj>0时，令θj=minsβsαsj|αsj>0=βiαij
则k+1=k+θjdj.
其中k表示迭代k次后的基本可行解，k+1表示迭代k+1次后的基本可行解，dj=（-α1j,-α2j,…,-αmj,0,…,1,0,…,0）T（1是第j个分量）是第k+1步迭代的迭代方向．k+1处的目标函数值为cTk+1=cT(k+θjdj)=cTk+cTθjdj=
cTk+θjcTdj=cTk+θjσj.
显然k+1处的目标函数值较k处的目标函数值要大（至少不小），增量为θjσj．为使目标函数值增加得最多，可选取使θpσp达到最大的p作为主元素的列标，即θpσp=maxj｛θjσj|σj>0｝.于是有下面的定理：定理1在单纯形法的每次迭代中，主元素的列标p按公式（1）确定θpσp=maxj{θjσj|σj>0}（1）
可使目标函数值增加得最多．2使目标函数值增加得最快的原则按照定理1确定主元素虽然使目标函数值增加得最多，但增加的速度不一定是最快的．下面给出另一个确定主元素的法则，按照这一原则确定主元素可使目标函数值增加得最快．首先给出速度的定义定义速度就是指单位距离内目标函数值的平均增量．第k+1步迭代的速度用公式表示就是
Vk+1=cT k+1-cT k‖k+1-k‖2
这里‖k+1-k‖2=∑nj=1(k+1,j-kj)2指的是相邻两点k+1与k之间的距离，其中k+1,j与kj(j=1,2,…,n)分别指k+1与k的第j个分量.由第1节的讨论可得Vk+1=cTk+1-cTk‖k+1-k‖2=θjσj‖θjdj‖2=
σj‖dj‖2=σj1+∑mi=1α2ij.
显然要使Vk+1最大，主元素的列标p应满足如下条件σp1+∑mi=1α2ip=maxjσj1+∑mi=1α2ijσj>0.于是得到定理2.定理2在单纯形法的每次迭代中，主元素的列标p按照公式（2）确定σp1+∑mi=1α2ip=maxjσj1+∑mi=1α2ijσj>0，（2）
可使目标函数值增加得最快．第1期罗进，等：单纯形法中确定主元素的两个新法则
武汉工程大学学报第30卷
3实例分析例求解线性规划问题 maxZ=9x1+8x2+40x3+19x4s.t.3x1+2x2+10x3+4x4≤18，
2x3+12x4≤3，
x1,x2,x3,x4≥0.加入松弛变量x5,x6，化问题为标准形
maxZ=9x1+8x2+40x3+19x4+0x5+0x6s.t.3x1+2x2+10x3+4x4+x5=18,
2x3+12x4+x6=3，
xj≥0(j=1,2,…,6).下面分别用三种确定主元素的方法来求解这个问题．方法一按“最大σ法则”，并结合“θ法则”确定主元素进行迭代（求解过程见表2~6）.
表2初始单纯形表
Table 2Initial simplex table
cj98401900 CB基β x1 x2 x3 x4 x5 x60x51832104100x6 300［2］12 01σj 98401900表3经1步迭代后的单纯形表
Table 3Simplex table after iteration step of 1
cj 98401900 CB 基 βx1x2x3x4x5 x60x53［3］20321-540x33200114012σj 98090-20表4经2步迭代后的单纯形表
Table 4Simplex table after iteration step of 2
cj 98401900 CB 基βx1 x2x3x4x5 x69x111230［12］13-5340x33200114012σj 02092-3-5表5经3步迭代后的单纯形表
Table 5Simplex table after iteration step of 3
cj 98401900 CB 基βx1x2x3x4x5 x619x422430123-10340x31-12-1310-16［43］σj-9-400 -610表6经4步迭代后的单纯形表
Table 6Simplex table after iteration step of 4
cj 98401900 CB 基βx1 x2x3x4x5 x619x49234125211400x634-38-14340-181σj-214-32-1520-1940从表6可得标准形的最优解为X*=0,0,0,92,0,34T.方法二利用定理1确定主元素进行迭代.在初始单纯形表（表2）中，σ1θ1=9×6=54,σ2θ2=8×9=72,σ3θ3=40×32=60,σ4θ4=19×92=1712.
因σ4θ4最大，利用定理1，取a14=4为主元素．经1次迭代后即得表6．方法三利用定理2确定主元素进行迭代.在初始单纯形表（表2）中，σ11+∑2i=1α2i1=91+32=8110，σ21+∑2i=1α2i2=81+22=645,σ31+∑2i=1α2i3=401+102+22=1600105,σ41+∑2i=1α2i4=191+42+122=144469.因σ41+∑2i=1α2i4=144469最大，利用定理2，选取第4列为主列，再利用θ法则确定a14=4为主元素．经1次迭代后即得表6．按方法一求解共需进行4次迭代，而按方法二、三求解仅需进行1次迭代即可求得最优解．4结语从上面这个简单的例子可以看出，按使目标函数值增加得最多的原则来确定主元素或按使目标函数值增加得最快的原则来确定主元素，较应用“最大σ法则”来确定主元素，具有迭代次数更少、收敛速度更快的特点．