东北财经大学：《运筹学》课程教学资源（教案讲义）第二篇 线性规划 第五章 变量有上限的线性规划问题

第五章变量有上限的线性规划问题 §I以往算法介绍 实际遇到的线性规划问题,大多是具有上界限制的问题(既有上界限制,又有下界限 制的问题,容易化成只有上界限制的问题)。它的一般形式如下 AX=b (2) 此问题的解法,以往不外两种:一是用松弛变量把限制(3)化成等式约束,使之变成 具有(m+n)个约束方程,2n个变量的普通线性规划问题,然后求解。但这样做存储和计算都 增加很多,故不认为是一种好的方法。二是根据新的判别条件,把检验数分成两种不同情形, 有区别地作换基迭代。其优点是可以不扩大系数矩阵,算法具体步骤介绍如下: 引入松弛变量将(1) (3)化成 min f=CX AX= 6 X+y=d X≥0,y≥0 则(4)为(m+n)个约束,2n个变量的(LP)。假定(4)中不含多余的约束,即其基变 量的个数为(m+n)。其中,x与y1同时均为基变量时,其个数记为{S}。x为基变量而y为 非基变量时,其个数记为{S2}。x为非基变量(这时y必为基变量)时,其个数记为S},则 应有关系: 2{S1}+{S2}+{S3}=m+n S1}+{S2}+{S3}=n 从而有{S}=m,即x和y都为基变量时,其总个数分别恰为m,这说明基可行解X中 其余分量x或为0,或为d。据此可重新定义基可行解x°为:存在指标集合S=(1…m) 满足 10B=(,…P)满秩 2当jS时,x=0或者x=d 0≤X0≤d 同样,当j∈S时,x称为基变量;j∈R= FLiES}时,称x为非基变量。令R=R∪R2,当 j∈R时,x=0;当j∈R时,x=d。于是典式具有如下形式: x=a1-∑x-∑Bx,,i∈S 0≤x.≤d,i=1,2,,n ∫=∑Ca1-∑x1-∑x

117 第五章 变量有上限的线性规划问题 §1 以往算法介绍 实际遇到的线性规划问题，大多是具有上界限制的问题（既有上界限制，又有下界限 制的问题，容易化成只有上界限制的问题）。它的一般形式如下： 此问题的解法，以往不外两种：一是用松弛变量把限制（3）化成等式约束，使之变成 具有(m+n)个约束方程，2n 个变量的普通线性规划问题，然后求解。但这样做存储和计算都 增加很多，故不认为是一种好的方法。二是根据新的判别条件，把检验数分成两种不同情形， 有区别地作换基迭代。其优点是可以不扩大系数矩阵，算法具体步骤介绍如下： 引入松弛变量将（1）——（3）化成          + = = = 0, 0 min X Y X Y d AX b f CX （4） 则（4）为（m+n）个约束，2n 个变量的(LP)。假定（4）中不含多余的约束，即其基变 量的个数为（m+n）。其中， i x 与 i y 同时均为基变量时，其个数记为 { } S1 。 i x 为基变量而 i y 为 非基变量时,其个数记为 { } S2 。 i x 为非基变量（这时 i y 必为基变量）时，其个数记为 { } S3 ，则 应有关系： S S S n S S S m n + + = + + = + { } { } { } 2{ } { } { } 1 2 3 1 2 3 从而有 {S1 } = m ，即 i x 和 i y 都为基变量时，其总个数分别恰为 m，这说明基可行解 X 中 其余分量 j x 或为 0，或为 j d 。据此可重新定义基可行解 0 X 为：存在指标集合 ( , , ) 1 m S = i  i ， 满足 1 0 ( , , ) i1 im B = P  P 满秩 2 0 当 j  S 时， 0 0 X j = 或者 X j = d j 0 3 0  X  d 0 0 同样，当 j  S 时， j x 称为基变量； j  R = { j | j  S} 时，称 j x 为非基变量。令 R = R1  R2 ，当 R1 j  时, xj = 0 ；当 R2 j  时， j d j x = 。于是典式具有如下形式：           = − −   = = − −  1 2 1 2 (1) (2) 0 1 2 , j R j j i S j R i i j j i i j R ij j j R i i ij j f C x x x d i n x x x i S       ， ，，， (5)        = = 0 (3) (2) min (1) X d AX b f CX

