4 第二章单纯形法 其中CB,XB分别为C和X中与m个基变量对应的分量组成的m维向量，Cv,Xw分别 为C和X中与n-m个非基变量对应的分量组成的n-m维向量，则约束方程AX=b 可以写为： aN(Xe）= 利用分块矩阵的乘法可得： BXB+NXN=6 两边乘以B1,得： XB+B-INXN B-1b 移项可得： XB=B-1b-B-INXN 目标函数z=CX可表示为： cc) CBXB+CNXN 把XB=B-b-B-1NXw代入上式得 z=CB(B-16-B-INXN)+CNXN CBB-1b+(CN-CBB-IN)XN 据此原线性规划问题可转换为如下等价形式 min 2=CBB-b+(CN-CBB-IN)XN (2.8) 满足 XB+B-1VXw=B-b X20 (2.9 显然上式与原问题完全等价，即两个问题的解完全相同，称上述问题为可行基1,2，工n 对应的典式对非基变量，令 g=B-lB=(@a吃，am) 并令 B-1b=(,,,n) 则 B-N =B-1(Pm+1.Pm+2.....Pn)=(B-IPm+1,B-1Pm+2.....B-1Pn) ai,m+1 1n =(Pm+1,Pm+2,'.,P)= m+1a吃，m+2…a吃.n m+1 dm.m+2 4 ò✡ó✡ôöõ✡÷✡ø❤ù ✾î✹ CB, XB ✤❈➾❈❉ C ✮ X ✹ç✿ m ✗❈ÿ❈❝❈❞❈â❈✫❈✕❈✤❈❞❈è❈❨❈✕ m Òîãç❞, CN , XN ✤❈➾ ❉ C ✮ X ✹❥✿ n − m ✗✁✡✡ÿ✡❝✡❞✡â✡✫✡✕✡✤✡❞✡è✡❨✡✕ n − m Ò❤ã❥❞, ➓✡❪✡❫Þ✡ß AX = b ❳✡ä✡å✡❉: (B, N) XB XN ! = b Ó ✭✡✤✁ÔÛ✡Ü✕✁Õ✡❃✡❳✡✼: BXB + NXN = b ➋✁Ö✁Õ✡ä B−1 , ✼: XB + B −1NXN = B −1 b ×✁Ø❳✡✼: XB = B −1 b − B −1NXN ÑÓ➹✡Ô✡Õ z = CX ❳✁Ð✁Ñ✡❉: z = (CB, CN ) XB XN ! = CBXB + CN XN ➛ XB = B−1 b − B−1NXN Ù✁Ú❬✁Û✡✼ z = CB(B −1 b − B −1NXN ) + CN XN = CBB −1 b + (CN − CBB −1N)XN ❛þ✁Ü✌✡✍✡✎✡✏✡❑✡▲✡❳✁Ý✁Þ✡❉✟✁ß②✁à✡❂✁Û: min z = CBB −1 b + (CN − CBB −1N)XN (2.8) ➴✡➷ ( XB + B−1NXN = B−1 b X ≥ 0 (2.9) á✴❬➂Û✿Ü❑▲➂â➂ã②➂à, ❣➋✗❑▲✕❏➂â➂ã➂Ï➂ä, ➱❬☞ ❑▲❉❳➌ÿ x1 , x2, . . . , xm â✡✫✡✕✏å✁æ. â✁✡✡ÿ✡❝✡❞ xj , à P 0 j = B −1Pj = (a 0 1j , a 0 2j , . . . , a 0 mj ) T ➠✡à B −1 b = (b 0 1 , b 0 2 , . . . , b 0 m) T ➓ B −1N = B−1(Pm+1, Pm+2, . . . , Pn) = (B −1Pm+1, B −1Pm+2, . . . , B −1Pn) = (P 0 m+1, Pm+2, 0 . . . , P 0 n) =   a 0 1,m+1 a 0 1,m+2 . . . a 0 1,n a 0 2,m+1 a 0 2,m+2 . . . a 0 2,n . . . . . . . . . . . . a 0 m,m+1 a 0 m,m+2 . . . a 0 m,n  