4运筹学之人工变量, 两阶段法.ppt

第一章线性规划与单纯型法
第5节单纯形法的进一步讨论
人工变量法
退化
检验数的几种表示形式
人工变量法
设线性规划问题的约束条件
其中没有可作为初始基的单位矩阵,则分别给每一个约束方程加入人工变量xn+1,…,xn+m,得到
以xn+1,…,xn+m为基变量,并可得到一个m×m单位矩阵。令非基变量x1,…,xn为零,便可得到一个初始基可行解X(0)=(0,0,…,0,b1,b2,…,bm)T
因为人工变量是后加入到原约束条件中的虚拟变量,要求经过基的变换将它们从基变量中逐个替换出来。
基变量中不再含有非零的人工变量,这表示原问题有解。
若在最终表中当所有cj-zj≤0,而在其中还有某个非零人工变量,这表示原问题无可行解。
以下讨论如何解含有人工变量的线性规划问题。
1大M法
在一个线性规划问题的约束条件中加进人工变量后,要求人工变量对目标函数取值不受影响;为此假定人工变量在目标函数中的系数为(-M)(M为任意大的正数),
这样目标函数要实现最大化时,必须把人工变量从基变量换出。否则目标函数不可能实现最大化。
例8 现有线性规划问题,试用大M法求解。
解在上述问题的约束条件中加入松弛变量x4,剩余变量x5,人工变量x6,x7,得到
这里M是一个任意大的正数。
因本例的目标函数是要求min,所以用所有cj-zj≥,见表1-6。
在表1-6的最终计算结果表中,表明已得到最优解是:x1=4,x2=1,x3=9,x4=x5=x6=x7=0;目标函数z=-2
2.两阶段法
以下介绍求解含有人工变量线性规划问题的两阶段法。
第一阶段:不考虑原问题是否存在基可行解;给原线性规划问题加入人工变量,并构造仅含人工变量的目标函数和要求实现最小化。
CB
XB
cj
-1
-2
0
0
-M

xj
b
x1
x2
x3
x4
x5
0
x4
3
1
0
0
1
0
∞
-M
x5
2
-1
2
-1
0
1
2/2
-Z
0
-1
-2
0
0
0
M
2
-1
2
-1
0
0