最优化方法 第二章第二讲 单纯形法.ppt

1、13 单纯形法单纯形法 p 单纯形法的一般原理单纯形法的一般原理 p 表格单纯形法表格单纯形法 p 借助人工变量求初始的基本可行解借助人工变量求初始的基本可行解2 单纯形法的一般步骤如下：单纯形法的一般步骤如下：（1 1）寻找一个寻找一个初始的基本可行解初始的基本可行解。（2 2）检查现行的基本可行解是否检查现行的基本可行解是否最优最优，如果为最优，如果为最优，则停止迭代，已找到最优解，否则转一步。则停止迭代，已找到最优解，否则转一步。（3 3）移至目标函数值有所改善的移至目标函数值有所改善的另一个基本可行解另一个基本可行解，然后转回到步骤（然后转回到步骤（2 2）。）。19471947年，年

2、，DantzigDantzig提出提出的单纯形法把寻优的目标集的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。中在所有基本可行解（即可行域顶点）中。3 一、引例一、引例用单纯形方法求解下列线性规划：min z=6x14x2 2x1+3x2100 4x1+2x2120 x1、x20解：化为标准型 min z=6x14x2+0 x3+0 x4 2x1+3x2+x3 =100 4x1+2x2 +x4 =120 x1、x2，x3，x4 04 基本解如下表基本解如下表 基基 基本解基本解 可行否可行否 目标值目标值 对应图中的点对应图中的点B1=（P1，P2）X1=（20，20，0，0）T

3、 200 BB2=（P1，P3）X2=（30，0，40，0）T 180 CB3=（P1，P4）X3=（50，0，0，80）T DB4=（P2，P3）X4=（0，60，80，0）T EB5=（P2，P4）X5=（0，100/3，0，160/3）T 400/3 AB6=（P3，P4）X6=（0，0，100，120）T 0 OABCDEOx1x22x1+3x2=1004x1+2x2 =120 min z=6x14x2 2x1+3x2+x3 =100 4x1+2x2 +x4 =120 x1、x2，x3，x4 05（1）找初始可行基：B1=（P3，P4）现成的初始可行基；此时，XB=（x3，x4）T，X

4、N=（x1，x2）T用XN表示Z和XB有：min z=6x14x2 x3 =1002x13x2 +x4 =1204x12x2令 XN=(0,0)T有 XB=(100,120)T则有：X（1）=（0，0，100，120）T为对应于基B1的基可行解。问：X（1）是否最优呢？否 称非基变量在目标函数中的系数为系数为检验数。min z=6x14x2 2x1+3x2+x3 =100 4x1+2x2 +x4 =120 x1、x2，x3，x4 0因为：x1和x2在目标函数中的系数为负，当x1，z；x2，z 。6（2）寻找可行）寻找可行基基B2，使其对应的基可行解，使其对应的基可行解X（2）能使目标函数值增加

5、。能使目标函数值增加。选：x10则有：X（2）=（x1，0，x3，x4）Tmin z=6x14x2 x3 =1002x13x2 +x4 =1204x12x2要使为X（2）基可行解，x3，x4中必有一个为零，而另一个大等于零。只要取 x1=min100/2，120/4=30就有 x3=40，x4=0这样 X（2）=（30，0，40，0）T因为 P1，P3线性无关，因此，B2=（P1，P3）为一个基而 X（2）为对应于B2的基可行解此时 XB=（x1，x3）T，XN=（x2，x4）T用XN表示Z和XB有：min z=180 x2（3/2）x4 x1 =30（1/2）x2（1/4）x4 x3 =40

6、 2 x2 +（1/2）x4问：X（2）是否最优呢？否因为：x2在目标函数中的系数为负，当x2，z 。7（3）寻找可行）寻找可行基基B3，使其对应的基可行解，使其对应的基可行解X（3）能使目标函数值增加。能使目标函数值增加。选：x20则有：X（3）=（x1，x2，x3，0）T min z=180 x2（3/2）x4 x1 =30（1/2）x2（1/4）x4 x3 =40 2 x2 +（1/2）x4要使为X（3）基可行解，x1，x3中必有一个为零，而另一个大等于零。只要取 x2=min30/（1/2），40/2=20就有 x1=20，x3=0这样 X（3）=（20，20，0，0）T因为 P1，P

