《运筹学5单纯形法》PPT课件.ppt

第五章 单纯形法 1. 线性规划问题的解 2 单纯形法 3 求初始基的人工变量法 1.线性规划问题的解 (1) 解的基本概念 定义 在线性规划问题中，约束方程组(2)的系 数矩阵A(假定 )的任意一个 阶的非奇 异(可逆)的子方阵B(即 )，称为线性规划 问题的一个基阵或基。 基阵 非基阵 基 向 量 非 基 向 量 基变量非基变量 令 则 定义 在约束方程组(2) 中，对于 一个选定的基B，令所有的非基变 量为零得到的解，称为相应于基B 的基本解。 定义 在基本解中，若该基本解满足非负约束， 即 ，则称此基本解为基本可行解，简 称基可行解；对应的基B称为可行基。 定义 在线性规划问题的一个基本可行解中，如果 所有的基变量都取正值，则称它为非退化解，如 果所有的基本可行解都是非退化解。称该问题为 非退化的线性规划问题；若基本可行解中，有基 变量为零，则称为退化解，该问题称为退化的线 性规划问题。 基本解中最多有m个非零分量。 基本解的数目不超过 个。 非可行解非可行解 解的集合：解的集合： 可行解可行解 基本解基本解 最优解最优解 基本可行解基本可行解 解空间 例 现有线性规划问题 试求其基本解、基本可行解并判断是否为退化 解。 解: (1)首先将原问题转化为标准型 引入松弛变量x3和x4 (2) 求基本解 由上式得 可能的基阵 由于所有|B| 0, 所以有6个基阵和 6个基本解。 对于基阵令 则 对于基阵令 则 为基本可行解，B13为可行基 为基本可行解，B12为可行基 对于基阵令 则 对于基阵令 则 对于基阵令 则 对于基阵令 则 为基本可行解，B24为可行基 为基本可行解，B34为可行基 0 A B C D E 1 基本解为边界约束方程的交点； 2 基对应于可行解可行域极点； 3 相邻基本解的脚标有一个相同。 (2) 解的基本性质 判别可行解为基可行解的准则 定理1 线性规划问题的可行解是基可行解的充要 条件是它的非零向量所对应的列向量线性无关. 线性规划问题的基本定理:定理2和定理3 定理2 线性规划问题有可行解,则它必有基可行解. 定理3 若线性规划问题有最优解,则一定存在一个 基可行解是它的最优解. 几点结论 v若线性规划问题有可行解,则可行域是一个凸多边形或 凸多面体(凸集),且仅有有限个顶点(极点); v线性规划问题的每一个基可行解都对应于可行域上的 一个顶点(极点); v若线性规划问题有最优解,则最优解必可在基可行解( 极点)上达到; v线性规划问题的基可行解(极点)的个数是有限的,不会 超过 个. 上述结论说明: 线性规划的最优解可通过有限次运算在基可行解中获得. 2 单纯形法 l例1 Max Z=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0 (1)单纯形法的引入 解：(1)、确定初始可行解 B = ( P3 P4 P5 ) = I Z = 0 + 40X1 + 50X2 X3 = 30 - ( X1 + 2X2 ) X4= 60 - ( 3X1 + 2X2 ) X5 = 24 - 2 X2 令X1 = X2 =0 X(1) =(0, 0, 30, 60, 24)T Z(1) =0 (2)、判定解是否最优 Z=0+40X1+50X2 当 X1 从 0 或 X2 从 0 Z 从 0 X(1) 不是最优解 (3)、由一个基可行解另一个基可行解。 50 40 选 X2 从 0，X1 =0 X3 = 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 ) =12 X2 ：进基变量， X5 ：出基变量。 B2=( P3 P4 P2 ) Z= 0 + 40 X1 + 50 X2 X3 + 2X2 = 30 - X1 X4 + 2X2 = 60 - 3X1 2X2 = 24 - X5 1/2 ， 代入 式， ， Z = 600 + 40X1 - 25X5 X3 = 6 - X1 + X5 X4 = 36 - 3X1 + X5 X2 = 12 -1/2X5 令 X1 = X5 = 0 X(2) = ( 0, 12, 6, 36, 0 )T Z(2) = 600 (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 ) =6 X1进基， X3出基。 B3 =(P1 P4 P2 ) Z=840-40X3+15X5 X1=6 - X3 + X5 X4= 18+3X3 - 2X5 X2=12 -1/2X5 令X3 =X5 =0 X(3) =(6, 12, 0, 18, 0)T Z(3) =840 (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 ) =9 X5进基， X4出基。 B4=(P1 P5 P2 ) Z=975- 35/2X3 - 15/2X4 X1= 15 + 1/2X3 - 1/2X4 X5= 9 + 3/2X3 - 1/2X4 X2= 15/2 -3/4X3 + 1/4X4 令X3 =X4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =975 0(0,0) X2 X1 A D C B (0,12) (6,12) (15,7.5) X(4) X(1) X(2) X(3) Z=40X1+50X2 单纯形法小结： 单纯形法是这样一种迭代算法如下图 当Zk中非基变量的系数的系数全为负值时，这时的基本可 行解Xk即是线性规划问题的最优解，迭代结束。 X1 Z1 保持单调增 保持可行性保持可行性保持可行性保持可行性 保持单调增保持单调增保持单调增 X2X3.Xk Z2Z3 . Zk 当Zk 中非基变量的系数的系数全为负值时，这时的基 本可行解Xk 即是线性规划问题的最优解，迭代结束。 (2) 线性规划的典则形式 标准型 上式称为线性规划问题对应于基B的典则形式，简称 典式。 1.约束方程组的系数矩阵中含有一个单位矩阵，并以 其为基； 2.目标函数中不含基变量，只有非基变量。 检 验 数 (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) = 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+k 0 且对应的列向量 Pm+k=(a1,m+k,a2,m+k,am,m+k) 0 则线性规划问题具有无界解，即无有限最优解。 无界解判别定理 (4) 基可行解改进定理 在线性规划问题的典式中，设 X(0)=(x1,x2,xm,0,0) 为对应于基B 的一个基可行解，若满足以下条件： 1) 某个非基变量的检验数 k 0 ( m+1 k n ); 2) aik ( i = 1,2,m )不全小于或等于零，即至少有一个 aik 0 ( 1 k m ); 3) bi 0( I = 1 , 2,m ),即X(0)为非退化的基可行解。 则从X(0)出发，一定能找到一个新的基可行解X(1)，使得 CX(1) CX(0) 。 (5) 单纯形表 将线性规划问题典式中各变量及系数填写在一张 表格中，该表即为单纯形表。 cj c1 c2 cn cn+1 cn+2 cn+m 解 CB基 x1 x2 xn xn+1 xn+2 xn+m 0 0 0 0 xn+1 xn+2 xn+m a11 a12 a1n 1 a21 a22 a2n 1 am1 am2 amn 1 b1 b2 bm 1 2 m j = cj zj 1 2 n n+1 n+2 n+m 单 纯 形 方 法 的 矩 阵 表 示 BNIb CBCN00 IB-1NB-1B-1b 0CN -CB B-1N-CB B-1CBB-1b 对应I 式的单纯形表 I 表(初始单纯形表) 对应B 式的单纯形表 B 表迭代 IB-1NB-1B-1b 0CN -CB B-1N-CB B-1CBB-1b BNIb CBCN00 价值系数cjCBCN0 解 基系数基XBXNXS CBXBIB-1NB-1B-1b 检验数j0CN -CB B-1N-CB B-1CBB-1b 当CN -CBB-1N0时，即为最优单纯形表 价值系数cjCBCN0 解 基系数基XBXNXS 0XBBNIb 检验数jCBCN00 (1)、确定初始基域初始基本可行解,列出初始单 纯形表 (3)、若有j 0，Pj 全 0，停止， 没有有限最优解； 否则转 (4) (2)、对应于非基变量检验数j全小于零。 若是，停止，得到最优解； 若否，转(3)。 (6) 单纯形法的迭代步骤 = min aim+k 0 = bi aim+k br arm+k 定Xr为出基变量，arm+k为主元。 由最小比值法求： Max j = m+kXm+k 进基变量 j 0 (4)、 转(2) a1m+k 0 a2m+k 0 ar,m+k 1 amm+k 0 初等行变换 Pm+k = (5)、以arm+k为中心，换基迭代 从步骤(2)-(5)的每一个循环，称为一次单纯形迭代. 单纯形表计算步骤举例 给定线性规划问题 例1 Max z = 50X1 + 30X2 4X1+3X2 120 s.t 2X1+ X2 50 X1，X2 0 Max z = 50X1 + 30X2 4X1+ 3X2 + X3 = 120 s.t 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 0 cj503000B-1b cBxBx1x2x3x4 0x34310120120/4 0x4(2)1015050/2 j5030000 0x30(1)1-22020 50x111/201/22550 j050-251250 30x2011-220 50x110-1/25/215 j00-5-151350 初始单纯形表 最优单纯形表B-1 唯一最优解 最优值 例2 cj4080000 B-1b cBxBx1x2x3x4x5 0x3121003015 0x4320106030 0x5020012412 j40800000 cj4080000 B-1b cBxBx1x2x3x4x5 0x31010-166 0x43001-13612 80x201001/212 j40000-40960 cj4080000 B-1b cBxBx1x2x3x4x5 40x11010-16 0x400-312189 80x201001/21224 j00-40001200 cj4080000 B-1b cBxBx1x2x3x4x5 40x110-1/21/2015 0x500-3/21/219 80x2013/4-1/4015/2 j00-40001200 达到最优状态时，若存在非基变量为零，则为有无穷多最优解 例3 cj2100B-1b cBxBx1x2x3x4 0x3111055 0x41-10100 j21000 0x3021-155/2 2x11-1010 j030-20 1x2011/2-1/25/2 2x1101/21/25/2 j00-3/2-1/215/2 可以为零 例4 例5 无法获得初始基 和初始基可行解 3 求初始基的人工变量法 求解线性规划问题的单纯形法第一步就是要找到一个初 始可行基并求出初始基可行解，以它作为迭代的起点。 获得初始可行基及初始基可行解的途径主要有： (1) 试算法； (2) 人工变量法。 在约束方程组中的每一个没有单位向量的约束方程中人 为加入一个变量，使系数矩阵中凑成一个单位方阵，以 形成一个初始可行基阵。 约束条件： 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 0 s.t 人工变量 人工基 等价否？ 大M法 两阶段法 大M法与二阶段法的一些说明 n由于人工变量在原问题的解中是不能存在的，应尽快被 迭代出去，因此人工变量在目标函数中对应的价值系数 应具有惩罚性，称为罚系数。 q大M法实质上与原单纯型法一样，M可看成一个很大 的常数 q人工变量被迭代出去后就不会再成为基变量 q当检验数都满足最优条件，但基变量中仍有人工变量 ，说明原线性规划问题无可行解 q大M法手算很不方便，因此提出了二阶段法 n计算机中常用大M法 n二阶段法手算可能容易 二阶段法的求解过程 n第一阶段的任务是将人工变量尽快迭代出去，从而找到 一个没有人工变量的基本可行解 n第二阶段以第一阶段得到的基础可行解为初始解，采用 原单纯型法求解 n若第一阶段结束时，人工变量仍在基变量中，则原问题 无（可行）解 n为了简化计算，在第一阶段重新定义价值系数如下： 例6 大M法 cj3-1-100-M-M B-1b cBxBx1x2x3x4x5x6x7 0x41-2110001111 -Mx6-4120-11033/2 -Mx7-201000111 j-6M+3M-13M-10-M00-4M cj3-1-100-M-M B-1b cBxBx1x2x3x4x5x6x7 0x43-20100-110 -Mx60100-11-211 -1x3-20100011 j1M-100-M0-3M+1 -M-1 cj3-1-100-M-M B-1b cBxBx1x2x3x4x5x6x7 0x43001-22-5124 -1x20100-11-21 -1x3-20100011 j1000-1-M+1 -M-1-2 cj3-1-100-M-M B-1b cBxBx1x2x3x4x5x6x7 3x11001/3-2/32/3-5/34 -1x20100-11-21 -1x30012/3-4/34/3-7/39 j000-1/3-1/3-M+1/3 -M+2/32 最 优 解 人工变量被迭代出去后就不会再成为基变量 例4 cj2400-M B-1b cBxBx1x2x3x4x5 -Mx521-10184 0x4-210102 j2+2M4+M-M00-8M cj2400-M B-1b cBxBx1x2x3x4x5 2x111/2-1/201/248 0x402-111105 j0310-M-18 cj2400-M B-1b cBxBx1x2x3x4x5 2x110-1/4-1/41/43/2 4x201-1/21/21/25 j005/2-3/2-M-5/226 未达到最优状态，但无法继续改进，即无有限最优解 例5 cj320-MB-1b cBxBx1x2x3x4 -Mx4-1-1-111 j-M+3-M+2-M0-M 已达到最优状态，但基变量中的人工变量未退出，故无可行解 例6 (2) 两阶段法 第一阶段 cj00000-1-1 B-1b cBxBx1x2x3x4x5x6x7 0x41-2110001111 -1x6-4120-11033/2 -1x7-201000111 j-6130-100-4 cj00000-1-1 B-1b cBx