少一半(但变量不减少)。P分法是针对特殊结构(15)-(17)的,解子规划(25)可在P 个计算机上并行,主规划的约束条件可减至m+p个。但是两种方法的每一步迭代,都要以 求出子规划的最优解为前提,可见付出的代价是相当大的,即使对例1这样简单的问题,求 解也要花费很大的篇幅。我们考虑一种新途径,其基本思想是通过适当的变换,把部分约束 转化成上限约束的形式,从而可用第五章中提供的方法处理,以达到减少约束和变量的目的。 (一)形如(5)-(7)的一般结构 不妨设4=(,N,于是(5)变成 A1X=(1,N X+NX= 6 设可以估计出x的一个上界 X≤d 再设(5y中矩阵N的秩为r 若r=m,令 u= Nx -+d 则由(5y 再由(26)知 0≤t≤d 再设N=(N,M),其中N非奇异,相应地x=8|,则由(27)有 Kx=M(u+b-d-N2Xx,)≥0 将(28),(30)代入(6)、(7)便得一含n-m变量u、Xx,m2个普通约束m个上限约束 (29)的问题,解之,并将解代入(30),求出X,若xx≥0,则立得(5)-(7)的 最优解,否则将使(30)小于0的那些中的一个作为新增约束,继续求解,直到x≥0 为止。 若r<m,不妨设N的前r行线性无关,记前r行的矩阵为N,仍令 对(5)的前r个约束重复以上过程,而将(5y中余下的看成是(6)的约束来处理 (二)约束是不等式≤的情形 AX≤b 若(31)中约束的个数不多于变量的个数,即m≤n,则添加松弛变量Y,有 AX+Y=b 于是可采用(一)的方法处理 若m>n,且秩A为n,取A的一个n阶可逆子矩阵A,不妨设为前n行,令4X=u,131 少一半（但变量不减少）。P 分法是针对特殊结构（15）-（17）的，解子规划（25）可在 P 个计算机上并行，主规划的约束条件可减至 m+p 个。但是两种方法的每一步迭代，都要以 求出子规划的最优解为前提，可见付出的代价是相当大的，即使对例 1 这样简单的问题，求 解也要花费很大的篇幅。我们考虑一种新途径，其基本思想是通过适当的变换，把部分约束 转化成上限约束的形式，从而可用第五章中提供的方法处理，以达到减少约束和变量的目的。 （一） 形如（5）-（7）的一般结构 不妨设 ( , ) A1 = I N ，于是（5）变成 1 1 ( , ) X NX b X X A X I N I N N I = + =         = (5) 设可以估计出 XI 的一个上界： XI  d (26) 再设 (5) 中矩阵 N 的秩为 r 若 r=m，令 u = NX N − b + d 1 (27) 则由 (5) XI = d − u (28) 再由（26）知 0  u  d (29) 再设 ( , ) N = N1 N2 ，其中 N1 非奇异，相应地         = 2 1 N N N X X X ，则由（27）有 ( ) 0 1 2 2 1 1 = 1 + − −  − XN N u b d N XN (30) 将（28），(30)代入（6）、（7）便得一含 n − m1 变量 u、 N2 X , m2 个普通约束 m1 个上限约束 （29）的问题，解之，并将解代入（30），求出 N1 X ，若 0 1 X N  ，则立得（5）-（7）的 最优解，否则将使（30）小于 0 的那些中的一个作为新增约束，继续求解，直到 0 1 X N  为止。 若 r<m1，不妨设 N 的前 r 行线性无关，记前 r 行的矩阵为 Nr ，仍令 u NrXN br dr r = − + 1 对 (5) 的前 r 个约束重复以上过程，而将 (5) 中余下的看成是（6）的约束来处理 （二） 约束是不等式  的情形 AX  b (31) 若（31）中约束的个数不多于变量的个数，即 m  n ，则添加松弛变量 Y，有 AX +Y = b 于是可采用（一）的方法处理。 若 m>n，且秩 A 为 n，取 A 的一个 n 阶可逆子矩阵 A1 ，不妨设为前 n 行，令 A1X = u