二章节单纯形法ppt课件

1、第二章第二章 单纯形法单纯形法 p 单纯形法的普通原理 p 表格单纯形法 p 借助人工变量求初始的根本可行解p 单纯形表与线性规划问题的讨论p 改良单纯形法 思索到如下线性规划问题 其中一个mn矩阵，且秩为m，总可以被调整为一个m维非负列向量，为n维行向量，为n维列向量。 根据线性规划根本定理： 假设可行域= n / =，0非空有界， 那么上的最优目的函数值=一定可以在的一个顶点上到达。 这个重要的定理启发了Dantzig的单纯形法， 即将寻优的目的集中在D的各个顶点上。maxZ=CXAX=bX0p单纯形法的普通原理单纯形法的普通原理 Dantzig的单纯形法把寻优的目的集中在一切根本可行解即

2、可行域顶点中。其根本思绪是从一个初始的根本可行解出发，寻觅一条到达最优根本可行解的最正确途径。 单纯形法的普通步骤如下： 1寻觅一个初始的根本可行解。 2检查现行的根本可行解能否最优，假设为最优， 那么停顿迭代，已找到最优解，否那么转一步。 3移至目的函数值有所改善的另一个根本可行解， 然后转会到步骤2。 n 确定初始的根本可行解确定初始的根本可行解 确定初始的根本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始根本可行解也就独一确定 为了讨论方便，无妨假设在规范型线性规划中，系数矩阵中前m个系数列向量恰好构成一个可行基，即 =，其中 =1，2，m为基变量x1，x2，xm的

3、系数列向量 构成的可行基， =(m+1，Pm+2， Pn)为非基变量xm+1，xm+2， xn的 系数列向量构成的矩阵。 所以约束方程所以约束方程 就可以表示为就可以表示为BBNNXAX=(BN)=BX+NX=bX 用可行基的逆阵-1左乘等式两端，再经过移项可推得：假设令一切非基变量, 那么基变量由此可得初始的根本可行解1B bX=0AX=b-1-1BNX =B b-B NX-1BX =B bNX =0问题：要判别m个系数列向量能否恰好构成一个基并不是一件容易的事。基由系数矩阵中m个线性无关的系数列向量构成。但是要判别m个系数列向量能否线性无关并非易事。即使系数矩阵中找到了一个基B，也不能保证

4、该基恰好是可行基。由于不能保证基变量B=-1b0。为了求得根本可行解 ，必需求基的逆阵-1。但是求逆阵-1也是一件费事的事。结论：在线性规划规范化过程中设法得到一个m阶单位矩阵I作为初始可行基，1B bX=0-1-1-1BNBNNBAX=bBX +NX =bX =B b-B NXX =0,X =B b 假设在化规范方式前，约束方程中有假设在化规范方式前，约束方程中有“不等式，不等式， 那么在化规范形时除了在方程式左端减去剩余变量使不等式变那么在化规范形时除了在方程式左端减去剩余变量使不等式变 成等式以外，还必需在左端再加上一个非负新变量，称为成等式以外，还必需在左端再加上一个非负新变量，称为

5、人工变量人工变量 假设在化规范方式前，约束方程中有等式方程，那么可以直接在假设在化规范方式前，约束方程中有等式方程，那么可以直接在 等式左端添加人工变量。等式左端添加人工变量。为了设法得到一个为了设法得到一个m m阶单位矩阵阶单位矩阵I I作为初始可行基，可在性规作为初始可行基，可在性规划规范化过程中作如下处置：划规范化过程中作如下处置： 假设在化规范方式前，m个约束方程都是“的方式，那么在化规范形时只需在一个约束不等式左端都加上一个松弛变量xn+i (i=12m)。n判别现行的根本可行解能否最优判别现行的根本可行解能否最优 假设已求得一个根本可行解将这一根本可行解代入目的函数，可求得相应的目

