运筹学03单纯形法

1、第三章 单纯形法3.1 线性规划问题的标准形式3.2 线性规划问题的解3.3 单纯形法3.4 求初始基的人工变量法13.1 线性规划问题的标准形式目标函数约束条件(1) 线性规划模型一般形式2价值系数决策变量技术系数右端常数(2) 线性规划模型标准形式3简记形式(3) 线性规划模型其它形式4矩阵形式价值向量决策向量系数矩阵右端向量5价值向量决策向量右端向量向量形式列向量6对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:(4) 一般型向标准型的转化目标函数目标函数为极小化约束条件分两种情况：大于和小于决策变量可能存在小于零的情况71.极小化目标函数的问题： 设目标函

2、数为 Min f = c1x1 + c2x2 + + cnxn 则可以令z -f ，该极小化问题与下面的极大化问题有相同的最优解，即 Max z = -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f - Max z82、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s = bi (ai1 x1 + ai2 x2 + + ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x

3、1+ai2 x2+ +ain xn+s = bi 变量 s 称为松弛变量9Max Z=40X1+ 50X2 X1 +2X2 30 s.t 3X1 +2X2 60 引入松弛变量X3、 X4、X5 2X2 24 X1 , X2 0Max Z=40X1+ 50X2+0 X3 +0 X4+0 X5 X1 +2X2 + X3 30 s.t 3X1 +2X2 + X4 60 2X2 + X5 24 X1 , X5 010当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时，类似地令 s = (ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的

4、约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi变量s称为剩余变量11Max Z=2X1+ 5X2+6X3 +8X4 4X1+6X2+ X3 +2X4 12 s.t X1+ X2+7X3+5X4 14 2X2+ X3+3X4 8 X1 , , X4 0引入剩余变量：X5、X6、X7Max Z=2X1+ 5X2+6X3 +8X4 4X1+6X2+ X3 +2X4 - X5 12 s.t X1+ X2+7X3+5X4 - X6 14 2X2+ X3+3X4 - X7 8 X1 , , X7 0123. 决策变量如果某个变量的约束条件为或者可令或者代入原问题如果某个变量为自由

5、变量，则可令且13 X1+X2 5s.t -6 X1 10 X20令 X1 = X1 +6 -6+6 X1+6 10+6 0 X1 16 X1 +X2 11s.t X1 16 X1 , X2 014 3X1+2X2 8 s.t X1 -4X2 14 X20, X1 无限制 令X1= X1- X1 3 X1 -3 X1 +2X2 8 s.t X1 - X1 - 4X2 14 X1 , X1 ,X2 015例：将线性规划模型 Min Z = -X1+2X2 -3X3 X1+X2 +X3 7 s.t X1 -X2 +X3 2 X1，X20，X3无限制 化为标准型16解： 令X3 =X4 - X5 加

6、松弛变量X6加剩余变量X7 令Z= -ZMax Z= X1 -2X2 +3X4 -3X5 X1 +X2 +X4 -X5 +X6=7X1 -X2 +X4 -X5 -X7 =2X1 , X2 , X4 , , X7 0s.t173.2 线性规划问题的解(1) 解的基本概念定义 在线性规划问题中，约束方程组(2)的系数矩阵A(假定 )的任意一个 阶的非奇异(可逆)的子方阵B(即 )，称为线性规划问题的一个基阵或基。18基阵非基阵基向量非基向量基变量非基变量19令则定义 在约束方程组(2) 中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。20定义 在基本解中，若该基本解满

7、足非负约束，即 ，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。定义 在线性规划问题的一个基本可行解中，如果所有的基变量都取正值，则称它为非退化解，如果所有的基本可行解都是非退化解。称该问题为非退化的线性规划问题；若基本可行解中，有基变量为零，则称为退化解，该问题称为退化的线性规划问题。基本解中最多有m个非零分量。基本解的数目不超过 个。21非可行解解的集合：可行解基本解最优解基本可行解解空间22例 现有线性规划问题试求其基本解、基本可行解并判断是否为退化解。23解: (1)首先将原问题转化为标准型 引入松弛变量x3和x4(2) 求基本解由上式得24可能的基阵 由于所有|B|

8、0,所以有6个基阵和6个基本解。25对于基阵令则对于基阵令则为基本可行解，B13为可行基为基本可行解，B12为可行基26对于基阵令则对于基阵令则27对于基阵令则对于基阵令则为基本可行解，B24为可行基为基本可行解，B34为可行基280ABCDE1 基本解为边界约束方程的交点；2 基对应于可行解可行域极点；3 相邻基本解的脚标有一个相同。29例2 现有线性规划问题试求其基本解、基本可行解并判断是否为退化解。30解: (1)首先将原问题转化为标准型 引入松弛变量x3和x4(2) 求基本解由上式得31可能的基阵 由于所有|B| 0，所以有6个基阵和6个基本解。32对于基阵令则对于基阵令则为基本可行解

9、，B12为可行基为基本可行解，B13为可行基,为退化解33对于基阵令则对于基阵令则为基本可行解，B23为可行基,为退化解34对于基阵令则对于基阵令则为基本可行解，B24为可行基为基本可行解，B34为可行基,为退化解350ABC36(2) 解的基本性质判别可行解为基可行解的准则定理1 线性规划问题的可行解是基可行解的充要条件是它的非零变量所对应的列向量线性无关. 线性规划问题的基本定理:定理2和定理3定理2 线性规划问题有可行解,则它必有基可行解.定理3 若线性规划问题有最优解,则一定存在一个基可行解是它的最优解.37定理2 线性规划问题有可行解,则它必有基可行解.证:设 为线性规划问题的一个可

10、行解. 若 ,则它是一个基可行解,定理成立; 若 ,则令 的前k个分量为非零分量：若上述分量所对应的列向量 线性无关,则它是一个基可行解,定理成立;若 线性相关，从 出发，必可找到线性规划问题的一个基可行解。38由于 线性相关，则存在一组不全为零的数 ， 使得假定令若令(若令)(*)由(*)可知即与 相比， 的非零分量减少1个，若对应的k-1个列向量线性无关，则即为基可行解；否则继续上述步骤，直至剩下的非零变量对应的列向量线性无关。39几点结论若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点);线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点

11、);若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到;线性规划问题的基可行解(极点)的个数是有限的,不会超过 个.上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得.403.3 单纯形法例1Max Z=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0(1)单纯形法的引入41解：(1)、确定初始可行解B = ( P3 P4 P5 ) = IZ = 0 + 40X1 + 50X2X3 = 30 - ( X1 + 2X2 )X4= 60 - ( 3X1 + 2X2 )X5 = 24 - 2 X2令X

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

