运筹学之灵敏度分析

1、第五章 线性规划灵敏度分析5.1 5.1 目标函数系数的灵敏度分析目标函数系数的灵敏度分析5.2 5.2 右端项的灵敏度分析右端项的灵敏度分析5.3 5.3 约束系数的灵敏度分析约束系数的灵敏度分析5.4 5.4 参数规划参数规划上表中上表中6个常数个常数 a1 , a2 , a3 , b , 1 , 2 取值在什么范围可使取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；、现基本解不可行；3、问题无可行解；、问题无可行解；4、无有限最优解；、无有限最优解；5、现基本解可行，由、现基本解可行，由 x1 取代取代 x6 目标函数可改善

2、。目标函数可改善。 cjB-1bcBxBx1x2x3x4x5x6x34a110a20bx4-1-501-102x6a3-300-413j1200-30线性规划标准形式线性规划标准形式(1)、参数、参数A，b，C在什么范围内变动，对当前方案无影响？在什么范围内变动，对当前方案无影响？(2)、参数、参数A，b，C中的一个中的一个(几个几个)变动，对当前方案影响？变动，对当前方案影响？(3)、如果最优方案改变，如何用简便方法求新方案？、如果最优方案改变，如何用简便方法求新方案？ 0XbAXs.tCXzMax当线性规划问题中的一个或几个参数变化时，可以用单纯当线性规划问题中的一个或几个参数变化时，可以

3、用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。有必要。灵敏度分析一词的含义是指对系统或事物因周围条件变化灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。显示出来的敏感程度的分析。5.1 目标函数系数的灵敏度分析j1Bjj1BPBCCABCC 考虑检验数考虑检验数(1) 若若ck是非基变量的系数：是非基变量的系数： 解。解。，用单纯形法求解最优，用单纯形法求解最优代替代替否则，用否则，用原最优解不变；原最优解不变；时时即即当当则则设设kkkkkkkkkk1Bkkkkkkc0ccPBCcc,ccc 解：

4、最优单纯形表解：最优单纯形表 0 xx4x3xx2x3xx2xxs.t4x3x2xzMax5153214321321例例试求试求 c3 在多大范围内变动时，原最优解保持不变。在多大范围内变动时，原最优解保持不变。cj-2-3-400B-1bcBxBx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5j00-9/5-8/5-1/5-28/5从表中看到从表中看到3= c3+c3-(c2a13+c1a23 ) 可得到可得到c3 9/5 时，原最优解不变。时，原最优解不变。cj-2-3-4c300B-1bcBxBx1x2x3x4x5-3x201-1/5

5、-2/51/52/5-2x1107/5-1/5-2/511/5j00-9/5+c3-8/5-1/5-28/5(2) 若若 ck 是基变量的系数是基变量的系数 解。解。，用单纯形法求解最优，用单纯形法求解最优代替代替否则，用否则，用原最优解不变；原最优解不变；时时即所有即所有所有的所有的当当则则为基变量的价值系数，为基变量的价值系数，设设jjrjrjjkrjkjjrjkjjkjjkBjjBjj1BjjkBkk1Bkkk,0aac0acacPc0Pc0CcPCcPBCcc0CcccC,ccc 例例 0,xx124x164x82xxs.t3x2xZMax21212121求求c c2 2在什么范围在什

6、么范围内变动时，原最内变动时，原最优解保持不变。优解保持不变。 下表为最优单纯形表下表为最优单纯形表,考虑基变量系数考虑基变量系数c2发生变化发生变化C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2 -1/8014从表中看到从表中看到可得到可得到 -3c21 时，原最优解不变。时，原最优解不变。1c08c813c02c232222即即即即C i23+c3000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143+c3 x2 011/2-1/802j00

7、-3/2-c3/2 -1/8+ c3 /8014+2 c3 设分量设分量 br 变化为变化为 br + br ，根据前面的讨论：，根据前面的讨论： 最优解的基变量最优解的基变量 xB = B-1b，那么只要保持，那么只要保持 B-1(b + b) 0 ， 则最优基不变，即基变量保持，只有值的变化；则最优基不变，即基变量保持，只有值的变化； 否则，需要利用对偶单纯形法继续计算。否则，需要利用对偶单纯形法继续计算。 5.2 右端项的灵敏度分析例例 0,xx124x164x82xxs.t3x2xzMax21212121求当求当b b1 1在由在由8 8变动为变动为1212时，原最优解是否保时，原最优

