运筹学课程04-灵敏度分析

1、NEUQNEUQ2022-3-91灵敏度分析又称灵敏度分析又称“后验分析后验分析”，它是对已经得到的最优，它是对已经得到的最优方案改变某些条件来检验最优解的方案改变某些条件来检验最优解的“稳定性稳定性”以及目标以及目标函数最优值随各种条件变化的函数最优值随各种条件变化的“敏感性敏感性”；换言之，假；换言之，假定对于已知线性规划问题已求得的最优解是获得的最大定对于已知线性规划问题已求得的最优解是获得的最大利润的生产计划安排，现在如果在生产过程中成本系数利润的生产计划安排，现在如果在生产过程中成本系数向量向量C C，约束常数向量，约束常数向量b, b,约束系数约束系数A A以及其他条件发生变以及其

2、他条件发生变化或波动，这些变化限制在什么范围内，在原来得到的化或波动，这些变化限制在什么范围内，在原来得到的最优安排仍为最优，而不需要改变工作计划？最优安排仍为最优，而不需要改变工作计划？解决这些问题的理论和方法就是灵敏度分析解决这些问题的理论和方法就是灵敏度分析灵敏度越小，解的稳定性越好灵敏度越小，解的稳定性越好NEUQNEUQ2022-3-92灵敏度分析包括以下几个方面的内容灵敏度分析包括以下几个方面的内容分析成本系数向量分析成本系数向量C C的变化对解和目标函数值的的变化对解和目标函数值的影响影响分析约束常数向量分析约束常数向量b b的变化对解的影响，以及通的变化对解的影响，以及通过对偶

3、最优解研究过对偶最优解研究b b的变化对目标函数值的影响的变化对目标函数值的影响分析系数矩阵分析系数矩阵A A中元素变化对解和目标值的影响中元素变化对解和目标值的影响增加新变化量时最优解和最优值的变化增加新变化量时最优解和最优值的变化增加新的约束条件后对最优解和最优值的影响增加新的约束条件后对最优解和最优值的影响NEUQNEUQ2022-3-93单纯形法计算的矩阵描述（回顾）单纯形法计算的矩阵描述（回顾）0maxXbAXCXz线性规划问题线性规划问题0, 00maxsssXXbIXAXXCXz化为标准型化为标准型NEUQNEUQ2022-3-94单纯形法计算的矩阵描述（回顾）单纯形法计算的矩阵

