运筹学第2讲：图解法及单纯形法基本概念.ppt

第2讲：图解法及单纯形法基本概念,浙江工业大学经贸管理学院 曹柬,一、图解法：,确定直角平面坐标系，图示非负约束条件 图示约束条件，找出可行域 图示目标函数，确定最优解,max z=2 x1+x2 s.t.x1+x2 5 6 x1+2x2 24 5x2 15 x1,x2 0,例1：,运筹学 第2讲：图解法及单纯形法基本概念,图解法仅适于两个变量的LP模型从图解法中可以看出LP模型的解的情况,二、LP模型解的几种情况,一、惟一最优解二、无穷多最优解三、无界解四、无可行解,运筹学 第2讲：图解法及单纯形法基本概念,min z=2 x1+3 x2s.t.x1+x2 350,x1 125 2 x1+x2 600,x1 0，x2 0。,x1,x2,600,600,100,100,300,300,解线性方程组 x1+x2=350 2 x1+x2=600得最优解 x1=250 x2=100最优值 z=800,例2：,惟一最优解,运筹学 第2讲：图解法及单纯形法基本概念,A,max z=x1+x2 s.t.x1+x2 5，2x1+x2 8 5x2 15，x1,x2 0,无穷多最优解,A,B,线段AB上的任意一点都是模型的解,例3：,运筹学 第2讲：图解法及单纯形法基本概念,max z=x1+x2 s.t.-2x1+x2 2，x1-3x2 3 x1,x2 0,无界解,可行域伸展到无穷，则z也可增大到无穷，即最优解无界,运筹学 第2讲：图解法及单纯形法基本概念,例4：,原因为模型中缺乏必要的约束条件,max z=x1+x2 s.t.x1+x2 2，2x1+2x2 6 x1,x2 0,无可行解,x2,不存在满足所有约束条件的可行域，即解无可行域，模型无解,例5：,运筹学 第2讲：图解法及单纯形法基本概念,原因是约束条件之间有矛盾,无界解：LP模型存在可行域，模型有解，但解无界，趋于无穷，即无最优解 无可行解(无解)：LP模型不存在可行域，模型无解。,运筹学 第2讲：图解法及单纯形法基本概念,三、单纯形法的几个基本概念,可行解、可行域、最优解、最优值（P11）,运筹学 第2讲：图解法及单纯形法基本概念,基(阵)（P14）基向量、基变量、基变矢、非基变量、非基变矢（P14）,基解、基可行解、可行基（P14）,例6：,运筹学 第2讲：图解法及单纯形法基本概念,将原模型改为标准型：,max z=3 x1+5x2 s.t.x1 8 2x2 12 3x1+4x2 36 x1,x2 0,其中，x3,x4,x5为松弛变量,max z=3 x1+5x2+0 x3+0 x4+0 x5s.t.x1+x3=8 2x2+x4=12 3x1+4x2+x5=36 xj 0，j=1,2,5,运筹学 第2讲：图解法及单纯形法基本概念,则模型的系数矩阵为,n=5,m=3,rA=3,运筹学 第2讲：图解法及单纯形法基本概念,P3,P4,P5是三个基向量,与P3,P4,P5相对应的三个变量x3,x4,x5是基变量,XB=x3,x4,x5T是基变矢,XN=x1,x2T是非基变矢,得到XB=x3,x4,x5T=8,12,36T,其也是基可行解,此时，z=0,(1),运筹学 第2讲：图解法及单纯形法基本概念,XB=x2,x3,x5T是基变矢,XN=x1,x4T是非基变矢,得到XB=x2,x3,x5T=6,8,12T,也是基可行解,此时，z=30,(2),若用P2替换P4，则,P2,P3,P5是三个基向量,运筹学 第2讲：图解法及单纯形法基本概念,P=(P1,P2,P3)=,XB=x1,x2,x3T,XN=x4,x5T,得到XB=x1,x2,x3T=4,6,4T,此时，z=42,(3),若用P1替换P5，则,得到基解,运筹学 第2讲：图解法及单纯形法基本概念,可不断变换可行基，并求得相应的基可行解（每个基可行解对应于可行域上的一个顶点），直至得到满足非负条件的最优解，这就是单纯形法的基本思想。,此时，z=45，解无效,四、几个基本定理,凸集：集合C中任意两点间x1、x2，其连线上的所有点ax1+(1-a)x2(0a1)也是C中的点，则C为凸集,定理一：线性规划问题的可行解集为凸集,定理二：线性规划问题的基可行解对应于可行域的顶点,定理三：线性规划问题如有最优解，则一定在其可行域的顶点上达到。如果几个顶点都是最优解，则在这些顶点的每个凸线性组合上也达到最优解,运筹学 第2讲：图解法及单纯形法基本概念,顶点：对任何x1 C，x2 C，不存在x=ax1+(1-a)x2(0a1)，则x为顶点,作业：2.2(1),(4)-图解法2.4,2.5,2.6,运筹学 第2讲：图解法及单纯形法基本概念,