第二章-05 灵敏度分析

1、灵敏度分析灵敏度分析1 灵敏度分析的含义和内容灵敏度分析的含义和内容 研究线性规划模型某些参数或限制量的变化对研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析最优解的影响及其程度的分析过程称为灵敏度分析或（优化后分析）。或（优化后分析）。2 灵敏度分析的内容：灵敏度分析的内容： 目标函数的系数变化对最优解的影响；目标函数的系数变化对最优解的影响；约束方程右端系数变化对最优解的影响；约束方程右端系数变化对最优解的影响； 约束方程组系数阵变化对最优解的影响约束方程组系数阵变化对最优解的影响 ； 这些系数在什麽范围内发生变化时，最优基不变这些系数在什麽范围内发生变

2、化时，最优基不变（即最优解或最优解结构不变）？（即最优解或最优解结构不变）？系数变化超出上述范围时，如何用最简便的方法系数变化超出上述范围时，如何用最简便的方法求出新的最优解？求出新的最优解？3 手工进行灵敏度分析的基本原则手工进行灵敏度分析的基本原则 (1) 在最优表格的基础上进行；在最优表格的基础上进行； (2) 尽量减少附加计算工作量尽量减少附加计算工作量. 二二 灵敏度分析举例灵敏度分析举例0,9743. .332max321321321321xxxxxxxxxtsxxxZ0,9743. .00332max543215321432154321xxxxxxxxxxxxxtsxxxxxZ引

3、入非负的松弛变量引入非负的松弛变量x4,x5, 将该将该LP化为化为标准型标准型：用表格单纯形法求解如下：用表格单纯形法求解如下： 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 X1 X2 2 3 3/1 6/3 1 1 1 1 0 0 3 6 -1 1 3 6 X1 X5 2 0 0 1 1 -2 0 -6 -Z 0 0 -1 -5/3 -1/3 -8 -Z 2 3 3 0 0 0 -Z3/19/1 1 1 1 1 0 1 4 7 0 1 3 9 X4 X5 0 0 j 2 3 3 0 0 x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 Cj b

4、 xj XB CB1、研究最优表格中的数据来源：、研究最优表格中的数据来源：（1）如果选）如果选B=（P1，P2）为初始可行基，能否从为初始可行基，能否从表格中直接看出表格中直接看出B-1？N舍弃中间计算过程，舍弃中间计算过程，只考察初始表和最终表：只考察初始表和最终表：N 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 X1 X2 2 3 0 0 -1 -5/3 -1/3 -8 -Z 2 3 3 0 0 0 -Z3/19/1 1 1 1 1 0 1 4 7 0 1 3 9 X4 X5 0 0 j 2 3 3 0 0 x x1 1 x x2 2 x x3 3 x x4 4

5、 x x5 5 Cj b xj XB CB2、价值系数、价值系数C发生变化的情况：发生变化的情况：（1）当）当cj是非基变量的价值系数是非基变量的价值系数它的变化只影它的变化只影响响 一个检验数一个检验数。为什麽？。为什麽？j例：例：c3发生变化时，发生变化时， =c3-z3=c3-2（-1）+32=c3-40，3得得c34。即当即当c34时，最优解不变；时，最优解不变；3否则否则 0,可使用可使用原始单纯形法原始单纯形法继续迭代求出新的最优继续迭代求出新的最优解。解。（2）当）当cj是基变量的价值系数是基变量的价值系数它的变化将影响它的变化将影响所有非基变量的检验数所有非基变量的检验数，为什

6、麽？，为什麽？NBCCBNN1 当当cj变化时，如能保持变化时，如能保持 ，则当前解仍为最优，则当前解仍为最优解，解，否则否则可用可用单纯形法单纯形法继续迭代继续迭代求出新的最优解求出新的最优解。0N将将cj看作待定参数，令看作待定参数，令 01NBCCBNN解这解这n-m个不等式，可算出保持最优解不变时个不等式，可算出保持最优解不变时cj的的变化范围变化范围 ！例：当例：当c1发生变化时，仍用发生变化时，仍用c1代表代表x1的价值系数（看的价值系数（看成待定参数），原最优表格即为：成待定参数），原最优表格即为： 0 1 2 -1/3 1/3 cjxj CB XB b c1 3 3 0 0 X

