《运筹学单纯形法的进一步讨论精选课件.ppt》由会员分享，可在线阅读，更多相关《运筹学单纯形法的进一步讨论精选课件.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于运筹学单纯形法关于运筹学单纯形法的进一步讨论的进一步讨论第一页，本课件共有21页一、一、LP问题的标准化问题的标准化LP模型的标准形式模型的标准形式运筹学 第4讲：单纯形法的进一步讨论max Z=CXs.t.AX=b X 0Q 目标函数为目标函数为max型型Q X 0Q b 0!单纯形法仅适于单纯形法仅适于LP标准模型的求解标准模型的求解第二页，本课件共有21页非标准型非标准型LP模型的标准化模型的标准化（P10）一、若目标函数为：一、若目标函数为：min Z=CX 令令Z=-Z，则原目标函数转化为，则原目标函数转化为 max Z=-CX二、若存在二、若存在bi 0 将将bi所在的约束条件
2、式两边同乘（所在的约束条件式两边同乘（1）三、若约束条件不等式为三、若约束条件不等式为“”左式加入松弛变量左式加入松弛变量xj，xj0运筹学 第4讲：单纯形法的进一步讨论第三页，本课件共有21页五、若存在五、若存在xj无约束无约束 可令可令xj=xj-xj,xj,xj0六、若存在六、若存在xj 0时，说明模型中存在多余的约束，使多个时，说明模型中存在多余的约束，使多个基可行解对应同一顶点。当模型存在退化解时，处理方基可行解对应同一顶点。当模型存在退化解时，处理方法如下：法如下：最小比值相同时，取下标值最大的变量为换出变量最小比值相同时，取下标值最大的变量为换出变量 j最大值相同时，取下标值最小
3、的变量为换入变量最大值相同时，取下标值最小的变量为换入变量运筹学 第4讲：单纯形法的进一步讨论第八页，本课件共有21页(大大M法的问题在于：采用手工计算求解不会法的问题在于：采用手工计算求解不会碰到问题，但用计算机求解时，对碰到问题，但用计算机求解时，对M只能在计只能在计算机中输入一个机器最大字长的数字；显然，算机中输入一个机器最大字长的数字；显然，如果其他参数值大于或与这个数字相近，便会如果其他参数值大于或与这个数字相近，便会导致计算结果发生错误！导致计算结果发生错误！运筹学 第4讲：单纯形法的进一步讨论第九页，本课件共有21页max z=-4x1 x2 s.t.3x1+x2 =3 4x1+
4、3x2-x3=6 x1+2x2+x4=4 x1-4 0例例3 3：P20P20例例2.62.6运筹学 第4讲：单纯形法的进一步讨论第十页，本课件共有21页运筹学 第4讲：单纯形法的进一步讨论第十一页，本课件共有21页三、二阶段法三、二阶段法 针对大针对大M法存在的问题，我们可以对添加人工变量后的法存在的问题，我们可以对添加人工变量后的LP模型分为两个阶段来计算，称为二阶段法模型分为两个阶段来计算，称为二阶段法(P22)。第一阶段：先求一个目标函数中只包含人工变量的第一阶段：先求一个目标函数中只包含人工变量的LP模型，也就模型，也就是说，令目标函数中其他变量的系数为是说，令目标函数中其他变量的系
5、数为0，人工变量的系数为某个，人工变量的系数为某个正常数正常数(一般为一般为1)，在原问题约束条件不变的情况下求解。，在原问题约束条件不变的情况下求解。第二阶段：当第一阶段求解结果表明模型有可行解时，在原问题中去第二阶段：当第一阶段求解结果表明模型有可行解时，在原问题中去除人工变量，从第一阶段的最优解出发，继续求解。除人工变量，从第一阶段的最优解出发，继续求解。例例4 4：采用二阶段法求解采用二阶段法求解P22P22中中LPLP模型模型运筹学 第4讲：单纯形法的进一步讨论第十二页，本课件共有21页运筹学 第4讲：单纯形法的进一步讨论首先应确定当首先应确定当x5,x6=0时，可行域是否存在！时，
6、可行域是否存在！则第一阶段先求解如下的则第一阶段先求解如下的LPLP模型：模型：显然，若显然，若z=0，即，即x5,x6=0，则问题的可行域存在。，则问题的可行域存在。第十三页，本课件共有21页运筹学 第4讲：单纯形法的进一步讨论x5,x6=0，则，则 z=0，问题的可，问题的可行域存在。行域存在。第十四页，本课件共有21页运筹学 第4讲：单纯形法的进一步讨论去除去除x5和和x6，进一步求解第，进一步求解第二阶段的二阶段的LP模型：模型：得到最优解和最优值。得到最优解和最优值。第十五页，本课件共有21页四、采用单纯形法求解的几种情况四、采用单纯形法求解的几种情况 惟一最优解惟一最优解 无可行解
7、无可行解(P23-例例2.7)所有检验数所有检验数j 0，但基变量中仍含有非零人工变量，但基变量中仍含有非零人工变量 无界解无界解(例例5)当存在最大的当存在最大的j 0，但，但值无解值无解 多重最优解多重最优解(例例6:习题习题2-1)当所有检验数当所有检验数0，但存在非基变量，但存在非基变量j=0，该非基变量可，该非基变量可以作为换入变量，模型存在多重最优解以作为换入变量，模型存在多重最优解运筹学 第4讲：单纯形法的进一步讨论第十六页，本课件共有21页max z=3x1+2x2 s.t.-2x1+x2 2 x1-3x2 3 x1,x2 0例例5 5：求解如下求解如下LPLP模型模型运筹学
8、第4讲：单纯形法的进一步讨论第十七页，本课件共有21页cj 3200bbi/aikcBXBx1x2x3x50 x3-21102/0 x41-30133j(1)3200max z=3x1+2x2+0 x3+0 x4 s.t.-2x1+x2+x3=2 x1-3x2 +x4=3 x1,x2 0解：将模型化为标准型，解：将模型化为标准型，运筹学 第4讲：单纯形法的进一步讨论第十八页，本课件共有21页cj 3200bbi/aikcBXBx1x2x3x50 x3-21102/0 x41-30133j(1)32000 x30-5128/3x11-3013/j(2)0110-3 由于由于maxj j|j j 0所对应的所对应的值无解，则该值无解，则该LP问题解无界。问题解无界。运筹学 第4讲：单纯形法的进一步讨论第十九页，本课件共有21页作业：作业：习题习题2-62-6，习题，习题2-72-7，2.3(2.3(2,32,3)准备：习题准备：习题2-112-11，案例，案例1 1，案例，案例2 2运筹学 第4讲：单纯形法的进一步讨论第二十页，本课件共有21页感感谢谢大大家家观观看看第二十一页，本课件共有21页