第三章 对偶理论和灵敏度分析(第7-8节)

1、第第1页页以前讨论线性规划问题时，假定以前讨论线性规划问题时，假定aij , bi , cj 都是常数。都是常数。 市场条件变化市场条件变化 cj 值发生变化值发生变化 工艺技术条件变化工艺技术条件变化 a i j 值发生变化值发生变化 资源投入后产生的经济效果的变化资源投入后产生的经济效果的变化 bi 值发生变化值发生变化 实际上，这些系数往往都是估计值和预测值，而不是实际上，这些系数往往都是估计值和预测值，而不是已知数。已知数。第第2页页因此提出以下问题：因此提出以下问题：当这些参数中的一个或几个发生变化时，问题的当这些参数中的一个或几个发生变化时，问题的最优解会发生什么变化。最优解会发生

2、什么变化。这些参数在多大范围内变化时，问题的最优解不这些参数在多大范围内变化时，问题的最优解不变。变。 上述问题就是灵敏度分析所要研究解决的内容。上述问题就是灵敏度分析所要研究解决的内容。 第第3页页解决上述问题的方法：解决上述问题的方法：1. 用单纯形法从头计算，求得新的最优解。用单纯形法从头计算，求得新的最优解。2. 只计算发生变化的个别系数，并直接填入最只计算发生变化的个别系数，并直接填入最终单纯形表中。终单纯形表中。 第第4页页灵敏度分析的步骤灵敏度分析的步骤1. 将参数的改变直接反映到最终单纯形表上来：将参数的改变直接反映到最终单纯形表上来：按下列公式分别计算参数按下列公式分别计算参

