线性规划的灵敏分析PPT学习教案

1、会计学1线性规划的灵敏分析线性规划的灵敏分析线性规划标准形式线性规划标准形式(1)、参数、参数A，b，C在什么范围内变动，对当前方案无影响？在什么范围内变动，对当前方案无影响？(2)、参数、参数A，b，C中的一个中的一个(几个几个)变动，对当前方案影响？变动，对当前方案影响？(3)、如果最优方案改变，如何用简便方法求新方案？、如果最优方案改变，如何用简便方法求新方案？ 0XbAXs.tCXzMax当线性规划问题中的一个或几个参数变化时，可以用单纯当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没形法从头计算，看最优解有无变化，但这样做既麻烦又没

2、有必要。有必要。灵敏度分析一词的含义是指对系统或事物因周围条件变化灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。显示出来的敏感程度的分析。第1页/共49页j1Bjj1BPBCCABCC 考虑检验数考虑检验数(1) 若若ck是非基变量的系数：是非基变量的系数： 解。解。，用单纯形法求解最优，用单纯形法求解最优代替代替否则，用否则，用原最优解不变；原最优解不变；时时即即当当则则设设kkkkkkkkkk1Bkkkkkkc0ccPBCcc,ccc 第2页/共49页 0 xx4x3xx2x3xx2xxs.t4x3x2xzMax5153214321321例例试求试求 c3 在

3、多大范围内变动时，原最优解保持不变。在多大范围内变动时，原最优解保持不变。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页/共49页从表中看到从表中看到3= c3+c3-(c2a13+c1a23 ) 可得到可得到c3 9/5 时，原最优解不变。时，原最优解不变。cj-2-3-4+c300B-1bcBxBx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5j00-9/5+c3-8/5-1/5-28/5第4页/共4

4、9页 解。解。，用单纯形法求解最优，用单纯形法求解最优代替代替否则，用否则，用原最优解不变；原最优解不变；时时即所有即所有所有的所有的当当则则为基变量的价值系数，为基变量的价值系数，设设jjrjrjjkrjkjjrjkjjkjjkBjjBjj1BjjkBkk1Bkkk,0aac0acacPc0Pc0CcPCcPBCcc0CcccC,ccc 第5页/共49页 0,xx124x164x82xxs.t3x2xZMax21212121求求c c2 2在什么范围在什么范围内变动时，原最内变动时，原最优解保持不变。优解保持不变。 下表为最优单纯形表下表为最优单纯形表,考虑基变量系数考虑基变量系数c2发生变

5、化发生变化C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2 -1/8014第6页/共49页从表中看到从表中看到可得到可得到 -3c21 时，原最优解不变。时，原最优解不变。1c08c813c02c232222即即即即C i23+c3000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143+c3 x2 011/2-1/802j00-3/2-c3/2 -1/8+ c3 /8014+2 c3第7页/共49页第8页/共49页 0,xx124x164x82xx

6、s.t3x2xzMax21212121求当求当b b1 1在由在由8 8变动为变动为1212时，原最优解是否时，原最优解是否保持不变，若变动求保持不变，若变动求出新的最优解。出新的最优解。解解: 下表为最优单纯形表下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2 -1/8014第9页/共49页 4-44224-80428-02440040812112120410244bBXbBbBbbBbBX0812112120410B111111则则由最优单纯形表可知：由最优单纯形表可知

