最新单纯行法精品课件.ppt

2 考虑到如下线性规划问题考虑到如下线性规划问题 其中一个其中一个m mn n矩阵，且秩为矩阵，且秩为m m，总可以被调整为一个，总可以被调整为一个m m维非负列维非负列向量，为向量，为n n维行向量，为维行向量，为n n维列向量。维列向量。 根据线性规划基本定理：根据线性规划基本定理： 如果可行域如果可行域= = n n / / = =，00非空有界，非空有界， 则上的最优目标函数值则上的最优目标函数值= =一定可以在的一个顶点上达到。一定可以在的一个顶点上达到。 这个重要的定理启发了这个重要的定理启发了DantzigDantzig的单纯形法，的单纯形法， 即将寻优的目标集中在即将寻优的目标集中在D D的各个顶点上。的各个顶点上。maxZ=CXAX=bX0p单纯形法的一般原理单纯形法的一般原理 9要判定是否已经达到最大值，只需将要判定是否已经达到最大值，只需将代入目标函数，使目标函数用非代入目标函数，使目标函数用非基变量基变量表示，即：表示，即： m+1m+2-1-1BNNBm+1,m+1,nnxxC B b+ XC B b+( )x 其中其中 称为非基变量称为非基变量N N的检验向量，它的各个分量称为检验数。若的检验向量，它的各个分量称为检验数。若N N的每一个检验数均小的每一个检验数均小于等于于等于0 0，即，即N N00，那么现在的基本可行解就是最优解。，那么现在的基本可行解就是最优解。-1-1BNX=B b-B NX-1BZ=C 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)X10定理定理1 1：最优解判别定理：最优解判别定理 对于线性规划问题对于线性规划问题若某个基本可行解所对应的检验向量，若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。则这个基本可行解就是最优解。定理定理2 2：无穷多最优解判别定理：无穷多最优解判别定理 若是一个基本可行解，所对应的检验向量若是一个基本可行解，所对应的检验向量，其中存在一个检验数，其中存在一个检验数m+km+k=0=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+( )x11n 基本可行解的改进基本可行解的改进 如果现行的基本可行解不是最优解，即在检验向量如果现行的基本可行解不是最优解，即在检验向量 中存在正的检验数，则需在原基本可行解的基中存在正的检验数，则需在原基本可行解的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：做法是： 先从检验数为正的非基变量中确定一个换入变量，使它从非基先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值），变量变成基变量（将它的值从零增至正值）， 再从原来的基变量中确定一个换出变量，使它从基变量变成非再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。基变量（将它的值从正值减至零）。由此可得一个新的基本可行解，由由此可得一个新的基本可行解，由 可知，这样的变换一定能使目标函数值有所增加。可知，这样的变换一定能使目标函数值有所增加。-1NNB=C -C B Nm+1m+2-1Bm+1,m+1,nnxxZC B b+( )x12 换入变量和换出变量的确定换入变量和换出变量的确定：l换入变量的确定换入变量的确定 最大增加原则最大增加原则 假设检验向量假设检验向量 ， 若其中有两个以上的检验数为正，那么为了使目标函数值增加得快若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常要用些，通常要用“最大增加原则最大增加原则”，即选取最大正检验数所对应的非基，即选取最大正检验数所对应的非基变量为换入变量，即若变量为换入变量，即若 则选取对应的则选取对应的 为换入变量，为换入变量， 由于且为最大，由于且为最大， 因此当由零增至正值，因此当由零增至正值，可使目标函数值可使目标函数值 最大限度的增加。最大限度的增加。-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+( )x13l 换出变量的确定换出变量的确定 最小比值原则最小比值原则 如果确定为换入变量，方程如果确定为换入变量，方程其中为中与对应的系数列向量。其中为中与对应的系数列向量。现在需在现在需在 中确定一个基变量为换出变量。中确定一个基变量为换出变量。 当由零慢慢增加到某个值时，当由零慢慢增加到某个值时， 的非负性可能被打破。的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量：为保持解的可行性，可以按最小比值原则确定换出变量： 若若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则选取对应的基变量则选取对应的基变量 为换出变量。为换出变量。 xlBX14 定理定理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+k015n 用初等变换求改进了的基本可行解用初等变换求改进了的基本可行解 假设是线性规划假设是线性规划 的可行基，则的可行基，则令非基变量，则基变量。令非基变量，则基变量。可得基本可行解可得基本可行解 。 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 bNX =016且改进了的基本可行解只是在的基变量的基础上用一个换且改进了的基本可行解只是在的基变量的基础上用一个换入变量替代其中一个换出变量，其它的基变量仍然保持不变。这些入变量替代其中一个换出变量，其它的基变量仍然保持不变。这些基变量的系数列向量是单位矩阵基变量的系数列向量是单位矩阵I I中的单位向量。为了求得改进的基中的单位向量。为了求得改进的基本可行解本可行解 ，只需对增广矩阵，只需对增广矩阵 施行初等行变换，将换入变量的系数列向量变换成换出变量所对施行初等行变换，将换入变量的系数列向量变换成换出变量所对应的单位向量即可。应的单位向量即可。由于行初等变换后的方程组由于行初等变换后的方程组与原约束方程组与原约束方程组 或同解或同解B-1-1NX(I,B N)=B bXAX=bX-1-1(I,BN ,Bb)BNX(B ,N )=bXX17123451234123512345maxZ=5x2x3xxxx2x2xx83x4xxx7 x ,x ,x ,x ,x012210A=341018b7 C = ( 5 , 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 18(2) 检验检验 是否最优。是否最优。检验向量检验向量 因为因为1 1=3=3，3 3=4 =4 均大于零，均大于零，所以不是最优解。所以不是最优解。X =(0,0,0,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)T19（3）基本可行解的改进基本可行解的改进 选取换入变量选取换入变量因为因为max3max3，4=44=4，取，取x x3 3为换入变量。为换入变量。 选取换出变量选取换出变量 且且 ， 选取选取x x4 4为换出变量为换出变量. .8 78min,2 12X = (0,0,0,8, 7 )T11382Bb=,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 20（4）求改进了的基本可行解求改进了的基本可行解 对约束方程组的增广矩阵施以初等行变换，使换入变量对约束方程组的增广矩阵施以初等行变换，使换入变量x x3 3所对应的所对应的系数列向量系数列向量 变换成换出变量变换成换出变量x x4 4所对应的单位向量所对应的单位向量 , , 注意保持基变量注意保持基变量x x5 5的系数列向量的系数列向量 为单位向量不变。为单位向量不变。32P =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 第一行除以第一行除以第二行减去第一行第二行减去第一行21可得改进的基本可行解。可得改进的基本可行解。 ，基变量，基变量，非基变量。非基变量。基本可行解基本可行解目标函数值目标函数值易见目标函数值比原来的易见目标函数值比原来的Z=-1Z=-1增加了，增加了， 再转向步骤再转向步骤(2)(2)3510B=(P P )=0113BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)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 ,x22（2）检验检验 是否最优。是否最优。检验向量检验向量因为，因为，所以仍不是最优解。所以仍不是最优解。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)T13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 110 23（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=B b-B P x =-xx35/2 24（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 第二行乘以第二行乘以/第一行减以第二行的第一行减以第二行的/倍倍25可得改进的基本可行解。可得改进的基本可行解。 ，基变量，基变量，非基变量非基变量基本可行解基本可行解目标函数值目标函数值 比比Z=15Z=15增加了，再转向步增加了，再转向步骤骤(2)(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-1230131022555526（2）检验检验 是否最优。是否最优。检验向量检验向量因为所有检验数均小于零，因为所有检验数均小于零，所以是最优解，所以是最优解，-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-126x555527p表格单纯形法表格单纯形法通过例我们发现，在单纯形法的求解过程中，有下列重要指标：通过例我们发现，在单纯形法的求解过程中，有下列重要指标：l 每一个基本可行解的检验向量每一个基本可行解的检验向量根据检验向量可以确定所求得的基本可行解是否为最优解。如果不根据检验向量可以确定所求得的基本可行解是否为最优解。如果不是最优又可以通过检验向量确定合适的换入变量。是最优又可以通过检验向量确定合适的换入变量。l 每一个基本可行解所对应的目标函数值每一个基本可行解所对应的目标函数值通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加，直至求得最优目标函数为止。有效地增加，直至求得最优目标函数为止。 在单纯形法求解过程中，每一个基本可行解都以在单纯形法求解过程中，每一个基本可行解都以某个经过初等行某个经过初等行变换的变换的约束方程组中的单位矩阵约束方程组中的单位矩阵为可行基。为可行基。当当= =时，时，-1-1= =，易知：，易知：-1NNB=C-C B N1BZ=C BbNNB=C-C NBZ=C b28 可将这些重要结论的计算设计成如下一个简单的表格，可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成：即单纯形表来完成：C CBCN CB XB b X1 X2 Xm X m+1 Xm+2 Xn C1C2.Cm X1X2 .Xm b1b2.bm I I N 12.m Z CBb 0 CN- - CBN 29例例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 x5bXBCB 5 2 3 -1 1C30换入变量，换出变量，为主元进行旋转变换换入变量，换出变量，为主元进行旋转变换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/131最优解最优解 最优值最优值 617X,0,0,055T换入变量，换出变量，换入变量，换出变量，/ /为主元进行旋转变换为主元进行旋转变换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 1C32例例3 3、用单纯形方法求解线性规划问题、用单纯形方法求解线性规划问题解：本题的目标函数是求极小化的线性函数，解：本题的目标函数是求极小化的线性函数，可以令可以令则则这两个线性规划问题具有相同的可行域和最优解，这两个线性规划问题具有相同的可行域和最优解，只是目标函数相差一个符号而已。只是目标函数相差一个符号而已。 121324125jminZ=-x -2xxx4xx3x2xx8x0 j1,2,3,4,5，12Z = -Z = x +2x1212minZ=-x -2xmaxx +2xZ33 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 -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-34 因为非基变量因为非基变量x x4 4的检验数的检验数4 4=0=0，由无穷多最优解判别定理，本例，由无穷多最优解判别定理，本例的线性规划问题存在无穷多最优解。事实上若以的线性规划问题存在无穷多最优解。事实上若以x x4 4为换入变量，以为换入变量，以x x3 3为为换出变量，再进行一次迭代，可得一下单纯形表：换出变量，再进行一次迭代，可得一下单纯形表：最优解最优解 最优值最优值最优解的一般表示式最优解的一般表示式maxZ=8 or minZ=-8X4,2,0,1,0TX(2,3,2,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 -135对于极小化的线性规划问题的处理：对于极小化的线性规划问题的处理：l先化为标准型，即将极小化问题变换为极大化问题，然后利用单先化为标准型，即将极小化问题变换为极大化问题，然后利用单纯形方法求解纯形方法求解l直接利用单纯形方法求解，但是检验是否最优的准则有所不同，直接利用单纯形方法求解，但是检验是否最优的准则有所不同，即：即： 若某个基本可行解的所有非基变量对应的检验数若某个基本可行解的所有非基变量对应的检验数 （而不是（而不是），），则基本可行解为最优解则基本可行解为最优解否则采用最大减少原则（而非最大增加原则）来确定换入变量，否则采用最大减少原则（而非最大增加原则）来确定换入变量，即：即： 若若则选取对应的非基变量则选取对应的非基变量x xm+km+k为换入变量为换入变量 确定了换入变量以后，换出变量仍采用最小比值原则来确定。确定了换入变量以后，换出变量仍采用最小比值原则来确定。 NNB= C-CN0jjm+kmin / 0因因但但所以原问题所以原问题无最优解无最优解1-1P=01-253n 退化解 当线性规划问题的基本可行解中有一个或多个基变量取零值时，当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。称此基本可行解为退化解。 产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值有时存在两个或两个以上相同的最小比值，那么在下次迭代中就会，那么在下次迭代中就会出现一个甚至多个基变量等于零。出现一个甚至多个基变量等于零。遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点，划可行域的同一个顶点，解决的办法：最小比值原则计算时存在两个及其以上相同的最小解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。定能避免循环现象的产生（摄动法原理）。54例例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 ,x55000-242-8030Z-5-60-420-805Z10001001x3 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,3T56n 无穷多最优解无穷多最优解 无穷多最优解判别原理：无穷多最优解判别原理：若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例：最优表：例：最优表：非基变量检验非基变量检验数，数，所以有无穷多所以有无穷多最优解。最优解。最优解集为可行域两个顶点的凸组合：最优解集为可行域两个顶点的凸组合：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.TT57n改进单纯形法的特点改进单纯形法的特点 利用单纯形表求解线性规划时，每一次迭代都把整个单纯形表计利用单纯形表求解线性规划时，每一次迭代都把整个单纯形表计算一遍，事实上我们关心的只是以下一些数据：算一遍，事实上我们关心的只是以下一些数据：l基本可行解基本可行解 ，其相应的目标函数值，其相应的目标函数值 ，l非基变量检验数非基变量检验数 ，及其换入变量，及其换入变量 ， 设设主元列元素主元列元素 ，及其换出变量，及其换出变量 ，设设 利用它们可得到一组新的基变量以及新的可行基利用它们可得到一组新的基变量以及新的可行基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 B Nkxxl-1kB P为基变量下标为基变量下标jjkmax / 0, j =为非基变量下标为非基变量下标58对对任一基本可行解，任一基本可行解，只要知道，上述关键数据都可以从只要知道，上述关键数据都可以从线性规划问题的初始数据直接计算出来。因此如何计算基本可行解线性规划问题的初始数据直接计算出来。因此如何计算基本可行解对应的可行基的逆阵成为改进单纯形法的关键对应的可行基的逆阵成为改进单纯形法的关键改进单纯形法推导出从可行基变换到改进单纯形法推导出从可行基变换到1 1时，到时，到的变换公式。当初始可行基为单位矩阵的变换公式。当初始可行基为单位矩阵时，变换公式将更具有优时，变换公式将更具有优越性，因为这样可以避免矩阵求逆的麻烦越性，因为这样可以避免矩阵求逆的麻烦以下推导从到的变换公式：以下推导从到的变换公式：-1B-1B-1B-11B-1B-11B-1BX =B b-1BZ=C B b-1NNB=C -C B N-1kB P59-1-1-1-1-1-1-11211mB B(B P ,B P ,B 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，其它元素均为零的单位列向量，其它元素均为零的单位列向量，为主元列元素。为主元列元素。 iei-1kB P60假设假设 ，则则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主元素主元素61n改进单纯形法的步骤改进单纯形法的步骤（1 1）根据给出的线性规划问题的标准型，确定初始基变量和初）根据给出的线性规划问题的标准型，确定初始基变量和初始可行基。求初始可行基始可行基。求初始可行基B B的逆阵的逆阵-1-1，得初始基本可行解，得初始基本可行解。 （2 2）计算单纯形乘子）计算单纯形乘子 ，得目标函数当前值，得目标函数当前值（3 3） 计算非基变量检验数，计算非基变量检验数，若若N N00，则当前解已是最优解，停止计算；否则转下一步。，则当前解已是最优解，停止计算；否则转下一步。（4 4） 根据，确定非基变量为换入变量，根据，确定非基变量为换入变量，计算计算, ,若若0 0，则问题没有有限最优解，停止计算，则问题没有有限最优解，停止计算，否则转下一步。否则转下一步。-1B=C B-1NNBN=C -C B N=C -N-1BZ=C B b=b-1BNX =B b,X0jjkmax / 0 =kx-1kB P-1kB P62（5 5） 根据根据 ，确定基变量，确定基变量 为换出变量。为换出变量。 （6 6） 用替代用替代 得新基得新基1 1，由变换公式，由变换公式计算新基的逆阵计算新基的逆阵1 1-1-1，求出新的基本可行解，求出新的基本可行解 其中为变换矩阵，构造方法是：其中为变换矩阵，构造方法是： 从一个单位矩阵出发，把换出变量从一个单位矩阵出发，把换出变量 在基在基B B中的对应列的单位中的对应列的单位 向量，替换成换入变量向量，替换成换入变量 对应的系数列向量对应的系数列向量 ，并做如下变形，并做如下变形， 主元素主元素 （应在主对角线上）取倒数，其它元素除以主元素（应在主对角线上）取倒数，其它元素除以主元素 并取相反数。并取相反数。重复（重复（2 2）（）（6 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 Pxlkxkal63 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(B b)(B b)min/(B P ) 0 =(B P )(B P )ll初始基初始基maxZ=CXAX=bX0新基新基64 例例9 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 ,x65 （2 2）计算单纯行乘子）计算单纯行乘子 目标函数当前值目标函数当前值 （3 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） 选择换入变量选择换入变量 故故 为换入变量。计算为换入变量。计算jjmax / 0 = 3,2 =31xC = (3 ,2 ,0 ,0 )1 1 10A=210140b=60C = (3 ,2 ,0 ,0 )1 1 10A=210140b=60-1011011B P00122 66( () )确定换出变量确定换出变量确定确定 为换出变量，主元素为换出变量，主元素(6) (6) 用用 代替代替 得新可行基得新可行基 为基变量，为基变量， 为非基变量，为非基变量， 重复以上步骤，进入第二循环重复以上步骤，进入第二循环11003411010134BbBb40 6060min,122BPBP4xC = (3 ,2 ,0 ,0 )1 1 10A=210140b=60-1B040 X =B b=60-1011B P2 1P4P13111 B =(P ,P )=0231x ,x-1-11410-1-1111022B = E B =10110022C = (3 ,2 ,0 ,0 )1 1 10A=210140b=60-1B040 X =B b=6024x ,x-1121021011010267(1)(1)(2)(2)(3)(3)-1B11121214010X =B b=, X(30,0,10,0)60300T-1-11B13111132 =C B(c ,c )B(0,3)(0, )120211403Z = b = (0,)90602C = (3 ,2 ,0 ,0 )1 1 10A=210140b=6013111 B =(P ,P )=02-11-112B =102NN1241242410313 =C - N=(c ,c )- (P P )=(2,0)-(0,)=(, -)11222 C = (3 ,2 ,0 ,0 )1 1 10A=210140b=6013111 B =(P ,P )=02-11-112B =10268(4) (4) 选择选择 换入变量换入变量(5)(5) 选择选择 换出变量换出变量, ,主元素主元素(6) (6) 用用 代替代替 得新可行基得新可行基 为基变量，为基变量， 为非基变量，为非基变量， 进入第三循环进入第三循环. .2x-112111122B P0111022 11113111121231BbBb103010min,1/ 2 1/ 21/ 2BPBP3x-11231(B P )23P2P21x ,x-1-12321-11202-12B = E B =111-1102C = (3 ,2 ,0 ,0 )1 1 10A=210140b=60-1B110X =B b=3013111 B =(P ,P )=0222111 B =(P ,P )=121001 102112 20-1134x ,x69 (1)(1) (2) (2) (3) (3) 非基变量对应的检验数全部非正，非基变量对应的检验数全部非正， 故当前解故当前解 即为最优解，即为最优解， 相应的目标函数最优值相应的目标函数最优值 。-1B22214020X =B b=, X(20,20,0,0)116020T-1-12B221221 =C B(c ,c )B(2,3)(1, 1)112240Z = b = (1,1)10060NN2342343410 =C - N=(c ,c )- (P P )=(0,0)-(1,1)=(-1, -1)01 *2X =X =(20,20,0,0)TmaxZ100C = (3 ,2 ,0 ,0 )1 1 10A=210140b=60-122-1B =-1122111 B =(P ,P )=12