3、数 bi、cj、aij、的变化而引、的变化而引起的最终单纯形表的变化：起的最终单纯形表的变化： bBbb 1njaccccaccmiijiijjmiijij,.,1,)()(11 jjPBP 1第第5页页2. 检验原问题是否仍然为可行解（检验最终单纯形检验原问题是否仍然为可行解（检验最终单纯形表的表的 b 列）；列）；3. 检验对偶问题是否仍然为可行解（检验最终单纯检验对偶问题是否仍然为可行解（检验最终单纯形表的检验数行）；形表的检验数行）；4. 按下表继续计算步骤：按下表继续计算步骤： 第第6页页原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解问题

4、的最优解或最优基不变问题的最优解或最优基不变可行解可行解非可行解非可行解用用单纯形法单纯形法继续跌代求出最优解继续跌代求出最优解非可行解非可行解可行解可行解用用对偶单纯形法对偶单纯形法继续跌代求出最继续跌代求出最优解优解非可行解非可行解非可行解非可行解引入引入人工变量人工变量，编制新的单纯形，编制新的单纯形表，求出最优解表，求出最优解第第7页页将右端常数将右端常数 bi 的变化反映到最终单纯形表上：的变化反映到最终单纯形表上：bBbb 1b 列数字的变化：列数字的变化： 最终单纯形表出现的情况：最终单纯形表出现的情况：1. 第一种情况出现：问题的最优基不变，变化后的第一种情况出现：问题的最优基

5、不变，变化后的 b 列列为最优解。为最优解。2. 第三种情况出现：用对偶单纯形法继续找出最优解。第三种情况出现：用对偶单纯形法继续找出最优解。 第第8页页 0,1241648232max21212121xxxxxxxxz例例 原问题的初始单纯形表：原问题的初始单纯形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j z j23000第第9页页cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/80（1）b1在什么范

6、围变化时，问题的最优基不发生变化。在什么范围变化时，问题的最优基不发生变化。（2）若）若b1增加增加4，其他不变，求该厂的最优生产方案。，其他不变，求该厂的最优生产方案。 原问题的最终单纯形表：原问题的最终单纯形表： 第第10页页解：解：（1）当）当 01 bBb时，最优基不发生变化时，最优基不发生变化 1 B1410004201 08/12/112/1204/10 001bb 1112/120bbbB第第11页页 bBb1 112/120244bb02/1224411 bb241 b即即 b1 可以在可以在 4，10 之间变化，而不影响最优基。之间变化，而不影响最优基。 第第12页页（2）

7、1 B1410004201 08/12/112/1204/10 004b 2801bB，将其反映到最终单纯形表中：，将其反映到最终单纯形表中： 第第13页页cj23000iCBXBbx1x2x3x4x52x141001/400 x5-400 -2 1/213x24011/2-1/80c j z j00-3/2-1/80即出现了第三种情况（原问题不可行，对偶问题可即出现了第三种情况（原问题不可行，对偶问题可行）利用对偶单纯形法：行）利用对偶单纯形法： 第第14页页cj23000iCBXBbx1x2x3x4x52x141001/400 x32001-1/4-1/23x2401001/4c j z

8、j000-1/2-3/4出现了第一种情况（原问题可行，对偶问题也可行出现了第一种情况（原问题可行，对偶问题也可行），问题达到最优。），问题达到最优。 第第15页页将目标函数系数将目标函数系数 cj 的变化反映到最终单纯形表上：的变化反映到最终单纯形表上： 检验数行（检验数行（cj - zj）的变化：）的变化： njaccccaccmiijiijjmiijij,.,1,)()(11 最终单纯形表出现的情况：最终单纯形表出现的情况：1. 第一种情况出现：问题的最优解不变。第一种情况出现：问题的最优解不变。2. 第二种情况出现：用单纯形法继续跌代求出最优解。第二种情况出现：用单纯形法继续跌代求出最优

9、解。 第第16页页 0,1241648232max21212121xxxxxxxxz例例 原问题的初始单纯形表：原问题的初始单纯形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j z j23000第第17页页cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/80原问题的最终单纯形表：原问题的最终单纯形表： （1）c2 在什么范围变化时，问题的最优解不发生变化。在什么范围变化时，问题的最优解不发生变化。（2）若）

10、若 c2 增加增加2，其他不变，求该厂的最优生产方案。，其他不变，求该厂的最优生产方案。 第第18页页解：解：（1）当）当 njaccmiijij,.,1, 01 时，最优解不发生变化时，最优解不发生变化 cj23+c2000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213+c2x22011/2-1/80c j z j00022123c 28181c 第第19页页021232 c081812 c132 c即即 c2 可以在可以在0，4之间变化，而不影响最优解。之间变化，而不影响最优解。 （2） cj25000iCBXBbx1x2x3x4x52x141001/4

11、00 x5400-2 1/2 15x22011/2-1/80c j z j00-5/21/80第第20页页cj25000iCBXBbx1x2x3x4x52x121010-1/20 x4800-4125x2301001/4c j z j00-20-1/4即出现了第二种情况（原问题可行，对偶问题不可行即出现了第二种情况（原问题可行，对偶问题不可行）利用单纯形法：）利用单纯形法： 第第21页页1. 增加一个新变量增加一个新变量 xj 的变化分析的变化分析 将增加一个新变量将增加一个新变量 xj 的变化反映到最终单纯形表上：的变化反映到最终单纯形表上： （1）增加一列）增加一列 （2）该列的检验数）该

12、列的检验数 （3）按下表进行：）按下表进行： jPB1 jBjjPBCc1 第第22页页原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解问题的最优解或最优基不变问题的最优解或最优基不变可行解可行解非可行解非可行解用单纯形法继续跌代求出最优解用单纯形法继续跌代求出最优解非可行解非可行解可行解可行解用对偶单纯形法继续跌代求出最用对偶单纯形法继续跌代求出最优解优解非可行解非可行解非可行解非可行解引入人工变量，编制新的单纯形引入人工变量，编制新的单纯形表，求出最优解表，求出最优解第第23页页 0,1241648232max21212121xxxxxxxxz例

13、例 原问题的初始单纯形表：原问题的初始单纯形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j z j23000第第24页页cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/80原问题的最终单纯形表：原问题的最终单纯形表： 如果增加变量如果增加变量 x6 ，其对应目标函数系数，其对应目标函数系数 c6 =5 , 其对应约束条件系数列向量为其对应约束条件系数列向量为P6= ( 2 , 6 , 3 )T。问题的最优解

14、为多少？问题的最优解为多少？ 第第25页页解：解：x6 为新变量。为新变量。 （1） 11410004201 B 08 / 12/ 112/ 1204 / 10 3626P61PB 4/122/3 第第26页页（2） 6166PBCcB 36208/12/112/1204/103025 45/ 第第27页页（3） cj230005iCBXBbx1x2x3x4x5x62x141001/403/28/30 x5400-21/21 2 23x22011/2-1/801/48c j z j00-3/2-1/805/4即出现了第二种情况（原问题可行，对偶问题不可即出现了第二种情况（原问题可行，对偶问题不

15、可行）利用单纯形法：行）利用单纯形法： 第第28页页cj230005iCBXBbx1x2x3x4x5x62x11103/2-1/8-3/405x6200-11/41/213x23/2013/4-3/16-1/80c j z j00-1/4-7/16-5/80出现了第一种情况（原问题可行，对偶问题也可行出现了第一种情况（原问题可行，对偶问题也可行），问题达到最优。），问题达到最优。 第第29页页2. 原变量原变量 xj（ xj 在最终单纯形表中为非基变量）在最终单纯形表中为非基变量）参数参数 aij 的变化分析的变化分析 将变量将变量 xj 的变化反映到最终单纯形表上：的变化反映到最终单纯形表上

16、： （1）增加一列）增加一列 （2）该列的检验数）该列的检验数 jPB 1jBjjPBCc 1 第第30页页（3）在最终单纯形表中用）在最终单纯形表中用 列替代列替代 xj 列，将列，将 xj 列列从最终单纯形表中删除（并不影响基矩阵），并按从最终单纯形表中删除（并不影响基矩阵），并按下表进行：下表进行： jx 原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解问题的最优解或最优基不变问题的最优解或最优基不变可行解可行解非可行解非可行解用单纯形法继续跌代求出最优解用单纯形法继续跌代求出最优解非可行解非可行解可行解可行解用对偶单纯形法继续跌代求出最用对偶

17、单纯形法继续跌代求出最优解优解非可行解非可行解非可行解非可行解引入人工变量，编制新的单纯形引入人工变量，编制新的单纯形表，求出最优解表，求出最优解第第31页页例例 max z = 2x1 + 3x2 0,12 4 16 452 .32121321xxxxxxxxts原问题的初始单纯形表：原问题的初始单纯形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j z j23000第第32页页cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z

18、j00-3/2-1/80原问题的最终单纯形表：原问题的最终单纯形表： 如果变量如果变量 x3 的目标函数系数变为的目标函数系数变为 2523P变量变量 x3 对应的约束条件系数列向量变为对应的约束条件系数列向量变为43 c问题的最优解为多少？问题的最优解为多少？ 第第33页页解：解：x3 在最终单纯形表中为非基变量。在最终单纯形表中为非基变量。 （1） 11410004201 B 08 / 12/ 112/ 1204 / 10 2523P31PB 8/32/14/5 第第34页页（2） 25208/12/112/1204/103024 83/ 3133PBCcB （3）在最终单纯形表中用）在最

19、终单纯形表中用 列替代列替代 x3列，并不再列，并不再保留保留 x3 ： 3x 第第35页页cj23400iCBXBbx1x2x4x52x14105/41/408/50 x54001/21/2183x22013/8-1/8016/3c j z j003/8-1/80即出现了第二种情况（原问题可行，对偶问题不可即出现了第二种情况（原问题可行，对偶问题不可行）利用单纯形法：行）利用单纯形法： 3x 第第36页页cj23400iCBXBbx1x2x4x5416/54/5011/500 x512/5 -2/5 002/513x24/5-3/1010-1/50c j z j-3/1000-1/503x

20、出现了第一种情况（原问题可行，对偶问题也可行出现了第一种情况（原问题可行，对偶问题也可行），问题达到最优。），问题达到最优。 3x 第第37页页3. 原变量原变量 xj（ xj 在最终单纯形表中为基变量）参在最终单纯形表中为基变量）参数数 aij 的变化分析的变化分析 将变量将变量 xj 的变化反映到最终单纯形表上：的变化反映到最终单纯形表上： （1）增加一列）增加一列 jPB 1（2）在最终单纯形表中用）在最终单纯形表中用 列替代列替代 xj 列，将列，将 xj 列列从最终单纯形表中删除（基矩阵受影响）；从最终单纯形表中删除（基矩阵受影响）；jx 第第38页页原问题原问题对偶问题对偶问题结论

21、或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解问题的最优解或最优基不变问题的最优解或最优基不变可行解可行解非可行解非可行解用单纯形法继续跌代求出最优解用单纯形法继续跌代求出最优解非可行解非可行解可行解可行解用对偶单纯形法继续跌代求出最用对偶单纯形法继续跌代求出最优解优解非可行解非可行解非可行解非可行解引入人工变量，编制新的单纯形引入人工变量，编制新的单纯形表，求出最优解表，求出最优解（3）将）将变为基变量，并将变为基变量，并将 列变为单位矩阵，列变为单位矩阵，重新计算各变量的检验数，并按下表进行：重新计算各变量的检验数，并按下表进行： jx jx 第第39页页例例 0,12416

22、482 .32max21212121xxxxxxtsxxz原问题的初始单纯形表：原问题的初始单纯形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j z j23000第第40页页如果变量如果变量 x1 的目标函数系数变为的目标函数系数变为 2521P变量变量 x1 对应的约束条件系数列向量变为对应的约束条件系数列向量变为41 c问题的最优解为多少？问题的最优解为多少？ cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2

23、-1/80原问题的最终单纯形表：原问题的最终单纯形表： 第第41页页解：解：x1 在最终单纯形表中为基变量。在最终单纯形表中为基变量。 （1） 11410004201 B 08 / 12/ 112/ 1204 / 10 2521P11PB 8/32/14/5 第第42页页cj43000iCBXBbx2x3x4x52x145/4001/400 x541/20-21/213x223/811/2-1/80c j z j1x （2）在最终单纯形表中用）在最终单纯形表中用 列替代列替代 x1列，并不再列，并不再保留保留 x1 ： 1x 第第43页页cj43000iCBXBbx2x3x4x5416/510

24、01/500 x512/500-22/513x24/5011/2-1/50c j z j00-3/2-1/50出现了第一种情况（原问题可行，对偶问题也可行出现了第一种情况（原问题可行，对偶问题也可行），问题达到最优。），问题达到最优。 （3）将）将列变换为单位向量，并重新计算检验数：列变换为单位向量，并重新计算检验数： 1x 1x 1x 第第44页页例例 0,12416482 .32max21212121xxxxxxtsxxz原问题的初始单纯形表：原问题的初始单纯形表： cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j

25、 z j23000第第45页页如果变量如果变量 x1 的目标函数系数变为的目标函数系数变为变量变量 x1 对应的约束条件系数列向量变为对应的约束条件系数列向量变为41 c问题的最优解为多少？问题的最优解为多少？ cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/80原问题的最终单纯形表：原问题的最终单纯形表： 2541P第第46页页解：解：x1 在最终单纯形表中为基变量。在最终单纯形表中为基变量。 （1） 11410004201 B 08 / 12/ 112/ 1204 / 10 2541P

26、11PB 8/112/74/5 第第47页页cj43000iCBXBbx2x3x4x52x145/4001/408/50 x54-7/20-21/2183x2211/811/2-1/8016/3c j z j（2）在最终单纯形表中用）在最终单纯形表中用 列替代列替代 x1列，并不再列，并不再保留保留 x1 ： 1x 1x 第第48页页cj43000iCBXBbx2x3x4x5416/51001/500 x576/500-26/513x2-12/5011/2-2/50c j z j00-3/22/50出现了第四种情况（原问题不可行，对偶问题也不出现了第四种情况（原问题不可行，对偶问题也不可行），

27、需引入人工变量。可行），需引入人工变量。 （3）将）将列变换为单位向量，并重新计算检验数：列变换为单位向量，并重新计算检验数： 1x 1x 1x 第第49页页因为因为 x2 为不可行解，故需要在为不可行解，故需要在 x2 所在行引入人工变量。所在行引入人工变量。 x2 + 1/2x3 - 2/5x4 = - 12/5 为了确保原问题的解为可行解，需要使约束条件右端为了确保原问题的解为可行解，需要使约束条件右端常数为正，从而必须常数为正，从而必须 将将 x2 所在行的等式两边乘以所在行的等式两边乘以 - 1： -x2 - 1/2x3 + 2/5x4 = 12/5 为凑出基变量来替换为凑出基变量来

28、替换 x2（因此此时（因此此时 x2 的列向量已经的列向量已经不是单位向量），从而需引入人工变量不是单位向量），从而需引入人工变量 x6： -x2 - 1/2x3 + 2/5x4 +x6 = 12/5 第第50页页cj43000-MiCBXBbx2x3x4x5x6416/51001/500-0 x576/500-26/510-Mx612/50-1-1/2 2/5 016c j z j03-M -1/2M 2/5M-4/5 001x 即出现了第二种情况（原问题可行，对偶问题不可即出现了第二种情况（原问题可行，对偶问题不可行）利用单纯形法：行）利用单纯形法： 1x 第第51页页cj43000-Mi

29、CBXBbx2x3x4x5x64211/21/4001/240 x580 3 -1/201-38/30 x460-5/2-5/4105/2-c j z j01-1 0 02-M 1x 仍然是第二种情况（原问题可行，对偶问题不可行仍然是第二种情况（原问题可行，对偶问题不可行），继续利用单纯形法：），继续利用单纯形法： 1x 第第52页页cj43000-MiCBXBbx2x3x4x5x642/3101/30-1/603x28/30 1 -1/601/3-10 x438/300-5/315/60c j z j00-5/6 0-1/3 3-M 出现了第一种情况（原问题可行，对偶问题也可行出现了第一种情

30、况（原问题可行，对偶问题也可行），问题达到最优。），问题达到最优。 1x 1x 第第53页页4. 增加一个约数条件的变化分析增加一个约数条件的变化分析 将增加的一个约数条件的变化反映到最终单纯形表将增加的一个约数条件的变化反映到最终单纯形表上：上：（1）将原问题最终单纯形表中得出的最优解带入新）将原问题最终单纯形表中得出的最优解带入新增加的约束条件；增加的约束条件；（2）如满足：则说明新增加的约束条件未起到限制）如满足：则说明新增加的约束条件未起到限制作用，原最优解不变；作用，原最优解不变； （3）如不满足：）如不满足：第第54页页引入松弛变量或剩余变量将该约束条件化为等式；引入松弛变量或剩余

31、变量将该约束条件化为等式；将该等式加入到原最终单纯形表的最后一行，重新将该等式加入到原最终单纯形表的最后一行，重新计算检验数，并按下表进行：计算检验数，并按下表进行： 原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解问题的最优解或最优基不变问题的最优解或最优基不变可行解可行解非可行解非可行解用单纯形法继续跌代求出最优解用单纯形法继续跌代求出最优解非可行解非可行解可行解可行解用对偶单纯形法继续跌代求出最用对偶单纯形法继续跌代求出最优解优解非可行解非可行解非可行解非可行解引入人工变量，编制新的单纯形引入人工变量，编制新的单纯形表，求出最优解表，求出最优解

32、第第55页页 0,524261552max212121221xxxxxxxxxz例例 第第56页页原问题的最终单纯形表：原问题的最终单纯形表： cj21000iCBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2c j z j000-1/4-1/2如果增加约束条件如果增加约束条件 3x1 + 2x2 12，求最优解？，求最优解？ 第第57页页解：解： 原问题最优解为原问题最优解为 x1 =7/2，x2=3/2，代入约束条件代入约束条件 3x1+2x212 不满足，故原问题不满足，故原问题最优解发生变化。最优解发生变

33、化。引入松弛变量引入松弛变量 x6 将约束条件化为等式：将约束条件化为等式： 3x1 + 2x2 + x6 = 12将其加入到最优单纯形表的最后一行。将其加入到最优单纯形表的最后一行。第第58页页cj210000iCBXBbx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x612320001c j z j第第59页页将将x1、x2列变为单位向量，并重新计算检验数：列变为单位向量，并重新计算检验数： cj210000iCBXBbx1x2x3x4x5x60 x315/20015/4-15/202x17/2100

34、1/4-1/201x23/2010-1/43/200 x6-3/2000-1/4-3/21c j z j000-1/4-1/20即出现了第三种情况（原问题不可行，对偶问题可即出现了第三种情况（原问题不可行，对偶问题可行）利用对偶单纯形法：行）利用对偶单纯形法： 第第60页页cj210000iCBXBbx1x2x3x4x5x60 x3150015/20-52x141001/30-1/31x20010-1/2010 x510001/61-2/3c j z j000-1/60-1/3出现了第一种情况（原问题可行，对偶问题也可行出现了第一种情况（原问题可行，对偶问题也可行），问题达到最优。），问题达到

35、最优。 第第61页页参数线性规划是研究参数（参数线性规划是研究参数（C、b）中某一参数连续变）中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量：参数作为参变量：目标函数在某区间内是这个参变量的线性函数。目标函数在某区间内是这个参变量的线性函数。约束条件在某区间内是这个参变量的线性不等式。约束条件在某区间内是这个参变量的线性不等式。第第62页页若若 C 按按(C+ C*) 或或 b 按按(b+b*)连续变化，而目标函数值连续变化，而目标函数值 z 是参数是参数的线性函数时，下式称为参数线性规划：的线性函数时，下式称为参数线

36、性规划： 0.) ( max*XbAXtsXCCz 0.max*XbbAXtsCXz 第第63页页参数线性规划问题的分析步骤：参数线性规划问题的分析步骤：（1）令）令= 0 求解得最终单纯形表；求解得最终单纯形表；（2）将）将C* 或或b* 项反映到最终单纯形表中去；项反映到最终单纯形表中去；（3）随）随值的增大或减小，观察原问题或对偶问题：值的增大或减小，观察原问题或对偶问题： 确定表中现有解（基）允许确定表中现有解（基）允许的变动范围。的变动范围。 当当变动超出该范围时，用单纯形法或对偶单纯变动超出该范围时，用单纯形法或对偶单纯形法求取新的解。形法求取新的解。（4）重复步骤（）重复步骤（3

37、），直到继续增大或减小时，表中），直到继续增大或减小时，表中的解（基）不再出现变化为止。的解（基）不再出现变化为止。第第64页页 0,52426155)21()2( max212121221xxxxxxxxxz 例例 分析分析值变化时，下述参数线性规划问题最优值变化时，下述参数线性规划问题最优解得变化。解得变化。 第第65页页解解：（：（1）令）令=0，求出最终单纯形表，如下所示。，求出最终单纯形表，如下所示。cj21000iCBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2c j z j000-1/4-1/2第

38、第66页页（2）将）将C* 项反映到最终单纯形表中去项反映到最终单纯形表中去cj2+1+2000iCBXBbx1x2x3x4x50 x315/20015/4-15/22+x17/21001/4-1/21+x23/2010-1/43/2c j z j000-1/4+1/4 -1/2-5/2 0252104141 151 时表中解为最优。时表中解为最优。第第67页页（3）当）当 1 时，变量时，变量 x4 的检验数的检验数 0，需将，需将 x4 换入换入，利用单纯形法继续跌代。，利用单纯形法继续跌代。cj2+1+2000iCBXBbx1x2x3x4x50 x315/2001 5/4 -15/262

39、+x17/21001/4-1/2141+x23/2010-1/43/2-c j z j000-1/4+1/4 -1/2-5/2 第第68页页cj2+1+2000iCBXBbx1x2x3x4x50 x46004/51-62+x1210-1/5011+x23011/500c j z j001/5-1/50-2- 0205151 1 时表中解为最优。时表中解为最优。第第69页页（4）当）当 0，需将，需将 x5 换换入，利用单纯形法继续跌代。入，利用单纯形法继续跌代。cj2+1+2000iCBXBbx1x2x3x4x50 x315/20015/4-15/2-2+x17/21001/4-1/2-1+x

40、23/2010-1/4 3/2 1c j z j000-1/4+1/4 -1/2-5/2 第第70页页cj2+1+2000iCBXBbx1x2x3x4x50 x315051002+x1411/301/600 x5102/30-1/61c j z j01/3+5/30-1/3-1/60 0613103531 512 时表中解为最优。时表中解为最优。第第71页页（5）当）当 0，需将，需将 x4 换入换入，利用单纯形法继续跌代。，利用单纯形法继续跌代。cj2+1+2000iCBXBbx1x2x3x4x50 x31505100-2+x1411/30 1/6 0240 x5102/30-1/61-c

41、j z j01/3+5/30-1/3-1/60第第72页页 02102 2 时表中解为最优。时表中解为最优。cj2+1+2000iCBXBbx1x2x3x4x50 x315051000 x4246201 00 x5511001c j z j2+1+2000第第73页页2 512 151 1 （x1 ， x2）=（2，3）（x1 ， x2）=（7/2，3/2）（x1 ， x2）=（4，0）（x1 ， x2）=（0，0）z =7+8z =17/2+13/2z =8+4z =0第第74页页 0,524261552 max212121221xxxxxxxxxz 例例 分析分析值变化时，下述参数线性规划

42、问题最优值变化时，下述参数线性规划问题最优解得变化。解得变化。 第第75页页解解：（：（1）令）令=0，求出最终单纯形表，如下所示。，求出最终单纯形表，如下所示。cj21000iCBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2c j z j000-1/4-1/2第第76页页1 B 2/34/102/14/102/154/51 00 b 4/14/14/51bB（2）将）将b* 项反映到最终单纯形表中去项反映到最终单纯形表中去第第77页页 bBb1 4/14/14/52/32/72/15 4/12/34/12/74/52/15cj21000iCBXBbx1x2x3x4x50 x315/2+5/40015/4-15/22x17/2+1/41001/4-1/21x23/2-1/