单纯形法的计算公式省公共课一等奖全国赛课获奖课件.pptx

单纯形法矩阵描述单纯形法矩阵描述第1页单纯形法矩阵表示单纯形法矩阵表示标准型标准型maxZ=CX AX=b X 0已知：已知：A、b、c A=(B N)第2页基阵基阵非基阵非基阵基基向向量量非非基基向向量量基变量基变量非基变量非基变量第3页令令则则定义定义 在约束方程组在约束方程组(2)中，对于中，对于一个选定基一个选定基B，令全部非基变量为，令全部非基变量为零得到解，称为对应于基零得到解，称为对应于基B基本解。基本解。第4页定义定义 在基本解中，若该基本解满足非负约束，在基本解中，若该基本解满足非负约束，即即 ，则称此基本解为，则称此基本解为基本可行解基本可行解，简称简称基可行解基可行解；对应基；对应基B称为称为可行基可行基。基本解中最多有基本解中最多有m个非零分量。个非零分量。基本解数目不超出基本解数目不超出 个。个。第5页若若B满足以下条件，称为满足以下条件，称为最优基最优基 称为称为最优解最优解第6页等式右边等式右边b基变量基变量XB非基变量非基变量XNXBB1bEB1N检验数检验数CB B1b(即即Z)0CN-CBB-1 N等式右边等式右边b变量变量XXBB1bB1A检验数检验数CB B1b(即即Z)C-CBB-1 A单纯形表矩阵形式（单纯形表矩阵形式（P26P26）等式右边等式右边b基变量基变量XB非基变量非基变量XNXBbBN检验数检验数0CBCN 或者或者第7页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 第8页规范形式：规范形式：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)第9页单纯形表矩阵形式（单纯形表矩阵形式（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第10页例：例：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=第11页(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第12页(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/2第13页A=C-CB B-1A=(40,50,0,0,0)-(0,0,50)=(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第14页(2)、3=-40,4=0P5=-1 2 1/2P3=1 -3 0第15页 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 0 X5 24 0 (2)0 0 1 24 0 (2)0 0 1 XB 600 [phone] [phone] 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 0 0 1/2 12 0 1 0 0 1/2B1-1B2-1B3-1第16页 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)=B2-1=1 0 -10 1 -10 0 1/2第17页(1)、只须存贮原始数据只须存贮原始数据A、B、C，每步需知每步需知B-1。(2)、每步必须计算数据每步必须计算数据 检验数检验数 N=CBB-1N-CN CBB-1=单纯形乘子单纯形乘子 当某个当某个 m+k 0时时，需关键列：需关键列：第18页Pm+k=B-1Pm+k=a1m+kamm+k 基变量基变量XB=B-1b=b1bm由由、，用最小，用最小 比值法得主元比值法得主元arm+k 主元已知，新基主元已知，新基B确定。返回确定。返回(1)第19页例例:maxZ=6X1+4X2 2X1+3X2 1004X1+2X2 120X1=14X2 22X1 X2 0maxZ=6X1+4X2-MX6-MX72X1+3X2+X3=1004X1+2X2+X4=120X1+X6=14X2-X5+X7=22X1 X7 0第20页 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 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 2 0 1 0 -4 0 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 1第21页CB 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 0 0 -M-10/3 -M0 0 X5 2 0 0 1/3 0 1 -2/3 -1 2 0 0 1/3 0 1 -2/3 -1 0 0 X4 1 16 0 6 0 0 -2/3 1 0 -8/3 0 0 -2/3 1 0 -8/3 0 6 X1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 4 X2 24 0 1 1/3 0 0 -2/3 -2第22页课后练习题1.131.17第23页