三、单纯形法的解题步骤.doc
Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date三、单纯形法的解题步骤三、单纯形法的解题步骤 三、单纯形法的解题步骤 第一步:作单纯形表.(1) (1)把原线性规划问题化为标准形式;(2) (2)找出初始可行基,通常取约束方程组系数矩阵中的单位矩阵;(3) (3)目标函数非基化;(4) (4)作初始单纯形表.第二步:最优解的判定.(1) 若所有检验数都是非正数,即 , 则此时线性规划问题已取得最优解.(2) 若存在某个检验数是正数,即 ,而所对应的列向量无正分量,则线性规划问题无最优解.如果以上两条都不满足,则进行下一步.第三步:换基迭代.(1)找到最大正检验数,设为 ,并确定 所在列的非基变量 为进基变量.(2)对最大正检验数 所在列实施最小比值法,确定出主元,并把主元加上小括号.主元是最大正检验数 所在列,用常数项 与进基变量 所对应的列向量中正分量的比值 最小者;(3)换基:用进基变量 替换出基变量 ,从而得到新的基变量.也就是主元所在列的非基变量进基,所在行的基变量出基;(4)利用矩阵的行初等变换,将主元变为1,其所在列其他元素都变为零,从此得到新的单纯形表;(5)回到第二步,继续判定最优解是否存在,然后进行新一轮换基迭代,直到问题得到解决为止.例3 求 . 解(1) 化标准型:令 ,引进松弛变量 ,其标准型为求 (2) 作单纯形表:在约束方程组系数矩阵中 的系数构成单位矩阵,故取 为基变量,目标函数已非基化了,作初始单纯形表并“换基迭代”(见表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 10 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 -12 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 -14 表 6.8 (3) 最终结果:此时检验数均为非正数,线性规划问题取得最优解,最优解为目标函数取得最优值 .原线性规划问题的最优解为: .目标函数的最优值为14,即 . 例4 用单纯形方法解线性规划问题.求 . 解 此数学模型已是标准型了,其中约束方程含有一个二阶单位矩阵(1、2行,3、4列构成),取 为基变量,而目标函数没有非基化.从约束方程找出, ,代入目标函数 ,经整理后,目标函数非基化了.作单纯形表,并进行换基迭代(见表6.9).最大检验数 ,由最小比值法知: 为主元,对主元所在列施以行初等变换,基变量 出基,非基变量 进基.表 6.9 x1 x2 x3 x4 常数 x3 x4 1 -1 1 0 -3 (1) 0 1 2 4 S 2 3 0 0 0 x3 x2 -2 0 1 1 -3 1 0 1 6 4 S 11 0 0 -3 12 目前最大检验数 ,其所在列没有正分量,所以该线性规划问题没有最优解.例5用单纯形方法解线性规划问题.求 解 此数学模型已是标准型了,其中约束方程含有一个二阶单位矩阵,取 为基变量,而目标函数没有非基化.从约束方程找出, , 代入目标函数,经整理得 ,目标函数已非基化.作单纯形表,并进行换基迭代(见表6.10).最大检验数 ,由最小比值法知: 为主元,对主元所在列施以行初等变换,基变量 出基,非基变量x2进基,先将主元 化为1,然后再将主元所在列的其他元素化为零. 表 6.10 x 1 x2 x3 x4 常数 x 3 x 4 -2 (2) 1 0 3 1 0 1 4 6 S -2 2 0 0 10 x 2 x 4 -1 1 0 4 0 - 1 2 4 S 0 0 -1 0 6 至此,检验数均为非正数,故得基础可行解 .原问题的最优解为: .最优值为6,即 .如果我们再迭代一次,将基变量 出基,非基变量 进基(见表6.11). 表 6.11 x1 x2 x3 x4 常数 x2 x4 -1 1 0 (4) 0 1 2 4 S 0 0 -1 0 6 x2 x1 0 1 1 0 3 1 S 0 0 1 0 6 可得到另一个基础可行解 , 原问题的最优解为: ,最优值仍为6,说明该线性规划问题有无穷多最优解,其最优解均为6. 如何知道线性规划问题有无穷多最优解呢? 这主要反映在单纯形表中.如果非基变量所对应的检验数为0,我们可对此列继续进行换基迭代,就可以得到另一个基础可行解.以此作下去,可得到许多基础可行解,即相对应的最优解有无穷多个. -