6、的函数值将这一根本可行解代入目的函数，可求得相应的目的函数值其中分别表示基变量和非基变量所对应的价值系数子向量。1B bX=01-1BNBB bZ=CX=(C C )=C B b0B12mNm+1m+2nC =(c ,c ,c ), C =(c,c,c )要断定能否曾经到达最大值，只需将代入目的函数，使目的函数用非基变量表示，即： m+1m+2-1-1BNNBm+1,m+1,nnxxC B b+ XC B b+( )x 其中 称为非基变量N的检验向量，它的各个分量称为检验数。假设N的每一个检验数均小于等于0，即N0，那么如今的根本可行解就是最优解。-1-1BNX=B b-B NX-1BZ=C

7、B b-1NNBm+1m+1n=C -C B N=(,)BBNN-1-1BBNNBNNN-1-1BNBNXZ=CX=(C C )X=C X +C X =C (B b-B NX )+C X=C B b+(C -C B N)X定理定理1 1：最优解判别定理：最优解判别定理 对于线性规划问题对于线性规划问题假设某个根本可行解所对应的检验向量，假设某个根本可行解所对应的检验向量，那么这个根本可行解就是最优解。那么这个根本可行解就是最优解。定理定理2 2：无穷多最优解判别定理：无穷多最优解判别定理 假设是一个根本可行解，所对应的检验向量假设是一个根本可行解，所对应的检验向量，其中存在一个检验数，其中存在

8、一个检验数m+k=0m+k=0，那么线性规划问题有无穷多最优解。那么线性规划问题有无穷多最优解。nmaxZ=CX, D= XR /AX=b,X0-1NNB=C -C B N01B bX=0-1NNB=C -C B N0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )xn 根本可行解的改良根本可行解的改良 假设现行的根本可行解不是最优解，即在检验向量 中存在正的检验数，那么需在原根本可行解的根底上寻觅一个新的根本可行解，并使目的函数值有所改善。详细做法是：先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量将它的值从零增至正值，再从原来的基变量中确定一个换出变量，使

9、它从基变量变成非基变量将它的值从正值减至零。由此可得一个新的根本可行解，由 可知，这样的变换一定能使目的函数值有所添加。-1NNB=C -C B Nm+1m+2-1Bm+1,m+1,nnxxZC B b+( )x 换入变量和换出变量确实定：换入变量和换出变量确实定：l换入变量确实定换入变量确实定 最大添加原那么最大添加原那么 假设检验向量假设检验向量 ， 假设其中有两个以上的检验数为正，那么为了使目的函数值添加得假设其中有两个以上的检验数为正，那么为了使目的函数值添加得快些，通常要用快些，通常要用“最大添加原那么，即选取最大正检验数所对应的非最大添加原那么，即选取最大正检验数所对应的非基变量为

10、换入变量，即假设基变量为换入变量，即假设 那么选取对应的那么选取对应的 为换入变量，为换入变量， 由于且为最大，由于且为最大， 因此当由零增至正值，因此当由零增至正值，可使目的函数值可使目的函数值 最大限制的添加。最大限制的添加。-1NNBm+1m+2n=C -C B N=(,)jjm+kmax / 0,m+1jn = m+kxm+kxm+k0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )xl 换出变量确实定换出变量确实定 最小比值原那么最小比值原那么l 假设确定为换入变量，方程假设确定为换入变量，方程l l 其中为中与对应的系数列向量。其中为中与对应的系数列向量。l 如今需在

11、如今需在 中确定一个基变量为换出变量。中确定一个基变量为换出变量。l 当由零渐渐添加到某个值时，当由零渐渐添加到某个值时， 的非负性能够被突破。的非负性能够被突破。l 为坚持解的可行性，可以按最小比值原那么确定换出变量：为坚持解的可行性，可以按最小比值原那么确定换出变量：l 假设假设B12mX =(x ,x ,x )T-1-1-1im+ki-1-1m+kim+k(B b)(B b)min/(B P) 0,1im =(B P)(B P)ll m+kx-1-1-1-1BNBm+km+kX=B b-B NXX=B b-B Pxm+kPm+kxm+kx那么选取对应的基变量那么选取对应的基变量 为换出变

