运筹学05-单纯形法

1、1第五章第五章 单纯形法单纯形法5.1 5.1 线性规划问题的基本解线性规划问题的基本解5.2 5.2 5.3 5.3 求初始基的人工变量法求初始基的人工变量法25.1 5.1 线性规划问题的基本解线性规划问题的基本解 302.1XbAXtsCXZMax(1) 解的基本概念解的基本概念定义定义 在线性规划问题中，约束方程组在线性规划问题中，约束方程组(2)(2)的系的系数矩阵数矩阵A(A(假定假定 ) )的任意一个的任意一个 阶的非奇阶的非奇异异( (可逆可逆) )的子方阵的子方阵B(B(即即 ) )，称为线性规划，称为线性规划问题的一个问题的一个基阵基阵或或基基。mm0Bnm 3mnmmmm

2、mmmmnmmmnmmmaaaaaaaaaaaaaaaaaaA212122212222211211111211mmmmmmaaaaaaaaaB212222111211mnmmmmnmmnmmaaaaaaaaaN212221212111基阵基阵非基阵非基阵TmBxxxX21TnmmNxxxX21基基向向量量非非基基向向量量基变量基变量非基变量非基变量4NBANBXXXbAX bXXNBNBbNXBXNBNBNXbBXNBNXBbBX11NBXXXNNXNXBbBX11令令0NX则则01bBX定义定义 在约束方程组在约束方程组(2) 中，对于中，对于一个选定的基一个选定的基B，令所有的非基变，令所

3、有的非基变量为零得到的解，称为相应于基量为零得到的解，称为相应于基B的基本解。的基本解。5定义定义 在基本解中，若该基本解满足非负约束，在基本解中，若该基本解满足非负约束，即即 ，则称此基本解为，则称此基本解为基本可行解基本可行解，简称简称基可行解基可行解；对应的基；对应的基B称为称为可行基可行基。01bBXB定义定义 在线性规划问题的一个基本可行解中，如果在线性规划问题的一个基本可行解中，如果所有的基变量都取正值，则称它为所有的基变量都取正值，则称它为非退化解非退化解，如，如果所有的基本可行解都是非退化解。称该问题为果所有的基本可行解都是非退化解。称该问题为非退化的线性规划问题非退化的线性规

4、划问题；若基本可行解中，有基；若基本可行解中，有基变量为零，则称为变量为零，则称为退化解退化解，该问题称为，该问题称为退化的线退化的线性规划问题性规划问题。基本解中最多有基本解中最多有m个非零分量。个非零分量。基本解的数目不超过基本解的数目不超过 个。个。!mnmnCmn6例例 现有线性规划问题现有线性规划问题0,24261553.221212121xxxxxxtsxxZMax试求其基本解、基本可行解并判断是否为退试求其基本解、基本可行解并判断是否为退化解。化解。7解解: (1)首先将原问题转化为标准型首先将原问题转化为标准型 引入松弛变量引入松弛变量x3和和x40,2402615053.24

5、3214321432121xxxxxxxxxxxxtsxxZMax(2) 求基本解求基本解由上式得由上式得10260153A2415b8可能的基阵可能的基阵10260153A265312B061313B160314B021523B120524B100134B612121234!24! 2! 424C 由于所有由于所有|B| 0，所以有所以有6个基阵和个基阵和6个基本解。个基本解。9242615532121xxxx对于基阵对于基阵265312B令令03x04x则则TX0043415246153131xxx对于基阵对于基阵令令02x04x则则TX0304061313B为基本可行解，为基本可行解，B

6、13为可行基为可行基为基本可行解，为基本可行解，B12为可行基为可行基10246153411xxx对于基阵对于基阵令令02x03x则则TX6005242155232xxx对于基阵对于基阵令令01x04x则则TX045120160314B021523B11242155422xxx对于基阵对于基阵令令01x03x则则Tx对于基阵对于基阵令令01x02x则则TX241500120524B100134B为基本可行解，为基本可行解，B24为可行基为可行基为基本可行解，为基本可行解，B34为可行基为可行基120ABCDETX0043415TX0304TX6005TX241500T