据典式(5)易见:若对可行解x有≤0j∈R:420,J∈R2,则对任意可行解x有 ∫=CX=∑Ca1-∑x-∑积x2∑C1-∑码d 可见x°是最优解。 不然,若有某艰>0,K∈R1。则令=Q≥0,其余不变,代入典式(5)得 d,i∈R ∫=CX0-eQ 可见,为保证可行性,Q应满足 0≤Q≤dk ≤x0-BQ≤d1,i∈S 它等价于 0≤Q≤dk O≤ (6) B 当Bk0-x (若所有A≤0,置Qk=+∞) 1Ba<0} (若所有Ak≥0,则置SA=+) 取 xk=0= min(@ek, S,, dk ①若Q=Q4,则以A为主元,实行高斯消元。这时x进基,x离基,x2=0故e∈R。 ②若Q=SA,则于x所在行的常数项减d后,以RA为主元实行高斯 Gauss消元。这时

118 据典式（5）易见；若对可行解 0 X 有 1 (1)  j  0, j  R ； 2 (2)  j  0, j  R ，则对任意可行解 1 X 有           = = − −  − = i S j R i i j j j R j j i S j R f CX Ci i j x j x C d CX 1 2 2 1 (1) 1 (2) 1 (2) 0      可见 0 X 是最优解。 不然，若有某 1 (1) K  0,K  R 。则令 0 1 xk = Q  ，其余不变，代入典式（5）得 , , 1 0 xi = xi − ikQ i  S x i R i k i = 0,  1 ,  1 2 1 xi = di，i  R f CX k Q 0 (1) = −  可见，为保证可行性，Q 应满足 0  Q  dk 0  xi − ikQ  di ,i  S 0  它等价于 0  Q  dk ik i x Q  0  ，当 ik  0 （6） , 0 ik i i d x Q −  −  当  ik  0 显然，当 dk =  。以及 ik  0,i =1,  ,m 且对所有的 ik  0 ，均有 di = + 时，由（6）可令 Q → + ，从而     = − − → − i S j R CX Ci i kQ jd j 2 1    ，即此时原问题（1）——（3）无最优解。 否则，令 ek e ik ik i ek x x Q    0 0 = min{ ,  0} = （若所有 ik  0 ，置 Qek = + ） rk r r ik ik i i d rk d x d x S i    − −  = − − = + 0 0 min { | 0} （若所有 ik  0 ，则置 Srk = + ） 取 min{ , , } 1 k Q Qek Srk dk x = = ①若 Q = Qek ，则以 ek 为主元，实行高斯消元。这时 k x 进基， e x 离基， 0 1 xe = 故 R1 e 。 ②若 Q = Srk ，则于 r x 所在行的常数项减 r d 后，以 rk 为主元实行高斯 Gauss 消元。这时

x进基,x离基,x=d故r∈R2 ③若Q=d4,则于常数项列减Bdn,i=1,…m,目标函数减λdk,这时xk仍为非基 变量,但x=d,故k∈R 同样,若有x2<0,k∈R则令x=4-Q≥0),其余不变,代入典式得: x=x+BA9,i∈S x=0,∈R1 x=d,i∈R2 f=Cx°+22Q 则Q满足 0≤dk-Q≤dk 0≤x+BAQ≤d 它等价于 0≤Q≤dk Q≤ 当<0 B -xo k 1B<0} (若所有Bk≥0,置g=+∞) (若所有4≤0,则置SA=+) 取 xk=dk-o=dk-minteek, Sr, d,i ④若Q=Q,则以A为主元实行 Gauss消元,然后于新基变量x所在行常数项加dk, 此时x离基,x=0故e∈R ⑤若Q=Sk,则于原基变量x,所在行的常数项减d,然后以风为主元实行 Gauss消元, 最后于新基变量x这行的常数项上加dk,此时x=d,故r∈R2

