单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2.2 单纯形法,单纯形法是解决线性规划问题的根本方法，其原理出自线性代数的矩阵理论，是可按现代计算机标准程序求解线性规划模型的一般方法，分为代数形式的单纯形法和表格形式的单纯形法。前者提供根本算法所依据的逻辑规那么，适用于在电子计算机上进行求解运算；后者将变量和数据列成表格，是本章采用的方法。,2.2.1 线性规划的有关概念,设线性规划的标准型为,其中,A,是,m,n,矩阵，且秩,r,(,A,)=,m,，亦即,A,中至少有一个满秩,m,m,子矩阵。,解,满足系统约束条件的决策向量,X,=(,x,1,x,2,x,n,),T,称为,线性规划的解,。,可行解,满足符号约束条件的解,X,=(,x,1,x,2,x,n,),T,称为线性规划的,可行解,。,11/16/2024,1,2.2 单纯形法,可行域,全体可行解的集合称为线性规划的,可行域,，一般记作,D,=,X,|,AX,=,b,X,0。,最优解 使目标函数到达最小值或最大值的可行解X*=(x1*,x2*,xn*)T称为线性规划的最优解。,最优值,最优解的目标函数值称为线性规划的最优值。,基 假设A中mm子矩阵B满足r(B)=m,那么称B是线性规划问题的一个基。也就是说，矩阵B是由A的m个线性无关列向量所构成，不妨设为：,称,P,j,(,j,=1,2,m,)为,基向量,。,11/16/2024,2,2.2 单纯形法,基变量、非基变量,与其基向量,P,j,(,j,=1,2,m,)相对应的变量,X,j,(,j,=1,2,m,)为,基变量,，其他决策变量称为,非基变量,。,根本解 记基变量为XB=(x1,x2,xn)T，非基变量为XN=(xm+1,xm+2,xn)T，称满足方程组的解XB=B-1b且XN=0为根本解。,根本可行解 假设根本解XB=B-1b0，那么称该解为根本可行解，也称为基可行解，B为可行基。,注,与基有关的概念都是相对的。,11/16/2024,3,【例2.8】求出下面线性规划的所有根本解,并指出那些是基可行解.,2.2 单纯形法,解 将线性规划模型化为标准型：,其中系数矩阵,11/16/2024,4,由于X1 0，所以也是根本可行解。,2.2 单纯形法,即,B,1,是一个基，,相应的线性规划根本解为X1=(15/4,3/4,0,0)，,求其他根本解的过程见下表。,11/16/2024,5,2.2 单纯形法,根本解与根本可行解表,基,基向量,基变量,非基变量,基本解,基可行解,X,1,=(15/4,3/4,0,0),是,X,2,=(4,0,3,0),是,X,3,=(5,0,0,-6),不是,X,4,=(0,12,-45,0),不是,X,5,=(0,3,0,18),是,X,1,=(0,0,15,24),是,一般来说，如果线性规划具有,n,个变量,m,个约束，则基本解的数量小于或等于 ，当然基可行解的数量更不会超过 个。,11/16/2024,6,2.2 单纯形法,2.2.2 单纯形法的理论根底,根本概念,凸集,设,D,是,n,维欧氏空间的一个点集，若任意两点 的连线上的一切点 （即集合D中任意两个点其连线上的所有点也都是集合D中的点）；则称,D,为,凸集,。,从直观上说，凸集没有凹入部分，其内部没有孔洞。,凸组合,设 是,n,维欧氏空间中的,k,个点，若存在,，且 使 ，则称,x,为 的,凸组合,。,顶点,设,D,是凸集，若 且,x,不能用,D,中不同的两点的线性组合表示为 ，则称,x,为,D,的一个,顶点,（或,极点,）。,S,1,S,2,S,3,11/16/2024,7,2.2 单纯形法,根本定理,定理2.1 假设线性规划问题存在可行域，那么可行域是凸集。,定理2.2,线性规划可行域,D,中的点,X,是顶点的充要条件为,X,是基可行解。,定理2.3 假设线性规划有最优解，那么最优解一定可以在可行域的顶点上得到。,【例2.9】指出例2.8中的线性规划根本解与其可行域顶点的对应关系。,解,见下表的说明及图示。,11/16/2024,8,2.2 单纯形法,根本解与其对应的顶点,基变量,基本解,基可行解,顶点,X,1,=(15/4,3/4,0,0),是,X,2,=(4,0,3,0),是,X,3,=(5,0,0,-6),不是,X,4,=(0,12,-45,0),不是,X,5,=(0,3,0,18),是,X,1,=(0,0,15,24),是,11/16/2024,9,2.2 单纯形法,但当,m,n,较大时，计算工作繁琐庞大，这种方法还是行不通的，所以还要继续讨论如何有效地找到最优解的方法，这就是下面介绍的,单纯形法,。,线性规划问题的所有解构成的集合是凸集，凸集的每一个顶点对应一个基可行解，由于基可行解的个数是有限的（它不大于 个），所以顶点的个数也是有限的。若线性规划问题有最优解，必在可行域某顶点上得到，可采用“枚举法”找出所有基可行解，然后一一进行比较，最终就可能找到最优解。,2.2.3 单纯形法的计算步骤,单纯形法是从可行域的一个基可行解出发顶点，判断该解是否为最优解，如果不是就转移到另一个较好的基可行解，如果目标函数到达最优，那么已得到最优解，否那么，继续转移到其它较好的基可行解。由于基可行解顶点的数目是有限的，所以经过有限次数的迭代转换后就能求出最优解，如以下图所示。,11/16/2024,10,否,是,否,是,2.2 单纯形法,确定初始基可行解,判断解是否最 优,是否有无界 解,搜索使目标函数改善的基可行解,结束,单纯形法求解,步骤流程图,定理2.4,定理2.5,定理2.6,初始基可行解确实定,1假设给定问题标准化后且b0，系数矩阵A中存在m个线性无关的单位列向量，那么以这m个单位列向量构成的单位矩阵B作为初始基，那么XB=B-1b=b0，其他xj=0就是初始基可行解。,【,例2.10,】,求下面问题的初始基可行解,11/16/2024,11,2.2 单纯形法,解 将线性规划标准化，添加松弛变量x3,x4，得,由于 有两个单位列向,量,可取为初始基 ，则,就是初始基可行解。,11/16/2024,12,2.2 单纯形法,2假设给定问题标准化后(b0)系数矩阵中不存在m个线性无关的单位列向量，那么在某些约束左端加一个非负的人工变量构建一些单位列向量，人工创造一个单位矩阵，参见后面的大M法。,单纯形法的求解定理,线性规划的标准型为,不妨设B=(P1,P2,Pm)是其中一个基，将有关矩阵和向量分块，记A=(B,N),C=(CB,CN),X=(XB,XN)T为求线性规划的根本最优解，先要求线性规划的根本可行解，这样就需将约束中的基变量用非基变量表示出来。,其中,A,是,m,n,矩阵，且,r,(,A,)=,m,。,11/16/2024,13,2.2 单纯形法,用,B,-1,左乘约束方程,AX,=,b,的两端，得：,将其代入目标函数得:,称 为非基变量,x,j,的,检验数,，,记为,表示该变量增加或减少一个单位所引起目标函数值的变化，它可以用来判断 xj 将变成基变量后能否改进目标函数值,11/16/2024,14,2.2 单纯形法,上面过程也可以通过,线性方程组消元,实现:,线性方程组,其变量为,整理得方程组,为便于求解，其增广矩阵见下表,常数项,z,X,B,X,N,b,0,B,N,(1),0,-1,C,B,C,N,(2),用,B,-1,左乘方程组(1)的两端,将,X,B,的系数化为单位矩阵,得下表,常数项,z,X,B,X,N,B,-1,b,0,B,-1,B=E,B,-1,N,(3),0,-1,C,B,C,N,11/16/2024,15,常数项,z,X,B,X,N,B,-1,b,0,B,-1,B=E,B,-1,N,(3),0,-1,C,B,C,N,(2),2.2 单纯形法,将方程组(3)左乘,-,C,B,加到方程(2)两边，得下表,常数项,z,X,B,X,N,B,-1,b,0,B,-1,B=E,B,-1,N,-,C,B,B,-1,b,-1,C,B,-C,B,B,-1,B=O,C,N,-C,B,B,-1,N,(4),注意(4)中基变量,X,B,、非基变量,X,N,的系数，他们形式结构相似，当前者,C,B,-C,B,B,-1,B=O,时，后者,C,N,-C,B,B,-1,N,即为检验数的矩阵形式，也就是说，用消元法将目标函数中基变量的系数化为零的同时，就会得到非基变量的检验数。,事实上，,C,B,-C,B,B,-1,B,也可看成基向量的检验数，应用消元法后，当基向量的检验数变为零时，非基变量的系数,C,N,-C,B,B,-1,N,就是其检验数。,11/16/2024,16,2.2 单纯形法,线性规划单纯形法求解有下述定理：,定理2.4,（,最优解判定定理,）对某基可行解,X,B,=,B,-1,b,其他,x,j,=0，若所有的 ，则该解为最优解。,定理2.5,（,无界解判定定理,）若对某可行基,B,存在且 ，则该线性规划问题有无界解。,定理2.6换基迭代定理,1）给定某可行基,B,对矩阵,A,的行列来说,通过下面步骤：,确定进基变量,：，选择,k,列的非基变量,x,k,为进基变量；按最小比值原则,确定出基变量,：,（最小值不唯一时任选一个行标,l,作为），其中(,B,-1,b,),i,表示向量,B,-1,b,的第,i,个元素，选择,l,行对应的基变量,x,l,为出基变量，那么,P,k,替换,B,中出基变量所在的列后就能得到一个新的可行基 。,11/16/2024,17,2.2 单纯形法,2）对线性方程组,AX,=,b,的增广矩阵实施初等行变换：第,l,行元素同除以,主元,a,lk,，使主元变为1；使主元所在列的其它元素变为0，这样就得到可行基对应的基可行解，并且所对应的目标函数值增加 。,单纯形表,为便于表达单纯形法的计算过程，上述计算过程可以在单纯形表上完成。每个可行基,B,都可构造出一个单纯形表，,一般将其化为单位矩阵后再列出单纯形表,，见下表,11/16/2024,18,2.2 单纯形法,C,B,X,B,B,-1,b,c,1,c,2,c,m,c,m,+1,c,n,x,1,x,2,x,m,x,m,+1,x,n,c,1,x,1,b,1,1,0,0,a,1,m,+1,a,1,n,c,2,X,2,b,2,0,1,0,a,2,m,+1,a,2,n,c,m,x,m,b,m,0,0,1,a,mm,+1,a,mm,检验数,0,0,0,m,+1,n,表中：,X,B,一列记录基变量；,C,B,一列跟踪基变量对应的价值系数；,B,-1,b,为基可行解；其余各列为,B,-1,P,j,(,j,=1,2,n,)，最后一行是每个变量对应的检验数。,大方框中元素就是增广矩阵，这样求解线性规划就可以在单纯形表中实现，单纯形表包含了线性规划求解的全部信息,。,11/16/2024,19,2.2 单纯形法,【,例2.11,】,用单纯形法求例2.8的最优解,b,2,1,0,0,x,1,x,2,x,3,x,4,15,3,5,1,0,24,6,2,0,1,B,X,B,N,X,N,15,3,5,1,0,24,6,2,0,1,E,B,-1,N,B,-1,b,填入下面初始单纯形表：,11/16/2024,20,2.2 单纯形法,C,B,X,B,B,-1,b,2,1,0,0,x,1,x,2,x,3,x,4,15,3,5,1,0,24,6,2,0,1,检验数,x,3,x,4,0,0,2,1,5,4,检验数,x,3,x,1,0,2,4,1,1/3,0,1/6,3,0,4,1,-1/2,1/3,-1/3,3/4,12,检验数,x,2,x,1,1,2,3/4,0,1,1/4,-1/8,15/4,1,0,-1/12,5/24,-1/24,-7/24,X,*=(15/4,3/4)z*=33/4,11/16/2024,21,2.2 单纯形法,【,例2.13,】,用单纯形法求解线性规划,解,将线性规划标准化，得,由于技术矩阵中有一个单