7、2线性无关，因此，B3=（P1，P2）为一个基而 X（3）为对应于B3的基可行解此时 XB=（x1，x2）T，XN=（x3，x4）T用XN表示Z和XB有：min z=200+（1/2）x3+（5/4）x4 x1 =20 +（1/4）x3 （3/8）x4 x2 =20 （1/2）x3+（1/4）x4问：X（3）是否最优呢？是，8从引例可以总结出求解过程：从引例可以总结出求解过程：（1）确定初始基及其基可行解；）确定初始基及其基可行解；（2）判断是否为最优解，是停止，否则）判断是否为最优解，是停止，否则转下一步；转下一步；（3）转换可行基，并求出相应的基可行）转换可行基，并求出相应的基可行解，使目

8、标函数值有所改进，转（解，使目标函数值有所改进，转（2）。）。9n 确定初始的基本可行解确定初始的基本可行解 确定初始的基本可行解等价于确定初始的可行基，一旦初确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定始的可行基确定了，那么对应的初始基本可行解也就唯一确定.在线性规划标准型中设法得到一个在线性规划标准型中设法得到一个m m阶单位矩阵阶单位矩阵I I作为初作为初始可行基。始可行基。若在化标准形式前，若在化标准形式前，m m个约束方程都是个约束方程都是“”的形式，的形式，那么在化标准形时只需在一个约束不等式左端都加上一个那么在化标准形时

9、只需在一个约束不等式左端都加上一个松弛变量松弛变量x xn+in+i(i=12(i=12m)m)。10n判断现行的基本可行解是否最优判断现行的基本可行解是否最优 设有标准形式的线性规划问题：设有标准形式的线性规划问题：min z=cX；AX=b，X0；现假定现假定 A中存在一可行基中存在一可行基B,且且B为单位阵为单位阵 这样这样 AX=b可以描述成如下形式，也就是用非基变量表示可以描述成如下形式，也就是用非基变量表示基变量基变量 x1 +a1,m+1xm+1+a1nxn=b1 x2 +a2,m+1xm+1+a2nxn=b2 xm+am,m+1xm+1+amnxn=bm即即 从上述约束方程中可

10、以得到对应于从上述约束方程中可以得到对应于基基B的基可行解的基可行解X=（b1，b2，bm，0，0）Tmixabxnmjjijii,1111 用非基变量表示目标函数有：nmjjjmiiinjjjxcxcxcz111111111()()mnniiijjjjij mj mmnmiiiijjjij mic ba xc xc bc acx 令令 有有 式中式中 j为基可行解X的检验数检验数。更一般性：更一般性：011;mmiijiijjiizcbc ac01njjjmzzx0;i ijiijji Si Szcbcac 0jjj Tzzx 12n向量形式向量形式 假如已求得一个基本可行解假如已求得一个基

11、本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值将这一基本可行解代入目标函数，可求得相应的目标函数值其中其中分别表示基变量和分别表示基变量和非基变量所对应的价值系数子向量。非基变量所对应的价值系数子向量。1B bX=01TTTT-1BNBB bZ=c X=(c)=c B b0cT12mNm+1m+2n=(c,c,c),c=(c,c,c)TBc13要判定是否已经达到最小值，只需将要判定是否已经达到最小值，只需将代入目标函数，使目标函数用非代入目标函数，使目标函数用非基变量基变量表示，即：表示，即：m+1m+2-1-1NNm+1,m+1,nnxxB b-XB b+()xTTBBcc 其

12、中其中 称为非基变量称为非基变量N N的的检验向量检验向量，它的各个分量称为检验数。若，它的各个分量称为检验数。若N N的每一个检验数均小的每一个检验数均小于等于于等于0 0，即，即N N 0 0，那么现在的基本可行解就是最优解。，那么现在的基本可行解就是最优解。-1-1BNX=B b-B NXT-1BZ=c B bT-1TNBNm+1m+1n=c B N-c=(,)BTTBNTT-1-1BBNBNNT-1T-1BBNXZ=c X=(c)X=c X+X=c(B b-B NX)+X=c B b-(c B N-)XTNTTNNTNcccc14定理定理1 1：最优解判别定理最优解判别定理 对于线性规

