6.4.4单纯形法ppt课件

1、6.4.4 6.4.4 单纯形法单纯形法 p 单纯形法的一般原理 p 表格单纯形法 p 借助人工变量求初始的基本可行解p 单纯形表与线性规划问题的讨论p 改进单纯形法 例题6.8 MAX Z=250X1+500X2 S.T. 20X1+50X2=1000 20X1+10X2=0求解1：确定初始基可行解 20X1+50X2+X3 =1000 20X1+10X2 +X4 =600 -250X1-500X2 -Z=0 X3=1000,X4=600,X1=X2=0,Z=0 引入松弛变量，得到增广矩阵，求出基可行解求解2：判别 -250X1-500X2 -Z=0 非基变量X1,X2的系数为负 基可行解X

2、3=1000,X4=600,X1=X2=0,不是最优解 Z=0不是最小值 非基变量为零才能得到最优解求解3：改良 20X1+50X2+X3 =1000 （1） 20X1+10X2 +X4 =600 （2） -250X1-500X2 -Z=0 （3） 0.4X1+X2+0.02X3 =20 （1） 16X1 -0.2X3+X4 =400 （2） -50X1 +10X -Z=0 （3）例题6.8 MAX Z=250X1+500X2 S.T. 20X1+50X2=1000 20X1+10X2=0 考虑到如下线性规划问题 其中一个mn矩阵，且秩为m，总可以被调整为一个m维非负列向量，为n维行向量，为n

3、维列向量。 根据线性规划基本定理： 如果可行域= n / =，0非空有界， 则上的最优目标函数值=一定可以在的一个顶点上达到。 这个重要的定理启发了Dantzig的单纯形法， 即将寻优的目标集中在D的各个顶点上。maxZ=CXAX=bX0p单纯形法的一般原理单纯形法的一般原理 Dantzig Dantzig的单纯形法把寻优的目标集中在所的单纯形法把寻优的目标集中在所有基本可行解即可行域顶点中。有基本可行解即可行域顶点中。其基本思路是从一个初始的基本可行解出发，其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。寻找一条达到最优基本可行解的最佳途径。 单纯单纯形法的一般

4、步骤如下：形法的一般步骤如下： （1 1寻找一个初始的基本可行解。寻找一个初始的基本可行解。 （2 2检查现行的基本可行解是否最优，如检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否则转果为最优，则停止迭代，已找到最优解，否则转一步。一步。 （3 3移至目标函数值有所改善的另一个基移至目标函数值有所改善的另一个基本可行解，然后转会到步骤本可行解，然后转会到步骤2 2）。）。 n 确定初始的基本可行解确定初始的基本可行解 确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定 为了讨论方便，不妨假设在标准型线性规划中，系数矩

5、阵中前m个系数列向量恰好构成一个可行基，即 =（），其中 =（1，2，m为基变量x1，x2，xm的系数列向量构成的可行基， =(m+1，Pm+2， Pn)为非基变量xm+1，xm+2， xn的 系数列向量构成的矩阵。 所以约束方程所以约束方程 就可以表示为就可以表示为BBNNXAX=(BN)=BX+NX=bX 用可行基的逆阵-1左乘等式两端，再通过移项可推得：若令所有非基变量, 则基变量由此可得初始的基本可行解1BbX=0AX=b-1-1BNX =B b-B NX-1BX =B bNX =0问题：要判断m个系数列向量是否恰好构成一个基并不是一件容易的事。基由系数矩阵中m个线性无关的系数列向量构

6、成。但是要判断m个系数列向量是否线性无关并非易事。即使系数矩阵中找到了一个基B，也不能保证该基恰好是可行基。因为不能保证基变量B=-1b0。为了求得基本可行解 ， 必须求基的逆阵-1。但是求逆阵-1也是一件麻烦的事。结论：在线性规划标准化过程中设法得到一个m阶单位矩阵I作为初始可行基，1B bX=0-1-1-1BNBNNBA X =bB X+N X =bX=Bb-BN XX =0,X=Bb 若在化标准形式前，约束方程中有若在化标准形式前，约束方程中有“”不等式，不等式， 那么在化标准形时除了在方程式左端减去剩余变量使不等那么在化标准形时除了在方程式左端减去剩余变量使不等式变成等式以外，还必须在

