[第二章--线性规划的对偶理论与灵敏度分析--运筹学.ppt

运筹学基础 例一 例一 一、线性规划的对偶问题 一、线性规划的对偶问题 对偶规则 —— 变量、约束与系数 对偶规则—— 变量与约束对应关系 对偶问题性质证明的几个重要内容 对偶问题性质证明的几个重要内容 对偶问题的基本性质（对称形） 影子价格 影子价格 对偶单纯形法 二、灵敏度分析 2、分析bj的变化 右端项bi的变化在实际问题中反映为可用资源数量的变化。bi变化反映到最终单纯形表上将引起b列数字的变化，在表2-9中可能出现第一或第三的两种情况。出现第一种情况时，问题的最优基不变，变化后的b列值为最优解。出现第三种情况时，用对偶单纯形法迭代继续找出最优解。 下面举例说明： 例：在上述美佳公司例子中，(1)若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化；(2)若设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 二、灵敏度分析 解 (1)因有 ，则： 将其反映到最终单纯形表中得表如下。由于该表中原问题为非可行解，故用对偶单纯形法继续计算，其结果如下量表所示： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 二、灵敏度分析 cj CB 0 2 1 cj-zj 基 x3 x1 x2 b 35/2 11/2 -1/2 2 x1 0 1 0 0 1 x2 0 0 1 0 0 x3 1 0 0 0 0 x4 5/4 1/4 [-1/4] -1/4 0 x5 -15/2 -1/2 3/2 -1/2 对偶单纯形法处理后结果： cj CB 0 2 0 cj-zj 基 x3 x1 x4 b 15 5 2 2 x1 0 1 0 0 1 x2 5 1 -4 -1 0 x3 1 0 0 0 0 x4 0 0 1 0 0 x5 0 1 -6 -2 由此美佳公司的最优计划改变为只生产5件家电I。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 二、灵敏度分析 (2)设调式工序每天可用能力为(5+m)h，因有 将其反映到最终单纯形表中，其b列数字为： 当b=0时问题的最优基不变，解得-1=m=1。由此调试工序的能力应在4h-6h之间。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * * 清华大学出版社 《运筹学教程》（第二版） 胡运权 主编 教材 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如下表所示。问该公司应制造Ⅰ、Ⅱ两种家电备多少件．使获取的利润为最大。 设： x1—— A产品的生产量 x2—— B产品的生产量 利润 max z= 2 x1 + x2 约束条件 5x2 　≤ 15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1，x2 ≥ 0 st . Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 5x2 　 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 = 5 x1，x2 ，x3 ，x4 ，x5 ≥ 0 约束条件 st . 利润 max z= 2 x1