119 k x 进基， r x 离基， r dr x = 1 故 R2 r  ③若 Q = dk ，则于常数项列减  ik r d ，i=1，m， 目标函数减 k dk ，这时 k x 仍为非基 变量，但 x 1 k = dk， 故 k  R2 。 同样，若有 0 (2) k  ， R2 k  则令 ( 0) 1 xk = dk − Q Q  ，其余不变，代入典式得： , , 1 0 xi = xi +  ikQ i  S 1 1 xi = 0,i  R x d i R i k i = i ,  2 ,  1 f CX k Q 0 (2) = +  则 Q 满足 0  dk −Q  dk i ikQ di  x +   0 0 它等价于 0  Q  dk ik i x Q −   0 ，当  ik  0 （7） , 0 ik i i d x Q  −  当 ik  0 令 ek e ik ik i ek x x Q    −  = − = 0 0 min{ | 0} （若所有  ik  0 ，置 Qek = + ） rk r r ik ik i i d rk d x d x S i    0 0 min { | 0} −  = − = + （若所有 ik  0 ，则置 Srk = + ） 取 min{ , , } 1 k dk Q dk Qek Srk dk x = − = − ④若 Q = Qek ，则以 ek 为主元实行 Gauss 消元，然后于新基变量 k x 所在行常数项加 k d ， 此时 e x 离基， 0 1 xe = 故 R1 e ⑤若 Q = Srk ，则于原基变量 r x 所在行的常数项减 r d ，然后以 rk 为主元实行 Gauss 消元， 最后于新基变量 k x 这行的常数项上加 d k ，此时 1 r x = r d ，故 R2 r 

