运筹学05-灵敏度分析.ppt

《运筹学05-灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第五章线性规划灵敏度分析5.1目标函数系数的灵敏度分析5.2右端项的灵敏度分析5.3约束系数的灵敏度分析5.4参数规划上表中6个常数a1,a2,a3,b,1,2取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；3、问题无可行解；4、无有限最优解；5、现基本解可行，由x1取代x6目标函数可改善。cjB-1bcBxBx1x2x3x4x5x6x34a110a20bx4-1-501-102x6a3-300-413σjσ1σ200-30线性规划标准形式(1)、参数A，b，C在什么

2、范围内变动，对当前方案无影响？(2)、参数A，b，C中的一个(几个)变动，对当前方案影响？(3)、如果最优方案改变，如何用简便方法求新方案？当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。5.1目标函数系数的灵敏度分析考虑检验数(1)若ck是非基变量的系数：解：最优单纯形表例试求c3在多大范围内变动时，原最优解保持不变。cj-2-3-400B-1bcBxBx1x2x

3、3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5σj00-9/5-8/5-1/5-28/5从表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5时，原最优解不变。cj-2-3-4Δc300B-1bcBxBx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5σj00-9/5+Δc3-8/5-1/5-28/5(2)若ck是基变量的系数例求c2在什么范围内变动时，原最优解保持不变。下表为

4、最优单纯形表,考虑基变量系数c2发生变化Ci23000B-1bCBXBx1x2x3x4x52x11001/4040x500-21/2143x2011/2-1/802σj00-3/2-1/8014从表中看到可得到-3≤Δc2≤1时，原最优解不变。Ci23+Δc3000B-1bCBXBx1x2x3x4x52x11001/4040x500-21/2143+Δc3x2011/2-1/802σj00-3/2-Δc3/2-1/8+Δc3/8014+2Δc3设分量br变化为br+br，根据前面的讨论：最优解的基

5、变量xB=B-1b，那么只要保持B-1(b+b)≥0，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。5.2右端项的灵敏度分析例求当b1在由8变动为12时，原最优解是否保持不变，若变动求出新的最优解。解:下表为最优单纯形表Ci23000B-1bCBXBx1x2x3x4x52x11001/4040x500-21/2143x2011/2-1/802σj00-3/2-1/8014将b’代入原最优单纯形表中，运用对偶单纯形法计算最优解。经一次迭代后，求得新的最优解:(4320

6、0)TCi23000B-1bCBXBx1x2x3x4x52x11001/4040x500-21/21-43x2011/2-1/804σj00-3/2-1/8014θ3/42x11001/4040x3001-1/4-1/223x201001/43σj000-1/2-3/417(1)增加一个变量增加一个变量，相当于系数矩阵增加一列。增加变量xn+1则有相应的pn+1,cn+1。那么计算出B-1pn+1,n+1=cn+1-cBpn+1填入最优单纯形表,若n+1≤0则最优解不变；否则，进一步用单纯形法求

7、解。5.3约束系数的灵敏度分析例求当增加x6,p6=(2,6,3)T,c6=5时，原最优解是否保持不变，若变动求出新的最优解。解:下表为最优单纯形表Ci23000B-1bCBXBx1x2x3x4x52x11001/4040x500-21/2143x2011/2-1/802σj00-3/2-1/8014用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)Tf*=16.5Ci230005B-1bθCBXBx1x2x3x4x5x62x11001/403/248/30x500-21/212423

8、x2011/2-1/801/428σj00-3/2-1/805/4142x1103/2-1/8-3/4015x600-11/41/2123x2013/4-3/16-1/403/2σj00-1/4-7/160033/2(2)增加一个约束条件增加一个约束条件相当于系数矩阵中增加一行。增加一个约束条件之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通