第一章单纯形法的计算公式

单纯形法的矩阵描述单纯形法的矩阵表示标准型maxZ=CXAX=bX0已知：A、b、cA=(BN)mnmmmmmmmmnmmmnmmmaaaaaaaaaaaaaaaaaaA212122212222211211111211mmmmmmaaaaaaaaaB212222111211mnmmmmnmmnmmaaaaaaaaaN212221212111基阵非基阵TmBxxxX21TnmmNxxxX21基向量非基向量基变量非基变量NBANBXXXbAXbXXNBNBbNXBXNBNBNXbBXNBNXBbBX11NBXXXNNXNXBbBX11令0NX则01bBX定义在约束方程组(2)中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。定义在基本解中，若该基本解满足非负约束，即，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。01bBXB基本解中最多有m个非零分量。基本解的数目不超过个。!!!mnmnCmnNBNBNNNBNNBBNBNBXNBCCbBCXCNXBbBCXCXCXXCCCXZ)()(),(111101bBXB01NBCCBNNBX若B满足下列条件，称为最优基称为最优解等式右边b基变量XB非基变量XNXBB－1bEB－1N检验数CBB－1b(即Z)0CN-CBB-1N等式右边b变量XXBB－1bB－1A检验数CBB－1b(即Z)C-CBB-1A单纯形表矩阵形式（P26）等式右边b基变量XB非基变量XNXBbBN检验数0CBCN或者C-CBB-1A=(CNCB)-CBB-1(NB)=(CN-CBB-1N,CB-CBB-1B)B-1A=B-1(NB)=(B-1N,B-1B)单个检验数：λj=Cj-CBB-1Pj某列Pj=B-1Pj规范形式：maxZ=CXAXbX0maxZ=CX+0·X′AX+EX′=bX,X′0令A′=(AE)C′=(CO)C′-CBB-1A′=(CO)-CBB-1(AE)=(C-CBB-1AO-CBB-1)B-1A′=B-1(AE)=(B-1AB-1E)单纯形表矩阵形式（P43）CBB-1bB-1bC-CBB-1A-CBB-1B-1AB-1CBB-1单纯形算子等式右边b变量X松驰变量XsXBB－1bB－1AB－1检验数-CBB－1b(即-Z)C-CBB－1A-CBB－1-Ys-Y例：maxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24Xj0(j=1…5)P1P2P3P4P5121003201002001A=(1)、已知B=(P3P4P2)验证：10-101-1001/2B-1=P5~,求λ1,λA,(2)、B=(P1P4P2)验证：10-1-312001/2B-1=P5~,求λ3,λ4,P3~(1)、λ1=C1-CBB-1P1=40-(0050)=40-(0,0,25)=4010-101-1001/2130130P5~=B-1P5=10-101-1001/2001=-1-11/2λA=C-CBB-1A=(40,50,0,0,0)-(0,0,50)=(40,50,0,0,0)-(0025)=(40,50,0,0,0)-(0,50,0,0,25)=(40,0,0,0,-25)10-101-1001/2121003201002001121003201002001(2)、λ3=-40,λ4=0P5=-121/2P3=1-304050000X1X2X3X4X5CBXB040500000X330121000X460320100X5240(2)001XB600+40000-250X36(1)010-10X4363001-150X21201001/284000-4001540X161010-10X41800-31250X21201001/2B1-1B2-1B3-1XB97500-35/2-15/2040X11510-1/21/200X5900-3/21/2150X215/2013/4-1/40B4-1100010001B1=(P3P4P5)=B1-1=100010001102012002B2=(P3P4P2)=B2-1=10-101-1001/2(1)、只须存贮原始数据A、B、C，每步需知B-1。(2)、每步必须计算的数据①检验数N=CBB-1N-CNCBB-1=单纯形乘子②当某个m+k﹥0时，需关键列：Pm+k=B-1Pm+k=a1m+kamm+k…③基变量XB=B-1b=b1bm…由②、③，用最小比值法得主元arm+k④主元已知，新基B确定。返回(1)例:maxZ=6X1+4X22X1+3X21004X1+2X2120X1=14X222X1X20maxZ=6X1+4X2-MX6-MX72X1+3X2+X3=1004X1+2X2+X4=120X1+X6=14X2-X5+X7=22X1…X7064000-M-MX1X2X3X4X5X6X7CBXB-36MM+6M+400-M000X310023100000X41204201000-MX6141000010-MX7220100-101CBXB84-22M0M+400-M6-M00X37203100-200X46402010-406X1141000010-MX7220100-101CBXB1720000-46-M4-M0X3600103-2-30X42000012-4-26X11410000104X2220100-101CBXB18000-4/300-M-10/3-M0X52001/301-2/3-10X41600-2/310-8/306X11410000104X224011/300-2/3-2•课后练习题1.13－1.17