运筹学--对偶问题及灵敏度分析.pptVIP

-3 -2 -1 0 0 0 XB b X1 X2 X3 X4 X5 X6 X4 X5 X6 -6 -4 -3 -1 -1 0 -1 0 -1 -1 1 1 1 0 0 0 1 0 0 0 1 -Z’ 0 -3 -2 -1 0 0 0 -3 -2 -1 0 0 0 XB b X1 X2 X3 X4 X5 X6 X3 X5 X6 6 -10 -9 1 -2 -1 1 -1 -2 1 0 0 -1 1 1 0 1 0 0 0 1 -Z’ 6 -2 -1 0 -1 0 0 第五节 对偶单纯形法 XB b X1 X2 X3 X4 X5 X6 X4 X1 X2 1 4 3 0 1 0 0 0 1 -3 -1 -1 1 0 0 -1 -1 0 -1 0 -1 -Z’ 18 0 0 -6 0 -3 -2 则最终单纯形表为： …… 得到最优解为： 第五节 对偶单纯形法 对偶单纯法优点： 初始解可是非可行解，只要满足σj≤0时即可，不需要加入人工变量。 当变量多于约束条件时，用对偶单纯形法计算可减少计算工作量。例如有2个约条件4个变量的情况下，用一般单纯形最多需要迭代多少？而用对偶单纯形则最多只需要多少次？ 主要缺点： 难以单独使用 为什么还要学习对偶单纯形？ 第五节 对偶单纯形法 第六节 线性规划问题的灵敏度分析 一、灵敏度分析的基本概念和基本原理 灵敏度分析是指系数及常数项的变化对最优解的影响，有时也讨论新产品是否投产等生产计划问题。 以标准线性规划问题为例： 第六节 线性规划问题的灵敏度分析 则Ｂ为最优基的条件是： 当某系数（常数）发生变化，若能继续满足可行性条件和正则性条件，则最优基不变；如果不满足某一个条件，可选择单纯形法或对偶单纯形法继续迭代。 二、资源数量b变化的灵敏度分析 资源数量变化不影响正则性条件，只影响可行性条件，因此若能继续保持 则，最优基不发生变化，但决策变量的取值一般会改变。 第六节 线性规划问题的灵敏度分析 设原资源数量为： 现第r种资源发生变化，变化后资源的数量为： 资源变化后的可行性条件将变化为： 另外，资源数量在什么范围内变化，而最优基不变呢？ 第六节 线性规划问题的灵敏度分析 第六节 线性规划问题的灵敏度分析 例7 分析下列线性规划问题(p31) 第六节 线性规划问题的灵敏度分析 则最终单纯形表为： 2 3 0 0 0 XB b X1 X2 X3 X4 X5 X1 X5 X2 4 4 2 1 0 0 0 0 1 0 -2 1/2 1/4 1/2 -1/8 0 1 0 -Z -14 0 0 -3/2 -1/8 0 ①最优基的逆矩阵是什么？ ②讨论第二种资源的变化范围 第六节 线性规划问题的灵敏度分析 ③第一种资源有４个单位的增量，最优解如何变化？ 三、目标函数系数C变化的灵敏度分析 目标函数系数的变化不影响可行性条件，只影响正则性条件（检验数），正则性条件（检验数）可以表示为： 第六节 线性规划问题的灵敏度分析 非基变量和基变量目标函数系数的变化对检验数的影响是不同的。 1.非基变量目标函数系数变化的分析 这里得到了两个方面的结论：一是非基变量系数发生变化后，检验数的变化情况，因此可判断是否对最优解产生影响；二是可确定最优解不变时，非基变量系数变化范围，即 第六节 线性规划问题的灵敏度分析 2.基变量目标函数系数变化的分析 为保持原最优解，则： 第六节 线性规划问题的灵敏度分析 2 3 0 0 0 XB b X1 X2 X3 X4 X5 X1 X5 X2 4 4 2 1 0 0 0 0 1 0 -2 1/2 1/4 1/2 -1/8 0 1 0 -Z -14 0 0 -3/2 -1/8 0 仍以上例： 第六节 线性规划问题的灵敏度分析 四、约束条件变化的灵敏度分析 1.增加新约束条件分析的方法 就是判断最优解能否满足新的约束条件。 满足：仍为最优解（可能可行域减小） 不满足：增加该约束条件，用对偶单纯形法迭代。 2.原某个约束条件的改变 原某个约束条件的资源是否有剩余？ 有剩余，说明原某个约束条件为非严格等式 无剩余，严格等式 结合改变后的约束条件和原最优解进行分析。 第六节 线性规划问题的灵敏度分析 例8 约束条件变化的灵敏度分析 -5 5 13 0 0 XB b X1 X2 X3 X4 X5 X4 X5 20 90 -1 12 1 4 3 10 1 0 0 1 -Z 0 -5 5 13 0 0 X2 X5 20 10 -1 16