⑥若Q=d,则于常数列加风41=1…,m,目标函数加4。此时x仍为非基变量 故k∈R 根据以上分析,可以给出具体迭代步骤,这里略去(详见[13])。 容易看出,若问题是非退化的,目标函数在迭代中严格下降,故有限步收敛。寻找初始 基可行解的方法以往由两种 (一)增加人工变量x1=(Xn,…,X),作 AX+IX= b x,X2≥0 0≤X≤d,X无上界 Z=min(Xm+1+…+Xnm) 这个问题有明显的基可行解: =0,X=b 然后运用两阶段法,或者证明原问题(1)——(3)无解。或者得到它的一个基可行解 (二)利用通常的单纯形法,求解 mn{x1|AX=b,X≥0)} 若所求得的解x°,使x>d(或者根本无可行解),则问题(1)——(3)也无可行解。 相反,记J=10sX≤d,j=1…,n 1°、若广={1…,,则已获问题(1)——(3)的基可行解。相反,任选igJ,利用前 面介绍的算法,继续求解问题: nmn(x1AX=b0≤x≤d,j∈J:0≤x≤+ajEJ 设求得的解为F 2°、若元>d,则问题无可行解。相反,修改=切105元≤d1,J=1…n,转步骤1° §2一种新的解法 前面介绍的方法,虽说不必扩大系数矩阵。但我们已经看到离基变量总共有六种选择, 这时程序的复杂性和每步迭代的计算量都增加,而且寻找初始基可行解也不容易,下面我们 给出一种解法,这种解法也不用扩大系数矩阵,而且迭代程序还十分简单,几与没有限制(3) 的情形相同。方法的关键在于充分利用(3)的特殊性。 显然,如用x′表示x的松弛变量,则(3)化成 d,,j n 这样亦可形式地把x看成x的松弛变量,从而有(x)=x,并且x与x显然有相同的限 制(3),知道了x,x可立即由(8)算出,反之亦然。 有了以上说明,新算法的说明可表述如下

120 ⑥若 Q = dk ，则于常数列加 ikdk ,i =1,  ,m ，目标函数加 k dk (2)  。此时 k x 仍为非基变量 0 1 xk = ，故 R1 k  根据以上分析，可以给出具体迭代步骤，这里略去（详见[13]）。 容易看出，若问题是非退化的，目标函数在迭代中严格下降，故有限步收敛。寻找初始 基可行解的方法以往由两种： （一） 增加人工变量 ( , , ) Xt  Xn+1  Xn+m ，作 min( ) 0 , , 0 n 1 n m t t t Z X X X d X X X AX IX b = + + + +    + =  无上界 这个问题有明显的基可行解： X = Xt = b 0 0 0, 然后运用两阶段法，或者证明原问题（1）——（3）无解。或者得到它的一个基可行解。 （二） 利用通常的单纯形法，求解 min{ | , 0} x1 AX = b X  若所求得的解 0 X ，使 1 0 X1  d （或者根本无可行解），则问题（1）——（3）也无可行解。 相反，记 { | 0 , 1, , } * 0 J = j  X j  d j j =  n 1 0、若 {1, , } * J =  n ，则已获问题（1）——（3）的基可行解。相反，任选 * i  J ，利用前 面介绍的算法，继续求解问题： min{ | ,0 , ;0 , } * * x AX b x d j J x j J i =  j  j   j  +   设求得的解为 X 2 0、若 i di x  ，则问题无可行解。相反，修改 { | 0 , 1, , } * J = j  xj  d j j =  n ，转步骤 1 0 §2 一种新的解法 前面介绍的方法，虽说不必扩大系数矩阵。但我们已经看到离基变量总共有六种选择， 这时程序的复杂性和每步迭代的计算量都增加，而且寻找初始基可行解也不容易，下面我们 给出一种解法，这种解法也不用扩大系数矩阵，而且迭代程序还十分简单，几与没有限制（3） 的情形相同。方法的关键在于充分利用（3）的特殊性。 显然，如用 x j ′表示 j x 的松弛变量，则（3）化成 x j + x j = d j , j =1,  ,n ， （8） 这样亦可形式地把 j x 看成 ， j x 的松弛变量，从而有 j j x = x ， ， ( ) ，并且 ， j x 与 j x 显然有相同的限 制（3），知道了 ， j x ， j x 可立即由（8）算出，反之亦然。 有了以上说明，新算法的说明可表述如下

A)不考虑约束(3),用单纯形法对问题(1)—(2)实行寻优迭代,其间如单纯形表 出现某检验数λ2>0,而该列变量x2的系数B≤0=1…,m,设与此对应的可行解为X,则有 (i)当d=+,且对所有风0为主元实行 Gauss消元,继 续用单纯形法迭代求优,转(B)。否则,即对每一Bad1,r=1…,t,取 max(x -d,)=x-d 然后于最终单纯形表里将变量x这列唯一的1变号,相应常数项变成x=a1-d,并对 变量x打撇,其余不变。这时若B≤0 ,n,则原问题(1)一(3)无解,终 止。若不然,对无正检验数的情形,用对偶单纯形法迭代求优(若无最优解,则原问题(1) (3)亦然):设为x2,对x,重复(B)以下过程。对由(ⅲi)转来的有正检验数情形 可实行日一处理1(即将ik行的-一倍加于检验数行),然后实行单纯形迭代(有正检验 数时)或对偶单纯形迭代(无正检验数时),直到求得最优解(或断定无解),设为X,对 之重复(B)以下过程。 理论分析 现对上述程序的正确性加以说明解释 首先,步骤(A)中(i)的判断成立,我们有 定理如表1所示,设检验数λ2>0,该列系数。≤O,i=1…,m,如果d=+∞,且 对所有B<0,均有d=+∞,则原问题(1)一(3)无解 121

121 A）不考虑约束（3），用单纯形法对问题（1）—（2）实行寻优迭代，其间如单纯形表 出现某检验数 e  0 ，而该列变量 e x 的系数 ie  0,i =1,  ,m ，设与此对应的可行解为 X，则有 （ⅰ）当 de = + ，且对所有 ie  0 ，均有 di = + 时，原问题（1）—（3）无最优解； 否则，选其它正检验数迭代，若已无其它正检验数，则当 de〈+  时，转（ⅱ）；当 de=+  时，转（ⅲ）。 （ⅱ）把 e x 这一列的数（包括 e ）全变号，对常数项列的  i 减去 iede ,i =1,  ,m ，该列 目标函数 0 f 减去 ede ，并对变量 e x 打撇，其余不变，继续迭代，直到求得最优表为止。设 最终单纯形表的解为 0 X （注意若出现（ⅱ），则 0 X 第 e 个分量为松弛变量 ， e x 的值）。转（B）。 （ⅲ）若存在某行 0 i ，满足 0 0 i e  ，且常数项   + 0 0 i  i d ，则将该行非基变量系 数全变号，基变量打撇，常数项换成 0 0 di − i 。然后以- i e0  >0 为主元实行 Gauss 消元，继 续用单纯形法迭代求优，转（B）。否则，即对每一  ie  0， 或者有 di<  i，或者有部分 di = + ，转（B）之 2 0。 （B）考察 0 X ， 1 0 若 X  d 0 ，则结合（8）可立得原问题（1）---（3）的最优解。否则，转 2 0 2 0 设 x d r t r r i i , 1, , 0  =  ，取 r r k k i i i i r t x − d = x − d   0 0 1 max{ } (9) 然后于最终单纯形表里将变量 k i x 这列唯一的 1 变号，相应常数项变成 0 k i x = k  i － k i d ，并对 变量 k i x 打撇，其余不变。这时若  i k j  0， j=1，，n ，则原问题（1）—（3）无解，终 止。若不然，对无正检验数的情形，用对偶单纯形法迭代求优（若无最优解，则原问题（1） ---（3）亦然）；设为 1 X ，对 1 X ，重复（B）以下过程。对由（ⅲ）转来的有正检验数情形 可实行  − 处理[20]（即将 ik 行的- i e e k   倍加于检验数行），然后实行单纯形迭代（有正检验 数时）或对偶单纯形迭代（无正检验数时），直到求得最优解（或断定无解），设为 X1，对 之重复（B）以下过程。 理论分析 现对上述程序的正确性加以说明解释。 首先，步骤（A）中（ⅰ）的判断成立，我们有 定理 如表 1 所示，设检验数 e  0,该列系数 0,i 1, ,m,  ie  =  如果 de=+∞，且 对所有 ie 均有di   0, =+ , 则原问题（1）—（3）无解

证明,设相应于(1)--(2)的典式 ∑x,=1 满足定理所述之条件。若由(10)确定的基可行解还满足(3),则它亦是(1)-(3)的可 行解。令x=M,其余非基变量仍为0,可解得 x,=a-Bex=a-pe i=l,,m 因风≤0;=1…m,故它构成(1)--(2)的一个可行解,又因d=+0,以及当Bd,将限制约束 x+x'=d 加到(10)中,由假定应有B=0(因β<0时,x无限制),故单纯形表具如下形式 XI B B 0 0 0 d (表1) 将x行的(1)倍加入x行中,并在x行中引入人工基变量Y6及正参数M。则目标函数 =-何变成厂=”-2x+M…,消掉)一列中的M后,则单纯形表具有 如下形式: x y B41…B4

122 证明，设相应于（1）---（2）的典式 x x i m j R i i ij j = −  , = 1,,    (10)   = − j R j j f f  x 0 满足定理所述之条件。若由（10）确定的基可行解还满足（3），则它亦是（1）-（3）的可 行解。令 xe = M ，其余非基变量仍为 0，可解得： xi =i − ie x =i − ieM i =1,  ,m 因 ie  0,i =1,  ,m ，故它构成（1）---（2）的一个可行解，又因 de = + ，以及当  ie  0 时， di = + 故知此可行解亦满足（3）。从而是（1）---（3）的一个可行解，它使目标函数取 值 f − eM 0 ，故当 M → + 时，目标函数值在可行解集合上无下界，因此问题（1）---（3） 无最优解。 若由（10）确定的基可行解不满足限制（3），故必有某常数项 0 0  i  di ，将限制约束 0 0 0 i i di x + x = ， 加到（10）中，由假定应有 0 0  i e = (因 0 0  i e  时， e x 无限制），故单纯形表具如下形式： ， 1 0 0 e i n i x  x  x  x  x ， 0 0 i i x x  0 0 ... 1 0 1 1 0 01 0 0      i   i e    i n       d i0   f 1  e  0 n  0 0 f （表 1） 将 ， 0 i x 行的（-1）倍加入 0 i x 行中，并在 0 i x 行中引入人工基变量 0 Yi 及正参数 M。则目标函数   = − j R j j f f  x 0 变成 0 0 i j R f = f − j x j + MY   ：，消掉 0 Yi 一列中的-M 后，则单纯形表具有 如下形式：  0 i y  .     ... 0 1 01 0 0  i   i e    i n − 1  0 0 i  i − d 0 0 0 1 i e i n i x x x x x y    

01 +风M…2…0…+BM-M0f°+M(an-d) (表2) 对(10)中不满足限制(3)的变量均照此办理,则不难看出处理后的x。一列数根本没变 即仍有λ>0,B≤0,i=1…(m+n),这说明所得辅助问题无最优解,故原问题(1)-(3) 无最优解 证毕 为了说明(A)之(ⅱ)处理正确,考虑增加约束 这时的单纯形表可设为 d (表3) 以Bm+=1为主元,迭代一次得 An xe B1 B, d 0 B B Bed d 结果x进基,x离基,此时x=d,x=O恰是新增约束(11)所表达的内容,现若再去 掉新增约束这一行,则表4x一列诸值恰好等于表1中x列诸值变号,而常数项列由a变成

123 0 i x 0  ... 0 ...1 0 1 0 0 i d f 1 +  i0 M e 0n +  i0nM − M 0 f 0 + M（i0 − di0 ） (表 2) 对（10）中不满足限制（3）的变量均照此办理，则不难看出处理后的 e x 一列数根本没变， 即仍有 e  0, 0,i 1, ,(m n) ie  =  + ，这说明所得辅助问题无最优解，故原问题（1）---（3） 无最优解。 证毕 为了说明（A）之（ⅱ）处理正确，考虑增加约束 e e de x + x  = (11) 这时的单纯形表可设为 1 x  m x e x  n x ， e x 1 x   xm ， e x 1  0 1e  1n 0    0  1  me   mn 0 0  0 1*  0 1 1   m d e f 0  0 e  n 0 0 f (表 3) 以  m+1e = 1 为主元，迭代一次得 1 x  m x e x  n x ， e x 1 x  m x e x 1  0 0  1n - 1e    0  1 0   mn …-  me 0  0 1*  0 1 1 - 1ede   m -  mede d e f 0  … 0 0  …n -  e ede f −  0 (表 4) 结果 e x 进基， e x  离基，此时 xe = de，x ， e = 0， 恰是新增约束（11）所表达的内容，现若再去 掉新增约束这一行，则表 4 e x  一列诸值恰好等于表 1 中 e x 列诸值变号，而常数项列由 i 变成

a-Bd2i=1…,m,目标函数由f变成∫0-d,这时表4中x这列已全为0,可去之,今 用相应松弛变量x那一列取代它的位置。不去不添两方便,于是去掉新约束行(11)的表4 可简化为: A Piede Brd 0 f-Ad (表5) 表5中x是非基变量,它等于零,再由(11),x=d,可见表5与表4完全等价。这正 是(A)之(i)所云者。 类似的,对表1增加约束: +x:=d (12) 可说明(ⅲ)的简化处理正确 当出现(B)之20时,仍把问题看成在前一步最优解的基础上增加一个新限制 x:+x=d (13) 继之用单纯形法或对偶单纯形法处理,并且基于前面所述类似理由,亦不必增加新的行和列 及其间的迭代过程便简化成如20所说的样 注意到采取上述处理的结果,对于非退化情形目标函数是严格上升的,而问题(1)- (3)的正则解又是有限的,故迭代必终止于有限步 亦可按每步迭代使目标函数增值最大的原则选择20中的变量,以便减少迭代次数。 综上所述,新的算法是基于这样一种思想:首先找出无上限约束(3)的规划问题(1) (2)的最优解(问题(1)一(2)通常称为(1)一(3)的松弛问题),这当然是很简便 的,即使出现(A)之(ⅱ),也只需改动一下单纯形表中的个别数据,然后看此解是否满 足(3),若满足,则其即为(1) (3)的最优解,若不然,则它实质是(1)---(3) 的一个正则解。而步骤(B)实质就是进行对偶单纯形迭代,这样整个迭代步骤也就清楚了 (即对偶单纯形法的迭代步数),其特点是,初始正则解用普通单纯形法求得,从而避免了 以往求初始的正则解带来的麻烦,也避免引进参数,而迭代中又不必扩大系数矩阵,必要时, 除对单纯形表做个别改动外,与原来的单纯形法和对偶单纯形法处理无异。此外,由于本方 法只涉及(3)中起作用限制,剔除了多余的约束,故实现了最大限度的简化,如将它与1 中介绍的算法对照、比较。易见§1所述min{*,SA,d}的三种可能值,在我们这里都至多由 于增添一个约束而带来的单纯形表的小小变动而加以解决了 例 124

124 i − iede ,i =1,  ,m ，目标函数由 0 f 变成 ede f −  0 ，这时表 4 中 e x 这列已全为 0，可去之，今 用相应松弛变量 e x  那一列取代它的位置。不去不添两方便，于是去掉新约束行（11）的表 4 可简化为： 1 x  m x e x   n x 1 x  m x 1  0 - 1  1n    0  1 -  me   mn 1 - 1ede   m -  mdm f 0  0 - e  n 0 f - ede （表 5） 表 5 中 ， e x 是非基变量，它等于零，再由（11）， xe = de， 可见表 5 与表 4 完全等价。这正 是（A）之（ⅱ）所云者。 类似的，对表 1 增加约束： 0 0 0 , i i di x + x = (12) 可说明(ⅲ)的简化处理正确。 当出现（B）之 2 0 时，仍把问题看成在前一步最优解的基础上增加一个新限制 k k k j j d j x + x  = （13） 继之用单纯形法或对偶单纯形法处理，并且基于前面所述类似理由，亦不必增加新的行和列 及其间的迭代过程便简化成如 2 0 所说的样子。 注意到采取上述处理的结果，对于非退化情形目标函数是严格上升的，而问题（1）--- （3）的正则解又是有限的，故迭代必终止于有限步。 亦可按每步迭代使目标函数增值最大的原则选择 2 0 中的变量，以便减少迭代次数。 综上所述，新的算法是基于这样一种思想：首先找出无上限约束（3）的规划问题（1） -（2）的最优解（问题（1）—（2）通常称为（1）—（3）的松弛问题），这当然是很简便 的，即使出现（A）之（ⅱ），也只需改动一下单纯形表中的个别数据，然后看此解是否满 足（3），若满足，则其即为（1）——（3）的最优解，若不然，则它实质是（1）----（3） 的一个正则解。而步骤（B）实质就是进行对偶单纯形迭代，这样整个迭代步骤也就清楚了 （即对偶单纯形法的迭代步数），其特点是，初始正则解用普通单纯形法求得，从而避免了 以往求初始的正则解带来的麻烦，也避免引进参数，而迭代中又不必扩大系数矩阵，必要时， 除对单纯形表做个别改动外，与原来的单纯形法和对偶单纯形法处理无异。此外，由于本方 法只涉及（3）中起作用限制，剔除了多余的约束，故实现了最大限度的简化，如将它与 1 中介绍的算法对照、比较。易见§1 所述 min{ , , } Qek Srk dk 的三种可能值，在我们这里都至多由 于增添一个约束而带来的单纯形表的小小变动而加以解决了。 例

x2) 初始表及迭代过程如下 0 0 5 0 0 0 -1/6 0 X 0 1/67/2 /3 1/3|-7 -1/4 超上限) 0 2 1/2 1/4114 0 0 1/2 31/4 0 14|14(实行(B)之2) 00 14|114 1/2 -1/4 31/4 0 0 0 30 由最终表知x1=17/6,x2=0=x2=2,x=1/6x4=5/6x5=0,最优值f23/3 作为练习,请试用1的方法解此例 125

