下载掌阅APP，畅读海量书库
立即打开
在前文中提到用人工变量法可以得到初始基可行解。但加入人工变量的数学模型与未加人工变量的数学模型一般是不等价的。
设线性规划问题的约束条件是：
分别给每一个约束方程加入人工变量 x n ＋1 ，…， x n ＋ m ，得到：
以 x n ＋1 ，…， x n ＋ m 为基变量，并可得到一个 m × m 单位矩阵。令非基变量 x 1 ，…， x n 为零，便可得到一个初始基可行解：
因为人工变量是最后加入原约束条件中的虚拟变量，要求将它们从基变量中逐个替换出来。若经过基的变换，基变量中含有某个非零人工变量，这表示有可行解。若在最终表中当所有 c j － z j ≤0，而在其中还有某个非零人工变量，这表示无可行解。为了消除人工变量常用的方法有大M法和两阶段法。
在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为此假定人工变量在目标函数（max z ）中的系数为（－ M ）（ M 为任意大的正数），若目标函数为min z ，则人工变量在目标函数中系数为 M ，这样目标函数要实现最大化（最小化）时，应把人工变量从基变量换出，或者人工变量在基变量中，但取值为0。否则目标函数不可能实现最大化（最小化）。
例2.5 现有线性规划问题：
试用大M法求解。
解：在上述问题的约束条件中加入松弛变量、剩余变量和人工变量，得到：
这里M是一个任意大的正数。
用单纯形法进行计算（见表2.7）。因本例是求min，所以用所有 c j － z j ≥0来判别目标函数是否实现了最小化。表中的最终表表明得到最优解是：
目标函数： z ＝－2
由于人工变量 x 6 ＝ x 7 ＝0，则原问题最优解为 X ＊ ＝（4，1，9） T ， Z ＊ ＝－2。
表2.7
用电子计算机求解含人工变量的线性规划问题时，只能用很大的数代替 M ，这就可能造成计算上的错误，故介绍两阶段法求线性规划问题。
第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化，如：
然后用单纯形法求解上述模型，若得到 ω ＝0，这说明原问题存在基可行解，可以进行第二阶段计算；否则原问题不可行解，应停止计算。
第二阶段：将第一阶段计算得到的最终表，除去人工变量。将目标函数换回原问题的目标函数，作为第二阶段的计算方法及步骤，与单纯形法相同。
例2.6 线性规划：
试用两阶段法求解。
解：先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：
这里 x 6 ， x 7 是人工变量。用单纯形法求解（见表 2.8）。第一阶段求得的结果是 w ＝0。得到最优解是：
因人工变量 x 6 ＝ x 7 ＝0，所以（0，1，1，12，0） T 是这线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消填入原问题的目标函数的系数，进行阶段计算（见表2.9）。
表2.8
表2.9
从表中得到最优解为 x 1 ＝4， x 2 ＝1， x 3 ＝9，目标函数值 z ＝－2。
单纯形法计算中用 θ 规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。这时换出变量 x l ＝0，迭代后目标函数值不变，这时不同基表示为同一顶点。有人构造了一个特例，当出现退化时，进行多次迭代，而基从 B 1 ， B 2 ，…又返回到 B 1 ，即出现计算过程的循环，便永远达不到最优解。
尽管计算过程的循环现象极少出现，但还是有可能的。为解决这个问题，先后有人提出了“摄动法”“辞典序”。1974年由勃兰特（Bland）提出一种简便的规则，简称勃兰特规则。
（1）选取 σ j ＞0中下标最小的非基变量 x k 为换入变量，即：
（2）当按 θ 规则计算存在两个以上最小比值时，选取下标最小的基变量为换出变量。
按勃兰特规则计算时，一定能避免出现循环。