第3章线性规划的解法(3).ppt

1 3 4单纯形法的进一步讨论 用人工变量法找初始可行基 问题的提出 在前面讨论的L P问题的约束条件都是 形式 在引进松驰变量后 就直接提供了一个单位矩阵作为现成的可行基B 但对于 形式 靠引进松驰变量却不行了 为了得到一个单位矩阵作为现成的可行基B 有必要引进人工变量 引进人工变量后可用两阶段法和大M法 2 二 大M法 3 大M法 引入人工变量xn i 0 i 1 m 及充分大正数M 得到 Maxz c1x1 c2x2 cnxn Mxn 1 Mxn ms t a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bmx1 x2 xn xn 1 xn m 0 单纯形法 4 显然 xj 0j 1 n xn i bii 1 m是基本可行解 对应的基是单位矩阵 结论 若得到的最优解满足xn i 0i 1 m则是原问题的最优解 否则 原问题无可行解 大M法 5 Maxz 5x1 2x2 3x3 x4 Mx5 Mx6s t x1 2x2 3x3 x5 152x1 x2 5x3 x6 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 x5 x6 0 大M法问题 LP M 以上面的例说明大M法 6 大M法 LP M 得到最优解 25 3 10 3 0 11 T最优目标值 112 3 7 注意到 1 M是在引入人工变量时的派生出来的 在运算中可只看作一个代数符号参加运算 2 只有人工变量完全 出基 取值为0 问题才会有最优解 3 计算机求解时 由于M只能输入一个机器最大字长数 不是任意大 可能会造成运算错误 故大M法一般仅适用于手工求解 8 一 两阶段法 基本思想第一阶段 通过求解辅助问题L P 的最优基可行解得到原问题的初始基可行解 辅助问题L P 目标函数只含系数都为 1 求最大值时为 1 求最小值时为 1 的人工变量 原L P问题的约束条件不变 如果辅助问题的最优解不能使Z 0 表明最优解中含有人工变量的非零解 这时原L P问题无解 第二阶段 求原问题的最优解 从第一阶段的最优表出发 目标函数恢复为原L P问题的目标函数 去掉人工变量 继续求出最优解 9 10 用单纯形法求得W 0 最优解X 3 2 1 2 0 0 0 0 T 计算过程如下 11 将第一阶段最终表中人工变量删去 并将目标行的各价值系数换为原目标函数的价值系数 进行第二阶段计算 结果如下 问题的最优解为X 3 2 1 2 T 目标函数值Z 9 4 12 Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 两阶段法 13 两阶段法 引入人工变量xn i 0 i 1 m 构造 Maxz xn 1 xn 2 xn ms t a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bmx1 x2 xn xn 1 xn m 0 14 第一阶段求解上述问题 显然 xj 0j 1 n xn i bii 1 m是基本可行解 它对应的基是单位矩阵 结论 若得到的最优解满足xn i 0i 1 m则是原问题的基本可行解 否则 原问题无可行解 得到原问题的基本可行解后 第二阶段求解原问题 15 例 LP Maxz 5x1 2x2 3x3 x4s t x1 2x2 3x3 152x1 x2 5x3 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 0 两阶段法 16 第一阶段问题 LP 1 Maxz x5 x6s t x1 2x2 3x3 x5 152x1 x2 5x3 x6 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 x5 x6 0 17 第一阶段 LP 1 得到原问题的基本可行解 0 15 7 25 7 52 7 T 18 第二阶段把基本可行解填入表中 得到原问题的最优解 25 3 10 3 0 11 T最优目标值 112 3 19 注意 单纯形法中1 每一步运算只能用矩阵初等行变换 2 表中第3列 b列 的