13、划问题对于线性规划问题若某个基本可行解所对应的检验向量，若某个基本可行解所对应的检验向量，则这个基本可行解就是则这个基本可行解就是最优解最优解。定理定理2 2：无穷多最优解无穷多最优解判别定理判别定理 若是一个基本可行解，所对应的检验向量若是一个基本可行解，所对应的检验向量，其中，其中存在一个检验数存在一个检验数m+km+k=0=0，则线性规划问题有则线性规划问题有无穷多最优解无穷多最优解。TnminZ=c X,D=XR/AX=b,X0T-1TNBN=c B N-c01B bX=0T-1TNBN=c B N-c0m+1m+2-1m+1,m+1,nnxxZB b-()xTBc15 定理定理3 3

14、：无最优解（无界）判别定理：无最优解（无界）判别定理 若若 是一个基本可行解，有一个检验数是一个基本可行解，有一个检验数 ，但是但是 ，则该线性规划问题无最优解。，则该线性规划问题无最优解。1B bX=0-1m+kB P0m+k0证：令证：令 ，则得新的可行解，则得新的可行解将上式代入将上式代入因为因为 ,故当故当+时，时，ZZ。-1-1-1-1Bm+km+km+kX=B b-B PxB b-B Pm+1T-1T-1Bm+1m+knBm+knxZ=C B b-(,)C B b-x m+kx,(0)m+k016 如果现行的基本可行解不是最优解，即在检验向量如果现行的基本可行解不是最优解，即在检验

15、向量 中存在中存在正的检验数正的检验数，则需在原基本可行解的基，则需在原基本可行解的基础上寻找一个新的基本可行解，并使目标函数值有所改善。础上寻找一个新的基本可行解，并使目标函数值有所改善。n 基本可行解的改进基本可行解的改进 具体做法是：具体做法是：先从检验数为正的先从检验数为正的非基变量非基变量中确定一个中确定一个换入变量换入变量，使它从非基，使它从非基变量变成基变量（将它的值从零增至正值），变量变成基变量（将它的值从零增至正值），再从原来的再从原来的基变量基变量中确定一个中确定一个换出变量换出变量，使它从基变量变成非，使它从基变量变成非基变量（将它的值从正值减至零）。基变量（将它的值从正

16、值减至零）。由此可得一个新的基本可行解，由由此可得一个新的基本可行解，由 可知，这样的变换一定能使可知，这样的变换一定能使目标函数值有所减少目标函数值有所减少。m+1m+2T-1Bm+1,m+1,nnxxZC B b+()xT-1TNBN=c B N-c17l换入变量的确定换入变量的确定 最大减少原则最大减少原则 假设检验向量假设检验向量 ，选取选取最大正检验数最大正检验数所对应的非基变量为所对应的非基变量为换入变量换入变量，即若，即若 则选取对应的则选取对应的 为换入变量，为换入变量，由于且为最大，由于且为最大，因此当由零增至正值，因此当由零增至正值，可使目标函数值可使目标函数值 最大限度的

17、最大限度的减少减少。T-1TNBBm+1m+2n=C B N-C=(,)jjm+kmax /0,m+1jn=m+kxm+kxm+k0m+1m+2T-1Bm+1,m+1,nnxxZC B b-()x18l如果确定为换入变量，方程如果确定为换入变量，方程其中为中与对应的系数列向量。其中为中与对应的系数列向量。现在需在现在需在 中确定一个基变量为换中确定一个基变量为换出变量。出变量。l 换出变量的确定换出变量的确定 最小比值原则最小比值原则 B12mX=(x,x,x)Tm+kxm+kPm+kxl 当由零慢慢增加到某个值时，当由零慢慢增加到某个值时，的的非负性非负性可可能被打破。能被打破。为保持解的可

18、行性，可以为保持解的可行性，可以按最小比值原则按最小比值原则确定换出变确定换出变量：量：若若-1-1-1im+ki-1-1m+kim+k(B b)(B b)min/(B P)0,1im=(B P)(B P)ll 则选取对应的基变量则选取对应的基变量 为换出变量。为换出变量。xlm+kxBX-1-1-1-1BNBm+km+kX=B b-B NXX=B b-B Px19单纯形表(1)XB XN RHS z-CBT-CNT 0 XB B N b 20单纯形表(2)21计算步骤：（1）构造单纯形表1和2。（2）求 。（3）若 ，则此时基解就是最优解，否则转（4）。（4）若 ，则无最优解，否则转（5）。

