纯形法的计算公式

1、单纯形法的矩阵描述单纯形法的矩阵描述单纯形法的矩阵表示单纯形法的矩阵表示标准型标准型maxz=cx ax=b x 0已知：已知：a、b、c a=(b n) mnmmmmmmmmnmmmnmmmaaaaaaaaaaaaaaaaaaa212122212222211211111211mmmmmmaaaaaaaaab212222111211mnmmmmnmmnmmaaaaaaaaan212221212111基阵基阵非基阵非基阵tmbxxxx21tnmmnxxxx21基基向向量量非非基基向向量量基变量基变量非基变量非基变量nbanbxxxbax bxxnbnbbnxbxnbnbnxbbxnbnxbbbx

2、11nbxxxnnxnxbbbx11令令0nx则则01bbx定义定义 在约束方程组在约束方程组(2) 中，对于中，对于一个选定的基一个选定的基b，令所有的非基变，令所有的非基变量为零得到的解，称为相应于基量为零得到的解，称为相应于基b的基本解。的基本解。定义定义 在基本解中，若该基本解满足非负约束，在基本解中，若该基本解满足非负约束，即即 ，则称此基本解为，则称此基本解为基本可行解基本可行解，简称简称基可行解基可行解；对应的基；对应的基b称为称为可行基可行基。01bbxb基本解中最多有基本解中最多有m个非零分量。个非零分量。基本解的数目不超过基本解的数目不超过 个。个。!mnmncmnnbnb

3、nnnbnnbbnbnbxnbccbbcxcnxbbbcxcxcxxcccxz)()(),(111101bbxb01nbccbnnbx若若b满足下列条件，称为满足下列条件，称为最优基最优基 称为称为最优解最优解等式右边等式右边b基变量基变量xb非基变量非基变量xnxbb1beb1n检验数检验数cb b1b(即即z) 0cn - cbb-1 n等式右边等式右边b变量变量xxbb1bb1a检验数检验数cb b1b(即即z)c - cbb-1 a单纯形表矩阵形式（单纯形表矩阵形式（p26p26）等式右边等式右边b基变量基变量xb非基变量非基变量xnxbbbn检验数检验数0cbcn 或者或者c - c

4、bb-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 bx 0maxz=cx+0x ax+ex= bx, x 0令令a=(a e) c=(c o)c- cb b-1 a=(c o)- cb b-1 (a e) =(c-cb b-1 a o-cb b-1 ) b-1 a= b-1(a e)=(b-1 a b-1 e)单纯形表矩阵形式（单纯形表矩阵形式

5、（p43p43）cb b-1 bb-1 bc- cb b-1 a - cb b-1 b-1 a b-1cb b-1单纯形算子单纯形算子等式右等式右边边b变量变量x松驰变量松驰变量xsxbb1bb1ab1检验数检验数-cb b1b(即即-z)c- cb b1a-cb b1-ys-y例：例：maxz=40x1 +50x2 x1 +2x2 +x3 =30 3x1 +2x2 +x4 =60 2x2 +x5 =24 xj 0 ( j=15)p1 p2 p3 p4 p5 1 2 1 0 03 2 0 1 00 2 0 0 1a=(1)、已知、已知b= (p3 p4 p2) 验证：验证：1 0 -10 1

6、-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) =(40, 50, 0, 0, 0) -(0 0 25) = (40, 50,

7、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 0 40 50 0 0 0 40 50 0 0 0 x1 x2 x3 x4 x5cb xb 0 40 50 0 0 0 0 40 50 0 0 0 0 0 x3 30 1 2 1 0 0 30 1 2 1 0 0 0 0 x4 6060 3 3 2 0 1 0 2 0 1 0 0

8、0 x5 24 0 (2) 0 0 1 24 0 (2) 0 0 1 xb 600 +40 0 0 0 -25 600 +40 0 0 0 -250 0 x3 6 (1) 0 1 0 -1 6 (1) 0 1 0 -1 0 0 x4 36 3 0 0 1 -1 36 3 0 0 1 -1 50 50 x2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 840 0 0 -40 0 15 840 0 0 -40 0 1540 40 x1 6 1 0 1 0 -16 1 0 1 0 -10 0 x4 18 0 0 -3 1 2 18 0 0 -3 1 250 50 x2 12 0 1

9、0 0 1/2 12 0 1 0 0 1/2b1-1b2-1b3-1 xb 975 0 0 -35/2 -15/2 0 975 0 0 -35/2 -15/2 040 40 x1 15 1 0 -1/2 1/2 0 15 1 0 -1/2 1/2 0 0 0 x5 9 0 0 -3/2 1/2 1 9 0 0 -3/2 1/2 1 50 50 x2 15/2 0 1 3/4 -1/4 0 15/2 0 1 3/4 -1/4 0b4-11 0 00 1 00 0 1b1= (p3 p4 p5)= b1 -1 =1 0 00 1 00 0 11 0 20 1 20 0 2b2= (p3 p4 p2

10、)= 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 +2

11、x2 120x1 =14x2 22x1 x2 0maxz=6x1 +4x2 -mx6 -mx72x1 +3x2 +x3 = = 1004x1 +2x2 +x4 = = 120x1 +x6 =14x2 -x5+x7 =22x1 x7 0 6 4 0 0 0 - 6 4 0 0 0 - m - - m x1 x2 x3 x4 x5 x6 x7cb xb -36 -36 m m +6 +6 m +4 0 0 - +4 0 0 - m 0 0 0 00 0 x3 100 2 3 1 0 0 0 0 100 2 3 1 0 0 0 0 0 0 x4 120120 4 4 2 0 1 0 0 0 2 0

12、1 0 0 0 -m x6 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 -m x7 22 0 1 0 0 -1 0 1cb xb 84 84-22m 0 0 m+4 0 0 - 0 0 -m 6-m 00 0 x3 72 0 3 1 0 0 -2 0 72 0 3 1 0 0 -2 0 0 0 x4 64 0 64 0 2 0 1 0 -4 0 2 0 1 0 -4 0 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 -m x7 22 0 1 0 0 -1 0 1cb xb 172 172 0 0 0 0 -4 0 0 -4 6- 6-m 4- 4-m0 0 x3 6 0 0 1 0 3 -2 -3 6 0 0 1 0 3 -2 -3 0 0 x4 2020 0 0 0 0 0 1 2 -4 -2 0 1 2 -4 -2 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 4 x2 22 0 1 0 0 -1 0 1cb xb 180 180 0 0 0 -4/3 0 -4/3