运筹学第4讲：单纯形法的进一步讨论

1、第4讲：单纯形法的进一步讨论1一、LP问题的标准化LP模型的标准形式运筹学 第4讲：单纯形法的进一步讨论max Z = CXs.t. AX = b X 0 目标函数为max型 X 0 b 0! 单纯形法仅适于LP标准模型的求解2非标准型LP模型的标准化（P10）一、若目标函数为：min Z = CX 令Z = -Z，则原目标函数转化为 max Z = -CX二、若存在bi 0 将bi所在的约束条件式两边同乘（1）三、若约束条件不等式为“” 左式加入松弛变量xj，xj0运筹学 第4讲：单纯形法的进一步讨论3五、若存在xj无约束 可令xj = xj - xj, xj, xj0六、若存在xj 0时，

2、说明模型中存在多余的约束，使多个基可行解对应同一顶点。当模型存在退化解时，处理方法如下： 最小比值相同时，取下标值最大的变量为换出变量 j最大值相同时，取下标值最小的变量为换入变量运筹学 第4讲：单纯形法的进一步讨论8 大M法的问题在于：采用手工计算求解不会碰到问题，但用计算机求解时，对M只能在计算机中输入一个机器最大字长的数字；显然，如果其他参数值大于或与这个数字相近，便会导致计算结果发生错误！运筹学 第4讲：单纯形法的进一步讨论9max z = -4x1 x2 s.t. 3x1 + x2 = 3 4x1 + 3x2 - x3 = 6 x1 + 2x2 + x4 = 4 x1-4 0例3：P

3、20例2.6运筹学 第4讲：单纯形法的进一步讨论10运筹学 第4讲：单纯形法的进一步讨论11三、二阶段法 针对大M法存在的问题，我们可以对添加人工变量后的LP模型分为两个阶段来计算，称为二阶段法(P22)。 第一阶段：先求一个目标函数中只包含人工变量的LP模型，也就是说，令目标函数中其他变量的系数为0，人工变量的系数为某个正常数(一般为1)，在原问题约束条件不变的情况下求解。 第二阶段：当第一阶段求解结果表明模型有可行解时，在原问题中去除人工变量，从第一阶段的最优解出发，继续求解。例4：采用二阶段法求解P22中LP模型运筹学 第4讲：单纯形法的进一步讨论12运筹学 第4讲：单纯形法的进一步讨论

4、首先应确定当x5, x6=0时，可行域是否存在！则第一阶段先求解如下的LP模型：显然，若z=0，即x5, x6=0，则问题的可行域存在。13运筹学 第4讲：单纯形法的进一步讨论x5, x6=0，则 z=0，问题的可行域存在。14运筹学 第4讲：单纯形法的进一步讨论去除x5和x6，进一步求解第二阶段的LP模型：得到最优解和最优值。15四、采用单纯形法求解的几种情况 惟一最优解 无可行解(P23-例2.7) 所有检验数j 0，但基变量中仍含有非零人工变量 无界解(例5) 当存在最大的j 0，但值无解 多重最优解(例6:习题2-1) 当所有检验数0，但存在非基变量j = 0，该非基变量可以作为换入变量，模型存在多重最优解运筹学 第4讲：单纯形法的进一步讨论16max z = 3x1 + 2x2 s.t. -2x1 + x2 2 x1 - 3x2 3 x1, x2 0例5：求解如下LP模型运筹学 第4讲：单纯形法的进一步讨论17max z = 3x1 + 2x2 + 0 x3 + 0 x4 s.t. -2x1 + x2 + x3 = 2 x1 - 3x2 + x4 = 3 x1, x2 0解：将模型化为标准型，运筹学 第4讲：单纯形法的进一步讨论18 由于maxj |j 0所对应的值无解，则该LP问题解无界。运筹学