第二章线性规划的对偶理论与灵敏度分析

1、运筹学运筹学赵明霞赵明霞山西大学经济与管理学院山西大学经济与管理学院2022-6-102第二章第二章 线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析1.线性规划的对偶问题线性规划的对偶问题2.影子价格影子价格3.对偶单纯形法对偶单纯形法4.灵敏度分析灵敏度分析2022-6-103例例1 美佳公司计划制造美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设两种家电产品。已知各制造一件时分别占用的设备备A A、B B的台时、调试时间及的台时、调试时间及A A、B B设备和调试工序每天可用于这两种家电的能力、设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如下表

2、所示。问该公司应制造各售出一件时的获利情况如下表所示。问该公司应制造、两种家电备多少两种家电备多少件使获取的利润为最大。件使获取的利润为最大。设：设： x x1 1 A A产品的生产量产品的生产量 x x2 2 B B产品的生产量产品的生产量利润利润 z= 2 xz= 2 x1 1 + x + x2 2 约束约束条件条件5 5x x2 2 15 156 6x x1 1 + 2x + 2x2 2 24 24x x1 1 + x + x2 2 5 5x x1 1，x x2 2 0 0stst . .第一节第一节 线性规划的线性规划的对偶问题对偶问题2022-6-1045 5x x2 2 + + x

3、 x3 3 = = 15 156 6x x1 1 + 2x + 2x2 2 + x+ x4 4 = = 24 24x x1 1 + x + x2 2 + + x x5 5 = = 5 5x x1 1，x x2 2 ，x x3 3 ，x x4 4 ，x x5 5 0 0约束约束条件条件stst . .利润利润 max z= 2 xmax z= 2 x1 1 + x + x2 2 + 0 x+ 0 x3 3 + 0 x + 0 x4 4 + 0 x + 0 x5 5 标准化标准化最终单纯形表最终单纯形表C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4

4、 x50 0 0 0 x x3 3 x x4 4 x x5 5151524245 5 0 5 1 0 0 0 5 1 0 0 6 6 2 2 0 1 0 0 1 0 1 1 1 1 0 0 10 0 1 2 1 0 0 0 2 1 0 0 0最优解最优解X X* *=(7/2,3/2,=(7/2,3/2,15/215/2, ,0 0, ,0 0) )Z Z* *= 17/2= 17/2C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4 x50 0 2 2 x x3 3 x x1 1 x x2 215/215/27/27/23/23/2 0 0 1

5、5/4 -15/2 0 0 1 5/4 -15/2 1 0 1 0 0 1/4 -1/2 0 1/4 -1/2 0 1 0 1 0 -1/4 3/20 -1/4 3/2 0 0 00 0 0 -1/4 -1/2 -1/4 -1/2 2022-6-1055 5x x2 2 15 156 6x x1 1 + 2x + 2x2 2 24 24x x1 1 + x + x2 2 5 5x x1 1，x x2 2 0 0约束约束条件条件把解把解X=(7/2,3/2)X=(7/2,3/2)代入原问题代入原问题( (因为因为为附加变量为附加变量) )分析分析5 53 32 215/215/224245 5P

6、 O 一个问题？一个问题？ 市场上设备市场上设备A A、设备设备B B和调试工序每小时值多少钱？和调试工序每小时值多少钱？在什么价位时，才能使美佳公司愿意出让自己的资源？在什么价位时，才能使美佳公司愿意出让自己的资源？2022-6-1066 6y y2 2 + y + y3 3分分析析设：设： y y1 1 设备设备A A值的值的价值价值 y y2 2 设备设备B B值的值的价值价值 y y3 3 调试工序调试工序值的值的价值价值2 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15 yz= 15 y1 1 + 24y + 24y2 2 + 5y+ 5y3 3

7、总价值总价值minminy y1 1 , y , y2 2 , y , y3 30 0stst . .2022-6-1076 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15 yz= 15 y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0stst . .z z = -15 y= -15 y1 1 - 24y - 24y2 2 - - 5y 5y3 3maxmaxstst . .6 6y y2 2 + y + y3 3 y y4 4=

8、 =2 25 5y y1 1 + 2y + 2y2 2 + y + y3 3 y y5 51 1= =y y1 1, y, y2 2, y, y3 3, y, y4 4, y, y5 5 0 0C C-15 -24 -5 -15 -24 -5 0 0 -M 0 0 -M -M-MC CB BY YB Bb y1 y2 y3 y4 y5 y6 y7 - -M M-M-My y6 6y y7 72 21 1 0 6 1 -1 0 1 0 0 6 1 -1 0 1 0 5 2 5 2 1 1 0 -1 0 1 0 -1 0 1 M-15 8M-24 2M-5 -M M-15 8M-24 2M-5 -