13、 50 X2 X3 + 2X2 = 30 - X1 X4 + 2X2 = 60 - 3X1 2X2 = 24 - X5 45 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) = 60046(2) 判断 400 X(2)不是最优解。(3) 选X1从0， X5 =0 X3= 6- X1 0 X4= 36-3X1 0 X2=12 0 X1=min( 6/1 , 36/3 , 1 ) =6X

14、1进基， X3出基。47B3 =(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) =84048(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出基。49B4=(P1 P5 P2 )Z=975- 35/2X3 - 15/2X4X1= 15 + 1/2X3 - 1/2X4X

15、5= 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) =975500(0,0)X2X1A DCB(0,12)(6,12)(15,7.5)X(4)X(1)X(2)X(3)Z=40X1+50X251单纯形法小结： 单纯形法是这样一种迭代算法如下图 当Zk中非基变量的系数的系数全为负值时，这时的基本可行解Xk即是线性规划问题的最优解，迭代结束。X1Z1保持单调增保持可行性保持可行性保持可行性保持可行性保持单调增保持单调增保持单调增X2X3.XkZ2Z3.Zk 当Zk 中非基变量的

16、系数的系数全为负值时，这时的基本可行解Xk 即是线性规划问题的最优解，迭代结束。52(2) 线性规划的典则形式标准型5354 上式称为线性规划问题对应于基B的典则形式，简称典式。约束方程组的系数矩阵中含有一个单位矩阵，并以其为基；目标函数中不含基变量，只有非基变量。检验数55(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 0 Z*=CX(0) =

17、 Z(0) Z(0) + X =CX 故X(0)为线性规划问题的最优解。56在线性规划问题的典式中，设 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+k 0 且对应的列向量 Pm+k=(a1,m+k,a2,m+k,am,m+k) 0 则线性规划问题具有无界解，即无有限最优解。无界解判别定理57(4) 基可行解改进定理在线性规划问题的典式中，

18、设 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)出发，一定能找到一个新的基可行解X(1)，使得 CX(1) CX(0) 。58(5) 单纯形表 将线性规划问题典式中各变量及系数填写在一张表格中，该表即为单纯形表。cj c1 c2 cn cn+1 cn+2 cn+m解CB基 x1 x2 xn xn+1 xn+2 xn+m000

19、0 xn+1xn+2xn+m a11 a12 a1n 1 a21 a22 a2n 1 am1 am2 amn 1b1 b2 bm12mj = cj zj 1 2 n n+1 n+2 n+m 59单纯形方法的矩阵表示BNIbCBCN00IB-1NB-1B-1b0CN -CB B-1N-CB B-1CBB-1b60对应I 式的单纯形表 I 表(初始单纯形表)对应B 式的单纯形表 B 表迭代IB-1NB-1B-1b0CN -CB B-1N-CB B-1CBB-1bBNIbCBCN00价值系数cjCBCN0解基系数基XBXNXSCBXBIB-1NB-1B-1b检验数j0CN -CB B-1N-CB B

20、-1CBB-1b当CN -CBB-1N0时，即为最优单纯形表价值系数cjCBCN0解基系数基XBXNXS0XBBNIb检验数jCBCN0061(1)、确定初始基域初始基本可行解,列出初始单纯形表(3)、若有j 0，Pj 全 0，停止， 没有有限最优解； 否则转 (4)(2)、对应于非基变量检验数j全小于零。 若是，停止，得到最优解； 若否，转(3)。(6) 单纯形法的迭代步骤62= min aim+k 0 =biaim+kbrarm+k定Xr为出基变量，arm+k为主元。由最小比值法求：Max j = m+kXm+k 进基变量j 0(4)、63转(2) a1m+k 0a2m+k 0ar,m+k

