运筹学基础线性规划.ppt

第一页，共三十九页，2022年，8月28日 另例： 0 0 0 -3 -4 12 -1 0 2 3 16 0 -1 4 2 x1 　x2 　x3 x4 b 问题：无标准的初始可行基，如何利用单纯形法求解 化为标准形 不是标准的初始可行基 第二页，共三十九页，2022年，8月28日 三、人工变量问题 用单纯形法解题时，需要有一个单位矩阵作为初始基。 当约束条件都是“≤”时，加入松弛变量就形成了初始基。 但如果存在“≥”或“＝”型的约束，就没有现成的单位矩阵。 采用人造基的办法：人为构造单位矩阵 处理方法有两种： 大M 法 两阶段法 第三页，共三十九页，2022年，8月28日 （一）大M法 maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x2 , x3 ≥0 S.t. 没有单位矩阵，不符合构造初始基的条件，需加入人工变量 。 maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 ≥0 人工变量最终必须等于0才能保持原问题性质不变。 为保证人工变量为0，在目标函数中令其系数为-M。 M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。 如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。 第四页，共三十九页，2022年，8月28日 大M法求解 按大M法构造人造基，引入人工变量x4 , x5 的辅助问题如下： 例如 maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x2 , x3 ≥0 S.t. maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 ≥0 第五页，共三十九页，2022年，8月28日 初始单纯形表为： 0 -M -2 -1 3 4 1 1 -2 1 6 0 -3 2 3 -M 0 1 ～ 10M 0 -2-2M -1 3+4M 4 1 1 -2 1 6 0 -3 2 3 0 0 1 3+3M -1+2M -2-3M 0 -M 6M 所以，此时求解不是最优解，需要换基。 x1 　 x2 　 x3 x4 x5 b 10M 0 -2-2M -1 3+4M 4 1 1 -2 1 6 0 -3 2 3 0 0 1 3+4M -1 -2-2M 0 0 10M ～ 第六页，共三十九页，2022年，8月28日 10M 0 -2-2M -1 3+4M 4 1 1 -2 1 6 0 -3 2 3 0 0 1 ～ -6+2M 0 1+2M -3-8M/3 0 2 1 2 -8/3 0 2 0 -1 2/3 1 -1-4M/3 -1/3 1/3 -7 -M-1/2 0 -5/3 0 1 1/2 1 -4/3 0 3 1/2 0 -2/3 1 -M-5/6