8、解是否保持不变，若变动求出持不变，若变动求出新的最优解。新的最优解。解解: 下表为最优单纯形表下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2 -1/8014 4-44224-80428-02440040812112120410244bBXbBbBbbBbBX0812112120410B111111则则由最优单纯形表可知：由最优单纯形表可知：将将b代入原最优单纯形表中，运用对偶单纯形法计算最优解。代入原最优单纯形表中，运用对偶单纯形法计算最优解。经一次迭代后，求得新的最优解

9、经一次迭代后，求得新的最优解: ( 4 3 2 0 0 )TC i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/21-43 x2 011/2-1/804j00-3/2 -1/80143/42 x1 1001/4040 x3 001-1/4-1/223 x2 01001/43j000-1/2-3/417(1) (1) 增加一个变量增加一个变量 增加一个变量，相当于系数矩阵增加一列。增加一个变量，相当于系数矩阵增加一列。 增加变量增加变量 xn+1 则有相应的则有相应的pn+1 ,cn+1 。 那么那么 计算出计算出B-1pn+1 , n+1=cn+

10、1-cB pn+1 填入最优单纯形表填入最优单纯形表, 若若 n+1 0 则则 最优解不变；最优解不变； 否则，进一步用单纯形法求解。否则，进一步用单纯形法求解。5.3 约束系数的灵敏度分析例例 0,xx124x164x82xxs.t3x2xzMax21212121求当增加求当增加x6 , p6=( 2, 6, 3 )T, c6=5时，原最优解是否保时，原最优解是否保持不变，若变动求出新的持不变，若变动求出新的最优解。最优解。解解: 下表为最优单纯形表下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2

11、-1/802j00-3/2 -1/80146666161p5c412233620812112120410pBp0812112120410B 算算代入最优单纯形表，计代入最优单纯形表，计与与将将则则由最优单纯形表可知：由最优单纯形表可知：用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5C i230005B-1bCBXBx1x2x3x4x5x62 x1 1001/403/248/30 x5 00-21/212423 x2 011/2-1/801/428j00-3/2 -1/805/4142 x1 103/2-1/8-3/40

12、15 x6 00-11/41/2123 x2 013/4-3/16-1/403/2j00-1/4 -7/160033/2(2) (2) 增加一个约束条件增加一个约束条件 增加一个约束条件相当于系数矩阵中增加一行。增加一个约束条件相当于系数矩阵中增加一行。 增加一个约束条件之后，应把最优解带入新的增加一个约束条件之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量

13、），并通过矩阵行量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为变换把对应基变量的元素变为0 0，进一步用单纯，进一步用单纯形法或对偶单纯形法求解。形法或对偶单纯形法求解。例例 0,xx124x164x82xxs.t3x2xzMax21212121求当增加求当增加3x1+ 2x215时，时，原最优解是否保持不变，原最优解是否保持不变，若变动求出新的最优解。若变动求出新的最优解。解解: 下表为最优单纯形表下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2 -1

14、/8014将将3x1+ 2x2+ x6=15 代入原最优单纯形表。代入原最优单纯形表。经对偶单纯形法迭代一步，可得：经对偶单纯形法迭代一步，可得：最优解为最优解为(3.5, 2.25, 0, 0, 3, 2 )T，最优值为，最优值为 13. 75C i230000B-1bCBXBx1x2x3x4x5x62 x1 1001/40040 x5 00-21/21043 x2 011/2-1/80020 x632000115j00-3/2 -1/800142 x1 1001/40040 x5 00-21/21043 x2 011/2-1/80020 x600-1-1/201-1j00-3/2 -1/8

