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