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

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

1、第第2 2讲：图解法及单纯形法讲：图解法及单纯形法基本概念基本概念浙江工业大学经贸管理学院浙江工业大学经贸管理学院 曹柬曹柬一、图解法：一、图解法：确定直角平面坐标系，图示非负约束条件确定直角平面坐标系，图示非负约束条件 图示约束条件，找出可行域图示约束条件，找出可行域 图示目标函数，确定最优解图示目标函数，确定最优解max z=2 x1+x2 s.t.x1+x2 5 6 x1+2x2 24 5x2 15 x1,x2 0例例1 1：运筹学 第2讲：图解法及单纯形法基本概念图解法仅适于两个变量的图解法仅适于两个变量的LPLP模型模型从图解法中可以看出从图解法中可以看出LPLP模型的解的情况模型的

2、解的情况二、二、LP模型解的几种情况模型解的几种情况一、惟一最优解一、惟一最优解二、二、无穷多最优解无穷多最优解三、无界解三、无界解四、无可行解四、无可行解运筹学 第2讲：图解法及单纯形法基本概念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惟

3、一最优解运筹学 第2讲：图解法及单纯形法基本概念Amax 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讲：图解法及单纯形法基本概念max z =x1+x2 s.t.-2x1+x2 2，x1-3x2 3 x1,x2 0无界解x1x2661133-2x1+x2=2z=x1+x2可行域伸展到无穷，可行域伸展到无穷，则则z z也可增大到无穷，也可增大到无穷，即最优解无界

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

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

6、x 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讲：图解法及单纯形法基本概念令令P=(P3,P4,P5)=，rP=3=rA=mP3,P4,P5是三个是三个基向量与与P3,P4,P5相对应的三个变量相对应的三个变量x3,x4,x

7、5是是基变量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),则则为为基解,运筹学 第2讲：图解法及单纯形法基本概念 P=(P2,P3,P5)=XB=x2,x3,x5T是是基变矢XN=x1,x4T是是非基变矢得到得到XB=x2,x3,x5T=6,8,12T也是也是基可行解此时，此时，z=30P 是一个是一个基(2)令令XN=x1,x4T=0,0T,对应的对应的可行基

8、为为P=(P2,P3,P5),则则为为基解,若用若用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)令令XN=x4,x5T=0,0T,若用若用P1替换替换P5，则，则得到基解得到基解运筹学 第2讲：图解法及单纯形法基本概念 可不断可不断变换可行基变换可行基，并求得相应的基可行解，并求得相应的基可行解（每个基可行解对应于可行域上的一个顶点），（每个基可行解对应于可行域上的一个顶点），直至得到直至得到满足非

9、负条件的最优解满足非负条件的最优解，这就是单纯形，这就是单纯形法的基本思想。法的基本思想。P=(P2,P3,P4)=(4)若用若用P4替换替换P1，则，则 得到得到为基解，但不是基可行解为基解，但不是基可行解此时，此时，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.2(1),(4)-图解法图解法2.4,2.5,2.62.4,2.5,2.6运筹学 第2讲：图解法及单纯形法基本概念