运筹学—104线性规划的基本定理.pptVIP

信息系刘康泽 信息系 刘康泽 线性规划的基本定理 1、基矩阵: 若A中的m×m子矩阵B有 r (B)＝m ， 则称B是LP问题的一个基矩阵（简称为基）。 当 m＝n 时，基矩阵唯一，当 m n 时，基矩阵就可能有多个，但数目不超过 个。 线性规划的基本定理 设LP问题的标准型: 约束系数矩阵A是m×n 矩阵，m≤n ，并且 r (A)＝m，于是A中至少有一个m×m子矩阵B，使得：r (B)＝m。 一、几个概念 约束方程的系数矩阵为： 【例】设 易看出 r（A）=2，2 阶子矩阵有 = 10个，而基矩阵只有9个， 由线性代数知，基矩阵B必为非奇异矩阵并且 | B |≠0。当矩阵B的行列式等式零，即 | B |＝0 时就不是基。 2、基向量: 当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为 基向量，其余列向量称为非基向量。 3、基变量: 基向量对应的变量称为基变量，非基向量对应的变量称为非基变量。 例如：基B2的对应的基向量是A中的第一列和第四列，其余列向量是非基向量，x1 , x4是基变量，x2 , x3 , x5是非基变量。 x1 x4 5、可行解: 称满足Ax＝b，且x≥0的解为LP问题的可行解。 【注】基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。 4、基解: 对于某一确定的基B，令所有的非基变量等于零 ，求出 Ax＝b 的解，称这组解为LP问题的关于基Ｂ 的基本解 。（简称基解） 6、基可行解： 若基解同时又是可行解， 则称为是基可行解。基可行解对应的基称为可行基。 显然，只要基解中的基变量满足非负要求，那么这个基解就一定是基可行解。 因 |Ｂ１|≠０，由克菜姆法则知，x1 , x2有唯一解 则关于Ｂ1的基解为: 同理： 是关于Ｂ9 的基解。 x1 x2 上例中，对Ｂ１来说， 变量，令x3＝x4＝x5＝0，则有： x1 , x2是基变量，x3 , x4 , x5是非基 在 中x1 0，因此它不是可行解，也当然不是基可行解。 【注】可行解不一定是基解，当然不一定是基可行解。 关于Ｂ2基解为 例如： 是LP的可行解。 对Ｂ2来说，x1 , x4 为基变量，令非基变量 x2 , x3 , x5为零， 但它不是任何基的基解。 x1 x4 得到: 7、最优解 满足Ax＝b，x≥0的可行解，且使得目标函数达到最大值就是最优可行解（简称最优解）。 例如：可行解 是最优解。 【注】最优可行解不一定是基解。（因可行解不一定是基解） 9、最优基: 基最优解对应的基称为最优基，如上述B3就是最优基，最优基也是可行基。 8、基最优解 : 最优解是基解称为基最优解。 例如：可行解 是最优解。又是对应B3的基解，因此它是基最优解。 当最优解唯一时，最优解亦是基最优解，当最优解不唯一时，则最优解不一定是基本最优解。例如右图中线段 上的点都为最优 解时，Q1点及Q2点是基最优解,但线段 的内点也是最优解，而不是基最优解。 x1 x2 O 与基向量 相对应的变量为 不妨设前m个变量的系数列向量是线性无关的，则约束条件可写为 一般地: 设 或 令非基变量为0，则 利用克莱姆法则可得一个基解： 这个解的非零分量的个数不大于方程个数 m. 特别的: 若 令非基变量等于0 , 即: 得基解: 注意到: 这个特别情形中的约束系数矩阵之中对应基变量的基阵是单位矩阵 例如:问题 对应基阵 的基解是: 即基解为: x = ( 0, 0, 5, 0, 21 )T 基本最优解、最优解、基本可行解、基本解、可行解的关系如下所示： 例如,B点和D点是可行解,不是基本解;C点是基本可行解;A点是基本最优解,同时也是最优解、基本可行解、基本解和可行解。 基本最优解 基本可行解 可行解