7、左端再加上一个非负新变量，称式变成等式以外，还必须在左端再加上一个非负新变量，称为人工变量为人工变量 若在化标准形式前，约束方程中有等式方程，那么可以直若在化标准形式前，约束方程中有等式方程，那么可以直接在等式左端添加人工变量。接在等式左端添加人工变量。为了设法得到一个为了设法得到一个m m阶单位矩阵阶单位矩阵I I作为初始可行基，作为初始可行基，可在线性规划标准化过程中作如下处理：可在线性规划标准化过程中作如下处理： 若在化标准形式前，m个约束方程都是“”的形式，那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量xn+i (i=12m)。n判断现行的基本可行解是否最优判断现行的基本可

8、行解是否最优 假如已求得一个基本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值将这一基本可行解代入目标函数，可求得相应的目标函数值其中分别表示基变量和非基变量所对应的价值系数子向量。1B bX=01-1BNBBbZ=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，那

9、么现在的基本可行解就是最优解。-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)X定理定理1 1：最优解判别定理：最优解判别定理 对于线性规划问题对于线性规划问题若某个基本可行解所对应的检验向量若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。，则这个基本可行解就是最优解。定理定理2 2：无穷多最优解判别定理：无穷多最优解判别定理 假设是一个基本可行解，所对应的检验假设

10、是一个基本可行解，所对应的检验向向量量 ，其中存在一个检验，其中存在一个检验数数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 ,nnxxZCBb + ()xn 基本可行解的改进基本可行解的改进 如果现行的基本可行解不是最优解，即在检验向量 中存在正的检验数，则需在原基本可行解的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：先从检验数为正的非基变量中确定一个换入变量，

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

12、增加原则”，即选取最大，即选取最大正检验数所对应的非基变量为换入变量，即若正检验数所对应的非基变量为换入变量，即若 则选取对应的则选取对应的 为换入变量，为换入变量， 由于由于 且为最大，且为最大， 因此当因此当 由零增至正值，由零增至正值，可使目标函数值可使目标函数值 最大限度的增加。最大限度的增加。-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

13、l 其中其中 为中与为中与 对应的系数列向量。对应的系数列向量。l 现在需在现在需在 中确定一个基变量为换出变量。中确定一个基变量为换出变量。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=Bb-BN XX=Bb-BPxm

14、+kPm+kxm+kx则选取对应的基变量则选取对应的基变量 为换出变量。为换出变量。 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+

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

16、向量把资源向量b b变换成变换成 。1B1BX =B b1B N1B bNX =0且改进了的基本可行解 只是在的基变量的基础上用一个换入变量替代其中一个换出变量，其它的基变量仍然保持不变。这些基变量的系数列向量是单位矩阵I中的单位向量。为了求得改进的基本可行解 ，只需对增广矩阵 施行初等行变换，将换入变量的系数列向量变换成换出变量所对应的单位向量即可。由于行初等变换后的方程组与原约束方程组 或 同解B-1-1NX(I,B N)=B bXAX=bX-1-1(I,BN ,Bb)BNX(B ,N )=bXX 可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成：C CBCN CB XB

17、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 123451234123512345maxZ=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

18、 = 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) (2) 检验检验 是否最优。是否最优。检验向量检验向量 因为因为1=31=3，3=4 3=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

19、,2,3)013417x X = (0,0,0, 8, 7 )T例例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 x

20、4 x5bXBCB 5 2 3 -1 1C（3 3基本可行解的改进基本可行解的改进 选取换入变量选取换入变量因为因为max3max3，4=44=4，取，取x3x3为换入变量。为换入变量。 选取换出变量选取换出变量 且且 ， 选取选取x4x4为换出变量为换出变量. .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 （4 4求改进了的基本可行

21、解求改进了的基本可行解 对约束方程组的增广矩阵施以初等行变换，使换入变量对约束方程组的增广矩阵施以初等行变换，使换入变量x3x3所对应的所对应的系数列向量系数列向量 变换成换出变量变换成换出变量x4x4所对应的单位向量所对应的单位向量 , , 注意保持基变量注意保持基变量x5x5的系数列向量的系数列向量 为单位向量不变。为单位向量不变。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)01