12、量。为换出变量。 xlBX 定理定理3 3：无最优解判别定理：无最优解判别定理 假设假设 是一个根本可行解，有一个检验数是一个根本可行解，有一个检验数 ，但是，那么该线性规划问题无最优解。但是，那么该线性规划问题无最优解。1B bX=0-1m+kB P0m+k0证：令证：令 ，那么得新的可行解，那么得新的可行解将上式代入将上式代入由于由于 , , 故当故当+时，时，Z+Z+。-1-1-1-1Bm+km+km+kX =B b-B PxB b-B Pm+1-1-1Bm+1m+knBm+knxZ=C B b+(, )C B b+x m+kx,(0) m+k0n 用初等变换求改良了的根本可行解用初等变

13、换求改良了的根本可行解 假设是线性规划 的可行基，那么令非基变量，那么基变量。可得根本可行解 。 1B bX=0BNXA X =b(B N )bXmaxZ=CX,AX=b,X0B-1-1NX(I,BN )=BbX用逆阵左乘约束方程组的两端，等价于对方程组施以一系列用逆阵左乘约束方程组的两端，等价于对方程组施以一系列的初等的初等“行变换。变换的结果是将系数矩阵中的可行基变换成行变换。变换的结果是将系数矩阵中的可行基变换成单位矩阵单位矩阵I I，把非基变量系数列向量构成的矩阵变换成，把，把非基变量系数列向量构成的矩阵变换成，把资源向量资源向量b b变换成。变换成。1B1BX =B b1B N1B

14、bNX =0且改良了的根本可行解只是在的基变量的根底上用一个换入变量替代其中一个换出变量，其它的基变量依然坚持不变。这些基变量的系数列向量是单位矩阵I中的单位向量。为了求得改良的根本可行解 ，只需对增广矩阵 施行初等行变换，将换入变量的系数列向量变换成换出变量所对应的单位向量即可。由于行初等变换后的方程组与原约束方程组 或同解B-1-1NX(I,B N)=B bXAX=bX-1-1(I,BN ,Bb)BNX(B ,N )=bXX123451234123512345maxZ=5x2x3xxxx2x2xx83x4xxx7 x ,x ,x ,x ,x012210A=341018b7 C = ( 5

15、, 2 , 3 ,1 , 1 )例例1 1解：解：( () )确定初始的根本可行解。确定初始的根本可行解。 ，基变量，基变量 ，非基变量，非基变量 。4510B=(P P )=0145x ,x123x ,x ,x14BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x 1NB8X=0X=Bb=7X = (0 ,0 ,0 , 8 , 7 )T1B8Z=C B b=(-1,1)17 (2) 检验检验 能否最优。能否最优。检验向量检验向量 由于由于1=3，3=4 均大于零，均大于零，所以不是最优解。所以不是最优解。X =(0,0,0

16、,8, 7)T-1NNB123122=C-C B N=(5,2,3)-(-1,1)341=(5,2,3)-(2,2,-1)=(3, 0, 4) 14BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x X =(0,0,0,8, 7)T3 3根本可行解的改良根本可行解的改良 选取换入变量选取换入变量由于由于max3max3，4=44=4，取，取x3x3为换入变量。为换入变量。 选取换出变量选取换出变量 且且 ， 选取选取x4x4为换出变量为换出变量. .8 78min,2 12X = (0,0,0,8, 7 )T11382Bb=

17、,BP07114BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x N123=(,)(3, 0, 4)4-1-13335x82=B b-B P x =-xx71 4 4求改良了的根本可行解求改良了的根本可行解 对约束方程组的增广矩阵施以初等行变换，使换入变量对约束方程组的增广矩阵施以初等行变换，使换入变量x3x3所对应的所对应的系数列向量系数列向量 变换成换出变量变换成换出变量x4x4所对应的单位向量所对应的单位向量 , , 留意坚持基变量留意坚持基变量x5x5的系数列向量的系数列向量 为单位向量不变。为单位向量不变。32P

18、 =1 41P0 50P =1 111 104122 108 2234 10 1734 10 17111 10422 5-1301 322 X14BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x 第一行除以第一行除以第二行减去第一行第二行减去第一行可得改良的根本可行解。 ， 基 变 量 ， 非 基 变 量。根本可行解目的函数值易见目的函数值比原来的Z=-1添加了， 再转向步骤(2)3510B=(P P )=0113BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)

