由单纯形法知，对于(2.1.2)的当前基本可行解x°={x}，若其检验数≥0，(，)空格，则 x°={x}为(2.1.2)的最优解。否则，则用以下的闭回路调整法对原方案进行调整。先给出如下结论。 定理2.2.1设变量组 X3X2’…,X (2.2.2) 是(2.1.2)关于某个基B的基变量组。若x,是关于B的非基变量，则在变量组 术，XX…,Xi (2.2.3) 这存在唯一的闭回路。 证明：首先，由定理2.1.2知(2.2.2)不含闭回路，由(4)=r和定理2.1.1知(2.2.3)含闭回路。其次，假 若(2.2.3)含两条不同的闭回路，则由(2.2.2)不含闭回路知，这两条闭回路均含有x,从而得知P.可用两 种不同方式表示为P,P,…,P,的线性组合，由此知P,P,…,P,线性相关，再根据定理2.11 知X…,含闭回路，矛盾。 令r=min{U|(i,j)空格}，则x,进基。根据定理2.2.1知，当把x,加入原基变量组(2.2.2)后，可 找到唯一的闭回路，不妨设为 Xsm=xstXs2XsXsXsea 当将x由x=0增加到x=0时，为保证等式约束条件成立，由以下推论： x4=X增加8(9，)带正号)→x6减少0(S,4)带负号)→x增加0(S,2)带正号) →x4减少0(S2,)带负号)→…→x4增加0(S,4)带正号)→4减少0(，4)带负号) 因此为保证非负性，应取0=mi{xI亿，)带负号}兰x,于是xm出基，新的基本可行解为： xg+日，6，)：+ x{x-, 0,):- 9, otherwise 例2.2.6用闭回路调整法对表2.2.4所示的方案进行调整。 解：由表22.4知，24=min|(亿，)空格}，则x24进基。易得闭回路x24,x23,x3,x4,分别标上 正负号，得下标： 号 2 9 3 10 B B2 B3 Ba a; 3 11 3 10 0 A 4 3 7 1 2 9 2 8 -1A 3 十 4 10 5 -5 A3 6 9 10 12 b 3 6 5 6 20 表2.2.6对表2.2.4所示的方案的调整过程 99 由单纯形法知，对于(2.1.2)的当前基本可行解 0 0 { }ij x = x ，若其检验数 0, ( , ) ij r ij ≥ ∀ 空格，则 0 0 { }ij x = x 为(2.1.2)的最优解。否则，则用以下的闭回路调整法对原方案进行调整。先给出如下结论。 定理 2.2.1 设变量组 11 2 2 , ,, r r ij i j ij x x x " (2.2.2) 是(2.1.2)关于某个基 B 的基变量组。若 st x 是关于 B 的非基变量，则在变量组 st x , 11 2 2 , ,, r r ij i j ij x x x " (2.2.3) 这存在唯一的闭回路。 证明：首先，由定理 2.1.2 知(2.2.2)不含闭回路，由 r(A)=r 和定理 2.1.1 知(2.2.3)含闭回路。其次，假 若(2.2.3)含两条不同的闭回路，则由(2.2.2)不含闭回路知，这两条闭回路均含有 st x ，从而得知 st p 可用两 种不同方式表示为 11 2 2 , ,, r r ij i j ij pp p " 的线性组合，由此知 11 2 2 , ,, r r ij i j ij pp p " 线性相关，再根据定理 2.1.1 知 11 2 2 , ,, r r ij i j ij x x x " 含闭回路，矛盾。 令 min{ | ( , ) st ij r r ij = 空格}，则 st x 进基。根据定理 2.2.1 知，当把 st x 加入原基变量组(2.2.2)后，可 找到唯一的闭回路，不妨设为 11 12 2 2 2 3 1 1 , , , ,, , kk k kk s t st s t s t s t s t s t s t x xx x x x x x + = = " + - + - + - 当将 st x 由 0 st x =0 增加到 st x =θ 时，为保证等式约束条件成立，由以下推论： 1 1 s t st x = x 增加θ ( 1 1 (,) s t 带正号)→ 1 2 s t x 减少θ ( 1 2 (,) s t 带负号)→ 2 2 s t x 增加θ ( 2 2 (,) s t 带正号) → 1 3 s t x 减少θ ( 2 3 (,) s t 带负号)→ → " k k s t x 增加θ ((,) k k s t 带正号)→ k 1 s t x 减少θ ( 1 ( ,) k s t 带负号) 因此为保证非负性，应取θ = 0 min{ | ( , ) ij x i j 带负号} 0 pq  x ，于是 pq x 出基，新的基本可行解为： 0 0 0 0 , ( , ): , ( , ): , ij ij ij ij x ij x x ij x otherwise θ θ ⎧ + ∀ + ⎪⎪ ⇐ ⎨ −∀ − ⎪ ⎪⎩ 例2.2.6 用闭回路调整法对表 2.2.4 所示的方案进行调整。 解：由表 2.2.4 知， 24 min{ | ( , ) ij r r ij = 空格}，则 24 x 进基。易得闭回路 24 x , 23 x , 13 x , 14 x ，分别标上 正负号，得下标： vj uj 2 B1 9 B2 3 B3 10 B4 ai 0 A1 3 1 11 2 3 4 + 10 - 3 7 -1 A2 1 3 9 1 2 1 - 8 + -1 4 -5 A3 7 10 4 6 10 12 5 3 9 bj 3 6 5 6 20 表 2.2.6 对表 2.2.4 所示的方案的调整过程