22、3417x 第一行除以第一行除以第二行减去第一行第二行减去第一行可得改进的基本可行解。 ， 基 变 量 ， 非 基 变 量。基本可行解目标函数值易见目标函数值比原来的Z=-1增加了， 再转向步骤(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-1301

23、32235x x124x ,x ,x换入变量，换出变量，为主元进行旋转变换换入变量，换出变量，为主元进行旋转变换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（2检验检验 是否最优。是否最优。检验向量检验向量由于，由于，所以仍不是最

24、优解。所以仍不是最优解。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 （3 3基本可行解的改进基本可行解的改进 选取换入变量选取换入变量由于，取为换入变量。由于，取为换入变量。 选取换出变量选取换出变量且且 ，选取为换出变量选取为换出变量. .433min,1/2 5/25/2X = (

25、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 （4 4求改进了的基本可行解求改进了的基本可行解 对约束方程组的增广矩阵施以初等行变换，使换入变量所对应对约束方程组的增广矩阵施以初等行变换，使换入变量所对应的系数列向量变换成换出变量所对应的单位向量的系数列向量变换成换出变量所对应的单位向量 , , 112P =5250P1 X1x5x111111041104 222

26、2665-12-11030135555223172-101 5555 66-12105555 13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 第二行乘以第二行乘以/第一行减以第二行的第一行减以第二行的/倍倍可得改进的基本可行解。 ，基变量，非基变量基本可行解目标函数值 比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

27、=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-12301310225555（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

28、-117xC =(3,5)x105555X =,X = x,B=,N=,b=C =(2,-1,1)x016-126x5555最优解最优解 最优值最优值 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/

29、5 2/56/5x15 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1Cp表格单纯形法表格单纯形法通过例我们发现，在单纯形法的求解过程中，有下列重要指标：每一个基本可行解的检验向量根据检验向量可以确定所求得的基本可行解是否为最优解。如果不是最优又可以通过检验向量确定合适的换入变量。每一个基本可行解所对应的目标函数值通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加，直至求得最优目标函数为止。 在单纯形法求解过程中，每一个基本可行解都以某个经过初等行变换的约束方程组中的单位矩阵为可行基。当=时，-1=，易知：-1NNB=C-C B N1BZ=C BbNNB=C-C

30、 NBZ=C b例例3 3、用单纯形方法求解线性规划问题、用单纯形方法求解线性规划问题解：本题的目标函数是求极小化的线性函数，解：本题的目标函数是求极小化的线性函数，可以令可以令那么那么这两个线性规划问题具有相同的可行域和最优解，这两个线性规划问题具有相同的可行域和最优解，只是目标函数相差一个符号而已。只是目标函数相差一个符号而已。 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/1

31、1 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- 因为非基变量x4的检验数4=0，由无穷多最优解判别定理，本例的线性规划问题存在无穷多最优解。事实上若以x4为换入变量，以x3为换出变量，再进行一次迭代，可得一下单纯形表：最优解最优解

32、 最优值最优值最优解的一般表示式最优解的一般表示式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 -1对于极小化的线性规划问题的处理：对于极小化的线性规划问题的处理：先化为标准型，即将极小化问题变换为极大化问题，然后利用单先化为标准型，即将极小化问题变换为极大化问题，然后利用单纯形方法求解纯形方法求解直接利用单纯形方法求解，但是检验是否最优

33、的准则有所不同，直接利用单纯形方法求解，但是检验是否最优的准则有所不同，即：即： 若某个基本可行解的所有非基变量对应的检验数若某个基本可行解的所有非基变量对应的检验数 （而不是（而不是），），则基本可行解为最优解则基本可行解为最优解否则采用最大减少原则而非最大增加原则来确定换入变量，否则采用最大减少原则而非最大增加原则来确定换入变量，即：即： 假设假设则选取对应的非基变量则选取对应的非基变量xm+kxm+k为换入变量为换入变量确定了换入变量以后，换出变量仍采用最小比值原则来确定。确定了换入变量以后，换出变量仍采用最小比值原则来确定。 NNB= C-CN0jjm+kmin / 0因因但但所以原问

34、题所以原问题无最优解无最优解1-1P=01-2n 退化解 当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。 产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值，那么在下次迭代中就会出现一个甚至多个基变量等于零。遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此得到任何改变由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点，解决的办

35、法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生摄动法原理）。例例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,

36、4,5,6,7567x ,x ,x000-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离基。离基。可得最优解可得最优

37、解 ，目标函数值，目标函数值maxZ=，X1,0,1,0,3Tn 无穷多最优解无穷多最优解 无穷多最优解判别原理：若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例：最优表：非基变量检验数，所以有无穷多最优解。最优解集为可行域两个顶点的凸组合：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改进单纯形法的特点改进单纯

38、形法的特点n 利用单纯形表求解线性规划时，每一次迭利用单纯形表求解线性规划时，每一次迭代都把整个单纯形表计算一遍，事实上我们关心代都把整个单纯形表计算一遍，事实上我们关心的只是以下一些数据：的只是以下一些数据：n基本可行解基本可行解 ，其相应的目标函数值，其相应的目标函数值 ，n非基变量检验数非基变量检验数 ，及其换入，及其换入变量变量 ，n 设设n主元列元素主元列元素 ，及其换出变量，及其换出变量 ，n设设n 利用它们可得到一组新的基变量以及新的可行利用它们可得到一组新的基变量以及新的可行基基1 1。1-1-1iki-11kik(B b)(B b)min/(B P ) 0, i (B P )

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

40、=C -C B N-1kB P-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假设当前基，假设当前基， 基变换中用非基变量取代基变量基变换中用非基变量取代基变量可得新基可得新基前后二个基相比仅相差一列，且前后二个基相比仅相差一列，且比较以上二式，可得比较以上二式，可得 xl1121k1m

41、B(P,P ,P ,P ,P ,P )llkx其中表示第个元素为其中表示第个元素为1 1，其它元素均为零的单位列向量，其它元素均为零的单位列向量，为主元列元素。为主元列元素。 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改进单纯形法的步骤改进单纯形法的步骤n（1 1）根

42、据给出的线性规划问题的标准型，）根据给出的线性规划问题的标准型，确定初始基变量和初始可行基。求初始可行基确定初始基变量和初始可行基。求初始可行基B B的逆阵的逆阵-1-1，得初始基本可行解，得初始基本可行解n。 n（2 2计算单纯形乘子计算单纯形乘子 ，得目标函数，得目标函数当前值当前值n（ 3 3 ） 计 算 非 基 变 量 检 验 数计 算 非 基 变 量 检 验 数，n若若N0N0，则当前解已是最优解，停止计算；，则当前解已是最优解，停止计算；否则转下一步。否则转下一步。n（4 4） 根据，确定非基变根据，确定非基变量为换入变量，计算量为换入变量，计算, ,假设假设00，则问题没有有限最

43、优解，停止计算，则问题没有有限最优解，停止计算，n否则转下一步。否则转下一步。-1B=C B-1NNBN=C -C B N=C -N-1BZ=C B b=b-1BNX =B b,X0jjkmax / 0 =kx-1kB P-1kB P（5 5） 根据根据 ，确定基变量，确定基变量 为换出变量。为换出变量。 （6 6） 用替代用替代 得新基得新基1 1，由变换公式，由变换公式计算新基的逆阵计算新基的逆阵1-11-1，求出新的基本可行解，求出新的基本可行解 其中为变换矩阵，构造方法是：其中为变换矩阵，构造方法是： 从一个单位矩阵出发，把换出变量从一个单位矩阵出发，把换出变量 在基在基B B中的对应

44、列的单位中的对应列的单位 向量，替换成换入变量向量，替换成换入变量 对应的系数列向量对应的系数列向量 ，并做如下变形，并做如下变形， 主元素主元素 （应在主对角线上取倒数，其它元素除以主元素（应在主对角线上取倒数，其它元素除以主元素 并取相反数。并取相反数。反复反复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 Pxlkxkal B=I-1BNX =B b,X0-1B=C BZ=bNN=C -Nkx换入换入-1kB P无界

45、解无界解换出换出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新基新基 例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 -