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

f解（1）化标准型：令求
，引进松弛变量
，其标准型为
（2）作单纯形表：在约束方程组系数矩阵中
的系数构成单位矩阵，故取
为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表68）
表68
x1x2x3x4x5
x3
10100
常数5
x4
12010
10
x5
0（1）001
4
S′
13000
0
x3
10100
5
x4（1）0012
2
x2
01001
4
S′
10003
12
x3
00112
3
x1
10012
2
x2
01001
4
S′
00011
14
f（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为
目标函数取得最优值

原线性规划问题的最优解为：
目标函数的最优值为14，即

例4用单纯形方法解线性规划问题
求

解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4
列构成），取
为基变量，而目标函数没有非基化从约束方程找出
，

代入目标函数

经整理后，目标函数非基化了
作单纯形表，并进行换基迭代（见表69）
最大检验数
，由最小比值法知：
换，基变量出基，非基变量进基
为主元，对主元所在列施以行初等变
f表69
x1x2x3x4
x3
1110
x4
3101
S
2300
x3
2011
x2
3101
S
11003
常数
240
6412
目前最大检验数
，其所
在列没有正分量，所以该线性规划问题没有最优解例5用单纯形方法解线性规划问题求
解此数学模型已r