《运筹学PPT 第二章第三节对偶与灵敏度分析.pptVIP

第三节 对偶问题与灵敏度分析 一、对偶问题及其模型 例7：回顾例1 这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。 例7称为例1的对偶问题，记为（D），例1称为例7的原问题,记为（P）。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 对偶模型的一般式 以例7为例，原问题为 （P） （D） 这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系： 原问题（P） 对偶问题 （D） 目标max型 目标min型 有n个变量（非负） 有n个约束（大于等于） 有m个约束 （小于等于） 有m个变量（非负） 价格系数 资源向量 资源向量 价格系数 技术系数矩阵 技术系数矩阵的转置 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 此外，还有一种情形 原问题（P） 对偶问题 （D） 第j个变量为自由变量 第j个约束为等式约束 第i个约束为等式约束 第i个变量为自由变量 例8：写出下面线性规划的对偶规划模型： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例8：写出下面线性规划的对偶规划模型： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 二、对偶的性质 （P） （D） 考虑 1 .对称性 （P）与（D）互为对偶。 4.对偶定理 若（P）有最优解，则（D）也有最优解，  且最优值相同。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 问题：(1) 由性质4可知，对偶问题最优解的表达式 Y* =？ (2) 求Y*是否有必要重新求解（ D）？ —— CBB-1 —— 不必。可以从原问题（P）的单纯形终表获得。 例如，在前面的练习中已知 的终表为 请指出其对偶问题的最优解和最优值。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 5. 对偶问题的经济解释（1）对偶最优解的经济解释——资源的影子价格（Shadow Price） CBB-1 —— 对偶问题的最优解 —— 买主的最低出价； —— 原问题资源的影子价格 —— 当该资源增加1单 位时引起的总收入的增量——卖主的内控价格。 例10：例1（煤电油例）的单纯形终表如下： （1）请指出资源煤电油的影子价格，并解释其经济意义。 （2）由单纯形终表还可得到哪些有用的信息？ Evaluation only. Created with Aspose.Sl