对偶问题四敏感性分析

2.4

灵敏度分析灵敏度分析目的灵敏度分析所要解决的问题：系数在什么范围内变化，不会影响已获得的最优基。如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。灵敏度分析内容※目标函数系数cj的改变※常数项bi的改变※技术系数aij的改变初始表和最优表的比较(一)初始表和最优表的比较(二)敏感性分析的三个公式1.目标函数系数cj的改变CBCNXBXNCB

XBIB-1NB-1b检验数0CN-CBB-1N非基变量在目标函数中系数的灵敏度分析基变量在目标函数中系数的灵敏度分析1.1非基变量价值系数的灵敏度分析maxz=-x1-x2+4x3s.t.x1+x2+2x3≤9x1+x2-x3≤2-x1+x2+x3≤4x1,x2,x3≥0在线性规划问题中，对c2进行灵敏度分析。-1-14000x1x2x3x4x5x6RHS-1x11-1/401/30-2/31/30x502001164x302/311/301/313/30-47/120-10-2得到以上问题的最优单纯形表：当c2’=c2+d时，相应的单纯形表为：-1-1+δ4000x1x2x3x4x5x6RHS-1x11-1/401/30-2/31/30x502001164x302/311/301/313/30d-47/120-10-212d

-

47

£

0要使原来的解仍保持最优解，就要zj-cj≤0（j=1,2,3,4,5），即12d

£

47212由此得到，d

£

47

，即当c

£35/12时，最优解保持不变1.2基变量价值系数的灵敏度分析maxz=-x1-x2+4x3s.t.x1+x2+2x3≤9x1+x2-x3≤2-x1+x2+x3≤4x1,x2,x3≥0在线性规划问题中，对c1进行灵敏度分析。-1-14000x1x2x3x4x5x6RHS-1x11-1/401/30-2/31/30x502001164x302/311/301/313/30-47/120-10-2得到以上问题的最优单纯形表：-1+δ-14000x1x2x3x4x5x6RHS-1+δx11-1/401/30-2/31/30x502001164x302/311/301/313/30-47/12-1/4d0-1+1/3d0-2-2/3d当c1’=c1+d时，相应的单纯形表为：-

2

-

2

/

3d

£

0

-1+1/

3d

£

0

-

4

-

1/3d

£

0要使原来的基仍保持最优基，就要zj-cj≤0（j=1,2,3,4,5），即

δ

‡

-3δ

£

3

δ

‡

-12由此得到，-3£d£3，即当-2£c1£4时，最优基保持不变2.右边常数的灵敏度分析CBCNXBXNCB

XBIB-1NB-1b检验数0CN-CBB-1N右边常数的灵敏度分析例maxz=-x1-x2+4x3s.t.x1+x2+2x3≤9x1-x1+x2+x2-x3+x3≤2≤4x1,x2,x3≥0在线性规划问题中，对b1进行灵敏度分析。-1-14000x1x2x3x4x5x6RHS0x411210090x511-101020x6-1110014-1-14000最优单纯形表-1-14000x1x2x3x4x5x6RHS-1x11-1/401/30-2/31/30x502001164x302/311/301/313/30-47/120-10-2初始单纯形表对于上述最优解，最优基为：B

=-10101

/3

0

-

2

/

3

11

/

31

/

3

b

=

B

-1b

=01

2=

61

/

31

/

3

41

/

3

0

-

2

/

3

9

1

/

3

1013

/

31

1

0 2

B

=

1

1

-1-1

0当b1’=b1+d=9+d时，最后一张单纯形表中的右边常数将成为

=

2

61/

3

4

1

11/

3

01/

313

/

3

+d

/

30

-

2

/

3

9+d

1/

3

+d

/

3

b

=

B-1b

=

0-1-14000x1x2x3x4x5x6RHS-1x11-1/401/30-2/31/3+δ/30x502001164x302/311/301/313/3+δ/30-47/120-10-2最后一张单纯形表中的右边常数将成为：原始可行条件为：

1

/

3

+

1

/

3d

‡

013

/

3

+

1

/

3d

‡

0

d

‡

-1d

‡

-13d‡-1，b1’=b1+d‡8时，原来的最优基仍为原始可行基3.增加一个新的变量增加一个新的变量x7，它在目标函数中的系数c7=1，在约束条件中的系数向量为：1a7

=

1

1求新的最优基和最优解。maxz=-x1-x2+4x3s.t.x1+x2+2x3≤9x1+x2-x3≤2-x1+x2+x3≤4x1,x2,x3≥0-1-14000x1x2x3x4x5x6RHS0x411210090x511-101020x6-1110014-1-14000最优单纯形表-1-14000x1x2x3x4x5x6RHS-1x11-1/401/30-2/31/30x502001164x302/311/301/313/30-47/120-10-2初始单纯形表对于上述最优解，最优基为：B

=-1011

/3

0

-

2

/

3

101

/

31

/

3

1

1

0 2

B

=

1

1

-1-1

0单纯形表中x7对应的系数：201

=

1/

3

10

-

2

/

31

-1/

3=

0

1

11/

3

01/

37B-1a加入x7后的单纯形表为：-1-140001x7x1x2x3x4x5x6RHS-1x11-1/401/30-2/3-1/3201/30x502001164x302/311/301/313/30-47/120-10-22/3……4.增加一个新的约束增加一个新的约束：-x1+2x2≥2，求新的最优基和最优解。maxz=-x1-x2+4x3s.t.x1+x2+2x3≤9x1+x2-x3≤2-x1+x2+x3≤4x1,x2,x3≥0-x1+2x2≥2-x1+2x2-x7=2x1-2x2+x7=-2在原最优单纯形表中加入新方程信息：-1-140000x7x1x2x3x4x5x6RHS-1x11-1/401/30-2/301/30x5020011064x302/311/301/3