教育学第节清华大学.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,（,第三版）,运筹学,教材编写组 编,清华大学出版社,运筹学,第,1,章,线性规划与单纯形法,第,1,节 线性规划问题及其数学模型,钱颂迪 制作,二,.,线性规划与目标规划,第,1,章 线性规划与单纯形法,第,2,章 对偶理论与灵敏度分析,第,3,章 运输问题,第,4,章 目标规划,第,1,章 线性规划与单纯形法,第,1,节 线性规划问题及其数学模型,第,2,节 线性规划问题的几何意义,第,3,节 单纯形法,第,4,节 单纯形法的计算步骤,第,5,节 单纯形法的进一步讨论,第,6,节 应用举例,第,1,节 线性规划问题及其数学模型,1.1,问题的提出,1.2,图解法,1.3,线性规划问题的标准形式,1.4,线性规划问题的解的概念,第,1,节 线性规划问题及其数学模型,线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介绍单纯形法,。,1.1,问题的提出,从一个简化的生产计划安排问题开始,例,1,某工厂在计划期内要安排生产,、,两种产品，已知生产单位产品所需的设备台时及,A,、,B,两种原材料的消耗，如表,1-1,所示。,资源,产 品,拥有量,设 备,1,2,8,台时,原材料,A,4,0,16 kg,原材料,B,0,4,12 kg,续例,1,该工厂,每生产一件产品,可获利,2,元，,每生产一件产品,可获利,3,元，,问应如何安排计划使该工厂获利最多,?,如何用数学关系式描述这问题，必须考虑,数学模型,例,2.,简化的环境保护问题,靠近某河流有两个化工厂,(,见图,1-1),，流经第一化工厂的河流流量为每天,500,万立方米，在两个工厂之间有一条流量为每天,200,万立方米的支流。,图,1-1,续例,2,第一 化工厂每天排放含有某种有害物质的工业污水,2,万立方米，第二化工厂每天排放这种工业污水,1.4,万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有,20%,可自然净化。根据环保要求，河流中工业污水的含量应不大于,0.2%,。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是,1000,元,/,万立方米。,第二 化工厂处理工业污水的成本是,800,元,/,万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。,建模型之前的分析和计算,设,：,第一化工厂每天处理工业污水量为,x,1,万立方米，,第二化工厂每天处理工业污水量为,x,2,万立方米,数学模型,共同的特征,每一个线性规划问题都用一组决策变量,表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的；,(2),要有各种资源和使用有关资源的技术数据,，创造新价值的数据；,共同的特征（继续）,(3),存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示,;,(4),要有一个达到目标的要求，它可用决策变量的线性函数,(,称为目标函数,),来表示。按问题的不同，要求目标函数实现最大化或最小化。,它们的对应关系可用表格表示：,线性规划的一般模型形式,1.2,图解法,例,1,是二维空间（平面）线性规划问题，可用作图法直观地来表述它的求解。,因存在,必须在直角坐标的第,1,象限内作图，求解。,图,1-2,图,1-3,目标值在（,4,，,2,）点，达到最大值,14,目标函数,可能出现的几种情况,（,1,）,无穷多最优解,(,多重最优解,),，见图,1-4,（,2,）,无界解，见图,1-5-1,（,3,）,无可行解，见图,1-5-2,图,1-4,无穷多最优解,(,多重最优解,),目标函数,max z=2x,1,+,4x,2,图,1-5-1,无界解,无可行解,当存在矛盾的约束条件时，为无可行域。,如果在例,1,的数学模型中增加一个约束条件,:,该问题的可行域为,空集,，即无可行解，,图,1-5-2,不存在可行域,增加的约束条件,1.3,线性规划问题的标准型式,线性规划问题的几种表示形式,用向量表示为：,用矩阵表示为：,如何变换为标准型：,(1),若要求目标函数实现最小化，即,min z=CX,。这时只需将目标函数最小化变换求目标函数最大化，即令,z=-z,，于是得到,max z=-CX,。这就同标准型的目标函数的形式一致了。,(2),约束方程为不等式。这里有两种情况：一种是约束方程为,“,”,不等式，则可在,“,”,不等式的左端加入非负松弛变量，把原,“,”,不等式变为等式；另一种是约束方程为,“,”,不等式，则可在,“,”,不等式的左端减去一个非负剩余变量,(,也可称松弛变量,),，把不等式约束条件变为等式约束条件。下面举例说明。,例,3,将例,1,的数学模型化为标准型。,例,1,的数学模型,加松驰变量后,(3),若存在取值无约束的变量,x,k,可令,其中,。,例,4,将下述线性规划问题化为标准型,处理的步骤：,(1),用,x,4,-x,5,替换,x,3,，其中,x,4,，,x,5,0,；,(2),在第一个约束不等式号的左端,加入,松弛变量,x,6,；,(3),在第二个约束不等式号的左端,减去,剩余变量,x,7,；,(4),令,z=-z,，把求,min z,改为求,max z,，即可得到该问题的标准型,例,4,的标准型,1.4,线性规划问题的解的概念,1.,可行解,2.,基,3.,基可行解,4.,可行基,1.,可行解,满足约束条件,(1-5),，,(1-6),式的解,X=(x,1,x,2,，,，,x,n,),T,，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。,2.,基，基向量，基变量,基可行解,满足非负条件（,1-6,）的基解，称为基可行解,.,基可行解的非零分量的数目也不大于,m,，并且都是非负的。,4.,可行基,对应,于基可行解的基，称为可行基。,约束方程组,(1-5),具有基解的数目最多是 个。一般基可行解的数目要小于基解的数目。,以上提到的几种解的概念，它们之间的关系可用图,1-6,表明。,另外还要说明一点，基解中的非零分量的个数小于,m,个时，该基解是退化解。在以下讨论时，假设不出现退化的情况。以上给出了线性规划问题的解的概念和定义，它们将有助于用来分析线性规划问题的求解过程。,图,1-6,它们之间的关系,小结,1.,线性规划问题的模型特征,2.,通过图解法了解如何求解线性规划问题,3.,为求解高维线性规划问题，必须建立的概念,运筹学,（,第三版）,运筹学,教材编写组 编,清华大学出版社,第,1,章 线性规划与单纯形法,第,2,节 线性规划问题的几何意义,钱颂迪 制作,第,1,章 线性规划与单纯形法,第,2,节线性规划问题的几何意义,2.1,基本概念,2.2,几个定理,2.1,基本概念,凸集,凸组合,顶点,1.,凸集,设,K,是,n,维欧氏空间的一点集，若任意两点,X,(1),K,，,X,(2),K,的连线上的所有点,X,(1),+(1-)X,(2),K,，,(01),；则称,K,为凸集。,图,1-7,实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图,1-7,中的,(a)(b),是凸集，,(c),不是凸集。,图,1-2,中的阴影部分,是凸集。,任何两个凸集的交集是凸集，见图,1-7(d),2.,凸组合,设,X,(1),，,X,(2),，,，,X,(k),是,n,维欧氏空间,E,中的,k,个点。若存在,1,，,2,，,，,k,，且,0i1,i=1,2,，,k;,使,X=,1,X,(1),+,2,X,(2),+,+,k,X,(k),则称,X,为,X,(1),，,X,(2),，,，,X,(k),的凸组合。（当,0,i,1,时，称为严格凸组合）,.,3.,顶点,设,K,是凸集，,XK,；若,X,不能用不同的两点,X,(1),K,和,X,(2),K,的线性组合表示为,X=X,(1),+(1-)X,(2),，,(0,1),则称,X,为,K,的一个顶点,(,或极点,),。,图中,0,，,Q,1,2,3,4,都是顶点。,2.2,几个定理,定理,1,若线性规划问题存在可行域，则其可行域,是凸集,证：为了证明满足线性规划问题的约束条件,的所有点,(,可行解,),组成的集合是凸集，,只要证明,D,中任意两点连线上的点必然在,D,内即可。,设,是,D,内的任意两点；,X,(1),X,(2),。,引理,1,线性规划问题的可行解,X=(x,1,x,2,，,x,n,),T,为基可行解的充要条件是,X,的正分量所对应的系数列向量是线性独立的。,定理,2,线性规划问题的基可行解,X,对应于可行,D,的顶点。,证：,不失一般性，假设基可行解,X,的前,m,个分量为正。故,现在分两步来讨论，分别用反证法。,（,1-8,）,若,X,不是基可行解，则它一定不是可行域,D,的顶点,根据引理,1,，若,X,不是基可行解，则其正分量所对应的系数列向量,P,1,，,P,2,，,，,P,m,线性相关，即存在一组不全为零的数,i,i=1,2,m,使得,1,P,1,+,2,P,2,+,+,m,P,m,=0 (1-9),用一个,0,的数乘,(1-9),式再分别与,(1-8),式相加和相减，。,这样得到,(x,1,-,1,)P,1,+(x,2,-,2,)P,2,+,+(x,m,-,m,)P,m,=b(x,1,+,1,)P,1,+(x,2,+,2,)P,2,+,+(x,m,+,m,)P,m,=b,现取,X,(1),=,(x,1,-,1,),(x,2,-,2,),(x,m,-,m,),0,，,0,X,(2),=,(x,1,+,1,),(x,2,+,2,),(x,m,+,m,),0,，,0,由,X,(1),X,(2),可以得到,X=,（,1/2,）,X,(1),+,（,1/2,）,X,(2),，,即,X,是,X,(1),，,X,(2),连线的中点,另一方面，当,充分小时，可保证,x,i,i,0,，,i=1,2,m,即,X,(1),，,X,(2),是可行解。,这证明了,X,不是可行域,D,的顶点。,(2),若,X,不是可行域,D,的顶点，则它一定不是基可行解,因为,X,不是可行域,D,的顶点，故在可行域,D,中可找到不同的两点,X,(1),=(x,1,(1),x,2,(1),x,n,(1),),T,X,(2),=(x,1,(2),x,2,(2),x,n,(2),),T,使,X=X,(1),+(1-),X,(2),，,0,1,设,X,是基可行解，对应向量组,P,1,P,m,线性独立。当,j,m,时，有,x,j,=x,j,(1),=x,j,(2),=0,，由于,X,(1),，,X,(2),是可行域的两点。应满足,将这两式相减，即得,因,X,(1),X,(2),，所以上式系数不全为零，故向量组,P,1,P,2,，,P,m,线性相关，与假设矛盾。即,X,不是基可行解。,引理,2,若,K,是有界凸集，则任何一点,XK,可表示为,K,的顶点的凸组合。,本引理证明从略，用以下例子说明这引理。,例,5,设,X,是三角形中任意一点，,X,(1),X,(2),和,X,(3),是三角形的三个顶点，试用三个顶点的坐标表示,X(,见图,1-8),解 任选一顶点,X,(2),，做一条连线,XX,(2),；并延长交于,X,(1),、,X,(3),连接线上一点,X,。因,X,是,X(1),、,X(3),连线上一点，故可用,X,(1),、,X,(3),线性组合表示为,X=X,(1),+(1-)X,(3),0,1,又因,X,是,X,与,X,(2),连线上的一个点，故,X=X+(1-)X,(2),0,1,将,X,的表达式代入上式得到,X=,X,(1),+(1-)X,(3),+(1-)X,(2),=X,(1),+(1-)X,(3),+(1-)X,(2),令,1,=,2,=(1-),3,=(1-),这就得到,X=,1,X,(1),+,2,X,(2),+,3,X,(3),i,i,=1,0,i,1,定理,3,若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。,证,设,X,(1),X,(2),，,，,X,(k),是可行域的顶点，若,X,(0),不是顶点，且目标函数在,X,(0),处达到最优,z,*,=CX,(0),(,标准型是,z=max z),。,因,X,(0),不是顶点，所以它可以用,D,的顶点线性表示为,定理,3,的证明：,证：,设,X,(1),X,(2),，,，,X,(k),是可行域的顶点，,若,X,(0),不是顶点，且目标函数在,X,(0),处达到,最优,z,*,=CX,(0),(,标准型是,z=max z),。,代入目标函数得,在所有的顶点中必然能找到某一个顶点,X,(m),，使,CX,(m),是所有,CX,(i),中最大者。并且将,X,(m),代替,(1-10),式中的所有,X,(i),，这就得到,（,1-10,）,由此得到,X,(0),CX,(m),根据假设,CX,(0),是最大值，所以只能有,CX,(0),=CX,(m),即目标函数在顶点,X,(m),处也达到最大值。,有时目标函数可能在多个顶点处达到最大,;,这时在这些顶点的凸组合上也达到最大值。,称这种线性规划问题有无限多个最优解。,假设是目标函数达到最大值的顶点，若是这些顶点的凸组合，即,于是,设：,于是：,另外，若可行域为无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。根据以上讨论，可以得到以下结论：,线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；,若线性规划问题有最优解，必在某顶点上得到。虽然顶点数目是有限的,(,它不大于个,),，若采用,“,枚举法,”,找所有基可行解，然后一一比较，最终可能找到最优解。但当,n,m,的数较大时，这种办法是行不通的，所以要继续讨论，如何有效地找到最优解，有多种方法，,这里仅介绍,单纯形法,。,第,2,节 结束,（,第三版）,运筹学,教材编写组 编,清华大学出版社,运筹学,第,1,章,线性规划与单纯形法,第,3,节,单纯形法,钱颂迪 制作,第,1,章 线性规划与单纯形法,第,3,节 单纯形法,3.1,举例,3.2,初始基可行解的确定,3.3,最优性检验与解的判断,3.4,基变换,3.5,迭代（旋转运算）,单纯形法求解线性规划的思路：,一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问题就得到了最优解，先举一例来说明。,注：,单纯形是指,0,维中的点，一维中的线段，二维中的三角形，三维中的四面体，,n,维空间中的有,n+1,个顶点的多面体。例如在三维空间中的四面体，其顶点分别为,(0,，,0,，,0),，,(1,，,0,，,0),，,(0,，,1,，,0),，,(0,，,0,，,1),。具有单位截距的单纯形的方程是,xi1,，并且,xi0,，,i=1,2,m,。,3.1,举例,例,6,试以例,1,来讨论如何用单纯形法求解。例,1,的标准型为：,约束方程,(1-12),式的系数矩阵,从,(1-12),式中可以看到,x,3,x,4,x,5,的系数列向量,P,3,P,4,P,5,是线性独立的，这些向量构成一个基,对应于,B,的变量,x,3,x,4,x,5,为 基变量,.,从,(1-12),式中可以得到（,1-13,）,将,(1-13),式代入目标函数,(1-11),得到,当令非基变量,x,1,=x,2,=0,，便得到,z=0,。这时得到一个基可行解,X,(0),X,(0),=(0,0,8,16,12),T,这个基可行解表示：工厂没有安排生产产品,、,；资源都没有被利用，所以工厂的利润指标,z=0,。,从分析目标函数的表达式,(1-14),可以看到,非基变量,x,1,x,2,(,即没有安排生产产品,，,),的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品,或,，就可以使工厂的利润指标增加。所以只要在目标函数,(1-14),的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。,如何确定换入，换出变量,一般选择正系数最大的那个非基变量,x,2,为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。,现分析,(1-13),式，当将,x,2,定为换入变量后，必须从,x,3,x,4,x,5,中确定一个换出变量，并保证其余的都是非负，即,x,3,x,4,x,5,0,。,当,x,1,=0,由,(1-13),式得到,x,2,取何值时，才能满足非负要求,从,(1-15),式中可以看出，只有选择,x,2,=min(8/2,-,12/4)=3,时，,才能使,(1-15),式成立。,因当,x,2,=3,时，基变量,x,5,=0,，这就决定用,x,2,去替换,x,5,。,以上数学描述说明了每生产一件产品,，需要用掉各种资源数为,(2,，,0,，,4),。由这些资源中的薄弱环节，就确定了产品,的产量。,这里就是由原材料,B,的数量确定了产品,的产量,x,2,=12/4=3,件。,为了求得以,x,3,x,4,x,2,为基变量的一个基可行解和进一步分析问题，需将,(1-13),中,x,2,的位置与,x,5,的位置对换。得到,用高斯消去法,将,(1-16),式中,x,2,的系数列向量变换为单位列向量。其运算步骤是：,=,/4,；,=,-2,;,=,并将结果仍按原顺序排列有,：,再将,(1-17),式代入目标函数,(1-11),式得到,从目标函数的表达式,(1-18),中可以看到，非基变量,x,1,的系数是正的，说明目标函数值还可以增大，,X,(1),还,不是最优解。,于是再用上述方法，确定换入、换出变量，继续迭代，再得到另一个基可行解,X,(2),X,(2),=(2,3,0,8,0),T,再经过一次迭代，再得到一个基可行解,X,(3),X,(3),=(4,2,0,0,4),T,而这时得到目标函数的表达式是：,z=14-1.5x,3,-0.125x,4,(1-19),再检查,(1-19),式，可见到所有非基变量,x,3,x,4,的系数都是负数。这说明若要用剩余资源,x,3,x,4,，就必须支付附加费用。,所以当,x,3,=x,4,=0,时，即不再利用这些资源时，目标函数达到最大值。所以,X,(3),是最优解。即当产品,生产,4,件，产品,生产,2,件，工厂才能得到最大利润。,通过上例，可以了解利用单纯形法求解线性规划问题的思路。现将每步迭代得到的结果与图解法做一对比，其几何意义就很清楚了。,原例,1,的线性规划问题是二维的，,即两个变量,x,1,x,2,；当加入松弛变量,x,3,x,4,x,5,后，,变换为高维的。,这时可以想象，满足所有约束条件的可行域是高维空间的凸多面体,(,凸集,),。,这凸多面体上的顶点，就是基可行解。,初始基可行解,X,(0),=(0,0,8,16,12),T,就相当于图,1-2,中的原点,(0,，,0),，,X,(1),=(0,3,2,16,0),T,相当于,图,1-2,中,的,Q,4,点,(0,，,3),；,X,(2),=(2,，,3,，,0,，,8,，,0),T,相当于,图,1-2,中的,Q,3,点,(2,，,3),，,最优解,X,(3),=(4,，,2,，,0,，,0,，,4),T,相当于图,1-2,中的,Q,2,点,(4,，,2),。,从初始基可行解,X,(0),开始迭代，依次得到,X,(1),，,X,(2),，,X,(3),。这相当于图,1-2,中的目标函数平移时，,从,0,点开始，首先碰到,Q,4,，然后碰到,Q,3,，最后达到,Q,2,。下面讨论一般线性规划问题的求解。,一般线性规划问题的求解,3.2,初始基可行解的确定,为了确定初始基可行解，要首先找出初始可行基，其方法如下。,(1),直接观察,(2),加松弛变量,(3),加非负的人工变量,(1),直接观察,若线性规划问题,从,P,j,(j=1,2,n),中一般能直接观察到存在一个初始可行基,(2),加松弛变量,对所有约束条件是,“,”,形式的不等式，可以利用化为标准型的方法，在每个约束条件的左端加上一个松弛变量。,经过整理，重新对,x,j,及,a,ij,(i=1,2,m;j=1,2,n),进行编号，则可得下列方程组,x,1,x,2,x,m,为松弛变量,于是含有,mm,单位矩阵，以,B,作为可行基。,将,(1-22),式每个等式移项得,令,x,m+1,=x,m+2,=,=x,n,=0,，由,(1-23),式可得,x,i,=b,i,(i=1,2,m),得到一个初始基可行解,又因,b,i,0(,在,1-3,节中已做过规定,),，所以得到一个初始基可行解,X=(x,1,x,2,x,m,0,，,，,0),T,n-m,个,=(b,1,b,2,b,m,0,，,，,0),T,n-m,个,(3),加非负的人工变量,对所有约束条件是,“,”,形式的不等式及等式约束情况，若不存在单位矩阵时，就采用人造基方法。,即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；,对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。关于这个方法将在本章第,5,节中进一步讨论。,3.3,最优性检验与解的判别,对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况，,为此需要建立对解的判别准则。一般情况下，经过迭代后,(1-23),式变成,将 代入目标函数,(1-20),式，整理后得,令,1,最优解的判别定理,若 为对应于基,B,的一个基可行解，且对于一切,j=m+1,n,，有,j,0,，则,X,(0),为最优解。称,j,为检验数。,当所有非基变量的,j,0,时，由（,1-27,）式可知已不存在任一可换入的非基变量，,使目标函数继续增大。所以以,j,0,，为最优解的判别准则。,2.,无穷多最优解判别定理,若 为一个基可行解，对于一切,j=m+1,，,n,，有,j,0,，又存在某个非基变量的检验数,m+k,=0,，则线性规划问题有无穷多最优解。,证,:,只需将非基变量,x,m+k,换入基变量中，找到一个新基可行解,X,(1),。因,m+k,=0,，由,(1-27),知,z=z,0,，故,X,(1),也是最优解。由,2.2,节的定理,3,可知,X,(0),，,X,(1),连线上所有点都是最优解。,3,无界解判别定理,若 为一基可行解，,有一个,m+k,0,，并且对,i=1,2,，,m,，有,存在。,那么该线性规划问题具有无界解,(,或称无最优解,),。,证,:,构造一个新的解,X,(1),，它的分量为,因 ，所以对任意的,0,都是可行解，把,x,(1),代入目标函数内得,z=z,0,+,m+k,因,m+k,0,，故当,+,，则,z+,，故该问题目标函数无界。,以上讨论都是针对标准型，即求目标函数极大化时的情况。当求目标函数极小化时，一种情况如前所述，将其化为标准型。,如果不化为标准型，只需在上述,1,，,2,点中把,j,0,改为,j,0,，第,3,点中将,m+k,0,改写为,m+k,0,即可。,3.4,基变换,若初始基可行解,X,(0),不是最优解及不能判别无界时，需要找一个新的基可行解。具体做法是从原可行解基中换一个列向量,(,当然要保证线性独立,),，得到一个新的可行基，这称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。,1.,换入变量的确定,由,(1-27),式看到，当某些,j,0,时，,x,j,增大，则目标函数值还可以增大。这时要将某个非基变量,x,j,换到基变量中去,(,称为换入变量,),。若有两个以上的,j,0,，那么选哪个非基变量作为换入变量呢,?,为了使目标函数值增加得快，从直观上一般选,j,0,中的大者，即,则对应的,x,k,为换入变量,。但也可以任选或按最小足码选。,2.,换出变量的确定,设,P,1,，,P,2,，,，,P,m,是一组线性独立的向量组，它们对应的基可行解是,X,(0,),。将它代入约束方程组,(1-21),得到,其他的向量,P,m+1,P,m+2,P,m+t,P,n,都可以,用,P,1,，,P,2,，,，,P,m,线性表示，,若确定非基变量,P,m+t,为换入变量，,必然可以找到一组不全为,0,的数,(i=1,2,m),使得,在,(1-29),式两边同乘一个正数,，然后将它加到,(1-28),式上，得到,新的基可行解,。,由此得到由,X,(0),转换到,X,(1),的各分量的转换公式,这里 是原基可行解,X,(0),的各分量；是新基可行解,X,(1),的各分量；,i,m+t,是换入向量,P,m+t,的对应原来一组基向量的坐标。,现在的问题是，这个新解,X,(1),的,m,个非零分量对应的列向量是否性独立,?,事实上，因,X,(0),的第,l,个分量对应于,X,(1),的相应分量是零，即,成立。又因,将,(1-32),式减,(1-31),式得到,由于上式中至少有,l,m+t,0,，,所以上式表明,P,1,，,P,2,，,，,P,m,是线性相关，,这与假设相矛盾。,由此可见，,X,(1),的,m,个非零分量对应的列向量,P,j,(,j,=1,2,m,j,l,),与,P,m+t,是线性独立的，,即经过基变换得到的解是基可行解。,实际上，从一个基可行解到另一个基可行解的变换，就是进行一次基变换。从几何意义上讲，就是从可行域的一个顶点转向另一个顶点,(,见,1-2,图解法,),3.5,迭代,(,旋转运算,),上述讨论的基可行解的转换方法是用向量方程来描述，在实际计算时不太方便，因此采用,系数矩阵法,。现考虑以下形式的约束方程组,一般线性规划问题的约束方程组中加入松弛变量或人工变量后，,很容易得到上述形式,设,x,1,x,2,x,m,为基变量，对应的系数矩阵是,mm,单位阵,I,，它是可行基。令非基变量,x,m+1,x,m+2,x,n,为零，即可得到一个基可行解。若它不是最优解，则要另找一个使目标函数值增大的基可行解。这时从非基变量中确定,x,k,为换入变量。显然这时,为,在迭代过程中,可表示为,其中是经过迭代后对应于的元素值。,按,规则确定,x,l,为换出变量，,x,k,x,l,的系数列向量分别为,为了使,x,k,与,x,l,进行对换，须把,P,k,变为单位向量，这可以通过,(1-33),式系数矩阵的增广矩阵进行初等变换来实现。,变换的步骤是：,(1),将增广矩阵,(1-34),式中的第,l,行除以,a,l k,，得到,(2),将,(1-34),式中,x,k,列的各元素，除,a,l k,变换为,1,以外，其他都应变换为零。其他行的变换是将,(1-35),式乘以,a,i k,(il),后，从,(1-34),式的第,i,行减去，得到新的第,i,行。,由此可得到变换后系数矩阵各元素的变换关系式：,是变换后的新元素。,(3),经过初等变换后的新增广矩阵是,(4),由,(1-36),式中可以看到,x,1,x,2,x,k,，,x,m,的系数列向量构成,m,m,单位矩阵,;,它是可行基,.,当非基变量,x,m+1,，,x,l,x,n,为零时，就得到一个基可行解,X,(1),。,在上述系数矩阵的变换中，元素,a,l k,称为主元素，,它所在列称为主元列，它所在行称为主元行。,元素,a,l k,位置变换后为,1,。,例,7,试用上述方法计算例,6,的两个基变换。,解,例,6,的约束方程组的系数矩阵写成增广矩阵,当以,x,3,x,4,x,5,为基变量，,x,1,x,2,为非基变量，,令,x,1,x,2,=0,，,可得到一个基可行解,X,(0),=(0,0,8,16,12),T,现用,x,2,去替换,x,5,，于是将,x,3,，,x,4,x,2,的系数矩阵变换为单位矩阵，经变换后为,令非基变量,x,1,x,5,=0,，得到新的基可行解,X,(1),=(0,3,2,16,0),T,第,3,节 结束,运筹学,（,第三版）,运筹学,教材编写组 编,清华大学出版社,第,1,章 线性规划与单纯形法,第,4,节,单纯型法的计算步骤,钱颂迪 制作,第,1,章 线性规划与单纯形法,第,4,节,单纯型法的计算步骤,第,4,节 单纯型法的计算步骤,根据以上讨论的结果，将求解线性规划问题的单纯形法的计算步骤归纳如下,如利用单纯型表，求解线性规划问题。,4.1,单纯型表,为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似，下面来建立这种计算表。,将,(1-22),式与目标函数组成,n+1,个变量，,m+1,个方程的方程组。,线性规划的方程组,为了便于迭代运算，可将上述方程组写成增广矩阵形式,若将,z,看作不参与基变换的基变量，它与,x,1,x,2,x,m,的系数构成一个基，这时可采用行初等变换将,c,1,c,2,c,m,变换为零，使其对应的系数矩阵为单位矩阵。得到,可根据上述增广矩阵设计计算表，表,1-2,。,表,1-2,的说明,X,B,列中填入基变量，这里是,x,1,，,x,2,，,x,m,；,C,B,列中填入基变量的价值系数，这里是,c,1,c,2,c,m,；它们是与基变量相对应的；,b,列中填入约束方程组右端的常数；,c,j,行中填入基变量的价值系数,c,1,c,2,c,n,；,i,列的数字是在确定换入变量后，按,规则计算后填入；,最后一行称为检验数行，对应各非基变量,x,j,的检验数是,4.2,计算步骤,表,1-2,称为初始单纯形表，每迭代一步构造一个新单纯形表。,计算步骤：,(1),按数学模型确定,初始可行基,和,初始基可行解，建立初始单纯形表。,(2),计算,各非基变量,xj,的检验数,，,检查检验数，若所有检验数,则已得到最优解，可停止计算。否则转入下一步。,(3),在,j,0,j=m+1,n,中，若有某个,k,对应,x,k,的系数列向量,P,k,0,，则此问题是无界，停止计算。,否则，转入下一步。,(4),根据,max(,j,0)=,k,，确定,x,k,为换入变量，按,规则计算,(5),以,a,lk,为主元素进行迭代,(,即用高斯消去法或称为旋转运算,),，把,x,k,所对应的列向量,将,X,B,列中的,x,l,换为,x,k,，得到新的单纯形表。重复,(2),(5),，直到终止。,现用例,1,的标准型来说明上述计算步骤。,(1),取松弛变量,x,3,x,4,x,5,为基变量，它对应的单位矩阵为基。这就得到初始基可行解,X,(0),=(0,0,8,16,12),T,将有关数字填入表中，得到初始单纯形表，见表,1-3,。表中左上角的,c,j,是表示目标函数中各变量的价值系数。在,C,B,列填入初始基变量的价值系数，它们都为零。,目标函数中各变量的价值系数,。,1.,计算检验数，由它确定为换人变量,2.,计算,，由它确定为换出变量,3.,确定主元素,表,1-3,基变量,计算非基变量的检验数,各非基变量的检验数为,1,=c,1,-z,1,=2-(01+04+00)=2,2,=c,2,-z,2,=3-(02+00+04)=3,填入表,1-3,的底行对应非基变量处。,进行（,2,），（,3,）,它所在行对应的,x,5,为换出变量，,x,2,所在列和,x,5,所在行的交叉处,4,称为主元素或枢元素,(pivot element),进行（,4,）,(4),以,4,为主元素进行旋转运算或迭代运算，即初等行变换，使,P,2,变换为（,0,0,1,）,T,在,X,B,列中将,x,2,替换,x,5,于是得到新表,1-4.,换人变量,换出变量,主元素,(5),检查表,1-4,的所有,c,j,-z,j,这时有,c,1,-z,1,=2,；说明,x,1,应为换入变量。重复,(2),(4),的计算步骤，得表,1-5,。,还存在检验数,0,，继续进行。,换人变量,换出变量,主元素,(6),表,1-6,最后一行的所有检验数都已为负或零。这表示目标函数值已不可能再增大，于是得到最优解,最优解,X,*,=X,(3),=(4,2,0,0,4),T,目标函数的最大值,z,*,=14,第,4,节 结束,运筹学,（,第三版）,运筹学,教材编写组 编,清华大学出版社,第,一章 线性规划与单纯性法,第,5,节 单纯形法的进一步讨论,钱颂迪 制作,第一章 线性规划与单纯型法,第,5,节 单纯形法的进一步讨论,5.1,人工变量法,5.2,退化,5.3,检验数的几种表示形式,5.1,人工变量法,设线性规划问题的约束条件,其中没有可作为初始基的单位矩阵，则,分别给每一个约束方程加入人工变量,x,n+1,x,n+m,，得到,以,x,n+1,，,x,n+m,为基变量，并可得到一个,mm,单位矩阵。令非基变量,x,1,x,n,为零，便可得到一个初始基可行解,X,(0),=(0,0,0,b,1,b,2,b,m,),T,因为人工变量是后加入到原约束条件中的虚拟变量，要求经过基的变换将它们从基变量中逐个替换出来。,基变量中不再含有非零的人工变量，这表示原问题有解。,若在最终表中当所有,c,j,-z,j,0,，而在其中还有某个非零人工变量，这表示,原问题,无可行解,。,以下讨论如何解含有人工变量的线性规划问题。,1,大,M,法,在一个线性规划问题的约束条件中加进人工变量后，要求人工变量对目标函数取值不受影响；为此假定人工变量在目标函数中的系数为,(-M)(M,为任意大的正数,),，,这样目标函数要实现最大化时，必须把人工变量从基变量换出。否则目标函数不可能实现最大化。,例,8,现有线性规划问题，,试用大,M,法求解,。,解,在上述问题的约束条件中加入松弛变量,x,4,，剩余变量,x,5,，人工变量,x,6,x,7,，得到,这里,M,是一个任意大的正数,。,因本例的目标函数是要求,min,，所以用所有,cj-zj,0,来判别目标函数是否实现了最小化,.,用单纯形法进行计算时，见表,1-6,。,在,表,1-6,的,最终计算结果表中,，表明,已,得到最优解是：,x,1,=4,x,2,=1,x,3,=9,，,x,4,=x,5,=x,6,=x,7,=0,；目标函数,z=-2,2.,两阶段法,用电子计算机求解含人工变量的线性规划问题时，只能用很大的数来代替,M,，这就可能造成计算上的错误。故介绍两阶段法求线性规划问题。,第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。,第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入,人工变量,，并,构造,仅含,人工变量,的目标函数和要求实现,最小化,。如,第一阶段求解,然后用单纯形法求解上述模型，若得到,=0,，这说明原问题存在基可行解，可以进行第二段计算。否则原问题无可行解，应停止计算。,第二阶段：,将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表。各阶段的计算方法及步骤与第,3,节单纯形法相同。下面举例说明,例,9,试用两阶段法求解线性规划问题,解,先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：,第一阶段用单纯形法求解，见表,1-7,。求得的结果是,=0,，得到最优解是,x,1,=0,x,2,=1,x,3,=1,x,4,=12,x,5,=x,6,=x,7,=0,因人工