三、单纯形法的解题步骤 第一步：作单纯形表. ） （1 ）把原线性规划问题化为标准形式； ） （2 ）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； ） （3 ）目标函数非基化； ） （4 ）作初始单纯形表. 第二步：最优解的判定. (1 ) 若所有检验数都是非正数，即 ， 则此时线性规划问题已取得最优解. (2 ) 若存在某个检验数是正数，即 ，而所对应的列向量无正分量，则线性规划问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. （1 ）找到最大正检验数，设为 ，并确定 所在列的非基变量 为进基变量. （2 ）对最大正检验数 所在列实施最小比值法，确定出主元，并把主元加上小括号.主元是最大正检验数 所在列，用常数项 与进基变量 所对应的列向量中正分量的比值 最小者； （3 ）换基：用进基变量 替换出基变量 ，从而得到新的基变量.也就是主元所在列的非基变量进基，所在行的基变量出基； （4 ）利用矩阵的行初等变换，将主元变为 1 ，其所在列其他元素都变为零，从此得到新的单纯形表； （5 ）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例 3 求 . 解（1 ） 化标准型：令 ，引进松弛变量 ，其标准型为 求 （2 ） 作单纯形表：在约束方程组系数矩阵中 的系数构成单位矩阵，故取 为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6 .8 ）. 表 6.8 x 1 x2 x3 x4 x5 常数 x 3 x 4 x 5 1 0 1 0 0 1 2 0 1 0 0 （1 ） 0 0 1 5 1 0 4 S′ 1 3 0 0 0 0 x 3 x 4 x 2 1 0 1 0 0 （1 ） 0 0 1 -2 0 1 0 0 1 5 2 4 S′ 1 0 0 0 -3 -1 2 x 3 x 1 x 2 0 0 1 -1 2 1 0 0 1 -2 0 1 0 0 1 3 2 4 S′ 0 0 0 -1 -1 -1 4 （3 ） 最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值 . 原线性规划问题的最优解为： .目标函数的最优值为1 4 ，即 . 例 4 用单纯形方法解线性规划问题. 求 . 解 此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1 、2 行，3 、4列构成），取 为基变量，而目标函数没有非基化.从约束方程找出 ， , 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表 6 .9...
