运筹学-第二节---图解法PPT课件

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