4、描述（回顾）),(),(NBNBCCCXXXNBAbNXBXbXXNBNBNB),(NEUQNEUQ2022-3-95初始单纯形表初始单纯形表00NBjjssNBCCzcINBbXXXX非基变量非基变量基变量基变量初始基变量初始基变量单纯形法计算的矩阵描述（回顾）单纯形法计算的矩阵描述（回顾）NEUQNEUQ2022-3-96111110BCNBCCzcBNBIbBXCXXXBBNjjBBsNB基变量基变量非基变量非基变量当前检验数当前检验数当前基解当前基解设若干步迭代后，基变量为设若干步迭代后，基变量为 ,在初始单纯形在初始单纯形表中的系数矩阵为表中的系数矩阵为B，而，而A中去掉中去掉B的若

5、干列组成矩的若干列组成矩阵阵N，则迭代后的单纯形表为：，则迭代后的单纯形表为： BXBX单纯形法计算的矩阵描述（回顾）单纯形法计算的矩阵描述（回顾）NEUQNEUQ2022-3-97单纯形法计算的矩阵描述（回顾）单纯形法计算的矩阵描述（回顾）0011BCNBCCBBN001BBCCICCBBBBBX检验数检验数0011BCABCCBB因此因此NEUQNEUQ2022-3-98一、目标函数系数一、目标函数系数C C（价值系统）（价值系统）变化变化 c cj j 变动可能由于市场价格的波动，或生产成本的变动变动可能由于市场价格的波动，或生产成本的变动 c cj j 的灵敏度分析是在保证最优解的基变

6、量不变的情况下，的灵敏度分析是在保证最优解的基变量不变的情况下，分析分析c cj j 允许的变动范围允许的变动范围 c cj j c cj j 的变化会引起检验数的变化，有两种情况的变化会引起检验数的变化，有两种情况 非基变量价值系数变化，不影响其它检验数非基变量价值系数变化，不影响其它检验数 基变量价值系数变化，影响所有非基变量检验数基变量价值系数变化，影响所有非基变量检验数NEUQNEUQ2022-3-99此表仍为最优，此表仍为最优，此时最优解不变但最优值改变此时最优解不变但最优值改变此表不是最优单纯形表此表不是最优单纯形表检验数和最优值改变检验数和最优值改变，用单纯形法继续迭代用单纯形法

7、继续迭代不变但01bBCC当变为时，01NBCCBN若01NBCCBN若 XB XN常数项常数项XBE B-1NB-1b检验行检验行0 CN- CBB-1NZ： CBB-1b00NEUQNEUQ2022-3-9101 1、非基变量对应的价值系数的灵敏度分析、非基变量对应的价值系数的灵敏度分析 则最优解不变；否则，将最优单纯形表的检验数则最优解不变；否则，将最优单纯形表的检验数 k k 用用 k k取代，继续单纯形法的表格计算取代，继续单纯形法的表格计算。 kkcc1mkkkiikkkiccc ac0kkkc kc设设变化为变化为只要只要即即1kkkkicccc 结结论论 ：若若是是非非基基变变

8、量量的的系系数数，则则当当 的的改改变变量量在在范范围围内内时时，最最优优解解不不变变NEUQNEUQ2022-3-911 例：最优单纯形表例：最优单纯形表 从表中看到从表中看到3 3= = c c3 3+c c3 3-(-(c c2 2a a1313+ +c c1 1a a23 23 ) ) 可得到可得到c c3 3 9/5 9/5 时，原最优解不变。时，原最优解不变。CI-2-3-400CBXBbX1X2X3X4X5-3 X22/501-1/5 -2/51/5-2 X111/5107/5-1/5 -2/5j00-9/5 -8/5 -1/5CI-2-3-4+c300CBXBbX1X2X3X4

9、X5-3 X22/501-1/5-2/51/5-2 X111/5107/5-1/5-2/5j00-9/5+c3-8/5-1/5NEUQNEUQ2022-3-9122 2、基变量对应的价值系数的灵敏度分析、基变量对应的价值系数的灵敏度分析由于基变量对应的价值系数在由于基变量对应的价值系数在 中出现，因此它会影响所中出现，因此它会影响所有非基变量的检验数。设有非基变量的检验数。设 中一个基变量的中一个基变量的 发生变发生变化，变化量为化，变化量为 。 100000jjj (), , , mjjiijkkjijjjjjjkjkkjkjkkjkkjkjkjzzc ac aczzczacaacacaaa

10、要要满满足足则则有有当当有有当当有有kckcBCBCNEUQNEUQ2022-3-91300jj, maxminkjkkjjjkjkjacaaa 为为保保证证所所有有非非基基变变量量检检验验数数仍仍满满足足最最优优条条件件 有有200max|,min|,kkkjjkjkkjkjkjcccajNcajNaa 结结论论 ：若若 是是基基变变量量的的系系数数，则则当当 的的改改变变量量在在范范围围内内时时，最最优优解解不不变变NEUQNEUQ2022-3-914C i 2 3 0 0 0 CB XB B X1 X2 X3 X4 X5 2 X1 4 1 0 0 1/4 0 0 X5 4 0 0 -2

11、1/2 1 3 X2 2 0 1 1/2 -1/8 0 j 0 0 -1.5 -1/8 0 Ci 2 3+C C2 0 0 0 CB XB B X1 X2 X3 X4 X5 2 X1 4 1 0 0 1/4 0 0 X5 4 0 0 -2 1/2 1 3+C C2 X2 2 0 1 1/2 -1/8 0 j 0 0 -1.5 -C C2/2 -1/8+C C2/8 0 从表中看到从表中看到j=cj-(c1a1j+c5 a5j+(c2+c2)a2j) j=3,4可得到可得到 -3-3c c2 211时，原最优解不变。时，原最优解不变。NEUQNEUQ2022-3-915设设 XB=B 1b 是最

12、优解，则有是最优解，则有XB=B 1b 0b 的变化的变化不会不会影响检验数影响检验数b 的变化量的变化量 b 可能导致原最优解变为非可行解可能导致原最优解变为非可行解二、右边项二、右边项 b b 发生变化的灵敏度分析发生变化的灵敏度分析NEUQNEUQ2022-3-916 最优单纯形表：最优单纯形表：00，设bb 不变01NBCCBNbBCZbBCZBB11bBbB11：若01bB单纯形表保持最优，1*0XB b最优解（， ），bBCZB1*最优值：若01bBbBbB11在原最优单纯形表中，bBCZbBCZBB11，用用对偶单纯形法对偶单纯形法迭代求出最优解迭代求出最优解1B求 XB XN常

13、数项常数项XBE B-1NB-1b检验行检验行0 CN- CBB-1NZ： CBB-1bNEUQNEUQ2022-3-9170.maxXbAXtsCXz对问题0.maxXbXAXtsCXzS标准型bBXBNXBXSNB111最优单纯形表的最优单纯形表的s.ts.t中中松弛变量的系数松弛变量的系数的求法：1BNEUQNEUQ2022-3-918变化时，原最优基不变在什么范围内变，则其余不问题：设iiiibbbb,miibbbbb1bb 001imibbbbmmmimmimiB1222111111，bB1)(1bbBbBbB11mmmimmimi12221111100ibimiiiiibbb211

14、21mbbB bb 记记12mbbb 1122iiiimmiibbbbbb 0 XB XN常数项常数项XBE B-1NB-1b检验行检验行0 CN- CBB-1NZ： CBB-1b12mbbb NEUQNEUQ2022-3-91901bBbi在什么范围内变化时，问题：bB11122iiiimmiibbbbbb 01122000iiiimmiibbbbbb 1122iiiimiimbbbbbb 0ki若,kikibb 0ki若,kikibb min|0kikikibb max|0kkikib 满足的改变量结论：当iibbmax|0kkikib 原问题的最优基不变列的第iB1bB1min|0kik

15、ikibb 01bBNEUQNEUQ2022-3-920121121.iimimBibbB bs tb其中：是的第 列，是最优单纯形表中的常数项满足的改变量结论：当iibb原问题的最优基不变max|0kkikib min|0kikikibb NEUQNEUQ2022-3-9211220b、若若劳劳动动力力拥拥有有量量 增增加加了了个个，求求最最优优生生产产方方案案例：某工厂准备生产例：某工厂准备生产A A、B B、C C三种产品，他们都消耗劳动三种产品，他们都消耗劳动力和材料，有关数据如下：力和材料，有关数据如下： 原料原料 产品产品ABC拥有量拥有量劳动力劳动力63545材料材料34530售

16、价（元）售价（元）314最优单纯形表最优单纯形表111Bbb问问题题 、劳劳动动力力拥拥有有量量 的的改改变变量量在在什什么么范范围围内内变变化化时时，仍仍然然不不生生产产产产品品2700305ZX最优值），（最优解X1X2X3X4X5X151-1/301/3-1/3X33011-1/52/5Z=270-20-1/5-3/5NEUQNEUQ2022-3-9220|min111kkkbb0|max11kkkb21bb1B0|min11kkkb150|max11kkkb212b111b153060B结结论论：当当劳劳动动力力的的拥拥有有量量在在至至之之间间时时，仍仍然然不不生生产产产产品品1515

17、1b即最优单纯形表最优单纯形表X1X2X3X4X5X151-1/301/3-1/3X33011-1/52/5Z=270-20-1/5-3/5111bbB问问题题 、劳劳动动力力拥拥有有量量 的的改改变变量量在在什什么么范范围围内内变变化化时时，仍仍然然不不生生产产产产品品NEUQNEUQ2022-3-923最优单纯形表最优单纯形表bB15/ 25/ 13/ 13/ 113/351:BZ C B b35 33 41/,31X1X2X3X4X5X1101-25/301/3X450-5-51-2Z=300-3-10-130050010ZX最优值），（最优解结论：最优生产方案：结论：最优生产方案：10

18、10个个A A，其余不生产，其余不生产1220b、若若劳劳动动力力拥拥有有量量 增增加加了了个个，求求最最优优生生产产方方案案1B 原料原料 产品产品ABC拥有量拥有量劳动力劳动力63545材料材料34530售价（元）售价（元）3143065X1X2X3X4X5X151-1/301/3-1/3X33011-1/52/5Z=270-20-1/5-3/513/3531Z=NEUQNEUQ2022-3-924三、新增三、新增决策变量决策变量的灵敏度分析的灵敏度分析研究：增加新变量时最优解和最优值的变化NEUQNEUQ2022-3-925资源的合理利用问题：资源的合理利用问题：资源单位消费产品mAAA

19、21nBBB21mnmmnnaaaaaaaaa212222111211资源限制mbbb21单位利润nccc21nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxa221122222121112121110,21nxxx的总利润最大？利用现有资源，使获得排生产计划，才能充分下表，问如何安件产品可获得的利润如资源的数量限制以及每所消费的资源数、每种种资源，已知每件产品，耗种产品，要消，周期内生产某厂计划在下一个生产mnAAABBB2121), 2 , 1njBxjj（的产量表示产品解：设新问题：工厂研制了一种新产品，估计单位利新问题：工厂研制了一种新产品，

