11LP问题的单纯形法大M法,无解.ppt

《运筹学》单纯形法 教案要点 文 件 名：051OR11.PPT；第五章.XLS 授课时间：第十一讲 授课内容：LP问题的单纯形法大M法,无解. 预备知识：凸集合，Excel 复习可行解、基可行解，基及非基变量。 难 点：引入人工变量,解的各种情况. 重 点：单纯形法的步骤：引入人工变量,初始表，检验数，判优，进基、比值、出基、迭代，无解、无穷界的情况表上操作；利用Excel。 下节预习：教材第六章§2 对偶理论。 《运筹学》单纯形法 解LP问题单纯形法 LP问题解的几种可能： 解LP问题单纯形法 LP问题解的几种可能： 解LP问题单纯形法 LP问题解的几种可能： 作业 第五章(P.99-100)： 7a,b,c,d 练习 一个LP问题的单纯形表如上： 1、试补齐中间的空格； 2、u取什么值时此问题有无穷多最优解？ * 练习㈠用图解法和单纯形法求如下线性规划问题的最优解： Max z =4 x1 + x2 x1 + 3x2 ≤ 7 s.t. 4x1 + 2x2 ≤ 9 x1 , x2 ≥ 0 x1+3x2=7经过点(__,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 练习㈠. 单纯形表 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 练习㈠. 单纯形表 1 3 1 0 7 4 2 0 1 9 4 1 0 0 x3 x4 0 0 0 0 0 0 0 4 1 0 0 最优吗？ 查什么？ 不是！ 谁进基？ 检验数最大的x1进基, 谁出基？ x1的系数有正的吗？ 求比值？ 7 9/4 9/4 4 1 3 1 0 7 4 2 0 1 9 4 1 0 0 x3 x4 0 0 0 0 0 0 0 4 1 0 0 9/4 7 练习㈠. 单纯形表 基变量列中___换为___, x4 x1 改CB列,___换为___. 0 4 Excel 练习㈠用单纯形法 x3 x4 4 1 0 0 0 0 1 3 1 0 7 4 2 0 1 9 迭代次数 基 变量 CB x1 x2 x3 x4 bi 比 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 迭代次数 基 变量 CB x1 x2 x3 x4 bi 比 ? ? ? ? ? ? ? ? ? ? ? ? ?