运筹学图解法.pptx

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