20、估计单位利 润为润为c cn+1n+1，问是否投入生产，若投入生产，问是否投入生产，若投入生产，求最优生产方案求最优生产方案1112111nmnnnncaaaB111nnxc111nnxa112nnxa11nnmxa1NEUQNEUQ2022-3-926nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111mBcccC,210,21nxxx对问题：对问题：mPPPB,21设最优单纯形表最优单纯形表nmmPPPN,21，mBxxxX,21nmmNcccC,21nmmNxxxX,21mbbbb,21mnmmnnaaaa

21、aaaaaA212222111211nPPP,21增加一个新变量xn+1 XB XN常数项常数项XBE B-1NB-1b检验行检验行0 CN- CBB-1NZ： CBB-1bNEUQNEUQ2022-3-927nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxa221122222121112121110,21nxxx对问题：对问题：mPPPB,21设 XB XN常数项常数项XBE B-1NB-1b检验行检验行0 CN- CBB-1NZ： CBB-1b最优单纯形表最优单纯形表bb BB 基增加一个新变量增加一个新变量x xn+1n+1111nnxc111

22、nnxa112nnxa11nnmxaBBXX BBCC 11,nnmPPPNN， 11,NNmnnXXxx x 11, ,NNmnnCCcc c 1nP1nPN，1,nNxX1,nNcC1nxNBCCNBCCBNBN11NBNB11NBCCBN11,nNcC11,nBPNBC1,nNcC111,nBBPBCNBC1111,nBnBNPBCcNBCC111nBnPBCcNB111nPNB，111nPBNB，11nPBNEUQNEUQ2022-3-928112211maxnnnnxcxcxcxczmnmnnmnmmnnnnnnnnbxaxaxaxabxaxaxaxabxaxaxaxa1122112

