单纯形法 之 出基入基

通过检验，初始可行解可能不是最优解。通过基变换得到一个新的可行基，具体做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到新的基本可行解，使目标函数值更优。为了换基就要确定换入变量与换出变量。

（1）入基变量的确定

从最优解判别定理知道，当某个j0时，非基变量xj不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去。若有两个以上的，则为了是目标函数增加的更大一些，一般选j最大者的非基变量为入变量。

（2）出变量的确定

确定出基变量的方法如下。把已确定的入基变量在各约束方程中的系数除其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。

下面再进行检验其最优性，如果不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。

设p1,p2,....pm是一组线性的向量组，它们对应的基可行解是X。将它代入约束方程

(0)组中

pxbjjj1n，

xj0,j1,2,...,n中得到

(0)xiPibi1m (1)

其他的向量Pm1,Pm2,...Pmt,...,Pn都可以用P1,P2,...Pm,线性表示，若确定非基变量pmt为换入变量，必然可以找到一组不全为0的数（i1,2,...,m）使得

mPmti,mtPii1m

或

Pmti,mtPi0i1 (2)

在（2）式两边同乘一个正数，然后将它加到（1）式上，得到

mxiPiPmti,mtPibi1 i1

(0)m或

(xi1m(0)ii,mt)PiPmtb （3）

当取适当值时，就能得到满足约束条件的一个可行解（即非零分量的数目不大于m个）。就应使

(xi(0)i,mt)(i1,2,...,m)中的某一个为零，并保证其余的分量为非负。这个要求可以

xi(0)用以下的办法达到：比较各比值

i,mt(i1,2,...,m)。又因必须是正数，所以只选

xi(0)择i,mt0(i1,2,...,m)中比值最小的等于。以上描述用数学使表述为：

xi(0)xi(0)min|i,mt0ii,mti,mt

xi(0)这时为换出变量。按最小比值确定值，称为最小比值规则。将便得到新的基可行解。

xii,mt带入X中，

X1(0)(x1(0)xi(0)l,mt(0)1,mt,...,0,...,xmxi(0)l,mtm,mt,0,...,xi(0)l,mt,0...,)

  第l个分量 第m+t分量

由此得到由X转换到X的各分量的转换公式

(0)(1)Xi(1) 这里

xi(0)(0)xi,ili,mtx(0)l,il1,mt0xl(0)

是原基可行解 X的各分量；

Xi(1)(1)是新基可行解 X的各分量； i,mt 是换

(1)入向量Pmt的对应原来一组基向量的坐标。现在的问题是，这个新解X的m个非零分量对应的列向量是否线性？事实上，因X的第l个分量对应于X的相应分量是零，即

(0)(1)

Xl(0)l,mt0

其中

Xl(0)，均不为零，根据规则（最小比值），

Pj(j1,2,...,m,jl)l,mt0。X中的m个非零分量对

(1)应的m个列向量是全为零的数

j和Pmt。若这组向量不是线性，则一定可以找到不

，使

PmtjPj,jlj1m （4）

成立。又因

Pmtj,mtPjj1m （5）

将（5）式减（1）式得到

由于上式中至少有

(1)j1,j1m(j,mtj)Pjl,mtPl0

1,P2,...,Pm是线性相关，这与假设相矛盾。，所以上式表明Pl,mt0由此可见，X的m个非零分量对应的列向量

Pj(j1,2,...,m)与Pmt是线性的，即经过基

变换得到的解是基可行解。实际上，从一个基到另一个基可行解的变换, 就是进行一次基变换。从几何意义上讲, 就是从可行域的一个顶点转向另一个顶点。