单纯形法中人工变量处理及与两阶段法分析.pdfVIP

第三节单纯形法的进一步讨论

以前讲过的引入人工变量的过程和目的，注意如何用人工变量和

大M对目标函数进行修改。思考以下：若目标函数是minZ的形式，究竟

是对目标函数加上M×（人工变量）还是减去M×（人工变量）呢？

二、大M法与两阶段法

1．大M法。就是将加入了人工变量后的线性规划问题用前面介绍的单纯

形法求解，整个过程和前面基本一致，就是有两点需要大家注意。

一、由于运算所得的数字中含有大M，在计算检验数时还要求出差，

所以检验数的正负判别时要谨慎。请大家判断下面数值的正负：

888101010

-M+10；（-M/10）+10；M-10；（M/10）-10

第三节单纯形法的进一步讨论

二、若已经满足了最优检验，但基变量中仍然有人工变量，也就

是说人工变量不为零，目标函数不能达到具有实际意义的最大

（最小），所以该问题无可行解，算法终止。

两阶段法（参看21~22页例题）

2．两阶段法：就是分两个阶段解含有人工变量的线性规划问题，算法

求解过程是，在第一阶段制造一个新的目标函数代替实际的目标函数，

用单纯形法求解，直到满足最优检验并且基变量中没有人工变量，再转

入第二阶段，恢复原来的目标函数，继续用单纯形法求解。

请大家思考一下，若第一阶段结束后，基变量中仍然含有人工

变量，这个规划问题的求解将会出现什么样的结果？

本节主要介绍在求解线性规划问题的解中出现的

几种情况；如何根据单纯形表判断解的类型。

用单纯形法求解线性规划过程中，最常见的是有唯一解，但也

有一些特殊情况，而且这些特殊情况都可以在单纯形表中反映出来。

希望大家结合23—26页的例题，掌握判定线性规划问题求解结

果的基本方法。

一．不可行性

在讲大M法和两阶段法时，已经给大家反复强调到，若线性

规划问题的求解已经满足最优检验，但基变量中仍然有人工变量，

也就是说人工变量不为零，这时目标函数不能达到具有实际意义

的最大（最小），所以该问题无可行解。产生这种情况的时在

建立数学模型时列出了的约束方程。

二.

在单纯形表中，可以清楚的看到，基变量的个数就等于约束条

件的个数（因为基本矩阵为m阶方阵），基变量的值就是基本可行

解，一般情况下基变量不等于零，此时基本可行解中非零变量的个

数就等于约束条件的个数；若基本可行解有变量等于零，显然非零

变量的个数就会小于约束条件数，这就是解。请大家参考

上24页的例题。

3，仔细看看线性规划问题在已经出现解的情况下，

是怎样求得最优解的。（是高等数学中的常用术语，

表示一个一般不为零的量变成零的现象，比如在求解方

程时，如果只有零解，那么就说该方程有解）。

三．多重解。

性规划问题的图解法中，已经有关于多重解的

实例（第7页例题5；参考文献第11页的图1-4）

下面结合24页表2-13看看多重解问题的最优单纯

形表有什么特征。

首先请大家仔细看看前面例题的单纯形表中，在满足

最优检验的条件下，基变量的检验数都是零，也就是说检验

数为零的变量的检验数为零，就出现检验数为零的变量的个

数大于基变量的个数这种现象，就可以将检验数为零的非基

变量作为换入变量而求出问题的另外一个最优解，由两个最

优解的线性组合就可以表示出多重解。

X=αX+(1-α)X(0≤α≤1)

12

四、无限界解

在求目标函数值最大的线性规划问题的单纯形表中，确定换

入换出变量时，用换出变量下的系数列向量中的非负分量作比较

a

（参考