资源描述：
《运筹学08-对偶理论与灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第8讲对偶理论与灵敏度分析IIISchoolofBusinessECUST灵敏度分析在以前讲的线性规划问题中，aij,bi,cj均为已知常数，但实际上这些数往往是一些估计和预测的数字，如随市场条件变化，cj的值就会变化；aij也会随工艺条件的改变而改变，bi是各项资源的投入数量，随着企业资金水平的变化也会变化。因此，就会提出以下问题：当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者这些参数在多大范围内变化时，问题的最优解不变。这就是灵敏度分析所要研究和解决的问题。一、目标函数中价值系数cj的变化
2、分析非基变量在目标函数中系数的灵敏度分析基变量在目标函数中系数的灵敏度分析目标函数中价值系数cj的变化会引起非基变量检验数的变化，从而影响最优性条件能否成立。1.若cj是非基变量的系数若cj是非基变量的系数，则cj的变化仅影响非基变量xj的检验数，设，则变化后，非基变量xj的检验数为：若成立，则最优性条件保持不变，cj的改变不会对最优解产生影响。SchoolofBusinessECUST2.若cr是基变量的系数若cr是基变量xr的系数，即cr是CB的一个分量，因此cr的变化即引起CB的变化，而在计算所有非基变量的
3、检验数时，均要使用CB，所以cr的变化可能影响多个非基变量的检验数。设，则变化后，任一非基变量xj的检验数为：B-1要求原最优性不变，则必须满足于是得到：当时，有当时，有j为非基变量的下标因此，的允许变化范围是：最优单纯形表系数矩阵中第r行第j列的元素例1：佳美公司计划制造Ⅰ、Ⅱ两种产品，已知各制造一个单位时分别占用的设备A、B的台时、调试时间、每天设备A、B的台时、调试工序每天可用于这两种产品的能力及各售出一单位时的获利情况，如表，问应怎样组织生产才能使总利润最多。设备A(h)设备B(h)调试工序(h)利润(百
4、元)ⅠⅡ每天可用能力资源产品0562112115245(1)如果产品Ⅰ的利润降至1.5百元/单位，而产品Ⅱ的利润增至2百元/单位时，最优生产计划有何变化；(2)如果产品Ⅰ的利润不变，则产品Ⅱ的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化。SchoolofBusinessECUST解：设x1,x2分别表示Ⅰ、Ⅱ两种产品的生产数量，maxz=2x1+x2s.t.5x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0maxz=2x1+x2+0x3+0x4+0x5s.t.5x2+x3=156x1+2x
5、2+x4=24x1+x2+x5=5x1,x2,x3,x4,x5≥0用单纯形法求解得最终单纯形表ccBxBx1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/27/23/2-17/2b000-1/4-1/2得最优解为：x*=(7/2,3/2,15/2,0,0)Tzmax=8.5(百元)(1)若两产品利润均改变3/223/221/8-9/4-33/45/44/51-66-1/51/5001023-1/10-3/2-9x*=(2,3,0,6,0)Tx
6、40zmax=9(百元)ccBxBx1x2x3x4x521000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/27/23/2-17/2b000-1/4-1/2(2)由直接计算,得:解得即产品Ⅱ的利润c2的变化满足:2/3≤c2≤2时,该公司的最优生产计划将不发生变化二、约束条件中资源数量bi的变化分析检验数B-1b-cBB-1bIB-1N0cN-cBB-1N由最终单纯形表可知，资源数量bi的变化，会影响到原最优解的可行性与目标函数值。设某个资源数量br变化为并假设原问
7、题的其他系数不变，则使最终单纯形表中原问题的解相应地变化为其中这时其中为B-1的第r列，要保持原最优基B不变，则必须当时，有当时，有因此的允许变化范围是：例2：在上述佳美公司的例子中：（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化；（2）若设备A和B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。解：(1)因设备B原每天的能力为24，所以有进一步有根据最终单纯形表，得：SchoolofBusinessECUSTccBxBx1x2x3x4x52
8、1000021x3x1x2检验数0015/4-15/21001/4-1/2010-1/43/215/27/23/2-17/2b000-1/4-1/2设备B每天的能力增加到32小时后，不再是可行解。此时，检验数不变，应用对偶单纯形法继续求解。厂商的最优生产计划改变为：仅生产5个单位Ⅰ产品。此时，利润z*=10ccBxBx1x2x3x4x521000021x3x1x2检验数0
