运筹学二.ppt

第二章 线性规划的 对偶理论与灵敏度分析 主要内容： 第一节 线性规划的对偶问题 第二节 对偶问题的基本性质 第三节 影子价格 第四节 对偶单纯形法 第五节 灵敏度分析 第一节 线性规划的对偶问题 一、对偶问题的提出 例1（回顾第一章）：美佳公司计划制造Ⅰ，Ⅱ两种家电产品。已知各制造一件时分别占用的设备A,B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。 表1-1 例2：在例1中，若有某个公司想把美佳公司的资源收购过来，它至少付出多大的代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。 因此，该问题的数学模型为： 二、对称形式下对偶问题的一般形式 满足下列条件的线性规划问题称为具有对称形式： 其变量均具有非负约束，其约束条件当目标函数求极大时均取“≤”，当目标函数求极小时均取“≥”。 第二节 对偶问题的基本性质 一、单纯形法的矩阵描述 二、对偶问题的基本性质 1.对称性 2.弱对偶性 3.最优性 4.强对偶性 5.互补松弛性 对称性：对偶问题的问偶即原问题 证明： 弱对偶性： 如果 是原问题的可行解， 是其对偶问题的可行解，则恒有： 证明：因为 是原问题的可行解，故有： 推论： （1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 （2）在一对对偶问题中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。 （3）在一对对偶问题中，若一个问题可行，而另一个问题不可行，则该可行的问题的目标函数无界。 最优性： 若 和 分别是原问题和对偶问题的可行解,且 ， 则 和 分别是原问题和对偶问题的最优解。 强对偶性： 若一对对偶问题的原问题和对偶问题都有可行解，则它们都有最优解，且目标函数的最优值相等。 综上所述，一对对偶问题的解，只能有下面三种情况之一出现： （1）都有最优解，分别设为 和 ，且必有 ； （2）一个问题无界，另一个问题无可行解； （3）两个都无可行解。 互补松弛性： 若 和 分别是原问题和对偶问题的可行解。则有： 若 和 分别是原问题和对偶问题的最优解。则有： 例子： 已知如下线性规划问题 解：首先写出原问题的对偶问题如下 第三节 影 子 价 格（shadow price) 一、影子价格的定义 二、多方面理解影子价格 第四节 对偶单纯形法 一、对偶单纯形法的原理 对偶单纯形法是求解线性规划问题的另一基本方法。 二、对偶单纯形法的步骤 1.找出对偶问题的初始基可行解，列出初始单纯形表； 2.进行最优性检验，若得到最优解，停止；若没有得到最优解，转入步骤3； 3.确定换出基变量； 4.确定换入基变量； 5.用换入变量代替换出变量，得到新的单纯形表；重新转入步骤2. 第五节 灵 敏 度 分 析 一、灵敏度分析的含义及思路 灵敏度分析，是针对某确定的线性规划问题，考虑其模型中一个或几个系数（ )发生变化时，已经求得的最优解会发生什么变化，以及这些系数在什么范围内变化时，问题的最优解不会发生变化。 在研究一个或几个参数变化后模型的最优解时，自然可以按单纯形法从头计算，但这样既麻烦又没有必要。因为一个或几个参数的变化，可能直接在变化前所求的最终单纯形表中反映出来，这就避免了从头计算，而可以从调整后的最终表入手，分析是否满足最优解的条件，如果不能满足，再从这个表开始进行迭代，求出参数变化后的最优解。 二、目标函数中变量系数 发生变化 例1： 在美佳公司的例子中，若家电Ⅰ的利润为1.5元/件，家电Ⅱ的利润为2元/件，美佳公司的最优生产计划有何变化？ 例2： 在美佳公司的例子中，若家电Ⅰ的利润不变，家电Ⅱ的利润在什么范围变化时，美佳公司的最优生产计划不变？ 例2： 在美佳公司的例子中，若家电Ⅰ的利润不变，家电Ⅱ的利润在什么范围变化时，美佳公司的最优生产计划不变？ 三、约束条件右边常数 的变化 四、约束条件中参数 发生变化 五、增加一个变量 例6： 在美佳公司的例子中，若考虑增加一个新型产品Ⅲ，生产一件该产品需设备A,B及调试工序的时间分别为3、4、2小时，该产品的预期盈利为3元/件，问该产品是否值得投产；若投产，最优生产计划如何变化？