125 0 3,0 2, 2, ,5 6 2 21 0 5 min (2 ) 1 2 1 2 5 1 2 4 1 2 3 1 2     =  + + = − + + = + + = = − + x x i x x x x x x x x x f x x 初始表及迭代过程如下： 由最终表知 x1=17/6,x2 ， =0  x2=2,x3=1/6,x4=5/6,x5=0，最优值 f=-23/3。 作为练习，请试用 1 的方法解此例。 x1 x2 x3 x4 x5 x3 x4 x5 1 1 1 0 0 -1 1 0 1 0 6 * 2 0 0 1 5 0 21 f 2 1 0 0 0 0 x3 x4 x1 0 2/3* 1 0 -1/6 0 4/3 0 1 1/6 1 1/3 0 0 1/6 3/2 7/2 7/2 f 0 1/3 0 0 -1/3 -7 x2 x4 x1 0 1 3/2 0 -1/4 0 0 -2 1 1/2 1 0 -1/2 0 1/4 9/4 （超上限） 1/2 11/4 0 0 -1/2 0 -1/4 -31/4 x2 ， x4 x1 0 -1 3/2* 0 -1/4 0 0 -2 1 1/2 1 0 -1/2 0 1/4 1/4 （实行（B）之 2 0） 1/2 11/4 0 0 -1/2 0 -1/4 -31/4 x3 x4 x1 0 -2/3 1 0 -1/6 0 -4/3 0 1 1/6 1 -1/3 0 0 1/6 1/6 5/6 17/6 f 0 -1/3 0 0 -1/3 -23/3