文档介绍：第五讲线性规划灵敏度分析
*
*
第一页，共30页
第五讲 线性规划灵敏度分析
一. 目标函数系数的变化
二. 约束右端常数项的变化
三. 系数矩阵A的变化
四. 用Excel进行灵敏度分析
*
*
第二页，共30页
一、目标函数系数的变化
第五讲 线性规划灵敏度分析
价值系数c发生变化：
考虑检验数 j=cj–CBB-1Pj， j =1,2,……,n
1. 若cj是非基变量的系数：
设cj变化为 cj + cj ： 则j’= cj + cj –CBB-1Pj = j+ cj
若使当前最优解不变，则j’≤0
即：cj + cj ≤ CBB-1Pj =YPj
*
*
第三页，共30页
第五讲 线性规划灵敏度分析
一、目标函数系数的变化
1. 若cj是非基变量的系数：
例题
Max z = -2x1 - 3x2 - 4x3
. -x1-2x2-x3+x4 = - 3
-2x1+x2-3x3+x5 = - 4
x1 ,x2 ,x3 ,x4 ,x5 ≥0
*
*
第四页，共30页
第五讲 线性规划灵敏度分析
1. 若cj是非基变量的系数：
从表中看到σ3= c3+Δc3-(c2×a13+c1×a23 )
可得到Δc3 ≤ 9/5 时，原最优解不变。
*
*
第五页，共30页
第五讲 线性规划灵敏度分析
一、目标函数系数的变化
2. 若cr是基变量的系数：
因cr∈CB，当cr变化Δcr时，就引起CB的变化，这时
(CB+ΔCB)B-1A=CBB-1A+(0，…，Δcr，…，0)B-1A
=CBB-1A+Δcr(αr1,αr2,…，αrn)
可见，当cr变化Δcr后，最终表中的检验数是
σj′=cj−CBB-1Pj−Δcr a’rj，j=1,2,…，n
若要求原最优解不变，即必须满足σj′≤0。于是得到:
*
*
第六页，共30页
第五讲 线性规划灵敏度分析
一、目标函数系数的变化
2. 若cr是基变量的系数：
Δcr可变化的范围是:
*
*
第七页，共30页
第五讲 线性规划灵敏度分析
一、目标函数系数的变化
例 试以例1的最终表为例。 设基变量x2的系数c2变化Δc2，在原最优解不变条件下，确定Δc2的变化范围。 解： 这时最终计算表便成为下表所示。
*
*
第八页，共30页
第五讲 线性规划灵敏度分析
若保持原最优解，从上表的检验数行可见应有 由此可得Δc2≥−4 和Δc2≤2。 Δc2的变化范围为 −4≤Δc2≤2 即x2的价值系数c2可以在［0，6］之间变化，而不影响原最优解。
一、目标函数系数的变化
*
*
第九页，共30页
第五讲 线性规划灵敏度分析
二、约束右端常数项的变化
资源数量变化是指资源中某系数br发生变化，即br′=br+Δbr。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为：
XB′=B -1(b+Δb)
这里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB′为新的最优解。新的最优解的值可允许变化范围用以下方法确定。
*
*
第十页，共30页