敏感性分析中退化情况与多重最优解的判别

The Discrimination of Degradation and Multiple Optimal Solutions in Sensitivity Analysis

摘要: 计算机工具求解线性规划模型的结果对应实际问题中多种解决方案，其中退化解和多重最优解对决策者进行合理决策是至关重要的。但在计算机工具所得敏感性报告中，无法直观判断线性规划模型是否存在退化解和多重最优解的情况。针对该问题，以Excel敏感性报告为例，结合单纯形法定理和对偶理论，能够得出判别敏感性分析中线性规划问题退化情况与多重最优解的一般方法，即定义法、个数相等法判定所得解是否存在退化情况，能够解决多重最优解判别的对偶关系法和递减成本法，以及判别退化解与多重最优解均适用的方法：综合法–退化解与多重解的关系法。

Abstract: The results of solving the linear programming model by computer tools correspond to many solutions in practical problems. Among them, the solution and multiple optimal solutions are crucial for decision makers to make reasonable decisions. However, in the sensitivity report obtained by computer tools, it is impossible to directly judge whether the linear programming model has degeneracy and multiple optimal solutions. Aiming at this problem, taking Excel sensitivity report as an example, combined with the simple method theorem and duality theory, a general method for judging the degradation of linear programming problems and multiple optimal solutions in sensitivity analysis can be obtained, that is, the definition method and the equal number method are used to determine whether the obtained solution has degradation. The dual relationship method and the decreasing cost method that can solve the discrimination of multiple optimal solutions, as well as the method that discriminates the regression solution and the multiple optimal solutions are applicable: The comprehensive method-the relationship method of regression solution and multiple solutions.

1. 引言

在现实生活中，数学规划能适当安排有限的资源条件以取得最大化的利益 [1] ；线性规划在实际生活中占有重要的地位，可以解决经济活动、生产管理、军事和国防等众多领域的优化问题。对于普通的线性规划问题，运用基本解法可以快速求出结果及解的判别；但是当决策量较多时，利用计算机工具求解不失为明智之举，不仅可以将人力解放出来，而且可以提高结果的准确性 [2] [3] 。但本文在研究过程中发现，除了无界解与无可行解以外，通用的计算机工具求出的敏感性结果报告无法直观判别是否存在退化解、多重最优解。退化解与多重最优解体现了决策者在资源供求方面的多种均衡解 [4] 。当线性规划问题为退化问题时，将对资源的影子价格产生影响；在实际工作中，将不利于决策者充分利用影子价格所提供的信息做出合理的决策。在生产管理中，多重最优解对应多种且最终效益一样的生产管理方式，但不同的生产方式具有不同的可行性，这对管理者来说至关重要。充分利用敏感性分析报告，读懂报告中蕴含的信息，是判断退化解与多重最优解的关键点 [5] 。一般文献中几乎没有讨论在计算机工具的敏感性分析中这两种情况的判断方法 [6] 。但退化解与多重最优解的情况不容忽视，解决这两个问题具有一定的现实意义。

因此，本文针对敏感性分析中出现退化解、多重最优解的情况进行研究，借鉴以往学者的研究经验以及单纯形法定理和对偶理论，以Excel敏感性分析报告为例，总结出多种判定线性规划问题是否存在退化情况及多重最优解的通用方法，并从实际案例上证明这些方法的可行性和通用性。

2. 问题提出

下面通过引入具体实例探讨在各类运筹学软件中退化解与多重最优解的通用判别方法及应用。

2.1. 生产计划问题

已知粤通汽车制造厂需用三种材料A、B、C共同生产三款不同的车型迷你车、跑车和家用轿车。已知单位车型所需材料量、材料总量及汽车单位利润如表1所示。那么经营者该如何安排生产计划，才能使得工厂的利润收入最大化？

Table 1. Production data table of Yuetong automobile factory

表1. 粤通汽车制造厂生产数据表

2.2. 建立模型

由问题提出及表1可知粤通汽车制造厂安排生产计划即为线性规划问题，下面根据求解线性规划问题的步骤一一展开。设 $x_i$ 表示迷你车、跑车和家庭轿车三款车型的生产量， $i=1,2,3$ ， $x_i$ 为决策变量，目标要求是粤通汽车制造厂生产利润最大化，根据该制造厂生产需求的数据，由此确立约束条件。那么粤通汽车制造厂的生产问题数学模型为：