19、（5）求 。（6）以 为主元对初始单纯形表做换基运算得新单纯形表，转（2）。max|0ljj0l0lPmin|0kiilklilbbaaakla12(,)(,)()nijm nAB NP PPa224 单纯形表单纯形表例例1 求解求解LP问题问题23123234235min2.223120,1,2,3,4,5jzxxs txxxxxxxxxxj Z 0 1 -2 0 0 0 x1 x4 x5 1 -2 1 0 0 0 1 -3 1 0 0 1 -1 0 1 2 1 223 Z 0 1 -2 0 0 0 x1 x4 x5 1 -2 1 0 0 0 1 -3 1 0 0 1 -1 0 1 2 1

20、2 Z 0 0 1 -1 0 -1 x1 x2 x5 1 0 -5 2 0 0 1 -3 1 0 0 0 2 -1 1 4 1 124 Z 0 0 1 -1 0 -1 x1 x2 x5 1 0 -5 2 0 0 1 -3 1 0 0 0 2 -1 1 4 1 1 Z 0 0 0 -0.5 -0.5-1.5 x1 x2 x3 1 0 0 -0.5 2.5 0 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.525例例2：23145245345min21513.2221352221112220,1,2,3,4,5jzxxs txxxxxxxxxxj 4 单纯形表单纯形表

21、26 Z 0 1 2 0 0 0 x1 x2 x3 1 0 0 -0.5 2.50 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.5 Z 0 0 0 1.5 -2.5 -3.5 x1 x2 x3 1 0 0 -0.5 2.5 0 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.527例例3：513345235min18.436313220,1,2,3,4,5jzxs txxxxxxxxxj 4 单纯形表单纯形表28 Z 0 0 0 0 -1 18 x1 x4 x2 1 0 1 0 0 0 0 3 1 -1 0 1 -3/2 0 1/2

22、4 6 3 Z 0 0 0 0 -1 18 x1 x3 x2 1 0 0 -1/3 1/3 0 0 1 1/3 -1/3 0 1 0 1/2 0 2 2 629练习：1、用单纯形法求解 min z=6x14x2 2x1+3x2100 4x1+2x2120 x1、x20 2 2、用单纯形方法求解线性规划问题、用单纯形方法求解线性规划问题121324125jminZ=-x-2xxx4xx3x2xx8x0 j1,2,3,4,5，30因为非基变量因为非基变量x4的检验数的检验数 ，由无穷多最优解判别定理，由无穷多最优解判别定理，本例的线性规划问题存在本例的线性规划问题存在无穷多最优解无穷多最优解X*=

23、（20，20，0，0）T，Z*=200最优解最优值最优解最优值X2,3,2,0,0T minZ=-84031n无最优解无最优解 无最优解与无可行解时两个不同的概念。无最优解与无可行解时两个不同的概念。无可行解是指原规划不存在可行解，从几何的角度无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集；解释是指线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷小（或者无穷大）。无最优解也称为内可以趋于无穷

24、小（或者无穷大）。无最优解也称为无有限最优解，或无界解。无有限最优解，或无界解。32p借助人工变量求初始的基本可行解借助人工变量求初始的基本可行解 假定我们下面研究的线性规划都是假定我们下面研究的线性规划都是非退化非退化的，将线性的，将线性规划问题化为标准型规划问题化为标准型,如果约束方程组中包含有一个如果约束方程组中包含有一个单位单位矩阵矩阵I I，那么已经得到了一个那么已经得到了一个初始可行基初始可行基。否则在约束方程组的左边加上若干个非负的否则在约束方程组的左边加上若干个非负的人工变量人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共使人工变量对应的系数列向量与其它变量的系数列

