运筹学图解法及单纯形法基本概念.pptx

《运筹学图解法及单纯形法基本概念.pptx》由会员分享，可在线阅读，更多相关《运筹学图解法及单纯形法基本概念.pptx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、二、二、LP模型解的几种情况模型解的几种情况一、惟一最优解一、惟一最优解二、无穷多最优解二、无穷多最优解三、无界解三、无界解四、无可行解四、无可行解运筹学 第2讲：图解法及单纯形法基本概念第1页/共16页min z =2 x1+3 x2s.t.x1+x2 350,x1 125 2 x1+x2 600,x1 0，x2 0。x1x2600600100100300300 x1=1252 x1+x2 =600 x1+x2=350解线性方程组 x1+x2=350 2 x1+x2 =600得最优解 x1=250 x2 =100最优值 z=800可行域例例2 2：Z=2x1+3x2惟一最优解运筹学 第2讲：

2、图解法及单纯形法基本概念A第2页/共16页max z =x1+x2 s.t.x1+x2 5，2x1+x2 8 5x2 15，x1,x2 0无穷多最优解x1x2661133x1+x2=52x1+x2=85x2=15可行域z=x1+x2AB线段线段ABAB上的上的任意一点都任意一点都是模型的解是模型的解例例3 3：运筹学 第2讲：图解法及单纯形法基本概念第3页/共16页max z =x1+x2 s.t.-2x1+x2 2，x1-3x2 3 x1,x2 0无界解x1x2661133-2x1+x2=2z=x1+x2可行域伸展到无穷，可行域伸展到无穷，则则z z也可增大到无穷，也可增大到无穷，即最优解无

3、界即最优解无界x1-3x2=3可行域运筹学 第2讲：图解法及单纯形法基本概念例例4 4：原因为模型中缺乏必要的约束条件第4页/共16页max z =x1+x2 s.t.x1+x2 2，2x1+2x2 6 x1,x2 0无可行解x2x1331122x1+x2=2不存在满足所有约束条件的不存在满足所有约束条件的可行域，即解无可行域，模可行域，即解无可行域，模型无解型无解2x1+2x2=6例例5 5：运筹学 第2讲：图解法及单纯形法基本概念原因是约束条件之间有矛盾原因是约束条件之间有矛盾第5页/共16页(无界解：无界解：LPLP模型存在可行域，模型有解，模型存在可行域，模型有解，但解无界，趋于无穷，

4、即无最优解但解无界，趋于无穷，即无最优解(无可行解无可行解(无解无解)：LPLP模型不存在可行域，模型不存在可行域，模型无解。模型无解。运筹学 第2讲：图解法及单纯形法基本概念第6页/共16页三、单纯形法的几个基本概念三、单纯形法的几个基本概念 可行解、可行域、最优解、最优值可行解、可行域、最优解、最优值（P11）运筹学 第2讲：图解法及单纯形法基本概念 基基(阵阵)（P14）基向量、基变量、基变矢、非基变量、非基变矢基向量、基变量、基变矢、非基变量、非基变矢（P14）基解、基可行解、可行基基解、基可行解、可行基（P14）第7页/共16页例例6：运筹学 第2讲：图解法及单纯形法基本概念将原模型

5、改为标准型：将原模型改为标准型：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第8页/共16页运筹学 第2讲：图解法及单纯形法基本概念则模型的系数矩阵为则模型的系数矩阵为n=5,m=3,rA=3第9页/共16页运筹学 第2讲：图解法及单纯形法基本概念令令P=(P3,P4,P5)=，rP=3=rA=mP3,P4,P5是三个是三个基向

6、量与与P3,P4,P5相对应的三个变量相对应的三个变量x3,x4,x5是是基变量XB=x3,x4,x5T是是基变矢XN=x1,x2T是是非基变矢得到得到XB=x3,x4,x5T=8,12,36T其也是其也是基可行解此时，此时，z=0P是一个是一个基,(1)令令XN=x1,x2T=0,0T,x1,x2是是非基变量,对应的对应的可行基为为P=(P3,P4,P5),则则为为基解,第10页/共16页运筹学 第2讲：图解法及单纯形法基本概念 P=(P2,P3,P5)=XB=x2,x3,x5T是是基变矢XN=x1,x4T是是非基变矢得到得到XB=x2,x3,x5T=6,8,12T也是也是基可行解此时，此时

7、，z=30P 是一个是一个基(2)令令XN=x1,x4T=0,0T,对应的对应的可行基为为P=(P2,P3,P5),则则为为基解,若用若用P2替换替换P4，则，则P2,P3,P5是三个是三个基向量第11页/共16页运筹学 第2讲：图解法及单纯形法基本概念 P=(P1,P2,P3)=XB=x1,x2,x3T,XN=x4,x5T得到得到XB=x1,x2,x3T=4,6,4T此时，此时，z=42(3)令令XN=x4,x5T=0,0T,若用若用P1替换替换P5，则，则得到基解得到基解第12页/共16页运筹学 第2讲：图解法及单纯形法基本概念 可不断可不断变换可行基变换可行基，并求得相应的基可行解，并求

8、得相应的基可行解（每个基可行解对应于可行域上的一个顶点），（每个基可行解对应于可行域上的一个顶点），直至得到直至得到满足非负条件的最优解满足非负条件的最优解，这就是单纯形，这就是单纯形法的基本思想。法的基本思想。P=(P2,P3,P4)=(4)若用若用P4替换替换P1，则，则 得到得到为基解，但不是基可行解为基解，但不是基可行解此时，此时，z=45，解无效，解无效第13页/共16页四、几个基本定理四、几个基本定理凸集：集合C中任意两点间x1、x2，其连线上的所有点ax1+(1-a)x2(0a1)也是C中的点，则C为凸集定理一：线性规划问题的可行解集为凸集线性规划问题的可行解集为凸集定理二：线性

9、规划问题的基可行解对应于可行域的顶点线性规划问题的基可行解对应于可行域的顶点定理三：线性规划问题如有最优解，则一定在其可行线性规划问题如有最优解，则一定在其可行域的顶点上达到。如果几个顶点都是最优解，则在这域的顶点上达到。如果几个顶点都是最优解，则在这些顶点的每个凸线性组合上也达到最优解些顶点的每个凸线性组合上也达到最优解运筹学 第2讲：图解法及单纯形法基本概念顶点：对任何x1 C，x2 C，不存在x=ax1+(1-a)x2(0a1)，则x为顶点第14页/共16页作业：作业：2.2(1),(4)-2.2(1),(4)-图解法图解法2.4,2.5,2.62.4,2.5,2.6运筹学 第2讲：图解法及单纯形法基本概念第15页/共16页感谢您的观看！第16页/共16页