运筹学单纯形法的例题.ppt

运筹学单纯形法5/12/20242.练习用图解法和单纯形法求如下线性规划问题的最优解：Maxz=4x1+x2x1+3x27s.t.4x1+2x29x1,x20 x1+3x2=7经过点(_,0)与(1,_)724x1+2x2=9经过点(2,_)与(0,_)0.54.5可行域在x1+3x2=7与4x1+2x2=9之_下下5/12/20243.练习用图解法练习用图解法0123456712345(2.25,0)4x1+x2=95/12/20244.练习练习.单纯形表单纯形表填入第一个约束的数据.13107填入第二个约束的数据.420195/12/20245.练习练习.单纯形表单纯形表1310742019基基?填目标函数系数,填基变量列填基变量列,填CB列,计算计算Zj,计算检验数j,4 1 0 0 x3x400000004 1 0 05/12/20246.练习练习.单纯形表单纯形表13107420194 1 0 0 x3x400000004 1 0 0最优吗？查什么？不是！谁进基？检验数最大的x1进基,谁出基？x1的系数有正的吗？求比值？79/49/445/12/20247.13107420194 1 0 0 x3x400000004 1 0 09/47练习练习.单纯形表单纯形表基变量列中_换为_,x4x1改CB列,_换为_.04Excel5/12/20248.练习用单纯形法练习用单纯形法x3x44100001 3 1 0 74 2 0 1 9迭代次数基变量CBx1x2x3x4bi比迭代次数基变量CBx1x2x3x4bi比0zjj=Cj-zj1zjj=Cj-zj0 0 0 0 04 1 0 079/44 1 0 0 x3x1041 0.5 0 0.25 2.250 2.5 1 -0.25 4.754 2 0 1 90 -1 0 -15/12/20249.练习用图解法和单纯形法求如下线性规划问题的最优解：Maxz=4x1+x2x1+3x27s.t.4x1+2x29x1,x20可行域在直线x1+3x2=7之_下下可行域在直线4x1+2x2=9之_上上5/12/202410.练习用图解法练习用图解法0123456712345(7,0)4x1+x2=28最优解是x1=7,x2=0,此时Maxz=285/12/202411.练习练习.用单纯形法用单纯形法标准化为:Maxz=4x1+x2+0 x3+0 x4x1+3x2+x3=7s.t.4x1+2x2-x4=9x1,x2,x3,x40基是谁?这个“-”如何处理?再引进一个“人工变量”x5+x5-Mx5M是一个大的正数(大大M法法),x55/12/202412.练习练习.用单纯形法用单纯形法Maxz=4x1+x2+0 x3+0 x4-Mx5x1+3x2+x3=7s.t.4x1+2x2-x4+x5=9x1,x2,x3,x4,x50基是谁?x3,x5x5的检验数为0请它出基,逼它取值为0.5/12/202413.练习练习.单纯形表单纯形表两行，几列?少一列?填入第一个约束的数据.5/12/202414.练习练习.单纯形表单纯形表填入第二个约束的数据.基基?填目标函数系数,填基变量列填基变量列,填CB列,计算计算Zj,计算检验数j,5/12/202415.练习练习.单纯形表单纯形表最优吗？查什么？不是！谁进基?检验数最大的x1进基,谁出基?x1的系数有正的吗?求比值?79/45/12/202416.练习练习.单纯形表：迭代单纯形表：迭代基变量列中_换为_,x5x1改CB列,_换为_.-M4Excel5/12/202417.练习用图解法和单纯形法求如下线性规划问题的最优解：Maxz=4x1+x2x1+3x27s.t.4x1+2x29x1,x20可行域在直线x1+3x2=7之_上上可行域在直线4x1+2x2=9之_上上5/12/202418.练习用图解法练习用图解法0123456712345有可行解,但无有限的最优解,z+.5/12/202419.练习练习.用单纯形法用单纯形法标准化为:Maxz=4x1+x2+0 x3+0 x4x1+3x2-x3=7s.t.4x1+2x2-x4=9x1,x2,x3,x40基是谁?这里“-”如何处理?引进两个“人工变量”x5,x6+x5-Mx5-Mx6M是一个大的正数(大M法),x5,x6+x65/12/202420.练习练习.用单纯形法用单纯形法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不能全出基,就无可行解.5/12/202421.解解LPLP问题单纯形法问题单纯形法vLP问题解的几种可能：问题解的几种可能：唯一解唯一解无穷多解无穷多解有解有解无解无解无有限最优解无有限最优解无可行解无可行解5/12/202422.解解LPLP问题单纯形法问题单纯形法vLP问题解的几种可能：问题解的几种可能：v无需引入人工变量无需引入人工变量.一定有可行一定有可行解解,从而一定有基可行解从而一定有基可行解,但还但还有可能有无穷最优解或无有限有可能有无穷最优解或无有限最优解最优解.Axb s.t.x05/12/202423.解解LPLP问题单纯形法问题单纯形法vLP问题解的几种可能：问题解的几种可能：v一般要引入人工变量一般要引入人工变量.v人工变量不能全出基则无可行解人工变量不能全出基则无可行解,更更无最优解无最优解.v不需人工变量或人工变量可以全部出不需人工变量或人工变量可以全部出基则必有可行解基则必有可行解.分分:v至少有一个非基变量的检验数为正至少有一个非基变量的检验数为正,但它的系但它的系数全为非正数全为非正,则无有限最优解；则无有限最优解；v所有非基变量的检验数全为非正，已有最优解，所有非基变量的检验数全为非正，已有最优解，但若其中至少有一个的检验数为但若其中至少有一个的检验数为0 0，且它的系数，且它的系数中有正的，则可能有无穷多个最优解。中有正的，则可能有无穷多个最优解。5/12/202424.作业作业v第五章第五章(P.99-100)：7a,b,c,dv预习第六章预习第六章2 线性规划的对偶问题线性规划的对偶问题5/12/202425.练习一个一个LP问题的单纯形表如上：问题的单纯形表如上：1、试补齐中间的空格；、试补齐中间的空格；2、u取什么值时此问题取什么值时此问题有无穷多最优解有无穷多最优解？0606100606u5-6u00003-300150必须为必须为_0u=5/65/12/202426.