我们称(20)-(22)是P分法的主规划,它与(15)-(17)是等价的 设已知主规划的一个可行基B,记其对应的乘子为 丌=(x1,mou,…;zop) 其中x1是一行向量,维数和(20)的方程个数相同,xm都是数量,是对应于方程(21) 的乘子。易知,B是最优基的条件是:对任何X,Y有 =(x14-C4)x+rak≤0 (23) 4=(x14-C)≤0 条件(23)和(24)等价于下述各线性规划问题 A4Xk=b(k=1…,p) X≥0 n(Ck-丌14)X 都有最优解,且最小值不小于xak,这个规划(25),称为子规划 若子规划(25)中有一个无可行解,则显然原规划(15)-(17)亦无可行解。 若有某k,使对应的子规划存在基可行方向y,使(24)不成立,则可由之生成主元 P A Y 若有某k,使对应的子规划有最优解x,且使(23)不成立,则可由之生成主元列 AX 这里1是第k个p维单位向量,=0-010.0 据以上分析,不难写出分解算法的计算步骤。这里从略 例1求x,x2,列y满足 ≤30 x, x+2x2+2y1+y2 x,x2,y1,y2≥0 求解过程略(详见[1或[14]) 4一种新途径 前两节介绍的二分法,对系数矩阵A没有特殊要求。解子规划(14)可使约束条件减130   = = = + p k j kj j K k p k i ki i f CK Xk C Y 1 1 min ( ) ( ) （22） 我们称（20）-（22）是 P 分法的主规划，它与（15）-（17）是等价的。 设已知主规划的一个可行基 B，记其对应的乘子为 ( , , , )  = 1 01  0P 其中  1 是一行向量，维数和（20）的方程个数相同，  0k 都是数量，是对应于方程（21） 的乘子。易知，B 是最优基的条件是：对任何 i X k ， j Yk 有 = ( 1 − ) + 0k  0 i ki k k k   A C x  (23) = ( 1 − )  0 j kj  Ak Ck Yk (24) 条件（23）和（24）等价于下述各线性规划问题      −  = = k k k k k k k C A X X A X b k p min( ) 0 ( 1, , )  1  (25) 都有最优解，且最小值不小于  0k ，这个规划（25），称为子规划。 若子规划（25）中有一个无可行解，则显然原规划（15）-（17）亦无可行解。 若有某 k，使对应的子规划存在基可行方向 j Yk ，使（24）不成立，则可由之生成主元 列：         = − 0 1 j k k kj A Y P B 若有某 k，使对应的子规划有最优解 i X k ，且使（23）不成立，则可由之生成主元列         = − k i k k ki e A X P B 1 这里 k e 是第 k 个 p 维单位向量， T k k e = (00 1 00) 据以上分析，不难写出分解算法的计算步骤。这里从略。 例 1 求 1 2 1 2 x , x , y , y 满足              = − − − −  + + +  +    +  +  1 2 1 2 1 2 1 2 1 2 1 2 1 2 2 1 1 2 1 2 min 2 , , , 0 2 2 40 15 10 10 2 20 3 30 f x x y y x x y y x x y y y y y y x x x x 求解过程略（详见[13]或[14]） 4 一种新途径 前两节介绍的二分法，对系数矩阵 A 没有特殊要求。解子规划（14）可使约束条件减