第1节单纯形法的矩阵描述 线性规划问题可表示为: 目标函数maxz=CBYB+CHN CBXB+CNXN +CsXs(2-1) 约束条件BXB+NXx=BB+NX+S2X b (2-2) 非负条件XB,X≥0 (3-2) 清华大学出版社
清华大学出版社 7 第1节 单纯形法的矩阵描述 线性规划问题可表示为： ,X ( ) b ( ) NX BX N X S X C X C X C X ( ) X C X N N B N S B B N N S S B N N X 0 3 2 2 2 BX 2 1 max z C B B 1 2 B 1 2 1 1 2 2 − = − + = + + = + + − = + 非负条件 约束条件 目标函数
第1节单纯形法的矩阵描述 将(2-2)式移项及整理后得到: BXB=b-NXN-S2Xs X=B.X 目标函数: z=CBBb+(CN -CRBNXN +(CS.-CRB1X 清华大学出版社
清华大学出版社 8 第1节 单纯形法的矩阵描述 将（2-2）式移项及整理后得到： S B S B N B N B N s B N S (C C B I )X z C B b (C C B N )X X B b B N X B S X ; BX b N X S X ; 1 1 1 1 2 1 1 1 1 1 2 2 1 1 1 2 1 2 − − − − − − + − = + − = − − = − − 目标函数：
第1节单纯形法的矩阵描述 令非基变量=0,由上式得到: 基可行解x/Bb 0 目标函数的值z=CBBb 清华大学出版社
清华大学出版社 9 第1节 单纯形法的矩阵描述 令非基变量=0，由上式得到： B b ; B b X ( ) 1 B 1 1 z C 0 − − = = 目标函数的值 基可行解
第1节单纯形法的矩阵描述 (1)非基变量的系数表示为: (CN,-CBB NI 对应已用的检验数符号 C1-1(j=1,2,…,n) 检验数也可表示为: C-CaBA与-CaB1 清华大学出版社
清华大学出版社 10 第1节 单纯形法的矩阵描述 （1）非基变量的系数表示为： 1 B 1 B j 1 1 C-C -C c 1 2 1 − − − − = − B A B z ( j , , ,n ) (C C B N ) j N B 与 检验数也可表示为： 对应已用的检验数符号
第1节单纯形法的矩阵描述 (2)规则表示为: RHS值 表示选用>0的分量 6=mi/(8 BP>0= (Bb) (BP) (B Pi) 换入变量的系数向量 清华大学出版社
清华大学出版社 11 第1节 单纯形法的矩阵描述 （2）θ规则表示为： RHS值 表示选用>0的分量 换入变量的系数向量 j i i j i j i i ( B P ) ( B b ) ( B P ) ( B P ) ( B b ) min 1 1 1 1 1 0 − − − − − = =