运筹学课件.ppt

§5单纯形法进一步讨论 处理方法一 大Ｍ法 人造基 添加人工变量造成基 去掉人工变量 人工变量 §5单纯形法进一步讨论 原问题的可行解 新问题的可行解 目标值 结论：新问题的最优解中，如果人工变量均为零，则得到的解也是原问题的最优解，否则原问题无可行解 例6 大M法 -M 0 -1 0 x5 0 0 0 1 0 x6 -M 0 0 -1 1 -2 1 x6 -M 0 0 1 4M -2M-3 cj-zj 1 0 1 3 0 9 x7 -M 0 1 1 1 1 4 x4 0 x7 x4 x3 x2 x1 b -M 0 1 0 -3 cj XB CB 表1-10 0 x4 0 0 0 1 1 -1/2 -1/2 -1/2 0 x2 3 0 1 1/3 0 0 0 1/3 -3 x1 1 1 0 2/3 0 1/2 -1/2 1/6 cj-zj 0 0 3 0 3/2 -M-3/2 -M+1/2 CB XB cj -3 0 1 0 0 -M -M b x1 x2 x3 x4 x5 x6 x7 0 x4 3 3 1 1 1 0 0 0 0 x2 1 -2 1 -1 0 -1 1 0 -M x7 6 6 3 1 0 0 0 1 cj-zj 6M-3 0 4M+1 0 3M -4M 0 0 x4 0 0 0 0 1 -1/2 1/2 -1/2 0 x2 5/2 -1/2 1 0 0 -1/4 1/4 1/4 -3 x3 3/2 3/2 0 1 0 3/4 0 1/4 cj-zj -2/9 0 0 0 -3/4 -M+3/4 -M-1/4 最优解:X=(0,5/2,3/2,0,0,0,0) 最优值： Z= 3/2 大M法举例 CB XB cj 1 2 0 0 -M xj b x1 x2 x3 x4 x5 0 x4 1 1 1 0 1 0 -M x5 4 -1 2 -1 0 1 cj-zj 0 1 2 0 0 0 CB XB cj -1 -2 0 0 -M xj b x1 x2 x3 x4 x5 0 x4 1 1 1 0 1 0 -M x5 4 -1 2 -1 0 1 cj-zj 0 1 2 0 0 0 -2 x2 1 1 1 0 1 0 -M x5 2 -3 0 -1 -2 1 cj-zj 2 1 0 0 2 0 CB XB cj -1 -2 0 0 -M xj b x1 x2 x3 x4 x5 -2 x2 1 1 1 0 1 0 -M x5 2 -3 0 -1 -2 1 －Ｚ 2 1 0 0 2 0 M 2 -3 0 -1 -2 0 所有检验数0 已经是最优解 x5=2 人工变量不为零, 表示原问题无可行解 参照图解法结果 §5单纯形法进一步讨论 处理方法二 两阶段法 人造基 添加人工变量造成基 去掉人工变量 人工变量 两阶段法 如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。 §5单纯形法进一步讨论 第一阶段 第一阶段最优解中: 如果Z0, 则原问题没有基本可行解; 如果Z=0, 则若人工变量全为非基变量,则得到原问题的基本可行解. 否则基本可行解退化,继续迭代就可以得到基本可行解. §5单纯形法进一步讨论 第二阶段 以第一阶段最优基作为初始基本可行解,继续迭代. 第一阶段 例 6 两阶段法 第一阶段： -1 0 -1 0 x5 0 0 0 1 0 x6 -1 0 0 -1 1 -2 1 x6 -1 0 0 0 4 -2 cj-zj 1 0 1 3 -1 9 x7 -1 0 1 1 1 1 4 x4 0 x7 x4 x3 x2 x1 b -1 0 0 0 0 cj XB CB 表1-11 请注意: 第一阶段的最优解不是唯一的 3 3 -1 1 x5 0 -4 -3 1 -1 x6 -1 0 0 -1 1 -2 1 x2 0 0 0 4 0 6 cj-zj 1 0 4 0 6 6 x7 -1 0 1 2 0 3 3 x4