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

2023/2/71灵敏度分析又称“后验分析”，它是对已经得到的最优方案改变某些条件来检验最优解的“稳定性”以及目标函数最优值随各种条件变化的“敏感性”；换言之，假定对于已知线性规划问题已求得的最优解是获得的最大利润的生产计划安排，现在如果在生产过程中成本系数向量C，约束常数向量b,约束系数A以及其他条件发生变化或波动，这些变化限制在什么范围内，在原来得到的最优安排仍为最优，而不需要改变工作计划？解决这些问题的理论和方法就是灵敏度分析灵敏度越小，解的稳定性越好2023/2/72灵敏度分析包括以下几个方面的内容分析成本系数向量C的变化对解和目标函数值的影响分析约束常数向量b的变化对解的影响，以及通过对偶最优解研究b的变化对目标函数值的影响分析系数矩阵A中元素变化对解和目标值的影响增加新变化量时最优解和最优值的变化增加新的约束条件后对最优解和最优值的影响2023/2/73单纯形法计算的矩阵描述（回顾）线性规划问题化为标准型2023/2/74单纯形法计算的矩阵描述（回顾）XS为松弛变量,XS=(xn+1,xn+2,…,xn+m),

I为m×m矩阵2023/2/75初始单纯形表非基变量基变量初始基变量单纯形法计算的矩阵描述（回顾）2023/2/76基变量非基变量当前检验数当前基解设若干步迭代后，基变量为,

在初始单纯形表中的系数矩阵为B，而A中去掉B的若干列组成矩阵N，则迭代后的单纯形表为：单纯形法计算的矩阵描述（回顾）2023/2/77单纯形法计算的矩阵描述（回顾）检验数因此2023/2/78一、目标函数系数C（价值系统）变化

cj

变动可能由于市场价格的波动，或生产成本的变动

cj

的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj允许的变动范围cj

cj的变化会引起检验数的变化，有两种情况

非基变量价值系数变化，不影响其它检验数

基变量价值系数变化，影响所有非基变量检验数2023/2/79此表仍为最优，此时最优解不变但最优值改变此表不是最优单纯形表检验数和最优值改变，用单纯形法继续迭代

XBXN常数项XBEB-1NB-1b检验行0CN-CBB-1NZ：CBB-1b≤02023/2/7101、非基变量对应的价值系数的灵敏度分析

则最优解不变；否则，将最优单纯形表的检验数

k

用k’取代，继续单纯形法的表格计算。

设变化为只要即2023/2/711

例：最优单纯形表

从表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5时，原最优解不变。2023/2/7122、基变量对应的价值系数的灵敏度分析由于基变量对应的价值系数在中出现，因此它会影响所有非基变量的检验数。设中一个基变量的发生变化，变化量为。

2023/2/7132023/2/714从表中看到σj=cj-(c1×a1j+c5×

a5j+(c2+Δc2)×a2j)j=3,4可得到-3≤Δc2≤1时，原最优解不变。2023/2/715设XB=B1b是最优解，则有XB=B1b0b的变化不会影响检验数b的变化量b可能导致原最优解变为非可行解二、右边项b发生变化的灵敏度分析2023/2/716

最优单纯形表：≤0用对偶单纯形法迭代求出最优解

XBXN常数项XBEB-1NB-1b检验行0CN-CBB-1NZ：CBB-1b2023/2/717最优单纯形表的s.t中松弛变量的系数2023/2/718

XBXN常数项XBEB-1NB-1b检验行0CN-CBB-1NZ：CBB-1b2023/2/7192023/2/7202023/2/721例：某工厂准备生产A、B、C三种产品，他们都消耗劳动力和材料，有关数据如下：

原料产品ABC拥有量劳动力63545材料34530售价（元）314最优单纯形表X1X2X3X4X5X151-1/301/3-1/3X33011-1/52/5Z=270-20-1/5-3/52023/2/722最优单纯形表X1X2X3X4X5X151-1/301/3-1/3X33011-1/52/5Z=270-20-1/5-3/52023/2/723最优单纯形表X1X2X3X4X5X1101-25/301/3X450-5-51-2Z=300-3-10-1结论：最优生产方案：10个A，其余不生产

原料产品ABC拥有量劳动力63545材料34530售价（元）314X1X2X3X4X5X151-1/301/3-1/3X33011-1/52/5Z=270-20-1/5-3/52023/2/724三、新增决策变量的灵敏度分析研究：增加新变量时最优解和最优值的变化2023/2/725资源的合理利用问题：资源单位消费产品资源限制单位利润新问题：工厂研制了一种新产品，估计单位利润为cn+1，问是否投入生产，若投入生产，求最优生产方案2023/2/726对问题：最优单纯形表增加一个新变量xn+1

XBXN常数项XBEB-1NB-1b检验行0CN-CBB-1NZ：CBB-1b2023/2/727对问题：

XBXN常数项XBEB-1NB-1b检验行0CN-CBB-1NZ：CBB-1b最优单纯形表增加一个新变量xn+12023/2/728对新问题：

XBXN常数项XBEB-1NB-1b检验行0CN-CBB-1NZ：CBB-1b最优单纯形表此表达到最优此表未达到最优用单纯形法迭代至找到最优解2023/2/729例：某工厂准备生产A、B、C三种产品，他们都消耗劳动力和材料，有关数据如下：产品原料ABC拥有量劳动力63545材料34530售价（元）314最优单纯形表:最优生产方案：5个A，0个B，3个C问题1、若工厂开发出第四种产品D，预计售价2元，生产每个D产品需要3个劳动力和3个单位材料，问是否生产该产品？2、若产品D的售价为3元，问如何调整生产方案？？X1X2X3X4X5X151-1/301/3-1/3X33011-1/52/5Z=270-20-1/5-3/52023/2/730问题1、若工厂开发出第四种产品D，预计售价2元，生产每个D产品需要3个劳动力和3个单位材料，问是否生产该产品？最优基不变，X6是非基变量，在最优解中取0即当新产品D的售价为2元时，不生产该产品。2023/2/731X603/53/5最优单纯形表:2、若产品D的售价为3元，问如何调整生产方案？X1X2X3X4X5X6X151-1/301/3-1/30X6505/35/3-1/32/31Z=300-3-10-10最优生产方案：5个A产品，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/52023/2/732四、新增约束条件的灵敏度分析

1、将最优解代入新的约束条件，若满足，则最优解不变2、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯形表，并变换为标准型3、利用单纯形法或对偶单纯形法继续迭代

——为什么可以利用对偶单纯形法？2023/2/733例：某工厂准备生产A、B、C三种产品，他们都消耗劳动力和材料，有关数据如下：

原料产品ABC拥有量劳动力63545材料34530售价（元）314最优生产方案：5个A，0个B，3个C新问题：由于特殊原因，要求至少生产6个C产品，求最优生产方案最优单纯形表X1X2X3X4X50-20-1/5-3/5Z:27X11-1/301/3-1/35X3011-1/52/5300000-1001-6X6X62023/2/734X1X2X3X4X50-20-1/5-3/5Z:27X11-1/301/3-1/35X3011-1/52/53X6X6000X1X2X3X4X5X60-20-1/5-3/50Z:27X11-1/301/3-1/305X3011-1/52/503X6010-1/52/51-300-1001-6X1X2X3X4X5X60-100-1-1Z:24X114/3001/35/30X300100-16X40-501-2-515最优生产方案：0个A，0个B，6个C2023/2/735最优单纯形