19、015-133x22 1NB4X =0X =B b=3X = (0,0,4, 0, 3)T1B4Z=C Bb=(3,1)153C = ( 5 ,2 ,3 ,1,1)C = (5 ,2 ,3 ,1,1)111 10412210822 5341017-130132235x x124x ,x ,x2检验检验 能否最优。能否最优。检验向量检验向量由于，由于，所以仍不是最优解。所以仍不是最优解。X = (0,0,4, 0, 3)T-1NNB12411122=C-C B N=(5,2,-1)-(3,1)5-1322=(5,2,-1)-(4,6,1)=(1, -4, -2) X =(0,0,4, 0,3)T

20、13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 110 3 3根本可行解的改良根本可行解的改良 选取换入变量选取换入变量由于，取为换入变量。由于，取为换入变量。 选取换出变量选取换出变量且且 ，选取为换出变量选取为换出变量. .433min,1/2 5/25/2X = (0,0,4, 0, 3)T111142Bb=, BP0352110 1x5x13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 3-1-11115x41/2

21、=B b-B P x =-xx35/2 4 4求改良了的根本可行解求改良了的根本可行解 对约束方程组的增广矩阵施以初等行变换，使换入变量所对应对约束方程组的增广矩阵施以初等行变换，使换入变量所对应的系数列向量变换成换出变量所对应的单位向量的系数列向量变换成换出变量所对应的单位向量 , , 112P =5250P1 X1x5x111111041104 2222665-12-11030135555223172-101 5555 66-12105555 13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 第二行乘以第

22、二行乘以/第一行减以第二行的第一行减以第二行的/倍倍可得改良的根本可行解。 ，基变量，非基变量根本可行解目的函数值 比Z=15添加了，再转向步骤(2)3110B=(P P )=012B3BN4N1523-117xC =(3,5)x105555X =,X = x,B=,N=,b=C =(2,-1,1)x016-126x55551NB175X =0X =B b=65617X=(,0,0,0)55T1B17815Z=C Bb=(3,5)655C = (5 ,2 ,3,1,1)C = (5 ,2 ,3,1,1)31x ,x245x ,x ,x3172-111011104555522 566-1-123

23、013102255552检验 能否最优。检验向量由于一切检验数均小于零，所以是最优解，-1NNB24523-1555=C-CBN =(2,-1,1)-(3,5)6-125553647-26-9-2=(2,-1,1)-(,)=(,)555555 617X =(,0,0,0)55T*617X =X =(,0,0,0)55T*81Z =52B3BN4N1523-117xC =(3,5)x105555X =,X = x,B=,N=,b=C =(2,-1,1)x016-126x5555p表格单纯形法表格单纯形法经过例我们发现，在单纯形法的求解过程中，有以下重要目的：每一个根本可行解的检验向量根据检验向量

24、可以确定所求得的根本可行解能否为最优解。假设不是最优又可以经过检验向量确定适宜的换入变量。每一个根本可行解所对应的目的函数值经过目的函数值可以察看单纯形法的每次迭代能否能使目的函数值有效地添加，直至求得最优目的函数为止。 在单纯形法求解过程中，每一个根本可行解都以某个经过初等行变换的约束方程组中的单位矩阵为可行基。当=时，-1=，易知：-1NNB=C-C B N1BZ=C BbNNB=C-C NBZ=C b 可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成：C CBCN CB XB b X1 X2 Xm X m+1 Xm+2 Xn C1C2.Cm m X1X2 .Xm b1b2

25、.bm I I N 12.m Z CBb 0 CN- - CBN 例例2 2、试利用单纯形表求例、试利用单纯形表求例1 1中的最优解解：中的最优解解：得初始的单纯形表：得初始的单纯形表：C = (5 ,2 ,3 ,1,1)122108(Ab)=341017123451234123512345maxZ=5x2x3xxxx2x2xx83x4xxx7 x ,x ,x ,x ,x0NNB=C-C NBZ=C b初始根本可行解，初始根本可行解，Z= -1Z= -1，X =(0,0,0,8, 7)T 1 2 2 1 08x4-1 3 0 4 0 0-1Z 3 4 1 0 17x51 x1 x2 x3 x4

