运筹学5-单纯形法

第五章单纯形法1.线性规划问题的解2单纯形法3求初始基的人工变量法1.线性规划问题的解302.1XbAXtsCXZMax(1)解的基本概念定义在线性规划问题中，约束方程组(2)的系数矩阵A(假定)的任意一个阶的非奇异(可逆)的子方阵B(即)，称为线性规划问题的一个基阵或基。mm0Bnm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非可行解解的集合：可行解基本解最优解基本可行解解空间(2)解的基本性质判别可行解为基可行解的准则定理1线性规划问题的可行解是基可行解的充要条件是它的非零向量所对应的列向量线性无关.线性规划问题的基本定理:定理2和定理3定理2线性规划问题有可行解,则它必有基可行解.定理3若线性规划问题有最优解,则一定存在一个基可行解是它的最优解.几点结论若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点);线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点);若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到;线性规划问题的基可行解(极点)的个数是有限的,不会超过个.mnC上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得.2单纯形法例1MaxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50(1)单纯形法的引入解：(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)=0(2)、判定解是否最优Z=0+40X1+50X2当X1从0↗或X2从0↗Z从0↗∴X(1)不是最优解(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：出基变量。B2=(P3P4P2)Z=0+40X1+50X2④X3+2X2=30-X1①X4+2X2=60-3X1②2X2=24-X5③③×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)=600(2)'判断∵400∴X(2)不是最优解。(3)'选X1从0↗，X5=0X3=6-X10X4=36-3X10X2=120X1=min(6/1,36/3,&)=6X1进基，X3出基。B3=(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)=840(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出基。B4=(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)=9750(0,0)X2X1ADCB(0,12)(6,12)(15,7.5)X(4)X(1)X(2)X(3)Z=40X1+50X2单纯形法小结：单纯形法是这样一种迭代算法——如下图…当Zk中非基变量的系数的系数全为负值时，这时的基本可行解Xk即是线性规划问题的最优解，迭代结束。X1Z1保持单调增保持可行性保持可行性保持可行性保持可行性保持单调增保持单调增保持单调增X2X3...XkZ2Z3...Zk当Zk中非基变量的系数全为负值时，这时的基本可行解Xk即是线性规划问题的最优解，迭代结束。(2)线性规划的典则形式0XbAXt.sCXZMaxNBANBXXXNBCCC标准型bAXbXXNBNBbNXBXNBN11BNXBbBXN1BN1-BNNN1-B1-BNNN11BNNBBNBNBXNBCCbBCXCNXBCbBCXCNXBbBCXCXCXXCCCXZ(3)最优性判别定理在线性规划问题的典式中，设X(0)=(x1,x2,…,xm,0,…,0)为对应于基B的一个基可行解，若有j0(j=m+1,m+2,…,n)则X(0)是线性规划问题的最优解，基B为最优基。证：设X为线性规划问题的一个可行解，必有X0，当j0，则X0Z*=CX(0)=Z(0)Z(0)+X=CX故X(0)为线性规划问题的最优解。在线性规划问题的典式中，设X(0)=(x1,x2,…,xm,0,…,0)为对应于基B的一个基可行解，若有j0(j=m+1,m+2,…,n)且j+k=0则线性规划问题有无穷多个最优解。无穷多最优解判别定理在线性规划问题的典式中，设X(0)为对应于基B的一个基可行解，若某一非基变量xj+k的检验数j+k0且对应的列向量P’m+k=(a1,m+k,a2,m+k,…,am,m+k)0则线性规划问题具有无界解，即无有限最优解。无界解判别定理(4)基可行解改进定理在线性规划问题的典式中，设X(0)=(x1,x2,…,xm,0,…,0)为对应于基B的一个基可行解，若满足以下条件：1)某个非基变量的检验数k0(m+1kn);2)aik(i=1,2,…,m)不全小于或等于零，即至少有一个aik0(1km);3)bi’0(I=1,2,…,m),即X(0)为非退化的基可行解。则从X(0)出发，一定能找到一个新的基可行解X(1)，使得CX(1)CX(0)。(5)单纯形表将线性规划问题典式中各变量及系数填写在一张表格中，该表即为单纯形表。cjc1c2…cn00…0SCB基x1x2…xnxn+1xn+2…xn+m0000xn+1xn+2…xn+ma11a12…a1n1a21a22…a2n1……………am1am2…amn1b1b2…bm12…mzjj=cj–zj00…000…012…nn+1n+2…n+m0S0XbAXt.sCXzMax0X,X,XbIXNXBXt.s0XXCXCzMaxsNBsNBsNNBBbIXNXBX00XXCXCz-sNBsNNBBbBBNBI000CC1bINB000CC11-1-1-NBNBbBBNBI0bBC-BC-NBCC011-1-1--1B-1B-1BN单纯形方法的矩阵表示0X,0XbBNXBXt.sXNBCCbBCZMaxNB1N1BN1BN1BBNIbCBCN00IB-1NB-1B-1b0CN-CBB-1N-CBB-1CBB-1b对应I式的单纯形表——I表(初始单纯形表)对应B式的单纯形表——B表迭代IB-1NB-1B-1b0CN-CBB-1N-CBB-1CBB-1bBNIbCBCN00价值系数cjCBCN0Sθ基系数基XBXNXSCBXBIB-1NB-1B-1bzj检验数σjCB0CBB-1NCN-CBB-1NCBB-1-CBB-1S-CBB-1b当CN-CBB-1N≤0时，即为最优单纯形表价值系数cjCBCN0Sθ基系数基XBXNXS0XsBNIbzj检验数σj0CB0CN000S(1)、确定初始基域初始基本可行解,列出初始单纯形表(3)、若有j0，Pj全0，停止，没有有限最优解；否则转(4)(2)、对应于非基变量检验数j全小于零。若是，停止，得到最优解；若否，转(3)。(6)单纯形法的迭代步骤θ=minaim+k0=biaim+kbrarm+k定Xr为出基变量，arm+k为主元。由最小θ比值法求：Maxj=m+k→Xm+k进基变量j0(4)、转(2)a1m+k0a2m+k0ar,m+k1amm+k0初等行变换Pm+k=…………(5)、以arm+k为中心，换基迭代从步骤(2)-(5)的每一个循环，称为一次单纯形迭代.单纯形表计算步骤举例给定线性规划问题例1Maxz=50X1+30X24X1+3X2≤120s.t2X1+X2≤50X1，X2≥0Maxz=50X1+30X24X1+3X2+X3=120s.t2X1+X2+X4=50X1，X2，X3，X4≥0cj503000SθcBxBx1x2x3x40x34310120120/40x4(2)1015050/2zjσj05003000000S0x30(1)1-2202050x111/201/22550zjσj002550025-251250S-125030x2011-22050x110-1/25/215zjσj5003005-515-151350S-1350初始基最优单纯形表B-1初始基可行解最优值初始单纯形表唯一最优解例20x,x242x602x3x302xxs.t80x40xzMax2122121210x,,x24x2x60x2x3x30x2xxs.t80x40xzMax515242132121cj4080000SθcBxBx1x2x3x4x50x31210030150x43201060300x5020012412zjσj0400800000000Scj4080000SθcBxBx1x2x3x4x50x31010-1660x43001-1361280x201001/212Zjσj040800000040-40960S-960cj4080000SθcBxBx1x2x3x4x540x11010-160x400-31218980x201001/21224zjσj40080040-4000001200S-1200cj4080000SθcBxBx1x2x3x4x540x110-1/21/20150x500-3/21/21980x2013/4-1/4015/2zjσj40080040-400000SS-1200达到最优状态时，若存在非基变量为零，则为有无穷多最优解