第一章 线性规划与单纯形法 §4单纯形法 单纯形法的基本思想是：从可行域的一个基 可行解（一个顶点）出发，判断该解是否为最 优解，如果不是最优解就转移到另一个较好的 基可行解，如果目标函数达到最优，则已得到 最优解，否则继续转移到其他较好的基可行解。 由于基可行解（顶点）数目有限，所以在一般 情况下经过有限次迭代后就一定能求出最优解
第一章 线性规划与单纯形法 §4 单纯形法 单纯形法的基本思想是：从可行域的一个基 可行解（一个顶点）出发，判断该解是否为最 优解，如果不是最优解就转移到另一个较好的 基可行解，如果目标函数达到最优，则已得到 最优解，否则继续转移到其他较好的基可行解。 由于基可行解（顶点）数目有限，所以在一般 情况下经过有限次迭代后就一定能求出最优解
4.1确定初始基可行解 对于线性规划问题 maxZ=CX (L) AX=b X≥0 我们首先介绍求初始基可行解的方法。 1.直接观察法 若给定问题标准化后（且b≥0)系数矩阵A中存在m 个线性无关的单位列向量，则以这个单位列向量构成的 单位子矩阵作为初始基B,则XBb=b≥0，其余x;=O是 基可行解
4.1确定初始基可行解 对于线性规划问题 maxZ= CX （L） AX=b X≥0 我们首先介绍求初始基可行解的方法。 1.直接观察法 若给定问题标准化后（且b≥0）系数矩阵A中存在m 个线性无关的单位列向量，则以这m个单位列向量构成的 单位子矩阵作为初始基B，则XB =B -1b =b≥0，其余xj =0是 基可行解
例5求例1问题的初始基可行解 maxZ=6x +4x 2x1+3x≤100 4x,+2x≤120 X1,X2≥0
例5 求例1问题的初始基可行解 maxZ=6x1+4x2 2x1+3x2 ≤100 4x1+2x2 ≤120 x1 ,x2 ≥0
2.大M法（人工变量法） 若给定问题标准化后(b≥0)系数矩阵中不存在个线性无关的单 位列向量，则在某些约束的左端加一个非负变x量（人工变量），使得 变化后的系数矩阵中恰有个线性无关的单位列向量，并且在日标函 数中减去这些人工变量与M的乘积M是相当大正数).对于变化后的 问题，取这个单位列向量构成的单位子矩阵为初始基，该基对应的解 一定是基可行解 例6求下面问题的初始基可行解 maxZ=3xj-X2-X3 X1-2x2+X311 -4x1+X2+2X3≥3 -2X1 +X3=1 X1,X2,X3≥0
2.大M法（人工变量法） 若给定问题标准化后(b≥0)系数矩阵中不存在m个线性无关的单 位列向量,则在某些约束的左端加一个非负变xn+i量(人工变量),使得 变化后的系数矩阵中恰有m个线性无关的单位列向量,并且在目标函 数中减去这些人工变量与M的乘积(M是相当大正数).对于变化后的 问题,取这m个单位列向量构成的单位子矩阵为初始基,该基对应的解 一定是基可行解. 例6 求下面问题的初始基可行解 maxZ=3x1 -x2 - x3 x1 -2x2+ x3≤11 -4x1+ x2 +2x3 ≥3 -2x1 + x3 = 1 x1 ,x2 , x3≥0
显然，对任意形式的线性规划问题都可以用这种增加人工变量的 方法“凑出”一个单位子矩阵作为初始可行基.按这种方法变化得 到的线性规划与原线性规划有如下关系： (1)原问题的任一基可行解都是变化后的问题的基可行解 (2)若变化后问题的最优解中不含有非零的人工变量，则该解就是原 问题的最优解 (3)若变化后问题的最优解中含有非零的人工变量，则原问题无可行 解
显然,对任意形式的线性规划问题都可以用这种增加人工变量的 方法“凑出”一个单位子矩阵作为初始可行基. 按这种方法变化得 到的线性规划与原线性规划有如下关系: ⑴原问题的任一基可行解都是变化后的问题的基可行解. ⑵若变化后问题的最优解中不含有非零的人工变量,则该解就是原 问题的最优解. ⑶若变化后问题的最优解中含有非零的人工变量,则原问题无可行 解