第2章 线性规划及对偶理论.ppt

6-1 价值系数cj发生变化(仅影响检验数) 单纯形表 CN - CBB-1N 0 ?j B-1N I B-1b XB CB xn x2 x1 b 基 CB cn c2 c1 cj s.t. 例 已知下述线性规划的最终单纯形表为 cj -zj x5 x4 x3 x2 x1 b 基 CB 0 0 0 3 2 cj → x2 x4 x1 3 0 2 -1/5 0 1/2 0 1 3 1/5 0 0 1 0 3 4/5 1 -2 0 0 4 -1/5 0 -1 0 0 (1) 若c由(2, 3)变成(3, 2), 最优解是否发生变化? (2) 若目标函数为 问 分别在什么范围内变化时，问题的最优解不变？ 当 在什么范围内变化时，问题的最优解不变？ CN - CBB-1N 0 ?j B-1N I B-1b XB CB xn x2 x1 b 基 CB cn c2 c1 cj 例 已知下述线性规划的最终单纯形表为 cj -zj x5 x4 x3 x2 x1 b 基 CB 0 0 0 3 2 cj → x2 x4 x1 3 0 2 -1/5 0 1/2 0 1 3 1/5 0 0 1 0 3 4/5 1 -2 0 0 4 -1/5 0 -1 0 0 (1) 若c由(2, 3)变成(3, 2), 最优解是否发生变化? 解： 将c的变化反映到最终单纯形表中 cj -zj x5 x4 x3 x2 x1 b 基 CB 0 0 0 3 2 cj → x2 x4 x1 3 0 2 -1/5 0 1/2 0 1 3 1/5 0 0 1 0 3 4/5 1 -2 0 0 4 -1/5 0 -1 0 0 3 2 3 2 - 3/2 -1 1/2 -5/2 0 0 0 1 0 5/4 0 0 5 x5 0 -1/4 -1/4 1/4 0 0 cj -zj 1 0 2 x2 2 0 1 4 x1 3 [ ] 最优解是(4,2,0,0,5), 最优值16 1/ 5 cj -zj x5 x4 x3 x2 x1 b 基 CB 0 0 0 3 2 cj → x2 x4 x1 3 0 2 -1/5 0 1/2 0 1 3 1/5 0 0 1 0 3 4/5 1 -2 0 0 4 -1/5 0 -1 0 0 (2) 若目标函数为 问 分别在什么范围内变化时, 问题的最优解不变？ cj -zj x5 x4 x3 x2 x1 b 基 CB 0 0 0 3 2 cj → x2 x4 x1 3 0 2 -1/5 0 1/2 0 1 3 1/5 0 0 1 0 3 4/5 1 -2 0 0 4 1/5 0 -1 0 0 解： 当 即 最优解不变. 时, 类似可讨论，当 最优解不变. cj -zj x5 x4 x3 x2 x1 b 基 CB 0 0 0 3 2 cj → x2 x4 x1 3 0 2 -1/5 0 1/2 0 1 3 1/5 0 0 1 0 3 4/5 1 -2 0 0 4 -1/5 0 -1 0 0 (3) 若目标函数为 问 在什么范围内变化时, 问题的最优解不变？ cj -zj x5 x4 x3 x2 x1 b 基 CB 0 0 0 3 2 cj → x2 x4 x1 3 0 2 -1/5 0 1/2 0 1 3 1/5 0 0 1 0 3 4/5 1 -2 0 0 4 1/5 0 -1 0 0 解： 当 即 最优解不变. 时, o 6-2 分析bi的变化范围 CN - CBB-1N 0 ?j B-1N I B-1b XB CB xn x2 x1 b 基 CB cn c2 c1 cj 引入人工变量, 编制新的单纯表, 重新计算 非可行解 非可行解 用对偶单纯形法继续迭代 可行解 非可行解 用单纯形法继续迭代 非可行解 可行解 仍为最优解 可行解 可行解 结论或继续计算的步骤 对偶问题 原问题 bi的变化引起基变量的取值发生变化，有可能发生1、3两种情况 s.t. 例 已知下述线性规划的最终单纯形表为 cj -zj x5 x4 x3 x2 x1 b 基 CB 0 0 0 3 2 cj → x2 x4 x1 3 0 2 -1/5 0 1/2 0 1 3 1/5 0 0 1 0 3 4/5 1 -2 0 0 4 -1/5 0 -1 0 0 (1) 若b由(12,16,15)变成(15,12,20), 最优基是否发生变化? (2) 若b变成 ，分别分析 在什么范围内变化时, 问题的最优基不变。 (3) 当 在什么范围内变化时