第三章 灵敏度分析.ppt

2020 1 30 1 第三章灵敏度分析 前提条件 原线性规划问题已取得了最优解 每次只讨论一种参数的变化 而参数之间的变化互不关联 2020 1 30 2 某厂准备用甲乙两种原料生产A B C D四种产品 相关参数见表 问如何安排生产总利润为最大 Maxz 9x1 8x2 50 x3 19x4s t 3x1 2x2 10 x3 4x4 182x3 1 2x4 3xj 0 j 1 2 3 4 Maxz 9x1 8x2 50 x3 19x4s t 3x1 2x2 10 x3 4x4 x5 182x3 1 2x4 x6 3xj 0 j 1 2 6 2020 1 30 3 用单纯形法对该线性规划进行求解 得初始单纯行表和最优单纯形表 Z 88 y1 y2 y3 y4 y5 y6 2020 1 30 4 一 目标函数中cj发生变化1 非基变量的cj发生变化x1的利润值由9变为9 c1则 1 9 c1 2 19 25 4 c1如果 1 4 c1 0 最优解不发生变化 1 4 c1 0 最优解将发生变化 所以当 c1 4时 最优解不发生变化 对于某一非基变量可以看出 它的价值系数发生变化时 只影响最优单纯行表中该非基变量的检验数 而基变量的检验数都不会发生变化 所以只需要考虑该非基变量的价值系数变化后的检验数是否仍然小于等于0 如果仍然小于等于0 则最优解不发生变化 2020 1 30 5 思考 如果x2的系数发生变化 c2在什么范围内变化 最优解不变 2020 1 30 6 2 基变量的cj发生变化假设x4的利润由19变为19 c4 4 2 c4 2 3 4 3 c4 13 3 2 3 c4 10 3 10 3 c4 当且仅当所有的非基变量的检验数都仍然小于等于0则最优解不变 2020 1 30 7 当目标函数中cj发生变化 将影响最终单纯形表非基变量的检验数 如果是非基变量的价值系数发生变化 只影响该非基变量的检验数 如果变化后的检验数仍然小于等于0 则最优解不变 如果是基变量的价值系数发生变化 将影响所有非基变量的检验数 只有当所有的非基变量检验数都仍然小于等于0 最优解才不变 2020 1 30 8 二 右端常数项bi发生变化X XB 0 T其中XB B 1bZ CBB 1b当bi发生变化时 bi b 0 bi 0 T b b则 XB B 1b B 1 b b B 1b B 1 b XB B 1 b如果XB XB B 1 b 0 则原最终单纯形表中的基变量不变 基变量的值将发生变化如果XB XB B 1 b 0 则需采用对偶单纯形表进行重新求解 2020 1 30 9 假设 甲原材料的供给量从18变为6 则b 6 3 T 可以看出甲的供给量发生变化后 x4的值 4 0 所以用对偶单纯形表求新解 2020 1 30 10 2020 1 30 11 2020 1 30 12 2020 1 30 13 2020 1 30 14 2020 1 30 15 当右端常数项发生变化时 主要考虑在最优单纯行表中基变量的值是否仍然大于等于0 如果仍然大于等于0 则线性规划问题的基变量不变 但是基变量的值将发生变化 如果右端常数项发生变化时 最优单纯行表中基变量的值小于0 则将用对偶单纯形法对原最优单纯形表进行继续求解 2020 1 30 16 三 增加一个变量假设用甲乙两种原材料还可以生产新产品为E 需要甲原料3个单位 乙原料1个单位 利润为10 问该种新产品是否应该生产 设生产E产品x7个 则线性规划方程为 Maxz 9x1 8x2 50 x3 19x4 10 x7s t 3x1 2x2 10 x3 4x4 3x7 182x3 1 2x4 x7 3xj 0 j 1 2 3 4 7 Maxz 9x1 8x2 50 x3 19x4 10 x7s t 3x1 2x2 10 x3 4x4 3x7 x5 182x3 1 2x4 x7 x6 3xj 0 j 1 2 7 2020 1 30 17 P7 3 1 T 7 c7 CBP7 10 19 50 13 4 5 6 T 19 3 0 因为x7的检验数小于0 所以原最优单纯形表即为最优单纯形表 最优解不变 考虑影子价格 y1 13 3 y2 10 3则生产一件E产品所需要的隐含成本为 13 3 3 10 3 1 49 3 10 每件E产品的利润 所以也不生产 2020 1 30 18 增加一个变量也就是多生产一种产品 只须考虑该种产品的检验数是否大于0 如果大于0则表示应该生产 用单纯形表进行求解 如果小于0则该种产品不用生产 最优解不发生变化 同时也可以考虑影子价格 如果该种新产品的利润大于隐含成本 则应该生产用单纯形表进行求解 如果小于隐含成本则该种产品不用生产 2020 1 30 19 四 增加一个约束条件假设原线性规划问题变为 Maxz 9x1 8x2 50 x3 19x4s t 3x1 2x2 10 x3 4x4 182x3 1 2x4 32x1 x2 x3 2x4 8xj 0 j 1 2 3 4 Maxz 9x1 8x2 50 x3 19x4s t 3x1 2x2 10 x3 4x4 x5 182x3 1 2x4 x6 32x1 x2 x3 2x4 x7 8xj 0 j 1 2 7 2020 1 30 20 2020 1 30 21 此时x7的值 3大于0 所以原问题和对偶问题都达到可行解 并分别为最优解 不需要进行下一步计算 2020 1 30 22 增加一个约束条件 可能影响的只是该约束条件的松弛变量的值 如果该松弛变量的值大于等于0 则线性规划最优解不变 如果该松弛变量的值小于0 则采用对偶单纯形表进行计算 2020 1 30 23 五 aij发生变化 Maxz 9x1 8x2 50 x3 19x4s t 3x1 2x2 10 x3 4x4 182x3 1 2x4 3xj 0 j 1 2 3 4 3x1 x2 10 x3 4x4 18 则P2 2 0 T P2 1 0 T 2 c2 CBP2 8 19 50 2 3 1 6 T 11 3 0 2020 1 30 24 2020 1 30 25 2020 1 30 26 2020 1 30 27 改变aij只会