25、向量共同构成一个同构成一个单位矩阵单位矩阵。以单位矩阵为初始基，即可求得一。以单位矩阵为初始基，即可求得一个个初始的基本可行解初始的基本可行解。33121212212minZ=x-2xxx2-xx1 x3 x,x0 首先将原问题化为标准型首先将原问题化为标准型12312425j xx-x 2-xx -x 1 x x3 x0,j1,2,3,4,512671236124725jminZ=x-2x+Mx+Mx xx -x x 2-xx -x x1 x x 3 x0,j1,2,3,4,5,6,7添加人工变量，并在目标函数中分别赋予添加人工变量，并在目标函数中分别赋予 67x,x例例4:4:线性规划问题

26、线性规划问题:34加入人工变量后的约束方程组与原约束方程加入人工变量后的约束方程组与原约束方程组是组是不等价不等价的。的。加上人工变量以后，线性规划的基本可行解不一定是加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问题的基本可行解。原线性规划的问题的基本可行解。只有当基本可行解中所有只有当基本可行解中所有人工变量都为取零值的非基人工变量都为取零值的非基变量变量时，该基本可行解对原线性规划才有意义。因为此时时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解而这正是我

27、们引入人工变量线性规划的一个基本可行解而这正是我们引入人工变量的主要目的。的主要目的。35初始基本可行解初始基本可行解 对原对原线性规划没有意义的线性规划没有意义的,但是我们可以从但是我们可以从X X(0)(0)出发进行迭代，出发进行迭代，迭代结果有两种：迭代结果有两种：1.1.一旦所有的一旦所有的人工变量人工变量都从基变量迭代出来，都从基变量迭代出来，变成只能变成只能取零值的非基变量取零值的非基变量，那么我们实际上已经求得了，那么我们实际上已经求得了原线性规原线性规划问题划问题的一个的一个初始的基本可行解初始的基本可行解。此时可以把所有人工变。此时可以把所有人工变量剔除，开始正式进入求原线性

28、规划最优解的过程。量剔除，开始正式进入求原线性规划最优解的过程。2.2.如果如果最优单纯形表的基变量中仍含有人工变量最优单纯形表的基变量中仍含有人工变量，那么，那么该线性规划就不存在可行解。该线性规划就不存在可行解。(0)12mX=(0,0,0,b,b,b)Tni jjij=1j a x =b ,i=1,2,.,m x0,j=1,2,.,nnijjn+iij=1j a x+x=b ,i=1,2,.,m x0,j=1,2,.,n+m36n 大大M法法 以后的计算与单纯形表解法相同，只需认定是一个以后的计算与单纯形表解法相同，只需认定是一个很大的正数很大的正数即可。即可。1.1.假如在单纯形假如在

29、单纯形最优表最优表的基变量中的基变量中不包含人工变量不包含人工变量，则则最优解中剔除人工变量即为最优解中剔除人工变量即为原问题的最优基本可行解原问题的最优基本可行解。2.2.否则说明否则说明原问题无可行解原问题无可行解。为了求得原问题的为了求得原问题的初始基本可行解，必须尽快通过迭代初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中可以在目标函数中赋予人工变量一个绝对值很大的系数赋予人工变量一个绝对值很大的系数。37njjj=1ni jjij=1jminZ=c x a x =b ,i=1,2,.,

30、m x0,j=1,2,.,nnn+mjjjj=1j=n+1nijjn+iij=1jminZ=c xx a x+x=b ,i=1,2,.,m x0,j=1,2,.,n+mM38解：解：首先将原问题化为标准型首先将原问题化为标准型添加人工变量，并在目标函数中分别赋予添加人工变量，并在目标函数中分别赋予 121212212minZ=x-2xxx2-xx1 x3 x,x012312425j xx-x 2-xx -x 1 x x3 x0,j1,2,3,4,512671236124725jminZ=x-2x+Mx+Mx xx -x x 2-xx -x x1 x x 3 x0,j1,2,3,4,5,6,76

31、7x,x例例5 5、用大、用大M M法求解下面的线性规划问题法求解下面的线性规划问题:39 z -1 2 0 0 0 -M -M 0 X6 X7 X5 1 1 -1 0 0 1 0-1 1 0 -1 0 0 1 0 1 0 0 1 0 0 2 1 3 z-1 2+2M -M -M 0 0 0 3M X6 X7 X5 1 1 -1 0 0 1 0-1 1 0 -1 0 0 1 0 1 0 0 1 0 0 2 1 340 z 1+2M 0 -M 2+M 0 0 -2-2M M-2 X6 X2 X5 2 0 -1 1 0 1 -1-1 1 0 -1 0 0 1 1 0 0 1 1 0 -1 1 1

