16改进单纯形法简介

1§1.6改进单纯形法简介(一)、单纯形法的矩阵表示标准型maxZ=CXAX=bX0已知：A、b、cA=(NB)B=E2用非基变量表示基变量Z=CBB-1b+(CN-CBB-1N)XNXB=B-1b-B-1NXNCBB-1bCN-CBB-1NOB-1bB-1NECBB-1bC-CBB-1AB-1bB-1A3C-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-1Pj4例：maxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24Xj0(j=1…5)P1P2P3P4P5121003201002001A=5(1)、已知B=(P3P4P2)验证：10-101-1001/2B-1=P5~,求λ1,λA,(2)、B=(P1P4P2)验证：10-1-312001/2B-1=P5~,求λ3,λ4,P3~6(1)、λ1=C1-CBB-1P1=40-(0050)=40-(0,0,25)=4010-101-1001/2130130P5~=B-1P5=10-101-1001/2001=-1-11/27λ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/21210032010020011210032010020018(2)、λ3=-40,λ4=0P5=-121/2P3=1-3094050000X1X2X3X4X5CBXB040500000X330121000X460320100X5240(2)001XB600+40000-250X36(1)010-10X4363001-150X21201001/284000-4001540X161010-10X41800-31250X21201001/2B1-1B2-1B3-110XB97500-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/211(1)、只须存贮原始数据A、B、C，每步需知B-1。(2)、每步必须计算的数据①检验数N=CBB-1N-CNCBB-1=单纯形乘子②当某个m+k﹥0时，需关键列：12Pm+k=B-1Pm+k=a1m+kamm+k…③基变量XB=B-1b=b1bm…由②、③，用最小比值法得主元arm+k④主元已知，新基B确定。返回(1)13(二)、改进单纯形法对maxZ=CXAXbX0A=(P1P2…Pn)(1)、已有初始可行基B，求B-1，XB=B-1b(2)、计算λj=Cj-CBB-1Pj若全部λj0，则计算Z0=CBB-1b,停；否则，取λm+k=maxλj，Xm+k换入。λj014(3)、计算Pm+k=B-1Pm+k，若Pm+k0，则无有限最优解,停；否则(5)、新基B。转(1)。θ=minbiAim+karm+k0=brarm+kXr换出(4)、最小θ比值法：15(5)、1)求初等变换矩阵Er(r换出变量在基中的位置)B=(P1…Pr-1PrPr+1…Pm)B=(P1…Pr-1Pm+kPr+1…Pm)BB=(B-1P1,…,B-1Pr-1,B-1Pr,B-1Pr+1,…,B-1Pm)=EB-1B=(B-1P1,…,B-1Pr-1,B-1Pm+k,B-1Pr+1,…,B-1Pm)16B-1B=1a1m+k1ar-1m+karm+kar+1m+k1amm+k1rr17Er=(B-1B)-1=a1m+karm+k-ar-1m+karm+k-1arm+kar+1m+karm+k-amm+karm+k-1111……18(B-1B)-1=B-1B=ErB-1=ErB-12)B-1=ErB-1130例：P1=主元a11=1B2-1=10-101-1001/2B2=(P3P4P2)B3=(P1P4P2)求B3-119解:Er=E1=1/100-3/110001=100-310001B3-1=E1B2-1==100-31000110-101-1001/210-1-312001/220特例：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)21单纯形表矩阵形式CBB-1bB-1bC-CBB-1A-CBB-1B-1AB-1CBB-1单纯形算子22102312002B3=(P1P4P2)=B3-1=10-1-312001/223例: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02464000-M-MX1X2X3X4X5X6X7CBXB-36MM+6M+400-M000X310023100000X41204201000-MX6141000010-MX7220100-101CBXB84-22M0M+400-M6-M00X37203100-200X46402010-406X1141000010-MX7220100-10125CBXB1720000-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-226练习：已知B=(P3P4P1P2)①验证B-1=10-2-301-4-200100001②求λ5③求P5