7、：第10页/共49页将将b代入原最优单纯形表中，运用对偶单纯形法计算最优解。代入原最优单纯形表中，运用对偶单纯形法计算最优解。经一次迭代后，求得新的最优解经一次迭代后，求得新的最优解: ( 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第11页/共49页第12页/共49页0,xx124x164x82xxs.t3x2xzMax212

8、12121求当增加求当增加x6 , p6=( 2, 6, 3 )T, c6=5时，原最优解是否保时，原最优解是否保持不变，若变动求出新的持不变，若变动求出新的最优解。最优解。解解: 下表为最优单纯形表下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2 -1/8014第13页/共49页6666161p5c412233620812112120410pBp0812112120410B 算算代入最优单纯形表，计代入最优单纯形表，计与与将将则则由最优单纯形表可知：由最优单纯形表可知：第

9、14页/共49页用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：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/4015 x6 00-11/41/2123 x2 013/4-3/16-1/403/2j00-1/4 -7/160033/2第15页/共49页第16页/共49页0,xx124x164x82xxs.t3x2xzMax21212

10、121求当增加求当增加3x1+ 2x215时，时，原最优解是否保持不变，原最优解是否保持不变，若变动求出新的最优解。若变动求出新的最优解。解解: 下表为最优单纯形表下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2 -1/8014第17页/共49页经对偶单纯形法迭代一步，可得：经对偶单纯形法迭代一步，可得：最优解为最优解为(3.5, 2.25, 0, 0, 3, 2 )T，最优值为，最优值为 13. 75C i230000B-1bCBXBx1x2x3x4x5x62 x1 10

11、01/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/80014第18页/共49页第19页/共49页最优单纯形表最优单纯形表为为问：当问：当P3由由(-1 3)T改为改为(-1 2)T时最优解是否变化？时最优解是否变化？0 x,x,x,x,x4x3xx2x3xx2xxt . s4x3x2xzMax5432153214321321例例C i-2-3-400B-1bCBXBx

12、1x2x3x4x5-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第20页/共49页解：解：P P3 3由由(-1 (-1 3)3)T T改为改为(-1 (-1 2)2)T T 由最由单纯形表可知由最由单纯形表可知 32CB 51525251B1 022151525251324PBCc31B33 4c3 所以原最优解不变所以原最优解不变第21页/共49页第22页/共49页（2 2）P P1 1由由(-1 (-1 2)2)T T改为改为(1 (1 1)1)T T 由最优单纯形表可知由最优单纯形表可知 515252

13、51B1代入最优单纯形表，用代入最优单纯形表，用P1代替代替P1 53511151525251PBP111第23页/共49页C 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

14、最优值为：最优值为：-59/7第24页/共49页第25页/共49页第26页/共49页(1)目标函数的价值系数含有参数的线性规划问题目标函数的价值系数含有参数的线性规划问题 0XbAXt . sXCCZMax ABCCABCCABCABCCCABCCCC1B1B1B1B1BB bBCbBCbBCCZ1B1B1BB 第27页/共49页 求解步骤：求解步骤： 令令= 0，求得最优解与最优基，求得最优解与最优基 B； 根据根据 求得求得的区间；的区间； 运用单纯形法求得其余区间的最优解。运用单纯形法求得其余区间的最优解。 0 例例 0 x,x,x420 x4x460 x2x3430 xx2xt . s

15、x25x52x63zMax3212131321321 第28页/共49页解：解： 化为标准形；求化为标准形；求= 0 的最优解与最优基的最优解与最优基 B 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第29页/共49页 根据根据 求得求得的区间

16、的区间 0 0492025104414541 52411698524116 即当即当时最优解为时最优解为 401350Z20002301000XT C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52 x2 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-40第30页/共49页 运用单纯形法求得其余区间的最优解运用单纯形法求得其余区间的最优解当当52时时C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2

17、 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-4000 x4 -1/2201-1/2020025x33/20101/2023000 x6 140001420j-9/2200-5/201150j-9-500-10460最优解为最优解为 4601150Z420020023000XT 第31页/共49页当当时时4116 C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2 -1/4101/2-1/4010025x33/20101/2023000

18、 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/21/210j0005001310j000-31/423/80-285/222851310Z000215220510X41163120T 时，时，则当则当第32页/共49页当当时时1320 C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2 0101/4-1/81/8205/225x30013/2-1/4-3/4215-63x1 100-11/2

19、1/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/30-5/6-1/21780/3j0031/6019/125/4-3760/33376031780Z003430032003460X3120T ，时，时，则当则当第33页/共49页 4601150Z23000X52401350Z2301000X52411622851310Z215220510X411631203376031780Z032003460X3120 参变量的取值

20、范围与最优解为参变量的取值范围与最优解为第34页/共49页（2）右端常数含有参数的线性规划问题）右端常数含有参数的线性规划问题 0XbbAXt . sCXZMax XXbBbBbbBX111 求解步骤：求解步骤： 令令= 0，求得最优解与最优基，求得最优解与最优基B； 根据根据 求得求得的区间；的区间； 运用对偶单纯形法求得其余区间的最优解。运用对偶单纯形法求得其余区间的最优解。 0XXX 第35页/共49页例例 0 x,x,x4420 x4x4460 x2x3430 xx2xt . sx5x2x3ZMax3212131321321 解：解： 化为标准形；求化为标准形；求= 0 的最优解与最优

21、基的最优解与最优基 B 6 ,2 , 1j0 x4420 xx4x4460 xx2x3430 xxx2xt . sx5x2x3ZMaxj6215314321321 第36页/共49页 根据根据 求得求得的区间；的区间；则则= 0 时最优解为时最优解为(0 100 230 0 0 20)T 0XXX C i325000B-1bCBXBx1x2x3x4x5x62x2 -1/4101/2-1/401005x33/20101/202300 x6 200-21120j-400-1-201350第37页/共49页 201020b2320011502230b3200023100b321 71350Z1020

22、002230231000XT 最优解为最优解为C i325000B-1bb*CBXBx1x2x3x4x5x62x2 -1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-7第38页/共49页当当时最优单纯形表为时最优单纯形表为2 运用单纯形法求得其余区间的最优解。运用单纯形法求得其余区间的最优解。C i325000B-1bb*CBXBx1x2x3x4x5x62x2 -1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-72x

23、2 1/410001/4105-15x33/20101/20230-20 x4 -1001-1/21/2-105j-5000-5/2-1/21360-12时，最优解为时，最优解为 121360Z0051022301050XT 1052 当当第39页/共49页当当时最优单纯形表为时最优单纯形表为3200430 C i325000B-1bb*CBXBx1x2x3x4x5x62x2 -1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-70 x5 1-40-210-400-65x312110043010 x6 14

24、0-3/201420-4j-2-80-50021505最优解为最优解为 52150Z44206400043000XT 第40页/共49页参变量的取值范围与最优解为参变量的取值范围与最优解为 无可行解无可行解无可行解无可行解105121360Z00510-2-230-1050X105271350Z10-20002-230231000X2320052150Z4-4206-400-043000X3200430430TTT 第41页/共49页第五章作业题第五章作业题1、5、7、9、10（选（选2） 第42页/共49页 时的最优单纯形表为时的最优单纯形表为当当已知线性规划已知线性规划00 x,x,x,x

25、,x325x5x2x6x210 x3xxxt . s54x2x2xzMax200503205432153214321321 求所有最优解。求所有最优解。是否唯一？如果不唯一是否唯一？如果不唯一。并判断最优解。并判断最优解线性规划问题的最优解线性规划问题的最优解求当求当。，并求，并求填空完成上面单纯形表填空完成上面单纯形表02B11 CBXBx1x2x3x4x5b2x213100 x50-1-2100第43页/共49页 。完成单纯形表如下所示完成单纯形表如下所示解：解： 1CBXBx1x2x3x4x5b2x2-11310100 x580-1-21500-2-2020 知：知：量。由最优单纯形表可量。由最优单纯形表可，就相当于增加一个变，就相当于增加一个变当当02 代入单纯形表中计算。代入单纯形表中计算。需将需将 P172025PBC-c72321201PBP1201B1B11第44页/共49页Cj-224005bCBXBx1x2x3x4x52x2-113102100 x580-1-21-7500-2-201205-1/21/23/21