第二章 对偶理论与灵敏度分析《运筹学》课件.PPT

* * 例1 已知下述问题的最优解及最优单纯形表, * 最优单纯形表如下: 0 -1/8 -3/2 0 0 0 -1/8 1/2 1 0 2 3 1 1/2 -2 0 0 4 0 0 1/4 0 0 1 4 2 0 0 0 3 2 * 由最优单纯形表得: * * 不可行! 用对偶单纯形法计算 * -3/4 -1/2 0 0 0 1/4 0 0 1 0 3 x2 3 -1/2 -1/4 1 0 0 2 x3 0 0 1/4 0 0 1 4 x1 2 0 -1/8 -3/2 0 0 0 -1/8 1/2 1 0 2+2 3 1 1/2 -2 0 0 4-8 x5 0 0 1/4 0 0 1 4+0 x1 2 ?i x5 x4 x3 x2 x1 b XB CB 0 0 0 3 2 x2 3/4 － － － － [-2] * * 例2 求例1 ?c4的变化范围,使最优解不变. 0 -1/8 -3/2 0 0 0 -1/8 1/2 1 0 2 3 1 1/2 -2 0 0 4 x5 0 0 1/4 0 0 1 4 x1 2 ?i x5 x4 x3 x2 x1 b XB CB 0 0 0 3 2 x2 解: * 分析: * 方法: 例3 求例1 ?c2的变化范围,使最优解不变. 0 -1/8 -3/2 0 0 0 -1/8 1/2 1 0 2 3 1 1/2 -2 0 0 4 x5 0 0 1/4 0 0 1 4 x1 2 ?i x5 x4 x3 x2 x1 b XB CB 0 0 0 3 2 x2 * 解: 0 -1/8 -3/2 0 0 0 -1/8 1/2 1 0 2 3 1 1/2 -2 0 0 4 x5 0 0 1/4 0 0 1 4 x1 2 ?i x5 x4 x3 x2 x1 b XB CB 0 0 0 3 2 x2 * * 分析: * * 例4 求例1 ?a24的变化范围,使最优解不变. 解: * 例5 在例1的基础上，企业要增加一个 新产品Ⅲ,每件产品需2个台时，原材料A 6kg， 原材料B 3kg，利润 5元/件，问如何安排各产 品的产量，使利润最大？ 解： 5 3 2 利润 12 3 4 0 料B 16 6 0 4 料A 8 2 2 1 设备 b Ⅲ Ⅱ Ⅰ * 表明生产新品有利。 * 5/4 0 -1/8 -3/2 0 0 1/4 0 -1/8 1/2 1 0 2 3 2 1 1/2 -2 0 0 4 x5 0 3/2 0 1/4 0 0 1 4 x1 2 x5 x4 x3 x2 x1 b XB CB 5 0 0 0 3 2 x2 ?i x’3 * 5/4 0 -1/8 -3/2 0 0 1/4 0 -1/8 1/2 1 0 2 3 2 1 1/2 -2 0 0 4 x5 0 3/2 0 1/4 0 0 1 4 x1 2 x5 x4 x3 x2 x1 b XB CB 5 0 0 0 3 2 x2 8/3 4/2 8 ?i x’3 [2] 0 -5/8 -7/16 -1/4 0 0 0 -1/8 -3/16 3/4 1 0 3/2 3 1 1/2 1/4 -1 0 0 2 0 -3/4 -1/8 3/2 0 1 1 x1 2 x5 x4 x3 x2 x1 b XB CB 5 0 0 0 3 2 x2 ?i x’3 x’3 5 * 小结 1、对偶问题及其化法 ※原问题决策变量决定对偶问题约束条件关系 ※原问题约束条件决定对偶问题决策变量取值方向。 * 2、检验数的计算方法 * 3、对偶问题的性质 4、对偶单纯形法 ●弱对偶性 ●无界性 ●最优性 ●松弛性 ●检验数与对偶问题的解 * 5、灵敏度分析 * * 第二章 对偶理论与灵敏度分析 §1 单纯形法的矩阵描述 设max z = CX AX = b X ≥ 0 A为m×n阶矩阵 RankA=m ,取B为可行基, N为非基， * * * 求解步骤： * 3 2 利润 12kg 4 0 材料B 16kg 0 4 材料A 8台时 2 1 设备台时 限制 Ⅱ Ⅰ §2 对偶问题的提出 [eg.1]制定生产计划 M1: max z = 2x1 + 3x2 1x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1，x2 ≥ 0 * 现在出租，设y1为设备单位台时的租金