1.2　分解筛选法的应用条件及实用的运算技术和规则

分解筛选法可直接适用于约束条件数m小于等于维数n的线性规划问题。对于m>n的情况，需要把原LP问题转化为它的对偶问题，再使用分解筛选法来求解。此m的数目不包括变量非负要求的约束条件，对于右端常数项已为正的求最大问题的大于等于约束，一般也可不包括在m数中。这是因为在求最大化问题中，起主要约束作用（也可称为有效约束）的通常是那些小于等于约束。

对于一个有m个约束的n维LP问题，其求解所需要的最大筛选步数为：min{m，n}。例如，若m<n，则筛选完m轮后，其余n-m个变量就不再需要计算，可直接令其为零。根据线性规划理论，此n个变量中至少有n-m个为零；或者说至多有m个为非零，而筛选法的功能就首先（依次）筛选出贡献较大的这“至多m个”的非零变量。

以下是针对求最大问题的情况进行筛选的主要运算技术和规则的讲解。

1.2.1　截点求法和Z_初m的选定

（1）一般可只计算a_ji>0的项的截点值，IT_ji=b_ja_ji，而不必计算a_ji<0的项。因规划问题多半有变量非负的要求，亦即解在第一象限，故不在第一象限的截点不会用上［当b_j<0时，a_ji<0的项亦要算截点。本法在最初准备模型时，出于上述原因，规定了须把各约束式的常数项b_j均转化为正值］。至于a_ji=0的项，一般不需要计算，只在某变量可能为无界时，才需要计算。对大于等于约束，求截点IG_ji，则a_ji为正或负均需要求解。

（2）对于Z_初i均为零时之处理，应分两种情况：①如Z_初i=0系部分由于c_i中有零，部分则是因某一约束式的常数项为零，则按c_ib_ja_ji=K_iO中K_i最大者选为Z_初m；②如Z_初m=0是全由于某一约束式的常数项为零，此时按c_i/a_ji=K_i最大者选为Z_初m。

（3）对于有（设为K个）等式约束时，显然，首先应利用它们来进行降维与消元运算，此时可先从K个约束整体来求Z_初m，以此来定消元顺序（Z_初m中截点值一致取列中最大值或最小值均可，因两种重点不同）。一般可在每列之K行中取最大截点值。

1.2.2　退化Ⅰ

如果目标函数中，某变量之系数为负或零；小于等于约束，该列诸系数等于零或正；大于等于约束，均为零或负；如有等式约束，其系数亦为零，等于零（常数项已均转化为正，若非正时也可以），则此变量之最优解，此称退化Ⅰ。

证明：假设尚有除零外的更优的解，因其必为正值解，故：

（1）目标函数的之项将为负，而使目标函数值减小（减优）。

（2）对于诸小于等于约束的条件，则当正值移项后，将减少右端常数项b_j之值，也就是使小于等于约束条件的约束范围更加缩小，这无异于增加了一个或一组新的约束。根据线性规划的下列特性：“对于一个LP问题，当增加一个新的有效约束后，不会使解增优。”

（3）对于大于等于约束，其负值项移项后的情况亦属相同，而对等式项的零值项，则无影响。因此结合上述三点，可知异于零的解，只会使最优解值减小（也可以相同），故的解会更优的假设是不对的。以上证毕。

对于退化Ⅰ_a的证明，也可以仿上给出。

1.2.3　退化Ⅱ

当优选出Z_初m后，如果此相应列有大于等于约束项一个或数个，则求大于等于诸式此列的最大截点：IG_j=b_j/a_ji（包括IG_j=∞时）。如果IG_j≤IT_j，且IG_j≥0，则无退化Ⅰ，可按正常认为解通过IT_j的约束来筛选。只当IG_j>IT_j或IG_j小于等于某负值（或IG<0）时，则称为有退化。它说明解已不在小于等于约束x之正向截轴上。此时的解法如下。

当IG_j>IT_j，即两截点的要求互相矛盾，解不在变量轴上时，解将（可能）在与Z_初m所在之x_i轴相连的某二维子坐标平面上。因此：

