第5章 单纯形法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,1,第五章 单 纯 形 法,1,单纯形法的基本思路和原理,2,单纯形法的表格形式,3,求目标函数值最小的线性规划的问题的,单纯形表解法,4,几种特殊情况,2,单纯形法,单纯形法不是最好的算法，但是一种非常适用的算法,基本思路：,从可行域某个顶点开始，判断是否为最优解，若不是则再找另一个使目标函数更优的顶点（称之为迭代），再判断是否为最优解，直到找到一个顶点为其最优解（或者判断无最优解）为止。,单纯形法中可行域的顶点叫,基本可行解,找到的第一个可行域的顶点叫,初始基本可行解,3,1,单纯形法的基本思路和原理,引例（第二章例）,目标函数：,Max z = 50 x1 + 100 x2,约束条件：,s.t,. x1 + x2 300,2 x1 + x2 400,x2 250,x1 , x2 0,标准形式为：,目标函数：,Max z = 50 x,1,+ 100 x,2,+ 0 s,1,+ 0 s,2,+ 0 s,3,约束条件：,s.t,. x,1,+ x,2,+ s,1,= 300,2 x,1,+ x,2,+ s,2,= 400,x,2,+ s,3,=,250,x,1, x,2, s,1, s,2, s,3, 0,4,1,单纯形法的基本思路和原理,三个约束方程的系数矩阵为：,其中,pj,为系数矩阵,A,中第列的列向量,A,的秩,m,（,3,）小于此方程组的变量的个数,n,（,5,），即有无数多解。,为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。,5,1,单纯形法的基本思路和原理,基,：,已知,A,是约束条件的,m,n,系数矩阵，其秩为,m,。若,B,是,A,中,m,m,阶非奇异子矩阵（即可逆矩阵， ），则称,B,是线性规划问题中的一个基。（注：,B,是,A,中个线性无关的系数列向量组成的。）,基向量,：,基,B,中的一列即称为一个基向量。基,B,中共有,m,个基向量。,非基向量,：,在,A,中除了基,B,之外的一列则称之为基,B,的非基向量。,基变量：,与基向量,pi,相应的变量,xi,叫基变量，基变量有,m,个。,非基变量：,与非基向量,pj,相应的变量,xj,叫非基变量，非基变量有,n,m,个。,6,1,单纯形法的基本思路和原理,基,基向量和非基向量,向量是基的基向量，也是基和基的非基向量,向量是基和基的基向量，也是基的非基向量,基变量和非基变量,都是的基变量，是的非基变量,7,1,单纯形法的基本思路和原理,基本解：,如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个,m,元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。,8,1,单纯形法的基本思路和原理,基本解,在此例中我们不妨找到了,为,A,的一个基，令这个基的,非基变量,x,，,s,2,为零。这时约束方程就变为基变量的约束方程,：,x,2,+s,1,300,，,x,2,=400,，,x,2,+s,3,=250.,求解得到此线性规划的一个基本解：,x,1,=0,，,x,2,=400,，,s,1,=,100,，,s,2,=0,，,s,3,=,150,9,1,单纯形法的基本思路和原理,基本可行解：,所有变量的解基本可行解足非负的条件的一个基本解叫做基本可行解。,（一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。）,可行基：,能够得到,基本可行解的基叫做可行基。,10,1,单纯形法的基本思路和原理,由于在这个基本解中,s,1,=,100,，,s,3,=,150,，不满足该线性规划,s,1,0,，,s,3,0,的约束条件，显然不是此线性规划的可行解。,因此不是可行基。,因此我们选基为，,令这个基的非基变量为零。,这时约束方程就变为,基变量的约束方程,：,求解得到此线性规划的一个基本解：,11,1,单纯形法的基本思路和原理,由于所有变量的解都大于等于零，可知此基本解为,基本可行解,。,因此，基是,可行基,。,=,=,目标函数,约束条件,行列式,0,基矩阵,右边常数,基变量,非基变量,12,1,单纯形法的基本思路和原理,初始可行基：,在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基。,初始基本可行解：,初始可行基,相应的基本可行解叫初始基本可行解。,13,一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。,我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？,由于在线性规划的标准型中要求,b,j,都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如，,那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向,量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个,b,j,或零。,1,单纯形法的基本思路和原理,14,在本例题中我们就找到了一个基是单位矩阵。,在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各,列向量所组成，称之为,初始可行基,，其相应的基本可行解叫,初始基本可行,解,。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行,基，我们将构造初始可行基，具体做法在以后详细讲述。,1,单纯形法的基本思路和原理,15,1,单纯形法的基本思路和原理,基,：,已知,A,是约束条件的,m,n,系数矩阵，其秩为,m,。若,B,是,A,中,m,m,阶非奇异子矩阵（即可逆矩阵， ），则称,B,是线性规划问题中的一个基。（注：,B,是,A,中个线性无关的系数列向量组成的。）,基向量,：,基,B,中的一列即称为一个基向量。基,B,中共有,m,个基向量。,非基向量,：,在,A,中除了基,B,之外的一列则称之为基,B,的非基向量。,基变量：,与基向量,p,i,相应的变量,x,i,叫基变量，基变量有,m,个。,非基变量：,与非基向量,p,j,相应的变量,x,j,叫非基变量，非基变量有,n,m,个。,基本解：,如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个,m,元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。,基本可行解：,所有变量的解基本可行解足非负的条件的一个基本解叫做基本可行解。,可行基：,能够得到,基本可行解的基叫做可行基。,初始可行基：,在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基。,初始基本可行解：,初始可行基,相应的基本可行解叫初始基本可行解。,16,二、 最优性检验,所谓最优性检验就是判断已求得的基本可行解是否是最优解。,1.,最优性检验的依据,检验数,j,一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求,只用非基变量来表示目标函数,，这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。,此时目标函数中所有变量的系数即为各变量的检验数,，把变量,x,i,的检验数记为,i,。显然所有基变量的检验数必为零。在本例题中目标函数为,50x,1,+100x,2,。由于初始可行解中,x,1,，,x,2,为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知,1,=50,，,2,=100,，,3,=0,，,4,=0,，,5,=0,。,1,单纯形法的基本思路和原理,17,1,单纯形法的基本思路和原理,2.,最优解判别定理,对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数 ,0,，则这个基本可行解是最优解。,下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式,由于所有的,x,j,的取值范围为大于等于零，当所有的 都小,于等于零时，可知 是一个小于等于零的数，要使,z,的值最大，显然 只有为零。我们把这些,x,j,取为非基,变量,(,即令这些,x,j,的值为零,),，所求得的基本可行解就使目标函数值最大为,z,0,。,*,对于求目标函数最小值的情况，只需把,0,改为 ,0,18,1,单纯形法的基本思路和原理,三、 基变换,通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进,行,基变换,找到一个新的可行基。,具体的做法：从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。,1.,入基变量的确定,把基检验数大于,0,的非基变量定为入基变量。若有两个以上的,j,0,，则选其中的,j,最大者的非基变量为入基变量。,从最优解判别定理知道，当某个,j,0,时，非基变量,x,j,变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于,0,的非基变量换到基变量中去（称之为入基变量）。若有两个以上的,j,0,，则为了使目标函数增加得更大些，一般选其中的,j,最大者的非基变量为入基变量，在本例题中,2,=100,是检验数中最大的正数，故选,x,2,为入基变量。,19,1,单纯形法的基本思路和原理,2.,出基变量,的确定,把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。,(1),若确定,s,1,为出基变量，则新的基变量为,x,2,，,s,2,，,s,3,。,可求出基本解,1,0,，,x2=300,，,s1=0,，,s2=100,，,s3=-50,，不是基本可行解，所以,s,1,不能作为出基变量。,(2),如果把,s3,作为出基变量，则新的基变量为,x2,，,s1,，,s2,，因为非基变量,x,1,=s,3,=0,，,我们也可以从下式：,x,2,+s,1,=300,，,x,2,+s,2,=400,，,x,2,=250,，,求出基本解：,x,1,=0,，,x,2,=250,，,s,1,=50,，,s,2,=150,，,s,3,=0,。因为此解满足非负,条件，是基本可行解，故,s,3,可以确定为出基变量。,20,1,单纯形法的基本思路和原理,我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方,程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所,在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变,换中可以确保新得到的,b,j,值都大于等于零。,在本例题中约束方程为,在第二步中已经知道,x,2,为入基变量，我们把各约束方程中,x,2,的为正的系数除,对应的常量，得,21,1,单纯形法的基本思路和原理,其中 的值最小，所以可以知道在原基变量中系数向量为,的基变量,s,3,为出基变量，这样可知,x,2,，,s,1,，,s,2,为基变量，,x,1,，,s,3,为非基变量。,令非基变量为零，得,x,2,+s,1,=300,x,2,+s,2,=400,x,2,=250.,求解得到新的基本可行解,x,1,=0,x,2,=250,s,1,=50,s,2,=150.,这时目标函数值为,50x,1,+100x,2,=50,0+100250=25000,。,显然比初始基本可行解,x,1,=0,x,2,=0,s,1,=300,s,3,=250,时的目标函数值为,0,要好,得多。,下面我们再进行检验其最优性，如果不是最优解还要继续进行基变,换，直至找到最优解，或者能够判断出线性规划无最优解为止。,22,基变换步骤,=,目标函数,约束条件,基矩阵,=,基变量,右边常数,23,=,入基变量,出基变量,目标函数,约束条件,右边常数,=,24,=,目标函数,约束条件,新的基矩阵,右边常数,=,25,2,单纯形法的表格形式,在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验,数 的表达式。,可行基为,m,阶单位矩阵的线性规划模型如下（假设其系数矩阵的前,m,列是单位矩阵）：,以下用 表示基变量，用,表示非基变量。,26,2,单纯形法的表格形式,把第,i,个约束方程移项，就可以用非基变量来表示基变量,x,i,，,把以上的表达式带入目标函数，就有,其中：,27,2,单纯形法的表格形式,上面假设,x,1,x,2,x,m,是基变量，即第,i,行约束方程的基变量正好是,x,i,，而,经过迭代后，基将发生变化，计算,z,j,的式子也会发生变化。如果迭代后的,第,i,行约束方程中的基变量为,x,Bi,，与,x,Bi,相应的目标函数系数为,c,Bi,，系数列,向量为 则,其中，,(,c,B,),是由第,1,列第,m,行各约束方程中的基变量相应的目标函数依,次组成的有序行向量。,单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、,迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，,而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来,求解第二章的例,1,。,max 50x,1,+100x,2,+0s,1,+0s,2,+0s,3,.,x,1,+x,2,+s,1,=300,，,2x,1,+x,2,+s,2,=400,，,x,2,+s,3,=250,，,x,1, x,2, s,1, s,2, s,3,0.,把上面的数据填入如下的单纯形表格,28,2,单纯形法的表格形式,按照线性规划模型在表中填入相对应的值，如上表所示；,在上表中有一个,m*m,的单位矩阵，对应的基变量为,s,1,s,2,s,3,；,在,z,j,行中填入第,j,列与,c,B,列中对应的元素相乘相加所得的值，如,z,2,=0*1+0*,1+0,*1=0,，所在,z,i,行中的第,2,位数填入,0,；,在 行中填入,c,j,-z,j,所得的值，如 ；,z,表示把初始基本可行解代入目标函数求得的目标函数值，即,b,列*,c,B,列；,初始基本可行解为,s,1,=300,s,2,=400,s,3,=250,x,1,=0,x,2,=0;,由于,250/1,最小，因此确定,s,3,为出基变量；,由于 ，因此确定,x,2,为入基变量。出基变量所在行，入基变量所在列的交汇处为,主元,，这里是,a,32,=1,，在表中画圈以示区别。,迭代次数,基变量,c,B,x,1,x,2,s,3,s,4,s,5,b,比值,B,i,/a,i2,50 100 0 0 0,0,s,1,s,2,s,3,0,0,0,1 1 1 0 0,2 1 0 1 0,0 1 0 0 1,300,400,250,300/1,400/1,250/1,z,j,0 0 0 0 0,50 100 0 0 0,z=0,29,2,单纯形法的表格形式,以下进行第一次迭代，其变量为,x,2,s,1,s,2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得,x,2,的系数向量,p,2,变换成单位向量，由于主元在,p,2,的第,3,分量上，所以这个单位向量是,也就是主元素变成,1,。这样我们又得到的第,1,次迭代的单纯表如下所示。,在上表中第,3,个基变量,s,1,已被,x,2,代替，故基变量列中的第,3,个基变量应变为,x,2,。由于第,0,次迭代表中的主元,a,32,已经为,1,，因此第,3,行不变。为了使第,1,行的,a,12,为,0,，只需把第,3,行*,(-1),加到第,1,行即可。同样可以求得第,2,行。,求得第,1,次迭代的基本可行解为,s,1,=50,s,2,=150,x,2,=250,x,1,=0,s,3,=0,z=25000.,迭代次数,基变量,c,B,x,1,x,2,s,3,s,4,s,5,b,比值,b,i,/,a,ij,50 100 0 0 0,1,s,1,s,2,x,2,0,0,100,1 0 1 0 -1,2 0 0 1 -1,0 1 0 0 1,50,150,250,50/1,150/2,z,j,0 100 0 0 100,50 0 0 0 -100,25000,30,2,单纯形法的表格形式,从上表可以看出，第一次迭代的 ，因此不是最优解。设,x,1,为入基变量，从此值可知,b,1,/a,11,=50,为最小正数，因此，,s,1,为出基变量，,a,11,为主元，继续迭代如下表所示。,从上表中可知第二次迭代得到的基本可行解为,x,1,=50,x,2,=250,s,1,=0,s,2,=50, s,3,=0,这时,z=27500,。,由于检验数都,0,，因此所求得的基本可行解为最优解，,z=27500,为最优目标函数值。,实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。,迭代次数,基变量,c,B,x,1,x,2,s,3,s,4,s,5,b,比值,b,i,/,a,ij,50 100 0 0 0,2,x,1,s,2,x,2,50,0,100,1 0 1 0 -1,0 0 -2 1 1,0 1 0 0 1,50,50,250,z,j,50 100 50 0 50,0 0 -50 0 -50,27500,知识回顾,单纯形法：,找到一个初始基本可行解,最优性检验,基变换,图解法的灵敏度分析,c,的灵敏度分析,b,的灵敏度分析,对偶价格,31,3,求目标函数值最小的线性规划的问题的单纯形表解法,一、大,M,法,以第二章的例,2,来讲解如何用单纯形表的方法求解目标函数值最小的线性规划问题。,例,2,某公司由于生产需要，共需要,A,，,B,两种原料至少,350,吨（,A,，,B,两种材料有一定替代性），其中,A,原料至少购进,125,吨。但由于,A,，,B,两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨,A,原料需要,2,个小时，加工每吨,B,原料需要,1,小时，而公司总共有,600,个加工小时。又知道每吨,A,原料的价格为,2,万元，每吨,B,原料的价格为,3,万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买,A,，,B,两种原料，使得购进成本最低？,33,3,求目标函数值最小的线性规划的问题的单纯形表解法,目标函数：,约束条件：,加入松弛变量和剩余变量，并转化目标函数，得到新的模型如下：,目标函数：,约束条件：,34,3,求目标函数值最小的线性规划的问题的单纯形表解法,由于在约束条件方程的系数矩阵里找不到,3,阶单位阵，所以加上人工变量，约束条件变为：,注意：人工变量与松弛、剩余变量不同，人工变量只能取零。,为了竭尽全力地要求人工变量为零，我们规定人工变量在目标函数中的系数为,M,（这里,M,为任意大的数）。这样只要人工变量,0,，所求的目标函数最大值就是一个任意小的数。这样为了使目标函数实现最大就必须把人工变量从基变量中换出。如果一直到最后，人工变量仍不能从基变量中换出，,也就是说人工变量仍不为零，则该问题无可行解。,35,3,求目标函数值最小的线性规划的问题的单纯形表解法,此例的数学模型如下所示,目标函数：,max z=,2x,1,3x,2,Ma,1,Ma,2.,约束条件：,x,1,+x,2,s,1,+a,1,=350,，,x,1,s,2,+a,2,=125,，,2x,1,+x,2,+s,3,=600,，,x,1,，,x,2,，,s,1,，,s,2,，,s,3,，,a,1,，,a,2,0.,像这样，为了构造初始可行基得到初始可行解，把人工变量,“,强行,”,地加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大值的目标函数里的系数为,M,，这个方法叫做,大,M,法,，,M,叫做,罚因子,。,36,3,求目标函数值最小的线性规划的问题的单纯形表解法,下面我们就用大,M,法来求解此题,:,迭代次数,基变量,c,B,x,1,x,2,s,1,s,2,s,3,a,1,a,2,b,比值,-2 -3 0 0 0 -M,-M,0,a,1,a,2,s,3,-M,-M,0,1 1 -1 0 0 1 0,1 0 0 -1 0 0 1,2 1 0 0 1 0 0,350,125,600,350/1,125/1,600/2,z,j,-2M -M M M 0 -M,-M,-2+2M -3+M -M,-M,0 0 0,-475M,1,a,1,x,1,s,3,-M,-2,0,0 1 -1 1 0 1 -1,1 0 0 -1 0 0 1,0 1 0 2 1 0 -2,225,125,350,225,-,350/2,z,j,-2 -M M -M+2 0 -M -M-2,0 -3+M -M M-2 0 0 2-2M,-225M-250,2,a,1,x,1,s,2,-M,-2,0,0 1/2 -1 0 -1/2 1 0,1 1/2 0 0 1/2 0 0,0 1/2 0 1 1/2 0 -1,50,300,175,50/1/2,300/1/2,175/1/2,z,j,-2 -1/2M-1 M 0 1/2M-1 -M 0,0 1/2M-2 -M 0 - 1/2M+1 0 -M,-50M-600,37,3,求目标函数值最小的线性规划的问题的单纯形表解法,从上表中可知检验数都小于零。已求得最优解为：,x,1,=250,x,2,=100,s,1,=0, s,2,=125,s,3,=0,a,1,=0,a,2,=0,，其最优值为,f=-z=-(-800)=800,。,迭代次数,基变量,c,B,x,1,x,2,s,1,s,2,s,3,a,1,a,2,b,比值,-2 -3 0 0 0 -M,-M,3,x,2,x,1,s,2,-3,-2,0,0 1 -2 0 -1 2 0,1 0 1 0 1 -1 0,0 0 1 1 1 -1,-1,100,250,125,z,j,-2 -3 4 0 1 -4 0,0 0 -4 0 -1 -M+4 -M,-800,38,4,几种特殊情况,一、无可行解,（判断方法：最优解里人工变量不为,0,）,例,1,、用单纯形表求解下列线性规划问题,解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：,填入单纯形表计算得：,39,4,几种特殊情况,迭代次数,基变量,C,B,x,1,x,2,s,1,s,2,s,3,a,1,b,比值,20 30 0 0 0 -M,0,s,1,s,2,a,1,0,0,-M,3,10,1 0 0 0,1 0 0 1 0 0,1 1 0 0 -1 1,150,30,40,150/10,40/1,z,j,c,j,-z,j,-M,-M,0 0 M -M,20+M 30+M 0 0 -M 0,-40M,1,x,2,s,2,a,1,30,0,-M,3/10 1 1/10 0 0 0,1,0 0 1 0 0,7/10 0 -1/10 0 -1 1,15,30,25,15/(3/10),30/1,25/(7/10),z,j,c,j,-z,j,9-7/10M 30 3+M/10 0 M -M,11+7/10M 0 -3-M/10 0 -M 0,450-25M,2,x,2,x,1,a,1,30,20,-M,0 1 1/10 -3/10 0 0,1 0 0 1 0 0,0 0 -1/10 -7/10 -1 1,6,30,4,z,j,c,j,-z,j,20 30 3+M/10 11+7M/10 M -M,0 0 -3-M/10 -11-7M/10 -M 0,780-4M,40,4,几种特殊情况,从第二次迭代的检验数都小于零来看，可知第,2,次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为,780-4M,。我们把最优解,x,1,=30,x,2,=6,s,1,=0,s,2,=0,s,3,=0,a,1,=4,代入第三个约束方程得,x,1,+x,2,-0+4=40,即有：,x,1,+x,2,=3640.,并不满足原来的约束条件,3,，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。,像这样只要求线性规划的,最优解里有人工变量大于零,，则此线性规划无可行解。,41,4,几种特殊情况,二、无界解,（判断方法：无法判断出基变量）,在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取任意的大。下面我们用单纯形表来求第二章中的例子。,例,2,、用单纯形表求解下面线性规划问题。,42,4,几种特殊情况,迭代次数,基变量,C,B,x,1,x,2,s,1,s,2,b,比值,1,1 0 0,0,s,1,s,2,0,0,1 -1 1 0,-3 2 0 1,1,6,1,z,j,c,j,-z,j,0 0 0 0 1 1 0 0,0,1,x,1,s,2,1,0,1,-1,1 0 0,-1,3 1,1,9,z,j,c,j,-z,j,1 -1 1 0,0,2,-1 0,1,填入单纯形表计算得：,解：在上述问题的约束条件中加入松驰变量，得标准型如下：,43,4,几种特殊情况,从单纯形表中，从第一次迭代的检验数等于,2,，可知所得的基本可行解,x,1,=1,x,2,=0,s,1,=0,s,2,=9,不是最优解。同时我们也知道如果进行第,2,次迭代，那么就选,x,2,为入基变量，但是在选择出基变量时遇到了问题 ：,=-1, =-1,找不到大于零的 来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从,1,次迭代的单纯形表中，得到约束方程：,移项可得：,44,4,几种特殊情况,由于,M,可以是任意大的正数，可知此目标函数值无界。,上述的例子告诉了我们在单纯形表中,识别线性规划问题是无界的方法,：在某次迭代的单纯形表中，如果存在着一个大于零的检验数 ，并且该列的系数向量的每个元素,a,ij,(i,=1,2,m),都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是,由于建模的错误所,引起的。,45,4,几种特殊情况,三、无穷多最优解,（判断方法：非基变量的检验数也等于,0,）,例,3,、用单纯形法表求解下面的线性规划问题,46,4,几种特殊情况,解：用单纯形表来求解,填入单纯形表计算得：,47,4,几种特殊情况,迭代次数,基变量,C,B,x,1,x,2,s,1,s,2,s,3,b,比值,50,50,0 0 0,0,s,1,s,2,s,3,0,0,0,1 1 1 0 0,2 1 0 1 0,0 1 0 0 1,300,400,250,300/1,400/1,250/1,z,j,c,j,-z,j,0 0 0 0 0,50,50,0 0 0,0,1,s,1,s,2,x,2,0,0,50,1,0 1 0 -1,2 0 0 1 -1,0 1 0 0 1,50,150,250,50/1,150/2,z,j,c,j,-z,j,0 50 0 0 50,50 0 0 0 0,12500,2,x,1,s,2,x,2,50,0,50,1 0 1 0 -1,0 0 -2 1,1,0 1 0 0 1,50,50,250,50/1,250/1,z,j,c,j,-z,j,50,50,50,0 0,0 0 -50 0 0,15000,48,4,几种特殊情况,这样我们求得了最优解为,x,1,=50,x,2,=250,s,1,=0,s,2,=50,s,3,=0,此线性规划的最优值为,15000,。这个最优解是否是惟一的呢？由于在第,2,次迭代的检验数中除了基变量的检验数 等于零外，非基变量,s,3,的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第,3,次迭代。可求得另一个基本可行解，如下表所示：,迭代次数,基变量,C,B,x,1,x,2,s,1,s,2,s,3,b,50,50,0 0 0,3,x,1,s,3,x,2,50,0,50,1 0 -1 1 0,0 0 -2 1 1,0 1 2 -1 0,100,50,200,z,j,c,j,-z,j,50,50,50,0 0,0 0 -50 0 0,15000,49,4,几种特殊情况,从检验数可知此基本可行解,x,1,=100,x,2,=200,s,1,=0,s,2,=0,s,3,=50,也是最优解，从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量,Z,1,，,Z,2,表示上述两个最优解即,Z,1,=,（,50,，,250,，,0,，,50,，,0,），,Z,2,=,（,100,，,200,，,0,，,0,，,50,），则此线段上的任一点，即可表示为,Z,1,+,（,1-,）,Z,2,，其中,0,1,。如图,5-1,所示：,100,200,300,100,200,300,250,Z,1,Z,2,图,5-1,50,4,几种特殊情况,四、退化问题,（勃兰特法则）,在单纯形法计算过程中，确定出基变量时有时,存在两个以上的相同的最小比值,，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。,例,4.,用单纯形表，求解下列线性规划问题。,解：加上松驰变量,s1,s2,s3,化为标准形式后，填入单纯形表计算得：,51,4,几种特殊情况,迭代次数,基,变,量,C,B,x,1,x,2,x,3,s,1,s,2,s,3,b,比值,2 0 3/2 0 0 0,0,s,1,s,2,s,3,0,0,0,1,-1 0 1 0 0,2 0 1 0 1 0,1 1 1 0 0 1,2,4,3,2/1,4/2,3/1,z,j,c,j,-z,j,0 0 0 0 0 0,2 0 3/2 0 0 0,0,1,x,1,s,2,s,3,2,0,0,1 -1 0 1 0 0,0,2,1 -2 1 0,0 2 1 -1 0 1,2,0,1,0/2,1/2,z,j,c,j,-z,j,2 -2 0 0 0 0,0 2 3/2 -2 0 0,4,2,x,1,x,2,s,3,2,0,0,1 0 1/2