26、 x5bXBCB 5 2 3 -1 1C换入变量，换出变量，为主元进展旋转变换换入变量，换出变量，为主元进展旋转变换3x4x根本可行解，根本可行解，Z= 15Z= 15，X = (0,0,4, 0, 3)T1/2 1 1 1/2 04x33 1 -4 0 -2 015Z5/2 3 0 -1/2 13x51 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C 1 2 2 1 08x4-1 3 0 4 0 0-1Z 3 4 1 0 17x51 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C8/27/1最优解最优解 最优值最优值 617X,0,0,055T换入变量，换出变

27、量，换入变量，换出变量，/ /为主元进展旋转变换为主元进展旋转变换1x5xNNB=C-C N081Z54/1/21/2 1 1 1/2 04x33 1 -4 0 -2 015Z3/5/25/2 3 0 -1/2 13x51x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C 0 2/5 1 3/5 -1/517/5x33 0 -26/5 0 -9/5 -2/581/5Z 1 6/5 0 -1/5 2/56/5x15 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C例例3 3、用单纯形方法求解线性规划问题、用单纯形方法求解线性规划问题解：此题的目的函数是求极小化的线性函数

28、，解：此题的目的函数是求极小化的线性函数，可以令可以令那么那么这两个线性规划问题具有一样的可行域和最优解，这两个线性规划问题具有一样的可行域和最优解，只是目的函数相差一个符号而已。只是目的函数相差一个符号而已。 121324125jminZ=-x -2xxx4xx3x2xx8x0 j1,2,3,4,5，12Z = -Z = x +2x1212minZ=-x -2xmaxx +2xZ 0 1 0 1 03x22 0 0 1 2 -12x30-0 1 0 1 03x224/11 0 1 0 04x303/10 1 0 1 03x40_1 0 1 0 04x30 0 0 0 0 -18Z 1 0 0

29、 -2 12x11 1 0 0 -2 06Z2/11 0 0 -2 12x50 1 2 0 0 00Z8/21 2 0 0 18x50 x1 x2 x3 x4 x5bXBCB 1 2 0 0 0C最优解最优值最优解最优值X2,3,2,0,0TmaxZ =8 or minZ=-82/23/1- 由于非基变量x4的检验数4=0，由无穷多最优解判别定理，本例的线性规划问题存在无穷多最优解。现实上假设以x4为换入变量，以x3为换出变量，再进展一次迭代，可得一下单纯形表：最优解最优解 最优值最优值最优解的普通表示式最优解的普通表示式maxZ=8 or minZ=-8X4,2,0,1,0TX(2,3,2,

30、0,0)(1) 4,2,0,1,0,01.TTC 1 2 0 0 0CBXBb x1 x2 x3 x4 x5021x4x2x1124 0 0 1/2 1 -1/2 0 1 -1/2 0 1/2 1 0 1 0 0Z8 0 0 0 0 -1对于极小化的线性规划问题的处置：对于极小化的线性规划问题的处置：先化为规范型，即将极小化问题变换为极大化问题，然后利用单先化为规范型，即将极小化问题变换为极大化问题，然后利用单纯形方法求解纯形方法求解直接利用单纯形方法求解，但是检验能否最优的准那么有所不同直接利用单纯形方法求解，但是检验能否最优的准那么有所不同，即：即： 假设某个根本可行解的一切非基变量对应的

31、检验数假设某个根本可行解的一切非基变量对应的检验数 而不是而不是，那么根本可行解为最优解那么根本可行解为最优解否那么采用最大减少原那么而非最大添加原那么来确定换入否那么采用最大减少原那么而非最大添加原那么来确定换入变量，变量，即：即： 假设假设那么选取对应的非基变量那么选取对应的非基变量xm+kxm+k为换入变量为换入变量确定了换入变量以后，换出变量仍采用最小比值原那么来确定。确定了换入变量以后，换出变量仍采用最小比值原那么来确定。 NNB= C-CN0jjm+kmin / 0因因但但所以原问题所以原问题无最优解无最优解1-1P=01-2n 退化解 当线性规划问题的根本可行解中有一个或多个基变

