单纯形法 之 出基入基_单纯形法怎么换基迭代

单纯形法 之 出基入基由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“单纯形法怎么换基迭代”。

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

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

（2）出变量的确定

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

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

设p1,p2,....pm是一组线性独立的向量组，它们对应的基可行解是X(0)。将它代入约束方程组中pxb，x0,j1,2,...,n中得到 jjnjj1(0)xiPib

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

Pmti,mtPi

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

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

m(0)xiPiPmti,mtPib i1i1(0)(xii,mt)PiP或mtb（3）i1mm当取适当值时，就能得到满足约束条件的一个可行解（即非零分量的数目不大于m个）。就应使(xi(0)i,mt)(i1,2,...,m)中的某一个为零，并保证其余的分量为非负。这个要求

x可以用以下的办法达到：比较各比值

(0)i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ti,mt这时xi为换出变量。按最小比值确定值，称为最小比值规则。将便得到新的基可行解。

xi(0)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(0)转换到X(1)的各分量的转换公式

(0)X(1)ixi0xl,ili,mtx(0)l ,il1,mt(0)这里xi(0)是原基可行解X的各分量；Xi(1)是新基可行解X(1)的各分量；i,mt是换入向量Pmt的对应原来一组基向量的坐标。现在的问题是，这个新解X(1)的m个非零分量对应的列向量是否线性独立？事实上，因X(0)的第l个分量对应于X(1)的相应分量是零，即

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

其中Xl(0)，均不为零，根据规则（最小比值），l,mt0。X(1)中的m个非零分量对应的m个列向量是Pj(j1,2,...,m,jl)和Pmt。若这组向量不是线性独立，则一定可以找到不全为零的数j，使

PmtjPj,jl（4）

j1m成立。又因

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

j1m将（5）式减（1）式得到

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

由于上式中至少有l,mt0，所以上式表明P1,P2,...,Pm是线性相关，这与假设相矛盾。由此可见，X(1)的m个非零分量对应的列向量Pj(j1,2,...,m)与Pmt是线性独立的，即经过基变换得到的解是基可行解。实际上，从一个基到另一个基可行解的变换, 就是进行一次基变换。从几何意义上讲, 就是从可行域的一个顶点转向另一个顶点。