则由分解定理,对X∈D2,可写为 x=∑ax+∑By 1, a, B x是D的极点。y是基可行方向 将(8)代入(5)和(7)得 ∑(AX)a1+2(4Y)B=b 2a1=1,a20,B,20 (10) minf=∑x+zCy)B 可见,若视a,B为变量,那么解(5)-(7)等价于解(9)·(11) 只是这里的系数矩阵之列向量(4X及Ay)和目标函数之系数(C1X及C1y1)也是 未知的罢了。也正因如此,直接求解(9)-(11)是不行的,还必须作进一步分析,以后称 (9)-(11)为主规划。 设已得主规划的一个基(如人造基),记其对应的单纯形算子为r=(x;,x)(x为m维 向量(与(9)相应)x为一数(与(10)相应)),于是各检验数可写为 -CX=(x141-C)X+z (12) CY=(丌1A1-C)Y (13) 为计算(12)(13),考虑解如下线性规划问题 A X=6- (14) min(C-14)X 称(14)为问题的子规划。 显然,若(14)无可行解,则原问题(5)-(7)亦无可行解。若(14)有可行解,而 无最优解,则利用单纯形迭代,可找到(14)的一个基可行方向y,使得(C-x14)y1<0, 从而由(13)知λ,>0,按照单纯形法,应选与λ,相应的变量进基,算出B,这列的系数 (因己经知道),得到主元列P=B-{4),并实行通常的换基迭代(修正算法),则可得到 个新的基B及对应的乘子 若(14)有最优解x,则对(14)的所有基可行方向y,均使得(-zA4)y1≥0(因这 时它的检验数0)。从而由(13),(9)·(11)的检验数,=-C-x14)y≤0,另方128 则由分解定理，对 X D2 ，可写为 j j j i i X = iX + Y (8)  = 1, i j  0 i  i  ， i X 是 D2 的极点。 j Y 是基可行方向。 将（8）代入（5）和（7）得 1 1 1 (A X ) (A Y ) j b j j i i i   +   = （9）  = 1, i  0 j  0 i  i  ， （10） j j j i i i min f = (CX ) + (C Y ) 可见，若视 i ，  j 为变量，那么解（5）-（7）等价于解（9）-（11）。 只是这里的系数矩阵之列向量（ i A1X 及 j A1Y ）和目标函数之系数（ i C1X 及 j C1Y ）也是 未知的罢了。也正因如此，直接求解（9）-（11）是不行的，还必须作进一步分析，以后称 （9）-（11）为主规划。 设已得主规划的一个基（如人造基），记其对应的单纯形算子为 ( , )  = 1 0 （  1 为 m1 维 向量（与（9）相应）  0 为一数（与（10）相应）），于是各检验数可写为 1 1 0 1 ( ) 1   − =  − +          = i i i i CX A C X A X （12） j j j j CY A C Y AY ( ) 0 1 1 1 − = −          =   （13） 为计算（12）（13），考虑解如下线性规划问题：      −  = C A X X A X b min( ) 0 1 1 2 2  （14） 称（14）为问题的子规划。 显然，若（14）无可行解，则原问题（5）-（7）亦无可行解。若（14）有可行解，而 无最优解，则利用单纯形迭代，可找到（14）的一个基可行方向 j Y ，使得 ( − 1 1 )  0 j C  A Y ， 从而由（13）知  j  0 ，按照单纯形法，应选与  j 相应的变量  j 进基，算出  j 这列的系数 （因已经知道），得到主元列         = − 0 1 1 j j AY P B ，并实行通常的换基迭代（修正算法），则可得到 一个新的基 B 及对应的乘子。 若（14）有最优解 k x ，则对（14）的所有基可行方向 j Y ，均使得 ( − 1 1 )  0 j C  A Y （因这 时它的检验数  0 ）。从而由（13），（9）-（11）的检验数 = −( − 1 1 )  0 j  j C  A Y ，另方