运筹学对偶理论与灵敏度分析.ppt

1 第2章线性规划的对偶理论与灵敏度分析 第一节线性规划的对偶理论 2 一 对偶问题的提出 在同一企业的资源状况和生产条件下产生的 且是同一个问题从不同角度考虑所产生的 因此两者密切相关 两个LP问题是互为对偶 3 即任何一个求maxZ的LP都有一个求minW的LP 原问题 LP 对偶问题 DP 4 1 原问题与对偶问题 对称形式 1 原问题中的约束条件个数等于它的对偶问题中的变量数 2 原问题中目标函数的系数是其对偶问题中约束条件的右端项 3 约束条件在原问题中为 则在其对偶问题中为 4 目标函数在原问题中为求最大值 在其对偶问题中则为求最小值 二 对偶理论 5 例2 2写出下述线性规划问题的对偶问题 解 按照上述规则 该问题的对偶线性规划为 6 非对称形式 例如 当原问题约束条件为等式 对偶问题 特点 对偶变量符号不限 7 对于一般情况下线性规划问题如何写出对偶问题 对于等式约束可以把它写成两个不等式约束 对于 的不等式 可以两边同乘 1 再根据对称形式的对偶关系写出对偶问题 然后进行适当的整理 使式中出现的所有系数与原问题中的系数相对应 归纳 表2 2 8 表2 2 9 例2 3写出下述线性规划问题的对偶问题 10 例2 4写出下述线性规划问题的对偶问题 11 2 对偶问题的基本定理 1 对称性 对偶问题的对偶是原问题 2 弱对偶定理 若X 0 是原问题的可行解 Y 0 是对偶问题的可行解 则有CX 0 Y 0 b 3 无界性 若原问题 对偶问题 为无界解 则其对偶问题 原问题 无可行解 4 最优性定理 若X 0 Y 0 分别是互为对偶问题的可行解 且CX 0 Y 0 b 则X 0 Y 0 分别是它们的最优解 5 强对偶定理 若互为对偶问题之一有最优解 则另一问题必有最优解 且它们的目标函数值相等 6 互补松驰性 若X Y 分别是原问题和对偶问题的可行解 则X Y 是最优解的充要条件是 Y XS 0 YSX 0 其中XS YS分别是原问题和对偶问题的松驰变量向量 12 证 设原问题是maxZ CX AX b X 0其对偶问题为minW Yb YA C Y 0 又因为 可得 对称变换 上式的对偶问题是 max W Yb YA C Y 0 两边取负号 因minW max W 得到 1 对称性 对偶问题的对偶是原问题 13 证 设原问题是 若X 0 是原问题的可行解 Y 0 是对偶问题的可行解 则有CX 0 Y 0 b 将右乘上式 得到 因为是LD的可行解 所以满足 对偶问题是 是LD的可行解 将左乘上式 得到 是LP可行解 满足约束 即 2 弱对偶定理 14 注意 不存在逆 当原问题 对偶问题 无可行解时 其对偶问题 原问题 或具有无界解或无可行解 若原问题 对偶问题 为无界解 则其对偶问题 原问题 无可行解 证 由弱对偶性CX 0 Y 0 b 显然得 3 无界性 15 证 若 所以是最优解 同样证明 对于LP所有可行解X 存在 可见使目标函数取值最小的可行解 既最优解 因为 所以 根据性质2 LD的所有可行解Y都存在 若X 0 Y 0 分别是互为对偶问题的可行解 且CX 0 Y 0 b 则X 0 Y 0 分别是它们的最优解 4 最优性定理 16 若互为对偶问题之一有最优解 则另一问题必有最优解 且它们的目标函数值相等 是原问题的最优解 对应基阵B必存在 即得到 其中 由此 得到 是对偶问题的最优解 5 强对偶定理 17 从上述性质中 可看到原问题与对偶问题的解必然是下列三种情况之一 原问题与对偶问题都有最优解 且CX Yb 一个问题具有无界解 则它的对偶问题无可行解 两个问题均无可行解 18 若X Y 分别是原问题和对偶问题的可行解 则X Y 是最优解的充要条件是 Y XS 0 YSX 0 其中XS YS分别是原问题和对偶问题的松驰变量向量 证明 设原问题和对偶问题的标准型是原问题对偶问题 6 互补松驰性 19 将原问题目标函数中的系数向量C用代替后 得到 必有 又若分别是原问题和对偶问题的最优解 则 若 则故是最优解 将对偶问题的目标函数中的系数向量 用代替后 得到 20 松约束 某一可行点 如X 和Y 处的严格不等式约束 包括对变量的非负约束 紧约束 严格等式约束 已知试通过求LD的最优解来求解LP的最优解 例2 5 21 化简为 又由于y1 1 y2 3 原问题的约束必为等式 即 将代入约束条件 1 2 5 紧约束 3 4 松约束 解 对偶问题为 令原问题的最优解为X x1 x2 x3 x4 x5 则根据互补松弛条件 必有x3 x4 0 图解 Y 1 3 W 11 22 无穷多解令x5 0 得到x1 1 x2 2 即X 1 1 2 0 0 0 Z 11 再令x5 2 3 得到x1 5 3 x2 0 即X 2 5 3 0 0 0 2 3 Z 11 23 1 影子价格 边际价格若LP的某个约束条件的右端项常数bi增加一个单位时 所引起的目标函数最优值Z 的改变量 第i个约束条件的影子价格 设 B是问题LP的最优基 由前式可知 Z CBB 1b Y b y 1b1 y 2b2 y ibi y mbm当bi变为bi 1时 其余右端项不变 也不影响B 则目标函数最优值变为 Z y 1b1 y 2b2 y i bi 1 y mbm所以有 Z Z Z y i 三 对偶问题的经济解释 影子价格 24 目标函数最优值对资源的一阶偏导数 问题中所有其它数据都保持不变 Z 对bi的变化率 经济意义是 在其它条件不变的情况下 单位资源变化所引起的目标函数的最优值的变化 即对偶变量yi就是第i个约束条件的影子价格 Z y 1b1 y 2b2 y ibi y mbm 25 问该公司如何安排生产才能使销售利润最大 表2 3生产消耗参数及产品售价 模型一 决策变量 甲 乙两种产品的数量两种原材料A B的使用量 模型二 决策变量 甲 乙两种产品的数量 例2 6 26 在最优决策下对资源的一种估价 没有最优决策就没有影子价格 又称 最优计划价格 预测价格 等 定量的反映了单位资源在最优生产方案中为总收益所做出的贡献 可称为在最优方案中投入生产的机会成本 若第i种资源的单位市场价格为mi当yi mi时 企业愿意购进这种资源 单位纯利为yi mi 则有利可图 yi mi 则企业有偿转让这种资源 可获单位纯利mi yi 否则 企业无利可图 甚至亏损 27 1 指出企业挖潜革新的途径影子价格 0 说明该资源已耗尽 成为短线资源 影子价格 0 说明该资源有剩余 成为长线资源 2 对市场资源的最优配置起着推进作用即在配置资源时 对于影子价格大的企业 资源优先供给 3 可以预测产品的价格产品的机会成本为CBB 1A C 只有当产品价格定在机会成本之上 企业才有利可图 2 影子价格的作用 28 4 可作为同类企业经济效益评估指标之一 对于资源影子价格越大的企业 资源的利用所带来的收益就越大 经济效益就越好 通过以上讨论可知 只有某资源对偶解大于0 该资源才有利可图 可增加此种资源量 若某资源对偶解为0 则不增加此种资源量 直接用影子价格与市场价格相比较 进行决策 是否买入该资源 29 1 单纯形法的重新解释设X 是最大化LP问题最优解的充要条件是 第二节 对偶单纯形法 30 1 初始单纯形表 检查b列 若都为非负 且检验数都为非正 得到最优解 停算 若b列至少还有一个负分量 检验数保持非正 转 2 2 确定换出变量对应基变量为换出变量 3 确定换入变量在单纯形表中检查所在的行的系数 若所有的 则无可行解 停止计算 若存在 计算 按 规则 所对应的列变量的非基变量为换入变量 4 以为主元素 按单纯形法进行换基迭代 得到新的单纯形表 重复 1 4 的步骤进行计算 对偶单纯形的计算步骤 31 例2 7用对偶单纯形法求解 32 33 34 1 初始解非可行解 检验数都是负数时 进行基变换 避免增加人工变量 运算简便 2 变量较少 约束条件很多的线性规划问题 可先将其变为对偶问题 再用对偶单纯形求解 简化计算 3 灵敏度分析 优点与用途 35 如市场条件发生变化 价值系数就会发生变化 当资源投入量发生改变时 也随着发生变化 当工艺条件发生改变时 也随着工艺的变化而变化 灵敏度分析1 系数在什么范围内变化时 最优解 基 不变 2 若系数的变化使最优解发生变化 如何最简便地求得新的最优解 值 结构 第三节 灵敏度分析 36 解 设三种产品的产量分别为x1 x2 x3 标准型为maxZ 5x1 8x2 6x3x1 x2 x3 x4 12x1 2x2 2x3 x5 20 x1 x2 x3 x4 x5 0 已知某企业计划生产3种产品A B C 其资源消耗与利润如表2 12所示 问 如何安排产品产量 可获最大利润 例2 9 37 最优方案为X 4 8 0 T 目标值为84 38 Cj的灵敏度分析 最优表 表2 16 若C3 10时 j 2 0 这时原方案已不是最优方案 原最优方案不发生改变 j 0 这时对最优解方案没有影响 在例2 9中 如果改变C3 使 j cj CBB 1Pj 1 目标函数中的价值系数 1 非基变量的价值系数 39 则最优方案调整为X 4 0 8 T 目标值为100 40 即单位产品A的利润在 4 8 之间变化时 最优方案不变 但最优值为 2 基变量的价值系数 41 为10时 原方案已不是最优方案 则最优方案调整为X 12 0 0 T 目标值为120 42 对偶单纯形法 新的最优方案 最优基不变 即生产产品的品种不变 但最优值会变化 影响最优解和最优值 2 资源b的灵敏度分析 43 即原料甲的供应量在 10 20 之间时并不影响最优方案 当时 最优方案调整为X 16 2 0 T 目标值为96 44 最优方案为X 20 0 0 T 目标值为100 45 新产品D 单位产品消耗原材料甲 3个单位 乙 2个单位 利润10 问 投产D是否有利 1 D利润为多少 投产产品D有利 最优方案不变 投产产品D无利 3 添加新变量的灵敏度分析 46 2 当时 生产B产品9件 生产D产品1件 目标值为87 47 假设电力供应紧张 13单位产品A B C每单位需电力 2 1 3个单位问该公司生产方案是否需要改变 加入松弛变量得2x1 x2 3x3 x6 13 解 原最优解 4 8 0 T 原解已不是新约束条件下的最优解 以x6为基变量 将上式反映到最终单纯形表中 化B I得表2 25 代入电力约束条件2x1 x2 3x3 13 4 添加新约束 48 对偶单纯形法 生产A产品1件 生产B产品9件 目标值为82 49 1 非基变量的工艺发生改变影响列 看检验数是大于零还是小于零 小于零 单纯形法 2 基变量的工艺发生改变当是基变量的系数时 它的变化会使发生改变 所以最终单纯形表也要发生变化 改变 计划生产的产品工