运筹学单纯形法的例题课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt课件完整,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,ppt课件完整,*,教案要点,文 件 名：051OR11.PPT；第五章.XLS,授课时间：第十一讲,授课内容：LP问题的单纯形法大M法,无解.,预备知识：凸集合，Excel,复习可行解、基可行解，基及非基变量。,难 点：引入人工变量,解的各种情况.,重 点：单纯形法的步骤：引入人工变量,初始表，检验数，判优，进基、比值、出基、迭代，无解、无穷界的情况表上操作；利用Excel。,下节预习：教材第六章2 对偶理论。,11/16/2024,1,ppt课件完整,教案要点文 件 名：051OR11.PPT；第五章.XLS1,运筹学单纯形法,11/16/2024,2,ppt课件完整,运筹学单纯形法10/1/20232ppt课件完整,练习用,图解法,和,单纯形法,求如下线性规划问题的最优解：Max z=4 x,1,+x,2,x,1,+3x,2,7 s.t.4x,1,+2x,2,9 x,1,x,2,0,x,1,+3x,2,=7经过点(_,0)与(1,_),7,2,4x,1,+2x,2,=9经过点(2,_)与(0,_),0.5,4.5,可行域在x,1,+3x,2,=7与4x,1,+2x,2,=9之_,下,11/16/2024,3,ppt课件完整,练习用图解法和单纯形法求如下线性规划问题的最优解：,练习用图解法,0,1,2,3,4,5,6,7,1,2,3,4,5,(2.25,0),4x,1,+x,2,=9,11/16/2024,4,ppt课件完整,练习用图解法,练习.单纯形表,填入第一个约束的数据.,1,3,1,0,7,填入第二个约束的数据.,4,2,0,1,9,11/16/2024,5,ppt课件完整,练习.单纯形表填入第一个约束的数据.13107填入第二个,练习.单纯形表,1,3,1,0,7,4,2,0,1,9,基?,填目标函数系数,填基变量列,填C,B,列,计算Z,j,计算检验数,j,4 1 0 0,x3,x4,0,0,0 0 0 0,0,4 1 0 0,11/16/2024,6,ppt课件完整,练习.单纯形表1310742019基?填目标函数系数,填,练习.单纯形表,1,3,1,0,7,4,2,0,1,9,4 1 0 0,x3,x4,0,0,0 0 0 0,0,4 1 0 0,最优吗？,查什么？,不是！,谁进基？,检验数最大的x,1,进基,谁出基？,x1的系数有正的吗？,求比值？,7,9/4,9/4,4,11/16/2024,7,ppt课件完整,练习.单纯形表13107420194 1,1,3,1,0,7,4,2,0,1,9,4 1 0 0,x3,x4,0,0,0 0 0 0,0,4,1 0 0,9/4,7,练习.单纯形表,基变量列中_换为_,x,4,x,1,改C,B,列,_换为_.,0,4,Excel,11/16/2024,8,ppt课件完整,13107420194 1 0 0 x,练习用单纯形法,x,3,x,4,4,1,0,0,0,0,1 3 1 0 7,4 2 0 1 9,迭代次数,基,变量,C,B,x,1,x,2,x,3,x,4,b,i,比,迭代次数,基,变量,C,B,x,1,x,2,x,3,x,4,b,i,比,0,z,j,j,=C,j,-,z,j,1,z,j,j,=C,j,-,z,j,0 0 0 0 0,4 1 0 0,7,9/4,4 1 0 0,x,3,x,1,0,4,1 0.5 0 0.25 2.25,0 2.5 1 -0.25 4.75,4 2 0 1 9,0 -1 0 -1,11/16/2024,9,ppt课件完整,练习用单纯形法x3x44100001 3,练习用图解法和,单纯形法,求如下线性规划问题的最优解：Max z=4 x,1,+x,2,x,1,+3x,2,7 s.t.4x,1,+2x,2,9 x,1,x,2,0,可行域在直线 x,1,+3x,2,=7之_,下,可行域在直线4x,1,+2x,2,=9之_,上,11/16/2024,10,ppt课件完整,练习用图解法和单纯形法求如下线性规划问题的最优解：,练习用图解法,0,1,2,3,4,5,6,7,1,2,3,4,5,(7,0),4x,1,+x,2,=28,最优解是x,1,=7,x,2,=0,此时Max z=28,11/16/2024,11,ppt课件完整,练习用图解法,练习.用单纯形法,标准化为:,Max z=4 x,1,+x,2,+0 x,3,+0 x,4,x,1,+3x,2,+x,3,=7 s.t.4x,1,+2x,2,-x,4,=9 x,1,x,2,x,3,x,4,0,基是谁?,这个“-”如何处理?,再引进一个“人工变量”x,5,+x,5,-Mx,5,M是一个大的正数,(大M法),x,5,11/16/2024,12,ppt课件完整,练习.用单纯形法标准化为:基是谁?这个“-”如何处理?再引,练习.用单纯形法,Max z=4x,1,+x,2,+0 x,3,+0 x,4,-Mx,5,x,1,+3x,2,+x,3,=7 s.t.4x,1,+2x,2,-x,4,+x,5,=9 x,1,x,2,x,3,x,4,x,5,0,基是谁?,x,3,x,5,x,5,的检验数为0,请它出基,逼它取值为0.,11/16/2024,13,ppt课件完整,练习.用单纯形法Max z=4x1+x2+0 x3+0 x,练习.单纯形表,两行，几列?,少一列?,填入第一个约束的数据.,11/16/2024,14,ppt课件完整,练习.单纯形表两行，几列?少一列?填入第一个约束的数据.,练习,.单纯形表,填入第二个约束的数据.,基?,填目标函数系数,填基变量列,填C,B,列,计算Z,j,计算检验数,j,11/16/2024,15,ppt课件完整,练习.单纯形表填入第二个约束的数据.基?填目标函数系数,练习,.单纯形表,最优吗？,查什么？,不是！,谁进基?,检验数最大的x,1,进基,谁出基?,x1的系数有正的吗?,求比值?,7,9/4,11/16/2024,16,ppt课件完整,练习.单纯形表最优吗？查什么？不是！谁进基?检验数最大的,练习.单纯形表：迭代,基变量列中_换为_,x,5,x,1,改C,B,列,_换为_.,-M,4,Excel,11/16/2024,17,ppt课件完整,练习.单纯形表：迭代基变量列中_换为_,x5x1,练习用图解法和,单纯形法,求如下线性规划问题的最优解：Max z=4 x,1,+x,2,x,1,+3x,2,7 s.t.4x,1,+2x,2,9 x,1,x,2,0,可行域在直线 x,1,+3x,2,=7之_,上,可行域在直线4x,1,+2x,2,=9之_,上,11/16/2024,18,ppt课件完整,练习用图解法和单纯形法求如下线性规划问题的最优解：,练习用图解法,0,1,2,3,4,5,6,7,1,2,3,4,5,有可行解,但无有限的最优解,z+.,11/16/2024,19,ppt课件完整,练习用图解法,练习.用单纯形法,标准化为:,Max z=4x,1,+x,2,+0 x,3,+0 x,4,x,1,+3x,2,-x,3,=7 s.t.4x,1,+2x,2,-x,4,=9 x,1,x,2,x,3,x,4,0,基是谁?,这里“-”如何处理?,引进两个“人工变量”x,5,x,6,+x,5,-Mx,5,-Mx,6,M是一个大的正数,(大M法),x,5,x,6,+x,6,11/16/2024,20,ppt课件完整,练习.用单纯形法标准化为:基是谁?这里“-”如何处理?引进,练习.用单纯形法,Max z=,4x,1,+x,2,+0 x,3,+0 x,4,-Mx,5,Mx,6,x,1,+3x,2,-x,3,+x,5,=7 s.t.4x,1,+2x,2,-x,4,+x,6,=9 x,1,x,2,x,3,x,4,x,5,x,6,0,基是谁?,x,5,x,6,它们的检验数为0,请它们出基,逼它们取值为0.,Excel,不能全出基,就无可行解.,11/16/2024,21,ppt课件完整,练习.用单纯形法Max z=4x1+x2+0 x3+0 x4,解LP问题单纯形法,LP问题解的几种可能：,唯一解,无穷多解,有解,无解,无有限最优解,无可行解,11/16/2024,22,ppt课件完整,解LP问题单纯形法LP问题解的几种可能：唯一解有解无解无有限,解LP问题单纯形法,LP问题解的几种可能：,无需引入人工变量.一定有可行解,从而一定有基可行解,但还有可能有无穷最优解或无有限最优解.,Axb,s.t.,x0,11/16/2024,23,ppt课件完整,解LP问题单纯形法LP问题解的几种可能：无需引入人工变量.一,解LP问题单纯形法,LP问题解的几种可能：,一般要引入人工变量.,人工变量不能全出基则无可行解,更无最优解.,不需人工变量或人工变量可以全部出基则必有可行解.分:,至少有一个非基变量的检验数为正,但它的系数全为非正,则无有限最优解；,所有非基变量的检验数全为非正，已有最优解，但若其中至少有一个的检验数为0，且它的系数中有正的，则可能有无穷多个最优解。,11/16/2024,24,ppt课件完整,解LP问题单纯形法LP问题解的几种可能：一般要引入人工变量.,作业,第五章(P.99-100)：,7a,b,c,d,预习第六章2,线性规划的对偶问题,11/16/2024,25,ppt课件完整,作业第五章(P.99-100)：预习第六章210/1/20,练习,一个LP问题的单纯形表如上：,1、试补齐中间的空格；,2、u取什么值时此问题,有无穷多最优解,？,0,6,0,6,1,0,0,6,0,6u,5-6u,0,0,0,0,3,-3,0,0,150,必须为_,0,u=5/6,11/16/2024,26,ppt课件完整,练习一个LP问题的单纯形表如上：0606100606u5-6,感谢亲观看此幻灯片，此课件部分内容来源于网络，,如有侵权请及时联系我们删除，谢谢配合！,感谢亲观看此幻灯片，此课件部分内容来源于网络，,