23、1122222121111112121110,121nnxxxx对新问题：对新问题： XB XN常数项常数项XBE B-1NB-1b检验行检验行0 CN- CBB-1NZ：CBB-1b最优单纯形表最优单纯形表1nx111nBnPBCc11nPB，此时01NBCCBN01bB：若0111nBnPBCc此表达到最优此表达到最优为非基变量1nx：若0111nBnPBCc此表未达到最优此表未达到最优为入基变量，1nx用单纯形法迭代用单纯形法迭代至找到最优解至找到最优解0*1nx新产品不投产NEUQNEUQ2022-3-929例：某工厂准备生产例：某工厂准备生产A A、B B、C C三种产品，他们都消耗

24、三种产品，他们都消耗劳动力和材料，有关数据如下：劳动力和材料，有关数据如下： 产品产品原料原料ABC拥有量拥有量劳动力劳动力63545材料材料34530售价（元）售价（元）314最优单纯形表最优单纯形表: :2700305ZX），最优值，（最优解最优生产方案：最优生产方案：5个个A，0个个B，3个个C问题问题1、若工厂开发出第四种产品、若工厂开发出第四种产品D，预计售价，预计售价2元，元， 生产每个生产每个D产品需要产品需要3个劳动力和个劳动力和3个单位材个单位材 料，问是否生产该产品？料，问是否生产该产品？2、若产品、若产品D的售价为的售价为3元，问如何调整生产方案？元，问如何调整生产方案？

