三、单纯形法的解题步骤
第一步：作单纯形表•
）（1）把原线性规划问题化为标准形式；
）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；
）（3）目标函数非基化；
）（4）作初始单纯形表.
第二步：最优解的判定.
（1）若所有检验数都是非正数，即，则此时线性规划问题已取
得最优解.
（2）若存在某个检验数是正数，即：二小，而所对应的列向量无正分量，则线性规划问题无最优解.
如果以上两条都不满足，则进行下一步.
第三步：换基迭代.
（1）找到最大正检验数，设为山，并确定，1|所在列的非基变量■■:为进基变量.
（2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号
主元是最大正检验数.：所在列，用常数项与进基变量、所对应的列向
量中正分量的比值匸最小者；
%
（3）换基：用进基变量;替换出基变量从而得到新的基变量.也就是主元所在
列的非基变量进基，所在行的基变量出基；
（4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表；
（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止.
例 3 求二匚：；二 1 .
x
<5
x
解（1）化标准型：令］二_「；，引进松弛变量.■. 2.,.-^ 2 ...'.. i .，其标准型为
心王00二12巩5）
（2）作单纯形表：在约束方程组系数矩阵中； .:；的系数构成单位矩阵，故取，；=仁：1为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）表6.8
x i X2 X3 X4 X5 常数
x 3 1 0 1 0 0 5
x 4 1 2 0 1 0 10
x 5 0 (1) 0 0 1 4
S' 1 3 0 0 0 0
x 3 1 0 1 0 0 5
X 4 (1) 0 0 1 -2 2
X2 0 1 0 0 1 4
S' 1 0 0 0 -3 -12
x 3 0 0 1 -1 2 3
x 1 1 0 0 1 -2 2
x 2 0 1 0 0 1 4
S' 0 0 0 -1 -1 -14
(3) 最终结果：此时检验数均为非正
数，线性规划问题取得最优解，最优解为
标函数取得最优值
J ］_ •
性规划问题的最优解为：^ ^
，］.
函数的最优值为 14 '， 即
.
nunS = -x 1-^x 2+^x 3--x 4
1
5 2 5 3
5
可一乃+心
=2 一 3心十兀2
+才4二4 勺 > 0(/ =
1.234)
解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵( 列构成)，取】.二.为基变量，而目标函数没有非基化
•从约束方程找出
—二，「二」丨 “ ,
代入目标函数
〔82 1
经整理后，目标函数非基化了
作单纯形表，并进行换基迭代(见表
6.9)
表6.9
目前最大检验数 f 其所
目
X 1 X 2 X 3 X 4 常数
原线 X 3
1
-1
1
2
目标
X 4
-3 (1) 0 1 4
S
2
3
题.
X 3
-2
1
1
6
X 2
-3 1 0 1 4
S
11
0 -3
12
例4用单纯形方法解线性规划问
1、2 行，3、4
最大检验数二-■■:，由最小比值法知: 换，基
变量 爲出基，非基变量 .［进基•
-为主元，对主元所在列施以行初等变
在列没有正分量，所以该线性规划问题没有最优解
例5用单纯形方法解线性规划问题
求[—一二+.. + …,
-2巧+ 2乜+為=4
st<坯+也+必二6
可刃（八1234）
解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵，取二y为基变量，而目标函数没有非基化•从约束方程找出
—；］二,
代入目标函数，经整理得
IT . ' - . 1111,
目标函数已非基化.
作单纯形表，并进行换基迭代（见表6.10）.
最大检验数J ,由最小比值法知：二为主元，对主元所在列施以行初等变
换，基变量I出基，非基变量X2进基，先将主元二］化为1,然后再将主元所在列的其他元素化为零-. 八
表6.10
最优值为6，即二一一一 ._ ■ II ■-
如果我们再迭代一次，将基变量〔出基，非基变量爲进基（见表6.11）
表6.11
可得到另一个基础可行解
—:::f,
原问题的最优解为：；. - .■ ■-，最优值仍为6,说明该线性规划问题有无穷多最优解，其最优解均为亠6. 一
如何知道线性规划问题有无穷多最优解呢?
这主要反映在单纯形表中.如果非基变量所对应的检验数为0,我们可对此列继续进行换基迭代，就可以得到另一个基础可行解.以此作下去，可得到许多基础可行解，即相对应的
最优解有无穷多个.。