线性规划[对偶问题](第3章2014.9).ppt

OR课件 LP （2）影子价格的获取 影子价格，又称Lagrange乘子或灵敏度系数，通常指线性规划对偶模型中对偶变量的最优取值。 当所有资源按最优方式分配时，第 i种资源的影子价格 给出了第i 种资源（单位）追加量的边际利润。 因此，人们可根据yi 的大小，对第i 种资源紧缺程度和占用的经济效果做出判断，探讨资源的优化利用为企业决策服务。 §4对偶问题的经济解释 OR课件 LP （3）影子价格在经营决策中的应用 （i）影子价格能指示企业内部挖潜的方向 因为影子价格能指出各种资源在实现企业最优目标时的影响作用，影子价格越高的资源，表明它对目标增益的影响愈大，同时也表明这种资源对该企业来说愈稀缺和愈贵重，企业的管理者就应该更加重视对这种资源的管理，通过挖潜革新、降低消耗或及时补充该种资源，以保证给企业带来较大的收益。 （ii）影子价格在企业经营决策中的作用 企业的决策者可以把本企业资源的影子价格与当时的市场价相比较，当某种资源的影子价格高于市场价格时，则企业可以买进该种资源；而当某种资源的影子价格低于市场价格时（特别是当影子价格为零时），则企业可以卖出该种资源，以获得较大的利润。 §4对偶问题的经济解释 OR课件 LP 基本思想： 最优 原问题（MaxZ)： 保持原问题可行（bi0) 当所有的检验数满足最优性检验 （cj-zj?0） 即：保持原问题可行，将对偶问题由不可行转化为可行 对偶问题（MinS）： 保持对偶问题可行 （ cj-zj?0） 当所有的bi0，则 即：保持对偶问题可行，将原问题由不可行化为可行 §5对偶单纯形法 OR课件 LP 计算步骤： 找出基本解，满足cj-zj≤0 bi0? Y 最优解 N i=L aLj′≥0? Y 无解 N 找出基本解，满足cj-zj≤0 ? ? §5对偶单纯形法 OR课件 LP 解：化标准型 §5对偶单纯形法 OR课件 LP 列入单纯形表： 换出变量：Min{bi|bi0}＝bL 换入变量：Min{负检验数/aLj|aLj0} Min{-1200/-2;-800/-2;-1200/-4}=300 -4 §5对偶单纯形法 OR课件 LP -1 -2 §5对偶单纯形法 OR课件 LP 有非基变量的检验数为0，多重解 最优解为：X＝（0,3/2,1/8,0,0,0） S=1400 §5对偶单纯形法 OR课件 LP 基本思想 在求出线性规划问题的最优解后，又增加一个约束条件，此时不必对新问题从头做起，而用对偶单纯形法可以求出问题的最优解。 其步骤如下： §6对偶单纯形法的应用 OR课件 LP 步骤 新增约束条件A 已得最优解满足A? 最优解 代入进行初等变换 对偶单纯形法 Y N ? §6对偶单纯形法的应用 OR课件 LP 解：用一般单纯形法求出的最优单纯形表如下表 §6对偶单纯形法的应用 OR课件 LP 现增加一个约束条件 ，加上松弛变量后，则 显然， 上表中的最优解违反了新的约束条件，转入下一步 §6对偶单纯形法的应用 OR课件 LP 初 等 变 换 §6对偶单纯形法的应用 OR课件 LP 对 偶 单 纯 形 法 -1 §6对偶单纯形法的应用 OR课件 LP 最优解为 x1=15, x2=65/3, x3=5, x4=x5=x6=0 Z=1695 §6对偶单纯形法的应用 可以取代大 M法和两阶段法 给整数规划问题的求解带来极大的方便 OR课件 LP 小结------对偶单纯法 §6对偶单纯形法的应用 OR课件 LP 回 顾 对于所有的线性规划问题基本可以求解； 可以获得决策变量的信息、目标函数的信息以及资源用完与否的信息等，如生产计划问题。 但是： 如何判断资源在规划中的重要程度？ 有没有什么方法可以替代因“构造基”，给LP问题求解带来的繁琐？ 如何从LP问题的求解过程中获得更多信息，以增强决策的准确性。 OR课件 运 筹 帷 幄 之 中 决 胜 千 里 之 外 对偶理论 第三章 Dual Theory OR课件 LP 主 要 内 容 §1 对偶问题及其数学模型 §2 对偶问题的性质 §3 原问题与对偶问题的对应关系 §4 对偶问题的经济解释 §5 对偶单纯形法 §6 对偶单纯形法的应用 重点 对偶问题的性质，对偶模型的建立和对偶单纯形法迭代原理。 难点 原问题与对偶问题在模型和解方面的对应关系。 本章 重点、难点 OR课件 OR课件 LP （1）什么是对偶问题？ （2）如何建立对偶问题？ §1对偶问题及其数学模型 OR课件 LP （1）什么是对偶问题？ 常识： 方形中：周长一定，正方形面