运筹学图解法PPT课件

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

2、束条件的图解: 每一个约束不等式在平面直角坐标系中都代表一个半平面，只要，然后。 第一个约束条件 1/3 x1+1/3 x2 1第2页/共41页 令令1/3 x1+1/3 x2 1， 即直线即直线AB。 1/3 x1+1/3 x2 1 所代表的半平面所代表的半平面 的边界的边界:第3页/共41页 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 第4页/共41页 令令 Z=2x1+3x2=c,其中其中，在图中画出直，在图中画出直线线 2x1+3x2=c,这条直线上的点即对应着一个

3、可行的生产方案，即使这条直线上的点即对应着一个可行的生产方案，即使两种产品的总利润达到两种产品的总利润达到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

4、 l2 1 x1 0 1 2 3A A 4 5 6 7 8 9C C (1/3)x1+(1/3)x2=1 最 优 点 第5页/共41页 的方向的方向目标函数等值线，使其目标函数等值线，使其, 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

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

6、 1/3x1+1/3x2=1 直线直线CD: 1/3x1+4/3x2=3第7页/共41页 0 1 2 3 4 5 6 7 8 9 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）第8页/共41页M ax Z = 2 x1 +3 x2 +x3 s.t 1/3x +1/3x +1/3x11/3x +4/3x +7/3x3 x ,x ,x0123123123 第9页/共41页122121212max25155.6224,0Zxxxxx

7、stxxx x0 x1x25x2=156x1+2x2=24x1+x2=5 x2=-2x1+Z最优解的确定:可行域使目标函数达到最优的点,目标函数的Z值逐渐增大，一直移动到目标函数的直线与约束条件包围成的凸多边形相切时为止，切点就是最优解。(x1,x2)=(3.5,1.5),z=8.5第10页/共41页12 2.2线性规划求解的各种可能的结局第11页/共41页 2.2.1 max Z= x1 + x2 s.t 1/ 3x +1/ 3x11/ 3x +4 / 3x3 x ,x0121212 第12页/共41页 该线性规划的可行域为上图中四边该线性规划的可行域为上图中四边形形OAED（即阴影区），虚

8、线为目标函数等（即阴影区），虚线为目标函数等值线，箭头为目标函数值递增的方向。沿着值线，箭头为目标函数值递增的方向。沿着箭头的方向平移目标函数等值线，发现平移箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的的最终结果是目标函数等值线将与可行域的一条边界线段一条边界线段AE重合，这个结果表明，重合，这个结果表明，该线性规划有该线性规划有线段线段AE上的所上的所有点都是最优点，它们都使目标函数取得相有点都是最优点，它们都使目标函数取得相同的最大值同的最大值Zmax=3。 第13页/共41页 max Z = x1 +2 x2 s.t -2x +x1x ,x01212 X1

9、X2第14页/共41页 本例中的可行域是一个无界区域，本例中的可行域是一个无界区域， 如图中阴影区所示。虚线为目函数如图中阴影区所示。虚线为目函数 等值线，沿着箭头所指的方向平移可等值线，沿着箭头所指的方向平移可 以使目标函数值无限制地增大，因此以使目标函数值无限制地增大，因此 找不到最优解。找不到最优解。 如果实际问题是一个生产计划问题，其经济含义就是某些如果实际问题是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大，解释不合理。此时资源是无限的，产品的产量可以无限大，解释不合理。此时应重新检查和修改模型，否则就没有实际意义。应重新检查和修改模型，否则就没有实际意义。

10、x1x2第15页/共41页 max Z = 2x1 + x2 s.t0 x,x2x12x+ x212121x x1X2第16页/共41页 1 1、求解线性规划问题时，解的情况：唯一最优解、无穷多、求解线性规划问题时，解的情况：唯一最优解、无穷多个最优解、无界解，无解。个最优解、无界解，无解。2 2、若线性规划的可行域存在，则可行域一定是凸多边形、若线性规划的可行域存在，则可行域一定是凸多边形（凸集）。（凸集）。3 3、若线性规划的最优解存在，则最优解（或最优解之一）、若线性规划的最优解存在，则最优解（或最优解之一）一定是可行域凸集的一个顶点。一定是可行域凸集的一个顶点。4 4、解题思路：先找任

11、一个顶点，计算目标函数；比较周围、解题思路：先找任一个顶点，计算目标函数；比较周围顶点的目标函数的值是否比此值大，一直找到使目标函顶点的目标函数的值是否比此值大，一直找到使目标函数达到最大的顶点。数达到最大的顶点。第17页/共41页图解法小结图解法小结 使用条件：使用条件：仅有两个至多不超过三个决策变量的线性规划。仅有两个至多不超过三个决策变量的线性规划。基本步骤：基本步骤：第一步建立平面直角坐标系；第一步建立平面直角坐标系；第二步根据约束条件和非负条件画出可行域。第二步根据约束条件和非负条件画出可行域。第三步作出目标函数等值线（至少两条），结合第三步作出目标函数等值线（至少两条），结合目标目

