运筹学第3讲：采用单纯形法求解LP模型

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第3讲：采用单纯形法求解LP模型,1,判断,：,运筹学 第3讲：采用单纯形法求解LP模型,若,LP,问题存在可行域，则必然存在最优解,若,LP,问题不存在可行域，则必然不存在最优解,LP,问题的每一个基解对应可行域上的一个顶点,若,LP,问题存在最优解，一定存在一个基可行解是最优解,若,LP,问题存在最优解，则必然是其可行域上的某个顶点,为使系数矩阵,A,满秩，一个较好的方法是构建一个单位子矩 阵，并将其作为初始可行基,在,LP,模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大,2,一、单纯形法求解步骤,确定初始基可行解,对其进行,最优性检验,，是，则为最优解；否， 转步骤,(3),转换可行基,，得到相邻的基可行解，转步骤,(2),运筹学 第3讲：采用单纯形法求解LP模型,3,例1,(习题2-1),、,某预制厂生产两种构件，每个构件制造时间大概为一个月(占时)。甲构件每件占地10m,2,，需要劳动力150个；乙构件每件占地2m,2,，需要劳动力25个。该厂共有生产用地720m,2,，每月劳动力10000个。并且受到其他设备限制，每月最多能生产甲构件50件，乙构件200件。若每个甲构件能创造价值250百元，每个乙构件能创造价值50百元，要想使创造的价值最多，每月应生产构件甲、乙各多少件？,运筹学 第3讲：采用单纯形法求解LP模型,4,采用单纯形法求解LP模型,(说明),：,在以上步骤中，第,3,步说明了基可行解何时为最优 解；第,3,、,4,步解释了基向量的替换过程,系数矩阵中，基变矢对应的基为单位基,基变量,x,j,对应的检验数,j,0,采用单纯形法，每次迭代都将使,Z,得到最快的增长,运筹学 第3讲：采用单纯形法求解LP模型,5,max,z,= 250,x,1,+50,x,2,s.t. 10,x,1,+ 2,x,2, 720,150,x,1,+ 25,x,2, 10000,x,1, 50,x,2, 200,x,1,0 ，,x,2,0,x,1,x,2,200,50,100,150,50,100,10,x,1,+ 2,x,2,= 720,150,x,1,+ 25,x,2,=10000,x,1,= 50,x,2,= 200,O,A,B,C,D,E,不难得到，最优解为,C,点,采用单纯形法求解，得到的基可行解依次为：,O,，,E,，,D,，,C,； 而不是：,O,，,A,，,B,，,C,。,Why?,运筹学 第3讲：采用单纯形法求解LP模型,6,max,z,= 2,x,1,+,x,2,s.t. 5,x,2, 15,6,x,1,+ 2,x,2, 24,x,1,+,x,2, 5,x,1,x,2, 0,例2,：,运筹学 第3讲：采用单纯形法求解LP模型,7,max,z,= 2,x,1,+,x,2,s.t.,x,1,+,x,2, 5，2,x,1,+,x,2, 8,5,x,2, 15，,x,1,x,2, 0,x,1,x,2,6,6,1,1,3,3,x,1,+,x,2,=5,2,x,1,+,x,2,=8,5,x,2,=15,可行域,A,B,C,D,O,z,= 2,x,1,+,x,2,运筹学 第3讲：采用单纯形法求解LP模型,采用单纯形法求解，得到的基可行解依次为：O，D，C； 而不是：O，A，B，C。,作业：2.2(1-3),8,