7、X18030TX045120所以，本问所以，本问题存在题存在6个基个基本解，其中本解，其中4个为基可行个为基可行解解,无退化解无退化解.13例例2 现有线性规划问题现有线性规划问题0,05.221212121xxxxxxtsxxZMax试求其基本解、基本可行解并判断是否为退试求其基本解、基本可行解并判断是否为退化解。化解。14解解: (1)首先将原问题转化为标准型首先将原问题转化为标准型 引入松弛变量引入松弛变量x3和和x4(2) 求基本解求基本解由上式得由上式得10110111A05b0,0050.243214321432121xxxxxxxxxxxxtsxxZMax15可能的基阵可能的基阵

8、111112B011113B110114B011123B110124B100134B612121234!24! 2! 424C 由于所有由于所有|B| 0，所以有所以有6个基阵和个基阵和6个基本解。个基本解。10110111A16对于基阵对于基阵令令03x04x则则TX002525对于基阵对于基阵令令02x04x则则TX0500为基本可行解，为基本可行解，B12为可行基为可行基为基本可行解，为基本可行解，B13为可行基为可行基,为退化解为退化解111112B052121xxxx011113B05131xxx17对于基阵对于基阵令令02x03x则则TX5005对于基阵对于基阵令令01x04x则则

9、TX0500为基本可行解，为基本可行解，B23为可行基为可行基,为退化解为退化解05411xxx05232xxx110114B011123B18对于基阵对于基阵令令01x03x则则TX5050对于基阵对于基阵令令01x02x则则TX0500为基本可行解，为基本可行解，B24为可行基为可行基为基本可行解，为基本可行解，B34为可行基为可行基,为退化解为退化解05422xxx0543xx110124B100134B190ABCTX002525TX0500TX5005TX505020(2) 解的基本性质解的基本性质判别可行解为基可行解的准则判别可行解为基可行解的准则定理定理1 线性规划问题的可行解是

10、基可行解的充要线性规划问题的可行解是基可行解的充要条件是它的非零向量所对应的列向量线性无关条件是它的非零向量所对应的列向量线性无关.线性规划问题的基本定理线性规划问题的基本定理:定理定理2和定理和定理3定理定理2 线性规划问题有可行解线性规划问题有可行解,则它必有基可行解则它必有基可行解.定理定理3 若线性规划问题有最优解若线性规划问题有最优解,则一定存在一个则一定存在一个基可行解是它的最优解基可行解是它的最优解.21定理定理2 线性规划问题有可行解线性规划问题有可行解,则它必有基可行解则它必有基可行解.证证:设设 为线性规划问题的一个可行解为线性规划问题的一个可行解. 若若 ,则它是一个基可

11、行解则它是一个基可行解,定理成立定理成立; 若若 ,则令则令 的前的前k个分量为非零分量：个分量为非零分量： 0X 0X 00X 00X mkkjxxxxXjTk, 2 , 1, 0000002010若上述分量所对应的列向量若上述分量所对应的列向量 线性无关线性无关,则它是一个基可行解则它是一个基可行解,定理成立定理成立;若若 线性相关，从线性相关，从 出发，出发，必可找到线性规划问题的一个基可行解。必可找到线性规划问题的一个基可行解。kPPP21kPPP21 0X22由于由于 线性相关，则存在一组不全为零线性相关，则存在一组不全为零的数的数 ， 使得使得kPPP21k21kjjjP10假定假

12、定0i令令 0min0iiix若若0i令令 01XX(若若0i令令 01XX)(*)0021k njxxjjj, 2 , 1001由由(*)可知可知即即 01X njnjjjjjnjjjjnjjjbPPxPxPxAX11010111 0X与与 相比，相比， 的非零分量减少的非零分量减少1个，若对应的个，若对应的k-1个个列向量线性无关，则即为基可行解；否则继续上述步列向量线性无关，则即为基可行解；否则继续上述步骤，直至剩下的非零变量对应的列向量线性无关。骤，直至剩下的非零变量对应的列向量线性无关。 1X23几点结论几点结论v若线性规划问题有可行解若线性规划问题有可行解,则可行域是一个凸多边形或

13、则可行域是一个凸多边形或凸多面体凸多面体(凸集凸集),且仅有有限个顶点且仅有有限个顶点(极点极点);v线性规划问题的每一个基可行解都对应于可行域上的一线性规划问题的每一个基可行解都对应于可行域上的一个顶点个顶点(极点极点);v若线性规划问题有最优解若线性规划问题有最优解,则最优解必可在基可行解则最优解必可在基可行解(极极点点)上达到上达到;v线性规划问题的基可行解线性规划问题的基可行解(极点极点)的个数是有限的的个数是有限的,不会超不会超过过 个个.mnC上述结论说明上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得线性规划的最优解可通过有限次运算在基可行解中获得.245.2 5.