9、M -M-M 0 0 0 0问题求解问题求解2022-6-108C C-15 -24 -5 -15 -24 -5 0 00 0C CB BY YB Bb y1 y2 y3 y4 y5-24-24-5-5y y2 2y y3 31/41/41/21/2-5/4 1 0 -1/4 1/4-5/4 1 0 -1/4 1/415/2 0 1 15/2 0 1 1/2 -3/2 1/2 -3/2 -15/2 0 0 -7/2 -3/2 -15/2 0 0 -7/2 -3/2 Y=(0, , Y=(0, , , 0, 0) , 0, 0)z z=-17/2=-17/2z z = 17/2= 17/2202

10、2-6-109Y=(0, , Y=(0, , , 0, 0 ) , 0, 0 )问题分析问题分析问题问题的解的解6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15yz= 15y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0stst . .问题：问题：？原问题：原问题：利润利润 z= 2 xz= 2 x1 1 + x + x2 2 约束约束条件条件5 5x x2 2 15 156 6x x1 1 + 2x + 2x2 2 24 24

11、x x1 1 + x + x2 2 5 5x x1 1，x x2 2 0 0stst . .问题问题的解的解X X* *=(7/2,3/2,15/2,0,0)=(7/2,3/2,15/2,0,0)Z Z* *= 17/2= 17/2Z Z* *= 17/2= 17/25 5* *3/2 = 15/23/2 = 15/215156 6* *7/2+27/2+2* *3/2 = 243/2 = 242424= =7/2+3/2 = 57/2+3/2 = 55 5= =结结论论估价估价影子价格影子价格（即增加单位资源所（即增加单位资源所得到的贡献）得到的贡献）Z= =CX=Yb Z/ b=(Yb)

12、=Y2022-6-1010C C 2 1 2 1 0 0 00 0 0C CB BX XB Bbx1 x2 x3 x4 x50 02 21 1x x3 3x x1 1x x2 215/215/27/27/23/23/20 0 1 5/4 -15/20 0 1 5/4 -15/21 01 0 0 1/4 -1/2 0 1/4 -1/2 0 1 0 1 0 -1/4 3/20 -1/4 3/20 0 0 -1/4 -1/20 0 0 -1/4 -1/2- -0 0 0 1/4 1/20 0 0 1/4 1/2利润利润 z= 2 xz= 2 x1 1 + x + x2 2 约束约束条件条件5 5x

13、x2 2 15 156 6x x1 1 + 2x + 2x2 2 24 24x x1 1 + x + x2 2 5 5x x1 1，x x2 2 0 0stst . .6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15yz= 15y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0stst . .C C-15 -24 -5 -15 -24 -5 0 00 0C CB BY YB Bb y1 y2 y3 y4 y5-24-24-5-5y

14、 y2 2y y3 31/41/41/21/2 -5/4 1 0 -1/4 1/4 -5/4 1 0 -1/4 1/4 15/2 0 1 15/2 0 1 1/2 -3/2 1/2 -3/2 -15/2 0 0 -7/2 -3/2-15/2 0 0 -7/2 -3/2- - 15/2 0 0 7/2 3/2 15/2 0 0 7/2 3/2 Y=(0, , Y=(0, , , 0, 0 ) , 0, 0 )X X* *=(7/2,3/2, 15/2,0,0)=(7/2,3/2, 15/2,0,0)问题变量问题变量问题剩余松弛变量问题剩余松弛变量解的关系解的关系2022-6-1011一、对偶问题

15、一、对偶问题对对称称形形式式X X 0 0stst. .AX AX b bmax z =max z = CXCX其中：其中： C= C=（c c1 1，c c2 2, , , ,c cn n) ) b= b=（b b1 1，b b2 2, , , ,b bm m) )T T X= X=（x x1 1，x x2 2, , , ,x xn n) )T T Y= Y=（y y1 1，y y2 2, , , ,y ym m) )T TY Y 0 0stst. .A AT TY CY CT Tmin w =min w = Y YT Tb b利润利润 z= 2 xz= 2 x1 1 + x + x2 2

