第五讲线性规划灵敏度分析.ppt

《第五讲线性规划灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学（operationsresearch,OR）第五讲线性规划灵敏度分析商学院电子商务系9/3/20211第五讲线性规划灵敏度分析一.目标函数系数的变化二.约束右端常数项的变化三.系数矩阵A的变化四.用Excel进行灵敏度分析9/3/20212一、目标函数系数的变化第五讲线性规划灵敏度分析价值系数c发生变化：考虑检验数j=cj–CBB-1Pj，j=1,2,……,n1.若cj是非基变量的系数：设cj变化为cj+cj：则j’=cj+cj–CBB-1Pj=j+cj若使当前最优解不变，则j’≤0即：cj+cj≤CBB-1Pj=YPj9/3/20213第五

2、讲线性规划灵敏度分析一、目标函数系数的变化1.若cj是非基变量的系数：例题Maxz=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥09/3/20214第五讲线性规划灵敏度分析1.若cj是非基变量的系数：从表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5时，原最优解不变。9/3/20215第五讲线性规划灵敏度分析一、目标函数系数的变化2.若cr是基变量的系数：因cr∈CB，当cr变化Δcr时，就引起CB的变化，这时(CB+ΔCB)B-1A=CBB-1A+(0

3、，…，Δcr，…，0)B-1A=CBB-1A+Δcr(αr1,αr2,…，αrn)可见，当cr变化Δcr后，最终表中的检验数是σj′=cj−CBB-1Pj−Δcra’rj，j=1,2,…，n若要求原最优解不变，即必须满足σj′≤0。于是得到:9/3/20216第五讲线性规划灵敏度分析一、目标函数系数的变化2.若cr是基变量的系数：Δcr可变化的范围是:9/3/20217第五讲线性规划灵敏度分析一、目标函数系数的变化例试以例1的最终表为例。设基变量x2的系数c2变化Δc2，在原最优解不变条件下，确定Δc2的变化范围。解：这时最终计算表便成为下表所示。9/3/202

4、18第五讲线性规划灵敏度分析若保持原最优解，从上表的检验数行可见应有由此可得Δc2≥−4和Δc2≤2。Δc2的变化范围为−4≤Δc2≤2即x2的价值系数c2可以在［0，6］之间变化，而不影响原最优解。一、目标函数系数的变化9/3/20219第五讲线性规划灵敏度分析二、约束右端常数项的变化资源数量变化是指资源中某系数br发生变化，即br′=br+Δbr。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为：XB′=B-1(b+Δb)这里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最终表中检验数不变，故最优基不变，但最优解的值发生

5、了变化，所以XB′为新的最优解。新的最优解的值可允许变化范围用以下方法确定。9/3/202110第五讲线性规划灵敏度分析二、约束右端常数项的变化新的最优解的值可允许变化范围用以下方法确定。9/3/202111第五讲线性规划灵敏度分析二、约束右端常数项的变化新的最优解的值可允许变化范围用以下方法确定。在最终表中求得的经过变化后的b列的所有元素，要求：于是得到：9/3/202112第五讲线性规划灵敏度分析二、约束右端常数项的变化例如求例1中第二个约束条件b2的变化范围。解：可以利用例1的最终计算表中的数据：00-21/2141001/404011/2-1/802x1x5

6、x2304B－1bXBCBx1x2x3x4x5θcj→9/3/202113第五讲线性规划灵敏度分析二、约束右端常数项的变化可计算Δb2：由上式，可得Δb2≥−4/0.25=−16，Δb2≥−4/0.5=−8，b2≤2/0.125=16。所以Δb2的变化范围是［−8，16］；显然原b2=16，加它的变化范围后，b2的变化范围是［8，32］。9/3/202114第五讲线性规划灵敏度分析二、约束右端常数项的变化练习题：从例1中，若该厂又从其他处抽调4个单位的原材料用于生产产品甲，乙。求这时该厂生产产品甲，乙的最优方案。9/3/202115第五讲线性规划灵敏度分析三、系数矩

7、阵A的变化1.A中某个元素的变化：若系数矩阵中aij变化了△aij，且它是非基变量的系数列向量的分量。而在单纯形最终计算表中，非基变量xj的检验数为：则：故：9/3/202116第五讲线性规划灵敏度分析三、系数矩阵A的变化2.A中某列向量的变化：若系数矩阵A中某一列向量Pj发生了变化，且其对应的变量xj为非基变量，那么Pj的变化仅影响起自身的检验数。如果，则说明变化后并不影响当前解；如果，则说明变化后影响当前解，需重新迭代；若系数矩阵A中某一列向量Pj发生了变化，且其对应的变量xj为基变量，则需恢复该列向量为单位列向量后，再处理。9/3/202117第五讲线性规