运筹学课件第二节图解法.ppt

1、第二节第二节 图解法图解法2.1图解法步骤图解法步骤图解法就是用几何作图的方法分析并求出图解法就是用几何作图的方法分析并求出其最优解的过程。其最优解的过程。求解的思路是：先将约束条件加以图求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行行域），然后结合目标函数的要求从可行域中找出最优解。域中找出最优解。实施图解法，以求出实施图解法，以求出生产计划生产计划（）maxZ=2x1+3x21/3x+1/3x11/3x+4/3x3 x,x0121212s.t.由于线性规划模型中只有两个决策变量，因此由于线性规划模

2、型中只有两个决策变量，因此只需建立平面直角系就可以进行图解了。只需建立平面直角系就可以进行图解了。第一步：建立平面直角坐标系，标出坐标原点第一步：建立平面直角坐标系，标出坐标原点,坐标轴的指向和单位长度。坐标轴的指向和单位长度。用用x1轴表示产品轴表示产品A的产量，用的产量，用x2轴表示产品轴表示产品B的的 产量。产量。第二步：对约束条件加以图解。第二步：对约束条件加以图解。第三步：画出目标函数等值线，结合目标函数第三步：画出目标函数等值线，结合目标函数的要求求出最优解的要求求出最优解-最优生产方案最优生产方案。约束条件的图解约束条件的图解:每一个约束不等式在平面直角坐标系中都每一个约束不等式

3、在平面直角坐标系中都代表一个半平面，只要代表一个半平面，只要，然后，然后。第一个约束条件第一个约束条件 1/3 x1+1/3 x2 1 令令1/3 x1+1/3 x2 1，即直线即直线AB。1/3 x1+1/3 x2 1 所代表的半平面所代表的半平面 的边界的边界:5 4 l1 3B B 2 D （1/3）x1+(4/3)x2=3 l2 1 0 1 2 3A A 4 5 6 7 8 9C C (1/3)x1+(1/3)x2=1 令令 Z=2x1+3x2=c,其中其中，在图中画出直线，在图中画出直线 2x1+3x2=c,这条直线上的点即对应着一个可行的生产方案，即使两种产品的总利润达这条直线上的

4、点即对应着一个可行的生产方案，即使两种产品的总利润达到到c。这样的直线有无数条，而且相互平行，称这样的直线为这样的直线有无数条，而且相互平行，称这样的直线为。画出画出，比如令，比如令c0和和c=6，就能看出，就能看出 ，用用这个方向。这个方向。图中两条虚线图中两条虚线 l1和和l2就就 分别代表分别代表 目标函数等值线目标函数等值线 2x1+3x2=0 和和 2x1+3x2=6,箭头表示使两种产品的箭头表示使两种产品的 总利润递增的方向。总利润递增的方向。X2 5 4 l1 3B B E 2 D （1/3）x1+(4/3)x2=3 l2 1 x1 0 1 2 3A A 4 5 6 7 8 9C

5、 C (1/3)x1+(1/3)x2=1 最 优 点 的方向的方向目标函数等值线，使其目标函数等值线，使其,E点就是要求的最优点，它对应点就是要求的最优点，它对应的相应坐标的相应坐标 x1=1,x2=2 就是最有利的产品组合，即生就是最有利的产品组合，即生产产A产品等于产品等于1，B产品等于产品等于2能使两种产品的总利润能使两种产品的总利润达到最大值达到最大值 max Z=2 1+3 2=8，就是线性就是线性规划模型的规划模型的，5 4 l1 3B B E 2 D （1/3）x1+(4/3)x2=3 l2 1 0 1 2 3A A 4 5 6 7 8 9C C (1/3)x1+(1/3)x2=

6、1 最优点 尽管最优点的对应坐标可以直接从图中尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通确地看出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精常总是用解联立方程的方法求出最优解的精确值。确值。比如比如E点对应的坐标值我们可以通过求点对应的坐标值我们可以通过求解下面的联立方程，即求直线解下面的联立方程，即求直线AB和和CD的交的交点来求得。点来求得。直线直线AB:1/3x1+1/3x2=1 直线直线CD:1/3x1+4/3x2=3 0 1 2 3 4 5 6 7 8 9

