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

3 单纯形法单纯形法 p 单纯形法的一般原理单纯形法的一般原理 p 表格单纯形法表格单纯形法 p 借助人工变量求初始的基本可行解借助人工变量求初始的基本可行解1 单纯形法的一般步骤如下：单纯形法的一般步骤如下：（1 1）寻找一个寻找一个初始的基本可行解初始的基本可行解。（2 2）检查现行的基本可行解是否检查现行的基本可行解是否最优最优，如果为最优，如果为最优，则停止迭代，已找到最优解，否则转一步。则停止迭代，已找到最优解，否则转一步。（3 3）移至目标函数值有所改善的移至目标函数值有所改善的另一个基本可行解另一个基本可行解，然后转回到步骤（然后转回到步骤（2 2）。）。19471947年年，DantzigDantzig提提出出的的单单纯纯形形法法把把寻寻优优的的目目标标集集中在所有基本可行解（即可行域顶点）中。中在所有基本可行解（即可行域顶点）中。2一、引例一、引例用单纯形方法求解下列线性规划：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 03基本解如下表基本解如下表 基基 基本解基本解 可行否可行否 目标值目标值 对应图中的点对应图中的点B1=（P1，P2）X1=（20，20，0，0）T 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 04（1）找初始可行基：B1=（P3，P4）现成的初始可行基；此时，XB=（x3，x4）T，XN=（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 。5（2）寻找可行）寻找可行基基B2，使其对应的基可行解使其对应的基可行解X（2）能使目标函数值增加。能使目标函数值增加。选：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 2 x2 +（1/2）x4问：X（2）是否最优呢？否因为：x2在目标函数中的系数为负，当x2，z 。6（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，P2线性无关，因此，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）是否最优呢？是，7从引例可以总结出求解过程：从引例可以总结出求解过程：（1）确定初始基及其基可行解；）确定初始基及其基可行解；（2）判断是否为最优解，是停止，否则）判断是否为最优解，是停止，否则转下一步；转下一步；（3）转换可行基，并求出相应的基可行）转换可行基，并求出相应的基可行解，使目标函数值有所改进，转（解，使目标函数值有所改进，转（2）。）。8n 确定初始的基本可行解确定初始的基本可行解 确定初始的基本可行解等价于确定初始的可行基，一旦初确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定始的可行基确定了，那么对应的初始基本可行解也就唯一确定.在在线线性性规规划划标标准准型型中中设设法法得得到到一一个个m m阶阶单单位位矩矩阵阵I I作作为为初初始始可行基。可行基。若在化标准形式前，若在化标准形式前，m m个约束方程都是个约束方程都是“”的形式，的形式，那么在化标准形时只需在一个约束不等式左端都加上一个那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量松弛变量x xn+in+i(i=12m)(i=12m)。9n判断现行的基本可行解是否最优判断现行的基本可行解是否最优 设有标准形式的线性规划问题：设有标准形式的线性规划问题：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即即 从上述约束方程中可以得到对应于从上述约束方程中可以得到对应于基基B的基可行解的基可行解X=（b1，b2，bm，0，0）T10用非基变量表示目标函数有：令令 有有 式中式中 j为基可行解X的检验数检验数。更一般性：更一般性：11n向量形式向量形式 假如已求得一个基本可行解假如已求得一个基本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值将这一基本可行解代入目标函数，可求得相应的目标函数值其中其中分别表示基变量和分别表示基变量和非基变量所对应的价值系数子向量。非基变量所对应的价值系数子向量。12要判定是否已经达到最小值，只需将要判定是否已经达到最小值，只需将代入目标函数，使目标函数用非代入目标函数，使目标函数用非基变量基变量表示，即：表示，即：其中其中 称为非基变量称为非基变量N N的的检验向量检验向量，它的各个分量称为检验数。若，它的各个分量称为检验数。若N N的每一个检验数均小于的每一个检验数均小于等于等于0 0，即，即N N 0 0，那么现在的基本可行解就是最优解。，那么现在的基本可行解就是最优解。13定理定理1 1：最优解判别定理最优解判别定理 对于线性规划问题对于线性规划问题若某个基本可行解所对应的检验向量，若某个基本可行解所对应的检验向量，则这个基本可行解就是则这个基本可行解就是最优解最优解。定理定理2 2：无穷多最优解无穷多最优解判别定理判别定理 若是一个基本可行解，所对应的检验向量若是一个基本可行解，所对应的检验向量，其中，其中存在一个检验数存在一个检验数m+km+k=0=0，则线性规划问题有则线性规划问题有无穷多最优解无穷多最优解。14 定理定理3 3：无最优解（无界）判别定理：无最优解（无界）判别定理 若若 是一个基本可行解，有一个检验数是一个基本可行解，有一个检验数 ，但是但是 ，则该线性规划问题无最优解。，则该线性规划问题无最优解。证：令证：令 ，则得新的可行解，则得新的可行解将上式代入将上式代入因为因为 ,故当故当+时，时，ZZ。15 如果现行的基本可行解不是最优解，即在检验向量如果现行的基本可行解不是最优解，即在检验向量 中中存存在在正正的的检检验验数数，则则需需在在原原基基本本可可行行解解的的基基础上寻找一个新的基本可行解，并使目标函数值有所改善。础上寻找一个新的基本可行解，并使目标函数值有所改善。n 基本可行解的改进基本可行解的改进 具体做法是：具体做法是：先先从从检检验验数数为为正正的的非非基基变变量量中中确确定定一一个个换换入入变变量量，使使它它从从非非基基变量变成基变量（将它的值从零增至正值），变量变成基变量（将它的值从零增至正值），再再从从原原来来的的基基变变量量中中确确定定一一个个换换出出变变量量，使使它它从从基基变变量量变变成成非非基变量（将它的值从正值减至零）。基变量（将它的值从正值减至零）。由此可得一个新的基本可行解，由由此可得一个新的基本可行解，由 可知，这样的变换一定能使可知，这样的变换一定能使目标函数值有所减少目标函数值有所减少。16l换入变量的确定换入变量的确定 最大减少原则最大减少原则 假设检验向量假设检验向量 ，选取选取最大正检验数最大正检验数所对应的非基变量为所对应的非基变量为换入变量换入变量，即若，即若 则选取对应的则选取对应的 为换入变量，为换入变量，由于且为最大，由于且为最大，因此当由零增至正值，因此当由零增至正值，可使目标函数值可使目标函数值 最大限度的最大限度的减少减少。17l如果确定为换入变量，方程如果确定为换入变量，方程其中为中与对应的系数列向量。其中为中与对应的系数列向量。现在需在现在需在 中确定一个基变量为换中确定一个基变量为换出变量。出变量。l 换出变量的确定换出变量的确定 最小比值原则最小比值原则 l 当由零慢慢增加到某个值时，当由零慢慢增加到某个值时，的的非负性非负性可可能被打破。能被打破。为保持解的可行性，可以为保持解的可行性，可以按最小比值原则按最小比值原则确定换出变确定换出变量：量：若若则选取对应的基变量则选取对应的基变量 为换出变量。为换出变量。18单纯形表(1)19单纯形表(2)20计算步骤：（1）构造单纯形表1和2。（2）求 。（3）若 ，则此时基解就是最优解，否则转（4）。（4）若 ，则无最优解，否则转（5）。（5）求 。（6）以 为主元对初始单纯形表做换基运算得新单纯形表，转（2）。214 单纯形表单纯形表例例1 求解求解LP问题问题 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 2x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 RHSRHS22 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 2x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 RHSRHS 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检验数检验数检验数检验数转轴元转轴元转轴元转轴元23 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.5 最优解：最优解：最优解：最优解：x x*=(6.5,2.5,0.5,0,0)=(6.5,2.5,0.5,0,0)T T最优值：最优值：最优值：最优值：z z*=-1.5=-1.524例例2：解解解解LPLP问题问题问题问题4 单纯形表单纯形表25 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.5x x1 1 x x2 2 x x3 3 x x4 4 x x5 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.5 此问题无最优解此问题无最优解此问题无最优解此问题无最优解RHSRHS26例例3：解解解解LPLP问题问题问题问题4 单纯形表单纯形表27 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 4 6 3x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 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 6 此问题有多解。此问题有多解。此问题有多解。此问题有多解。RHSRHS28练习：1、用单纯形法求解 min z=6x14x2 2x1+3x2100 4x1+2x2120 x1、x20 2 2、用单纯形方法求解线性规划问题、用单纯形方法求解线性规划问题29因为非基变量因为非基变量x4的检验数的检验数 ，由无穷多最优解判别定理，由无穷多最优解判别定理，本例的线性规划问题存在本例的线性规划问题存在无穷多最优解无穷多最优解X*=（20，20，0，0）T，Z*=200最优解最优值最优解最优值30n无最优解无最优解 无最优解与无可行解时两个不同的概念。无最优解与无可行解时两个不同的概念。无无可可行行解解是是指指原原规规划划不不存存在在可可行行解解，从从几几何何的的角角度度解释是指线性规划问题的可行域为空集；解释是指线性规划问题的可行域为空集；无无最最优优解解则则是是指指线线性性规规划划问问题题存存在在可可行行解解，但但是是可可行行解解的的目目标标函函数数达达不不到到最最优优值值，即即目目标标函函数数在在可可行行域域内内可可以以趋趋于于无无穷穷小小（或或者者无无穷穷大大）。无无最最优优解解也也称称为为无有限最优解，或无界解。无有限最优解，或无界解。31p借助人工变量求初始的基本可行解借助人工变量求初始的基本可行解 假假定定我我们们下下面面研研究究的的线线性性规规划划都都是是非非退退化化的的，将将线线性性规规划划问问题题化化为为标标准准型型,如如果果约约束束方方程程组组中中包包含含有有一一个个单单位位矩阵矩阵I I，那么已经得到了一个那么已经得到了一个初始可行基初始可行基。否否则则在在约约束束方方程程组组的的左左边边加加上上若若干干个个非非负负的的人人工工变变量量，使使人人工工变变量量对对应应的的系系数数列列向向量量与与其其它它变变量量的的系系数数列列向向量量共共同同构构成成一一个个单单位位矩矩阵阵。以以单单位位矩矩阵阵为为初初始始基基，即即可可求求得得一一个个初始的基本可行解初始的基本可行解。32 首先将原问题化为标准型首先将原问题化为标准型添加人工变量，并在目标函数中分别赋予添加人工变量，并在目标函数中分别赋予 例例4:4:线性规划问题线性规划问题:33加加入入人人工工变变量量后后的的约约束束方方程程组组与与原原约约束束方方程程组是组是不等价不等价的。的。加加上上人人工工变变量量以以后后，线线性性规规划划的的基基本本可可行行解解不不一一定定是是原线性规划的问题的基本可行解。原线性规划的问题的基本可行解。只只有有当当基基本本可可行行解解中中所所有有人人工工变变量量都都为为取取零零值值的的非非基基变变量量时时，该该基基本本可可行行解解对对原原线线性性规规划划才才有有意意义义。因因为为此此时时只只需需去去掉掉基基本本可可行行解解中中的的人人工工变变量量部部分分，剩剩余余部部分分即即为为原原线线性性规规划划的的一一个个基基本本可可行行解解而而这这正正是是我我们们引引入入人人工工变变量量的主要目的。的主要目的。34初初始始基基本本可可行行解解 对对原原线线性性规规划划没没有有意意义义的的,但但是是我我们们可可以以从从X X(0)(0)出出发发进进行行迭迭代代，迭代结果有两种：迭代结果有两种：1.1.一一旦旦所所有有的的人人工工变变量量都都从从基基变变量量迭迭代代出出来来，变变成成只只能能取取零零值值的的非非基基变变量量，那那么么我我们们实实际际上上已已经经求求得得了了原原线线性性规规划划问问题题的的一一个个初初始始的的基基本本可可行行解解。此此时时可可以以把把所所有有人人工工变变量量剔除，开始正式进入求原线性规划最优解的过程。剔除，开始正式进入求原线性规划最优解的过程。2.2.如如果果最最优优单单纯纯形形表表的的基基变变量量中中仍仍含含有有人人工工变变量量，那那么么该线性规划就不存在可行解。该线性规划就不存在可行解。35n 大大M法法 以以后后的的计计算算与与单单纯纯形形表表解解法法相相同同，只只需需认认定定是是一一个个很大的正数很大的正数即可。即可。1.1.假假如如在在单单纯纯形形最最优优表表的的基基变变量量中中不不包包含含人人工工变变量量，则则最优解中剔除人工变量即为最优解中剔除人工变量即为原问题的最优基本可行解原问题的最优基本可行解。2.2.否则说明否则说明原问题无可行解原问题无可行解。为为了了求求得得原原问问题题的的初初始始基基本本可可行行解解，必必须须尽尽快快通通过过迭迭代代过过程程把把人人工工变变量量从从基基变变量量中中替替换换出出来来成成为为非非基基变变量量。为为此此可以在目标函数中可以在目标函数中赋予人工变量一个绝对值很大的系数赋予人工变量一个绝对值很大的系数。3637解：解：首先将原问题化为标准型首先将原问题化为标准型添加人工变量，并在目标函数中分别赋予添加人工变量，并在目标函数中分别赋予 例例5 5、用大、用大M M法求解下面的线性规划问题法求解下面的线性规划问题:38 x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 x x7 7 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 3RHSRHS39 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 2 x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 x x7 7 RHSRHS 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/240 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 x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 x x7 7 RHSRHS 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最优解最优解 最优值最优值41n无可行解无可行解 通通过过大大法法求求初初始始的的基基本本可可行行解解。但但是是如如果果在在大大法法的的最最优优单单纯纯形形表表的的基基变变量量中中仍仍含含有有人人工工变变量量，那那么么该该线性规划就不存在可行解。线性规划就不存在可行解。人人工工变变量量的的值值不不能能取取零零，说说明明了了原原线线性性规规划划的的数数学学模模型型的的约约束束条条件件出出现现了了相相互互矛矛盾盾的的约约束束方方程程。此此时时线线性性规划问题的规划问题的可行域为空集可行域为空集。42解：解：故引入人工变量，故引入人工变量，并利用大并利用大M M法求解法求解例例6 6、求解下列线性规划问题、求解下列线性规划问题43 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 01 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 6 4 3RHSRHS 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 344 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 RHSRHS z 0 0 3-3M 3-M -M 1-M 0 -1 15+M X1 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为为基基变变量量，所所以以原原线线性性规规划划不不存存在可行解。在可行解。45n两阶段法两阶段法 两两阶阶段段法法引引入入人人工工变变量量的的目目的的和和原原则则与与大大M M法法相相同同，所不同的是处理人工变量的方法。所不同的是处理人工变量的方法。两阶段法的步骤：两阶段法的步骤：1.求求解解一一个个辅辅助助线线性性规规划划。目目标标函函数数取取所所有有人人工工变变量量之之和，并取极小化；和，并取极小化；2.如如果果辅辅助助线线性性规规划划存存在在一一个个基基本本可可行行解解，使使目目标标函函数数的的最最小小值值等等于于零零，则则所所有有人人工工变变量量都都已已经经“离离基基”。表表明明原原问问题题已已经经得得了了一一个个初初始始的的基基本本可可行行解解，可可转转入入第第二二阶阶段段继续计算；继续计算；否则否则说明说明原问题没有可行解原问题没有可行解，可停止计算。，可停止计算。46第一阶段：第一阶段：加入人工加入人工变量量,构造初始可行基构造初始可行基.47用用单纯形法求解形法求解,若若g=0,进入第二入第二阶段段,否否则,原原问题无可行解。无可行解。第二第二阶段段：去掉人工：去掉人工变量，量，还原目原目标函数系数，做函数系数，做出初始出初始单纯形表。形表。48例：求解下列线性规划问题例：求解下列线性规划问题49将原将原问题化成化成标准型：准型：解解:化标准型化标准型用两阶段方法来求解。用两阶段方法来求解。50第一阶段第一阶段的线性规划问题为的线性规划问题为 x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 x x7 7 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 9RHSRHS51x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 x x7 7 RHS RHS g-2 4 0 0 -1 0 0 10 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 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 652 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 1x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 x x7 7 RHSRHS得原问题的基可行解得原问题的基可行解X=(1,3,0,0,0,)T。第二阶段：第二阶段：将上表中的人工变量去除，目标函数换成原问题的将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。目标函数从上表的最后一个单纯形表出发，继续计算。53 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 1x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 RHSRHS 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 154 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/2x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 RHSRHS得原标准线性规划问题的最优解得原标准线性规划问题的最优解X=（0，5/2，3/2，0，0）T，最优值是最优值是-3/2。所以最初的线性规划问题的最优解所以最初的线性规划问题的最优解X=（0，5/2，3/2）T，最优最优值是值是3/2。55例：求解下列线性规划问题例：求解下列线性规划问题56将原将原问题化成化成标准型：准型：解解:化标准型化标准型用两阶段方法来求解。用两阶段方法来求解。57第一阶段第一阶段的线性规划问题为的线性规划问题为x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 RHS RHS 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 358x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 RHS RHS 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 259x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 RHS RHS 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 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/560 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 x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 RHS RHS 第二阶段：第二阶段：将上表中的人工变量去除，目标函数换成原问题的将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。目标函数从上表的最后一个单纯形表出发，继续计算。61 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/5x x1 1 x x2 2 x x3 3 x x4 4 RHS RHS 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。62n无可行解无可行解 通通过过两两阶阶段段法法求求初初始始的的基基本本可可行行解解。但但是是如如果果两两阶阶段段法法的的辅辅助助线线性性规规划划的的目目标标函函数数的的极极小小值值大大于于零零，那那么么该该线线性性规规划划就就不不存存在在可行解可行解。人人工工变变量量的的值值不不能能取取零零，说说明明了了原原线线性性规规划划的的数数学学模模型型的的约约束束条条件件出出现现了了相相互互矛矛盾盾的的约约束束方方程程。此此时时线线性性规规划划问问题题的的可可行行域域为为空空集集。63例：求解下列线性规划问题例：求解下列线性规划问题64将原将原问题化成化成标准型：准型：解解:化标准型化标准型用两阶段方法来求解。用两阶段方法来求解。65第一阶段第一阶段的线性规划问题为的线性规划问题为x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 RHS RHS g 0 0 0 0 -1 -1 0 X5 X6 2 -3 -1 0 1 0 -1 1 0 -1 0 1 2 366x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 RHS RHS 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 0 1/2 0 0 -1/2 -1/2 -1 1/2 1 1 4原问题无解。原问题无解。67练习：练习：用两阶段法求解线性规划问题。用两阶段法求解线性规划问题。1 1、2 2、681、2、无可行解69n 退化与循环 循环产生的循环产生的原因原因：在在单单纯纯形形法法计计算算中中用用最最小小比比值值原原则则确确定定换换出出变变量量时时，有有时时存存在在两两个个或或两两个个以以上上相相同同的的最最小小比比值值，那那么么在在下下次次迭迭代代中中就就会会出出现现一一个个甚甚至至多多个个基基变变量量等等于于零零。当当某某个个基基变变量量为为零零，且且下下次次迭迭代代以以该该基基变变量量作作为为换换出出变变量量时时，目目标标函函数数并并不不能能因因此此得得到到任任何何改改变变（由由旋旋转转变变换换性性质质可可知知，任任何何一一个个换换入入变变量量只只能能仍仍取取零零值值，其其它它基基变变量量的的取取值值保保持持不不变变）。通通过过基基变变换换以以后后的的前前后后两两个个退退化化的的基基本本可可行行解解的的坐坐标标形形式式完完全全相相同同。从从几几何何角角度度来来解解释释，这这两两个个退退化化的的基基本本可可行行解解对对应应线线性性规规划划可可行行域域的的同同一一个个顶顶点点.当当线线性性规规划划问问题题的的基基本本可可行行解解中中有有一一个个或或多多个个基基变变量量取取零零值时，称此基本可行解为值时，称此基本可行解为退化解退化解。70Beale的例子的例子71解解决决的的办办法法：最最小小比比值值原原则则计计算算时时存存在在两两个个及及其其以以上上相相同同的的最最小小比比值值时时，选选取取下下标标最最大大的的基基变变量量为为换换出出变变量量，按按此此方方法法进进行行迭迭代代一一定定能能避避免免循循环环现现象象的的产产生生（摄摄动法原理）。动法原理）。72