前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。
【例】用大M法解 下列线性规划
北京邮电大学 运筹学
【解】首先将数学模型化为标准形式
式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量，x6、，x7，目标函数中加入―MR6―MR7一项，得到人工变量单纯形法数学模型
再用前面介绍的单纯形法求解，见下表。
北京邮电大学 运筹学
Cj
3
2
－1
0
0
－M
－M
b
CB
XB
x1
x2
x3
x4
x5
x6
x7
－M 0
－M
x6
x5
x7
－4
1
2
3
－1
－2
1
2
1
－1
0
0
0
1
0
1
0
0
0
0
1
4
10
1→
λj
3－2M
2+M
－1+2M↑
－M
0
0
0
－M
0
－1
x6
x5
x3
－6
－3
2
5
3
－2
0
0
1
－1
0
0
0
1
0
0
0
1
3→
8
1
λj
5－6M
5M↑
0
－M
0
0
2
0
－1
x2
x5
x3
－6/5
3/5
－2/5
1
0
0
0
0
1
－1/5
3/5
－2/5
0
1
0
3/5
31/5→11/5
λj
5↑
0
0
0
0
2
3
－1
x2
x1
x3
0
1
0
1
0
0
0
0
1
1
1
0
2
5/3
2/3
13
31/3
19/3
λj
0
0
0
－5
－25/3
北京邮电大学 运筹学
（1）初始表中的检验数有两种算法，第一种算法是利用第一、三约束将x6、x7的表达式代入目标涵数消去x6和x7，得到用非基变量表达的目标函数，其系数就是检验数；第二种算法是利用公式计算，如
(参看第二章第一节)；
（2）M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；
（3）在第二张中x7已出基，故没有计算第七列的数值，同理，第三、四张表中x6、x7都已出基，故第六、七列没有计算；
（4）第三、四张表中的基变量没有人工变量x6、x7，因而检验数中不含M；
（5）可以看出，人工变量是帮助我们寻求原问题的可行基，第三张表就找到了原问题的一组基变量x2、x5、x3，此时人工变量就可以从模型中退出，也说明原规划有可行解，但不能肯定有最优解。
北京邮电大学 运筹学
【例】求解线性规划
【解】加入松驰变量x3、x4化为标准型
在第二个方程中加入人工变量x5，目标函数中加上M x5一项，得到
北京邮电大学 运筹学
用单纯形法计算如下表所示。
Cj
5
－8
0
0
M
b
CB
XB
x1
x2
x3
x4
x5
0
M
x3
x5
3※
1
1
－2
1
0
0
－1
0
1
6→
4
λj
5－M↑
－8+2M
0
M
0
5
M
x1
x5
1
0
1/3
－7/3
1/3
－1/3
0
－1
0
1
2
2
λj
0
－29/3+7/3M
－5/3+1/3M
M
0
北京邮电大学 运筹学
表中λj≥0，j=1，2，…，5，从而得到最优解X=（2，0，0，0，2）， Z=10+2M。但最优解中含有人工变量x5≠0说明这个解是伪最优解，是不可行的，因此原问题无可行解。
解的判断
唯一最优解的判断：最优表中所有非基变量的检验数非零,则线 规划具有唯一最优解
多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解.
无界解的判断: 某个λk>0且aik≤０（i=1，2,…,m）则线性规划具有无界解
退化基本可行解的判断:存在某个基变量为零的基本可行解。
无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri>0时，则表明原线性规划无可行解。
北京邮电大学 运筹学
计算公式
第二章 对偶线性规划
人工变量法演示
人工变量法练习
Exit
北京邮电大学 运筹学