7、 x1 5 4 3 2 1x2M ax Z=2 x1+3 x2 st.1/3 x+1/3 x 1 1/3x+4/3 x 3 x,x0 121212（3，0）C=6（9，0）（0，9/4）C=0（0，3）M ax Z=2 x1+3 x2+x3 s.t 1/3x+1/3x+1/3x11/3x+4/3x+7/3x3 x,x,x0123123123 122121212max25155.6224,0Zxxxxxstxxx x0 x1x25x2=156x1+2x2=24x1+x2=5 x2=-2x1+Z最优解的确定:可行域使目标函数达到最优的点,目标函数的Z值逐渐增大，一直移动到目标函数的直线与约束条件包

8、围成的凸多边形相切时为止，切点就是最优解。(x1,x2)=(3.5,1.5),z=8.512 2.2线性规划求解的各种可能的结局线性规划求解的各种可能的结局 2.2.1 max Z=x1+x2 s.t 1/3x+1/3x11/3x+4/3x3 x,x0121212 该线性规划的可行域为上图中四边形该线性规划的可行域为上图中四边形OAED（即阴影区），虚线为目标函数等值（即阴影区），虚线为目标函数等值线，箭头为目标函数值递增的方向。沿着箭线，箭头为目标函数值递增的方向。沿着箭头的方向平移目标函数等值线，发现平移的头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一最终结果

9、是目标函数等值线将与可行域的一条边界线段条边界线段AE重合，这个结果表明，该重合，这个结果表明，该线性规划有线性规划有线段线段AE上上的所有点都是最优点，它们都使目标函数取的所有点都是最优点，它们都使目标函数取得相同的最大值得相同的最大值Zmax=3。max Z=x1+2 x2 s.t-2x+x1x,x01212 X1X2 本例中的可行域是一个无界区域，本例中的可行域是一个无界区域，如图中阴影区所示。虚线为目函数如图中阴影区所示。虚线为目函数 等值线，沿着箭头所指的方向平移可等值线，沿着箭头所指的方向平移可 以使目标函数值无限制地增大，因此以使目标函数值无限制地增大，因此 找不到最优解。找不到

10、最优解。如果实际问题是一个生产计划问题，其经济含义就是某些资源如果实际问题是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大，解释不合理。此时应重新是无限的，产品的产量可以无限大，解释不合理。此时应重新检查和修改模型，否则就没有实际意义。检查和修改模型，否则就没有实际意义。x1x2 max Z=2x1+x2 s.t0 x,x2x12x+x212121x x1X2 1 1、求解线性规划问题时，解的情况：唯一最优解、无穷多个、求解线性规划问题时，解的情况：唯一最优解、无穷多个最优解、无界解，无解。最优解、无界解，无解。2 2、若线性规划的可行域存在，则可行域一定是凸多边形（凸

11、、若线性规划的可行域存在，则可行域一定是凸多边形（凸集）。集）。3 3、若线性规划的最优解存在，则最优解（或最优解之一）一、若线性规划的最优解存在，则最优解（或最优解之一）一定是可行域凸集的一个顶点。定是可行域凸集的一个顶点。4 4、解题思路：先找任一个顶点，计算目标函数；比较周围顶、解题思路：先找任一个顶点，计算目标函数；比较周围顶点的目标函数的值是否比此值大，一直找到使目标函数达到点的目标函数的值是否比此值大，一直找到使目标函数达到最大的顶点。最大的顶点。图解法小结图解法小结 使用条件：使用条件：仅有两个至多不超过三个决策变量的线性规划。仅有两个至多不超过三个决策变量的线性规划。基本步骤：

