数据挖掘对偶理论与灵敏度分析.ppt

* 练习1： maxZ=-X1 -4X2 -3X4 X1+2X2 - X3 +X4 ? 3 -2X1 - X2 +4X3 +X4 ? 2 X1 … X4 ?0 * 最优解：X=(7,0,4,0)T Z= -7 -1 -4 0 -3 0 0 CB XB b X1 X2 X3 X4 X5 X6 0 X5 -3 (-1) -2 1 -1 1 0 0 X6 -2 2 1 -4 -1 0 1 0 σ　-1 -4 0 -3 0 0 -1 X1 3 1 2 -1 1 -1 0 0 X6 -8 0 -3 (-2) -3 2 1 - 3 σ　0 -2 -1 -2 -1 0 -1 X1 7 1 7/2 0 5/2 -2 -1/2 0 X3 4 0 3/2 1 3/2 -1 -1/2 -7　σ 0 -1/2 0 -1/2 -2 -1/2 * maxZ=-X1 -X2 2X1 -X2 ? 2 -X1 + 1/2X2 ? 1 X1 , X2 ?0 练习2： * 第五节 灵敏度分析 CBB-1b C - CBB-1 A B-1 b B-1 A 原始数据A，b，C A=(P1 P2 … Pn ) aij ,bj, cj 一、灵敏度分析的概念 对系统或事物（线性规划问题）因周围条件的变化（如aij ,bj, cj 的变化）显示出来的敏感程度的分析。 * (1) 参数A，b，C在什么范围内变动，对当前方案无影响？ (2) 参数A，b，C中的一个(几个)变动，对当前方案影响？ (3) 如果最优方案改变，如何用简便方法求新方案？ 二、灵敏度分析所解决的问题 * 原问题 对偶问题 结论或继续计算的步骤 可行解 可行解 问题的最优解或最优基不变 可行解 非可行解 用单纯形法继续迭代求最优解 非可行解 可行解 用对偶单纯形法继续迭代求最优解 非可行解 非可行解 引进人工变量，编制新的单纯形表重新计算 * 一、分析 cj 的变化 cj 的变化首先影响检验数 ① XB= B-1b ② σA = C - CBB-1 A = C - Y A σN = CN - CBB-1 N = CN - Y N σj = Cj - CBB-1 Pj = Cj - Y Pj * maxZ=2X1 +X2 5X2 + X3 =15 6X1 +2X2 + X4 =24 X1 + X2 + X5 =5 Xj ?0 设备A 设备B 调试工序 * CB XB b x1 x2 x3 x4 x5 θ 2 1 0 0 0 0 x3 15/2 0 0 1 5/4 -15/2 2 x1 7/2 1 0 0 1/4 -1/2 1 x2 3/2 0 1 0 -1/4 3/2 σ 0 0 0 -1/4 -1/2 1.若家电1的利润降至1.5元/件，而家电2的利润增至2元/件时，美佳公司最优生产计划有何变化？ * 2.若家电1的利润不变，则家电2的利润在什么范围内变化时则该公司的最优生产计划将不发生变化。 CB XB b x1 x2 x3 x4 x5 θ 2 1+λ 0 0 0 0 x3 15/2 0 0 1 5/4 -15/2 2 x1 7/2 1 0 0 1/4 -1/2 1+λ x2 3/2 0 1 0 -1/4 3/2 σ 0 0 0 -1/4+ 1/4 λ -1/2- 3/2 λ * -1/4+1/4 λ≤0 -1/2- 3/2 λ≤0 - 1/3 ≤λ≤1 2/3 ≤c2≤2 * 二、分析 bi的变化 bi 的变化首先影响XB=