第二章单纯形法 由上一章定理5,线性规划问题的最优解可以只限于在基可行解中去挑选。由于基可行 解有限,故原则上可采用枚举法。但从算法的角度看这显然不是简便有效的。当m、n较大 时,根本行不通。事实上m、n在100左右的线性规划问题属于小型的。而此时基可行解的数 目可能多达230(m=50,n=100)以上故必须寻找有效算法。 Danzig首先提出的单纯形算法 被实践证明是异常有效和普遍适用的。其基本思想是从一个基可行解出发,寻找一个比之更 “好”的。由此不断改进最后得到最优解 单纯形法可分为两阶段。第一阶段是寻求第一个基可行解。第二阶段是通过换基迭代 寻找最优解。下面先介绍第二阶段,然后再讲第一阶段。 §1典式及单纯形表 (一)典式 考虑标准形式的线性规划 AX=b LPX≥0 min f= CX 设已知一个可行基B是m阶单位矩阵。不失一般性可假定B位于A的前m列。这时约束 方程(1)的形式为 X Pu B, x=b +B2 +B,nx,=b2 Bmxm++…+Bmxn=b 其中b≥0,1=1…,m,显然对应基可行解X=(b1…bn,0,…0),将 x=b-∑Bx1,=1…m代入目标函数(3),得 j=m+1 CX=∑cx=∑c(b-∑周x)+∑c c-∑②cB-c)x B-e (5)
63 第二章 单纯形法 由上一章定理 5，线性规划问题的最优解可以只限于在基可行解中去挑选。由于基可行 解有限,故原则上可采用枚举法。但从算法的角度看,这显然不是简便有效的。当 m、n 较大 时,根本行不通。事实上 m、n 在 100 左右的线性规划问题属于小型的。而此时基可行解的数 目可能多达 2 50 （m=50,n=100）以上,故必须寻找有效算法。Danzig 首先提出的单纯形算法 被实践证明是异常有效和普遍适用的。其基本思想是从一个基可行解出发,寻找一个比之更 “好”的。由此不断改进,最后得到最优解。 单纯形法可分为两阶段。第一阶段是寻求第一个基可行解。第二阶段是通过换基迭代 寻找最优解。下面先介绍第二阶段，然后再讲第一阶段。 §1 典式及单纯形表 （一） 典式 考虑标准形式的线性规划 (1) 0 (2) min (3) AX b LP X f CX = = 设已知一个可行基 B 是 m 阶单位矩阵。不失一般性,可假定 B 位于 A 的前 m 列。这时约束 方程（1）的形式为 1 1 1 1 1 1 2 2 1 1 2 2 1 1 m m n n m m n n m mm m mn n m x x x b x x x b x x x b + + + + + + + + + = + + + = + + + = 其 中 0, 1, , i b i m = ， 显 然 对 应 基 可 行 解 1 ( , , ,0, ,0)T X b b = m ， 将 1 , 1, , n i i ij j j m x b x i m = + = − = 代入目标函数（3）,得 1 1 1 1 1 1 1 ( ) ( ) n m n n j j i i ij j j j j i j m j m m n m i i i ij j j i j m i CX c x c b x c x c b c c x = = = + = + = = + = = = − + = − − 记 1 m i i i f c b = = （4） 1 m j i ij j i c c = = − （5）
则原问题(LP)变为 A ≥0,j=1, ∑ 这种形式叫作线性规划问题的典式。它显然与(LP)(1)-(3)等价。 对于任何一可行基B,亦可把(LP)化为典式形式。化法如下: 仍设B位于A的前m列,即A=(B、N)。其中B=(,…,Pn),N=(Pm+1…,P) 相应地向量X和C可分为X= r C=(CB,CN 于是 (1)可写成 (B,M/ =BX+NX=b X=B6-B- NX x=a1-∑Bx,=1 a1 Blm+1…Bn 其中Bb=:,B1 Bm+t…B 把(6)代入目标函数(3)。得 CX=(CR CIx/88-b-(CPB-IN-CN)X, (7) ∑①c月-cx,=f-∑ j=m+I 其中仍为基可行解x对应的目标函数值(x=(a1,…,am0…0))。仍为目标 函数中非基变量x系数之相反数。这样我们得到一般典式的矩阵形式
64 则原问题（LP）变为 （* ） 1 1 , 1, , 0, 1, , min n i i ij j j m j n j j j m x b x i m x j n f f x = + = + = − = = = − 这种形式叫作线性规划问题的典式。它显然与（LP）(1)-(3)等价。 对于任何一可行基 B，亦可把（LP）化为典式形式。化法如下： 仍设 B 位于 A 的前 m 列，即 A=（B、N）。其中 B= 1 ( , , ) P P m ， 1 ( , , ) N P P = m n + 。 相应地向量 X 和 C 可分为 , ( , ) B B N N X X C C C X = = 。于是 （1）可写成 1 1 ( , ) B B N N B N X B N BX NX b X X B b B NX − − = + = = − （6） 或 1 , 1, , n i i ij j j m x x i m = + = − = (6) 其中 1 1 1 1 1 1 1 , m n m mm mn B b B N + − − + = = 把（6）代入目标函数（3）。得 1 1 ( , ) ( ) B B N B B N N N X CX C C C B b C B N C X X − − = = − − （7） 即 1 1 1 1 ( ) m n m n i i i ij j j j j i j m i j m f c c c x f x = = + = = + = − − = − （7） ' 其中 f 仍为基可行解 x 对应的目标函数值 1 ( ( , , ,0, ,0) ) T X = m 。 j 仍为目标 函数中非基变量 j x 系数之相反数。这样我们得到一般典式的矩阵形式：
X=B6-B-NX X≥0 ninf=CrB(CrB (二)单纯形表 设对某初始可行基B,已求得(LP)的典式为 x1= Bix,i=l, x,≥0,j=1…,n (9) x 为了计算方便,将式中的系数分离出来,象形成增广矩阵那样列成表格,称为对应于 基B的初始单纯形表 基变量xx2 x B1m+1…B1 x2 0 B2m+…B2 0 B Bn 0 0 0 n 注意表中最后一行实际上是等式:f=f0∑x1→f+∑x=f的简化和变形。 我们将看到这样写不会影响以后的运算,反而带来很多方便。 上述单纯形表又可写成矩阵形式: 基变量 B N CoBN-O 因BA=B(B,N)=(1,BN B'A-C=CBB(B, N)-(CB, CN)=(0, CBBN-CN) (10) 故这个表又可进一步简写为
65 ** 1 1 1 1 0 min ( ) B N B B N N X B b B NX X f C B b C B N C X − − − − = − = − − （8） （二） 单纯形表 设对某初始可行基 B，已求得（LP）的典式为 ： 1 1 , 1, , 0, 1, , min n i i ij j j m j n j j j m x x i m x j n f f x = + = + = − = = = − （9） 为了计算方便，将式中的系数分离出来，象形成增广矩阵那样列成表格，称为对应于 基 B 的初始单纯形表： 基变量 1 x 2 x m x m 1 x + n x 1 x 2 x m x 1 0 0 1m+1 1n 0 1 0 2m 1 + 2n 0 0 1 mm+1 mn 1 2 m f 0 0 0 m+1 n f 注意表中最后一行实际上是等式： 0 0 f f x f x f = − j j → + j j = 的简化和变形。 我们将看到这样写不会影响以后的运算，反而带来很多方便。 上述单纯形表又可写成矩阵形式： 基变量 1 x 2 x m x m 1 x + n x 1 x 2 x m x I B −1 N 1 B b− f 0 CB B N −CN −1 CB 1 B b− 因 1 1 1 B A B B N I B N ( , ) ( , ) − − − = = CB 1 B A− - 1 1 ( , ) ( , ) (0, ) C C B B N C C C B N C B B N B N − − = − = − （10） 故这个表又可进一步简写为
基变量 x2 B-A B CB-lA-C CB b 单纯形表的这种矩阵形式在线性规划的理论与计算中都是十分重要的。应该指出, 这里给出的表是对一个特殊的可行基B=(2…,P)而言。但所得结果具有普遍适用 性。如不限制基变量是前m个,引入以下符号:设S∈{,2,…,n}是基变量下标集合, R={1,2…,m}S是非基变量下标集合,这样基变量{x|i∈s}的典式可以写成 ∑x,i∈S x≥0J=12, mIn §2判别定理与换基迭代 (一)判别定理 对于给定的基B及相应的基可行解X,可针对典式作出如下判断 定理1若所有的≤0,则X是最优解。 证明:因,≤0,j=m+1…,n,故对任意可行解 f()=f-∑x≥f=f(X),故X是最优解。 可见,在进行最优性检验时,数,起着重要的判别作用称之为检 验数。为明确起见称λ为相应于变量x的检验数基变量的检验数均视为0 定理2若有某个n+>0且Bm≤0,i=1,…,m,则(LP)无最优解 证明:根据典式(*)可作一新的可行解X b,x=0,(>m,j≠m+k) 6Bm+k20i=1, 将X代入(7),得
66 基变量 1 x 2 x m x m 1 x + n x 1 x 2 x m x 1 B A− 1 B b− f CB 1 B A− -C CB 1 B b− 单纯形表的这种矩阵形式在线性规划的理论与计算中都是十分重要的。应该指出， 这里给出的表是对一个特殊的可行基 1 ( , , ) B P P = m 而言。但所得结果具有普遍适用 性。如不限制基变量是前 m 个，引入以下符号：设 S {1,2, , }n 是基变量下标集合， R= {1, 2, , }n /S 是非基变量下标集合，这样基变量 { | } i x i s 的典式可以写成 0 1, 2, , min i i ij j j R j j j j R x x i S x j n f f x = − = = − （11） §2 判别定理与换基迭代 （一） 判别定理 对于给定的基 B 及相应的基可行解 X ，可针对典式作出如下判断。 定理 1 若所有的 0 j ,则 X 是最优解。 证明：因 0 j , j m n = +1, , , 故 对 任 意 可 行 解 X ， 有 1 ( ) ( ) n j j j m f X f x f f X = + = − = ，故 X 是最优解。 可见，在进行最优性检验时，数 j 起着重要的判别作用,称之为检 验数。为明确起见称 j 为相应于变量 j x 的检验数,基变量的检验数均视为 0。 定理 2 若有某个 0 m k + 且 0, 1, , im k + =i m ，则（LP）无最优解 证明：根据典式（*）可作一新的可行解 1 X : 1 m k x + = , 1 0,( , ) j x j m j m k = + 1 0 1, , i i im k x i m = − = + 将 1 X 代入 (7) ，得
当6→+∞时,因n>0,故∫→-∞。由此可知f在可行解集合中无下 界。所以(LP)无最优解。 (二)换基迭代 设初始基可行解X不满足定理1和2的条件。即存在某Am+k>0,且对 某一i(1≤i≤m)有Bn4>0。则根据典式可造一新的基可行解X xk=0≥0,x=0,(j>m,j≠m+k) x=a- bmk i=1,…,m 这样的X自然满足(1),为了满足非负性条件(2),O的取法应满足 取b尽量大,即 0地n=B (12) 这时X为可行解。且其中至少有一个变量x1=a1-Bm+O=0。从而X的非0分量至多 是x,x2,…,x1,xm,x1…,x。以下往证H为基可行解。且在非退化情形下使目标函 数值严格下降 1、证X是基可行解。这只要证P…,P_,P,P1…,P线性无关。因已知 P,…,B,…P线性无关。故只须证明后面的向量组可由前一个线性表示就行了。首先由x 的典式有 B Into =BnkF1+…+BnB+…+ Bmk P Bn (注意f,…,P…P都是单位向量)。因Bn4≠0,故有 =-BnmP+…+1P+…-BmsP B 注意到P=BP(=1…,m),故以B乘上式两边就得到
67 m k f f = − + 当 → + 时，因 0 m k + ,故 f → − 。由此可知 f 在可行解集合中无下 界。所以（LP）无最优解。 （二） 换基迭代 设初始基可行解 X 不满足定理 1 和 2 的条件。即存在某 0 m k + ，且对 某一 i( 1 i m )有 0 im k + 。则根据典式可造一新的基可行解 1 X ： 1 1 0, 0,( , ) m k j x x j m j m k + = = + 1 1, , i i im k x i m = − = + 这样的 1 X 自然满足（1），为了满足非负性条件（2）， 的取法应满足 0 0 min im k i im k + + 取 尽量大，即 0 min im k i l im k lm k + + + = = （12） 这时 1 X 为可行解。且其中至少有一个变量 l lm k 0 l x = − = + 。从而 1 X 的非 0 分量至多 是 1 1 1 1 1 2 1 , , , , l m k x x x x − + ， 1 1 1 , , l m x x + 。以下往证 1 X 为基可行解。且在非退化情形下使目标函 数值严格下降。 1、证 1 X 是基可行解。这只要证 1 1 1 , , , , , , P P P P P l m k l m − + + 线性无关。因已知 1 , , , P P P l m 线性无关。故只须证明后面的向量组可由前一个线性表示就行了。首先由 X 的典式有 1 1 1 m k m k m k lm k l mm k m mm k P P P P + + + + + + = = + + + + （13） （注意 1 , , , P P P l m 都是单位向量）。因 0 lm k + ，故有 1 1 m k mm k 1 l m k m lm k lm k lm k P P P P + + + + + + = − + + + − 注意到 1 ( 1, , ) P B P j n j j − = = ，故以 B 乘上式两边就得到