运筹学－北京邮电大学2-2PPT模板|运筹学－北京邮电大学2-2PPT模版(幻灯片模板|Powerpoint模板)

运筹学－北京邮电大学2-2

2.4 灵敏度分析
灵敏度分析又称为后优化分析
2.4 线性规划的灵敏度分析
线性规划是静态模型
参数发生变化，原问题的最优解还是不是最优
哪些参数容易发生变化
C, b, A
每个参数发生多大的变化不会破坏最优解
灵敏度越小，解的稳定性越好
2.4.1 边际值(影子价) qi
以(max,%26#61603;)为例
边际值(影子价)qi 是指在最优解的基础上，当第 i 个约束行的右端项 bi 减少一个单位时，目标函数的变化量
例2.4.2
关于影子价的一些说明
影子价是资源最优配置下资源的理想价格，资源的影子价与资源的紧缺度有关
松弛变量增加一个单位等于资源减少一个单位
剩余变量增加一个单位等于资源增加一个单位
资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为 0
影子价为 0，资源并不一定有剩余
应用，邮电产品的影子价格
2.4.2 价值系数 cj 的灵敏度分析
cj 变动可能由于市场价格的波动，或生产成本的变动
cj 的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj 允许的变动范围%26#61508;cj
cj 的变化会引起检验数的变化，有两种情况
非基变量对应的价值系数变化，不影响其它检验数
基变量对应的价值系数变化，影响所有非基变量检验数
1、非基变量对应的价值系数的灵敏度分析
例2.4.2
2、基变量对应的价值系数的灵敏度分析
由于基变量对应的价值系数在CB中出现，因此它会影响所有非基变量的检验数
只有一个基变量的 cj%26#61602; 发生变化，变化量为%26#61508; cj%26#61602;
令 cj%26#61602; 在CB中的第k行，研究非基变量xj 机会成本的变化

2.4.3 右端项 bi 的灵敏度分析
设 XB=B%26#61485;1b 是最优解，则有XB=B%26#61485;1b%26#61619;0
b 的变化不会影响检验数
b 的变化量 %26#61508;b 可能导致原最优解变为非可行解
2.4.3 右端项 bi 的灵敏度分析

2.4.4 技术系数 aij 的灵敏度分析
技术系数aij变化的影响比较复杂
对应基变量的 aij ，且资源bi已全部用完
对应基变量的 aij ，但资源bi未用完
对应非基变量的 aij ，且资源bi全用完或未用完
1、对应基变量的 aij ，且资源bi已全部用完 %26#61508;aij=0
2、对应基变量的 aij ，但资源bi未用完 %26#61485;%26#61605; %26#61603; %26#61508;aij%26#61603; xn+i /xj
上述两个公式不充分，为什么？
B–1发生变化，从而引起非基变量检验数 cj– zj 的变化
3、对应非基变量的 aij
只影响对应非基变量xj的检验数 cj– zj
若%26#61508; aij %26gt; 0，不会破坏最优解
若%26#61508; aij %26lt; 0，必须保证 cj– zj %26#61603; 0

2.4.5 新增决策变量的分析
例2.4.2中，若新增产品 x8，问是否生产？
已知 c8=9, a18=5, a28=4, a38=3
计算 x8 的检验数可知生产是否有利
2.4.6 新增约束条件的分析
1、将最优解代入新的约束条件，若满足，则最优解不变
2、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型
3、利用对偶单纯型法继续迭代
为什么可以利用对偶单纯型法

2.4.7 灵敏度分析举例
例2.4.3 某工厂生产三种产品 A, B, C，有五种生产组合方案。下两表给出有关数据。规定每天供应 A产品至少110 个，求收益最大的生产方案。
例2.4.3
解：设xj为已选定各种组合方案的组数(j=1,2,…,5)， x6为A产品的剩余变量， x7，x8分别为工人工时和机器工时的松弛变量。
例2.4.3
最优解的B–1是什么
产品A的影子价为多少
第II组方案的生产费用提高2元，是否要调整生产组别
若工人加班费为1元/小时，是否要采取加班措施
若通过租借机器增加工时，租费的上限应为多少
A产品的订购合同是否有利
若要选用第IV组方案，该组的生产费用应降低多少
若工人加班费为0.3元/小时，最多允许加班时间多少
若机器租费低于44元/小时，问租几部机器才合适(每天8小时计)
若第III组方案使机器工时减少0.5小时，能否被选入
2.5 参数线性规划
2.4 节中 aij, bi, cj 只有一个发生变化，多个同时发生变化则很难解析
但在一些特殊情况下，用参数表示变化量，也可以用来进行多个系数的灵敏度分析
2.5.1 参数cj的变化分析
%26#61553;i 第i 种资源的单位费用变化量， %26#61553;i %26#61617;不限
%26#61537;i %26#61553;i 变化对 cj 的影响率
例2.4.2 资源b1单价变化量%26#61553;1，价格影响率%26#61537;j=a1j
例2.4.2 资源b1单价变化量%26#61553;1 与%26#61508;c5
2.5.2 参数 bi 的变化分析
例2.4.2中，将b1,b2,b3理解为三个车间的周工时资源。假设从第2向1车间调动工人%26#61553; 个，每个工人的周工时为 40小时，问调动多少工人不会破坏最优产品组合