第1章 分解筛选法求解线性规划的概念和方法及多重解求解
1.1 分解筛选法思路、要点及示例
1.1.1 分解筛选法及有关概念
线性规划法经过多年的发展完善，已趋成熟，其中单纯形法最为著名，但是单纯形法属于指数型算法，因此求解效率不高，并存在着死循环等问题，分解筛选法应运而生。分解筛选法可把一个n维的LP问题分解成n个一维的子LP问题，由此筛选出通过最优解角点的有效约束，并把它看作等价于一个等式约束，利用这一思路和特性，可大大简化整个求解步骤，解决了单纯形法存在的一些问题，有更好的应用前景。
1.1.2 解题步骤
在解题时，使用分解筛选法的思路为：①若线性规划问题非空且有界，则其最优解必在其约束凸集的边界或某一角点上；②最优解所在之角点或相切之边界，其对应的起控制作用的诸约束条件此时必然恰好满足，从而具有等式约束的特性，可用这样的等式通过消元法使问题连续降维；③当多次降维把一个n维的LP问题分解为n个一维子问题时，就可以使用约束超平面在各子问题坐标轴上的截点的概念，来求得这些子问题各自的独立“最优解”，称初优解Z初i，然后选出此n个初优解中最大者（对求最大问题而言）Z初max。可以证明，此最大初优解所对应的子问题和约束方程，就指出了系统最优角点所通过的那些约束之一。一旦找出了这种约束就可如②中所述使问题连续降维；可将步骤重复进行，直至问题降为一维方停止降维，或筛选完了全部m个约束后，即可通过回代求得最后解答。
为了便于说明和具体理解上述思路和步骤，借助算例来阐述，以加深理解。设有一个三维线性规划问题如下例。
例1-1
求：
对于此题应先进行一维分解，把此三维问题分解为x1、x2、x3三个一维子问题，并求各子问题之初优解Z初i。为方便和明晰解题思路，解题步骤可以通过列表进行，如表1-1所示。在表1-1含ci的行中，1、2、3为各目标函数式变量的系数，如式（1-1）所列。
表1-1 分解筛选截点IT与Z初计算值
注：∗表示xi列中的最小值，∗∗表示Z初i行中的最大值。
对于每一个子问题，例如对x1子问题，先分别求约束方程（即约束平面）[式（1-2）、式（1-3）、式（1-4）]在x1轴上的截点，此截点是令式（1-2）～式（1-4）中除x1以外的变量均为零时得出的，其表达式为：
式中，ITji为第j约束线在第i个变量轴（即xi轴）上的截点值；aji为约束条件式的系数；bj为各约束式右端的常数项；j、i为约束条件和变量的序号。
然后，选xi列诸小于或等于截点值ITji中的最小者（表1-1中数值带∗者），对x1轴而言就是6和其对应的约束式（1-3）。再将此最小截点值6乘以目标函数的对应系数c1得第一子LP问题的初优解Z初1，即Z初1=c1ITjimin。一般有：
由于Z初3=18为表1-1中最大的Z初i，相应的变量为x3，式（1-4）为约束条件，由此可知，全系统的最优解必通过此约束平面式（1-4）。下一步是将式（1-4）看作等式，进而解出x3：
然后将式（1-8）代入目标函数式和其他约束方程，这样就得到一个降维后的新LP模型：
该模型与前一个一样，它可再次做一维分解筛选。不过对于目前这一类型，由于
为负，且属于退化Ⅰ的情况，故解是简单的，即有
=0，从而又有：
把它们回代至式（1-8）中，得
，而最优解为：
（x1，x2，x3）∗=（2，0，6），Z∗=20
解毕。
分解筛选法解题流程图如下：
若计算时Z初max同时出现在两个以上的列中，则把不同行的相应约束方程都可看成是等式约束，进而可以联解消元。这样，明显可使计算效率提高，简化计算。
例1-2
求：
在对上面所列九维LP问题进行分解之前，可简单判别出变量x9属于退化Ⅰ（即c9<0，Aj9≥0，j=1，…，9）。故有
，并可先行从模型中剔除有x9的项。然后再次分解此八维LP模型，并一一列出所有一维子模型截点值的计算，如表1-2所示。
表1-2 分解筛选法——ITi及Z初i计算
注：右上角有√为该列的最小截点值。
在计算截点值时，凡是约束式中系数为负的部分，不需要计算，因其已不在第一象限，系数为零者，只需要取每列中的最小截值点，故也不必列出。
在表1-2中，Z初max为+0，它同时出现在x2、x3、x5、x6四个子问题中。由此可知，全系统的最优解通过四个相应的约束式［式（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）必然满足，不需要再次代入引进有关于xi≥0的新约束。于是可得降维后的新LP模型：
在上述式中变量x4属于退化Ⅰ条件，故
，并可将其在LP模型中剔除。对于新的LP，再次做一维分解筛选表（见表1-3）。
表1-3 一维分解筛选表
注：右上角有√者为该列的最小截点值。
通过表1-3可得Z初max=500相应的变量为x1，约束式为式（1-19），于是可由式（1-19）解出x1：
再把式（1-19）′代入式（1-14）′、式（1-20）′、式（1-21）′，可得第二次降维后的新LP模型：
在上面的新LP模型中，x7符合退化Ⅰ的情况，可知
以及x8≤50，在目标式中已无任何未解变量，再将
的值回代到式（1-19）以及式[1-23（a）]、式[1-23（b）]、式[1-23（c）]、式[1-23（d）]和式（1-14）″，可得：
至此解毕。
分解筛选法解题流程图如下：