32、2 z 0 0 1/2 3/2 0 -M -3/2-M -5/2 X1 X2 X5 1 0 -1/2 1/2 0 1/2 -1/2 0 1 -1/2 -1/2 0 1/2 1/2 0 0 1/2 1/2 1 -1/2 -1/2 1/2 1/2 3/241 z-3 0 2 0 0 -2-M -M -4 X4 X2 X5 2 0 -1 1 0 1 -1 1 1 -1 0 0 1 0-1 0 1 0 1 -1 0 1 2 1 z-1 0 0 0 -2 -M -M -6 X4 X2 X3 1 0 0 1 1 0 -1 0 1 0 0 1 0 0-1 0 1 0 1 -1 0 2 3 1最优解最优解 最

33、优值最优值X0,3,1,2,0TZ642n无可行解无可行解 通过大法求初始的基本可行解。但是如果在大通过大法求初始的基本可行解。但是如果在大法的法的最优单纯形表的基变量中仍含有人工变量最优单纯形表的基变量中仍含有人工变量，那么该，那么该线性规划就不存在可行解。线性规划就不存在可行解。人工变量的值不能取零，说明了原线性规划的数学人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的规划问题的可行域为空集可行域为空集。431231231323123minZ=3x+2x+xxxx6x -x4 x-x3x,

34、x,x 0解：解：12378123413572368jMMminZ=3x+2x+x+x+xx+x+x+x =6x -x -x +x =4 x -x -x +x=3x0,j=1,2,8.故引入人工变量，故引入人工变量，并利用大并利用大M M法求解法求解78x,x1231234135236jminZ=3x+2x+xx+x+x+x =6x -x -x =4 x -x -x =3x0,j=1,2,6.例例6 6、求解下列线性规划问题、求解下列线性规划问题44 x1 x2 x3 x4 x5 x6 x7 x8 z-3 -2 -1 0 0 0 -M -M 0 X4 X7 X8 1 1 1 1 0 0 0 0

35、1 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 6 4 3 z-3+M -2+M -1-2M 0 -M -M 0 0 7M X4 X7 X8 1 1 1 1 0 0 0 0 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1 6 4 345 z-3+M 0 -3-M 0 -M -2 0 2-M 6+4M X4 X7 X2 1 0 2 1 0 1 0 -1 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1 6 4 3 x1 x2 x3 x4 x5 x6 x7 x8 z 0 0 3-3M 3-M -M 1-M 0 -1 15+M X1

36、 X7 X21 0 2 1 0 1 0 -10 0 -3 -1 -1 -1 1 10 1 -1 0 0 -1 0 1 3 1 3 在以上最优单纯形表中，所有非基变量检验数都小于零，在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量但在该表中人工变量x7=1为基变量，所以原线性规划不存为基变量，所以原线性规划不存在可行解。在可行解。46n两阶段法两阶段法 两阶段法引入人工变量的目的和原则与大两阶段法引入人工变量的目的和原则与大M M法相同，法相同，所不同的是处理人工变量的方法。所不同的是处理人工变量的方法。两阶段法的步骤：两阶段法的步骤：1.求解一个求解一个辅助线性规划辅助线性

37、规划。目标函数取所有人工变量之。目标函数取所有人工变量之和，并取极小化；和，并取极小化；2.如果辅助线性规划存在一个基本可行解，使目标函数如果辅助线性规划存在一个基本可行解，使目标函数的最小值的最小值等于零等于零，则，则所有人工变量所有人工变量都已经都已经“离基离基”。表明。表明原问题已经得了一个原问题已经得了一个初始的基本可行解初始的基本可行解，可转入第二阶段，可转入第二阶段继续计算；继续计算；否则否则说明说明原问题没有可行解原问题没有可行解，可停止计算。，可停止计算。47第一阶段：第一阶段：加入人工变量加入人工变量,构造初始可行基构造初始可行基.1111221112112222221122

