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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,3,单纯形法,单纯形法的一般原理,表格单纯形法,借助人工变量求初始的基本可行解,1,单纯形法的一般步骤如下：,（,1,）,寻找一个,初始的基本可行解,。,（,2,）,检查现行的基本可行解是否,最优,，如果为最优，,则停止迭代，已找到最优解，否则转一步。,（,3,）,移至目标函数值有所改善的,另一个基本可行解,，,然后转回到步骤（,2,）。,1947,年，,Dantzig,提出,的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。,2,一、引例,用单纯形方法求解下列线性规划：,min,z,=,6,x,1,4,x,2,2,x,1,+3,x,2,100,4,x,1,+2,x,2,120,x,1,、,x,2,0,解：化为标准型,min,z,=,6,x,1,4,x,2,+0 x,3,+0 x,4,2,x,1,+3,x,2,+x,3,=100,4,x,1,+2,x,2,+x,4,=120,x,1,、,x,2,，,x,3,，,x,4,0,3,基本解如下表,基 基本解 可行否 目标值对应图中的点,B,1,=,（,P,1,，,P,2,）,X,1,=,（,20,，,20,，,0,，,0,）,T,200 B,B,2,=,（,P,1,，,P,3,）,X,2,=,（,30,，,0,，,40,，,0,）,T,180 C,B,3,=,（,P,1,，,P,4,）,X,3,=,（,50,，,0,，,0,，,80,）,T,D,B,4,=,（,P,2,，,P,3,）,X,4,=,（,0,，,60,，,80,，,0,）,T,E,B,5,=,（,P,2,，,P,4,）,X,5,=,（,0,，,100/3,，,0,，,160/3,）,T,400/3 A,B,6,=,（,P,3,，,P,4,）,X,6,=,（,0,，,0,，,100,，,120,）,T,0 O,A,B,C,D,E,O,x,1,x,2,2,x,1,+3,x,2,=100,4,x,1,+2,x,2,=120,min,z,=,6,x,1,4,x,2,2,x,1,+3,x,2,+x,3,=100,4,x,1,+2,x,2,+x,4,=120,x,1,、,x,2,，,x,3,，,x,4,0,4,（,1,）,找初始可行基：,B,1,=,（,P,3,，,P,4,）,现成的初始可行基；,此时，,X,B,=,（,x,3,，,x,4,）,T,，,X,N,=,（,x,1,，,x,2,）,T,用,X,N,表示,Z,和,X,B,有：,min,z,=,6,x,1,4,x,2,x,3,=100,2x,1,3x,2,+x,4,=120,4x,1,2x,2,令,X,N,=(0,0),T,有,X,B,=(100,120),T,则有：,X,（,1,）,=,（,0,，,0,，,100,，,120,）,T,为对应于基,B,1,的基可行解。,问：,X,（,1,）,是否最优呢？,否,称非基变量在目标函数中的,系数为,检验数,。,min,z,=,6,x,1,4,x,2,2,x,1,+3,x,2,+x,3,=100,4,x,1,+2,x,2,+x,4,=120,x,1,、,x,2,，,x,3,，,x,4,0,因为：,x,1,和,x,2,在目标函数中的系数为,负,，,当,x,1,，,z,；,x,2,，,z,。,5,（,2,）寻找可行,基,B,2,，,使其对应的基可行解,X,（,2,）,能使目标函数值增加。,选：,x,1,0,则有：,X,（,2,）,=,（,x,1,，,0,，,x,3,，,x,4,）,T,min,z,=,6,x,1,4,x,2,x,3,=100,2x,1,3x,2,+x,4,=120,4x,1,2x,2,要使为,X,（,2,）,基可行解，,x,3,，,x,4,中必有一个为零，而另一个大等于零。,只要取,x,1,=min,100/2,，,120/4,=30,就有,x,3,=40,，,x,4,=0,这样,X,（,2,）,=,（,30,，,0,，,40,，,0,）,T,因为,P,1,，,P,3,线性无关，因此,，,B,2,=,（,P,1,，,P,3,）,为一个基,而,X,（,2,）,为对应,于,B,2,的基可行解,此时,X,B,=,（,x,1,，,x,3,）,T,，,X,N,=,（,x,2,，,x,4,）,T,用,X,N,表示,Z,和,X,B,有：,min,z,=,180,x,2,（,3/2,）,x,4,x,1,=30,（,1/2,）,x,2,（,1/4,）,x,4,x,3,=40,2 x,2,+,（,1/2,）,x,4,问：,X,（,2,）,是否最优呢？,否,因为：,x,2,在目标函数中的系数为负，,当,x,2,，,z,。,6,（,3,）,寻找可行,基,B,3,，,使其对应的基可行解,X,（,3,）,能使目标函数值增加。,选：,x,2,0,则有：,X,（,3,）,=,（,x,1,，,x,2,，,x,3,，,0,）,T,min,z,=,180,x,2,（,3/2,）,x,4,x,1,=30,（,1/2,）,x,2,（,1/4,）,x,4,x,3,=40,2 x,2,+,（,1/2,）,x,4,要,使为,X,（,3,）,基可行解,，,x,1,，,x,3,中必有一个为零，而另一个大等于零。,只要取,x,2,=min,30/,（,1/2,），,40/2,=20,就有,x,1,=20,，,x,3,=0,这样,X,（,3,）,=,（,20,，,20,，,0,，,0,）,T,因为,P,1,，,P,2,线性无关，因此，,B,3,=,（,P,1,，,P,2,）,为一个基,而,X,（,3,）,为对应,于,B,3,的基可行解,此时,X,B,=,（,x,1,，,x,2,）,T,，,X,N,=,（,x,3,，,x,4,）,T,用,X,N,表示,Z,和,X,B,有：,min,z,=,200+,（,1/2,）,x,3,+,（,5/4,）,x,4,x,1,=20 +,（,1/4,）,x,3,（,3/8,）,x,4,x,2,=20,（,1/2,）,x,3,+,（,1/4,）,x,4,问：,X,（,3,）,是否最优呢？,是，,7,从引例可以总结出求解过程：,（,1,）确定初始基及其基可行解；,（,2,）判断是否为最优解，是停止，否则转下一步；,（,3,）转换可行基，并求出相应的基可行解，使目标函数值有所改进，转（,2,）。,8,确定初始的基本可行解,确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定,.,在线性规划标准型中设法得到一个,m,阶单位矩阵,I,作为初始可行基。,若在化标准形式前，,m,个约束方程都是“,”,的形式，那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量,x,n+i,(i=12m),。,9,判断现行的基本可行解是否最优,设有标准形式的线性规划问题：,min z=,cX,；,AX=b,，,X0,；,现假定,A,中存在一可行基,B,且,B,为单位阵,这样,AX=b,可以描述成如下形式，也就是用非基变量表示基变量,x,1,+a,1,m+1,x,m+1,+,+,a,1n,x,n,=b,1,x,2,+a,2,m+1,x,m+1,+,+,a,2n,x,n,=b,2,x,m,+a,m,m+1,x,m+1,+,+,a,mn,x,n,=,b,m,即,从上述约束方程中可以得到对应于,基,B,的基可行解,X=,（,b,1,，,b,2,，,，,b,m,，,0,，,，,0,）,T,10,用非基变量表示目标函数有：,令,有,式中,j,为基可行,解,X,的,检验数,。,更一般性：,11,向量形式,假如已求得一个基本可行解,将这一基本可行解代入目标函数，可求得相应的目标函数值,其中,分别表示基变量和,非基变量所对应的价值系数子向量。,12,要判定是否已经达到最小值，只需将,代入目标函数，使目标函数用非,基变量,表示，即：,其中 称为非基变量,N,的,检验向量,，它的各个分量称为检验数。若,N,的每一个检验数均小于等于,0,，即,N,0,，那么现在的基本可行解就是最优解。,13,定理,1,：,最优解判别定理,对于线性规划问题,若某个基本可行解所对应的检验向量，,则这个基本可行解就是,最优解,。,定理,2,：,无穷多最优解,判别定理,若是一个基本可行解，所对应的检验向量,，其中,存在一个检验数,m+k,=0,，,则线性规划问题有,无穷多最优解,。,14,定理,3,：无最优解（无界）判别定理,若,是一个基本可行解，有一个检验数 ，,但是，则该线性规划问题无最优解。,证：令，则得新的可行解,将上式代入,因为,故当,+,时，,Z,。,15,如果现行的基本可行解不是最优解，即在检验向量,中存在,正的检验数,，则需在原基本可行解的基础上寻找一个新的基本可行解，并使目标函数值有所改善。,基本可行解的改进,具体做法是：,先从检验数为正的,非基变量,中确定一个,换入变量,，使它从非基变量变成基变量（将它的值从零增至正值），,再从原来的,基变量,中确定一个,换出变量,，使它从基变量变成非基变量（将它的值从正值减至零）。,由此可得一个新的基本可行解，由,可知，这样的变换一定能使,目标函数值有所减少,。,16,换入变量的确定,最大减少原则,假设检验向量，,选取,最大正检验数,所对应的非基变量为,换入变量,，即若,则选取对应的 为换入变量，,由于且为最大，,因此当由零增至正值，,可使目标函数值,最大限度的,减少,。,17,如果确定为换入变量，方程,其中为中与对应的系数列向量。,现在需在 中确定一个基变量为换出变量。,换出变量的确定,最小比值原则,当由零慢慢增加到某个值时，,的,非负性,可能被打破。,为保持解的可行性，可以,按最小比值原则,确定换出变量：,若,则选取对应的基变量 为换出变量。,18,单纯形表,(1),19,单纯形表,(2),20,计算步骤：,（,1,）构造单纯形表,1,和,2,。,（,2,）求 。,（,3,）若 ，则此时基解就是最优解，否则转（,4,）。,（,4,）若 ，则无最优解，否则转（,5,）。,（,5,）求 。,（,6,）以 为主元对初始单纯形表做换基运算得新单纯形表，转（,2,）。,21,4,单纯形表,例,1,求解,LP,问题,Z,0 1 -2 0 0,0,x,1,x,4,x,5,1 -2 1 0 0,0 1 -3 1 0,0 1 -1 0 1,2,1,2,x,1,x,2,x,3,x,4,x,5,RHS,22,Z,0 1 -2 0 0,0,x,1,x,4,x,5,1 -2 1 0 0,0 1 -3 1 0,0 1 -1 0 1,2,1,2,x,1,x,2,x,3,x,4,x,5,RHS,Z,0 0 1 -1 0,-1,x,1,x,2,x,5,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,x,1,x,2,x,5,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,x,1,x,2,x,3,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,*,=(6.5,2.5,0.5,0,0),T,最优值：,z,*,=-1.5,24,例,2,：,解,LP,问题,4,单纯形表,25,Z,0 1 2 0 0,0,x,1,x,2,x,3,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,1,x,2,x,3,x,4,x,5,Z,0 0 0 1.5 -2.5,-3.5,x,1,x,2,x,3,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,此问题无最优解,RHS,26,例,3,：,解,LP,问题,4,单纯形表,27,Z,0 0 0 0 -1,18,x,1,x,4,x,2,1 0 1 0 0,0 0 3 1 -1,0 1 -3/2 0 1/2,4,6,3,x,1,x,2,x,3,x,4,x,5,Z,0 0 0 0 -1,18,x,1,x,3,x,2,1 0 0 -1/3 1/3,0 0 1 1/3 -1/3,0 1 0 1/2 0,2,2,6,此问题有多解。,RHS,28,练习：,1,、用单纯形法求解,min,z,=,6,x,1,4,x,2,2,x,1,+3,x,2,100,4,x,1,+2,x,2,120,x,1,、,x,2,0,2,、用单纯形方法求解线性规划问题,29,因为非基变量,x4,的检验数 ，由无穷多最优解判别定理，,本例的线性规划问题存在,无穷多最优解,X*=,（,20,，,20,，,0,，,0,）,T,，,Z*=200,最优解最优值,30,无最优解,无最优解与无可行解时两个不同的概念。,无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集；,无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷小（或者无穷大）。无最优解也称为无有限最优解，或无界解。,31,借助人工变量求初始的基本可行解,假定我们下面研究的线性规划都是,非退化,的，将线性规划问题化为标准型,如果约束方程组中包含有一个,单位矩阵,I,，,那么已经得到了一个,初始可行基,。,否则在约束方程组的左边加上若干个非负的,人工变量,，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个,单位矩阵,。以单位矩阵为初始基，即可求得一个,初始的基本可行解,。,32,首先将原问题化为标准型,添加人工变量，并在目标函数中分别赋予,例,4:,线性规划问题,:,33,加入人工变量后的约束方程组与原约束方程组是,不等价,的。,加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问题的基本可行解。,只有当基本可行解中所有,人工变量都为取零值的非基变量,时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解而这正是我们引入人工变量的主要目的。,34,初始基本可行解,对原线性规划没有意义的,但是我们可以从,X,(0),出发进行迭代，迭代结果有两种：,1.,一旦所有的,人工变量,都从基变量迭代出来，,变成只能取零值的非基变量,，那么我们实际上已经求得了,原线性规划问题,的一个,初始的基本可行解,。此时可以把所有人工变量剔除，开始正式进入求原线性规划最优解的过程。,2.,如果,最优单纯形表的基变量中仍含有人工变量,，那么该线性规划就不存在可行解。,35,大,M,法,以后的计算与单纯形表解法相同，只需认定是一个,很大的正数,即可。,1.,假如在单纯形,最优表,的基变量中,不包含人工变量,，则,最优解中剔除人工变量即为,原问题的最优基本可行解,。,2.,否则说明,原问题无可行解,。,为了求得原问题的,初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中,赋予人工变量一个绝对值很大的系数,。,36,37,解：,首先将原问题化为标准型,添加人工变量，并在目标函数中分别赋予,例,5,、用大,M,法求解下面的线性规划问题,:,38,x,1,x,2,x,3,x,4,x,5,x,6,x,7,z,-1 2 0 0 0 -M,-M,0,X,6,X,7,X,5,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,X,6,X,7,X,5,1 1 -1 0 0 1 0,-1 1 0 -1 0 0 1,0 1 0 0 1 0 0,2,1,3,RHS,39,z,1+2M 0 -M 2+M 0 0 -2-2M,M-2,X,6,X,2,X,5,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,1,x,2,x,3,x,4,x,5,x,6,x,7,RHS,z,0 0 1/2 3/2 0 -M -3/2-M,-5/2,X,1,X,2,X,5,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/2,40,z,-3 0 2 0 0 -2-M -M,-4,X,4,X,2,X,5,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,1,x,2,x,3,x,4,x,5,x,6,x,7,RHS,z,-1 0 0 0 -2 -M -M,-6,X,4,X,2,X,3,1 0 0 1 1 0 -1,0 1 0 0 1 0 0,-1 0 1 0 1 -1 0,2,3,1,最优解 最优值,41,无可行解,通过大法求初始的基本可行解。但是如果在大法的,最优单纯形表的基变量中仍含有人工变量,，那么该线性规划就不存在可行解。,人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的,可行域为空集,。,42,解：,故引入人工变量，,并利用大,M,法求解,例,6,、求解下列线性规划问题,43,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,z,-3 -2 -1 0 0 0 -M,-M,0,X,4,X,7,X,8,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,3,RHS,z,-3+M -2+M -1-2M 0 -M,-M,0 0,7M,X,4,X,7,X,8,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,3,44,z,-3+M 0 -3-M 0 -M -2 0 2-M,6+4M,X,4,X,7,X,2,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,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,RHS,z,0 0 3-3M 3-M -M 1-M 0 -1,15+M,X,1,X,7,X,2,1 0 2 1 0 1 0 -1,0 0 -3 -1,-1,-1,1 1,0 1 -1 0 0 -1 0 1,3,1,3,在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量,x,7,=1,为基变量，所以原线性规划不存在可行解。,45,两阶段法,两阶段法引入人工变量的目的和原则与大,M,法相同，所不同的是处理人工变量的方法。,两阶段法的步骤：,1.,求解一个,辅助线性规划,。目标函数取所有人工变量之和，并取极小化；,2.,如果辅助线性规划存在一个基本可行解，使目标函数的最小值,等于零,，则,所有人工变量,都已经,“离基”,。表明原问题已经得了一个,初始的基本可行解,，可转入第二阶段继续计算；,否则,说明,原问题没有可行解,，可停止计算。,46,第一阶段：,加入人工变量,构造初始可行基,.,47,用单纯形法求解,若,g,=0,进入第二阶段,否则,原问,题无可行解。,第二阶段,：去掉人工变量，还原目标函数系数，做,出初始单纯形表。,48,例：求解下列线性规划问题,49,将原问题化成标准型：,解:,化标准型,用两阶段方法来求解。,50,第一阶段,的线性规划问题为,x,1,x,2,x,3,x,4,x,5,x,6,x,7,g,0 0 0 0 0 -1 -1,0,X,4,X,6,X,7,1 1 1 1 0 0 0,-2 1 -1 0 -1 1 0,0 3 1 0 0 0 1,4,1,9,RHS,51,x,1,x,2,x,3,x,4,x,5,x,6,x,7,RHS,g,-2 4 0 0 -1 0 0,10,X,4,X,6,X,7,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,X,4,X,2,X,7,3 0 2 1 1 -1 0,-2 1 -1 0 -1 1 0,6 0 4 0 3 -3 1,3,1,6,52,g,0 0 0 0 0 -1 -1,0,X,4,X,2,X,1,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,x,2,x,3,x,4,x,5,x,6,x,7,RHS,得原问题的基可行解,X=(1,3,0,0,0,),T,。,第二阶段：,将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。,53,Z,-3 0 1 0 0,0,X,4,X,2,X,1,0 0 0 1 -1/2,0 1 1/3 0 0,1 0 2/3 0 1/2,0,3,1,x,1,x,2,x,3,x,4,x,5,RHS,Z,0 0 3 0 3/2,3,X,4,X,2,X,1,0 0 0 1 -1/2,0 1 1/3 0 0,1 0 2/3 0 1/2,0,3,1,54,Z,-9/2 0 0 0 -3/4,-3/2,X,4,X,2,X,3,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,x,1,x,2,x,3,x,4,x,5,RHS,得原标准线性规划问题的最优解,X=,（,0,，,5/2,，,3/2,，,0,，,0,）,T,，,最优值是,-3/2,。,所以最初的线性规划问题的最优解,X=,（,0,，,5/2,，,3/2,）,T,，,最优值是,3/2,。,55,例：求解下列线性规划问题,56,将原问题化成标准型：,解:,化标准型,用两阶段方法来求解。,57,第一阶段,的线性规划问题为,x,1,x,2,x,3,x,4,x,5,x,6,RHS,g,0 0 0 0 -1 -1,0,X,5,X,6,X,4,3 1 0 0 1 0,4 3 -1 0 0 1,1 2 0 1 0 0,3,6,3,58,x,1,x,2,x,3,x,4,x,5,x,6,RHS,g,7 4 -1 0 0 0,9,X,5,X,6,X,4,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,X,1,X,6,X,4,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,59,x,1,x,2,x,3,x,4,x,5,x,6,RHS,g,0 5/3 -1 0 -7/3 0,2,X,1,X,6,X,4,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,X,1,X,6,X,2,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,60,g,0 0 0 0 -1,-1,0,X,1,X,3,X,2,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,1,x,2,x,3,x,4,x,5,x,6,RHS,第二阶段：,将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。,61,z,-4 -1 0 0,0,X,1,X,3,X,2,1 0 0 -1/5,0 0 1 1,0 1 0 3/5,3/5,0,6/5,x,1,x,2,x,3,x,4,RHS,z,0 0 0 -1/5,18/5,X,1,X,3,X,2,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,。,62,无可行解,通过两阶段法求初始的基本可行解。但是如果两阶段法的,辅助线性规划,的目标函数的,极小值大于零,，那么该线性规划就,不存在可行解,。,人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的,可行域为空集,。,63,例：求解下列线性规划问题,64,将原问题化成标准型：,解:,化标准型,用两阶段方法来求解。,65,第一阶段,的线性规划问题为,x,1,x,2,x,3,x,4,x,5,x,6,RHS,g,0 0 0 0 -1 -1,0,X,5,X,6,2 -3 -1 0 1 0,-1 1 0 -1 0 1,2,3,66,x,1,x,2,x,3,x,4,x,5,x,6,RHS,g,1 -2 -1,-1,0 0,5,X,5,X,6,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,X,1,X,6,1 -3/2 -1/2 0 1/2 0,0 -1/2,-1/2,-1 1/2 1,1,4,原问题无解。,67,练习：,用两阶段法求解线性规划问题。,1,、,2,、,68,1,、,2,、无可行解,69,退化与循环,循环产生的,原因,：,在单纯形法计算中用最小比值原则确定换出变量时，有时存在,两个或两个以上相同的最小比值,，,那么在下次迭代中就会出现一个甚至多个基变量等于零。,当某个,基变量为零,，且下次迭代以该基变量,作为换出变量,时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点,.,当线性规划问题的基本可行解中有一个或多个,基变量,取,零,值时，称此基本可行解为,退化解,。,70,Beale,的例子,71,解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。,72,