《《单纯行法例题解析》PPT课件.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经过点(
2、_,0)与(1,_),7,2,4x1+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,x3 x4,0 0,0 0 0 0 0,4 1 0 0,练习. 单纯形表,最优吗？,查什么？,不是！,谁进基？,检验数最大的x1进基,谁出基？
3、,x1的系数有正的吗？,求比值？,7,9/4,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
4、,可行域在直线 x1+3x2=7之_,下,可行域在直线4x1+2x2=9之_,上,练习用图解法,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的检
5、验数为0,请它出基,逼它取值为0.,练习. 单纯形表,两行，几列?,少一列?,填入第一个约束的数据.,练习. 单纯形表,填入第二个约束的数据.,基?,填目标函数系数,填基变量列,填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
6、 0,可行域在直线 x1+3x2=7之_,上,可行域在直线4x1+2x2=9之_,上,练习用图解法,0,1,2,3,4,5,6,7,1,2,3,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,请
7、它们出基,逼它们取值为0.,Excel,不能全出基,就无可行解.,解LP问题单纯形法,LP问题解的几种可能：,唯一解 无穷多解,有解,无解,无有限最优解 无可行解,解LP问题单纯形法,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,