21、 1amm+k 0初等行变换Pm+k =(5)、以arm+k为中心，换基迭代从步骤(2)-(5)的每一个循环，称为一次单纯形迭代.64单纯形表计算步骤举例给定线性规划问题例1 Max z = 50X1 + 30X2 4X1+3X2 120 s.t 2X1+ X2 50 X1，X2 0Max z = 50X1 + 30X2 4X1+ 3X2 + X3 = 120s.t 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 065单纯形表计算步骤举例给定线性规划问题Max z = 50X1 + 30X2s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50

22、 X1， X2 ，X3 ，X4 0cj503000B-1bcBxBx1x2x3x40X343101200 x4210150j5030000120/450/2( )x15011/21/22501-220050-252050( )x23020011-21510-1/23/20-5-151250135066cj503000B-1bcBxBx1x2x3x40 x34310120120/40 x4(2)1015050/2j50300000 x30(1)1-2202050 x111/201/22550x2011-22050 x110-1/25/215j00-5-151350初始

23、单纯形表最优单纯形表B-1唯一最优解最优值67例2 68cj4080000 B-1bcBxBx1x2x3x4x50 x31210030150 x43201060300 x5020012412j40800000cj4080000 B-1bcBxBx1x2x3x4x50 x31010-1660 x43001-1361280 x201001/212j40000-4096069cj4080000 B-1bcBxBx1x2x3x4x540 x11010-160 x400-31218980 x201001/21224j00-40001200cj4080000 B-1bcBxBx1x2x3x4x540 x1

24、10-1/21/20150 x500-3/21/21980 x2013/4-1/4015/2j00-40001200达到最优状态时，若存在非基变量检验数为零，则为有无穷多最优解70例3 71cj2100B-1bcBxBx1x2x3x40 x31110550 x41-10100j210000 x3021-155/22x11-1010j030-201x2011/2-1/25/22x1101/21/25/2j00-3/2-1/215/2可以为零72例4 例5 无法获得初始基和初始基可行解733.4 求初始基的人工变量法求解线性规划问题的单纯形法第一步就是要找到一个初始可行基并求出初始基可行解，以它作

25、为迭代的起点。获得初始可行基及初始基可行解的途径主要有：(1) 试算法；(2) 人工变量法。在约束方程组中的每一个没有单位向量的约束方程中人为加入一个变量，使系数矩阵中凑成一个单位方阵，以形成一个初始可行基阵。74约束条件： a11x1 + a12x2 + + a1nxn +xn+1= b1 a21x1 + a22x2 + + a2nxn +xn+2 = b2 . . . am1x1 + am2x2 + + amnxn +xn+m = bm x1 ，x2 ， ，xn , xn+1 , , xn+m 0s.t人工变量人工基75等价否？76大M法两阶段法77大M法与二阶段法的一些说明由于人工变量在

26、原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。大M法实质上与原单纯形法一样，M可看成一个很大的常数人工变量被迭代出去后就不会再成为基变量当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解大M法手算很不方便，因此提出了二阶段法计算机中常用大M法二阶段法手算可能容易78二阶段法的求解过程第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基本可行解第二阶段以第一阶段得到的基本可行解为初始解，采用原单纯形法求解若第一阶段结束时，人工变量仍在基变量中，则原问题无（可行）解为了简化计算，在第一阶段重新定义

27、价值系数如下：79例6 大M法80cj3-1-100-M-M B-1bcBxBx1x2x3x4x5x6x70 x41-2110001111-Mx6-4120-11033/2-Mx7-201000111j-6M+3M-13M-10-M00-4Mcj3-1-100-M-M B-1bcBxBx1x2x3x4x5x6x70 x43-20100-110-Mx60100-11-211-1x3-20100011j1M-100-M0-3M+1-M-181cj3-1-100-M-M B-1bcBxBx1x2x3x4x5x6x70 x43001-22-5124-1x20100-11-21-1x3-20100011

28、j1000-1-M+1-M-1-2cj3-1-100-M-M B-1bcBxBx1x2x3x4x5x6x73x11001/3-2/32/3-5/34-1x20100-11-21-1x30012/3-4/34/3-7/39j000-1/3-1/3-M+1/3-M+2/32最优解人工变量被迭代出去后就不会再成为基变量82例4 83cj2400-M B-1bcBxBx1x2x3x4x5-Mx521-101840 x4-210102j2+2M4+M-M00-8Mcj2400-M B-1bcBxBx1x2x3x4x52x111/2-1/201/2480 x402-111105j0310-M-18cj2400-M B-1bcBxBx1x2x3x4x52x110-1/4-1/41/43/24x201-1/21/21/25j005/2-3/2-M-5/226未达到最优状态，但无法继续改进，即无有限最优解84例5