32、量取零值时，称此根本可行解为退化解。 产生的缘由：在单纯形法计算中用最小比值原那么确定换出变量时，有时存在两个或两个以上一样的最小比值，那么在下次迭代中就会出现一个甚至多个基变量等于零。遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目的函数并不能因此得到任何改动由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值坚持不变。经过基变换以后的前后两个退化的根本可行解的坐标方式完全一样。从几何角度来解释，这两个退化的根本可行解对应线性规划可行域的同一个顶点，处理的方法：最小比值原那么计算时存在两个及其以上一样的最小比值时，选取下标最大的基变量为换出变量，按此方法进展

33、迭代一定能防止循环景象的产生摄动法原理。例例8 8、求解下述线性规划问题：、求解下述线性规划问题：解：引入松弛变量解：引入松弛变量化规范型化规范型123412341234 3jmaxZ=3x -80 x +2x -24xx -32x -4x36x 0 x -24x - x 6x 0 x 1 x0,j1,2,3,41234123451234 637jmaxZ=3x -80 x +2x -24xx -32x -4x36x x 0 x -24x - x 6x x 0 x x 1 x0,j1,2,3,4,5,6,7567x ,x ,x000-242-8030Z-5-60-420-805Z1000100

34、1x3 212060-2411x1 3321300-803x5 00-30-425-800Z1100 1001x7 00106-1-2410 x1 30-1130-3-800 x5 0-11001001x7 000106-1-2410 x6 0000136-4-3210 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 000-242-803C 第一次迭代第一次迭代中运用了摄动中运用了摄动法原理，选择法原理，选择下标为下标为6的基的基变量变量x6离基。离基。可得最优解可得最优解 ，目的函数值，目的函数值maxZ=，X1,0,1,0,3Tn 无穷多最优解无穷多最优解 无穷多最优

35、解判别原理：假设线性规划问题某个根本可行解一切的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例：最优表：非基变量检验数，所以有无穷多最优解。最优解集为可行域两个顶点的凸组合：C1 2 0 0 0CBXBb x1 x2 x3 x4 x5021x3x2x12320 0 1 2 -10 1 0 1 01 0 0 -2 12/23/1-Z8 0 0 0 0 -14= 0X(2,3,2,0,0)(1) 4,2,0,1,0,01.TTn改良单纯形法的特点改良单纯形法的特点n 利用单纯形表求解线性规划时，每一次迭利用单纯形表求解线性规划时，每一次迭代都把整个单纯

36、形表计算一遍，现实上我们关怀代都把整个单纯形表计算一遍，现实上我们关怀的只是以下一些数据：的只是以下一些数据：n根本可行解根本可行解 ，其相应的目的函数值，其相应的目的函数值 ，n非基变量检验数非基变量检验数 ，及其换入，及其换入变量变量 ，n 设设n主元列元素主元列元素 ，及其换出变量，及其换出变量 ，n设设n 利用它们可得到一组新的基变量以及新的可行利用它们可得到一组新的基变量以及新的可行基基1 1。1-1-1iki-11kik(B b)(B b)min/(B P ) 0, i (B P )(B P )llp改良单纯形法改良单纯形法-1BX =B b-1BZ=C B b-1NNB=C -C

37、 B Nkxxl-1kB P为基变量下标为基变量下标jjkmax / 0, j =为非基变量下标为非基变量下标对任一根本可行解，只需知道，上述关键数据都可以从线性规划问题的初始数据直接计算出来。因此如何计算根本可行解对应的可行基的逆阵成为改良单纯形法的关键改良单纯形法推导出从可行基变换到1时，到的变换公式。当初始可行基为单位矩阵时，变换公式将更具有优越性，由于这样可以防止矩阵求逆的费事以下推导从到的变换公式：-1B-1B-1B-11B-1B-11B-1BX =B b-1BZ=C B b-1NNB=C -C B N-1kB P-1-1-1-1-1-1-11211mB B(B P ,B P ,B

38、P ,B P,B P ,B P )lllm m1.0.0.1-1-1-1-1-1-1-11121k1mB B(B P ,B P ,B P ,B P ,B P ,B P )ll-1121k1m(, , , ,B P , , )lleeeee1211mB(P,P ,P ,P,P ,P )lll假设当前基，假设当前基， 基变换中用非基变量取代基变量基变换中用非基变量取代基变量可得新基可得新基前后二个基相比仅相差一列，且前后二个基相比仅相差一列，且比较以上二式，可得比较以上二式，可得 xl1121k1mB(P,P ,P ,P ,P ,P )llkx其中表示第个元素为其中表示第个元素为1 1，其它元素均

