第1章 线性规划及单纯形法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三节 单纯形法原理,一、线性规划规划问题的解的概念,（一）线性规划问题标准型,（,1,）可行解：满足上述约束条件,(1.7),(1.8),的解,X=(x,1,x,n,),T,，称为线性规划问题的可行解。全部可行解的集合称为可行域。,（,2,）最优解：使目标函数,(1.6),达到最大值的可行解称为最优解。,（,3,）基：设,A,为约束方程组,(1.7),的,mn,阶系数矩阵，（设,nm,），其秩为,m,，,B,是矩阵,A,中的一个,mm,阶的满秩子矩阵，称,B,是线性规划问题的一个基。不失一般性，设,B,中的每一个列向量,P,j,(j,=1,m),称为基向量，与基向理,P,j,对应的变量,x,j,称为基变量。线性规划中除基变量以外的变量称为非基变量。,（,4,）基解：在约束方程组,(1.7),中，令所有非基变量为,x,m+1,=x,m+2,=,x,n,=0,零，以因为有,|B|0,，根据克莱姆法则，由,m,个约束方程可解出,m,个基变量的唯一解,X,B,=(x,1,x,m,),T,。将这个解加上非基解中变量取,0,的值有,X=,（,x,1,x,2,x,m,0,0,0,）,T,，称,X,为线性规划问题的基解。显然在基解中变量取非零值的个数不大于方程数,m,，故基解的总数不超过,C,n,m,个。,（,5,）基可行解：满足变量非负约束条件,(1.8),的基解称为基可行解。,（,6,）可行基：对应基可行解的基称为可行基。,可行解,基解,基可行解,（二）可行解、基解与基可行解的关系,线性规划的,基矩阵,、,基变量,、,非基变量,=,=,目标函数,约束条件,行列式,0,基矩阵,右边常数,（三）线性规划的基本概念的直观描述,（四）求出下列线性规划问题的所有基解、基可行解,该线性规划问题的标准型为：,基变量,x,1,、,x,2,、,x,3,，,非基变量,x,4,、,x,5,、,x,6,基解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,5,，,3,，,1,，,0,，,0,，,0,）,是基可行解，表示可行域的一个极点。,目标函数值为：,z=20,基变量,x,1,、,x,2,、,x,4,，,非基变量,x,3,、,x,5,、,x,6,基解为,（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,27/5,，,12/5,，,0,，,2/5,，,0,，,0,）,是基可行解，表示可行域的一个极点。,目标函数值为：,z=18,基变量,x,1,、,x,2,、,x,5,，,非基变量,x,3,、,x,4,、,x,6,基解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,6,，,3,，,0,，,0,，,-3,，,0,）,是基解，但不是可行解，不是一个极点。,基变量,x,1,、,x,2,、,x,6,，,非基变量,x,3,、,x,4,、,x,5,基解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,3,，,4,，,0,，,0,，,0,，,4,）,是基可行解，表示可行域的一个极点。,目标函数值为：,z=18,基变量,x,2,、,x,3,、,x,4,，,非基变量,x,1,、,x,5,、,x,6,基解为,（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,0,，,21/2,，,27/2,，,-30,，,0,，,0,）,是基解，但不是可行解。,基变量,x,1,、,x,2,、,x,3,，,非基变量,x,4,、,x,5,、,x,6,基解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,0,，,3,，,6,，,0,，,15,，,0,）,是基可行解，表示可行域的一个极点。,目标函数值为：,z=15,基变量,x,1,、,x,2,、,x,3,，,非基变量,x,4,、,x,5,、,x,6,基解为,（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）,=,（,0,，,11/2,，,-3/2,，,0,，,0,，,10,）,是基解但不是可行解。,例：设有一标准的线性规划问题的约束条件如下：,2x,1,+x,2,+x,4,=7,x,2,+x,3,=3,x,1,x,2,x,3,x,4,0,已知下列各点均满足以上的两个方程：,(1)(0,7,-4,0),T,(2)(2,3,0,0),T,(3)(1,0,3,5),T,(4)(2.5,2,1,0),T,(5)(0,3,0,4),T,二、,凸集及其顶点,1,凸集,设,C,是,n,维空间中的一个点集。若对任意,n,维向量,X,1,C,，,X,2,C,，且,X,1,X,2,，以及任意实数,（,0,1,），有,X,=,X,1,+(1-,),X,2,C,则称,C,为,n,维空间中的一个凸集。点,X,称为点,X,1,和,X,2,的凸组合。,以上定义有明显的几何意义，它表示凸集,C,中的任意两个不相同的点连线上的点（包括这两个端点），都位于凸集,C,之中。,2,顶点,凸集,C,中满足下述条件的点,X,称为顶点：如果,C,中不存在任何两个不同的点,X,1,，,X,2,，使,X,成为这两个点连线上的一个点。或者这样叙述：对任何,X,1,C,，,X,2,C,，不存在,X=,X,1,+(1-,),X,2,C,（,0,1,），,则称,X,是凸集,C,的顶点。,三、几,个定理的证明,定理,1,若线性规划问题存在可行解，则问题的可行域是,凸集。,证：设,C,为满足约束条件的集合，,X,1,=,（,x,11,x,12,x,1n,),T,X,2,=(x,21,x,22,x,2n,),T,为,C,内任意两点，即,X,1,C,，,x,2,C,，将,X,1,，,X,2,代约束条件有：,X,1,，,X,2,连线上任意一点可以表示为：,将（,1.9,）代入（,1.10,）得：,即：,引理,线性规划问题的可行解,X=,（,x,1,x,2,x,n,),为基可行解的充要条件是,X,的正分量所对应的系数列向量线性独立的。,证,：（,1,）必要性（结论,条件）,由基可行解的定义显然成立。,（,2,）充分性。,（,条件,结论,）若向量,P,1,P,2,P,k,线性独立，则必有,km,.,当,k=m,时，它们恰好构成一个基，从而,X=(x,1,x,2,x,m,0,0,.,0),为相应的基可行解。,当,Km,时，则一定可以从其余列向量中找出,(,m-k,),个与,P,1,P,2,P,k,构成一个基，其对应的解恰为,X,，所以根据定义它是基可行解。,定理,2,线性规划问题的基可行解,X,对应线性规划问题可行域（凸集）的顶点。,证：即要证明,X,是可行域顶点,X,是基可行解,反证法，即,X,不是可行域顶点,X,不是基可行解,（,1,）,X,不是基可行解,X,不是可行域顶点,不失一般性，设,X,的前,m,个分量为正，即：,由引理知,P,1,P,2,P,m,线性相关，即存在一组不全为零的数,i,(i,=1,m),使得有：,1,P,1,+,2,P,2,+,m,P,m,=0 (1.12),(1.12),式乘上一个不为零的数,得：,1,P,1,+,2,P,2,+,m,P,m,=0 (1.13),式,(1.11)+(1.13),得：,(x,1,+,1,)P,1,+(x,2,+,2,)P,2,+(,x,m,+,m,)P,m,=b,式,(1.11)-(1.13),得：,(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,又,可以这样来选取，使得对所有,i=1,2,m,有,x,1,1,0,由引,X,(1),C,X,(2),C,又,X=X,(1),/2+X,(2),/2,即,X,不是可行域的顶点。,（,2,）,X,不是可行域顶点,X,不是基可行解,不失一般性，设,X=(x,1,x,2,x,r,0,0),不是可行域的顶点，因而可以找到可行域内另外两个不同点,Y,和,Z,，,有,X=Y+(1-)Z (01),，或可写成,x,j,=y,j,+(1-),z,j,(0 0,1-0,故当,x,j,=0,时,必有,y,j,=,z,j,=0,因有,故有,式,(1.14)-,式,(1.15),得,因,(,y,j,-z,j,),不全为零,故,p,1,p,r,线性相关,即,X,不是基可行解,定理,3,若线性规划问题有最优解，一定存在一个基可行解是最优解。,证 设,X(0)=(x,1,0,x,2,0,x,n,0,),是线性规划的一个最优解,是目标函数的最大值,.,若,X,(0),不是基可行解,由定理,2,知,X,(0),不是顶点,一定能在可行域内找到通过,X,(0),的直线上的另外两个顶点,(X,(0),+,)0,和,(X,(0),-,)0.,将这两个点代入目标函数有,因,CX,(0),为目标函数的最大值,故有,由此,C,=0,即有,X(x,(0),+,)=CX,(0),=X(X,(0),-,),。如果,(x,(0),+,),或,(x,(0),-,),仍不是基可行解,按上面的方法继续做下去,最后一定可以找到一个基可行解,其目标函数值等于,CX,(0),问题得证。,四、单纯形法迭代原理,1,确定初始基可行解,在约束条件,(1.16),式的变量的系数矩阵中总会存在一个单位矩阵,基可行解：,X=(x,1,x,m,x,m+1,x,n,),T,=(b,1,b,m,0,.,0),T,2,从一个基可行解转换为相邻的基可行解。,定义：,两个基可行解称为相邻的，如果它们 之间变换且仅变换一个基变量。,设初始基可行解中的前,m,个为基变量，即,X,(0),=(x,1,0,x,2,0,x,m,0,0,0),T,代入约束条件,(1.16),有,写出式,(1.19),系数的增广矩阵,因,P,1,P,m,一个基，其他向量,P,j,可用这个基的线性组合来表示，有,将,(1.20),式乘上一个正的数,0,得,（,1.19),式,+(1.21),式并经过整理后有,要使,X,(1),是一个基可行解，因规定,0,，故应对所有,i=1,m,，存在,令这,m,个不等式至少有一个等号成立。因为,a,ij,0,时，,(1.23),式显然成立，故可令,故,X,(1),是一个可行解。,又因与变量,x,1,1,x,1,l,x,1,l-1,x,1,l+1,x,m,x,j,对应的向量，经重新排列后加上,b,列有如下形式的增广矩阵。,因,a,lj,0,，故由上述矩阵元素组成的行列式不为零，,P,1,P,2,P,l-1,P,j,P,l+1,P,m,是一个基。在上述增广矩阵中进行行的初等变换，将第,l,行乘上,(1/a,lj,),，再分别乘以,(-,a,ij,)(i,=1,k,l-1,l+1,m),加到各行上去，则增广矩阵左半部变成为单位矩阵，又因,b,l,/a,lj,=,，故,X,(1),=(b,1,-,a,1j,b,l-1,-a,l-1,j,b,l+1,-a,l+1,j,b,m,-,a,mj,),T,由此,X,(1),是同,X,(0),相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。,3.,最优性检验和解的判别,将基可行解,X,(0),和,X,(1),分别代入目标函数得,3,最优性检验和解的判别,（,1,）当所有的,j,0,时，该顶点是最优解。,（,2,）当所有的,j,0,，又对某个非基变量,x,j,有,c,j,-,z,j,=0,，有无穷多解。,（,3,）如果存在某个,j,0,，又,P,j,0,，有无界解。,作业：,P45,（,1,）,1.9,（,2,）,1.10,