第六章分解算法 生产实际中遇到的线性规划问题常常是规模很大的,如果约束条件多到超过计算机容量 的程度,就会给求解造成困难。为了克服这一困难,对于大型问题,针对其具体结构,往往 可把它分解成几个较小问题来处理,这类方法称为分解算法。 §1分解定理 我们先介绍作为分解算法理论根据之一的分解定理。 对于线性规划问题 AX= b min CX 我们已定义可行解集D D={X|AX=b,X≥0} 相应地,定义集合D0 D={Y|AY=0,Y≥0} 以及集合D D={|AY=0,y≥0∑y=1 则易见是有界凸集,并且的极点个数有限,设它们为y,y2,…,y,常称为(1)的 基可行方向,而D中的元素则称为(1)的可行方向或极射向。 设B=(P,P2,…,Pn)是(1)的一个可行基,如果对某一非基变量x,其检验数x>0 系数≤0,=1…;m,令Y=(n,y2…y)2,满足 片=-B,=4,…m =0,k≠j,,…,mn 则Y≥0AY=yP+…+yP=-(BP+…+B1,P1)+P=-BBP+P=0,故 Y∈D,即为(1)的可行方向或极射向,并且Cy=-3<0,而=∑BY,便是(1)的 基可行方向,即y∈D。以上分析表明,若(1)的可行解无界,则它存在可行方向或极射 向 定理1如果D非空,则X∈D的充要条件是 x=∑aX+∑BF 这里x,=1…,s是D的极点,y,i=1,…l是(1)的基可行方向; a≥0,i=1…,S,∑a1=1,月≥0,=1,…,l 证明:充分性是显然的,故只需证必要性,任取X∈D,若X是D的极点,则(2)自 然成立,否则应有X,X(∈D,X(≠X2),使
126 第六章 分解算法 生产实际中遇到的线性规划问题常常是规模很大的，如果约束条件多到超过计算机容量 的程度，就会给求解造成困难。为了克服这一困难，对于大型问题，针对其具体结构，往往 可把它分解成几个较小问题来处理，这类方法称为分解算法。 §1 分解定理 我们先介绍作为分解算法理论根据之一的分解定理。 对于线性规划问题 = CX X AX b min 0 （1） 我们已定义可行解集 D： D = {X | AX = b, X 0} 相应地，定义集合 D0 { | 0, 0} D0 = Y AY = Y 以及集合 D0 { | 0, 0, 1} 1 0 = = = = n i i D Y AY Y y 则易见 D0 是有界凸集，并且 D0 的极点个数有限，设它们为 l Y ,Y , ,Y 1 2 ，常称为（1）的 基可行方向，而 D0 中的元素则称为（1）的可行方向或极射向。 设 ( , , , ) i1 i2 im B = P P P 是（1）的一个可行基，如果对某一非基变量 j x ，其检验数 j 0 ， 系数 ij m 0,i i , ,i = 1 ，令 T n Y ( y , y , , y ) = 1 2 ，满足 = = = − = k m j i ij m y k j i i y y i i i 0, , , , 1 , , , 1 1 则 0, ( ) 0 1 1 1 1 1 = + + = − + + + = − + = − i j j j j Y AY y P ynPn i jPi i P P BB P P m m ，故 Y D0 ，即为（1）的可行方向或极射向，并且 CY = − j 0 ，而 Y Y − ij = 1 1 ，便是（1）的 基可行方向，即 Y D0 。以上分析表明，若（1）的可行解无界，则它存在可行方向或极射 向。 定理 1 如果 D 非空，则 X D 的充要条件是 i l i i i S i X iX Y = = = + 1 1 (2) 这里 X i s i , = 1, , 是 D 的极点，y i，i=1，l 是（1）的基可行方向； i 0,i =1, ,S ， i l i S i i 1, 0, 1, , 1 = = = 证明：充分性是显然的，故只需证必要性，任取 X D ，若 X 是 D 的极点，则（2）自 然成立，否则应有 (1) (2) (1) (2) X , X D, X X ，使
00,g2=min!1x2>0再取Q=m,则000,取 x==a(x=.x),则X“的正分量个数不多于Pl,而x=x0+4-②x“,其中x 和x(4正分量的个数均不多于P-1,即比X少1 若x(3,x(4仍不是极点,则对之重复以上步骤,经有限步,必可将X表成 X aix+y (4) 其中a20,∑=1y∈D。故以下只需证Y=∑月y。若Y=0,只需取 B=0,i=1…,1。若y≠0,则B=∑y>0,取F=1y,则F∈。再注意到(4)对有界 集合D0亦成立,且此时y=0。(若D有界而Y≠0,则易证X+M∈D,令M→+∞。导致 D无界,矛盾)从而必有 ∑,≥0∑ 令月=丽,便有y=所-∑r,≥0,至此,定理获证 这样,由定理1,得到了(1)之可行解的一般表达式(2),且知若可行解集D有界, 其一般表达式为 X=>aX 其中a≥0.∑a=1x,=1…S,是D的极点,亦即X可表为极点的凸组合。 §2二分法 考虑如下线性规划问题 AX=b minf= CX (7) 这里4k是mxn矩阵,b是m维向量k=1,2 设D2={X|42X=b2,X≥0}
127 (1 ) 0 1 (1) (2) X = X + − X （3） 设 X 有 P 个正分量，则由（3）知，若 xj = 0 ，亦有 0 (1) (2) xj = xj = ，故 (1) (2) , j j x x 正分量不多 于 P 个，取 min{ | 0} (1) 1 (1) = i i i x x x Q ， min{ | 0} (2) 2 (2) = i i i x x x Q 再取 min{ , } Q = Q1 Q2 ，则 0 Q 1 ，不 妨设 Q = Q1 ，令 ( ) 1 (3) 1 (1) X QX Q X − − = ，则易见 X D (3) ，且其正分量个数不多于 P-1 个，而 (3) (1) X = (1−Q)X + QX 。若 (3) X X ，则 0, 0 (1) (3) (1) Y = X − X AY = ，且有 (3) (1) X = X + Y 。而 (3) X 的 正 分 量 个数 不 多于 P-1 个；若 (3) X X 不 成 立， 则 min{ | 0} 1, 3 0 (3) 3 (3) = x Q x x Q i i i , 取 ( ) 1 1 (3) 3 3 4 X Q X Q X − − = ，则 (4) X 的正分量个数不多于 P-1，而 (4) 3 (3) 3 X = Q X +（1− Q )X ，其中 (3) X 和 (4) X 正分量的个数均不多于 P-1，即比 X 少 1。 若 (3) X ， (4) X 仍不是极点，则对之重复以上步骤，经有限步，必可将 X 表成 X X Y I s I = i + =1 （4） 其 中 I 0 , = = S i i Y D 1 0 1, 。故以下只需证 = = l i i i Y y 1 。 若 Y=0 ，只需取 i l i = 0, = 1, , 。若 Y 0 ，则 0 1 = = n i i y ，取 Y Y 1 = ，则 Y D0 。再注意到（4）对有界 集合 D0 亦成立，且此时 Y = 0 。（若 D 有界而 Y≠0，则易证 X + MY D ，令 M → + 。导致 D 无界，矛盾）从而必有 , 0, 1 1 1 = = = = l i i i i l i Y iY 令 i = i ，便有 , 0 1 = = = i l i i Y Y iY ，至此，定理获证。 这样，由定理 1，得到了（1）之可行解的一般表达式（2），且知若可行解集 D 有界， 其一般表达式为 i S i X iX = = 1 其中 X i S i S i i i 0, 1, , 1, , 1 = = = ，是 D 的极点，亦即 X 可表为极点的凸组合。 §2 二分法 考虑如下线性规划问题 = = = min (7) 0 (6) (5) 2 2 1 1 f CX X A X b A X b 这里 AK 是 mk n 矩阵， k b 是 mk 维向量,k=1,2 设 { | , 0 2 D2 = X A2X = b X }
则由分解定理,对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)y10,按照单纯形法,应选与λ,相应的变量进基,算出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 ，另方
面若x使目标函数满足(C-x14)xk2x0,则对任意基可行解x (C-x14)x2-z0≥(C-141)xk-zo20 便有A1=-(C-丌1A1)X+丌0≤0 这说明已得到最优解。否则说明入>0,从而选a4为进基变量,算出4X4和主元列 R=B-4 r 实行换基迭代,可得一新基E及对应乘子z。 重复以上过程,即可求出(9)-(11)的解,再代入(8),便得(5)-(7)的解。 如果初始基是人造基,或(9)--(11)以典式形式给出,则乘子不必单独计算,就是 初始基变量的检验数。 §3p分法 若问题具有以下的结构形式 4X1+A2X2+…+AXP=b (15) B,X B2X2 (16) B X=6 mnf=C1X1+C2k2+…+CPX (17) 这里A,B都是矩阵,Xx,Cκ,b,b都是适当维数的向量,这种特殊的结构可理解 为,有一个总公司,下属p个子公司,每个子公司都有自己的决策变量(xk)和需要遵守 的约束(16)。同时各子公司之间还具有某种联系约束(15),目标是要使总公司的耗费(17) 最小。 记Dk={Xk14xk=b,Xk20,k=1…,P 利用分解定理,对Xx∈Dx,可写为 K+∑yFk B20∑ak=1 (19) xk是D2的极点,是基可行方向 将(18)代入(15)和(17)得: ∑∑(4X)a+∑∑(4H)y=b k=l i ∑ak=1k=1,…,P (21) ak20,k20
129 面若 k x 使目标函数满足 1 1 0 ( − ) k C A X ，则对任意基可行解 i X ( −1 1 ) − 0 ( −1 1 ) − 0 0 i k C A X C A X 便有 = −( − 1 1 ) + 0 0 i i C A X 这说明已得到最优解。否则说明 k 0 ，从而选 k 为进基变量，算出 k A1X 和主元列 = − 1 1 1 k k A x P B ，实行换基迭代，可得一新基 B 及对应乘子 。 重复以上过程，即可求出（9）-（11）的解，再代入（8），便得（5）---（7）的解。 如果初始基是人造基，或（9）---（11）以典式形式给出，则乘子不必单独计算，就是 初始基变量的检验数。 §3 p 分法 若问题具有以下的结构形式 A1X1 + A2X2 ++ APXP = b （15） = = = p BP X P b B X b B X b 2 2 2 1 1 1 （16） C X C X CPXP min f = 1 1 + 2 2 ++ （17） X1 , ,XP 0,P 1 这里 Ai Bi , 都是矩阵， XK ，CK ，b ， b k 都是适当维数的向量，这种特殊的结构可理解 为，有一个总公司，下属 p 个子公司，每个子公司都有自己的决策变量（ XK ）和需要遵守 的约束（16）。同时各子公司之间还具有某种联系约束（15），目标是要使总公司的耗费（17） 最小。 记 D X A X b X K k p k K K K K = { | = , 0}, = 1, , 利用分解定理，对 XK DK ，可写为 j K j kj i k i X K = kiX + Y （18） 0, 0, = 1 i ki kj ki （19） I X K 是 Dk 的极点， j Yk 是基可行方向。 将（18）代入（15）和（17）得： A X A Y b p k j kj j K k p k i ki i K k + = =1 =1 ( ) ( ) （20） k p i ki = 1, = 1,, （21） ki 0,kj 0
我们称(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 = (00 1 00) 据以上分析，不难写出分解算法的计算步骤。这里从略。 例 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）可使约束条件减
少一半(但变量不减少)。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 为止。 若rn,且秩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 为止。 若 rn，且秩 A 为 n，取 A 的一个 n 阶可逆子矩阵 A1 ，不妨设为前 n 行，令 A1X = u
便有 设能估计出AX的一个下界d,并不妨设d=0,(此假定,对许多实际问题例如资源利用 可题,是成立的,至于若d<0,可作变换v=u-d)便有 A24flu≤b2 0≤u≤b 这是一个含有m-n个普通约束,n个上限约束的问题,解之,并代入(32)若求得的X≥0, 则其即为最优解。否则,设负分量为xx,k=1,。t,则增加约束(或选其中之一,例 如绝对值最大的) (4u)≥0,k=1,…,t (34) 继续求解,直到求得的x≥0为止。 注意,若x20,则必有x≥0 (三)约束为不等式≥的情形: AX≥b (35) 任取A的r个线性无关的行,记为A=(B,N1),其中B1非奇异,仍令 4X-b=u≥0 记X ,可得 XB=B(u+b'-NXN)20 (37) 将(37)代入(35)其余约束条件A2X≥b2中,便得含有mr约束,n个变量u1≥0,X,≥0 的问题,解之,再代入(37),若x≥0,则已得最优解,若可行解无下界或xB中有 负分量,则于(37)中选适当约束加上去,继续求解,直到求得的xB≥0为止 例2用本节的方法解例1 (38) 2x,+x 代入其余约束后得
132 便有 X A u 1 1 − = (32) 设能估计出 A1X 的一个下界 d，并不妨设 d=0，（此假定，对许多实际问题例如资源利用 问题，是成立的，至于若 d<0，可作变换 v=u-d）便有 − 1 1 2 2 1 0 u b A A u b (33) 这是一个含有 m-n 个普通约束，n 个上限约束的问题，解之，并代入（32）若求得的 X 0 ， 则其即为最优解。否则，设负分量为 XK ，k=1，。。。t，则增加约束（或选其中之一，例 如绝对值最大的）： A u k t k ( ) 0, 1, , 1 1 − = (34) 继续求解，直到求得的 X 0 为止。 注意，若 0 1 1 − A ，则必有 X 0 。 （三） 约束为不等式 的情形： AX b (35) 任取 A 的 r 个线性无关的行，记为 ( , ) A1 = B1 N1 ，其中 B1 非奇异，仍令 0 1 A1X − b = ur (36) 记 = 1 1 N B X X X ，可得 ( ) 0 1 1 1 1 1 = 1 + − − XB B ur b N XN (37) 将（37）代入（35）其余约束条件 2 A2X b 中，便得含有 m-r 约束，n 个变量 ur 0 , 0 1 X N 的问题，解之，再代入（37），若 0 1 XB ，则已得最优解，若可行解无下界或 B1 X 中有 负分量，则于（37）中选适当约束加上去，继续求解，直到求得的 0 1 XB 为止 例 2 用本节的方法解例 1 令 + = + = 1 2 2 1 2 1 2 3 x x u x x u （38） 得 = − = − + 2 1 2 1 1 2 5 1 5 2 5 3 5 1 x u u x u u （39） 代入其余约束后得
n1+y2≤15 (40) 0≤1≤30,0≤l2≤20,0≤≤100sy2≤10 2 (40)是变量有上限的问题,引入松弛变量η,n2’做单纯形表,具体迭代过程如下 1/5·2 f|1/52/52 1|0 0 0 2 03 0 3/10°1/100 1/2 y|3/10-1/1011/2 1/2|18 f-2/5-1/50 0 10/3 1 0|15→5 1/30 2/34/3 1/3 1/35/3 0 5/3|55/3 0 05 2/3 1/3-110/3 于是得 55/3,u2=20y1=10,y2=5=-110/3 从而x1=25/3,x2=10/3,由于它们均非负,故已求得最优解 x1=25/3,X2=10/3,y1=10.y2=5 minf=-110/3 这比用P分法求解简单多了,但是,事情并非总是如此成功。因为最后求得的x可能 有负值,这就要增加约束迭代了,只有当(32)中的≥0,X才肯定不会出现负值。 不过事先很难保证这一点,一般4中负值元素不多并比较小(象本例那样)就不错了 当然从平均性态看来(32)中可有一半的分量非负,从而能减少其中的一半约束
133 − − − − + + + + 1 2 1 2 1 2 1 2 1 2 1 2 1 2 2 5 2 5 1 min 0 30,0 20,0 10,0 10 2 40 5 1 5 3 15 u u y y u u y y u u y y y y （40） （40）是变量有上限的问题，引入松弛变量 1 2 v ,v ，做单纯形表，具体迭代过程如下： 1u 2 u 1 y 2 y 1 v 2 v 1 v 2 v 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 1 v 2 v 0 0 1 1 1 0 3 1 10 5 0 5 15 200 f -1 0 -2 -1 0 -2 -80 1 v 2 u 0 0 1 1 1 0 3 -1 10* 5 0 5 15 180 f -1 0 -2 -1 0 -2 -80 1 v 1 y -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 1u 1 y 1 -1/3 0 -5/3 -10/3 5/3 0 0 -1 1 * 1 0 10 15 → 5 f 0 -1/3 0 -2/3 -4/3 -1/3 -40 1u 2 y 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 分法求解简单多了，但是，事情并非总是如此成功。因为最后求得的 Xi 可能 有负值，这就要增加约束迭代了，只有当（32）中的 0 1 1 − A ，Xi 才肯定不会出现负值。 不过事先很难保证这一点，一般 1 1 − A 中负值元素不多并比较小（象本例那样）就不错了。 当然从平均性态看来（32）中可有一半的分量非负，从而能减少其中的一半约束