12、基本步骤：第一步建立平面直角坐标系；第一步建立平面直角坐标系；第二步根据约束条件和非负条件画出可行域。第二步根据约束条件和非负条件画出可行域。第三步作出目标函数等值线（至少两条），结合目标第三步作出目标函数等值线（至少两条），结合目标函数优化要求，平移目标函数等值线求出最优解。函数优化要求，平移目标函数等值线求出最优解。图解法的优缺点：图解法的优缺点：简单、直观但有局限性。简单、直观但有局限性。第三节第三节 单纯形法原理单纯形法原理1.3.1线性规划问题解概念：可行解：满足所有约束条件的解。最优解：使目标函数达到最大值的可行解。njxmibxaxcZjnjijijnjjj,.2,1,0,.2,

13、1,max11基基:设设A 为约束方程组的为约束方程组的mn阶系数矩阵阶系数矩阵(nm),R(A)=m,B是矩阵是矩阵A中的一个中的一个mm阶满秩子阶满秩子矩阵矩阵,称称B是线性规划问题的一个基是线性规划问题的一个基,设设列向量列向量Pj(j=1,2,m)为基向量为基向量,Pj 所对应的变量所对应的变量xj基变量基变量,其余变量为非基变量其余变量为非基变量.),.,(.211111mmmmmPPPaaaaB秩秩:设在矩阵设在矩阵A中存在一个不等于零的中存在一个不等于零的r阶子式阶子式D,且所有的且所有的r+1阶阶子式全等于零子式全等于零,那么那么D为为A的最高阶非零子式的最高阶非零子式,数数r

14、称为称为A的秩的秩.P1 P2PjPm基解基解:在约束方程组中在约束方程组中,令所有的非基变量令所有的非基变量 ,有因为有有因为有 根据克莱姆法则根据克莱姆法则,有有m个约束方程可解出个约束方程可解出m个变量的唯一解个变量的唯一解,将此解加上非基变量取将此解加上非基变量取0的值有的值有此解为线性规划问题的基解此解为线性规划问题的基解.基解的个数不会超过基解的个数不会超过0.21nmmxxx0BTmBxxxX),.,(21mnCTmxxxX)0,.,0,0,.,(21基可行解：基解当中的可行解。基可行解：基解当中的可行解。可行基：对应于基可行解的基称为可行基可行基：对应于基可行解的基称为可行基例

15、题 找出全部基解，指出其中的基可行解，确定最优解041025.32max515242131321xxxxxxxxstxxxZ100100102100101A P1 P2 P3 P4 P5B1=(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)基基x1x2x3x4x5Z是否基可行解是否基可行解P3,P4,P50051045P2,P3,P40452017P1,P4,P55005410P2,P3,

16、P50550-120P1,P3,P5100-50415P1,P2,P552.5001.517.5P1,P2,P4540-3022P1,P2,P32430019基的概念的理解基的概念的理解对于线性规划的约束条件AXAX=b bX X0 0设B B是A A矩阵中的一个非奇异的mm子矩阵，则称B B为线性规划的一个基。设B B是线性规划的一个基，则A A可以表示为A=A=B,N B,N X X也可相应地分成NBXXX其中XB为m1向量，称为基变量，其分量与基B的列向量对应；XN为(n-m)1向量，称为非基变量，其分量与非基矩阵N的列对应。这时约束等式AX=b可表示为或BXB+NXN=b若XN取确定的

17、值，则XB有唯一的值与之对应XB=B-1b-B-1NXNbXXNBNB.,特别，取X XN=0 0，这时有X XB=B B-1b b。线性规划的解称为线性规划与基B B对应的基解。若其中基变量的值X XB=B B-1b b0 0，则称以上的基解为一基可行解，相应的基B B称为可行基。0bBXXX1NB 如果集合如果集合C中任意两个点中任意两个点X1,X2，其连线上的所有，其连线上的所有点也都是集合点也都是集合C中的点，则称中的点，则称C为凸集为凸集用数学解析式表示：若任意两点用数学解析式表示：若任意两点XC，X2C的连线上的一切的连线上的一切点：点：（01），则称），则称C为为凸集凸集。1.3

18、.2凸集及其顶点凸集及其顶点 设设C是凸集，对任何的是凸集，对任何的 X C，X2 C 有有 则称则称X为为C的一个的一个顶点顶点。说明集合说明集合C中不存在任何两个不同的点中不存在任何两个不同的点X1,X2,使使X成为成为这两个点连线上的一个点这两个点连线上的一个点.线性规划问题存在可行解，则问题线性规划问题存在可行解，则问题的可行域的可行域 是凸集。是凸集。：从从C中任取两个不同的点，中任取两个不同的点，应满足应满足 可行解定义中相应的条件；可行解定义中相应的条件；证明证明X=X(1)+(1-)X(2)D (利用利用，证明，证明X满足凸集定义中相应的条件满足凸集定义中相应的条件)TnTnx

19、xxXxxxX),.,(,),.,(222212112111X1,x2 为C内任意两点,将两点代入约束条件:bbbxPxPxxPxPXXXbxPbxPnjjjnjjjnjjjjnjjjjjnjnjjj)1()1()1()10(;)1(;12111211212111X1,X2连线上的任意一点X将X代入约束条件X为C内任意点,所以C为凸集A 线性规划问题的可行解线性规划问题的可行解 为基可行解的为基可行解的充分必要条件充分必要条件。TnxxxX),.,(21正分量正分量K个个k=m X=(xX=(x1 1,x,x2 2,x,xm m,0,0),0,0)T T即为即为 基本可行解基本可行解km 补齐

20、得基补齐得基退化的基本可行解退化的基本可行解 线性规划问题的基可行解线性规划问题的基可行解X对对应线性规划问题可行域的顶点。应线性规划问题可行域的顶点。首先可行域非空有界就肯定有最优解首先可行域非空有界就肯定有最优解X不是可行域的顶点不是可行域的顶点X不是基可行解不是基可行解(1).X不是基可行解 不是可行域的顶点不失一般性,假设X的前m个分量为正,所以有:)1(1mjjjbxP由引理得到P1,P2,Pm,线性相关,存 在 一 组 不 全 为 0 的 数k1,k2,km,使bPukxPukxPukxbPukxPukxPukxPukPukPukuPkPkPkmmmmmmmmmm)(.)()(:)

