第四章 灵敏度分析

第四章灵敏度分析引导案例4.1灵敏度分析概述4.2灵敏度分析4.3软件求解与分析引导案例王飞在2003年开了一家火腿生产厂，今年效益一直不错。主要生产的火腿包括普通火腿肠、鱼肉肠、清真肠、精制火腿、香菇火腿、牛肉火腿等品种。但近年来，市场上猪肉价格波动较大，普通猪肉价格从去年的10元一公斤涨到了18元一公斤。王飞感到原来企业的生产方案可能已经不是最好的方案了，必须根据当前的市场状况对企业原来的生产计划进行调整。王飞想知道，如何组合其生产方案才能在当前的市场状况下达到企业的最佳效益，当猪肉价格达到多高时其新的生产组合就需要再进行调整。4.1灵敏度分析概述Maxf=CXAX=bX0系数矩阵A、约束条件右端项b和价值系数C给定以后，这个线性规划问题就确定了。例产品资源ABC资源拥有量原料甲11112kg原料乙12220kg利润（元/kg）586数学模型max,,fxxxxxxxxxxxx5861222200123123123123设产品A、B、C的产量分别为x1、x2、x3，则该问题的数学模型为：（1）当这些系数中的一个或几个发生变化时，已求得的最优解会有什么变化；（2）这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变；（3）若最优解变化，如何用最简便的方法找到新的最优解。为了回答这些问题，可以在变化了的条件下重新求解线性规划问题。但是这样做太麻烦，也不必要。本节的目的是讲，如何在已经得到的最优解的基础上，进行适当的修改计算，即可回答上面的问题。这就是灵敏度分析的基本内容。1.灵敏度分析的定义灵敏度分析就是研究cj、bi、aij等参数在什么范围内变化时最优解不变，若最优解发生变化，如何用简便的方法求出新的最优解。线性规划中用到的数据很多，决策者既希望知道个别数据变化的影响，还希望知道几个数据同时发生变化所产生的影响。因此灵敏度分析的范围是相当广的，这里只讨论个别数据变化的灵敏度分析。2.灵敏度分析的主要内容价值系数cj的变化的分析约束条件右端项bi变化的分析系数矩阵A变化的分析系数列向量Pk变化的分析（产品的工艺系数发生变化）增加新约束条件的分析增加新变量的分析（增加一种新产品）3.灵敏度分析的步骤（1）将参数的改变计算反应到最终单纯形表上来。具体计算方法是：按下列公式计算出参数aij、bi、cj的变化而引起的最终单纯形表上有关数字的变化：（2）检查原问题是否仍为可行解。（3）检查对偶问题是否仍为可行解。（4）按下表所列情况得出结论和决定继续计算的步骤。bBXB1jjPBP1'ABCCB1表4-1结论和步骤原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算1.价值系数cj变化•cj变动可能由于市场价格的波动，或生产成本的变动。•cj的变化仅仅影响到检验数j（即cj-zj）的变化。•cj的变化会引起检验数的变化，有两种情况：–非基变量对应的价值系数变化，不影响其它检验数–基变量对应的价值系数变化，影响所有非基变量检验数4.2灵敏度分析例1产品资源ABC资源拥有量原料甲11112kg原料乙12220kg利润（元/kg）586数学模型max,,fxxxxxxxxxxxx5861222200123123123123设产品A、B、C的产量分别为x1、x2、x3，则该问题的数学模型为：Cj58600CBXBB-1bX1X2X3X4X500X4X512201112121001j=cj-zj058600初始单纯形表：Cj58600CBXBB-1bX1X2X3X4X558X1X2481001012-1-11j=cj-zj-8400-2-2-3最优单纯形表：非基变量对应的价值系数C3的变化在实例1中，分析产品丙的利润C3的变化对最优解的影响。由上表可知：当C3-8≤0，即0≤C3≤8时，最优解不变。3xCj58600CBXBB-1bX1X2X3X4X558X1X2481001012-1-11j=cj-zj-8400-2-2-3C3C3-8基变量X1对应价值系数C1变化(1)基变量对应的价值系数C1的变化由上表可知：当8-2C1≤0，同时C1-8≤0，即4≤C1≤8时，最优解不变。Cj58600CBXBB-1bX1X2X3X4X558X1X2481001012-1-11j=cj-zj-8400-2-2-3C1C1-28-2C1C1-8-(64+4C1)基变量X2对应的价值系数C2的变化由上表可知：当6-C2≤0，C2-10≤0，同时5-C2≤0，即6≤C2≤10时，最优解不变。Cj58600CBXBB-1bX1X2X3X4X558X1X2481001012-1-11j=cj-zj-8400-2-2-3C2C26-C2C2-105-C2-(20+8C2)价值系数cj变化的分析总结•cj的变化会引起检验数的变化，有两种情况：（1）非基变量对应的价值系数变化，不影响其它检验数（2）基变量对应的价值系数变化，影响所有非基变量检验数。要使原来的最优解不变，新的检验数均≤0例2:云天公司生产计划问题产品资源产品A产品B资源总量煤（吨）1230劳动日（天）3260仓库（m2）0224利润（千元）4050解：设产品A、B的产量分别为x1、x2，z表示总利润，则该问题的数学模型为：0,24260233025040max212212121xxxxxxxxxz用单纯形法求解结果:最优单纯形表XBB-1bx1x2x3x4x510-1/21/2000-3/21/21x1x5x215915/2013/4-1/40j0035/215/20初始单纯形表XBbx1x2x3x4x51210032010x3x4x530602402001j4050000最优生产方案：产品A生产15件，产品B生产15/2件,利润最大为975千元。三种资源的影子价格例2在云天公司的实例中:（1）若c1=20,c2=80,最优生产计划有何变化？（2）若c1不变,c2在什么范围内变化，该公司的最优生产计划将不发生变化？原问题最优单纯形表cj4050000CBXBB-1bx1x2x3x4x510-1/21/2000-3/21/2140050x1x5x215915/2013/4-1/40j0035/215/20解：把产品利润的变化直接反映到最优单纯形表中20208080-5010θ3018-[]单纯形迭代计算结果如下表：最优单纯形表cj2080000CBXBB-1bx1x2x3x4x520080x1x4x2618121010-100-31201001/2j00200-20新的最优生产方案为：产品A生产6件，产品B生产12件,利润最大为1080千元。（2）若c1不变,c2在什么范围内变化，该公司的最优生产计划将不发生变化？最优单纯形表cj4050000CBXBB-1bx1x2x3x4x510-1/21/2000-3/21/2140050x1x5x215915/2013/4-1/40j0035/215/20解：设产品B的利润为C2千元，将其反映到最优单纯形表中：为使最优解不变，应有：C2C220-3/4C2-20+C2/420-3/4C2≤0-20+C2/4≤0解得：80/3≤C2≤80产品B的利润的变化范围是：80/3≤c2≤80（2）若c1不变,c2在什么范围内变化，该公司的最优生产计划将不发生变化？最优单纯形表cj4050000CBXBB-1bx1x2x3x4x510-1/21/2000-3/21/2140050x1x5x215915/2013/4-1/40j0035/215/20解：设产品B的利润为（50+）千元，将其反映到最优单纯形表中：为使最优解不变，应有：50+50+-35/2-3/4-15/2+/4-35/2-3/4≤0-15/2+/4≤0解得：-70/3≤≤30产品B的利润c2=50+，故c2的变化范围是：80/3≤c2≤802.右端资源项bi变化•若b变化后的最优解XB’=B1b0,则最优基不变；否则，最优基改变，用对偶单纯形法迭代。•b的变化在实际问题中表明可用资源量发生变化。•由XB=B1b和=C-CBB-1A可知，b的变化只会影响最优解的改变，不会引起检验数的变化。Cj58600CBXBB-1bX1X2X3X4X500X4X512201112121001j=cj-zj058600初始单纯形表Cj58600CBXBB-1bX1X2X3X4X558X1X2481001012-1-11j=cj-zj-8400-2-2-3最优单纯形表例1：分析b1=16和b2=20时，最优基和最优解的变化16124-92当b1=16,b2=20时，最优基不变，最优解变为：x1=12，x2=4结论Cj58600CBXBB-1bX1X2X3X4X500X4X512201112121001j=cj-zj058600初始单纯形表Cj58600CBXBB-1bX1X2X3X4X558X1X2481001012-1-11j=cj-zj-8400-2-2-3最优单纯形表例1：分析b1=22和b2=20时，最优基和最优解的变化2224-2-104Cj58600CBXBB-1bX1X2X3X4X558X1X224-21001012-1-11j=cj-zj-10400-2-2-3Cj58600CBXBB-1bX1X2X3X4X550X1X4202102-12-1011-1j=cj-zj-1000-2-40-5用对偶单纯形方法求解当b1=22,b2=20时，最优基改变，最优解变为：x1=20，x4=2结论020202201112'1111bbbbB解之得：10≤b1≤20即:当10≤b1≤20时，最优基不变保持b2=20,分析b1在什么范围内变化时，最优基不变?Cj58600CBXBB-1bX1X2X3X4X500X4X512201112121001j=cj-zj058600初始单纯形表Cj58600CBXBB-1bX1X2X3X4X558X1X2481001012-1-11j=cj-zj-8400-2-2-3最优单纯形表b12b1-20-b1+20?01224121112'2221bbbbB解之得：12≤b2≤24即:当12≤b2≤24时，最优基不变保持b1=12,分析b2在什么范围内变化时，最优基不变?Cj58600CBXBB-1bX1X2X3X4X500X4X512201112121001j=cj-zj058600初始单纯形表Cj58600CBXBB-1bX1X2X3X4X558X1X2481001012-1-11j=cj-zj-8400-2-2-3最优单纯形表b224-b2-12+b2?练习0,,652325max32123211321321xxxbxxxbxxxxxxf最优单纯形表为：求：（1）b1、b2的值；（2）对偶问题的最优解；（3）表中f、g、h、d、e的值；（4）在不破坏最优基的情况下，能否单独增加b1、b2来增加目标函数f的值，最多能增加到多少？Cj52300CBXBB-1bX1X2X3X4X550X1X5301010fg2-81-101j=cj-zj-1500h-7de例2在云天公司的实例中:（1）若b1=40，试分析公司最优计划的变化。（2）b1在什么范围内变化时，问题的最优基不变？246040b04/14/312/12/302/12/11B