《单纯行法例题解析PPT课件》由会员分享，可在线阅读，更多相关《单纯行法例题解析PPT课件（26页珍藏版）》请在金锄头文库上搜索。
1、运筹学单纯形法练习用图解法和单纯形法求如下线性规划问题的最优解：Maxz=4x1+x2x1+3x27s.t.4x1+2x29x1,x20x1+3x2=7经过点(_,0)与(1,_)724x1+2x2=9经过点(2,_)与(0,_)0.54.5可行域在x1+3x2=7与4x1+2x2=9之_下下练习用图解法练习用图解法0123456712345(2.25,0)4x1+x2=9练习练习. . 单纯形表单纯形表填入第一个约束的数据.13107填入第二个约束的数据.42019练习练习. . 单纯形表单纯形表1310742019基基?填目标函数系数,填基变量列填基变量列,填CB列, 计算计算Zj,计算检
2、验数j,4 1 0 0x3x400000004 1 0 0练习练习. . 单纯形表单纯形表13107420194 1 0 0x3x400000004 1 0 0最优吗？查什么？ 不是！谁进基？检验数最大的x1进基,谁出基？x1的系数有正的吗？求比值？79/49/4413107420194 1 0 0x3x400000004 1 0 09/47练习练习. . 单纯形表单纯形表基变量列中_换为_,x4x1改CB列,_换为_.04Excel练习用单纯形法练习用单纯形法x3x44100001 3 1 0 74 2 0 1 9迭代次数基变量CBx1x2x3x4bi比迭代次数基变量CBx1x2x3x4bi
3、比0zjj=Cj- zj1zjj=Cj- zj0 0 0 0 04 1 0 079/44 1 0 0x3x1041 0.5 0 0.25 2.250 2.5 1 -0.25 4.754 2 0 1 90 -1 0 -1练习用图解法和单纯形法求如下线性规划问题的最优解：Maxz=4x1+x2x1+3x27s.t.4x1+2x29x1,x20可行域在直线x1+3x2=7之_下下可行域在直线4x1+2x2=9之_上上练习用图解法练习用图解法0123456712345(7,0)4x1+x2=28最优解是x1=7,x2=0,此时Maxz=28练习练习. .用单纯形法用单纯形法标准化为:Maxz=4x1+
4、x2+0x3+0x4x1+3x2+x3=7s.t.4x1+2x2-x4=9x1,x2,x3,x40基是谁?这个“-”如何处理?再引进一个“人工变量”x5+x5-Mx5M是一个大的正数(大大M法法),x5练习练习. .用单纯形法用单纯形法Maxz=4x1+x2+0x3+0x4-Mx5x1+3x2+x3=7s.t.4x1+2x2-x4+x5=9x1,x2,x3,x4,x50基是谁?x3,x5x5的检验数为0请它出基,逼它取值为0.练习练习. . 单纯形表单纯形表两行，几列? 少一列?填入第一个约束的数据.练习练习. . 单纯形表单纯形表填入第二个约束的数据.基基?填目标函数系数,填基变量列填基变量
5、列,填CB列, 计算计算Zj,计算检验数j,练习练习. . 单纯形表单纯形表最优吗？查什么？ 不是！ 谁进基?检验数最大的x1进基,谁出基?x1的系数有正的吗?求比值?79/4练习练习. . 单纯形表：迭代单纯形表：迭代基变量列中_换为_,x5x1改CB列,_换为_.-M4Excel练习用图解法和单纯形法求如下线性规划问题的最优解：Maxz=4x1+x2x1+3x27s.t.4x1+2x29x1,x20可行域在直线x1+3x2=7之_上上可行域在直线4x1+2x2=9之_上上练习用图解法练习用图解法0123456712345有可行解,但无有限的最优解,z+.练习练习. .用单纯形法用单纯形法标
6、准化为:Maxz=4x1+x2+0x3+0x4x1+3x2-x3=7s.t.4x1+2x2-x4=9x1,x2,x3,x40基是谁?这里“-”如何处理?引进两个“人工变量”x5,x6+x5-Mx5-Mx6M是一个大的正数(大M法),x5,x6+x6练习练习. .用单纯形法用单纯形法Maxz=4x1+x2+0x3+0x4-Mx5Mx6x1+3x2-x3+x5=7s.t.4x1+2x2-x4+x6=9x1,x2,x3,x4,x5,x60基是谁?x5,x6它们的检验数为0请它们出基,逼它们取值为0.Excel不能全出基,就无可行解.解解LPLP问题单纯形法问题单纯形法vLP问题解的几种可能：问题解的
7、几种可能：唯一解唯一解无无穷多解多解有解有解无解无解无有限最无有限最优解解无可行解无可行解解解LPLP问题单纯形法问题单纯形法vLP问题解的几种可能：问题解的几种可能：v无需引入人工无需引入人工变量量.一定有可行一定有可行解解,从而一定有基可行解从而一定有基可行解,但但还有有可能有无可能有无穷最最优解或无有限最解或无有限最优解解. Axb s.t. x0解解LPLP问题单纯形法问题单纯形法vLP问题解的几种可能：问题解的几种可能：v一般要引入人工一般要引入人工变量量. v人工人工变量不能全出基量不能全出基则无可行解无可行解,更更无最无最优解解. v不需人工不需人工变量或人工量或人工变量可以全部
8、出量可以全部出基基则必有可行解必有可行解.分分:v至少有一个非基至少有一个非基变量的量的检验数数为正正,但它的系但它的系数全数全为非正非正,则无有限最无有限最优解；解；v所有非基所有非基变量的量的检验数全数全为非正，已有最非正，已有最优解，解，但若其中至少有一个的但若其中至少有一个的检验数数为0，且它的系，且它的系数中有正的，数中有正的，则可能有无可能有无穷多个最多个最优解。解。 作业作业v第五章第五章(P.99-100)： 7a,b,c,dv预习第六章预习第六章2 线性规划的对偶问题线性规划的对偶问题练习一个一个LP问题的单纯形表如上：问题的单纯形表如上：1、试补齐中间的空格；、试补齐中间的空格；2、u取什么值时此问题取什么值时此问题有无穷多最优解有无穷多最优解？0606100606u5-6u00003-300150必须为必须为_0 u=5/6
