《第一章 单纯形法的计算公式》由会员分享，可在线阅读，更多相关《第一章 单纯形法的计算公式（23页珍藏版）》请在金锄头文库上搜索。
1、单纯形法的矩阵描述单纯形法的矩阵表示标准型maxZ=CXAX=bX 0已知：A、b、cA=(B N)基阵非基阵基 向 量非 基 向 量基变量非基变量令则定义 在约束方程组(2) 中，对于 一个选定的基B，令所有的非基变 量为零得到的解，称为相应于基B 的基本解。定义 在基本解中，若该基本解满足非负约束， 即 ，则称此基本解为基本可行解， 简称基可行解；对应的基B称为可行基。基本解中最多有m个非零分量。基本解的数目不超过 个。若B满足下列条件，称为最优基称为最优解等式右边边b基变变量XB非基变变量XN XBB1bEB1N 检验检验 数CB B1b(即Z) 0CN - CBB-1 N等式右边边b变
2、变量XXBB1bB1A检验检验 数CB B1b(即Z)C - CBB-1 A单纯形表矩阵形式（P26）等式右边边b基变变量XB非基变变量XNXBbBN检验检验 数0CBCN 或者C - CBB-1A= (CN CB )- CBB-1 (NB )= (CN - CBB-1N, CB -CBB-1B)B-1A= B-1(N B )= (B-1N, B-1B)单个检验数：j = Cj - CBB-1 Pj 某列Pj = B-1 Pj 规范形式：maxZ=CX AX bX0maxZ=CX+0X AX+EX= bX, X0令A=(A E) C=(C O)C- CB B-1 A=(C O)- CB B-1
3、 (A E)=(C-CB B-1 A O-CB B-1 ) B-1 A= B-1(A E)=(B-1 A B-1 E)单纯形表矩阵形式（P43） CB B-1 b B-1 bC- CB B-1 A - CB B-1 B-1 A B-1CB B-1单纯形算子等式右 边边b变变量X松驰变驰变 量 XsXBB1bB1AB1检验检验 数-CB B 1b(即- Z)C- CB B 1A-CB B1-Ys-Y例：maxZ=40X1 +50X2 X1 +2X2 +X3 =303X1 +2X2 +X4 =602X2 +X5 =24Xj 0 ( j=15)P1 P2 P3 P4 P5 1 2 1 0 03 2
4、0 1 00 2 0 0 1A=(1)、已知B= (P3 P4 P2) 验证：1 0 -10 1 -10 0 1/2B-1 =P5,求1 , A ,(2)、B= (P1 P4 P2) 验证：1 0 -1-3 1 20 0 1/2B-1 =P5,求3 , 4,P3(1)、1 =C1 - CB B-1P1=40 -(0 0 5 0)= 40 -(0,0,25) =401 0 -10 1 -10 0 1/21 3 01 3 0P5= B-1P5 =1 0 -10 1 -10 0 1/20 0 1=-1 -1 1/2A= C - CB B-1A=(40, 50, 0, 0, 0)-(0, 0, 50)
5、=(40, 50, 0, 0, 0) -(0 0 25)= (40, 50, 0, 0, 0) -(0, 50, 0, 0, 25)= (40, 0, 0, 0, -25)1 0 -10 1 -10 0 1/21 2 1 0 03 2 0 1 00 2 0 0 11 2 1 0 03 2 0 1 00 2 0 0 1(2)、3 = -40 ,4= 0P5 =-1 2 1/2P3 =1 -3 040 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 X3 30 1 2 1 0 0 0 X4 60 3 2 0 1 0 0 X5 24 0 (2) 0 0 1
6、XB 600 +40 0 0 0 -250 X3 6 (1) 0 1 0 -1 0 X4 36 3 0 0 1 -1 50 X2 12 0 1 0 0 1/2 840 0 0 -40 0 1540 X1 6 1 0 1 0 -10 X4 18 0 0 -3 1 250 X2 12 0 1 0 0 1/2B1-1B2-1B3-1XB 975 0 0 -35/2 -15/2 040 X1 15 1 0 -1/2 1/2 0 0 X5 9 0 0 -3/2 1/2 1 50 X2 15/2 0 1 3/4 -1/4 0B4-11 0 00 1 00 0 1B1= (P3 P4 P5)= B1 -1
7、=1 0 00 1 00 0 11 0 20 1 20 0 2B2= (P3 P4 P2)= B2 -1 =1 0 -10 1 -10 0 1/2(1)、只须存贮原始数据A、B、C，每步需知B-1 。(2)、每步必须计算的数据 检验数N = CBB-1N - CN CBB-1 =单纯形乘子 当某个m+k 0时，需关键列：Pm+k = B-1Pm+k =a1m+kamm+k 基变量XB = B-1b =b1bm由 、，用最小 比值法得主元arm+k 主元已知，新基B确定。返回(1)例:maxZ=6X1 +4X2 2X1 +3X2 1004X1 +2X2 120X1 =14X2 22X1 X2 0
8、maxZ=6X1 +4X2 -MX6 -MX72X1 +3X2 +X3 = 1004X1 +2X2 +X4 = 120X1 +X6 =14X2 -X5+X7 =22X1 X7 06 4 0 0 0 - M - M X1 X2 X3 X4 X5 X6 X7CB XB -36 M M +6 M +4 0 0 - M 0 00 X3 100 2 3 1 0 0 0 0 0 X4 120 4 2 0 1 0 0 0 -M X6 14 1 0 0 0 0 1 0 -M X7 22 0 1 0 0 -1 0 1CB XB 84-22M 0 M+4 0 0 -M 6-M 00 X3 72 0 3 1 0 0 -2 0 0 X4 64 0 2 0 1 0 -4 0 6 X1 14 1 0 0 0 0 1 0 -M X7 22 0 1 0 0 -1 0 1CB XB 172 0 0 0 0 -4 6-M 4-M0 X3 6 0 0 1 0 3 -2 -3 0 X4 20 0 0 0 1 2 -4 -2 6 X1 14 1 0 0 0 0 1 0 4 X2 22 0 1 0 0 -1 0 1CB XB 180 0 0 -4/3 0 0 -M-10/3 -M0 X5 2 0 0