14、2 单纯形法单纯形法l基本思路和原理：基本思路和原理：l从可行域的某个顶点出发，判断是否最优。如不从可行域的某个顶点出发，判断是否最优。如不是，再找另一个使得目标函数值更优的顶点（迭是，再找另一个使得目标函数值更优的顶点（迭代）。再判断是否最优，直到找到一个顶点为其代）。再判断是否最优，直到找到一个顶点为其最优解，或判断出线性规划问题无最优解为止。最优解，或判断出线性规划问题无最优解为止。l单纯型法解题步骤：单纯型法解题步骤：l1 1、找出一个初始基本可行解、找出一个初始基本可行解l2 2、最优性检验、最优性检验l3 3、基变换、基变换(1)单纯形法的引入单纯形法的引入255.2 5.2 单纯

15、形法单纯形法l例例1 1Max Z=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0 0(1)单纯形法的引入单纯形法的引入26解：解：(1)(1)、确定初始可行解、确定初始可行解B = ( P3 P4 P5 ) = IZ = 0 + 40X1 + 50X2X3 = 30 - ( X1 + 2X2 )X4= 60 - ( 3X1 + 2X2 )X5 = 24 - 2 X2令令X1 = X2 =0X(1) =(0, 0, 30, 60, 24)TZ(1) =027(2)(2)、判定解是否最优、判定解是否最优Z=0+40X

16、1+50X2当当 X1 从从 0 或或 X2 从从 0 Z 从从 0 X X(1) (1) 不是最优解不是最优解28(3)(3)、由一个基可行解、由一个基可行解另一个基可行解。另一个基可行解。 50 40 选选 X2 从从 0，X1 =0X3 = 30 - 2X2 0 0 X2 30/2 X4 = 60 - 2X2 0 0 X2 60/2 X5 = 24 - 2 X2 0 0 X2 24/2 X2 = min ( 30/2 , 60/2 , 24/2 ) =12X2 ：进基变量进基变量， X5 ：出基变量出基变量。29B B2 2=( P3 P4 P2 )Z= 0 + 40 X1 + 50 X

17、2 X3 + 2X2 = 30 - X1 X4 + 2X2 = 60 - 3X1 2X2 = 24 - X5 30 1/2 ， 代入代入 式，式， ，Z = 600 + 40X1 - 25X5X3 = 6 - X1 + X5 X4 = 36 - 3X1 + X5 X2 = 12 -1/2X5令令 X1 = X5 = 0 X(2) = ( 0, 12, 6, 36, 0 )T Z(2) = 60031(2)(2) 判断判断 400 X(2)不是最优解不是最优解。(3) 选选X1从从0 ， X5 =0 X3= 6- X1 0 0 X4= 36-3X1 0 0 X2=12 0 0 X1=min( 6

18、/1 , 36/3 , 12 /0) =6X1进基，进基， X3出基。出基。32B3 =(P1 P4 P2 )Z=840-40X3+15X5X1=6 - X3 + X5 X4= 18+3X3 - 2X5X2=12 -1/2X5令令X3 =X5 =0 X(3) =(6, 12, 0, 18, 0)TZ(3) =84033(2) 150 X(3)不是不是(3) 选选X5从从0 ， X3 =0 X1=6 +X5 0 X4= 18 -2X5 0 X2=12-1/2 X5 0 X5=min( 18/2 , 12/1/2 ) =9X5进基，进基， X4出基。出基。34B4=(P1 P5 P2 )Z=975

19、- 35/2X3 - 15/2X4X1= 15 + 1/2X3 - 1/2X4X5= 9 + 3/2X3 - 1/2X4X2= 15/2 -3/4X3 + 1/4X4令令X3 =X4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =975350(0,0)X X2 2X X1 1A A D DC CB B(0,12)(6,12)(15,7.5)X(3)X(4)X(1)X(2)X(3)Z=40X1+50X236初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解? ?结束结束沿边界找新沿边界找新的基本可行解的基本可行解N NY Y37(2) 线性规划