（1）除了已知的x_Zm之变量轴（记为x_mi，可称为主变量）外，尚须找另一变量轴相配（记为x_si，可称为副变量），以便能够组合成一个二元联立方程组，解出小于等于与大于等于（称主约束和副约束）这两约束的交点P之值。

（2）此副变量x_si一般均可选Z_初次大所对应之列。当出现下列两类特殊情况时则略异：一种是具有最大截值的大于等于副约束，其x_si和x_mi相应的两个系数不能都为零或负，否则须另选Z_初再次大者；另一种是当线性规划问题时，仅有一个小于等于（包括等于）约束时，如果不是无解，则由于唯一的非零解必在此约束上，故可根据下列比值来更快地直接求解。

即按最小者来选出副变量x_si联解；或按R_ci=R_Ai/C_i之最小者来选x_si的解，最后取出两者中Z的更优者。

（3）在找出了x_si并令主、副变量x_mi、x_si两列的外变量均为零，解出二元联立方程，即交点坐标后，将其代入其余各约束式，看是否满足。如均满足，则知解通过此x_mi相应之小于等于约束。故令它为等式，并解出主变量和消元，一如无退化Ⅱ时之正规筛选法进行。

（4）如果交点值不能满足某些约束，则当不满足者为小于等于约束，就改选同列中小于等于的截点值的次小者，作为新的主约束，并重新同上步骤进行计算（此时原主约束可剔除）。如果不满足者为大于等于约束，则同理另选同列中大于等于截点的次大之约束，进行同上步骤之计算，依次类推。

（5）若有小于等于约束或大于等于约束均已改选完的情况，而交点坐标在某轮中有负值（即交点尚不能最后满足），则说明规划问题无解，此时约束集为空集。否则此最后交点P即为最优解。

对于另一种退化Ⅱ_a，即IG_j小于某负值，说明解不在该变量的正值轴上。此时它的求解办法和步骤仍同前述。

1.2.4　解题步骤

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

下面我们举一算例，借以说明退化Ⅱ问题和其解法概貌。

例1-3

对此问题，首先可看出x₃、x₄属退化Ⅰ情况，故其最优解为零，并可先从模型中剔除。然后求两约束式各变量的截点值，并列出分解筛选表（见表1-4）。

从表1-4中可见，最优解通过必然的唯一的式（1-25）和x₆。但式（1-26）和式（1-25）的截点值IG₆=7>6=IT₆，故有矛盾，所以属于退化Ⅰ（若无矛盾，则解得：，Z^∗=18，其余变量均为0）。

为了进一步求解，根据上文所述，比较两式中各例的子LP问题之系数比值R_Ai。简单计算可知最小比值为x₁列的R_A1=2/3，于是可以写出令其余变量为零，x₁和x₆的二元联立方程组：

2x₁+3x₆=18

3x₁+x₆=7

并解出：x₁=0.4286，x₆=5.7143。

由于此题之R_cmin亦为i=1，故此即为欲求的最优解。将这个值连同x₂=x₃=x₄=x₆=0代入目标式，有Z^∗=17.714。

至此解毕。

从这个解答过程中可以看出，式（1-26）起了辅助性的有效约束，解答过程稍有减少，解答效率有所提高。

当有多个大于等于约束时，则应将以上求得的解代入其余各约束式看是否满足。如有不满足的解，则寻找IG_j截点为次大者再次计算直至满足，否则最后为无解。

退化Ⅱ问题的解题流程图如下：

1.2.5　退化Ⅲ

相对于m=n的模型，如果某变量的各个约束式的截点值都相同，则它是一种角顶在此变量轴的角锥形约束凸集。在遇到此类特种情况时应将其转化为对偶问题来进行求解，称为退化Ⅲ。另外，若使用退化Ⅰ的法则，那么原问题的一个或多个变量从一开始就应等于零，所以率先从模型中剔除后，若此时余下的变量数n′<m，则应将其转为对偶问题来求解。此可称退化Ⅲa。

1.2.6　至多m个变量为非零

根据线性规划理论，在n维m个约束的LP问题中，最多有m个变量为非零，故即至少n-m个变量为零。因此当筛选完m个约束后，由于筛选法逐次筛选出的常是贡献最大（一般为非零）的变量，故可令余下的n-m个未筛选到的变量为零。上述原则中，m主要是指求最大问题时的小于等于的约束，且无退化Ⅱ时的情况。而提“最多”和“至少”，是因为在诸约束条件中可能还有大于等于的一些约束。