16、约束约束条件条件5 5x x2 2 15 156 6x x1 1 + 2x + 2x2 2 24 24x x1 1 + x + x2 2 5 5x x1 1，x x2 2 0 0stst . .6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15yz= 15y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0stst . .2022-6-1012非非对称形式对称形式x x1 1 0, x 0, x2 2 0, x 0, x3 3无约束无

17、约束 stst. .a a1111x x1 1+a+a1212x x2 2+a+a1313x x3 3 b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2323x x3 3 = b = b2 2a a3131x x1 1+a+a3232x x2 2+a+a3333x x3 3 b b3 3max z = cmax z = c1 1x x1 1 + c + c2 2x x2 2 +c +c3 3x x3 3 x x1 1 , , x x2 2 , , x x3 3 ，x x3 3 00stst. .a a1111x x1 1 - a- a1212x x2 2 + a+

18、a1313x x3 3- a a1313x x3 3 b b1 1a a2121x x1 1 - a- a2222x x2 2 + a+ a2323x x3 3- a a2323x x3 3 b b2 2-a-a2121x x1 1 + a+ a2222x x2 2 _ a_ a2323x x3 3+ a a2323x x3 3 -b-b2 2-a-a3131x x1 1 + a+ a3232x x2 2 - a- a3333x x3 3+ a a3333x x3 3 -b-b3 3max z = cmax z = c1 1x x1 1 - c - c2 2x x2 2 + c + c3 3x

19、 x3 3 - c - c3 3x x3 3 y y1 1 , y, y2 2 , y, y2 2 ，y y3 3 00stst. .a a1111y y1 1 + + a a2121y y2 2 a a2121y y2 2 - - a a3131y y3 3 c c1 1-a-a1212y y1 1 - - a a2222y y2 2 + a+ a2222y y2 2 - - a a3232y y3 3 -c-c2 2a a1313y y1 1 + + a a2323y y2 2 a a2323y y2 2- a a3333y y3 3 c c3 3-a-a1313y y1 1 - - a

20、a2323y y2 2 + a+ a2323y y2 2+ a a3333y y3 3 -c-c3 3min w = bmin w = b1 1y y1 1 + b + b2 2y y2 2 - b- b2 2y y2 2 - b - b3 3y y3 3 min w = bmin w = b1 1y y1 1 + b + b2 2y y2 2 + b + b3 3y y3 3a a1111y y1 1 + + a a2121y y2 2 + + a a3131y y3 3 c c1 1a a1212y y1 1 + + a a2222y y2 2 + + a a3232y y3 3 c c2

21、 2a a1313y y1 1 + + a a2323y y2 2 + + a a3333y y3 3 = c= c3 3stst. .y y1 10, y0, y2 2无约束无约束，y y3 3 0 02022-6-1013二、对偶规则二、对偶规则 &原问题有原问题有m m个约束条件，对偶问题有个约束条件，对偶问题有m m个变量个变量&原问题有原问题有n n个变量，对偶问题有个变量，对偶问题有n n个约束条件个约束条件&原问题的价值系数对应对偶问题的右端项原问题的价值系数对应对偶问题的右端项&原问题的右端项对应对偶问题的价值系数原问题的右端项对应对偶问题的价值

22、系数&原问题的系数矩阵转置后为对偶问题系数矩阵原问题的系数矩阵转置后为对偶问题系数矩阵变量、约束与系数变量、约束与系数2022-6-1014变量与约束对应关系变量与约束对应关系原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题） max z=CX AX ( ) b X ( ) 0 或无约束或无约束 min w=Yb ATY ( ) C Y ( ) 0 或无约束或无约束 有有n个决策变量个决策变量 xj (j0、2n) xj 0 0变量变量 xj 0 0 xj 无约束无约束 有有n个约束条件个约束条件 对应的约束为对应的约束为 约束约束 对应的约束为对应的约束为 对应

23、的约束为对应的约束为 有有m个约束条件个约束条件 对应的约束为对应的约束为 约束约束 对应的约束为对应的约束为 对应的约束为对应的约束为 有有m个决策变量个决策变量 yj (j0、2m) yj 0 0变量变量 yj 0 0 yj 无约束无约束2022-6-1015三、对偶问题的基本性质（对称形）三、对偶问题的基本性质（对称形）1对称性：对偶问题的对偶问题是原问题对称性：对偶问题的对偶问题是原问题1弱对偶性：极大化原问题的任一可行解的目弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的标函数值，不大于其对偶问题任意可行解的目标函数值目标函数值1对偶定理：若一个问题有最优