$\begin{array}{l}\max Z=30x_1+50x_2+30x_3\\ \{\begin{array}{l}17x_1+12x_2+12x_3\le 10000\left(\text{A}材料使用量约束\right)\\ 23x_2+8x_3\le 12000\left(\text{B}材料使用量约束\right)\\ 30x_1+45x_2+20x_3\le 20000\left(\text{C}材料使用量约束\right)\\ x_i\ge 0,i=1,2,3\left(非负约束\right)\end{array}\end{array}$

为了方便上述模型求解，将通过引入松弛变量x₄，x₅，x₆化为标准型，标准LP形式下的线性规划模型为：

$\begin{array}{l}\max Z=30x_1+50x_2+30x_3+x_4+x_5+x_6\\ \{\begin{array}{l}17x_1+12x_2+12x_3+x_4=10000\\ 23x_2+8x_3+x_5=12000\\ 30x_1+45x_2+20x_3+x_6=20000\\ x_i\ge 0,i=1,2,3,4,5,6\end{array}\end{array}$

3. 基本解法中判别退化问题和多重最优解

3.1. 图解法

图解法是通过平面图形求解线性规划问题，不仅能快速求得最优解，而且可以直观理解任意决策变量的规律性。对于两变量的线性规划存在退化解，平面图形中至少有三条直线交于可行域某一顶点(见图1)；若存在多重最优解，平面图形中目标函数与可行域某一边重合 [7] (见图2)。

但需要注意图解法不适用于多于两个决策变量的情况，尽管早期有学者研究出利用拐点理论可将三维问题的求解通过立体坐标系图形化 [8] ，但多于三个变量的模型求解仍具有一定局限性。因此，不采用图解法判别上述案例退化解和多重最优解的情况。

3.2. 单纯形法

单纯形法是求解多个决策变量的通用方法。迭代过程如表2~4所示，表中C_j表示目标函数的系数，C_b表示基变量的系数，X_b表示基变量，b表示约束方程右侧的常数，使用单纯形法的迭代方法将不多赘述。

Figure 1. Graphic display of retreat resolution

图1. 退化解的图形展示

Figure 2. Graphic display of multiple optimal solutions

图2. 多重最优解的图形展示

Table 2. Initial simplex table

表2. 初始单纯形表

Table 3. The simplex table after the first iteration

表3. 第一次迭代后单纯形表

Table 4. The simplex table after the second iteration

表4. 第二次迭代后单纯形表

运算结果可得： $X^{*}={\left(0,400/3,700,0,10000/3,0\right)}^{\text{T}}$ ，去掉松弛变量得最优解： $X^{*}={\left(0,133,700\right)}^{\text{T}}$ 。当使用单纯形表判别退化解时：若单纯形表进行无休止的循环迭代，无法求解最优解，那么存在退化情况；本实例进行两次迭代即得最优解，由此说明不存在退化情况。当使用单纯形法判别多重最优解时：若最终单纯形表中非基变量检验数为零，那么说明存在多最优解；本实例中初始单纯形表中非基变量为x₄，x₅，x₆，通过两次迭代过程最终得出x₁，x₄，x₆为非基变量，其检验数均不为0，由此说明不存在多重最优解。

通过该实例的数学模型迭代过程，可以发现单纯形法可给出简单的灵敏度分析，但在处理数据庞大、任意变量的模型时计算量会非常大、重复性操作繁琐 [9] 。

4. Excel敏感性分析中判别退化解及多最优解

相较于上述图解法与单纯形法迭代，借助计算机工具是求解复杂线性规划模型最简便的一种方式。下面采用Excel对该线性规划数学模型进行求解，对应的敏感性分析报告如表5和表6所示。

Table 5. Excel sensitivity report 1: variable cell part

表5. Excel敏感性报告1：可变单元格部分

Table 6. Excel sensitivity report 2: constraints

表6. Excel敏感性报告2：约束部分

Figure 3. Four optimal solutions of linear programming problem

图3. 线性规划问题四种最优解

针对线性规划四种解的情况(见图3)，Excel敏感性分析报告中仍无法直观判断其是否有退化情况和多重最优解。因此，本文将以该模型为出发点，探究基于Excel敏感性分析报告判别退化解、多重最优解的存在情况。

4.1. Excel判断退化情况的方法

根据退化解的定义：基变量取值为零。已知存在变量取值为0 (即迷你车x₁终值 = 0)，若要判断其是否有退化情况，问题核心即分析该变量为基变量或非基变量，若为基变量则存在退化解，否则反之。

4.1.1. 解及其性质——定义法

根据线性规划的解及其性质可知，标准LP问题的任一基本可行解，其所含正分量个数必不超过问题的阶数m；对于非退化的基本可行解则必恰有m个正分量，其余分量均为0 [10] 。即若存在正分量的个数恰好等于线性规划问题的阶数且其余分量为0，那么不存在退化情况。下面通过实例说明该方法的应用。

由该模型的敏感性分析报告表5、表6可得最优基本解： $X^{*}={\left(0,133,700,0,333,0\right)}^{\text{T}}$ ，以及阶数m为3。观察该基本可行解恰好有3个正分量x₂，x₃，x₅，其余变量均为0，符合正分量个数等于阶数m的条件。综上，此解是一个非退化的基本可行解，因此不存在退化情况。

4.1.2. 基变量及非基变量在初始与最终单纯形表中个数必相等法

根据单纯形法迭代过程可知，最终单纯形表中基变量个数与初始单纯形表中个数相等，非基变量的个数同样保持不变。在标准LP问题最终解中，基变量一般不为零，非基变量(基变量的退化解情况除外)都须为0。因此，若要判断基变量与非基变量的情况，需要分析最初与最终单纯形表中两者的个数；此处，需要将单纯形法的思想与敏感度分析表结合应用。下面通过实例说明该方法的应用：

如前例所述，求解该模型时已引入松弛变量x₄，x₅，x₆，可见存在3个基变量(x₄, x₅, x₆)和3个非基变量(x₁, x₂, x₃)。由该模型的敏感性分析报告表5已得该模型的基本可行解： $X^{*}={\left(0,133,700,0,333,0\right)}^{\text{T}}$ ，且阶数为3。根据基变量一般不为零的定义，可以确定x₂，x₃，x₅为基变量，x₄，x₆为非基变量。综上，迷你车x₁ = 0存在两种情况：x₁为基变量或为非基变量，下面将以此分析：

若x₁为基变量：已知最初模型中，存在三个基变量x₄，x₅，x₆，三个非基变量x₁，x₂，x₃，根据单纯形法迭代原理，初始单纯形表与最终单纯形表中的基变量必相等，同样，非基变量个数也保持不变。假设x₁为基变量的退化解，且已知最终解中x₂，x₃，x₅为基变量，那么基变量共有4个，与单纯形法迭代原理不符，故x₁属于非基变量。因此，不存在退化解。

4.2. Excel判断多重最优解的方法

根据无穷多最优解的定义：非基变量的检验数取值为零。上文已确认该存在变量(即迷你车x₁)为非基变量，若要判断其是否存在多重最优解，核心即分析其检验数是否为零，若为零则存在多重最优解，否则反之。

4.2.1. 递减成本法

引入递减成本的定义，以便理解该方法。递减成本指该变量变化一个单位导致目标函数发生的变化量。根据单纯形表计算的结果和递减成本的值，可以发现递减成本等于最终(或最优)单纯形表中相应变量的检验数 [10] ，下面通过实例说明该方法的应用。

若非基变量检验数 = 0，则存在多重最优解。根据该模型的敏感性分析报告表5可以得到非基变量x₁，x₄，x₆的递减成本不为0，即检验数不为零。因此，所以该线性规划问题不存在多重最优解，即该最优解是唯一解。

综合上述，在敏感性分析表中，若非基变量的递减成本为零，那么该线性规划问题存在多重最优解。

4.2.2. 对偶关系法

在此，引入(李如兵，宗凤喜)原问题与对偶问题变量之间的对偶关系定理 [6] ，以便于叙述解法(见表7)：

Table 7. Dual relation theorem

表7. 对偶关系定理

由此可得该线性规划模型的变量与标准形式下对偶问题变量的对应关系(见表8)为：

Table 8. Corresponding relation of linear programming model

表8. 线性规划模型的对应关系

退化解情况除外，取值为0的变量为非基变量，如果该非基变量对应的对偶问题变量的阴影价格为0 (阴影价格 = 检验数的相反数)，则说明该线性规划问题有无穷多最优解。下面通过实例说明该定理的应用。

从该模型的敏感性分析报告表6可以看出，变量x₄，x₆是非基变量，x₁为非基变量在第二部分求解退化问题时已确定其必为非基变量。根据上述对偶定理的对应关系可以得出x₁对应y₅，y₅的阴影价格不为0，由此该线性规划问题不存在多重最优解，即该最优解是唯一解。

因此，在敏感性分析结果中，当阴影价格为零时，那么该线性规划问题存在多重最优解。

4.3. 综合法——退化解与多重解对应关系

综合法是判别退化解与多最优解均适用的方法，主要运用退化解与多重解的互补松弛关系。当存在退化解时，原规划问题对应的对偶问题有无穷多个最优解，即原问题资源的影子价格不唯一 [11] 。因此，判别原问题的退化情况可转化为判别对偶问题的多最优解的情况。同理，根据对偶规划的对称性质(对偶规划的对偶是原规划)可知，当原问题存在多最优解时，原问题对应的对偶规划存在退化解。于是，判别原问题的多最优解情况可转换为判别对偶问题的退化解情况。

为便于理解，引入递减成本和阴影价格的关系。根据基解对应性，原规划单纯形法表中检验数行等于对偶规划的一个基解，对偶规划的最优解可以在原问题的最终单纯形表中读出 [12] ；由对偶关系理论可知，线性规划对偶问题的最优解对应资源的影子价格；可以得出原问题的递减成本与对偶问题的阴影价格相互对应。下面结合对偶问题和多重最优解定义，通过该法判别具体实例的退化情况：

根据基解的对应性和敏感性报告中的递减成本，可以读取对偶问题的一个基解 $X^{*}={\left(1.16666667,0,0.8,13.338,0,0\right)}^{\text{T}}$ 。根据基变量不为0及基变量与非基变量最初与最终单纯形表的个数必相等的定理，可以判断y₁，y₃，y₄为非基变量。由对偶规划的对偶是原规划的性质可知，y₁，y₃，y₄的检验数对应x₂，x₃，x₅的终值，检验数不为零，所以对偶问题的解不存在多最优解，等价于原问题不存在退化问题。

5. 进一步讨论

除了Matlab输出结果较为简洁以外，其他计算机工具的输出结果均较为丰富。因此本文不仅适用于Excel的敏感性分析中，其他辅助工具也同样适用。下面进一步讨论前述实例，以Lindo系统输出的敏感性结果作展示。

Table 9. Lindo code running results (no degradation)

表9. Lindo代码运行结果(无退化)

Table 10. Lindo code running results (degradation)

表10. Lindo代码运行结果(退化)

前文数学模型在Lindo中的输出报告见表9，“LP OPTIMUM FOUND AT STEP 2”表示Lindo用单纯形法2次迭代后得到的最优解，直接表明了不存在退化解；除此之外，“REDUCED COST”递减价格、“DUAL PRICES”对偶价格(影子价格)在Lindo系统中均有展示，可见多重最优解的判别与上文Excel的敏感性分析类似，在此不多做赘述。

此外，为了检验出现退化时Lindo系统的结果展示，以Beale的循环实例为退化例子(表10)，可以发现“LP OPTIMUM FOUND AT STEP 0”，即迭代0次或进入无限循环。

6. 结语

本文基于单纯形法定理和对偶理论，通过引用、建立和求解实例模型，结合Excel敏感性分析的报告，从影子价格、递减成本、基变量与非基变量的定义出发，总结出多种判定线性规划问题的最优解是否存在退化情况及多重最优解的方法，具有一定的稳定性、合理性、可靠性。此外，本文通过实例验证了判别方法具有一定的通用性，各种计算机工具均可适用，对使用敏感性分析的人员具有一定的参考价值。