第五章变量有上限的线性规划问题 §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 当Bk<0 Pa 显然,当d4=∞。以及风4≤0i=1…,m且对所有的<0,均有d=+∞时,由(6)可令 →+∞,从而Cx=∑Ca-49-∑→-∞,即此时原问题(1) (3)无最优解。 否则 Let=min(p,B >0-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,均有d=+∞时,原问题(1)—(3)无最优解 否则,选其它正检验数迭代,若已无其它正检验数,则当d(+∞时,转(ⅱ):当d=+∞ 时,转(i)。 (ⅱ)把x这一列的数(包括λ)全变号,对常数项列的a;减去dl,l=1…,m,该列 目标函数∫减去λd,并对变量x打撇,其余不变,继续迭代,直到求得最优表为止。设 最终单纯形表的解为x°(注意若出现(ⅱ),则x°第c个分量为松弛变量x的值)。转(B) (i)若存在某行6,满足A<0,且常数项a。≤d<+,则将该行非基变量系 数全变号,基变量打撇,常数项换成d一∝。然后以-β>0为主元实行 Gauss消元,继 续用单纯形法迭代求优,转(B)。否则,即对每一Ba<O,或者有d<ai,或者有部分 d,=+∞,转(B)之20。 (B)考察x0, 10若X°≤d,则结合(8)可立得原问题(1)--(3)的最优解。否则,转20 2设x>d1,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）无解