(2.6.3)--02_6_3基变换.pdf

换入变量的确定由其对应的为换入变量。若有两个以上的，为了使目标函数的值增加得快，一般选择中最大值，即基变换（2-28）其他向量Pm+1，Pm+2 Pm+t Pn都可以用P1，P2 Pm线性表示，若确定非基变量xm+t为换入变量，必然可以找到一组不全为零的数（i=1,2,m）使得（2-29）换出变量的确定设P1，P2 Pm是一组线性独立向量组，它们对应的基可行解是X(0)。代入约束方程得：在2-29两边同乘一个正数，与（2-28）相加，得：（2-30）当取适当值时，就能得到满足约束条件的一个可行解（即非零分量的数目不大于m个）.并保证其余的分量为非负.比较正数选择中比值最小的等于应使中的某一个为0，即：将求出的代入X中，得到新的基可行解：换入变量对应的列向量是否能与原来的基向量的剩余向量构成一个基？为换出变量最小比值规则规则第l个分量第m+t个分量即X X(1)(1)的非零分量对应的列向量是否线性独立若它们不是线性独立，则Pm+t可以用Pj中线性表示，即存在不全为零的数j，使（2-31）（2-32）X(1)中的m个非零分量对应的m个列向量X(0)的第个分量对应于X(1)的相应分量为零即和Pm+t（2-32）-（2-31）得：与假设矛盾.P1，P2 Pm线性相关和Pm+t线性独立X X(1)(1)的中的m个非零分量对应的m个列向量新组成的向量组是LP的一个基.迭代（旋转运算）x1+a1,m+1xm+1+a1,kxk+a1nxn=b1x2+a2,m+1xm+1+a2kxk+a2nxn=b2xl+al,m+1xm+1+alkxk+alnxn=b2 xm+am,m+1xm+1+am,kxk+amnxn=bm（2-33）若不是最优解，根据规则，确定换出换入变量设xk为换入变量,则为：在迭代过程中可表示为：x1,x2,xl,xm为基变量，对应的系数列向量组成一个基.令：xm+1=xm+2=xn=0,X(0)=（b1，b2，bm，0，0）T根据 规则xl为换出变量，把xk与xl对换：Pk=Pl=经过迭代后：第l个分量（2-33）系数矩阵的增广矩阵为：（2-34）进行初等变换:（2-35）1.为了为主元素2.新的增广矩阵各元素的变换公式为:新的增广矩阵为:x1、x2xl-1、xk、xl+1 xm构成新的基变量.令非基变量xm+1=xl=xn=0,得:TlmllbbbbbbX)0,0,0,0,(1121)1(例2-max z=2x1+3x2+0 x3+0 x4+0 x5 x1+2x2+x3 =84x1+x4 =164x2 +x5=12x1,x2 0系数矩阵的增广矩阵为：X(0)=（,0,8,16,12）TX(1)=（0,3,2,16,0）T