线性对偶与灵敏度分析

1、2.3.1 线性规划的对偶问题对偶问题的含义线性规划对偶问题的基本性质对偶变量的经济含义-影子价格（shadow price）2.3.2 灵敏度分析资源向量b的分量 变化的分析价格系数 变化的分析追加新变量的分析约束矩阵A变化的分析2.3 对偶问题与灵敏度分析例：回顾例1现在换个角度讨论这个问题： 这时有另一家公司提出要购买其煤、电、油全部资源。该公司希望确定一组价格，一方面使工厂能接受这价格而同意出售资源，另一方面又使公司购买这些资源的总成本最低。试建立该公司的线性规划模型。一、对偶问题的含义由于购买方是理智的，会把购买这些资源的总成本压至最低。故购买的公司在满足上述二约束情况下，要使购买这

2、些资源的总成本最低（目标函数）为：约束一：工厂自己生产甲产品的利润必须不高于出售相关资源的收入：约束二：工厂自己生产乙产品的利润必须不高于出售相关资源的收入：对偶规划由于购买方是理智的，会把购买这些资源的总成本压至最低。故购买的公司在满足上述二约束情况下，要使购买这些资源的总成本最低（目标函数）为：对偶规划称（2）为（1）的对偶，也称（1）为（2）的对偶。任何一个线性规划问题都存在一个伴生的线性规划问题，我们称之为“对偶”。本节将讨论对偶问题模型的建立、影子价格及敏感性分析。约束一：工厂自己生产甲产品的利润必须不高于出售相关资源的收入：约束二：工厂自己生产乙产品的利润必须不高于出售相关资源的收

3、入：对偶模型的一般式（P）（D）这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系： 原问题（P） 对偶问题 （D） 目标max型 目标min型 有n个变量（非负） 有n个约束（大于等于） 有m个约束 （小于等于） 有m个变量（非负） 价格系数 资源向量 资源向量 价格系数 技术系数矩阵 技术系数矩阵的转置（1）对称形式对偶问题 原问题 对偶问题（2）原问题中有等式约束条件设等式约束条件的线性规划问题：先将等式约束条件分解为两个不等式约束：（2）原问题中有等式约束条件按对称形式写出其对偶问题：整理可得：更一般的，线性规划总可表示为( ):例2.14：写出下面线性规划的对

4、偶规划模型：解：首先将原问题改为规定形式，即为：二、对偶问题的基本性质（P）（D）考虑1 .对称性：对偶规划的对偶是原始规划。 这个性质说明，对偶关系是相互的，如果线性规划甲是乙的对偶，那么乙也是甲的对偶。等价写为： 根据定义,对偶规划为： 二、对偶问题的基本性质几何意义：CXYb2 .弱对偶性： 这个性质说明，对于一对对称形式的对偶规划而言，在可行解上，相应的极大化线性规划的目标函数值不会超过极小化线性规划的目标函数值。X0, YACY0, AXb二、对偶问题的基本性质4.无界性： 若原问题 （对偶问题）为无界解，则其对偶问题 （原问题）无可行解（逆命题不成立）。证：对（P）增加松弛变量Xs

5、，化为设其最优基为B，终表为其检验数为二、对偶问题的基本性质5.强对偶性： 若（P）有最优解，则（D）也有最优解， 且最优值相同。6.互补松弛定理： 在线性规划最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；另一方面，如果约束条件取严格不等式，则其对应的对偶变量一定为零。例2.15 已知线性规划问题问题：(1) 由性质5强对偶性可知，对偶问题最优解的表达式 Y* =？ (2) 求Y*是否有必要重新求解对偶规划（ D）？ 证：对（P）增加松弛变量Xs，化为设其最优基为B，终表为其检验数为二、对偶问题的基本性质5.强对偶性： 若（P）有最优解，则（D）也有最优解， 且最优值

6、相同。问题：(1) 由性质5强对偶性可知，对偶问题最优解的表达式 Y* =？ (2) 求Y*是否有必要重新求解（ D）？ 请指出其对偶问题的最优解和最优值。 CBB-1 不必。可以从原问题（P）的单纯形终表获得。例如，在前面的练习中已知的终表为3.对偶变量的经济含义影子价格（Shadow Price）CBB-1 对偶问题的最优解 买主的最低出价； 原问题资源的影子价格 当该资源增加1单 位时引起的总收入的增量卖主的内控价格。 例：（煤电油例）的单纯形终表:（1）请指出资源煤电油的影子价格，并解释其经济意义。表示煤、电、油的影子价格分别是0、1.36、0.52；其经济意义是当煤、电、油分别增加1

7、单位时可使总收入分别增加0 、1.36、0.52。影子价格在经营管理中的应用：影子价格可以告诉决策者，增加哪种资源对增加经济效益最有利。本例中，煤、电、油的影子价格分别是0、1.36、0.52，说明首先应考虑增加第二种资源“电”，因为相比之下它能使收益增加最多。影子价格可以告诉决策者，用多大的代价增加资源才合算。如第三种资源“油”每增加一个单位能使收益增加0.52，如果增加油的代价大于0.52就不划算了。告诉决策者应如何考虑新产品的价格。如果企业要生产一种新产品，每件新产品消耗三种资源分别为1,2,3个单位，则新产品的定价一定要大于才能增加公司的收益，如售价低于4.28，生产不划算。三、灵敏度

8、分析我们在求解线性规划时都把系数A，C，b作为确定元素考虑。实际上，这些系数往往是变化的。例如：市场条件变化会使价格系数C改变，技术革新会改变系数矩阵A。所谓灵敏度分析是分析系数A、b、C的变化对已得到的最优解有何影响。（如它们在何范围内变化时可使原最优解或最优基不变？）1. b变化时的分析在例1（煤电油例）中，其单纯形终表如下：（1）电资源b2在何范围内变化时不影响最优基？2. C变化时的分析在例1（煤电油例）中，其单纯形终表如下：（2）甲产品的价格在何范围内变化时，现最优解不变？在问题已求出最优解后又追加新的变量，（给定相应的价格系数和技术系数），分析最优解的变化。主要讨论增加新变量xn+1是否有利。经济意义是第n+1种新产品是否应当投产，数学意义是xn+