因此，如进行更细一步的分析，则有：当有m′个大于等于约束都不起控制作用，则一般就有n-（m-m′）个变量为零值或m-m′个变量为非零值。若存在退化Ⅱ情况（即有一些大于等于约束起控制作用），则零值变量的数目将相应减少。上述中，大于等于约束的数目为m′，各约束条件的总数为m。

1.2.7　化为求最小问题

如果在逐轮筛选的各次新LP模型中，若出现目标函数各系数均为负或零时，宜将其化为求最小问题来求解。而且这些负系数的变量的解就都等于零，从而可以结束筛选。

1.2.8　变量非负约束的简易处理

按理在筛选出消元变量和相应约束式后，其代换式应当同时代入该变量的非负约束x_i≥0中。但是考虑到筛选出的常是贡献较大的，它应是有正值的变量，故x_i≥0的约束一般能自然满足，而不起什么作用。因此为了使运算简便，可以不在每次代换时都列入x_i≥0，而只需在最后一维求解和回代的过程中，遇有某变量值小于零时，则令其等于零，并在最后得解后检验解是否满足各约束式。若满足，则解无误，若不满足某些约束式，则解为无解。

1.2.9　一些附属求解技术——无解、无界解和多重解

在常规线性规划的求解过程中，常要求进行附带判别是否为无解或无界解，以及是否具有多重解存在。下面列出前两者的判别条件：

（1）无解判别。当约束集为空集时即为无解，或当对变量有非负要求的问题出现，且最后解某变量的值为负时为无解。它一般存在于同时有小于等于及大于等于两类约束，且起控制作用的两个此类约束的交点不在第一象限（对于变量有非负要求的LP问题而言）。

（2）无界解判别。在求最大问题时某变量在目标函数式中的系数为正值，而诸小于等于约束之中该列的系数均为零或负、大于等于约束中的系数均为零或正，以及等于约束中它的系数为零时，三条同时满足即为无界（如原问题无大于等于或等于约束，则上述条件可以自动缩减）。

另外一类是目标函数系数有一正一负，在相应的小于等于诸有效约束之中，相对应的系数亦有一正一负且数值相当，亦可有无界解。

约束集没有上限或上界是无界的几何特征。

（3）多重解问题。对LP可分为相似性重解Ⅰ和无关性重解Ⅱ两大类别。它有一定的重要实用意义，而分解筛选法又恰有独特的解此问题的功能。

1.2.10　解的最优性检验

使用筛选法所得的成果，按其理论基础与运算规则，一般可以确信其解为最优。但也可通过简便的办法，来另行旁证其最优性。可以仿单纯形法对成果最优性进行论证，说明它在筛选法中的作用。

当在筛选的过程中得出了各轮的消元变量和回代方程之后，就可将这些回代式（再加上相应的松弛变量，或当在大于等于约束时，减去一剩余变量之后）按顺向的轮次顺序先后代入原目标函数式，及其余各项约束式，则最后得出的新目标式，即相当于单纯形法表中最后表的末行式。如果此行的各变量（可称非基本变量）的系数均为负或零，即可以说明解确实为最优（不过当变量无非负约束的时候，则可能有正号，实即“负负值解”）。

1.2.11　求最小问题时运算规则的不同之处

（1）在LP模型的列式上：①等于约束仍放置最前；②大于等于约束放置其后；③小于等于约束放置最后，可作为辅助性约束来看待。

（2）求Z_初min时：①取诸截值点IT_i的最大值；②在诸Z_初i中取其最小值。

（3）退化Ⅰ和退化Ⅱ要做相应改变。①退化Ⅰ：所有c_i>0，诸大于等于约束的该列系数a_ji均小于等于零，诸小于等于约束的系数约大于等于零，等式约束系数为零者属退化Ⅰ，该变量的最优值为零；②退化Ⅱ：应该就诸小于等于约束来求最小截点IG_i的值，并与上述（2）①中IT_i的值进行比较，检查是否有矛盾，有矛盾时属退化Ⅱ。