灵敏度分析

一、灵敏度分析概述对某一线性规划问题来说，一旦其约束条件系数矩阵A、约束条件的右端常数向量b和价值系数向量C给定以后，这个线性规划问题就确定了。反之，给定一个线性规划问题，就有确定的一组A、b、C与之对应。在此之前我们一直假定A、b、C中的元素均为常数，他们不发生变化。但实际上这些系数往往是通过估计、预测或人为决策得来的，不可能十分准确和一成不变。例如：市场条件一变，价值系数cj就会跟着变化；约束条件系数矩阵A中的元素aij往往随着工艺技术条件的改变而改变；b的元素bi随着资源使用量的变化而改变。这就是说，随着时间的推移或情况的改变，我们往往需要修改原来线性规划问题中的若干系数，从而使原来的线性规划问题有所改变。因此，就实际需要来说，单单把线性规划问题的最优解确定下来，还不能说问题已完全解决了。决策者还需要知道这样的问题：1.当这些系数中的一个或几个发生变化时，已求得的最优解会有什么变化；2.这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变；3.若最优解变化，如何用最简便的方法找到新的最优解。为了回答这些问题，可以在变化了的条件下重新求解线性规划问题。但是这样做太麻烦，也不必要。本节的目的是讲，如何在已经得到的最优解的基础上，进行适当的修改计算，即可回答上面的问题。这就是灵敏度分析的基本内容。二、灵敏度分析的定义灵敏度分析就是研究cj、bi、aij等参数在什么范围内变化时最优解不变，若最优解发生变化，如何用简便的方法求出新的最优解。线性规划中用到的数据很多，决策者既希望知道个别数据变化的影响，还希望知道几个数据同时发生变化所产生的影响。因此灵敏度分析的范围是相当广的，这里只讨论个别数据变化的灵敏度分析。三、灵敏度分析的内容价值系数cj的变化的分析约束条件右端项bi变化的分析系数矩阵A变化的分析系数列向量Pk变化的分析增加新约束条件的分析增加新变量的分析实例1产品资源ABC资源拥有量原料甲11112kg原料乙12220kg利润（元/kg）586实例1的数学模型max,,fxxxxxxxxxxxx5861222200123123123123设产品A、B、C的产量分别为x1、x2、x3，则该问题的数学模型为：用单纯形法求解结果最优单纯形表x1x2x3x4x5bix1100214x2011118f0022384初始单纯形表x1x2x3x4x5bix41111012x51220120f5860001.价值系数cj变化的分析•cj变动可能由于市场价格的波动，或生产成本的变动。•cj的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj允许的变动范围cj•cj的变化会引起检验数的变化，有两种情况：–非基变量对应的价值系数变化，不影响其它检验数–基变量对应的价值系数变化，影响所有非基变量检验数1.1非基变量对应的价值系数变化0jjc要保持，故有在实例1中，分析产品丙的利润变化对最优解的影响。x1x2x3x4x5bix1100214x2011118f0022384由上表可知：当⊿c3≤2，即0≤c3≤8时，最优解不变若非基变量xj对应的系数cj的变化量为⊿cj，新的判别数为jjcjjc1.2基变量对应价值系数变化•由于基变量对应的价值系数在CB中出现，因此它会影响所有非基变量的检验数•只有一个基变量的ck发生变化，变化量为ck2.约束条件右端项bi变化的分析(1)•设XB=B1b是最优解，则有XB=B1b0•b的变化不会影响检验数•b的变化量b可能导致原最优解变为非基可行解设b’=b+b为保证最优基不变，必须满足XB=B-1b’0在实例1中:1.分析b1=16和b1=22时，最优基和最优解的变化。2.分析b2=18和b2=24时，最优基和最优解的变化。解：由最优单纯形表可知：当b1=16时，11121B2016b412201611121bB最优单纯形表变为：x1x2x3x4x5B-1bx11002112x2011114f00223-92结论：当b1=16时，最优基不变，最优解变为：x1=12，x2=4x1x2x3x4x5B-1bx11002124x201111-2f00223-104当b1=22时2022b224202211121bB最优单纯形表x1x2x3x4x5B-1bx11220120x40-1-11-12-f0-2-40-5-100结论：当b1=22时，最优基改变，最优解变为：x1=20，x4=2x1x2x3x4x5B-1bx11002-114x2011-112-f00-2-2-3-86结论：当b2=18时，最优基不变，最优解变为：x1=14，x2=2当b2=18时，最优单纯形表为：x1x2x3x4x5B-1bx1122018x20-1-11-18-f00-2-2-3-104结论：当b2=24时，最优基不变，最优解变为：x1=8，x2=8当b2=24时，最优单纯形表为：2.约束条件右端项bi变化的分析(2)在实例1中:1.分析b1在什么范围内变化时，最优基不变。2.分析b2在什么范围内变化时，最优基不变。分析使最优基保持不变的b1的范围:020202201112'1111bbbbB解之得：10≤b1≤20即当10≤b1≤20时，最优基不变分析使最优基保持不变的b2的范围:01224121112'2221bbbbB解之得：12≤b2≤24即当12≤b2≤24时，最优基不变3.系数矩阵A变化的分析系数矩阵A变化的分析包括系数列向量Pk变化的分析增加新约束条件的分析增加新变量的分析3.1系数列向量Pk变化的分析在初始单纯形表上，变量xk的系数列向量Pk变为Pk’，经过迭代后，在最终单纯形表上，xk是非基变量。这时最终单纯形表上xk的系数列就变成B-1Pk’。新的判别数为''1kBkkPBCC若，原最优解不变；若，则最优解改变，继续迭代可以求出新的最优解。0'k0'k在实例1中，假设产品C的资源消耗量由变为，试分析最优解的变化情况。2112最优单纯形表x1x2x3x4x5B-1bx11032-14x201-1-118-f00-1-2-3-84所有的判别数都非正，故最优解不变。在上例中，假设产品C的资源消耗量由变为，试分析最优解的变化情况。2111最优单纯形表x1x2x3x4x5B-1bx11012-14x2010-118-f001-2-3-84x1x2x3x4x5B-1bx31012-14x2010-118-f-100-4-2-88经迭代，得到最优单纯形表如下：3.2增加新约束条件的分析1、将最优解代入新的约束条件，若满足，则最优解不变。2、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯形表，并变换为标准型。3、利用对偶单纯型法继续迭代–为什么可以利用对偶单纯形法?在实例1中，假设生产产品A、B、C需要增加原料丙。这种原料的总量为18kg，生产单位产品A、B、C需原料丙分别为1、2、2kg。在这种情况下，应对生产计划作怎样的调整？将原最优解x1=4，x2=8代入上式知，原最优解不满足该约束条件，因而原最优解不再是增加约束条件以后的最优解。1822321xxx18226321xxxx这个问题相当于在原问题的基础上增加约束条件在新的约束条件中引入松驰变量x6，则有将该条件填入最优单纯形表中：x1x2x3x4x5x6B-1bx11002-104x2011-1108x60000-11-2-f00-2-2-30-84x1x2x3x4x5x6B-1bx11002-104x2011-1108x612200118-f00-2-2-30-84将该单纯形表标准化：用对偶单纯形方法迭代一次得：x1x2x3x4x5x6B-1bx110020-16x2011-1016x500001-12-f00-2-20-3-78增加约束条件以后的最优解为：x1=6，x2=63.3增加新的决策变量的分析假如要增加一个新的决策变量xn+1，其对应的系数列向量为Pn+1，价值系数为cn+1。在原最优单纯形表中xn+1对应的检验数为1111nBnnpBCc若，则原最优解不变。从经济学的观点来看，增加该项活动（或产品）是不利的。01n若，则原来的最优解不再是最优解，表明增加该活动是有利的。n10这时把xn+1对应于原最优基B的系数列向量加入到原最优表中，并以xn+1作为换入变量按单纯形法进行迭代，即可得到新的最优解。11/1nnpBP在实例1中，如果该厂还计划生产一种新产品D，单位产品D需消耗原料甲2kg，原料乙1kg，获利8元。问生产产品D是否有利？设产品D的生产量为x6，已知c6=8，，CB=(58)126P11121B1312111261'6PBP17813858'666PCcB因，可知原最优解已不再是最优解，增加该产品是有利的。610为求得新的最优解，在原最优表上增加新的列，得下表：'6Px1x2x3x4x5x6bix11002134x20111118f00223184选x6为进基变量，x1为出基变量经过一次迭代，得新的单纯形表如下：x1x2x3x4x5x6bix61/3002/31/314/3x21/3111/32/3028/3f1/3028/38/3085.33新的最优解为X=(028/30004/3)T