12、标函数优化要求，平移目标函数等值线求出最优解。函数优化要求，平移目标函数等值线求出最优解。 图解法的优缺点：图解法的优缺点： 简单、直观但有局限性。简单、直观但有局限性。 第18页/共41页第三节第三节 单纯形法原理单纯形法原理1.3.1线性规划问题解概念：可行解：满足所有约束条件的解。最优解：使目标函数达到最大值的可行解。njxmibxaxcZjnjijijnjjj,.2 , 1, 0,.2 , 1,max11第19页/共41页基:设A 为约束方程组的mn阶系数矩阵(nm),R(A)=m,B是矩阵A中的一个mm阶满秩子矩阵,称B是线性规划问题的一个基,设列向量Pj(j=1,2,m) 为基向量

13、,Pj 所对应的变量xj基变量,其余变量为非基变量.),.,(.211111mmmmmPPPaaaaB秩:设在矩阵A中存在一个不等于零的r阶子式D,且所有的r+1阶子式全等于零,那么D为A的最高阶非零子式,数r称为A的秩.P1 P2PjPm第20页/共41页基解:在约束方程组中,令所有的非基变量 ,有因为有 根据克莱姆法则,有m个约束方程可解出m个变量的唯一解, 将此解加上非基变量取0的值有此解为线性规划问题的基解.基解的个数不会超过0.21nmmxxx0BTmBxxxX),.,(21mnCTmxxxX)0,.,0 , 0 ,.,(21基可行解：基解当中的可行解。可行基：对应于基可行解的基称为

14、可行基第21页/共41页例题 找出全部基解，指出其中的基可行解，确定最优解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)第22页/共41页 基基x1x2x3x4x5Z是否基可行解是否基可行解P3,P4,P50051045P2,P3,P404520

15、17P1,P4,P55005410P2,P3,P50550-120P1,P3,P5100-50415P1,P2,P552.5001.517.5P1,P2,P4540-3022P1,P2,P32430019第23页/共41页基的概念的理解基的概念的理解对于线性规划的约束条件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第24页/共41页其中XB为m1向量，称为基变量，其分量与基B的列向量对应；XN为(n-m)1向量，称为非基变量，其

16、分量与非基矩阵N的列对应。这时约束等式AX=b可表示为或BXB+NXN=b若XN取确定的值，则XB有唯一的值与之对应XB=B-1b-B-1NXNbXXNBNB.,第25页/共41页特别，取X XN=0 0，这时有X XB=B B-1b b。线性规划的解称为线性规划与基B B对应的基解。若其中基变量的值X XB=B B-1b b0 0，则称以上的基解为一基可行解，相应的基B B称为可行基。 0bBXXX1NB第26页/共41页 如果集合C中任意两个点X1,X2，其连线上的所有点也都是集合C中的点，则称C为凸集用数学解析式表示：若任意两点XC，X2C的连线上的一切点： （01），则称C为凸集。 1

17、.3.2凸集及其顶点第27页/共41页 设C是凸集，对任何的 X C，X2 C 有 则称X为C的一个顶点。 说明集合C中不存在任何两个不同的点X1,X2,使X成为这两个点连线上的一个点.第28页/共41页 线性规划问题存在可行解，则问题的可行域 是凸集。 ：从C中任取两个不同的点， 应满足 可行解定义中相应的条件； 证明X=X(1)+(1-)X(2)D (利用，证明X满足凸集定义中相应的条件)第29页/共41页TnTnxxxXxxxX),.,(,),.,(222212112111X1,x2 为C内任意两点,将两点代入约束条件:bbbxPxPxxPxPXXXbxPbxPnjjjnjjjnjjjj

18、njjjjjnjnjjj)1 ()1 ()1 () 10( ;)1 (;12111211212111X1,X2连线上的任意一点X将X代入约束条件X为C内任意点,所以C为凸集第30页/共41页A 线性规划问题的可行解 为基可行解的充分必要条件。TnxxxX),.,(21第31页/共41页正分量K个k=m X=(xX=(x1 1,x,x2 2, ,x,xm m,0,0,0)0)T T即为 基本可行解km 补齐得基退化的基本可行解第32页/共41页 线性规划问题的基可行解X对应线性规划问题可行域的顶点。首先可行域非空有界就肯定有最优解X不是可行域的顶点X不是基可行解第33页/共41页(1).X不是基

19、可行解 不是可行域的顶点不失一般性,假设X的前m个分量为正,所以有:) 1 (1mjjjbxP由引理得到P1,P2,Pm,线性相关,存在一组不全为0的数k1,k2,km,使bPukxPukxPukxbPukxPukxPukxPukPukPukuPkPkPkmmmmmmmmmm)(.)()(: )2() 1 ()(.)()(: )2() 1 ()2(0.00.22211122211122112211上式乘以第34页/共41页(1)1122(2)1122(1)(2)(1)(2)(),(),.,(),0,.,0(),(),.,(),0,.,00;1122mmmmiiXxukxukxukXxukxukxukxukXC XCXXXu可以这样选取:使所有的i=1,2,mX不是可行域的顶点第35页/共41页(2).X不是可行域的顶点 X不是基可行解 线性相关，所以：不全为因为当有点则可行域