第六章 分解算法
生产实际中遇到的线性规划问题常常是规模很大的，如果约束条件多到超过计算机容量的程度，就会给求解造成困难。为了克服这一困难，对于大型问题，针对其具体结构，往往可把它分解成几个较小问题来处理，这类方法称为分解算法。
§1 分解定理我们先介绍作为分解算法理论根据之一的分解定理。
对于线性规划问题
（1）
我们已定义可行解集D：
相应地，定义集合
以及集合
则易见是有界凸集，并且的极点个数有限，设它们为，常称为（1）的基可行方向，而中的元素则称为（1）的可行方向或极射向。
设是（1）的一个可行基，如果对某一非基变量，其检验数，系数，令，满足
则，故，即为（1）的可行方向或极射向，并且，而，便是（1）的基可行方向，即。以上分析表明，若（1）的可行解无界，则它存在可行方向或极射向。
定理1 如果D非空，则的充要条件是
(2)
这里是D的极点，yi，i=1，是（1）的基可行方向；
，
证明：充分性是显然的，故只需证必要性，任取，若X是D的极点，则（2）自然成立，否则应有，使
（3）
设X有P个正分量，则由（3）知，若，亦有，故正分量不多于P个，取，再取，则，不妨设，令，则易见，且其正分量个数不多于P-1个，而。若，则，且有。而的正分量个数不多于P-1个；若不成立，则,取，则的正分量个数不多于P-1，而，其中和正分量的个数均不多于P-1，即比X少1。
若，仍不是极点，则对之重复以上步骤，经有限步，必可将X表成
（4）
其中,。故以下只需证。若Y=0，只需取。若，则，取，则。再注意到（4）对有界集合亦成立，且此时。（若D有界而Y≠0，则易证，令。导致D无界，矛盾）从而必有
令，便有，至此，定理获证。
这样，由定理1，得到了（1）之可行解的一般表达式（2），且知若可行解集D有界，其一般表达式为
其中，是D的极点，亦即X可表为极点的凸组合。
§2 二分法考虑如下线性规划问题
这里是矩阵，是维向量,k=1,2
设}
则由分解定理，对，可写为
(8)
是的极点。是基可行方向。
将（8）代入（5）和（7）得
（9）
（10）
可见，若视，为变量，那么解（5）-（7）等价于解（9）-（11）。
只是这里的系数矩阵之列向量（及）和目标函数之系数（及）也是未知的罢了。也正因如此，直接求解（9）-（11）是不行的，还必须作进一步分析，以后称（9）-（11）为主规划。
设已得主规划的一个基（如人造基），记其对应的单纯形算子为（为维向量（与（9）相应）为一数（与（10）相应）），于是各检验数可写为
（12）
（13）
为计算（12）（13），考虑解如下线性规划问题：
（14）
称（14）为问题的子规划。
显然，若（14）无可行解，则原问题（5）-（7）亦无可行解。若（14）有可行解，而无最优解，则利用单纯形迭代，可找到（14）的一个基可行方向，使得，从而由（13）知，按照单纯形法，应选与相应的变量进基，算出这列的系数（因已经知道），得到主元列，并实行通常的换基迭代（修正算法），则可得到一个新的基及对应的乘子。
若（14）有最优解，则对（14）的所有基可行方向，均使得（因这时它的检验数）。从而由（13），（9）-（11）的检验数，另方面若使目标函数满足，则对任意基可行解
便有
这说明已得到最优解。否则说明，从而选为进基变量，算出和主元列，实行换基迭代，可得一新基及对应乘子。
重复以上过程，即可求出（9）-（11）的解，再代入（8），便得（5）---（7）的解。
如果初始基是人造基，或（9）---（11）以典式形式给出，则乘子不必单独计算，就是初始基变量的检验数。
§3 p分法若问题具有以下的结构形式
（15）
（16）
（17）
这里都是矩阵，，，，bk都是适当维数的向量，这种特殊的结构可理解为，有一个总公司，下属p个子公司，每个子公司都有自己的决策变量（）和需要遵守的约束（16）。同时各子公司之间还具有某种联系约束（15），目标是要使总公司的耗费（17）最小。
记
利用分解定理，对，可写为
（18）
（19）
是的极点，是基可行方向。
将（18）代入（15）和（17）得：
（20）
（21）
（22）
我们称（20）-（22）是P分法的主规划，它与（15）-（17）是等价的。
设已知主规划的一个可行基B，记其对应的乘子为
其中是一行向量，维数和（20）的方程个数相同，都是数量，是对应于方程（21）的乘子。易知，B是最优基的条件是：对任何，有
(23)
(24)
条件（23）和（24）等价于下述各线性规划问题
(25)
都有最优解，且最小值不小于，这个规划（25），称为子规划。
若子规划（25）中有一个无可行解，则显然原规划（15）-（17）亦无可行解。
若有某k，使对应的子规划存在基可行方向，使（24）不成立，则可由之生成主元列：
若有某k，使对应的子规划有最优解，且使（23）不成立，则可由之生成主元列
这里是第k个p维单位向量，
据以上分析，不难写出分解算法的计算步骤。这里从略。
例1 求满足
求解过程略（详见[13]或[14]）
4 一种新途径前两节介绍的二分法，对系数矩阵A没有特殊要求。解子规划（14）可使约束条件减少一半（但变量不减少）。P分法是针对特殊结构（15）-（17）的，解子规划（25）可在P个计算机上并行，主规划的约束条件可减至m+p个。但是两种方法的每一步迭代，都要以求出子规划的最优解为前提，可见付出的代价是相当大的，即使对例1这样简单的问题，求解也要花费很大的篇幅。我们考虑一种新途径，其基本思想是通过适当的变换，把部分约束转化成上限约束的形式，从而可用第五章中提供的方法处理，以达到减少约束和变量的目的。
形如（5）-（7）的一般结构不妨设，于是（5）变成
设可以估计出的一个上界：
(26)
再设中矩阵N的秩为r
若r=m，令
(27)
则由
(28)
再由（26）知
(29)
再设，其中非奇异，相应地，则由（27）有
(30)
将（28），(30)代入（6）、（7）便得一含变量u、,个普通约束个上限约束（29）的问题，解之，并将解代入（30），求出，若，则立得（5）-（7）的最优解，否则将使（30）小于0的那些中的一个作为新增约束，继续求解，直到为止。
若r<m1，不妨设N的前r行线性无关，记前r行的矩阵为，仍令
对的前r个约束重复以上过程，而将中余下的看成是（6）的约束来处理约束是不等式的情形
(31)
若（31）中约束的个数不多于变量的个数，即，则添加松弛变量Y，有
于是可采用（一）的方法处理。
若m>n，且秩A为n，取A的一个n阶可逆子矩阵，不妨设为前n行，令，便有
(32)
设能估计出的一个下界d，并不妨设d=0，（此假定，对许多实际问题例如资源利用问题，是成立的，至于若d<0，可作变换v=u-d）便有
(33)
这是一个含有m-n个普通约束，n个上限约束的问题，解之，并代入（32）若求得的，则其即为最优解。否则，设负分量为，k=1，。。。t，则增加约束（或选其中之一，例如绝对值最大的）：
(34)
继续求解，直到求得的为止。
注意，若，则必有。
约束为不等式的情形：
(35)
任取A的r个线性无关的行，记为，其中非奇异，仍令
(36)
记，可得
(37)
将（37）代入（35）其余约束条件中，便得含有m-r约束，n个变量,的问题，解之，再代入（37），若，则已得最优解，若可行解无下界或中有负分量，则于（37）中选适当约束加上去，继续求解，直到求得的为止例2 用本节的方法解例1
令 （38）
得 （39）
代入其余约束后得
（40）
（40）是变量有上限的问题，引入松弛变量，做单纯形表，具体迭代过程如下：
0 0 1 1 1 0
3/5 1/5* 2 1 0 1
15
40
f
1/5 2/5 2 1 0 0
0
0 0 1 1 1 0
3 1 10 5 0 5
15
200
f
-1 0 -2 -1 0 -2
-80
0 0 1 1 1 0
3 -1 10* 5 0 5
15
180
f
-1 0 -2 -1 0 -2
-80
-3/10* 1/10 0 1/2 1 -1/2
3/10 -1/10 1 1/2 0 1/2
-3
18
f
-2/5 -1/5 0 0 0 -1
-44
1 -1/3 0 -5/3 -10/3 5/3
0 0 -1 1* 1 0
10
155
f
0 -1/3 0 -2/3 -4/3 -1/3
-40
1 -1/3 5/3 0 -5/3 5/3
0 0 -1 1 1 0
55/3
5
f
0 -1/3 -2/3 0 -2/3 -1/3
-110/3
于是得
u1=55/3,u2=20,y1=10,y2=5,f= -110/3
从而x1=25/3,x2=10/3，由于它们均非负，故已求得最优解：
x1=25/3,x2=10/3,y1=10.y2=5
minf=-110/3
这比用P分法求解简单多了，但是，事情并非总是如此成功。因为最后求得的可能有负值，这就要增加约束迭代了，只有当（32）中的，才肯定不会出现负值。不过事先很难保证这一点，一般中负值元素不多并比较小（象本例那样）就不错了。当然从平均性态看来（32）中可有一半的分量非负，从而能减少其中的一半约束。
生产实际中遇到的线性规划问题常常是规模很大的，如果约束条件多到超过计算机容量的程度，就会给求解造成困难。为了克服这一困难，对于大型问题，针对其具体结构，往往可把它分解成几个较小问题来处理，这类方法称为分解算法。
§1 分解定理我们先介绍作为分解算法理论根据之一的分解定理。
对于线性规划问题
（1）
我们已定义可行解集D：
相应地，定义集合
以及集合
则易见是有界凸集，并且的极点个数有限，设它们为，常称为（1）的基可行方向，而中的元素则称为（1）的可行方向或极射向。
设是（1）的一个可行基，如果对某一非基变量，其检验数，系数，令，满足
则，故，即为（1）的可行方向或极射向，并且，而，便是（1）的基可行方向，即。以上分析表明，若（1）的可行解无界，则它存在可行方向或极射向。
定理1 如果D非空，则的充要条件是
(2)
这里是D的极点，yi，i=1，是（1）的基可行方向；
，
证明：充分性是显然的，故只需证必要性，任取，若X是D的极点，则（2）自然成立，否则应有，使
（3）
设X有P个正分量，则由（3）知，若，亦有，故正分量不多于P个，取，再取，则，不妨设，令，则易见，且其正分量个数不多于P-1个，而。若，则，且有。而的正分量个数不多于P-1个；若不成立，则,取，则的正分量个数不多于P-1，而，其中和正分量的个数均不多于P-1，即比X少1。
若，仍不是极点，则对之重复以上步骤，经有限步，必可将X表成
（4）
其中,。故以下只需证。若Y=0，只需取。若，则，取，则。再注意到（4）对有界集合亦成立，且此时。（若D有界而Y≠0，则易证，令。导致D无界，矛盾）从而必有
令，便有，至此，定理获证。
这样，由定理1，得到了（1）之可行解的一般表达式（2），且知若可行解集D有界，其一般表达式为
其中，是D的极点，亦即X可表为极点的凸组合。
§2 二分法考虑如下线性规划问题
这里是矩阵，是维向量,k=1,2
设}
则由分解定理，对，可写为
(8)
是的极点。是基可行方向。
将（8）代入（5）和（7）得
（9）
（10）
可见，若视，为变量，那么解（5）-（7）等价于解（9）-（11）。
只是这里的系数矩阵之列向量（及）和目标函数之系数（及）也是未知的罢了。也正因如此，直接求解（9）-（11）是不行的，还必须作进一步分析，以后称（9）-（11）为主规划。
设已得主规划的一个基（如人造基），记其对应的单纯形算子为（为维向量（与（9）相应）为一数（与（10）相应）），于是各检验数可写为
（12）
（13）
为计算（12）（13），考虑解如下线性规划问题：
（14）
称（14）为问题的子规划。
显然，若（14）无可行解，则原问题（5）-（7）亦无可行解。若（14）有可行解，而无最优解，则利用单纯形迭代，可找到（14）的一个基可行方向，使得，从而由（13）知，按照单纯形法，应选与相应的变量进基，算出这列的系数（因已经知道），得到主元列，并实行通常的换基迭代（修正算法），则可得到一个新的基及对应的乘子。
若（14）有最优解，则对（14）的所有基可行方向，均使得（因这时它的检验数）。从而由（13），（9）-（11）的检验数，另方面若使目标函数满足，则对任意基可行解
便有
这说明已得到最优解。否则说明，从而选为进基变量，算出和主元列，实行换基迭代，可得一新基及对应乘子。
重复以上过程，即可求出（9）-（11）的解，再代入（8），便得（5）---（7）的解。
如果初始基是人造基，或（9）---（11）以典式形式给出，则乘子不必单独计算，就是初始基变量的检验数。
§3 p分法若问题具有以下的结构形式
（15）
（16）
（17）
这里都是矩阵，，，，bk都是适当维数的向量，这种特殊的结构可理解为，有一个总公司，下属p个子公司，每个子公司都有自己的决策变量（）和需要遵守的约束（16）。同时各子公司之间还具有某种联系约束（15），目标是要使总公司的耗费（17）最小。
记
利用分解定理，对，可写为
（18）
（19）
是的极点，是基可行方向。
将（18）代入（15）和（17）得：
（20）
（21）
（22）
我们称（20）-（22）是P分法的主规划，它与（15）-（17）是等价的。
设已知主规划的一个可行基B，记其对应的乘子为
其中是一行向量，维数和（20）的方程个数相同，都是数量，是对应于方程（21）的乘子。易知，B是最优基的条件是：对任何，有
(23)
(24)
条件（23）和（24）等价于下述各线性规划问题
(25)
都有最优解，且最小值不小于，这个规划（25），称为子规划。
若子规划（25）中有一个无可行解，则显然原规划（15）-（17）亦无可行解。
若有某k，使对应的子规划存在基可行方向，使（24）不成立，则可由之生成主元列：
若有某k，使对应的子规划有最优解，且使（23）不成立，则可由之生成主元列
这里是第k个p维单位向量，
据以上分析，不难写出分解算法的计算步骤。这里从略。
例1 求满足
求解过程略（详见[13]或[14]）
4 一种新途径前两节介绍的二分法，对系数矩阵A没有特殊要求。解子规划（14）可使约束条件减少一半（但变量不减少）。P分法是针对特殊结构（15）-（17）的，解子规划（25）可在P个计算机上并行，主规划的约束条件可减至m+p个。但是两种方法的每一步迭代，都要以求出子规划的最优解为前提，可见付出的代价是相当大的，即使对例1这样简单的问题，求解也要花费很大的篇幅。我们考虑一种新途径，其基本思想是通过适当的变换，把部分约束转化成上限约束的形式，从而可用第五章中提供的方法处理，以达到减少约束和变量的目的。
形如（5）-（7）的一般结构不妨设，于是（5）变成
设可以估计出的一个上界：
(26)
再设中矩阵N的秩为r
若r=m，令
(27)
则由
(28)
再由（26）知
(29)
再设，其中非奇异，相应地，则由（27）有
(30)
将（28），(30)代入（6）、（7）便得一含变量u、,个普通约束个上限约束（29）的问题，解之，并将解代入（30），求出，若，则立得（5）-（7）的最优解，否则将使（30）小于0的那些中的一个作为新增约束，继续求解，直到为止。
若r<m1，不妨设N的前r行线性无关，记前r行的矩阵为，仍令
对的前r个约束重复以上过程，而将中余下的看成是（6）的约束来处理约束是不等式的情形
(31)
若（31）中约束的个数不多于变量的个数，即，则添加松弛变量Y，有
于是可采用（一）的方法处理。
若m>n，且秩A为n，取A的一个n阶可逆子矩阵，不妨设为前n行，令，便有
(32)
设能估计出的一个下界d，并不妨设d=0，（此假定，对许多实际问题例如资源利用问题，是成立的，至于若d<0，可作变换v=u-d）便有
(33)
这是一个含有m-n个普通约束，n个上限约束的问题，解之，并代入（32）若求得的，则其即为最优解。否则，设负分量为，k=1，。。。t，则增加约束（或选其中之一，例如绝对值最大的）：
(34)
继续求解，直到求得的为止。
注意，若，则必有。
约束为不等式的情形：
(35)
任取A的r个线性无关的行，记为，其中非奇异，仍令
(36)
记，可得
(37)
将（37）代入（35）其余约束条件中，便得含有m-r约束，n个变量,的问题，解之，再代入（37），若，则已得最优解，若可行解无下界或中有负分量，则于（37）中选适当约束加上去，继续求解，直到求得的为止例2 用本节的方法解例1
令 （38）
得 （39）
代入其余约束后得
（40）
（40）是变量有上限的问题，引入松弛变量，做单纯形表，具体迭代过程如下：
0 0 1 1 1 0
3/5 1/5* 2 1 0 1
15
40
f
1/5 2/5 2 1 0 0
0
0 0 1 1 1 0
3 1 10 5 0 5
15
200
f
-1 0 -2 -1 0 -2
-80
0 0 1 1 1 0
3 -1 10* 5 0 5
15
180
f
-1 0 -2 -1 0 -2
-80
-3/10* 1/10 0 1/2 1 -1/2
3/10 -1/10 1 1/2 0 1/2
-3
18
f
-2/5 -1/5 0 0 0 -1
-44
1 -1/3 0 -5/3 -10/3 5/3
0 0 -1 1* 1 0
10
155
f
0 -1/3 0 -2/3 -4/3 -1/3
-40
1 -1/3 5/3 0 -5/3 5/3
0 0 -1 1 1 0
55/3
5
f
0 -1/3 -2/3 0 -2/3 -1/3
-110/3
于是得
u1=55/3,u2=20,y1=10,y2=5,f= -110/3
从而x1=25/3,x2=10/3，由于它们均非负，故已求得最优解：
x1=25/3,x2=10/3,y1=10.y2=5
minf=-110/3
这比用P分法求解简单多了，但是，事情并非总是如此成功。因为最后求得的可能有负值，这就要增加约束迭代了，只有当（32）中的，才肯定不会出现负值。不过事先很难保证这一点，一般中负值元素不多并比较小（象本例那样）就不错了。当然从平均性态看来（32）中可有一半的分量非负，从而能减少其中的一半约束。
