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