§1单纯形表的灵款度分析 约束方程中常数项的灵敏度分析 迭代次数基变量 C XI X2 SI S2 b 50100000 5( 0 10 50 0 0 0 2 50 X 100 0 00 250 Z 501005005027500 0 0 500-50 从上表我们可以发现各个松弛变量的值,正好等于相应变量的对偶价格。在最 优解中S2=50是基变量,即为,原料A有50千克没用完,再增加A原料是不会增 加利润的,A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的 对偶价格为0;换句话说就是松弛变量的zj值等于对应的约束条件的对偶价格 运筹
管 理 运 筹 学 11 §1 单纯形表的灵敏度分析 二、约束方程中常数项的灵敏度分析 从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最 优解中S2 =50是基变量，即为，原料A有50千克没用完，再增加A原料是不会增 加利润的， A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的 对偶价格为0;换句话说就是松弛变量的Zj值等于对应的约束条件的对偶价格。 迭代次数 基变量 CB X1 X2 S1 S2 S3 b 50 100 0 0 0 2 X1 50 1 0 1 0 -1 50 S2 0 0 0 -2 1 1 50 X2 100 0 1 0 0 1 250 ZJ 50 100 50 0 50 27500 CJ -ZJ 0 0 -50 0 -50
§1单纯形表的灵敏度分析 可以看出,上题中对于设备台时数约束来说,当其松弛变量在目标函数 中从0变到Z3=50时,也就是只要当前余下一台时数设备从不能获利变成获利 50元时,譬如有人愿意出50元买一个设备时,我们就不必为生产I、I产 而使用完所有的设备台时了,这说明了设备台时数的对偶价格就是Z3=50元。 对于含有大于等于号的约束条件,添加剩余变量化为标准型。这时 这个约束条件的对偶价格就和这个剩余变量的z有关了。这将使得最优目 标值特别“恶化”而不是改进,故这时约束条件的对偶价格应取z值的相反 数 对于含有等于号的约束条件,其约束条件的对偶价格就和该约束方 程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变 量的2值 管理蓦 12
管 理 运 筹 学 12 §1 单纯形表的灵敏度分析 可以看出，上题中对于设备台时数约束来说，当其松弛变量在目标函数 中从0变到Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利 50元时，譬如有人愿意出50元买一个设备时，我们就不必为生产Ι、П产品 而使用完所有的设备台时了，这说明了设备台时数的对偶价格就是Z3=50元。 对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时 这个约束条件的对偶价格就和这个剩余变量的 有关了。这将使得最优目 标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取 值的相反 数- 。 对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方 程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变 量的 值。 j z j z j z j z
§1单纯形表的灵款度分析 下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值 约束条件 影子价格的取值 等于这个约束条件对应的松弛变量的与值,即为O的相反数 等于这个约束条件对应的剩余变量的2;值,即为的相反数 等于这个约束条件对应的人工变量的2值,即为可的相反数 从对偶价格的定义,可以知道当对偶价格为正时它将改进目标函数的值,当对 偶价格为负时它将使得目标函数朝着与最优化相反的方向前进。 下面我们研究当右端项b发生变化时,在什么范围内其对偶价格不变。由于b 的变化并不影响系数矩阵的迭代,故其最终单纯形表中的系数矩阵没有变化。由 此可见当b变化时,要使原来的基不变得到的基本可行解仍然是可行解,也就是所 求的基变量的值一定要大于0。所谓使其对偶价格不变的b的变化范围,也就是使 其最优解的所有基变量不变,且所得的最优解仍然是可行的b的变化范围 管理蓦 13
管 理 运 筹 学 13 下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值。 从对偶价格的定义,可以知道当对偶价格为正时它将改进目标函数的值，当对 偶价格为负时它将使得目标函数朝着与最优化相反的方向前进。 下面我们研究当右端项bj发生变化时，在什么范围内其对偶价格不变。由于bj 的变化并不影响系数矩阵的迭代，故其最终单纯形表中的系数矩阵没有变化。由 此可见当bj变化时，要使原来的基不变得到的基本可行解仍然是可行解，也就是所 求的基变量的值一定要大于0。所谓使其对偶价格不变的bj的变化范围，也就是使 其最优解的所有基变量不变，且所得的最优解仍然是可行的bj的变化范围。 约束条件 影子价格的取值 ≤ 等于这个约束条件对应的松弛变量的 值,即为 的相反数 ≥ 等于这个约束条件对应的剩余变量的 值,即为 的相反数 = 等于这个约束条件对应的人工变量的 值,即为 的相反数 j z j z j z j j j §1 单纯形表的灵敏度分析
§1单纯形表的灵款度分析 当b中的第k项bk变成b+△b时,也就是原来的初始单 纯形表中的b向量变成了b向量 00 令△b 4b圆则有b=b+△b 管理蓦
管 理 运 筹 学 14 §1 单纯形表的灵敏度分析 当bj中的第k项bK 变成 时，也就是原来的初始单 纯形表中的b向量变成了b’向量 b b b bk = + = ' 0 ... ... 0 0 令 b 则有bk + bk
§1单纯形表的灵敏度分析 这样在最终单纯形表中基变量X的解就变成了 XB=B1(b+△b)=Bb+B1·Ab。 如要使X成为可行解,只要使上述等式的右边>0,就可求出 Δb,的取值范围,也就是使得第K个约東条件的对偶价格不变的 b的变化范围 △b1 k lk k 2k 2k 则BAb=△bk*d3k △bk*d'mk △b,*d", lk 新的最优解为Xp有XB XBn(△b*dnk 运筹 15
管 理 运 筹 学 15 §1 单纯形表的灵敏度分析 这样在最终单纯形表中基变量XB的解就变成了 如要使XB成为可行解，只要使上述等式的右边>0，就可求出 的取值范围，也就是使得第K个约束条件的对偶价格不变的 bk的变化范围。 ， -1 -1 -1 X' B .(b b) B b B b B = + = + 。 k b = = k mk k 3 k k 2 k k 1 k 2 -1 1 k b d' ... b d' b d' b d' , B b ' ... ' ' D 则 mk k k d d d + = k mk k 2 k k 1 k 2 1 B B b d' ... b d' b d' ... X' X' B m B B X X X 新的最优解为 有