第1章　分解筛选法求解线性规划的概念和方法及多重解求解

1.1　分解筛选法思路、要点及示例

1.1.1　分解筛选法及有关概念

线性规划法经过多年的发展完善，已趋成熟，其中单纯形法最为著名，但是单纯形法属于指数型算法，因此求解效率不高，并存在着死循环等问题，分解筛选法应运而生。分解筛选法可把一个n维的LP问题分解成n个一维的子LP问题，由此筛选出通过最优解角点的有效约束，并把它看作等价于一个等式约束，利用这一思路和特性，可大大简化整个求解步骤，解决了单纯形法存在的一些问题，有更好的应用前景。

1.1.2　解题步骤

在解题时，使用分解筛选法的思路为：①若线性规划问题非空且有界，则其最优解必在其约束凸集的边界或某一角点上；②最优解所在之角点或相切之边界，其对应的起控制作用的诸约束条件此时必然恰好满足，从而具有等式约束的特性，可用这样的等式通过消元法使问题连续降维；③当多次降维把一个n维的LP问题分解为n个一维子问题时，就可以使用约束超平面在各子问题坐标轴上的截点的概念，来求得这些子问题各自的独立“最优解”，称初优解Z_初i，然后选出此n个初优解中最大者（对求最大问题而言）Z_初max。可以证明，此最大初优解所对应的子问题和约束方程，就指出了系统最优角点所通过的那些约束之一。一旦找出了这种约束就可如②中所述使问题连续降维；可将步骤重复进行，直至问题降为一维方停止降维，或筛选完了全部m个约束后，即可通过回代求得最后解答。

为了便于说明和具体理解上述思路和步骤，借助算例来阐述，以加深理解。设有一个三维线性规划问题如下例。

例1-1

求：

对于此题应先进行一维分解，把此三维问题分解为x₁、x₂、x₃三个一维子问题，并求各子问题之初优解Z_初i。为方便和明晰解题思路，解题步骤可以通过列表进行，如表1-1所示。在表1-1含c_i的行中，1、2、3为各目标函数式变量的系数，如式（1-1）所列。

对于每一个子问题，例如对x₁子问题，先分别求约束方程（即约束平面）[式（1-2）、式（1-3）、式（1-4）]在x₁轴上的截点，此截点是令式（1-2）～式（1-4）中除x₁以外的变量均为零时得出的，其表达式为：

式中，IT_ji为第j约束线在第i个变量轴（即x_i轴）上的截点值；a_ji为约束条件式的系数；b_j为各约束式右端的常数项；j、i为约束条件和变量的序号。

然后，选x_i列诸小于或等于截点值IT_ji中的最小者（表1-1中数值带∗者），对x₁轴而言就是6和其对应的约束式（1-3）。再将此最小截点值6乘以目标函数的对应系数c₁得第一子LP问题的初优解Z_初1，即Z_初1=c₁IT_jimin。一般有：

由于Z_初3=18为表1-1中最大的Z_初i，相应的变量为x₃，式（1-4）为约束条件，由此可知，全系统的最优解必通过此约束平面式（1-4）。下一步是将式（1-4）看作等式，进而解出x₃：

然后将式（1-8）代入目标函数式和其他约束方程，这样就得到一个降维后的新LP模型：

该模型与前一个一样，它可再次做一维分解筛选。不过对于目前这一类型，由于为负，且属于退化Ⅰ的情况，故解是简单的，即有=0，从而又有：

把它们回代至式（1-8）中，得，而最优解为：

（x₁，x₂，x₃）^∗=（2，0，6），Z^∗=20

解毕。

分解筛选法解题流程图如下：

若计算时Z_初max同时出现在两个以上的列中，则把不同行的相应约束方程都可看成是等式约束，进而可以联解消元。这样，明显可使计算效率提高，简化计算。

例1-2

求：

在对上面所列九维LP问题进行分解之前，可简单判别出变量x₉属于退化Ⅰ（即c₉<0，A_j9≥0，j=1，…，9）。故有，并可先行从模型中剔除有x₉的项。然后再次分解此八维LP模型，并一一列出所有一维子模型截点值的计算，如表1-2所示。

在计算截点值时，凡是约束式中系数为负的部分，不需要计算，因其已不在第一象限，系数为零者，只需要取每列中的最小截值点，故也不必列出。

在表1-2中，Z_初max为+0，它同时出现在x₂、x₃、x₅、x₆四个子问题中。由此可知，全系统的最优解通过四个相应的约束式［式（1-15）、式（1-16）、式（1-17）、式（1-18）］。把上述四个方程式作为等式联立，通过解出上述的四个变量，可得出下列结果：

把式[1-23（a）]、式[1-23（b）]、式[1-23（c）]、式[1-23（d）]代入目标函数式（1-14）、式（1-19）和式（1-21）。由于式[1-23（a）]、式[1-23（b）]、式[1-23（c）]、式[1-23（d）]都只是单变量之间的比例关系，可使式（1-22）必然满足，不需要再次代入引进有关于x_i≥0的新约束。于是可得降维后的新LP模型：

在上述式中变量x₄属于退化Ⅰ条件，故，并可将其在LP模型中剔除。对于新的LP，再次做一维分解筛选表（见表1-3）。

通过表1-3可得Z_初max=500相应的变量为x₁，约束式为式（1-19），于是可由式（1-19）解出x₁：

再把式（1-19）′代入式（1-14）′、式（1-20）′、式（1-21）′，可得第二次降维后的新LP模型：

在上面的新LP模型中，x₇符合退化Ⅰ的情况，可知以及x₈≤50，在目标式中已无任何未解变量，再将的值回代到式（1-19）以及式[1-23（a）]、式[1-23（b）]、式[1-23（c）]、式[1-23（d）]和式（1-14）″，可得：

至此解毕。

分解筛选法解题流程图如下：