20、的典则形式线性规划的典则形式0XbAXt . sCXZMaxNBA NBXXXNBCCC 标准型标准型380X, 0XbBNXBXt . sXNBCCbBCZMaxNB1N1BN1BN1B上式称为线性规划问题对应于基上式称为线性规划问题对应于基B的的典则形式典则形式，简称简称典式典式。约束方程组的系数矩阵中含有一个单位矩约束方程组的系数矩阵中含有一个单位矩阵，并以其为基；阵，并以其为基；1.目标函数中不含基变量，只有非基变量。目标函数中不含基变量，只有非基变量。 NBCC0NBCCBBCCNBBCCCABCC1BN1BN1BB1BNB1B检检验验数数39(3) 最优性判别定理最优性判别定理在线

21、性规划问题的典式中，设在线性规划问题的典式中，设 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 0 Z*=CX(0) = Z(0) Z(0) + X =CX 故故X(0)为线性规划问题的最优解为线性规划问题的最优解。40在线性规划问题的典式中，设在线性规划问题的典式中，设 X(0)=(

22、x1,x2,xm,0,0)为对应于基为对应于基B 的一个基可行解，若有的一个基可行解，若有 j 0 ( j = m+1 , m+2 , , n ) 且且 j+k = 0 则则线性规划问题有无穷多个最优解。线性规划问题有无穷多个最优解。无穷多最优解判别定理无穷多最优解判别定理在线性规划问题的典式中，设在线性规划问题的典式中，设X(0) 为对应于基为对应于基B 的一个的一个基可行解，若某一非基变量基可行解，若某一非基变量xj+k的检验数的检验数 j+k 0 且对应的列向量且对应的列向量 Pm+k=(a1,m+k,a2,m+k,am,m+k) 0 则则线性规划问题具有无界解。线性规划问题具有无界解。

23、无界解判别定理无界解判别定理41(4) 基可行解改进定理基可行解改进定理在线性规划问题的典式中，设在线性规划问题的典式中，设 X(0)=(x1,x2,xm,0,0)为对应于基为对应于基B 的一个基可行解，若满足以下条件：的一个基可行解，若满足以下条件： 某个非基变量的检验数某个非基变量的检验数 k 0 ( m+1 k n ); aik ( i = 1,2,m )不全小于或等于零，即至少有一个不全小于或等于零，即至少有一个 aik 0 ( 1 k m ); bi 0( I = 1 , 2,m ),即即X(0)为非退化的基可行解。为非退化的基可行解。则从则从X(0)出发，一定能找到一个新的基可行解

24、出发，一定能找到一个新的基可行解X(1)，使得，使得 CX(1) CX(0) 。42(5) 单纯形表单纯形表00,XXbBNXBXs.tXNBCCbBCZMaxNB1N1BN1BN1B将线性规划问题典式中的数据按一定规则列入表将线性规划问题典式中的数据按一定规则列入表中，该表即为中，该表即为单纯形表单纯形表。CCBCNCBXBbXBXNCBXBB-1bIB-1NZCB B-1b0CN-CB B-1N43C2100CBXBbX1X2X3X40X31535100X4246201Z02100C2100CBXBbX1X2X3X40X33041-1/22X1411/301/6Z801/30-1/344(

25、1)、确定初始基域初始基本可行解、确定初始基域初始基本可行解,列出初始单列出初始单纯形表纯形表(3)、若有、若有 j 0，Pj 全全 0，停止，停止， 没有有限最优解；没有有限最优解； 否则转否则转 (4)(2)、对应于非基变量检验数、对应于非基变量检验数 j全小于全小于零零。 若是，停止，得到最优解；若是，停止，得到最优解； 若否，转若否，转(3)。(6) (6) 单纯形单纯形法的迭代步骤单纯形单纯形法的迭代步骤45= = min aim+k 0 =0 =biaim+kbrarm+k定定Xr为出基变量，为出基变量，arm+k为为主元。主元。由最小由最小比值法求：比值法求：Max j = m+