24、解，则另一问对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题也有最优解，且目标函数值相等。若原问题最优基为题最优基为B B，则其对偶问题最优解则其对偶问题最优解Y Y* *=C=CB BB B-1-11无界性：原问题无界，对偶问题无可行解无界性：原问题无界，对偶问题无可行解需要说明的是：需要说明的是：这些性质同样适用于非对称形问题这些性质同样适用于非对称形问题2022-6-1016X X 0 0stst. .AX AX b bmax z = CXmax z = CXX, Xs 0X, Xs 0stst. .AX + AX + IXsIXs = = b bmax z

25、 = CX + 0Xsmax z = CX + 0XsC C C C 0 0C CB BX XB Bb X Xs0 0X Xs sb b A IA IC C C CB B C CN N 0 0C CB BX XB Bb XB XN Xs0 0X Xs sb b B N IB N IC C C CB B C CN N 0 0C CB BX XB Bb XB XN XsC CB BX XB BB B-1-1b b B B-1-1B B B B-1-1N N B B-1-1I IC CB B-C-CB BB B-1-1B B C CN N-C-CB BB B-1-1N 0-CN 0-CB BB B-

26、1-1I I C C C CB B C CN N 0 0C CB BX XB Bb XB XN XsC CB BX XB BB B-1-1b b B B-1-1B B B B-1-1N N B B-1-1I I 0 0 C CN N-C-CB BB B-1-1N -CN -CB BB B-1-12022-6-1017C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4 x5151524245 5 0 5 1 0 0 0 5 1 0 0 6 6 2 2 0 1 0 0 1 0 1 1 1 1 0 0 10 0 1 C C 2 1 2 1 0 0 0 0

27、 0 0C CB BX XB Bb x1 x2 x3 x4 x515/215/27/27/23/23/2 0 0 1 5/4 -15/2 0 0 1 5/4 -15/2 1 0 1 0 0 1/4 -1/2 0 1/4 -1/2 0 1 0 1 0 -1/4 3/20 -1/4 3/2 B与与B-1B B-1-1= =1 5/4 -15/21 5/4 -15/20 1/4 -1/20 1/4 -1/20 -1/4 3/20 -1/4 3/2B=B=1 0 51 0 50 6 20 6 20 1 10 1 12022-6-1018第二节第二节 影子价格影子价格*1*1*miiinjjjybxcz

28、bi是线性规划原问题约束条件的右端项，它代表第是线性规划原问题约束条件的右端项，它代表第i i种资源的拥种资源的拥有量；有量；对偶变量对偶变量yiyi* *的意义代表在资源最优利用条件下对单位第的意义代表在资源最优利用条件下对单位第i i种资种资源的估价。这种估价不是资源的市场价格，而是根据资源在生源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而做的估价，为区别起见，称为产中作出的贡献而做的估价，为区别起见，称为影子价格影子价格(shadow price)(shadow price)。2022-6-10191 1、资源的市场价格是其价值的客观体现，相对比较稳定，、资源的市

29、场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用情况。因企业生产任而它的影子价格则有赖于资源的利用情况。因企业生产任务、产品结构等情况发生变化，资源的影子价格也务、产品结构等情况发生变化，资源的影子价格也随之改随之改变变。2 2、影子价格是一种、影子价格是一种边际价格边际价格，若对式中目标函数，若对式中目标函数z z求求bibi的偏的偏导数可得导数可得 。这说明。这说明yiyi* *的值相当于在资源得到的值相当于在资源得到最优利用的生产条件下，最优利用的生产条件下，bibi每增加一个单位时目标函数每增加一个单位时目标函数z z的增量。的增量。*/iiybz2022-6-

30、1020injijbxa1 3 3、资源的影子价格实际上又是一种、资源的影子价格实际上又是一种机会成本机会成本。在完全市场经济条件下，。在完全市场经济条件下，当第当第2 2种资源的市场价格低于影子价格时，可以买进这种资源；相反，当市种资源的市场价格低于影子价格时，可以买进这种资源；相反，当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，其影场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，其影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平，才子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平，才处于平衡状态。处于平衡状态。 4 4、在上一节对偶问