7、1 X2 X3 X4 X5 c1 3 X1 X2 1 21 0 -1 4/3 -1/3 -Z -c1-6 0 0 c1-3 1-4/3c1 1/3c1-1 令所有检验数小于令所有检验数小于0，得不等式组：，得不等式组：0131034103111ccc解该不等式组得：解该不等式组得： 3431 c说明当说明当 时，最优解不变。时，最优解不变。 3 , 4/31c当当c13时时,有有 ,可选可选x3或或 x5进基进基,x2出基出基.0131, 031513cc3、右端常数、右端常数b发生变化：发生变化： 当当bi发生变化时，将影响所有基变量的取值。为什麽？发生变化时，将影响所有基变量的取值。为什麽

8、？：bBXB1保持保持B-1b0,当前的基仍为最优基，最优解的结构当前的基仍为最优基，最优解的结构不变（取值改变）；不变（取值改变）；（B-1b）i0,当前基为非可行基当前基为非可行基,但是仍保持为对偶但是仍保持为对偶可行基可行基,(为什麽为什麽?),可用对偶单纯形法求出新的最优解；可用对偶单纯形法求出新的最优解；如何求出保持最优基不变的如何求出保持最优基不变的bi的范围的范围?把把bi看作待定参数看作待定参数,令令B-1b0,求解该不等式组即可；求解该不等式组即可； 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 X1 X2 2 3 0 0 -1 -5/3 -1/3 -

9、8 -Z 2 3 3 0 0 0 -Z3/19/1 1 1 1 1 0 1 4 7 0 1 3 9 X4 X5 0 0 j 2 3 3 0 0 x1 x2 x3 x4 x5 Cj b xj XB CB仍然来看上例的最优表格：仍然来看上例的最优表格： 9490330334333349313131349111011111bbbbbbbBb令该向量313131341B原原b1=3，现用待定参数现用待定参数b1代替代替3，则最优表中的解答列应为：则最优表中的解答列应为： 若若b1的变化超出这个范围，则解答列中至少有一个元的变化超出这个范围，则解答列中至少有一个元素小于素小于0，可用对偶单纯形法迭代求出

10、新的最优解。，可用对偶单纯形法迭代求出新的最优解。4、系数阵、系数阵A的元素发生变化：的元素发生变化：（1）增加）增加1个新变量：相当于系数阵个新变量：相当于系数阵A增加增加1列列 如开发出一种新产品，已知其有关工艺参数（或消如开发出一种新产品，已知其有关工艺参数（或消耗的资源量）和单位产品利润，设该种产品的产量为耗的资源量）和单位产品利润，设该种产品的产量为xk，则则ck和和Pk已知，需要进行已知，需要进行“是否投产是否投产”的决策。的决策。如例中欲增加产品如例中欲增加产品D，单件利润为单件利润为c6=5千元，工时消耗与材料消耗为千元，工时消耗与材料消耗为 326P相当于在原始表中增加相当于

11、在原始表中增加1列列P6，则在最优表中则在最优表中P6应应变成变成31353231313134616PBP相应的检验数：相应的检验数：323135) 3 , 2(5666166PCcPBCcBB在此基础上继续迭代，直至求出最优解：在此基础上继续迭代，直至求出最优解： 23 CB XB cj xjb j X1 X2 X3 X4 X5 X6 X1 X2 1 21/(5/3)2/(1/3) -Z -80 0 -1 -5/3 -1/3 2/3 5 3 X6X23/59/53/5 0 -3/5 4/5 -1/5 1-1/5 1 11/5 -3/5 2/5 0 -Z-42/5-2/5 0 -3/5 -11

12、/5 -1/5 0 2 3 3 0 0 5 1 0 -1 4/3 -1/3 5/3 0 1 2 -1/3 1/3 1/3q -Zq -80 0 -1 -5/3 -1/3 2/3-Z-42/52/5 0 -3/5 -11/5 -1/5 0说明新产品说明新产品D应于投产，新的生产计划为应于投产，新的生产计划为X*=(0,9/5,0,0,0,3/5)T,即生产即生产B产品产品5/9吨吨,生产生产D产产品品3/5吨吨,两种资源全部用完两种资源全部用完,可得到最大利润为可得到最大利润为8.4 (千元千元)( 42/5=8.4)。 如果算出的如果算出的60,说明新产品说明新产品D不宜投产，否不宜投产，否则会使产品总利润下降！则会使产品总利润下降！ q -Z CB XB cj xjb 2 3 3 0 0 5 X1 X2 X3 X4 X5 X6 2 3 0 X1 X2 X6 1 2 51 0 -1 4/3 -1/3 00 1 2 -1/3 1/3 02 2 1 0 0 1 2 3 0 X1 X2 X6 1 2 -11 0 -1 4/3 -1/3 00 1 2 -1