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