(精品)运筹学课件 第二节 图解法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学教程,*,运筹学教程,第二节 图解法,2.1,图解法步骤,图解法就是用几何作图的方法分析并求出其最优解的过程。,求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。,图解法举例,实施图解法，以求出,最优,生产计划,（,最优解,）,maxZ,=2x,1,+3x,2,s.t.,由于线性规划模型中只有两个决策变量，因此只需建立平面直角系就可以进行图解了。,第一步：建立平面直角坐标系，标出坐标原点,坐标轴的指向和单位长度。,用,x,1,轴表示产品,A,的产量，用,x,2,轴表示产品,B,的,产量。,第二步：对约束条件加以图解。,第三步：画出目标函数等值线，结合目标函数,的要求求出最优解,-,最优生产方案,。,约束条件的图解,:,每一个约束不等式在平面直角坐标系中都代表一个半平面，只要,先画出该半平面的边界,，然后,确定是哪个半平面,。,第一个约束条件,1/3 x,1,+1/3 x,2,1,令,1/3 x,1,+1/3 x,2,1,，,即直线,AB,。,1/3 x,1,+1/3 x,2,1,所代表的半平面,的边界,:,两个约束条件及非负条件,x,1,x,2,0,所代表的公共部分图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。,第二个约束条件的边界,直线,CD:,1/3x,1,+4/3 x,2,=3,5,4,l,1,3,B,2,D,（,1/3,）,x,1,+(4/3)x,2,=3,l,2,1,0,1,2,3,A,4,5,6,7,8,9,C,(1/3),x,1,+(1/3)x,2,=1,令,Z=2x,1,+3x,2,=c,其中,c,为任选的一个常数,，在图中画出直线,2x,1,+3x,2,=c,这条直线上的点即对应着一个可行的生产方案，即使两种产品的总利润达到,c,。,这样的直线有无数条，而且相互平行，称这样的直线为,目标函数等值线,。,只要,画出,两条目标函数等值线,，比如令,c,0,和,c=6,，,就能看出,目标函数值递增的方向,，,用,箭头标出,这个方向。,图中两条虚线,l,1,和,l,2,就,分别代表 目标函数等值线,2x,1,+3x,2,=0,和,2x,1,+3x,2,=6,箭头表示使两种产品的,总利润递增的方向。,沿着箭头,的方向,平移,目标函数等值线，使其,达到可行域中的最远点,E,E,点就是要求的最优点，它对应的相应坐标,x,1,=1,x,2,=2,就是最有利的产品组合，即生产,A,产品等于,1,，,B,产品等于,2,能使两种产品的总利润达到最大值,max Z=2,1+3,2=8,，,x,1,=1,x,2,=2,就是线性规划模型的,最优解,，,Zmax,=8,就是相应的目标函数最优值,。,尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精确值。,比如,E,点对应的坐标值我们可以通过求解下面的联立方程，即求直线,AB,和,CD,的交点来求得。,直线,AB:1/3x,1,+1/3x,2,=1,直线,CD:1/3x,1,+4/3x,2,=3,0 1 2 3 4 5 6 7 8 9 x,1,5 4 3 2 1,x,2,（,3,，,0,）,C=6,（,9,，,0,）,（,0,，,9/4,）,E（1，2）,C=0,（,0,，,3,）,设三种产品的产量分别是,x,1,、,x,2,、,x,3,吨，由于有三个决策变量，用图解法求解下面的线性规划时，必须首先建立空间直角坐标系。,变量超过,2,个情况,0,x,1,x,2,5x,2,=15,6x,1,+2x,2,=24,x,1,+x,2,=5,x,2,=-2x,1,+Z,最优解的确定,:,可行域使目标函数达到,最优的点,目标函数的,Z,值逐渐增大，,一直移动到目标函数的直线与约束条,件包围成的凸多边形相切时为止，切,点就是最优解。,(x,1,x,2,)=(3.5,1.5),z=8.5,1,、无穷多个最优解：将目标函数,max Z=x,1,+x,2,2,、,无界解：可行域可伸展到无穷，导致目标函数增大到无限。产生无界解的原因是由于在建立实际问题的数学模型中遗漏某些必要的资源约束。,3,、无解：不存在满足约束条件的可行域。,2.2,线性规划求解的各种可能的结局,2.2.1,无穷多个最优解,该线性规划的可行域为上图中四边形,OAED,（,即阴影区），虚线为目标函数等值线，箭头为目标函数值递增的方向。沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一条边界线段,AE,重合，这个结果表明，该线性规划有,无穷多个最优解,线段,AE,上的所有点都是最优点，它们都使目标函数取得相同的最大值,Zmax,=3,。,2.2.2,无界解,X1,X2,本例中的可行域是一个无界区域，,如图中阴影区所示。虚线为目函数,等值线，沿着箭头所指的方向平移可,以使目标函数值无限制地增大，因此,找不到最优解。,如果实际问题是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大，解释不合理。此时应重新检查和修改模型，否则就没有实际意义。,x,1,x,2,2.2.3,无解,x1,X2,2.3,图解法得到的启示,1,、求解线性规划问题时，解的情况：唯一最优解、无穷多个最优解、无界解，无解。,2,、若线性规划的可行域存在，则可行域一定是凸多边形（凸集）。,3,、若线性规划的最优解存在，则最优解（或最优解之一）一定是可行域凸集的一个顶点。,4,、解题思路：先找任一个顶点，计算目标函数；比较周围顶点的目标函数的值是否比此值大，一直找到使目标函数达到最大的顶点。,图解法小结,使用条件：,仅有两个至多不超过三个决策变量的线性规划。,基本步骤：,第一步建立平面直角坐标系；,第二步根据约束条件和非负条件画出可行域。,第三步作出目标函数等值线（至少两条），结合目标,函数优化要求，平移目标函数等值线求出最优解。,图解法的优缺点：简单、直观但有局限性。,第三节 单纯形法原理,1.3.1,线性规划问题解概念,：,可行解：满足所有约束条件的解。,最优解：使目标函数达到最大值的可行解。,基,:,设,A,为约束方程组的,m,n,阶系数矩阵,(nm),R(A)=m,B,是矩阵,A,中的一个,m,m,阶满秩子,矩阵,称,B,是线性规划问题的一个基,设,列向量,P,j,(j,=1,2,m),为基向量,P,j,所对应的变量,x,j,基变量,其余变量为非基变量,.,秩,:,设在矩阵,A,中存在一个不等于零的,r,阶子式,D,且所有的,r+1,阶,子式全等于零,那么,D,为,A,的最高阶非零子式,数,r,称为,A,的秩,.,P,1,P,2,P,j,P,m,基解,:,在约束方程组中,令所有的非基变量,有因为有,根据克莱姆法则,有,m,个约束方程可解出,m,个变量的唯一解,将此解加上非基变量取,0,的值有,此解为线性规划问题的基解,.,基解的个数不会超过,基可行解：基解当中的可行解。,可行基：对应于基可行解的基称为可行基,例题 找出全部基解，指出其中的基可行解，确定,最优解,P,1,P,2,P,3,P,4,P,5,B,1,=(P,3,P,4,P,5,),B,2,=(P,2,P,3,P,4,),B,3,=(P,1,P,4,P,5,),B,4,=(P,2,P,3,P,5,),B,5,=(P,1,P,3,P,5,),B,6,=(P,1,P,2,P,5,),B,7,=(P,1,P,2,P,4,),B,8,=(P,1,P,2,P,3,),B,9,=(P,3,P,4,P,1,),B,10,=(P,2,P,4,P,5,),基,x1,x2,x3,x4,x5,Z,是否基可行解,P3,P4,P5,0,0,5,10,4,5,P2,P3,P4,0,4,5,2,0,17,P1,P4,P5,5,0,0,5,4,10,P2,P3,P5,0,5,5,0,-1,20,P1,P3,P5,10,0,-5,0,4,15,P1,P2,P5,5,2.5,0,0,1.5,17.5,P1,P2,P4,5,4,0,-3,0,22,P1,P2,P3,2,4,3,0,0,19,基的概念的理解,对于线性规划的约束条件,AX,=,b,X,0,设,B,是,A,矩阵中的一个非奇异的,mm,子矩阵，则称,B,为线性规划的一个基。,设,B,是线性规划的一个基，则,A,可以表示为,A=,B,N,X,也可相应地分成,其中,X,B,为,m1,向量，称为基变量，其分量与基,B,的列向量对应；,X,N,为,(n-m)1,向量，称为非基变量，其分量与非基矩阵,N,的列对应。这时约束等式,AX,=,b,可表示为,或,BX,B,+,NX,N,=,b,若,X,N,取确定的值，则,X,B,有唯一的值与之对应,X,B,=,B,-1,b,-,B,-1,NX,N,特别，取,X,N,=,0,，,这时有,X,B,=,B,-1,b,。,线性规划的解称为线性规划与基,B,对应的基解。,若其中基变量的值,X,B,=,B,-1,b,0,，,则称以上的基解为一基可行解，相应的基,B,称为可行基。,基本概念：,凸集,如果集合,C,中任意两个点,X,1,X,2,，,其连线上的所有点也都是集合,C,中的点，则称,C,为凸集,用数学解析式表示：若任意两点,X,C,，,X,2,C,的连线上的一切点：,X,1,+,（,1-,）,X,2,C,（,01,），,则称,C,为,凸集,。,1.3.2,凸集及其顶点,顶点,设,C,是凸集，对任何的,X,C,，,X,2,C,有,XX,+,（,1-,）,X,（,01,）,则称,X,为,C,的一个,顶点,。,说明集合,C,中不存在任何两个不同的点,X,1,X,2,使,X,成为这两个点连线上的一个点,.,1.3.3,几个基本定理,定理,1,线性规划问题存在可行解，则问题的可行域 是凸集。,证明思路,：,根据凸集定义，采用直接法证明；,具体步骤：,从,C,中任取两个不同的点，,应满足 可行解定义中相应的条件；,证明,X=X,(1),+(1-)X,(2),D,(,利用，证明,X,满足凸集定义中相应的条件,),X,1,x,2,为,C,内任意两点,将两点代入约束条件,:,X,1,X,2,连线上的任意一点,X,将,X,代入约束条件,X,为,C,内任意点,所以,C,为凸集,引理,线性规划问题的可行解,为基可行解的,充分必要条件,是,X,的正分量所对应的系数列向量线性独立,。,证明要点：,引理,:,X,为,LP,的基本可行解,X,的正分量所对应的系数列向量线性无关,必要性,由基本可行解定义直接证得,充分性,正分量,K,个,线性无关,k=m,X=(x,1,x,2,x,m,0,0),T,即为,基本可行解,km,补齐得基退化的基本可行解,定理,线性规划问题的基可行解,X,对应线性规划问题可行域的顶点。,证明思路：,首先可行域非空有界就肯定有最优解,本定理要证明的是,X,不是可行域的顶点,X,不是基可行解,(1).X,不是基可行解 不是可行域的顶点,不失一般性,假设,X,的前,m,个分量为正,所以有,:,由引理得到,P,1,P,2,P,m,线性相关,存在一组不全为,0,的数,k,1,k,2,k,m,使,u,可以这样选取,:,使所有的,i=1,2,m,X,不是可行域的顶点,(2).X,不是可行域的顶点,X,不是基可行解,X,不是基可行解,定理,若线性规划问题有最优解，一定存在一个基可行解是最优解,证明,:,设,是线性规划的最优解,是目标函数的最大值,如果,X,(0),不是基可行解,由定理,2,得到,X,(0),不是顶点,可在找到另外,2,点,将以上两点代入目标函数有,:,启示：,1,、,LP,的可行域一定是凸集，但是凸集不一定成为,LP,的可行域，而非凸集一定不会是,LP,的可行域。,2,、线性规划的基本可行