15、0014(3) (3) 技术系数改变技术系数改变(计划生产的产品工艺结构改变计划生产的产品工艺结构改变) 非基变量非基变量xj工艺改变工艺改变只影响单纯形表只影响单纯形表Pj 列列， j .关键看关键看 j 0? 还是还是0? . 用增加新变量类似方用增加新变量类似方法解决。法解决。 基变量基变量xj工艺改变，复杂，在此暂不予讨论。工艺改变，复杂，在此暂不予讨论。最优单纯形表为最优单纯形表为（1）P3由由(-1 3)T改为改为(-1 2)T（2）P1由由(-1 2)T改为改为(1 1)T0 x,x,x,x,x4x3xx2x3xx2xxt . s4x3x2xzMax543215321432132

16、1例例C i-2-3-400B-1bCBXBx1x2x3x4x5-3 x2 01-1/5-2/51/52/5-2 x1 107/5-1/5-2/511/5j00-9/5 -8/5-1/5-28/5解：（解：（1 1）P P3 3由由(-1 (-1 3)3)T T改为改为(-1 (-1 2)2)T T 由最由单纯形表可知由最由单纯形表可知 32CB 51525251B1 022151525251324PBCc31B33 4c3 所以原最优解不变所以原最优解不变（2 2）P P1 1由由(-1 (-1 2)2)T T改为改为(1 (1 1)1)T T 由最优单纯形表可知由最优单纯形表可知 5152

17、5251B1代入最优单纯形表，用代入最优单纯形表，用P1代替代替P1 53511151525251PBP111C i-2-3-400B-1bCBXBx1x2x3x4x5-3 x2 -3/51-1/5-2/51/52/5-2 x1 1/507/5-1/5-2/511/5j-28/5-3 x2 014-1-177/4-2 x1 107-1-21111/7j0022 -5-7-43-3 x2 -4/710-3/71/75/7-4 x3 1/701-1/7-2/711/7j-22/700-13/7-5/7-59/7所以，新的最优解为所以，新的最优解为:(0,5/7,11/7,0,0)T 最优值为：最优

18、值为：-59/75.4 参数线性规划n在线性规划的实际应用中，由于某种原因，线性规划在线性规划的实际应用中，由于某种原因，线性规划问题的目标函数的价值系数问题的目标函数的价值系数C和约束条件的右端常数和约束条件的右端常数b会随着某个参数而连续变动。会随着某个参数而连续变动。n当数据随着某个参数连续变化时，研究其对最优解的当数据随着某个参数连续变化时，研究其对最优解的影响，即为参数线性规划问题。影响，即为参数线性规划问题。v目标函数的价值系数含有参数的线性规划问题目标函数的价值系数含有参数的线性规划问题v右端常数含有参数的线性规划问题右端常数含有参数的线性规划问题(1)目标函数的价值系数含有参数

19、的线性规划问题目标函数的价值系数含有参数的线性规划问题 0XbAXt . sXCCZMax ABCCABCCABCABCCCABCCCC1B1B1B1B1BB bBCbBCbBCCZ1B1B1BB 求解步骤：求解步骤： 令令= 0，求得最优解与最优基，求得最优解与最优基 B； 根据根据 求得求得的区间；的区间； 运用单纯形法求得其余区间的最优解。运用单纯形法求得其余区间的最优解。 0 例例 0 x,x,x420 x4x460 x2x3430 xx2xt . sx25x52x63zMax3212131321321 解：解： 化为标准形；求化为标准形；求= 0 的最优解与最优基的最优解与最优基 B

20、 6 ,2 ,1j0 x420 xx4x460 xx2x3430 xxx2xt . sx25x52x63ZMaxj6215314321321 则则= 0 时最优解为时最优解为(0 100 230 0 0 20)T C i325000B-1bCBXBx1x2x3x4x5x62x2 -1/4101/2-1/401005x33/20101/202300 x6 200-21120j-400-1-201350 根据根据 求得求得的区间的区间 0 0492025104414541 52411698524116 即当即当时最优解为时最优解为 401350Z20002301000XT C i-6-52000B

21、-1bC i325000CBCBXBx1x2x3x4x5x6-52 x2 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-40 运用单纯形法求得其余区间的最优解运用单纯形法求得其余区间的最优解当当52时时C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-4000 x4 -1/220

