运筹学5-单纯形法

第五章 单纯形法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为可行基0ABCDE1 基本解为边界约束方程的交点；2 基对应于可行解可行域极点；3 相邻基本解的脚标有一个相同。(2) 解的基本性质判别可行解为基可行解的准则定理 1 线性规划问题的可行解是基可行解的充要条件是它的非零向量所对应的列向量线性无关 .线性规划问题的基本定理 :定理 2和定理 3定理 2 线性规划问题有可行解 ,则它必有基可行解 .定理 3 若线性规划问题有最优解 ,则一定存在一个基可行解是它的最优解 .几点结论v 若线性规划问题有可行解 ,则可行域是一个凸多边形或凸多面体 (凸集 ),且仅有有限个顶点 (极点 );v 线性规划问题的每一个基可行解都对应于可行域上的一个顶点 (极点 );v 若线性规划问题有最优解 ,则最优解必可在基可行解 (极点 )上达到 ;v 线性规划问题的基可行解 (极点 )的个数是有限的 ,不会超过 个 .上述结论说明 :线性规划的最优解可通过有限次运算在基可行解中获得 .2 单纯形法l 例 1Max Z=40X1 +50X2 X1 +2X2 +X3 =303X1 +2X2 +X4 =602X2 +X5 =24X1 X 5 0(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) =0(2)、判定解是否最优Z=0+40X1+50X2当 X1 从 0 或 X2 从 0Z 从 0 X(1) 不是最优解(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 ： 出基变量 。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 - 25X5X3 = 6 - X1 + X5 X4 = 36 - 3X1 + X5X2 = 12 -1/2X5令 X1 = X5 = 0 X(2) = ( 0, 12, 6, 36, 0 )TZ(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 ) =6X1进基， X3出基。B3 =(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) =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 ) =9X5进基， X4出基。B4=(P1 P5 P2 )Z=975- 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) =9750(0,0)X2X1A DCB(0,12)(6,12)(15,7.5)X(4)X(1)X(2) X(3)Z=40X1+50X2单纯形法小结：单纯形法是这样一种迭代算法 如下图 当 Zk中 非基变量 的系数的系数全为负值时，这时的基本可行解 Xk即是线性规划问题的最优解， 迭代结束。X1Z1保持单调增保持可行性 保持可行性 保持可行性 保持可行性保持单调增 保持单调增 保持单调增X2 X3 . XkZ2 Z3 . Zk当 Zk 中 非基变量 的系数的系数全为负值