39、为零的单位列向量，其它元素均为零的单位列向量，为主元列元素。为主元列元素。 iei-1kB P假设 ，那么1k2k-1KkmkaaB P =aal1klk2klkkm klka1-0aa-a111k1aa0-1a-E(BB )ll-1-111211mB B(, , , ,B P , , )lkleeeee第列换出变量对应列第列换出变量对应列 第行第行ll所以由所以由-1-1-1-1-1k111kE(B B )BB BE Bllxl主元素主元素n改良单纯形法的步骤改良单纯形法的步骤n1 1根据给出的线性规划问题的规范型，根据给出的线性规划问题的规范型，确定初始基变量和初始可行基。求初始可行基确定

40、初始基变量和初始可行基。求初始可行基B B的逆阵的逆阵-1-1，得初始根本可行解，得初始根本可行解n。 n2 2计算单纯形乘子计算单纯形乘子 ，得目的函数，得目的函数当前值当前值n 3 3 计 算 非 基 变 量 检 验 数计 算 非 基 变 量 检 验 数，n假设假设N0N0，那么当前解已是最优解，停顿，那么当前解已是最优解，停顿计算；否那么转下一步。计算；否那么转下一步。n4 4 根据，确定非基变根据，确定非基变量为换入变量，计算量为换入变量，计算, ,假设假设00，那么问题没有有限最优解，停顿计算，那么问题没有有限最优解，停顿计算，n否那么转下一步。否那么转下一步。-1B=C B-1NN

41、BN=C -C B N=C -N-1BZ=C B b=b-1BNX =B b,X0jjkmax / 0 =kx-1kB P-1kB P5 5 根据根据 ，确定基变量，确定基变量 为换出变量。为换出变量。 6 6 用替代用替代 得新基得新基1 1，由变换公式，由变换公式计算新基的逆阵计算新基的逆阵1-11-1，求出新的根本可行解，求出新的根本可行解 其中为变换矩阵，构造方法是：其中为变换矩阵，构造方法是： 从一个单位矩阵出发，把换出变量从一个单位矩阵出发，把换出变量 在基在基B B中的对应列的单位中的对应列的单位 向量，交换成换入变量向量，交换成换入变量 对应的系数列向量对应的系数列向量 ，并做

42、如下变形，并做如下变形， 主元素主元素 应在主对角线上取倒数，其它元素除以主元素应在主对角线上取倒数，其它元素除以主元素 并取相反数。并取相反数。反复反复2 26 6直至求得最优解。直至求得最优解。 -1-1-1iki-1-1kik(B b)(B b)min/(B P ) 0 =(B P )(B P )llxlPlkP-1-11k BE Blk Elkal-1kB Pxlkxkal B=I-1BNX =B b,X0-1B=C BZ=bNN=C -Nkx换入换入-1kB P无界解无界解换出换出xl1 B-1-11k BE Bl最优解最优解jjkmax / 0 =-1-1-1iki-1-1kik(

43、B b)(B b)min/(B P ) 0 =(B P )(B P )ll初始基初始基maxZ=CXAX=bX0新基新基 例9、试用改良单纯形法求解解：察看法确定，为基变量 为非基变量 121231241234maxZ=3x +2x x +x +x =402x +x +x =60 x ,x ,x ,x01 1 10A=2101C = (3 ,2 ,0 ,0 )4 0b =6 003410B =(P P )=0134x ,x-1-10B0010104040B, X =B b=, X(0,0,40,60)01016060T12x ,x 2计算单纯行乘子 目的函数当前值 3非基变量检验数-1-10B034010 =C B(c ,c )B(0,0)(0,0)010040Z = b = (0,0)060NN0120121211 =C - N=(c ,c )- (P P )=(3,2)-(0,0)= (3, 2)21 (4(4 选择换入变量选择换入变量 故故 为换入