关于线性规划问题退化解的教学思考

On the Teaching of Degenerate Solutions to Linear Programming Problems

摘要: 本文通过三个实例探讨了线性规划问题退化解的单纯形法求解。退化可能带来单纯形法求解效率下降，在高度退化情形下，进基变量或离基变量选择不当，可能陷入退化循环；退化可能导致最优解的误判或遗漏。当线性规划问题存在退化最优解时，多重最优解的判定准则失效，最优解具有唯一性，但最优基可能有多个。

Abstract: This paper illustrates how to solve degenerate solutions to linear programming problems using the simplex method with three examples. Degeneracy might have the simplex method become not very efficient. In the circumstance of highly degeneracy, wrong selection of entering basic variables or leaving basic variables could have the iterations go round in a perpetual loop. Degeneracy could cause misjudgment or omission of optimal solutions. When a linear programming problem has a degenerate optimal solution, the multiple optimality test rule becomes ineffective, there is exactly one optimal solution with multiple optimal bases.

1. 引言

在多年的《管理运筹学》教学过程中，发现学生在用单纯形法求解线性规划问题时遇到退化解无所适从，在进基变量或离基变量的选择、最优解的判定及原问题与对偶问题最优解的关系等等方面搞不明白。线性规划问题求解过程中，有时会遇到基变量取值为零的退化情况。出现退化解的原因是线性规划模型中存在多余约束，使多个基可行解和可行域同一顶点相对应 [1]。退化会降低单纯形法的求解效率，进基变量或离基变量选择不当，可能陷入迭代循环；最优解是退化解时，多重最优解判定准则可能失效；原问题是退化最优解时，对偶问题最优解可能有多个，资源影子价格表现出方向性等 [2] [3] [4]。虽然退化是一种特殊情况，但很有必要深入讨论。本文通过三个实例，着重探讨线性规划问题退化解的单纯形法求解方法。

已知线性规划问题为 $\left\{\max Z=CX|AX=b,X\ge 0\right\}$，A为 $m\times n$ 矩阵，假定 $R\left(A\right)=m$，则该线性规划

问题的基解应包含基变量m个，非基变量n − m个。基解中非零分量数量小于m (即技术矩阵A的秩)时，说明存在基变量为零，该基解是退化解 [5]。单纯形法求解极大化线性规划问题的步骤是首先找出或构造一个单位矩阵，求出初始基可行解，判断其是否最优解，如不是，则换基迭代到相邻的基可行解，并使目标函数值不断增大，直到找到最优解为止 [1]。用单纯形法求解线性规划问题过程中，当换基迭代到相邻的基可行解是退化解时，可能陷入退化循环，不能顺利找到最优解。因此，从教学角度，有必要探讨求解线性规划问题退化解需要注意哪些方面，以避免陷入退化循环或遗漏最优解。下面先从线性规划问题退化解的理论基础入手，然后通过实例探讨线性规划问题退化解的单纯形法求解。

2. 求解线性规划问题退化解的理论基础

定理：线性规划问题的基可行解对应于可行域的顶点 [5]。在讲解该定理时，需要强调两个方面，一是对于每个基可行解，存在唯一的顶点与其相对应；二是对于每个顶点，与其相对应的基可行解可能不止一个。只有在不存在退化的情况下，基可行解和可行域的顶点是一一对应的。

已知

