将系数矩阵(A,I)分划为(BNI),其中B为可行基,对应于基变量向量 XBN对应于XN,I对应于XL,(XN,X)为非基变量向量。于是 X,L}=(XB,XNⅪL),C,0}=(CBCN、0)。因此,矩阵形式的LP模型改写为: MaxZ=(CB, CN O)Xn MaxZ=CBXB+CNXN+OX X (B, N,DX=b BX+Nx+x=b X XX,,X,≥0 X.XX,≥0 用非基变量向量表示基变量向量,有 XB=B-b-B. NXN-B XL 代入目标函数中有 Z=CB(B-b-B NXN-B-XLHCNXN+OXL -CBB-b-CBB-NXN-CBB-XLHCNXN =CBB-b-(CBB-N-CN)XN-CBB.XI 将 Z+(CRB N-CVXN+CRB CBB B NX+BX=bb 写成对应于基B的矩阵形式的单纯形表T(B) b b B B 0CBBN-CN 例如将例1化成标准型后如下表T(B)
-16- 将系数矩阵(A,I)分划为(B,N,I)，其中B为可行基，对应于基变量向量 XB,N 对应于 XN ， I 对 应 于 XL,(XN,XL) 为 非 基 变 量 向 量 。 于 是 (X,L)T=(XB,XN,XL) T,(C,0)=(CB,CN,0)。因此，矩阵形式的LP模型改写为： B B N N L L N B B N MaxZ C X C X X X X X MaxZ (C ,C ,0) = + + 0 = = , , 0 ( , , ) B N L L N B X X X b X X X B N I → + + = B , N , L 0 B N L X X X BX NX IX b 用非基变量向量表示基变量向量，有 XB=B-1b－B-1NXN－B-1XL 代入目标函数中有 Z =CB(B-1b－B －1NXN－B-1XL)+CNXN+0XL =CBB-1b－CBB-1NXN－CBB-1XL)+CNXN =CBB-1b－(CBB-1N－CN)XN－CBB-1XL 将 + + = + − + = − − − − − − X B NX B X B b Z C B N C X C B X C B b B N L B N N B L B 1 1 1 1 1 1 ( ) 写成对应于基B的矩阵形式的单纯形表T（B）： C→ CB CN CL b XB XN XL XB B b −1 1 B-1N B-1 Z CBB-1b 0 CBB-1N－CN CBB-1 例如将例1 化成标准型后如下表T（B）：
23000 1 CB XB 38 2 0 0010 23。。 ←0 初始可行基B=(P3,P4,Ps)=,X=(0,0,8.,16,12) (2)判别最优解 1°在T(B)中,若所有的检验数≥0(=1,2,…n) 则B为最优基,相应的基可行解为最优解,停止计算。 2°在T(B)中,若有0k<0(1≤k≤n),且xk的系数列向量P△≤0,则该问题 无界,停止计算。否则转入(3) (3)换基迭代(基变换) 1°先确定入基变量Xk:k=min{∝」0} 按最小比值原则确定出基变量 6=m 0 3°以ax为主元,进行初等行变换(又称旋转变换)即将列向量F变 换为单位列向量 返回(2)。 换基迭代的关键在于将换入变量对应的列向量P用初等行变换方法 变换成单位列向量。其中主元ax变成1。即
-17- Cj 2 3 0 0 0 i CB XB b x1 x2 x3 x4 x5 0 x3 8 1 2 1 0 0 0 x4 16 4 0 0 1 0 0 x5 12 0 4 0 0 1 -Z 0 -2 -3 0 0 0 σj 初始可行基B=(P3,P4,P5)=I, X=(0,0,8,16,12)T （2）判别最优解 1 在T(B)中，若所有的检验数σj≥0 (j=1,2,…,n) 则B为最优基，相应的基可行解为最优解，停止计算。 2 在T(B)中，若有σk<0 (1kn)，且xk的系数列向量Pk0，则该问题 无界，停止计算。否则转入（3） （3）换基迭代（基变换） 1 先确定入基变量Xk: k=min{j| j<0} 2 按最小比值原则确定出基变量xL： Lk L ik ik i a b a a b = = min | 0 3 以 LK a 为主元，进行初等行变换（又称旋转变换）即将列向量 PK 变 换为单位列向量： 返回（2）。 换基迭代的关键在于将换入变量对应的列向量 PK 用初等行变换方法 变换成单位列向量。其中主元 LK a 变成1。即