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

2020/5/31,运筹学单纯形法,1,教案要点,文件名：051OR11.PPT；第五章.XLS授课时间：第十一讲授课内容：LP问题的单纯形法大M法,无解.预备知识：凸集合，Excel复习可行解、基可行解，基及非基变量。难点：引入人工变量,解的各种情况.重点：单纯形法的步骤：引入人工变量,初始表，检验数，判优，进基、比值、出基、迭代，无解、无穷界的情况表上操作；利用Excel。下节预习：教材第六章2对偶理论。,2020/5/31,运筹学单纯形法,2,运筹学单纯形法,2020/5/31,运筹学单纯形法,3,练习用图解法和单纯形法求如下线性规划问题的最优解：Maxz=4x1+x2x1+3x27s.t.4x1+2x29x1,x20,x1+3x2=7经过点(_,0)与(1,_),7,2,4x1+2x2=9经过点(2,_)与(0,_),0.5,4.5,可行域在x1+3x2=7与4x1+2x2=9之_,下,2020/5/31,运筹学单纯形法,4,练习用图解法,0,1,2,3,4,5,6,7,1,2,3,4,5,(2.25,0),4x1+x2=9,2020/5/31,运筹学单纯形法,5,练习.单纯形表,填入第一个约束的数据.,1,3,1,0,7,填入第二个约束的数据.,4,2,0,1,9,2020/5/31,运筹学单纯形法,6,练习.单纯形表,基?,填目标函数系数,填基变量列,填CB列,计算Zj,计算检验数j,4100,x3x4,00,00000,4100,2020/5/31,运筹学单纯形法,7,练习.单纯形表,最优吗？,查什么？,不是！,谁进基？,检验数最大的x1进基,谁出基？,x1的系数有正的吗？,求比值？,7,9/4,9/4,4,2020/5/31,运筹学单纯形法,8,练习.单纯形表,基变量列中_换为_,x4,x1,改CB列,_换为_.,0,4,Excel,2020/5/31,运筹学单纯形法,9,练习用单纯形法,x3,x4,4,1,0,0,0,0,13107,42019,00000,4100,7,9/4,4100,x3,x1,0,4,10.500.252.25,02.51-0.254.75,42019,0-10-1,2020/5/31,运筹学单纯形法,10,练习用图解法和单纯形法求如下线性规划问题的最优解：Maxz=4x1+x2x1+3x27s.t.4x1+2x29x1,x20,可行域在直线x1+3x2=7之_,下,可行域在直线4x1+2x2=9之_,上,2020/5/31,运筹学单纯形法,11,练习用图解法,0,1,2,3,4,5,6,7,1,2,3,4,5,(7,0),4x1+x2=28,最优解是x1=7,x2=0,此时Maxz=28,2020/5/31,运筹学单纯形法,12,练习.用单纯形法,基是谁?,这个“-”如何处理?,再引进一个“人工变量”x5,+x5,-Mx5,M是一个大的正数,(大M法),x5,2020/5/31,运筹学单纯形法,13,练习.用单纯形法,Maxz=4x1+x2+0 x3+0 x4-Mx5x1+3x2+x3=7s.t.4x1+2x2-x4+x5=9x1,x2,x3,x4,x50,基是谁?,x3,x5,x5的检验数为0,请它出基,逼它取值为0.,2020/5/31,运筹学单纯形法,14,练习.单纯形表,两行，几列?,少一列?,填入第一个约束的数据.,2020/5/31,运筹学单纯形法,15,练习.单纯形表,填入第二个约束的数据.,基?,填目标函数系数,填基变量列,填CB列,计算Zj,计算检验数j,2020/5/31,运筹学单纯形法,16,练习.单纯形表,最优吗？,查什么？,不是！,谁进基?,检验数最大的x1进基,谁出基?,x1的系数有正的吗?,求比值?,7,9/4,2020/5/31,运筹学单纯形法,17,练习.单纯形表：迭代,基变量列中_换为_,x5,x1,改CB列,_换为_.,-M,4,Excel,2020/5/31,运筹学单纯形法,18,练习用图解法和单纯形法求如下线性规划问题的最优解：Maxz=4x1+x2x1+3x27s.t.4x1+2x29x1,x20,可行域在直线x1+3x2=7之_,上,可行域在直线4x1+2x2=9之_,上,2020/5/31,运筹学单纯形法,19,练习用图解法,0,1,2,3,4,5,6,7,1,2,3,4,5,有可行解,但无有限的最优解,z+.,2020/5/31,运筹学单纯形法,20,练习.用单纯形法,基是谁?,这里“-”如何处理?,引进两个“人工变量”x5,x6,+x5,-Mx5-Mx6,M是一个大的正数,(大M法),x5,x6,+x6,2020/5/31,运筹学单纯形法,21,练习.用单纯形法,Maxz=4x1+x2+0 x3+0 x4-Mx5Mx6x1+3x2-x3+x5=7s.t.4x1+2x2-x4+x6=9x1,x2,x3,x4,x5,x60,基是谁?,x5,x6,它们的检验数为0,请它们出基,逼它们取值为0.,Excel,不能全出基,就无可行解.,2020/5/31,运筹学单纯形法,22,解LP问题单纯形法,LP问题解的几种可能：,唯一解无穷多解,有解,无解,无有限最优解无可行解,2020/5/31,运筹学单纯形法,23,解LP问题单纯形法,LP问题解的几种可能：,无需引入人工变量.一定有可行解,从而一定有基可行解,但还有可能有无穷最优解或无有限最优解.,2020/5/31,运筹学单纯形法,24,解LP问题单纯形法,LP问题解的几种可能：,一般要引入人工变量.,人工变量不能全出基则无可行解,更无最优解.,不需人工变量或人工变量可以全部出基则必有可行解.分:至少有一个非基变量的检验数为正,但它的系数全为非正,则无有限最优解；所有非基变量的检验数全为非正，已有最优解，但若其中至少有一个的检验数为0，且它的系数中有正的，则可能有无穷多个最优解。,2020/5/31,运筹学单纯形法,25,作业,第五章(P.99-100)：7a,b,c,d,预习第六章2线性规划的对偶