31、题的互补松弛性质中有、在上一节对偶问题的互补松弛性质中有 时，时，yiyi=0=0；当；当yiyi00时，有时，有 ，这表明生产过程中如果某种资源，这表明生产过程中如果某种资源bibi未得到充分利未得到充分利用时，该种资源的影子价格为用时，该种资源的影子价格为零零；又当资源的影子价格；又当资源的影子价格不为零时不为零时，表明该，表明该种资源在生产中已耗费完毕。种资源在生产中已耗费完毕。 5 5、当产品产值大于隐含成本时，表明生产该产品有利，可在计划中安、当产品产值大于隐含成本时，表明生产该产品有利，可在计划中安排，否则用这些资源来生产别的产品更为有利，就不在生产计划中安排。排，否则用这些资源来

32、生产别的产品更为有利，就不在生产计划中安排。这就是单纯形表中这就是单纯形表中各个检验数的经济各个检验数的经济意义。意义。injjijbxa 1miiijjjyac12022-6-10216 6、一般说、一般说对线性规划问题的求解是确定资源的最优分配方案对线性规划问题的求解是确定资源的最优分配方案，而而对于对偶问题的求解则是确定对资源的恰当估价对于对偶问题的求解则是确定对资源的恰当估价，这种估，这种估价直接涉及资源的最有效利用。价直接涉及资源的最有效利用。 如在一个大公司内部，可借助资源的影子价格确定一些内部如在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考

33、核下属企业经营的结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。好坏。 又如在社会上可对一些最紧缺的资源，借助影子价格规定使又如在社会上可对一些最紧缺的资源，借助影子价格规定使用这种资源一单位时必须上缴的利润额，以控制一些经济效用这种资源一单位时必须上缴的利润额，以控制一些经济效益低的企业自觉地节约使用紧缺资源，使有限资源发挥更大益低的企业自觉地节约使用紧缺资源，使有限资源发挥更大的经济效益。的经济效益。2022-6-1022第三节第三节 对偶单纯形法对偶单纯形法C C C CB B C CN N 0 0C CB BX XB Bb XB B XB B XsC CB BX XB BB

34、B-1-1b b B B-1-1B B B B-1-1N N B B-1-1I I 0 0 C CN N-C-CB BB B-1-1N -CN -CB BB B-1-1对于单纯形法叠代过程本质对于单纯形法叠代过程本质：确保：确保1 1）z z变大；变大； 2 2）B B-1-1b b 00由对偶理论知道，当原问题为最优解时，由对偶理论知道，当原问题为最优解时，- -00且且为对偶问题的最优解，为对偶问题的最优解，因此人们提出对偶因此人们提出对偶单纯形法。叠代过程本质单纯形法。叠代过程本质：1 1） 0 0； 2 2）逐步使）逐步使B B-1-1b b 000|minijaaijj0|min0i

35、jaxaiji与与2022-6-10236 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15 yz= 15 y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0stst . .z z = -15 y= -15 y1 1 - 24y - 24y2 2 - - 5y 5y3 3stst . .maxmax6 6y y2 2 + y + y3 3 y y4 4= = 2 25 5y y1 1 + 2y + 2y2 2 + y + y3 3 y

36、 y5 51 1= =y y1 1, y, y2 2, y, y3 3, y, y4 4, y, y5 5= = 0 0问题求解问题求解z z = -15 y= -15 y1 1 - 24y - 24y2 2 - - 5y 5y3 3 + 0y+ 0y4 4 + 0y+ 0y5 5 stst . .maxmax-6y-6y2 2 - y - y3 3 + y+ y4 4= =-2-2 -5y -5y1 1 - 2y - 2y2 2 - y - y3 3 + y+ y5 5-1-1= =y y1 1, y, y2 2, y, y3 3, y, y4 4, y, y5 50 02022-6-102

37、41.1.确定出基变量确定出基变量。在常数列中找一个最小的。在常数列中找一个最小的负常量负常量，把这个常量所在行作为出基，把这个常量所在行作为出基变量变量0,miniirbbb 0 0 -6-6 -1 1 0 -1 1 0 -5 -2 -1 -5 -2 -1 0 10 1-2-2-1-1y1 y2 y3 y4 y5bY YB BC CB B-15 -24 -5 -15 -24 -5 0 00 0C Cy4 y50 0-15 -24 -5-15 -24 -5 0 00 0rsssrjrjjjazcaazc0min2. 确定入基变量确定入基变量。在系数列中找。在系数列中找负数负数，把这个常量所在行

