1、第五章 单纯形法1. 线性规划问题的解2 单纯形法3 求初始基的人工变量法1.线性规划问题的解(1) 解的基本概念定义 在线性规划问题中，约束方程组 (2)的系数矩阵 A(假定 )的任意一个 阶的非奇异 (可逆 )的子方阵 B(即 )，称为线性规划问题的一个 基阵 或 基 。基阵 非基阵基向量非基向量基变量 非基变量令则定义 在约束方程组 (2) 中，对于一个选定的基 B，令所有的非基变量为零得到的解，称为相应于基 B的基本解。定义 在基本解中，若该基本解满足非负约束，即 ，则称此基本解为 基本可行解 ，简称 基可行解 ；对应的基 B称为 可行基 。定义 在线性规划问题的一个基本可行解中，如果
2、所有的基变量都取正值，则称它为 非退化解 ，如果所有的基本可行解都是非退化解。称该问题为非退化的线性规划问题 ；若基本可行解中，有基变量为零，则称为 退化解 ，该问题称为 退化的线性规划问题 。基本解中最多有 m个非零分量。基本解的数目不超过 个。非可行解非可行解解的集合：解的集合：可行解可行解 基本解基本解最优解最优解基本可行解基本可行解解空间(2) 解的基本性质判别可行解为基可行解的准则定理 1 线性规划问题的可行解是基可行解的充要条件是它的非零向量所对应的列向量线性无关 .线性规划问题的基本定理 :定理 2和定理 3定理 2 线性规划问题有可行解 ,则它必有基可行解 .定理 3 若线性规
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