21、2()1()(.)()(:)2()1()2(0.00.22211122211122112211上式乘以(1)1122(2)1122(1)(2)(1)(2)(),(),.,(),0,.,0(),(),.,(),0,.,00;1122mmmmiiXxukxukxukXxukxukxukxukXC XCXXXu可以这样选取:使所有的i=1,2,mX不是可行域的顶点(2).X不是可行域的顶点 X不是基可行解 线性相关，所以：不全为因为当有点则可行域内的另外不是可行域的顶点设rjjrjjjjrjjjnjjjrjjjnjjjrjjjnjjjjjjjjjrPPPzyzyPbzPzPbyPyPbxPxPzyx

22、zyxZYXZYxxxX,.,0)(0)(:)2()1()2()1(;0,0)1(10;)1(,2)0,.,0,.,(21111111111X不是基可行解 若线性规划问题有最优解，一定存在一个基可行解是最优解若线性规划问题有最优解，一定存在一个基可行解是最优解CCXCXCCXCCCXCXCCXCXCCXXCCCXXCXXxcCXZxxxXnjjjn)0()0()0()0()0()0()0()0()0()0()0()0()0(10)0(00201)0(;0;)()(0;0),.,(证明:设是线性规划的最优解是目标函数的最大值如果X(0)不是基可行解,由定理2得到X(0)不是顶点,可在找到另外2点将以上两点代入目标函数有:)0()0()0(CXXX目标函数等于，并且可以找到一个基可行解后一定的方法继续做下去，最上面仍不是基可行解，按照或如果1 1、LPLP的可行域一定是凸集，但是凸集不的可行域一定是凸集，但是凸集不一定成为一定成为LPLP的可行域，而非凸集一定不的可行域，而非凸集一定不会是会是LPLP的可行域。的可行域。2 2、线性规划的基本可行解和可行域的顶、线性规划的基本可行解和可行域的顶点是一一对应的（类似于坐标与点的对点是一一对应的（类似于坐标与点的对应关系！）应关系！）总结：总结：1、图解法过程。2、线性规划问题解的基本概念。作业：作业：P43 1.1(1)(2),1.2