单纯形法 之 出基入基.docx

通过检验，初始可行解可能不是最优解通过基变换得到一个新的可行基，具体做法 是从可行基中换一个列向量，得到一个新的可行基，使得求解得到新的基本可行解，使目 标函数值更优为了换基就要确定换入变量与换出变量1）入基变量的确定从最优解判别定理知道，当某个时，非基变量不取零值可以使目标函数值增0jjx大，故我们要选基检验数大于 0 的非基变量换到基变量中去若有两个以上的，则为了是目标函数增加的更大一些，一般选最大者的非基变量为入变量j（2）出变量的确定确定出基变量的方法如下把已确定的入基变量在各约束方程中的系数除其所在约束方 程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量下面再进行检验其最优性，如果不是最优解还要继续进行基变换，直至找到最优解，或 者能够判断出线性规划无最优解为止设是一组线性独立的向量组，它们对应的基可行解是将它代入约束方1,2, ....mp pp(0)X程组中，中得到 1nj jjpxb0,1,2,...,jxjn(1)(0)1miiixPb其他的向量都可以用线性表示，若确定非基变量12,,...,...,mmmtnPPPP12,,...,mP PP为换入变量，必然可以找到一组不全为 0 的数（）使得mtp1,2,...,im,1mmti mtiiPP或 (2),10mmti mtiiPP在（2）式两边同乘一个正数，然后将它加到（1）式上，得到(0),11mmiimti mtiiixPPPb或 （3）(0) , 1()miii m tm t ixPPb 当取适当值时，就能得到满足约束条件的一个可行解（即非零分量的数目不大于个） 。

m就应使中的某一个为零，并保证其余的分量为非负这个要(0) ,()(1,2,...,)mtiixim求可以用以下的办法达到：比较各比值又因必须是(0),(1,2,...,)ii mtxim正数，所以只选择中比值最小的等于以上描述用数学(0),0(1,2,...,)ii m txim使表述为：(0)(0), ,,min|0ii i m tii m ti m txx 这时为换出变量按最小比值确定值，称为最小比值规则将带入中，ix(0),ii m txX便得到新的基可行解0)(0)(0) (0)(0)(0) 111,, ,,,(,...,0,...,,0,...,,0...,)iii m tmm m t l m tl m tl m txxxXxx gg第 l 个分量 第 m+t 分量由此得到由转换到的各分量的转换公式(0)X(1)X (0)0, (0)1,,(1),li i m tlm txxi lixi lX这里是原基可行解 的各分量；是新基可行解 的各分量； 是换(0) ix(0)X(1) iX(1)X, i m t入向量的对应原来一组基向量的坐标。

现在的问题是，这个新解的个非零分m tP(1)Xm量对应的列向量是否线性独立？事实上，因的第 个分量对应于的相应分量是零，(0)Xl(1)X即(0) ,0ll m tX其中，均不为零，根据规则（最小比值） ，中的个非零分量对(0) lX,0l m t(1)Xm应的个列向量是和若这组向量不是线性独立，则一定可以m(1,2,...,,)jPjm jlm tP找到不全为零的数，使j（4） 1,mm tjj jPP jl 成立又因（5）, 1mm tj m tj jPP 将（5）式减（1）式得到,, 1,1()0mj m tjjl m tl jjPP 由于上式中至少有 ，所以上式表明是线性相关，这与假设相矛盾0l m t12,,...,mP PP由此可见，的个非零分量对应的列向量与是线性独立的，即(1)Xm(1,2,...,)jPjmm tP经过基变换得到的解是基可行解实际上，从一个基到另一个基可行解的变换, 就是进行 一次基变换从几何意义上讲, 就是从可行域的一个顶点转向另一个顶点。