38、121,.,.,.,nnnnnnmmmnnn mmnnn ma xa xa xxba xa xa xxbaxaxaxxbx xxxx 0 12min g.nnnmxxx 48用单纯形法求解用单纯形法求解,若若g=0,进入第二阶段进入第二阶段,否则否则,原问原问题无可行解。题无可行解。第二阶段第二阶段：去掉人工变量，还原目标函数系数，做：去掉人工变量，还原目标函数系数，做出初始单纯形表。出初始单纯形表。491312312323123m ax342139,0zxxxxxxxxxxxxx 例：求解下列线性规划问题例：求解下列线性规划问题50将原问题化成标准型：将原问题化成标准型：1312312323

39、123max342139,0zxxxxxxxxxxxxx 131234123523min3421390,1,.5jzxxxxxxxxxxxxxj 化标准型化标准型用两阶段方法来求解。用两阶段方法来求解。51第一阶段第一阶段的线性规划问题为的线性规划问题为67123412356237min421390,1,.7jgxxxxxxxxxxxxxxxj g 0 0 0 0 0 -1 -1 0 X4 X6 X7 1 1 1 1 0 0 0-2 1 -1 0 -1 1 0 0 3 1 0 0 0 1 4 1 952 g-2 4 0 0 -1 0 0 10 X4 X6 X7 1 1 1 1 0 0 0-2

40、1 -1 0 -1 1 0 0 3 1 0 0 0 1 4 1 9 g 6 0 4 0 3 -4 0 6 X4 X2 X7 3 0 2 1 1 -1 0-2 1 -1 0 -1 1 0 6 0 4 0 3 -3 1 3 1 653 g 0 0 0 0 0 -1 -1 0 X4 X2 X1 0 0 0 1 -1/2 1/2 -1/2 0 1 1/3 0 0 0 1/3 1 0 2/3 0 1/2 -1/2 1/6 0 3 1得原问题的基可行解得原问题的基可行解X=(1,3,0,0,0,)T。第二阶段：第二阶段：将上表中的人工变量去除，目标函数换成原问题的将上表中的人工变量去除，目标函数换成原问题

41、的目标函数从上表的最后一个单纯形表出发，继续计算。目标函数从上表的最后一个单纯形表出发，继续计算。54 Z-3 0 1 0 0 0 X4 X2 X1 0 0 0 1 -1/2 0 1 1/3 0 0 1 0 2/3 0 1/2 0 3 1 Z 0 0 3 0 3/2 3 X4 X2 X1 0 0 0 1 -1/2 0 1 1/3 0 0 1 0 2/3 0 1/2 0 3 155 Z-9/2 0 0 0 -3/4-3/2 X4 X2 X3 0 0 0 1 -1/2-1/2 1 0 0 -1/4 3/2 0 1 0 3/4 0 5/2 3/2得原标准线性规划问题的最优解得原标准线性规划问题的最优

42、解X=（0，5/2，3/2，0，0）T，最优值是最优值是-3/2。所以最初的线性规划问题的最优解所以最初的线性规划问题的最优解X=（0，5/2，3/2）T，最优，最优值是值是3/2。56例：求解下列线性规划问题例：求解下列线性规划问题 0,3263433.4min2121212121xxxxxxxxtsxxz57将原问题化成标准型：将原问题化成标准型：化标准型化标准型用两阶段方法来求解。用两阶段方法来求解。0,3263433.4min2121212121xxxxxxxxtsxxz 0,3263433.4min43214213212121xxxxxxxxxxxxtsxxz58第一阶段第一阶段的线

43、性规划问题为的线性规划问题为 g 0 0 0 0 -1 -1 0 X5 X6 X4 3 1 0 0 1 0 4 3 -1 0 0 1 1 2 0 1 0 0 3 6 3 0,3263433.min654321421632152165xxxxxxxxxxxxxxxxtsxxg59 g 7 4 -1 0 0 0 9 X5 X6 X4 3 1 0 0 1 0 4 3 -1 0 0 1 1 2 0 1 0 0 3 6 3 g 0 5/3 -1 0 -7/3 0 2 X1 X6 X4 1 1/3 0 0 1/3 0 0 5/3 -1 0 -4/3 1 0 5/3 0 1 -1/3 0 1 2 260 g

