单纯行法例题解析.ppt

《单纯行法例题解析.ppt》由会员分享，可在线阅读，更多相关《单纯行法例题解析.ppt（26页珍藏版）》请在三一办公上搜索。

1、教案要点,文 件 名：051OR11.PPT；第五章.XLS授课时间：第十一讲授课内容：LP问题的单纯形法大M法,无解.预备知识：凸集合，Excel复习可行解、基可行解，基及非基变量。难 点：引入人工变量,解的各种情况.重 点：单纯形法的步骤：引入人工变量,初始表，检验数，判优，进基、比值、出基、迭代，无解、无穷界的情况表上操作；利用Excel。下节预习：教材第六章2 对偶理论。,运筹学单纯形法,练习用图解法和单纯形法求如下线性规划问题的最优解：Max z=4 x1+x2 x1+3x2 7 s.t.4x1+2x2 9 x1,x2 0,x1+3x2=7经过点(_,0)与(1,_),7,2,4x1

2、+2x2=9经过点(2,_)与(0,_),0.5,4.5,可行域在x1+3x2=7与4x1+2x2=9之_,下,练习用图解法,0,1,2,3,4,5,6,7,1,2,3,4,5,(2.25,0),4x1+x2=9,练习.单纯形表,填入第一个约束的数据.,1,3,1,0,7,填入第二个约束的数据.,4,2,0,1,9,练习.单纯形表,基?,填目标函数系数,填基变量列,填CB列,计算Zj,计算检验数j,4 1 0 0,x3x4,00,0 0 0 0 0,4 1 0 0,练习.单纯形表,最优吗？,查什么？,不是！,谁进基？,检验数最大的x1进基,谁出基？,x1的系数有正的吗？,求比值？,7,9/4,

3、9/4,4,练习.单纯形表,基变量列中_换为_,x4,x1,改CB列,_换为_.,0,4,Excel,练习用单纯形法,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,练习用图解法和单纯形法求如下线性规划问题的最优解：Max z=4 x1+x2 x1+3x2 7 s.t.4x1+2x2 9 x1,x2 0,可行域在直线 x1+3x2=7之_,下,可行域在直线4x1+2x2=9之_

4、,上,练习用图解法,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,练习.用单纯形法,基是谁?,这个“-”如何处理?,再引进一个“人工变量”x5,+x5,-Mx5,M是一个大的正数,(大M法),x5,练习.用单纯形法,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.,练习.单纯形表,两行，几列?,少一列?,填入第一个约束的数据.,练习.单纯形表

5、,填入第二个约束的数据.,基?,填目标函数系数,填基变量列,填CB列,计算Zj,计算检验数j,练习.单纯形表,最优吗？,查什么？,不是！,谁进基?,检验数最大的x1进基,谁出基?,x1的系数有正的吗?,求比值?,7,9/4,练习.单纯形表：迭代,基变量列中_换为_,x5,x1,改CB列,_换为_.,-M,4,Excel,练习用图解法和单纯形法求如下线性规划问题的最优解：Max z=4 x1+x2 x1+3x2 7 s.t.4x1+2x2 9 x1,x2 0,可行域在直线 x1+3x2=7之_,上,可行域在直线4x1+2x2=9之_,上,练习用图解法,0,1,2,3,4,5,6,7,1,2,3,

6、4,5,有可行解,但无有限的最优解,z+.,练习.用单纯形法,基是谁?,这里“-”如何处理?,引进两个“人工变量”x5,x6,+x5,-Mx5-Mx6,M是一个大的正数,(大M法),x5,x6,+x6,练习.用单纯形法,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,不能全出基,就无可行解.,解LP问题单纯形法,LP问题解的几种可能：,唯一解无穷多解,有解,无解,无有限最优解无可行解,解LP

7、问题单纯形法,LP问题解的几种可能：,无需引入人工变量.一定有可行解,从而一定有基可行解,但还有可能有无穷最优解或无有限最优解.,解LP问题单纯形法,LP问题解的几种可能：,一般要引入人工变量.,人工变量不能全出基则无可行解,更无最优解.,不需人工变量或人工变量可以全部出基则必有可行解.分:至少有一个非基变量的检验数为正,但它的系数全为非正,则无有限最优解；所有非基变量的检验数全为非正，已有最优解，但若其中至少有一个的检验数为0，且它的系数中有正的，则可能有无穷多个最优解。,作业,第五章(P.99-100)：7a,b,c,d,预习第六章2 线性规划的对偶问题,练习,一个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,