38、作为入基变量。，把这个常量所在行作为入基变量。2022-6-1025 0 1 1/6 1/6 0 0 1 1/6 1/6 0 -5 0 -2/3 1/3-5 0 -2/3 1/3 1 11/31/3-1/3-1/3 y1 y2 y3 y4 y5bY YB BC CB B-15 -24 -5 -15 -24 -5 0 00 0C C -5/4 1 0 -1/4 1/4 -5/4 1 0 -1/4 1/4 15/2 0 15/2 0 1 1/21 1/2 -3/2 -3/21/41/41/21/2-15 0 -1-15 0 -1 -4 -4 0 0y2 y5-24 0-24 -5y2 y3-15-

39、15/2 0 0 -7/2/2 0 0 -7/2 3/2 3/22022-6-1026第四节第四节 灵敏度分析灵敏度分析 ),.,2 , 1(0),.,2 , 1(max1njxmibxaxcZjijijnjjj 灵敏度分析是指系统或事物对周围环境变化显示出来的敏感灵敏度分析是指系统或事物对周围环境变化显示出来的敏感程度。程度。 在在LPLP问题中，问题中，a aijij、c cj j、b bi i都有可能发生变化，分析这些变化都有可能发生变化，分析这些变化对最优解或目标值的影响程度就是对最优解或目标值的影响程度就是灵敏度分析灵敏度分析。2022-6-1027c cj j通常表示一些估计或预测

40、的数据，随市场而变化；通常表示一些估计或预测的数据，随市场而变化；a aijij通常随工艺技术条件的改变而改变；通常随工艺技术条件的改变而改变；b bi i则反映了企业资源状况。则反映了企业资源状况。 CBB-1b C - CBB-1 AB-1 b B-1 A原始数据原始数据A A，b b，C CA=(A=(P1 P2 Pn ) ) Z Z0= = CBB-1b X XB= = B-1b A = = C - CBB-1 A N = = CN - CBB-1 N j = = Cj- CBB-1 Pj 2022-6-1028 b b* *= = B-1 b b 最优解的增量最优解的增量b b* *

41、与初始与初始b b的增量的增量b b 成成B-1 倍变化倍变化Pj* * = =B-1 Pj最优解时的系数增量最优解时的系数增量Pj* * 与初始的系与初始的系数增量数增量Pj也成也成B-1 倍变化倍变化最优性条件可表达为：最优性条件可表达为：01NBCCBNN0 bB X-1B2022-6-1029通常需要分析的项目：通常需要分析的项目：(1)(1) 参数参数a a，b b，C C在什么范围内变动，对当前方案无影响？在什么范围内变动，对当前方案无影响？(2)(2) 参数参数b b，b b，c c中的一个中的一个( (几个几个) )变动，对当前方案影响程度？变动，对当前方案影响程度？(3)(3

42、) 如果最优方案改变，如何用简便方法求新方案？如果最优方案改变，如何用简便方法求新方案？2022-6-1030灵敏度分析的步骤：灵敏度分析的步骤： 1 1、将参数的改变通过计算反映到最终单纯形表上来。、将参数的改变通过计算反映到最终单纯形表上来。 具体计算方法是，按下列公式计算出由参数具体计算方法是，按下列公式计算出由参数a aijij，b bi i，c cj j的的变化而引起的最终单纯形表上有关数字的变化。变化而引起的最终单纯形表上有关数字的变化。 2 2、检查原问题是否仍为可行解。、检查原问题是否仍为可行解。 3 3、检查对偶问题是否仍为可行解。、检查对偶问题是否仍为可行解。 4 4、按下

43、表所列情况得出结论或决定继续计算的步骤。、按下表所列情况得出结论或决定继续计算的步骤。原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解问题的最优解或最优基不变问题的最优解或最优基不变可行解可行解非可行解非可行解用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解非可行解非可行解可行解可行解用对偶单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解非可行解非可行解非可行解非可行解引进人工变量，编制新的单纯形表重新计算引进人工变量，编制新的单纯形表重新计算0ib0j2022-6-1031一、分析一、分析cj的变化的变化 线性规划目标函数中变量系数线性规

44、划目标函数中变量系数c cj j的变化仅仅影响到检验数的变化仅仅影响到检验数( (cj-zjcj-zj) )的变化。的变化。所以将所以将cjcj的变化直接反映到的变化直接反映到最终单纯形表最终单纯形表中，只可能出现上页中，只可能出现上页表中前两种情况。表中前两种情况。jjmiijijjzcacc12022-6-1032 例例1-11-1：在美佳公司例子中，：在美佳公司例子中，(1)(1)若家电若家电I I的利润降至的利润降至1.51.5元元/ /件，而家电件，而家电IIII的利润增至的利润增至2 2元元/ /件件时，美佳公司最优生产计划有何变化；时，美佳公司最优生产计划有何变化；(2)(2)若

45、家电若家电I I的利润不变，则家电的利润不变，则家电IIII的利润在什么范围内变化时，的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？该公司的最优生产计划将不发生变化？2022-6-1033 解解 (1)：将家电：将家电I、II的利润变化直接反映到最终单纯的利润变化直接反映到最终单纯形表中得到表如下：形表中得到表如下：cj1.52000CB基基bx1x2x3x4x50 x315/20015/4-15/21.5x17/21001/4-1/22x23/2010-1/43/2cj-zj0001/8-9/4 因变量因变量x4的检验数大于零，故需继续用单纯形法迭代计算，的检验数大于零，故需继

46、续用单纯形法迭代计算，得表如下：得表如下：cj1.52000CB基基bx1x2x3x4x50 x46004/51-61.5x1210-1/5012x23011/500cj-zj00-1/100-3/2 即美佳公司随家电即美佳公司随家电I、II的利润变化应调整为生产的利润变化应调整为生产2件件I，生产生产3件件II。2022-6-1034 (2)：设家电：设家电II的利润为的利润为(1+m)元，反映到最终单纯形元，反映到最终单纯形表中，得表如下：表中，得表如下：cj21+m000CB基基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21+mx23/20

47、10-1/43/2cj-zj000-1/4+1/4m-1/2-3/2m 为使上表中的解为使上表中的解仍为最优解仍为最优解，应有：，应有：02321,04141mm解得：解得：131m即家电即家电II的利润的利润c2的变化范围应满足：的变化范围应满足：2322 c2022-6-1035二、分析二、分析bi的变化的变化 右端项右端项bibi的变化在实际问题中反映为可用资源数量的变化。的变化在实际问题中反映为可用资源数量的变化。bibi变化反映到最终单纯形表变化反映到最终单纯形表上将引起上将引起b b列数字的变化列数字的变化，在表中，在表中可能出现第一或第三的两种情况。可能出现第一或第三的两种情况。

48、 出现第一种情况时，问题的最优基不变，变化后的出现第一种情况时，问题的最优基不变，变化后的b b列值为最列值为最优解。优解。 出现第三种情况时，用对偶单纯形法迭代继续找出最优解。出现第三种情况时，用对偶单纯形法迭代继续找出最优解。2022-6-1036例例1-21-2：在上述美佳公司例子中，：在上述美佳公司例子中，(1)(1)若设备若设备A A和调试工序的每天能力不变，而设备和调试工序的每天能力不变，而设备B B每天的能力每天的能力增加到增加到32h32h，分析公司最优计划的变化；，分析公司最优计划的变化；(2)(2)若设备若设备A A和设备和设备B B每天可用能力不变，则调试工序能力在什每天

49、可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。么范围内变化时，问题的最优基不变。2022-6-1037 解解 (1)(1)：因有：因有 ，则：，则：080b22100802/34/102/14/102/154/511bBb将其反映到最终单纯形表中得表如下。由于该表中原问题为将其反映到最终单纯形表中得表如下。由于该表中原问题为非可行解非可行解，故用对偶单纯形法继续计算，其结果如下量表所，故用对偶单纯形法继续计算，其结果如下量表所示：示：2022-6-1038cj21000CB基基bx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-1/21x

50、2-1/2010-1/43/2cj-zj000-1/4-1/2对偶单纯形法处理后结果：对偶单纯形法处理后结果：cj21000CB基基bx1x2x3x4x50 x315051002x15110010 x420-401-6cj-zj0-100-2由此美佳公司的最优计划改变为只生产由此美佳公司的最优计划改变为只生产5件家电件家电I。2022-6-1039 (2)(2)：设调式工序每天可用能力为设调式工序每天可用能力为(5+m)h(5+m)h，因有，因有mmmmbBb2321215002/34/102/14/102/154/511将其反映到最终单纯形表中，其将其反映到最终单纯形表中，其b b列数字为：

51、列数字为：mmmb23232127215215当当b=0b=0时问题的最优基不变，解得时问题的最优基不变，解得-1=m=1-1=m=1。由此调试工序。由此调试工序的能力应在的能力应在4h-6h4h-6h之间。之间。2022-6-1040三、增加一个变量三、增加一个变量xj的分析的分析 增加一个变量在实际问题中反映为增加一种新的产品。其分增加一个变量在实际问题中反映为增加一种新的产品。其分析步骤为：析步骤为： 1 1、计算、计算 2 2、计算、计算 3 3、若、若 ，原最优解不变，只需将计算得到的，原最优解不变，只需将计算得到的 和和 直接直接写入最终单纯形表中；若写入最终单纯形表中；若 ，则按

52、单纯形法继续迭代计算，则按单纯形法继续迭代计算找出最优。找出最优。 例例1-31-3：在美佳公司例子中，设该公司又计划推出新型号的：在美佳公司例子中，设该公司又计划推出新型号的家电家电IIIIII，生产一件所需设备，生产一件所需设备A A、B B及调试工序的时间分别为及调试工序的时间分别为3h3h、4h4h、2h2h，该产品的预期盈利为，该产品的预期盈利为3 3元元/ /件，试分析该种产品是否值件，试分析该种产品是否值得投产；若投产，该公司的最优生产计划有何变化。得投产；若投产，该公司的最优生产计划有何变化。miiijjjjjyaczc1jjPBP10jjPj0j2022-6-1041 解解

53、设该公司生产设该公司生产x6x6件家电件家电IIIIII，有，有c6=3c6=3，P6=(3,4,2)P6=(3,4,2)T T2072432/34/102/14/102/154/516P将其反映到最终单纯形表中得表如下将其反映到最终单纯形表中得表如下: :1243)21,41,0(362022-6-1042因因 ，故用单纯形法继续迭代计算结果为：，故用单纯形法继续迭代计算结果为：cj210003CB基bx1x2x3x4x5x60 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22cj-zj000-1/4-1/2106cj210003CB

54、基bx1x2x3x4x5x60 x351/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj0-1/20-1/8-5/40由上表可知，美佳公司新的最优生产计划应该为每天生产由上表可知，美佳公司新的最优生产计划应该为每天生产7/27/2件家电件家电I I，51/451/4件家电件家电IIIIII。2022-6-1043四、分析参数四、分析参数aij的变化的变化 a aijij的变化使线性规划的约束系数矩阵的变化使线性规划的约束系数矩阵A A发生变化。发生变化。 若变量若变量x xj j在最终单纯形表中为基变量，则在最终单纯形表中为基变量

55、，则a aijij的变化分析步骤的变化分析步骤可参照本节之三；可参照本节之三； 若变量若变量x xj j在最终单纯形表中为基变量，则在最终单纯形表中为基变量，则a aijij的变化将使相应的变化将使相应的的B B和和B B-1-1发生变化，因此有可能出现原问题和对偶问题均为非发生变化，因此有可能出现原问题和对偶问题均为非可行解的情况。出现这种情况时，需引进人工变量先将原问题可行解的情况。出现这种情况时，需引进人工变量先将原问题的解转化为可行解，再用单纯形法求解。的解转化为可行解，再用单纯形法求解。 例例1-41-4：在美佳公司的例子中，若家电：在美佳公司的例子中，若家电IIII每件需设备每件需

56、设备A A、B B和和调试工时变为调试工时变为8h8h、4h4h、1h1h，该产品的利润变为，该产品的利润变为3 3元元/ /件，试重新件，试重新确定该公司最优生产计划。确定该公司最优生产计划。2022-6-1044 解解 先将生产工时变化后的新家电先将生产工时变化后的新家电IIII看作是一种新产品，看作是一种新产品，生产量生产量x x2 2，仿上一节的步骤直接计算，仿上一节的步骤直接计算 和和 并反映到最终并反映到最终单纯形表中。其中：单纯形表中。其中：2/12/12/111482/34/102/14/102/154/512P将其反映到最终单纯形表中得表如下。将其反映到最终单纯形表中得表如下

57、。22P2/3148)2/1 ,4/1 ,0(322022-6-1045 因因x2x2已变换为已变换为x2x2，故用单纯形算法将，故用单纯形算法将x2x2替换出基变量替换出基变量中的中的x2x2，并在下一个表中不再保留，并在下一个表中不再保留x2x2，得表如下：，得表如下：cj213000CB基基bx1x2x2x3x4x50 x315/20011/215/4-15/22x17/2101/201/4-1/21x23/2011/20-1/43/2cj-zj003/20-1/4-1/2cj23000CB基基bx1x2x3x4x50 x3-90014-242x121001/2-23x23010-1/23cj-