运筹学08-对偶理论与灵敏度分析III-11.pptVIP

第8讲 对偶理论与灵敏度分析III School of Business ECUST 灵敏度分析 在以前讲的线性规划问题中，aij, bi, cj均为已知常数，但实际上这些数往往是一些估计和预测的数字，如随市场条件变化，cj的值就会变化；aij也会随工艺条件的改变而改变，bi是各项资源的投入数量，随着企业资金水平的变化也会变化。 因此，就会提出以下问题：当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者这些参数在多大范围内变化时，问题的最优解不变。这就是灵敏度分析所要研究和解决的问题。 一、目标函数中价值系数cj 的变化分析 非基变量在目标函数中系数的灵敏度分析 基变量在目标函数中系数的灵敏度分析 目标函数中价值系数 cj 的变化会引起非基变量检验数的变化，从而影响最优性条件能否成立。 1. 若cj 是非基变量的系数 若cj 是非基变量的系数，则cj 的变化仅影响非基变量xj的检验数 ，设 ，则变化后，非基变量xj的检验数为： 若 成立， 则最优性条件保持不变，cj的改变不会对最优解产生影响。 School of Business ECUST 2. 若cr 是基变量的系数 若cr 是基变量xr的系数，即cr是CB的一个分量，因此cr 的变化即引起CB的变化，而在计算所有非基变量的检验数时，均要使用CB，所以cr 的变化可能影响多个非基变量的检验数。设 ，则变化后，任一非基变量xj的检验数为： B-1 要求原最优性不变，则必须满足 于是得到： 当 时，有 当 时，有 j为非基变量的下标 因此， 的允许变化范围是： 最优单纯形表系数矩阵中第r行第j列的元素 例1： 佳美公司计划制造Ⅰ、Ⅱ两种产品，已知各制造一个单位时分别占用的设备A、B的台时、调试时间、每天设备A、B 的台时、调试工序每天可用于这两种产品的能力及各售出一单位时的获利情况，如表，问应怎样组织生产才能使总利润最多。 设备A(h) 设备B(h) 调试工序(h) 利润(百元) Ⅰ Ⅱ 每天可用能力 资源 产品 0 5 6 2 1 1 2 1 15 24 5 (1) 如果产品Ⅰ的利润降至1.5百元/单位，而产品Ⅱ的利润增至2百元/单位时，最优生产计划有何变化； (2) 如果产品Ⅰ的利润不变，则产品Ⅱ的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化。 School of Business ECUST 解： 设 x1,x2 分别表示Ⅰ、Ⅱ两种产品的生产数量， max z = 2x1+x2 s.t. 5 x2 ≤15 6x1+2x2 ≤24 x1+ x2 ≤5 x1, x2 ≥0 max z = 2x1+x2+0x3+0x4 +0x5 s.t. 5 x2 +x3 =15 6x1+2x2 +x4 =24 x1+ x2 +x5 =5 x1, x2 , x3, x4 , x5 ≥0 用单纯形法求解得最终单纯形表 c cB xB x1 x2 x3 x4 x5 2 1 0 0 0 0 2 1 x3 x1 x2 检验数 0 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 15/2 7/2 3/2 -17/2 b 0 0 0 -1/4 -1/2 得最优解为： x*=(7/2,3/2,15/2,0,0)T zmax=8.5(百元) (1)若两产品利润均改变 3/2 2 3/2 2 1/8 -9/4 -33/4 5/4 4/5 1 -6 6 -1/5 1/5 0 0 1 0 2 3 -1/10 -3/2 -9 x*=(2,3,0,6,0)T x4 0 zmax= 9(百元) c cB xB x1 x2 x3 x4 x5 2 1 0 0 0 0 2 1 x3 x1 x2 检验数 0 0 1