$\{\begin{array}{l}{x}_1+x_2+x_3=4\\ x_1+x_4=4\\ x_j\ge 0,j=1,2,3,4\end{array}$,

该线性规划问题系数矩阵是 $\left(\begin{array}{llll}1\hfill & 1\hfill & 1\hfill & 0\hfill \\ 1\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\right)=\left(\begin{array}{cccc}{P}_1& P_2& P_3& P_4\end{array}\right)$，根据 $\left(\begin{array}{cc}{P}_2& P_4\end{array}\right)$ 基矩阵所计算的非退化基可行解和顶点 ${\left(0,4,0,4\right)}^{\text{T}}$ 对应，根据 $\left(\begin{array}{cc}{P}_3& P_4\end{array}\right)$ 基矩阵所计算的非退化基可行解和顶点 ${\left(0,0,4,4\right)}^{\text{T}}$ 对应。该线性规划问题的非退化基可行解和可行域的顶点是一一对应的。根据 $\left(\begin{array}{cc}{P}_1& P_2\end{array}\right)$ 、 $\left(\begin{array}{cc}{P}_1& P_3\end{array}\right)$ 和 $\left(\begin{array}{cc}{P}_1& P_4\end{array}\right)$ 三个基矩阵所计算的基可行解是退化基可行解，这三个退化基可行解都和同一可行域顶点 ${\left(4,0,0,0\right)}^{\text{T}}$ 相对应。从 $x_1$ 和 $x_2$ 两个变量平面图看，直线 $x_1+x_2=4$ 和直线 $x_1=4$ 与 $x_1$ 横轴交于可行域顶点 ${\left(4,0\right)}^{\text{T}}$。

3. 求解线性规划问题退化解的常见题型分析

用单纯形法求解线性规划问题的过程中，有以下情形之一的可能是退化：一是约束条件右边常数项b有一个或多个分量为零值，二是在选择离基变量进行最小θ比值检验时有两个相同的θ比值。退化可能发生在初始解、换基迭代及最优表的一个或多个阶段：初始解是退化解，随着换基迭代，可能不再出现退化解；初始解不是退化解，但在迭代过程中出现退化解，可能出现迭代前后的解都是退化解，甚至陷入退化引起的循环，目标函数值不会改善；初始解或迭代过程中出现退化解，但最优解不是退化解；只有最优单纯形表出现退化解，才是退化最优解。下面分别举例说明。

例1 求解下列线性规划问题 [6]：

$\begin{array}{l}\max z=10x_1-57x_2-9x_3-24x_4\\ \text{s}\text{.t}.\{\begin{array}{l}0.5x_1-5.5x_2-2.5x_3+9x_4\le 0\\ 0.5x_1-1.5x_2-0.5x_3+x_4\le 0\\ x_1\le 1\\ x_j\ge 0,j=1,2,3,4\end{array}\end{array}$

Table 1. Starting simplex tableau of Example 1

表1. 线性规划问题1的单纯形计算初始表

线性规划问题1的约束条件的右端常数项b有2个分量是零值，表1的初始解是退化解， $x_1$ 检验数是10 > 0， $x_1$ 是进基变量，确定离基变量时进行最小θ比值检验，有两个相同的θ比值0，这时选择下标大的变量 $x_6$ 为离基变量，换基迭代后结果见表2。

Table 2. Simplex tableaus of Example 1

表2. 线性规划问题1的单纯形计算表

根据表1， $x_1$ 是进基变量，确定离基变量时进行最小θ比值检验，有两个相同的θ比值0，如果按照Bland规则 [1] [5] 选择下标小的变量 $x_5$ 为离基变量，则进入了退化迭代循环(计算过程略) [6]。退化循环的主要原因是在迭代时，始终在对应于同一顶点 ${\left(0,0,0,0,0,0,\text{1}\right)}^{\text{T}}$ 的基矩阵 $\left(\begin{array}{ccc}{P}_5& P_6& P_7\end{array}\right)$ 、 $\left(\begin{array}{ccc}{P}_1& P_6& P_7\end{array}\right)$ 、 $\left(\begin{array}{ccc}{P}_1& P_2& P_7\end{array}\right)$ 、 $\left(\begin{array}{ccc}{P}_3& P_2& P_7\end{array}\right)$ 、 $\left(\begin{array}{ccc}{P}_3& P_4& P_7\end{array}\right)$ 和 $\left(\begin{array}{ccc}{P}_5& P_4& P_7\end{array}\right)$ 之间进行基变换，无法迭代到相邻顶点。本文选择下标大的变量 $x_6$ 为离基变量，从对应于顶点(0,0,0,0,0,0,1)^T的 $\left(\begin{array}{ccc}{P}_5& P_6& P_7\end{array}\right)$ 和 $\left(\begin{array}{ccc}{P}_5& P_6& P_7\end{array}\right)$ 基矩阵之间进行基变换后，迭代到相邻顶点 ${\left(\text{1},0,\text{1},0,\text{2},0,0\right)}^{\text{T}}$，最终得到非退化最优解 ${\left(\text{1},0,\text{1},0,\text{2},0,0\right)}^{\text{T}}$。因此，为避免进入退化迭代循环，求解极大化线性规划问题，选择检验数大于0的下标小的变量为进基变量，进行最小θ比值检验时，有两个或两个以上相同θ比值，选择下标大的变量为离基变量。

例2 求解下列线性规划问题 [6]：

$\begin{array}{l}\max z=x_1+x_2+4x_3\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1+4x_3\le 4\\ x_2+4x_3\le 4\\ x_j\ge 0,j=1,2,3\end{array}\end{array}$

Table 3. Complete simplex tableaus of Example 2

表3. 线性规划问题2的单纯形计算表

《管理数学(下)：运筹学》教材对问题2的求解过程是，在初始表确定 $x_3$ 为进基变量，因为其检验数是4，在正检验数中最大，确定离基变量时进行最小θ比值检验，有两个相同的θ比值1，在后续的两步换基迭代中依次出现了两个退化基可行解 [6]。本文选择检验数大于0的下标小的变量 $x_1$ 为进基变量，在后续换基迭代过程中没有出现退化基可行解，见表3。因此，在用单纯形法求解极大化线性规划问题时，尽量避免选择可能出现多个相同θ比值的变量为进基变量，只要检验数大于0的变量都可以作为进基变量，优先考虑下标小的变量作为进基变量。

例3 求解下列线性规划问题：

$\begin{array}{l}\max z=-2x_1-x_2-x_3+1.5x_4+x_5\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1+2x_3-x_4+x_5=2\\ 2x_1+2x_2-2x_3+2x_4=2\\ -3x_1-x_2-x_3+x_4=1\\ x_j\ge 0,j=1,2,3,4,5\end{array}\end{array}$

Table 4. Complete simplex tableaus of Example 3

表4. 线性规划问题3的单纯形计算表

表4是用大M法求解线性规划问题3的单纯形计算过程。首先选择检验数大于0的 $x_4$ 为进基变量，因为其检验数2.5 + 3M在正检验数中最大，且 $x_4$ 的价值系数为正，在确定离基变量时进行最小θ比值检验时有两个相同的θ比值1，在后续的两步换基迭代中依次出现了退化解，最优解 ${\left(0,0,0,\text{1},\text{3},0,0\right)}^{\text{T}}$ 是退化解，最优基 $\left(\begin{array}{ccc}{P}_5& P_1& P_4\end{array}\right)$ 、 $\left(\begin{array}{ccc}{P}_5& P_7& P_4\end{array}\right)$，分别对应于表4的第3个和第4个单纯形表。根据表4的第3个单纯形表(最优表)检验数行的相反数和互补松弛性定理，求出对偶问题的一个非退化最优解 $\left(1,0.5625,1.375,0,0.75,0.5,0,0\right)$。当原问题是退化最优解且对偶问题有非退化最优解时，此时对偶问题是多重最优解 [3] [4]。以取值为零的基变量 $x_1$ 为离基变量，用对偶单纯形法迭代，求出另一个最优解 $\left(1,1.25,0,5.5,3.5,0.5,0,0\right)$，该解是退化最优解，用两个最优解的凸组合表示其对偶问题多重最优解的一般表达式。

通过上述实例，可以得到以下启示：1) 线性规划问题的资源向量有两个或多个分量相等时，用单纯形法求解时会遇到退化解情况；2) 退化可能带来单纯形法求解效率下降，尤其在高度退化情形下，基本可行解的零值分量占很高比例，导致大量迭代总是在对应于可行域同一顶点的不同基矩阵之间进行基变换，无法迭代到相邻顶点，从而陷入退化循环 [7]；3) 在求解极大化线性规划问题时，有多个非基变量检验数为正，检验数最大的非基变量或检验数为正的任一非基变量都可以作为进基变量，应尽量避免选择可能出现多个相同θ比值的变量为进基变量，优先考虑下标小的变量为进基变量，在进行最小θ比值检验时，碰到两个及以上相同θ比值情况，选择下标大的变量为离基变量；4) 当线性规划问题存在退化最优解时，对于极大化线性规划问题的非基变量检验数严格小于零或极小化线性规划问题的非基变量严格大于零，或存在非基变量检验数为零值，我们不能据此判断是唯一最优解或多重最优解，即多重最优解的判定准则失效；5) 线性规划问题有退化最优解时，此时的最优解具备唯一性，但最优基可能有多个。

基金项目

安徽省大规模在线开放课程(MOOC)示范项目(2018mooc482)《管理运筹学》。