44、 0 5/3 -1 0 -7/3 0 2 X1 X6 X4 1 1/3 0 0 1/3 0 0 5/3 -1 0 -4/3 1 0 5/3 0 1 -1/3 0 1 2 2 g 0 0 -1 -1 -2 0 0 X1 X6 X2 1 0 0 -1/5 2/5 0 0 0 -1 -1 -1 1 0 1 0 3/5 -1/5 0 3/5 0 6/561 g 0 0 0 0 -1 -1 0 X1 X3 X2 1 0 0 -1/5 2/5 0 0 0 1 1 1 -1 0 1 0 3/5 -1/5 0 3/5 0 6/5第二阶段：第二阶段：将上表中的人工变量去除，目标函数换成原问题的将上表中的人工变量

45、去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。目标函数从上表的最后一个单纯形表出发，继续计算。62 z-4 -1 0 0 0 X1 X3 X2 1 0 0 -1/5 0 0 1 1 0 1 0 3/5 3/5 0 6/5 z 0 0 0 -1/518/5 X1 X3 X2 1 0 0 -1/5 0 0 1 1 0 1 0 3/5 3/5 0 6/5所以最初的线性规划问题的最优解所以最初的线性规划问题的最优解X=(3/5，6/5)T，最优值是最优值是18/5。63n无可行解无可行解 通过两阶段法求初始的基本可行解。但是如果两阶段法的通过两阶段法求初始的基本可行解。但是

46、如果两阶段法的辅辅助线性规划助线性规划的目标函数的的目标函数的极小值大于零极小值大于零，那么该线性规划就，那么该线性规划就不存在不存在可行解可行解。人工变量的值不能取零，说明了原线性规划的数学模型的约束人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的条件出现了相互矛盾的约束方程。此时线性规划问题的可行域为空可行域为空集集。64例：求解下列线性规划问题例：求解下列线性规划问题 0,3232.42min21212121xxxxxxtsxxz65将原问题化成标准型：将原问题化成标准型：化标准型化标准型用两阶段方法来求解。用两阶段方法来求解。0,3

47、232.42min21212121xxxxxxtsxxz 0,3232.42min432142132121xxxxxxxxxxtsxxz66第一阶段第一阶段的线性规划问题为的线性规划问题为 g 0 0 0 0 -1 -1 0 X5 X6 2 -3 -1 0 1 0 -1 1 0 -1 0 1 2 3 0,3232.min6543216421532165xxxxxxxxxxxxxxtsxxg67 g 1 -2 -1 -1 0 0 5 X5 X6 2 -3 -1 0 1 0 -1 1 0 -1 0 1 2 3 g 0 -1/2 -1/2 -1 -1/2 0 4 X1 X6 1 -3/2 -1/2

48、0 1/2 0 0 -1/2 -1/2 -1 1/2 1 1 4原问题无解。原问题无解。68121212212minZ=x-2xxx2-xx1 x3 x,x0练习：练习：用两阶段法求解线性规划问题。用两阶段法求解线性规划问题。1 1、2 2、1231231323123minZ=3x+2x+xxxx6x -x4 x-x3x,x,x 0691、2、无可行解70n 退化与循环 循环产生的循环产生的原因原因：在单纯形法计算中用最小比值原则确定换出变量时，有在单纯形法计算中用最小比值原则确定换出变量时，有时存在时存在两个或两个以上相同的最小比值两个或两个以上相同的最小比值，那么在下次迭代中，那么在下次迭

49、代中就会出现一个甚至多个基变量等于零。就会出现一个甚至多个基变量等于零。当某个当某个基变量为零基变量为零，且下次迭代以该基变量且下次迭代以该基变量作为换出变量作为换出变量时，目标函数并不能因时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一个换入变量此得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可几何角度来解释，这两个退化

50、的基本可行解对应线性规划可行域的同一个顶点行域的同一个顶点.当线性规划问题的基本可行解中有一个或多个当线性规划问题的基本可行解中有一个或多个基变量基变量取取零零值时，称此基本可行解为值时，称此基本可行解为退化解退化解。711234123451234637j31minS=-x+150 x-x+6x45011x-60 x-x+9x+x =042511x-90 x-x+3x+x =0250 x +x=1x0,j=1,2,7.Beale的例子的例子72解决的办法：最小比值原则计算时存在两个及其以解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变上相同的最小比值