三、单纯形法的解题步骤

《三、单纯形法的解题步骤》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、三、单纯形法的解题步骤第一步：作单纯形表.（1）                                                                    （1）把原线性规划问题化为标准形式；（2）                                                                    （2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；（3）                                                                    （3）目标函数非基化；（4

2、）                                                                    （4）作初始单纯形表.第二步：最优解的判定.(1)若所有检验数都是非正数，即，则此时线性规划问题已取得最优解.(2)若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划问题无最优解.如果以上两条都不满足，则进行下一步.第三步：换基迭代.（1）找到最大正检验数，设为，并确定所在列的非基变量为进基变量.（2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号.主元是最大正检验数所在列，用常数项与进基变量所对应的列向量中正分量

3、的比值最小者；（3）换基：用进基变量替换出基变量，从而得到新的基变量.也就是主元所在列的非基变量进基，所在行的基变量出基；（4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表；（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止.例3求.解（1）化标准型：令，引进松弛变量，其标准型为求（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）. x1x2x3x4x5常数x3x4x510100120100（1）0015104S′130000

4、x3x4x210100（1）001-201001524S′1000-3-12x3x1x2001-121001-201001324S′000-1-1-14表6.8             （3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为目标函数取得最优值.原线性规划问题的最优解为：.目标函数的最优值为14，即.例4用单纯形方法解线性规划问题.求.解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出，,代入目标函数,经整理后，目标函数非基化了.作单纯形表，并进行换基迭代（见表6.9）.

5、最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变换，基变量出基，非基变量进基.表6.9 x1x2x3x4常数x3x41-110-3(1)0124S23000x3x2-2011-310164S1100-312 目前最大检验数，其所在列没有正分量，所以该线性规划问题没有最优解.例5用单纯形方法解线性规划问题.求解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵，取为基变量，而目标函数没有非基化.从约束方程找出，,代入目标函数，经整理得,目标函数已非基化.作单纯形表，并进行换基迭代(见表6.10).最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变换，基变量出

6、基，非基变量x2进基，先将主元化为1，然后再将主元所在列的其他元素化为零.表6.10 x1x2x3x4常数x3x4-2（2）10310146S-220010x2x4-11040-124S’00-106         至此，检验数均为非正数，故得基础可行解.原问题的最优解为：.最优值为6，即.如果我们再迭代一次，将基变量出基，非基变量进基（见表6.11）.表6.11 x1x2x3x4常数x2x4-110（4）0124S’00-106x2x1011031S’00－1　06           可得到另一个基础可行解,原问题的最优解为：，最优值仍为6，说明该线性规划问题有无穷多最优解，其

7、最优解均为6.如何知道线性规划问题有无穷多最优解呢？这主要反映在单纯形表中.如果非基变量所对应的检验数为0，我们可对此列继续进行换基迭代，就可以得到另一个基础可行解.以此作下去，可得到许多基础可行解，即相对应的最优解有无穷多个.