《运筹学第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 。x1x2600600100100300300x1 =1252 x1+ x2 = 600x1+ x2 =350解解线性方程性方程组 x1+ x2 =350 2 x1+ x2 = 600得最得最优解解 x1 = 250 x2 = 100最最优值 z= 800可行域
3、可行域例例2 2：Z=2x1+3x2独一最优解运筹学 第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
4、 = x1 + x2可行域伸展到无可行域伸展到无穷，那么那么z z也可增大到无也可增大到无穷，即最即最优解无界解无界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讲：图解法及单纯形法根本概念缘由是由是约束条
5、件之束条件之间有矛盾有矛盾( 无界解：无界解：LPLP模型存在可行域，模型有解，模型存在可行域，模型有解，但解无界，趋于无穷，即无最优解但解无界，趋于无穷，即无最优解( 无可行解无可行解( (无解无解) )：LPLP模型不存在可行域，模型不存在可行域，模型无解。模型无解。运筹学 第2讲：图解法及单纯形法根本概念三、三、单纯形法的几个根本概念形法的几个根本概念 可行解、可行域、最优解、最优值可行解、可行域、最优解、最优值 P11运筹学 第2讲：图解法及单纯形法根本概念 基基(阵阵)P14 基向量、基变量、基变矢、非基变量、非基变矢基向量、基变量、基变矢、非基变量、非基变矢P14 基解、基可行解、
6、可行基基解、基可行解、可行基 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 + 0x3 + 0x4 + 0x5s.t. x1 + x3 = 8 2x2 + x4 = 12 3x1 + 4x2 + x5 = 36 xj 0， j=1,2,5运筹学 第2讲：图解法及单纯形法根本概念那么模型的系数矩阵那么模型的系数矩阵为为n=5, m=3, rA=3运筹学
7、第2讲：图解法及单纯形法根本概念令令P = (P3, P4, P5) = ，rP=3= rA=mP3, P4, P5是三个基向量是三个基向量与与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) ,那么那
8、么为基解为基解,运筹学 第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,对应的可行基的可行基为P = (P2, P3, P5) ,那么那么为基解为基解,假设用假设用P2交换交换P4，那，那么么P2, P3, P5是三个基向量是三个基向量运筹学 第2讲：图解法及单纯形法根本概念 P = (P1, P2, P3)
9、 = 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讲：图解法及单纯形法根本概念 可不断变换可行基，并求得相应的基可行可不断变换可行基，并求得相应的基可行解每个基可行解对应于可行域上的一个解每个基可行解对应于可行域上的一个顶点，直至得到满足非负条件的最优解，顶点，直至得到满足非负条件的最优解，这就是单纯形法的根本思想。这就是单纯形法的根本思想。 P= (P2, P3, P4) = (4)
10、 假设用假设用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讲：图解法及单纯形法根本概念