22、1-1/2020025x33/20101/2023000 x6 140001420j-9/2200-5/201150j-9-500-10460最优解为最优解为 4601150Z420020023000XT 当当时时4116 C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-40-52x2 0101/4-1/81/8205/225x30013/2-1/4-3/4215-63x1 100-11/

23、21/210j0005001310j000-31/423/80-285/222851310Z000215220510X41163120T 时，时，则当则当当当时时1320 C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2 0101/4-1/81/8205/225x30013/2-1/4-3/4215-63x1 100-11/21/210j0005001310j000-31/423/80-285/2-52x2 01-1/60-1/121/4200/300 x4002/31-1/6-1/2430/3-63x1 102/301/30460/3j0010/

24、30-5/6-1/21780/3j0031/6019/125/4-3760/33376031780Z003430032003460X3120T ，时，时，则当则当 4601150Z23000X52401350Z2301000X52411622851310Z215220510X411631203376031780Z032003460X3120 参变量的取值范围与最优解为参变量的取值范围与最优解为（2）右端常数含有参数的线性规划问题）右端常数含有参数的线性规划问题 0XbbAXt . sCXZMax XXbBbBbbBX111 求解步骤：求解步骤： 令令= 0，求得最优解与最优基，求得最优解与最优

25、基B； 根据根据 求得求得的区间；的区间； 运用对偶单纯形法求得其余区间的最优解。运用对偶单纯形法求得其余区间的最优解。 0XXX 例例 0 x,x,x4420 x4x4460 x2x3430 xx2xt . sx5x2x3ZMax3212131321321 解：解： 化为标准形；求化为标准形；求= 0 的最优解与最优基的最优解与最优基 B 6 ,2 , 1j0 x4420 xx4x4460 xx2x3430 xxx2xt . sx5x2x3ZMaxj6215314321321 根据根据 求得求得的区间；的区间；则则= 0 时最优解为时最优解为(0 100 230 0 0 20)T 0XXX

26、C i325000B-1bCBXBx1x2x3x4x5x62x2 -1/4101/2-1/401005x33/20101/202300 x6 200-21120j-400-1-201350 201020b2320011502230b3200023100b321 71350Z1020002230231000XT 最优解为最优解为C i325000B-1bb*CBXBx1x2x3x4x5x62x2 -1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-7当当时最优单纯形表为时最优单纯形表为2 运用单纯形法求得其余

27、区间的最优解。运用单纯形法求得其余区间的最优解。C i325000B-1bb*CBXBx1x2x3x4x5x62x2 -1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-72x2 1/410001/4105-15x33/20101/20230-20 x4 -1001-1/21/2-105j-5000-5/2-1/21360-12时，最优解为时，最优解为 121360Z0051022301050XT 1052 当当当当时最优单纯形表为时最优单纯形表为3200430 C i325000B-1bb*CBXBx1x

28、2x3x4x5x62x2 -1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-70 x5 1-40-210-400-65x312110043010 x6 140-3/201420-4j-2-80-50021505最优解为最优解为 52150Z44206400043000XT 参变量的取值范围与最优解为参变量的取值范围与最优解为 无可行解无可行解无可行解无可行解105121360Z00510-2-230-1050X105271350Z10-20002-230231000X2320052150Z4-4206-4

29、00-043000X3200430430TTT 第五章作业题第五章作业题1、5、7、9、10（选（选2） 时的最优单纯形表为时的最优单纯形表为当当已知线性规划已知线性规划00 x,x,x,x,x325x5x2x6x210 x3xxxt . s54x2x2xzMax200503205432153214321321 求所有最优解。求所有最优解。是否唯一？如果不唯一是否唯一？如果不唯一。并判断最优解。并判断最优解线性规划问题的最优解线性规划问题的最优解求当求当。，并求，并求填空完成上面单纯形表填空完成上面单纯形表02B11 CBXBx1x2x3x4x5b2x213100 x50-1-2100 。完成单纯形表如下所示完成单纯形表如下所示解：解： 1CBXBx1x2x3x4x5b2x2-11310100 x580-1-21500-2-2020 知：知：量。由最优单纯形表可量。由最