25、633P 26c4 , 3BC0616PBCcB？X1X2X3X4X5X151-1/301/3-1/3X33011-1/52/5Z=270-20-1/5-3/5NEUQNEUQ2022-3-93033,6P26c616PBCcB 1/31/3323 41/52/53 5/ 2,6xD的产量为设产品525131311B问题问题1、若工厂开发出第四种产品、若工厂开发出第四种产品D，预计售价，预计售价2元，元， 生产每个生产每个D产品需要产品需要3个劳动力和个劳动力和3个单位材个单位材 料，问是否生产该产品？料，问是否生产该产品？0最优基不变，X6是非基变量，在最优解中取0即当新产品即当新产品D的售

26、价为的售价为2元时，不生产该产品。元时，不生产该产品。NEUQNEUQ2022-3-931X603/53/5最优单纯形表最优单纯形表: :061PB335/ 25/ 13/ 13/ 15/ 302、若产品、若产品D的售价为的售价为3元，问如何调整生产方案？元，问如何调整生产方案？33,6P36c525131311B616PBCcB335/ 25/ 13/ 13/ 14335/ 3X1X2X3X4X5X6X151-1/301/3-1/30X6505/35/3-1/32/31Z=300-3-10-105 0 0 0 0,530XZ最优解（ ，），最优值最优生产方案：最优生产方案：5个个A产品，产品

27、， 0个个B产品，产品， 0个个C产品，产品， 5个个D产品产品X1X2X3X4X5X151-1/301/3-1/3X33011-1/52/5Z=270-20-1/5-3/5X1X2X3X4X5X151-1/301/3-1/3X33011-1/52/5Z=270-20-1/5-3/5NEUQNEUQ2022-3-932四、新增四、新增约束条件约束条件的灵敏度分析的灵敏度分析 1 1、将最优解代入新的约束条件，若满足，则最优、将最优解代入新的约束条件，若满足，则最优 解不变解不变2 2、若不满足，则当前最优解要发生变化；将新增约、若不满足，则当前最优解要发生变化；将新增约 束条件加入最优单纯形表

28、，并变换为标准型束条件加入最优单纯形表，并变换为标准型3 3、利用单纯形法或对偶单纯形法继续迭代、利用单纯形法或对偶单纯形法继续迭代 为什么可以利用对偶单纯形法？为什么可以利用对偶单纯形法？NEUQNEUQ2022-3-933例：某工厂准备生产例：某工厂准备生产A A、B B、C C三种产品，他们都消耗三种产品，他们都消耗劳动力和材料，有关数据如下：劳动力和材料，有关数据如下： 原料原料 产品产品ABC拥有量拥有量劳动力劳动力63545材料材料34530售价（元）售价（元）3142700305ZX最优值），（最优解最优生产方案：最优生产方案：5个个A，0个个B，3个个C新问题：新问题：由于特殊原因，要求至由于特殊原因，要求至少生产少生产6个个C产品，求最产品，求最优生产方案优生产方案63x即最优单纯形表最优单纯形表63*3x显然63x约束方程：在最优单纯形表中增加663xx为基变量并取6xX1X2X3X4X50-20-1/5-3/5Z:27X11-1/301/3-1/35X3011-1/52/5300000-1001-6X6X6NEUQNEUQ2022-3-934X1X2X3X4X50-20-1/5-3/5Z:27X11-1/301/3-1/35X3011-1/52/53X6X6000X1X