15单纯形法

1§1.5单纯形法1.5.1引例maxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X502解：(1)、确定初始可行解B=(P3P4P5)=IZ=0+40X1+50X2X3=30-(X1+2X2)X4=60-(3X1+2X2)X5=24-2X2令X1=X2=0X(1)=(0,0,30,60,24)TZ(1)=03(2)、判定解是否最优Z=0+40X1+50X2当X1从0↗或X2从0↗Z从0↗∴X(1)不是最优解4(3)、由一个基可行解→另一个基可行解。∵5040选X2从0↗，X1=0X3=30-2X20X230/2X4=60-2X20X260/2X5=24-2X20X224/2X2=min(30/2,60/2,24/2)=12X2进基变量，X5出基变量。5B2=(P3P4P2)Z=0+40X1+50X2④X3+2X2=30-X1①X4+2X2=60-3X1②2X2=24-X5③6③×1/2，③代入④式，①－③，②－③Z=600+40X1-25X5X3=6-X1+X5X4=36-3X1+X5X2=12-1/2X5令X1=X5=0X(2)=(0,12,6,36,0)TZ(2)=6007(2)'判断∵400∴X(2)不是。(3)'选X1从0↗，X5=0X3=6-X10X4=36-3X10X2=120X1=min(6/1,36/3,1)=6X1进基，X3出基。8B3=(P1P4P2)Z=840-40X3+15X5X1=6-X3+X5X4=18+3X3-2X5X2=12-1/2X5令X3=X5=0X(3)=(6,12,0,18,0)TZ(3)=8409(2)∵150∴X(3)不是(3)选X5从0↗，X3=0X1=6+X50X4=18-2X50X2=12-1/2X50X5=min(18/2,12/1/2)=9X5进基，X4出基。10B4=(P1P5P2)Z=975-35/2X3-15/2X4X1=15+1/2X3-1/2X4X5=9+3/2X3-1/2X4X2=15/2-3/4X3+1/4X4令X3=X4=0X(4)=(15,15/2,0,0,9)TZ(4)=975110(0,0)X2X1ADCB(0,12)(6,12)(15,7.5)12maxZ=CX当LP的数学模型为矩阵型AX=b时，X0两个重要公式：XB=B-1b-B-1NXNZ=CBB-1b+(CN-CBB-1N)XN当XN=0时，B-1b0X=Z=CBB-1b13当LP的数学模型为一般型时njjjXCZ1max),,2,1(0),,2,1(1njXmibXajnjijij两个重要公式形如：nmjjmiijijmiiinmjjijiiXaCCbCZmiXabX1111)(),,2,1(1410…0a1m+1…a1n01…0a2m+1…a2n………………………00…1amm+1…amn设A=B=(P1P2…Pm)=InmjijijimibXaX1),,1(),,2,1(1miXabXnmjjijii15nmjjmiijijimiinmjiinmjjijimiiminmjiiiiXaCCbCXCXabCXCXCZ11111111)()(miiiTmbCZbbX11)0,0,(当Xj=0(j=m+1,…,n)时,161.5.2单纯形法原理njjjXCZ1max),,2,1(0),,2,1(1njXmibXajnjijijnmjjmiijijmiiinmjjijiiXaCCbCZmiXabX1111)(),,2,1(17此时，B=(P1P2…Pm)对应的基本可行解为miiiTmbCZbbX11)0,0,(nmjjijiinmjjjmiXabXXZZ110),,2,1((1)(1)18定理1：对解X(1)，若检验数j(j=m+1,…,n)全部0，则X(1)为最优解。定理2：对X(1)，若有某个非基变量Xm+k→m+k0且相应的Pm+k=(a1m+k,…,amm+k)T0，则原问题无有限最优解。19定理2证明Xi=bi-aijxjJ=m+1n令非基变量Xm+k=(﹥0)X(2)=(b1-a1m+k,…,bm-amm+k,0,…,,…,0)TAX(2)=bX(2)0Z=Z0+m+k当时Z20例：Z=30X1+20X2-X1+3X2+X3=10-3X1+2X2+X4=15初始基B1=(P3P4)X(1)=(0,0,10,15)TZ(1)=0Z=0＋30X1+20X2X3=10-(-X1+3X2)X4=15-(-3X1+2X2)21选中X1从0↗，X2=0X3=10-(-X1)0X4=15-(-3X1)0求X1，X1→+,Z→+22换基迭代公式：(1)、决定换入变量：maxj=m+k，则Xm+k为换入变量j0(2)、决定换出变量：bi-aim+kXm+k0(i=1,2,…,m)Xm+kbiaim+k(aim+k0)23θ=minaim+k0=biaim+kbrarm+k则Xr为换出变量。24定理3：经单纯形法得到的X(2)=(b1-a1m+k,…,bm-amm+k,0,…,,…,0)T是基本可行解，且Z(2)﹥Z(1)25证明：设Xr=Xm,Xm=0,Xm+k==bmAmm+k(﹥0)X(1)中P1,…Pm线性无关，下证P1,…Pm-1,Pm+k线性无关。若否，因为P1,…Pm线性无关则Pm+k=a1m+kP1+…+amm+kPm①而Pm+k=l1P1+…+lm-1Pm-1②26①-②(a1m+k-l1)P1+…+(am-1m+k-lm-1)Pm-1+amm+kPm=0P1,…,Pm线性相关，矛盾。X(2)是基本解，且是可行解27单纯形法基本步骤(1)、定初始基，初始基本可行解(3)、若有k0，Pk全0，停，没有有限最优解；否则转(4)(2)、对应于非基变量检验数j全0。若是，停，得到最优解；若否，转(3)。28θ=minaim+k0=biaim+kbrarm+k定Xr为换出变量，arm+k为主元。由最小θ比值法求：maxj=m+k→Xm+k换入变量j0(4)、29转(2)m+k0…………a1m+k0arm+k1amm+k0初等行变换Pm+k=…………(5)、以arm+k为中心，换基迭代30证明可用归纳法（略）X(1)X(2)X(3)X’XX在边界上X在内部X＝X’+(1-)X(2)(01)X’＝X(1)+(1-)X(3)X(1)(1-)X(2)(1-)X(3)X=++(01)31证明：设X(1),…,X(k)为可行域顶点，若X*不是顶点，但maxZ=CX*X*=定理2：可行域有界，最优值必可在顶点得到µiX(i)ki=1µi=1ki=10µi1CX*=µiCX(i)ki=1µiCX(m)ki=1=CX(m)[设CX(m)＝Max(CX(i))]1ik32Z(1)=Cibii=1mZ(2)=Ci(bi-aim+k)+Cm+ki=1m=Cibi-+Cm+ki=1mCiaim+ki=1m=Cibi+[Cm+k-Ciaim+k]i=1mi=1mZ(2)-Z(1)=(Cm+k-Zm+k)=m+k﹥0331.5.3单纯形表C1C2…CmCm+1…Cm+k…CnX1X2…XmXm+1…Xm+k…XnCBXBZ000…0m+1…m+k…nC1X1b110…0a1m+1…a1m+k…a1nC2X2b201…0a2m+1…a2m+k…a2nCrXrbr00…0arm+1…arm+k…arnCmXmbm00…1amm+1…amm+k…ann……………………………………miiibCZ10miijijjaCC1344050000X1X2X3X4X5CBXB04050000θ0X33012100150X46032010300X5240(2)00112XB60040000-250X36(1)010-160X4363001-11250X21201001/284000-4001540X161010-10X41800-31250X21201001/235XB97500-35/2-15/2040X11510-1/21/200X5900-3/21/2150X215/2013/4-1/40本问题的最优解X=(15,15/2,0,0,9)TZ=97536几点说明：(1)、例maxZ=X1+2X2X14X23X1+2X28X1,X20X1+X3=4X2+X4=3X1+2X2+X5=8X1…X503712000X1X2X3X4X5CBXB0120000X34101000X430(1)0100X5812001CBXB6100-200X34101002X23010100X52(1)00-21(接下表)3812000X1X2X3X4X5CBXB80000-10X32001(2)-12X23010101X12100-21CBXB80000-10X41001/21-1/22X2201-1/201/21X141010039X(1)=(2,3)Z(1)=8X(2)=(4,2)Z(2)=8无穷多解全部解：X=α+(1-α)(0α1)243240(2)、例：求minZ=X1-X2+X3-3X5X2+X3-X4+2X5=6X1+2X2-2X4=52X2+X4+3X5+X6=8X1…X60411-110-30X1X2X3X4X5X6CBXB110-403-501X36011-1201X15120-2000X68020131CBXB-7/30-2/3014/305/31X32/30-1/31-5/30-2/31X15120-200-3X58/302/301/311/3CBXB-41/300405/31X33/21/601-20-2/3-1X25/21/210-100-1X51-2/300111/342判定定理1：基本可行解X，当全部j0时，X为最优解。判定定理2：对可行基B，当某k0，且Pk=(a1k…amk)T0，则原问题无有限最优解。换入变量：maxj=j=m+k→Xm+kj043(3)、maxZ=10X1+12X23X1+4X264X1+X223X1+2X23X1,X20441012000X1X2X3X4X5XB01012000θiX363(4)1003/2X42410102/1X53320013/2XB1810-300θiX23/23/411/4002X41/213/40-1/4102/13X50(3/2)0-1/2010XB1800-8/30-2/3X23/2011/20-1/2X41/2005/61-13/6X1010-1/302/345退化解X*=(0,3/2,0,1/2,0)TZmax=1846例：maxZ=-3/4X4+20X5-1/2X6+6X7X1+1/4X4-8X5-X6+9X7=0X2+1/2X4-12X5-1/2X6+3X7=0X3+X6=1X1…X70(P1P2P3)(P4P2P3)(P4P5P3)(P6P5P3)(P6P7P3)(P1P7P3)(P1P2P3)47(4)例：maxZ=4X1+X2-X1+X22X1-4X24X1-2X28X1,X204841000X1X2X3X4X5CBXB0410000X32-111000X44(1)-40100X581-200149160170-400X360-31104X141-40100X540(2)0-11500009/