改进单纯形法简介课件.ppt

《改进单纯形法简介课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§1.6改进单纯形法简介(一)、单纯形法的矩阵表示标准型maxZ=CXAX=bX0已知：A、b、cA=(NB)B=E1用非基变量表示基变量Z=CBB-1b+(CN-CBB-1N)XNXB=B-1b-B-1NXNCBB-1bCN-CBB-1NOB-1bB-1NECBB-1bC-CBB-1AB-1bB-1A2C-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-1Pj3

2、例：maxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24Xj0(j=1…5)P1P2P3P4P5121003201002001A=4(1)、已知B=(P3P4P2)验证：10-101-1001/2B-1=P5~,求λ1,λA,(2)、B=(P1P4P2)验证：10-1-312001/2B-1=P5~,求λ3,λ4,P3~5(1)、λ1=C1-CBB-1P1=40-(0050)=40-(0,0,25)=4010-101-1001/2130130P5~=B-1P5

3、=10-101-1001/2001=-1-11/26λ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/21210032010020011210032010020017(2)、λ3=-40,λ4=0P5=-121/2P3=1-3084050000X1X2X3X4X5CBXB040500000X330121000X460320100X5240

4、(2)001XB600+40000-250X36(1)010-10X4363001-150X21201001/284000-4001540X161010-10X41800-31250X21201001/2B1-1B2-1B3-19XB97500-35/2-15/2040X11510-1/21/200X5900-3/21/2150X215/2013/4-1/40B4-1100010001B1=(P3P4P5)=B1-1=100010001102012002B2=(P3P4P2)=B2-1=10-101-10

5、01/210(1)、只须存贮原始数据A、B、C，每步需知B-1。(2)、每步必须计算的数据①检验数N=CBB-1N-CNCBB-1=单纯形乘子②当某个m+k﹥0时，需关键列：11Pm+k=B-1Pm+k=a1m+kamm+k…③基变量XB=B-1b=b1bm…由②、③，用最小比值法得主元arm+k④主元已知，新基B确定。返回(1)12(二)、改进单纯形法对maxZ=CXAXbX0A=(P1P2…Pn)(1)、已有初始可行基B，求B-1，XB=B-1b(2)、计算λj=Cj-CBB-1Pj若全部

6、λj0，则计算Z0=CBB-1b,停；否则，取λm+k=maxλj，Xm+k换入。λj>013(3)、计算Pm+k=B-1Pm+k，若Pm+k0，则无有限最优解,停；否则(5)、新基B。转(1)。θ=minbiAim+karm+k>0=brarm+kXr换出(4)、最小θ比值法：14(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-1P

7、m)=EB-1B=(B-1P1,…,B-1Pr-1,B-1Pm+k,B-1Pr+1,…,B-1Pm)15B-1B=1a1m+k1ar-1m+karm+kar+1m+k1amm+k1r………r16Er=(B-1B)-1=a1m+karm+k-ar-1m+karm+k-1arm+kar+1m+karm+k-amm+karm+k-1111………………17(B-1B)-1=B-1B=ErB-1=ErB-12)B-1=ErB-1130例：P1=主元a11=1B2-1=10-101-1001/2B2=(P3P4

8、P2)B3=(P1P4P2)求B3-118解:Er=E1=1/100-3/110001=100-310001B3-1=E1B2-1==100-31000110-101-1001/210-1-312001/219特例：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