26、kXm+k 进基变量进基变量 j 0 0(4)、46转转(2) (2) a1m+k 0a2m+k 0ar,m+k 1amm+k 0初等行变换初等行变换Pm+k =(5)、以、以arm+k为中心，换基迭代为中心，换基迭代从步骤从步骤(2)-(5)(2)-(5)的每一个循环，称为一次的每一个循环，称为一次单纯形迭代单纯形迭代。47例例1、Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 0s.t X1+2X2 +X3 = 303X1+2X2 +X4 =60 2X2 +X5 = 24 X1 X5 0 0s.t48C4050000CBXBBX1

27、X2X3X4X50X33012100150X46032010300X5240200112Z04050000 CBXBBX1X2X3X4X50X33012100 0X46032010 50X22402001 Z CBXBBX1X2X3X4X50X361010-160X4363001-11250X21201001/2 Z60040000-25 49C4050000CBXBBX1X2X3X4X540X161010-10X41800-312950X21201001/224Z84000-40015 CBXBBX1X2X3X4X540X11510-1/21/20 0X5900-3/21/21 50X215

28、/2975013/4-1/40 Z 0 0-35/2-15/2 0 50例例1、Max Z=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 0s.t X1+2X2 +X3 = 303X1+2X2 +X4 =60 2X2 +X5 = 24 X1 X5 0 0s.t51C4080000CBXBBX1X2X3X4X50X33012100150X46032010300X5240200112Z04080000 CBXBBX1X2X3X4X50X361010-1 60X4363001-112 80X21201001/2 Z 960 40 0 0 0 -40

29、CBXBBX1X2X3X4X540X161010-10X41800-312980X21201001/2 24Z120000-4000 52C4050000CBXBBX1X2X3X4X540X115101/2-1/20 0X59003/2-1/20 80X215/2120001-3/41/41 Z 0 0 -200 0 535.3 5.3 求初始基的人工变量法求初始基的人工变量法求解线性规划问题的单纯形法第一步就是要找求解线性规划问题的单纯形法第一步就是要找到一个初始可行基并求出初始基可行解，以它到一个初始可行基并求出初始基可行解，以它作为迭代的起点。作为迭代的起点。获得初始可行基及初始基可行解

30、的途径主要有：获得初始可行基及初始基可行解的途径主要有：(1) 试算法；试算法；(2) 人工变量法。人工变量法。在约束方程组中的每一个没有单位向量的约束在约束方程组中的每一个没有单位向量的约束方程中人为加入一个变量，使系数矩阵中凑成方程中人为加入一个变量，使系数矩阵中凑成一个单位方阵，以形成一个初始可行基阵。一个单位方阵，以形成一个初始可行基阵。54约束条件约束条件： a11x1 + a12x2 + + a1nxn +xn+1= b1 a21x1 + a22x2 + + a2nxn +xn+2 = b2 . . . am1x1 + am2x2 + + amnxn +xn+m = bm x1 ，

31、x2 ， ，xn , xn+1 , , xn+m 0s.t0,.MMXXbIXAXts人工变量人工变量人工基人工基550.XbAXtsCXZMax0,.MMXXbIXAXtsCXZMax等价否？等价否？0.XbAXtsCXZMax0,.MMXXbIXAXtsCXZMax0MX560.XbAXtsCXZMax0,.MMMXXbIXAXtsMXCXZMax0.XbAXtsCXZMax0,.MMMXXbIXAXtsIXZMax大大M法法两阶段法两阶段法57(1) 大大M法法例例3、 Max Z=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0s.t2X1+X2-X3 =8-2X

32、1+X2 +X4= 2X1 X4 0s.tMax Z=2X1+ 4X2 MX52X1+X2-X3 +X5 =8-2X1+X2 +X4= 2X1 X5 0s.t58C2400-MCBXBbX1X2X3X4X5-MX5821-10140X42-21010 Z-8M2+2M4+M-M00 2X1411/2-1/201/280X41002-1115Z80310-1 2X1610-1-11 4X2501-1/21/21/2 Z320040-4 59例例4、 Max Z=3X1+2X2 -X1 -X2 1X1 , X2 0s.t-X1 -X2 X3 =1X1 , X2 0s.tMax Z=3X1+2X2 MX4-X1 -X2 X3 +X4 =1X1 X4 0s.tC320-MCBXBbX1X2X3X4-MX41-1-1-11 Z-M3+M2+MM0 60C23-5-M0-MCBXBbX1X2X3X4X5X6-MX471111007-MX6102-510-115Z-17M2+3M3-4M2M-50-M0 -MX4207