管理运筹学单纯形法的灵敏度分析与对偶 对偶问题

1、管理运筹学单纯形法的灵敏度分析与对偶 对偶问题分别用大M法和两阶段法求解下列线形规划问题,并指出解的类型 minZ=2x1+3x2+x3 x1+4x2+2x38 S.t. 3x1+2x2 6 x1,x2,x3 0 :1:402:10CjCBXB b检验数检验数 j x1x2x3x4x5x6x7-2 -3 -1 0 0 -M-M 8142-10 1 0 x6x7-M-M初初始始单单纯纯形形表表格格4M-2 6M -3 2M-1-M-M 00 63200-1 0 1CjCBXB b检验数检验数 j x1x2x3x4x5x6x7-2 -3 -1 0 0 -M-M 9/5013/5-3/101/10

2、3/10 -1/10 X2x1-3-2最最终终单单纯纯形形表表格格4M-2 6M -3 2M-1-M-M 00 4/510-2/5 1/5-2/5 -1/5 2/5第六章第六章 单纯形法的灵敏度分析单纯形法的灵敏度分析与对偶与对偶DUAL窗含西岭千秋雪，门泊东吴万里船窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象对偶是一种普遍现象 1 1 单纯形表的灵敏度分析单纯形表的灵敏度分析( (重点重点. .难点难点. .掌握掌握) ) 2 2 线性规划的对偶问题线性规划的对偶问题 ( (重点重点. .理解理解. .掌握掌握) ) 3 3 对偶规划的基本性质对偶规划的基本性质( (重点重点. .应用应

3、用) ) 4 4 对偶单纯形法对偶单纯形法( (难点难点. .掌握掌握-前面已讲前面已讲) )学习学习与与 1 单纯形表的灵敏度分析单纯形表的灵敏度分析(重点重点.难点难点.掌握掌握) 2 2 线性规划的对偶问题线性规划的对偶问题一、对偶问题实例一、对偶问题实例例例1 1 某工厂生产甲、乙两种产品，要消耗某工厂生产甲、乙两种产品，要消耗A A、B B和和C C三种资源，三种资源，已知每件产品对这三种资源的消耗、这三种资源的现有数量和每已知每件产品对这三种资源的消耗、这三种资源的现有数量和每件产品可获得的利润如表所示件产品可获得的利润如表所示. .问：如何安排生产计划，使得既能问：如何安排生产计

4、划，使得既能充分利用现有资源又使总利润最大？充分利用现有资源又使总利润最大？ 产品资源甲乙资源限制A3265B2140C0375单件利润15002500 该问题的数学模型为： max Z=1500 x1+2500 x2 s.t. 3x1+2x2 65 A资源 2x1+ x2 40 B资源 3x2 75 C资源 x1,x2 0 考虑： 1、定价不能太高太高？ 2、定价不能太低太低？ 假设该厂现自己不生产，因而要转让资源A、B和C，请问他们应如何给这三种资源定价？咋办？设A、B、C资源的出售价格分别为 y1 、 y2和y3甲乙资源限制A3265y1B2140y2C0375y3单件利润1500250

5、01500 2123yy 250032132yyy 0 321,yyy321754065minyyyw原问题： max Z=1500 x1+2500 x2 s.t. 3x1+2x2 65 A资源 2x1+ x2 40 B资源 3x2 75 C资源 x1,x2 0 对偶问题： Min W = 65 y1 + 40 y2 + 75 y3 s.t. 3y1 + 2 y2 1500 2y1 + y2 + 3y3 2500 y1, y2 , y3 0210 3A=654075b=1500 2500c=2 02 1 3A=15002500 b= 65 40 75c=maxmin对偶问题对偶问题 MinMi

6、n W=b W=bT TY Y s.t. As.t. AT TY YC CT T Y Y 00maxbACCTATbTminmnmn二、对偶问题的形式二、对偶问题的形式 1 1、对称型对偶问题、对称型对偶问题原问题原问题 MaxMax Z=cX Z=cX s.t. AXbs.t. AXb X X 00 对偶关系表对偶关系表 x x1 1x x2 2x xm mx xn nc c1 1c c2 2c cm mc cn nmaxZ maxZ minWminW Y Y1 1A A1111a a1212a a1m1ma a1n1n b b1 1 Y Y2 2a a2121a a2222a a2m2ma

7、 a2n2n b b2 2 Y Ym ma am1m1a am2m2a ammmma amnmn b bm m由表可以看出：由表可以看出：从行看是原问题（从行看是原问题（），从列看是对偶问题（），从列看是对偶问题（），两个问题），两个问题的变量系数矩阵互为转置矩阵。的变量系数矩阵互为转置矩阵。原问题（原问题（）的常数项是对偶问题（）的常数项是对偶问题（）的目标系数，反之，）的目标系数，反之，原问题（原问题（）的目标系数是对偶问题（）的目标系数是对偶问题（）的常数项。）的常数项。原问题（原问题（）有）有n个决策变量，对偶问题（个决策变量，对偶问题（）有）有n个约束方程；个约束方程；原问题有原问题

8、有m个约束方程，对偶问题就有个约束方程，对偶问题就有m个决策变量。个决策变量。原问题的约束是原问题的约束是“”型，对偶问题的约束是型，对偶问题的约束是“”型。型。1. 原问题的目标函数是求极大，对偶问题的目标是求极小。原问题的目标函数是求极大，对偶问题的目标是求极小。 12121212x3x902xx80s txx45xx0、max Z5x1 +4x2 321458090minYYYW52321YYY43321YYY0,321YYY例例2 请给出下列线性规划问题的对偶问题：请给出下列线性规划问题的对偶问题：对称型线性规划问题对称型线性规划问题 怎么样怎么样简单吧简单吧 2 2、非对称型对偶问题

9、、非对称型对偶问题 表表 对偶变换的规则对偶变换的规则 约束条件的类型约束条件的类型(规范与否规范与否)与非负条件相互对应与非负条件相互对应 非标准的约束条件类型对应非正常的非负条件非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的对偶变换是一一对应的好难记呀！例例3：Min z= 5x1+ 25x2 7x1+ 75x2 98s.t. 5x1 + 6x2 = 78 24x1+ 12x254 x10 、x2 0Max w= 98y1+ 78y2 + 54y37y1+ 5y2 + 24y3 5s.t. 75y1+ 6y2 + 12y3 25 y1 0 、y2无限制、 y30 怎么样，怎

10、么样， 没问题吧！没问题吧！对称形式线形规划问题为对称形式线形规划问题为: Max Max Z=cX Z=cX s.t. AXbs.t. AXb X X 00加上松弛变量化为标准形后为加上松弛变量化为标准形后为: Max Max Z=cX +0X Z=cX +0Xs s s.t. AX+IXs.t. AX+IXs s=b=b X X 0,0,X Xs s 00 3 对偶规划的基本性质对偶规划的基本性质一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述:检验数j当迭代若干步，基变量为当迭代若干步，基变量为X B时，新的单纯形表时，新的单纯形表:bXS0Cj X B XN XS B N I CB

11、 CN 0 CB CN 0检验数jB-1bXBCBCj X B XN XS I B-1N B-1 0 CN- CB B-1N - CB B-1 CB CN 0初始单纯形表为初始单纯形表为: maxZ=3x1 +5 x2 +0 x3 +0 x4+0 x5 =0 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 Cj比值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000 35000举例举例 最优基最优基 Cj35000比值CBXBbx1x2x3x4x50 x340012/3-1/35x260101/2

12、03x14100-2/31/3检验数j 000-1/2-1340020101*Bx3x2x1313200210313211*B 最优基的逆最优基的逆 最优基和最优基的逆最优基和最优基的逆 maxZ=2x1+x2 5x215 s.t. 6x1+2x2 24 x1+x2 5 x1,x2 0 maxZ=2x1+x2+0 x3 +0 x4 +0 x5 5x2+x3 =15s.t. 6x1+2x2 +x4 =24 x1+x2 +x5 = 5 x1,x2 ,x3 ,x4,x5 0例例4：对称形线性规划问题：对称形线性规划问题：标准型： j x3x1x2 021 0 0 0 -1/4 -1/2 x1 x2

13、x3 x4 x5 CB XB b CB j 2 1 0 0 0 x3x4x5 000 15 0 5 1 0 024 6 2 0 1 0 5 1 1 0 0 12 1 0 0 0初始单纯形表初始单纯形表最终单纯形表最终单纯形表B=(P3,P1,P2) 15/2 0 0 1 5/4 -15/2 7/2 1 0 0 1/4 -1/2 3/2 0 1 0 -1/4 3/2B-1= (P3,P4,P5)初表初表中中终终表表中中 minZ=2x1+3x2+x3 x1+4x2+2x38 S.t. 3x1+2x2 6 x1,x2,x3 0CjCBXB b检验数检验数 j x1x2x3x4x5x6x7-2 -3

14、 -1 0 0 -M-M 8142-10 1 0 x6x7-M-M初初始始单单纯纯形形表表格格4M-2 6M -3 2M-1-M-M 00 63200-1 0 1CjCBXB b检验数检验数 j x1x2x3x4x5x6x7-2 -3 -1 0 0 -M-M 9/5013/5-3/101/10 3/10 -1/10 X2x1-3-2最最终终单单纯纯形形表表格格 0 0 0-1/2-1/2 -M-M 4/510-2/5 1/5-2/5 -1/5 2/5 maxZ=50 x1+100 x2 x1 +x2 300 s.t. 2x1+x2 400 x2 250 x1,x2 0 maxZ=50 x1+1

15、00 x2+0 x3 +0 x4 +0 x5 x1 +x2 +x3 =300 s.t. 2x1+x2 +x4 =400 x2 +x5=250 x1,x2 , x3 ,x4,x5 0例5：对称形线性规划问题： x1 x2 x3 x4 x5 CB XB b CB j x3x4x5 000 300 1 1 1 0 0400 2 1 0 1 0250 0 1 0 0 1 50 100 0 0 0原问题初始单纯形表原问题初始单纯形表 50 100 0 0 0已知最优基的基变量为已知最优基的基变量为x1， x4， x2，请直接写出该线性，请直接写出该线性规划问题的最终单纯形表。并给出其对偶问题的最优解规划

16、问题的最终单纯形表。并给出其对偶问题的最优解最优基为最优基为 B=（p1， p4， p2）=B-1=（p3， p4 ， p5 ）=b= B-1 b=1 0 - 1 -2 1 1 0 0 11 0 1 2 1 10 0 11 0 - 1 -2 1 1 0 0 13004002505050250=j= Cj-CBB-1 P j x1 x2 x3 x4 x5 CB XB b CB j x1x4x2500100 50 1 0 1 0 -1 50 0 0 -2 1 1250 0 1 0 0 1 0 0 -50 0 -50原问题最终单纯形表原问题最终单纯形表 50 100 0 0 0原问题初始单纯形表原问

17、题初始单纯形表 x1 x2 x3 x4 x5 CB XB b CB j x3x4x5 000400 2 1 0 1 0250 0 1 0 0 1 50 100 0 0 0 50 100 0 0 0 300 1 1 1 0 0检验数j当迭代若干步，基变量为当迭代若干步，基变量为X B时，新的单纯形表时，新的单纯形表:bXS0Cj X B XN XS B N I CB CN 0 CB CN 0检验数jB-1bXBCBCj X B XN XS I B-1N B-1 0 CN- CB B-1N - CB B-1 CB CN 0初始单纯形表为初始单纯形表为:对应初始单纯表中的单位矩阵I，迭代后的单纯形表

18、中为B-1初始单纯表中的基变量Xs=b，迭代后的单纯形表中为XB= B-1b初始单纯表中的约束系数矩阵为： A,I=B,N,I 迭代后的单纯形表中约束系数矩阵为： B-1A, B-1I=B-1B, B-1N, B-1I=I , B-1N, B-1若初始矩阵中变量xj的系数向量为Pj，迭代后为Pj ，则有： Pj =B-1 Pj 小结小结当B为最优基最优基时，迭代后的单纯表中检验数： CN- CB B-1N 0 - CB B-1 0因XB的检验数可写 为： CB- CB B-1B 故可重写为：C- CB B-1A 0 - CB B-1 0CB B-1称为单纯形乘子称为单纯形乘子。若令YT=CB

19、B-1 则：C-YT A 0 AT Y C所以： AT Y CT Y 0 可见检验数的相反数恰好是其对偶问题的一个可可见检验数的相反数恰好是其对偶问题的一个可行解，将这个解代入对偶问题的目标函数，有：行解，将这个解代入对偶问题的目标函数，有：W=YTb=CBB-1b=Z当原问题为最优解时，这时对偶问题为可行解，当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值，根据对偶问题且两者具有相同的目标函数值，根据对偶问题的基本性质，将看到这时对偶问题的解也为最的基本性质，将看到这时对偶问题的解也为最优解。优解。所以从最优解的单纯形表中同时可以得到其对所以从最优解的单纯形表中同时可以得

20、到其对偶问题的最优解。偶问题的最优解。 maxZ=2x1+x2 5x215 s.t. 6x1+2x2 24 x1+x2 5 x1,x2 0 maxZ=2x1+x2+0 x3 +0 x4 +0 x5 5x2+x3 =15 y1 s.t. 6x1+2x2 +x4 =24 y2 x1+x2 +x5 = 5 y3 x1,x2 ,x3 ,x4,x5 0 minW=15y1+24y2+5y3 6y2 +y3 -y4 = 2 x1s.t. 5y1+2y2 +y3 -y5= 1 x2 y1,y2 ,y3 ,y4,y5 0 minW=15y1+24y2+5y3 6y2 +y32s.t. 5y1+2y2 +y3

21、1 y1,y2 ,y3 0例5：对称形线性规划问题：对偶问题：标准型： x1 x2 x3 x4 x5 CB XB b CB j 2 1 0 0 0 x3x1x2 02115/2 0 0 1 5/4 -15/27/2 1 0 0 1/4 -1/23/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 y1 y2 y3 y4 y5 CB XB b CB j -15 -24 -5 0 0y2y3-24 -51/4 -5/4 1 0 -1/4 1/41/2 15/2 0 1 1/2 -3/2-15/2 0 0 -7/2 -3/2 -y4 - y5 -y1 -y2 -y3 - x3 -x4

22、 -x5 -x1 -x2原问题最终单纯形表原问题最终单纯形表对偶问题最终单纯形表对偶问题最终单纯形表松松弛弛变变量量对对偶偶变变量量剩剩余余变变量量决决策策变变量量例例6 6、利用原问题的最优单纯形表求解对偶问题的最、利用原问题的最优单纯形表求解对偶问题的最优解优解 s.t. 100 100 0解: 对偶问题为 s.t. 4 3 7 0321734maxxxxz32122xxx32133xxx321,xxx21100100minyyw213yy 212yy 2132yy 21, yyCjCBXBb检验数检验数 jx1x2x3x4x54370025-3/4103/4-1/2255/401-1/4

23、1/2x2x337 -5/200-1/2-2最最终终单单纯纯形形表表格格x4x5松弛变量可见原问题的最优解为可见原问题的最优解为: X*=(0,25,25)T 其对偶问题的最优解为其对偶问题的最优解为: y *=(1/2,2)T 为了便于讨论，下面不妨总是假设为了便于讨论，下面不妨总是假设:定理定理1 （对称性定理）对偶问题的对偶是原问题（对称性定理）对偶问题的对偶是原问题。根据对称性定理，在任一对偶问题中，可以把其中的任何一个称为根据对称性定理，在任一对偶问题中，可以把其中的任何一个称为原问题，而把另一个称为其对偶问题。原问题，而把另一个称为其对偶问题。:0YCTATYbTY. .mints

24、W对偶问题对偶问题:0XbAXCX. .maxtsZ原问题原问题二、对偶问题的基本性质二、对偶问题的基本性质:0YCTATYbTY. .mintsW0Y-CT-ATY-bTY. .maxts(-W)0. .minXbAXtsCXf0. .maxXbAXtsCXZ证明证明:由前面可知对偶问题为由前面可知对偶问题为:等价于该问题等价于该问题:可见此问题为对称型的规划问题可见此问题为对称型的规划问题,其对偶问题表示为其对偶问题表示为:令令Z=-f, 则化简为则化简为:即为原问题即为原问题可见对偶问题的对偶是原问题。可见对偶问题的对偶是原问题。 证毕证毕 定理定理 2 （弱（弱对偶性定理）对偶性定理）

25、 对偶问题对偶问题(min)的任何可行解的任何可行解Y0，其目标函，其目标函数值总是不小于原问题数值总是不小于原问题(max)任何可行解任何可行解X0的目标函数值。的目标函数值。证证: :假设假设X X0 0,Y,Y0 0分别为原问题和对偶问题的可行解分别为原问题和对偶问题的可行解, ,故有故有: :0X0 0bAX0 0CX0 0. .maxtsZ0Y0 0CTATY0 0bTY0 0. .mintsW-(1)-(2)因为因为Y0 0是对偶问题的可行解是对偶问题的可行解,用用Y0 0T左乘左乘(1)得得: Y0 0T AX0 0 Y0 0T b转置得转置得: X0 0T ATY0 0 bT

26、y0 0 因为因为X0 0是原问题的可行解是原问题的可行解,用用X0 0左乘左乘(2)得得: X0 0T ATY0 0X0 0T CT 转置得转置得: Y0 0T AX0 0 CX0 0可见可见CX0 0 Y0 0T AX0 0 Y0 0T b= bT Y0 0 即即CX0 0 bT Y0 0例例7、应用弱对偶定理，证明下列线性规划问题、应用弱对偶定理，证明下列线性规划问题的最大值不超过的最大值不超过1. 3212maxxxxz2321xxx1321xxx22321xxx无约束321,0,0 xxx s.t. 证明：该线性问题的对偶问题为：证明：该线性问题的对偶问题为： 00min22.212

27、1001001 (2,1,2)10maxTwyyystyyyyyyyyyyyyYcxy bz -0， 自由，易知（ ， ， ）是对偶问题的一个可行解，由对偶问题的对偶定理可得：即最大值不超过11 弱弱对偶定理推论对偶定理推论 推论推论 1 1 最优解判别最优解判别定理定理 若原问题的某个可行解若原问题的某个可行解X0的目标函数值与对偶问题的目标函数值与对偶问题某个可行解某个可行解Y0的目标函数值相等，则的目标函数值相等，则X0, Y0分别是相分别是相 应问题的最优解应问题的最优解证：由弱对偶定理可知结论是显然的证：由弱对偶定理可知结论是显然的, 即即CX0 = bTY0 CX, bTY0 =

28、CX0 Yb 。 证毕。证毕。 推论推论 2 如果原如果原max(min)问题为无界解，则其对偶问题为无界解，则其对偶 min (max)问题无可行解问题无可行解(反之不然反之不然) maxZ=x1+x2 x1-x2-1s.t. -x1+x2-1 x1,x20 minW=-y1-y2 y1-y2 1s.t. -y1+y2 1 y1,y2 0原问题和对偶问题同时无可行解原问题和对偶问题同时无可行解 推论推论 3原问题原问题(max)的任何可行解目的任何可行解目标函数值是其对偶问题标函数值是其对偶问题(min)目标函数目标函数值的下界；原问题值的下界；原问题(min)的任何可行解的任何可行解目标函

29、数值是其对偶问题目标函数值是其对偶问题(max)目标目标函数值的上界函数值的上界 推论推论 4 如果原问题如果原问题max(min)有可行有可行解，其对偶解，其对偶 问题问题min (max)无可行解，无可行解，则原问题为无界解则原问题为无界解 例8、应用对偶理论证明下列线性规划应用对偶理论证明下列线性规划问题目标函数值无界问题目标函数值无界.s.t.21maxxxz2321xxx12321xxx0,321xxx证明：证明：000 x 是线性问题的可行解，即该问题存在可行解； 又其对偶问题为：min2.2110,0201wyystyyyyyyyyy yyy-0，0-这与约束条件（）不符该对偶问

30、题无可行解原问题无最优解。 定理定理 3 3 主对偶主对偶定理定理( (强对偶性定理强对偶性定理) ) 如果原问题和对偶问题都有可行解，则它如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解所对应的们都有最优解，且它们的最优解所对应的目标函数值相等。目标函数值相等。 证证: 由弱对偶定理推论由弱对偶定理推论1 1可知，原问题和对偶问题的目标函数可知，原问题和对偶问题的目标函数有界，故一定存在最优解。有界，故一定存在最优解。 现证明定理的后一句话。现证明定理的后一句话。设设 X X0 0 为原问题的最优解，它所对应的基矩阵是为原问题的最优解，它所对应的基矩阵是 B B， X X0

31、0= = B B 1 1 b b，则其检验数满足，则其检验数满足 C C C CB BB B 1 1A A 0 0 令令 Y Y0 0= = C CB BB B 1 1，则有，则有 Y Y0 0 A A C C 显然显然Y Y0 0为对偶问题的可行解。因此有对偶问题目标函数值为对偶问题的可行解。因此有对偶问题目标函数值, , W W= =Y Y0 0b b= = C CB BB B 1 1 b b 而原问题最优解的目标函数值为而原问题最优解的目标函数值为 Z Z= =CXCX0 0= = C CB BB B 1 1 b b 故由最优解判别定理可知故由最优解判别定理可知Y Y0 0 为对偶问题的

32、最优解。证毕。为对偶问题的最优解。证毕。定理定理 4 4 互补松弛互补松弛定理定理定理定理 设设X0, Y0分别是原问题和对偶问题的可行解，分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、为原问题的松弛变量的值、V0为对偶问题剩余变为对偶问题剩余变量的值。量的值。X0, Y0分别是原问题和对偶问题最优解的分别是原问题和对偶问题最优解的充分必要条件是充分必要条件是 Y0 U0 = V0 X0 = 0证证：由定理所设，可知有由定理所设，可知有 A XA X0 0 + U+ U0 0 = = b Xb X0 0, U, U0 0 0 0 (1)(1) Y Y0 0 A A V V0 0

33、= = C YC Y0 0, V, V0 0 0 0 (2) (2)分别以分别以Y Y0 0左乘左乘(1)(1)式，以式，以X X0 0右乘右乘(2)(2)式后，两式相减，得式后，两式相减，得 Y Y0 0 U U0 0 + + V V0 0 X X0 0 = Y= Y0 0 b b C XC X0 0若若 Y Y0 0 U U0 0 + + V V0 0 X X0 0 = = 0 0，根据最优解判别定理，根据最优解判别定理， X X0 0, , Y Y0 0分别是原问题和对偶问题最优解。反之亦然。分别是原问题和对偶问题最优解。反之亦然。 证毕。证毕。例例9、考虑下列原始线性规划、考虑下列原始

34、线性规划 (1) 写出其对偶问题；写出其对偶问题；(2) 已知（已知（3,2,0）是上述原始问题的最优解，根据互补松弛定理，）是上述原始问题的最优解，根据互补松弛定理，求出对偶问题的最优解；求出对偶问题的最优解；(3) 如果上述规划中的第一个约束为资源约束，写出这种资源的影如果上述规划中的第一个约束为资源约束，写出这种资源的影子价格子价格.32132maxxxxz52321xxx12432321xxx)3 , 2 , 1(0jxjmin512.223143wyystyyyyyyyy20， 无符号限制解： （1）对偶问题： （2）由题知原问题的最优解为）由题知原问题的最优解为*(3 2 0)Tx

35、 ， ， ； 由互补松弛定理得：在对偶问题中对应第一，二个约束为紧约由互补松弛定理得：在对偶问题中对应第一，二个约束为紧约束，第三个约束条件为松约束，即，束，第三个约束条件为松约束，即，*12*1*12*2*12224311243yyyyyyyy对偶规划问题的最优解 *141y （ ， ） （ 3）影子价格为）影子价格为 y1 = 4 -1(4, -1)例例 10：利用互补松弛定理：利用互补松弛定理 2134maxxxz s.t. 212xx 2 212xx 3 2132xx 5 21xx 2 213xx 3 21,xx0 试求其（D）问题的最优解. 解：该问题的（D）问题为 54321325

36、32minyyyyyw s.t. 5432132yyyyy4 54321322yyyyy3 54321,yyyyy0 由于（P）问题只含两个决策变量，故可用图解法求解，得最优解为： )53,54(*x 其相应的目标函数最优值 5*z. 将*x代入约束条件，知第2、3、4个约束条件成立严格不等式，由互补 松弛定理，对偶规划最优解中相应的变量有 0*4*3*2yyy，又因为 *2*1,xx不为0，在对偶规划中对应的约束条件为紧，因此，得到43*5*1 yy， 32*5*1yy，解得1*5*1 yy，故（D）问题的最优解为： ) 1 , 0 , 0 , 0 , 1 (*y 其相应的目标函数最优值 5

37、*w. 原问题检验数与对偶问题的解的总结原问题检验数与对偶问题的解的总结在主对偶定理在主对偶定理(强对偶性强对偶性)的证明中我们有：对偶的证明中我们有：对偶(min型型)变量的最优解等于原问题松弛变量的机会成本，或变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值者说原问题松弛变量检验数的绝对值容易证明，对偶问题最优解的剩余变量解值等于原问容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值题对应变量的检验数的绝对值由于原问题和对偶问题是相互对偶的，因此对偶问题由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。的检

38、验数与原问题的解也有类似上述关系。更一般地讲，不管原问题是否标准，在最优解的单纯更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量型表中，都有原问题虚变量(松弛或剩余松弛或剩余) 的检验数对应的检验数对应其对偶问题实变量其对偶问题实变量 (对偶变量对偶变量)的最优解，原问题实变量的最优解，原问题实变量(决策变量决策变量) 的检验数对应其对偶问题虚变量的检验数对应其对偶问题虚变量 (松弛或剩松弛或剩余变量余变量)的最优解。因此，原问题或对偶问题只需求解的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。其中之一就可以了。 4 对偶单纯形法对偶单纯形法一、一、 对偶单纯形

39、法的基本思路对偶单纯形法的基本思路单纯形迭代要求每步都是基本可行解单纯形迭代要求每步都是基本可行解达到最优解时，检验数达到最优解时，检验数 c cj jz zj j 0 (max)0 (max)但对于所加的剩余变量无法构成初始基但对于所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决础可行解，因此通过加人工变量来解决大大M M法和二阶段法较繁法和二阶段法较繁能否从剩余变量构成的初始基础非可行能否从剩余变量构成的初始基础非可行解出发迭代，但保证解出发迭代，但保证检验数满足最优条检验数满足最优条件，件， c cj jz zj j 0 (max)0 (max)b=B1b000？二、二、

40、对偶单纯形法的计算步骤对偶单纯形法的计算步骤对某线形规划问题存在一个对偶问题的可行基，即必对某线形规划问题存在一个对偶问题的可行基，即必须所有的须所有的cj-zj00，bi的值不要求全为正的值不要求全为正:1、确定换出变量（离基变量）、确定换出变量（离基变量）在小于在小于0的的b中找出最小者，其所对应的变量中找出最小者，其所对应的变量xr为换出变量为换出变量2、确定换入变量（进基变量）、确定换入变量（进基变量） =min =minj j/a/arjrj|a|arjrj0= 0，则按单纯形法继续迭代计算找出最优解，则按单纯形法继续迭代计算找出最优解j最最终终单单纯纯形形表表bXS0Cj X B

41、XN XS B N I CB CN 0 CB CN 0jB-1bXBCBCj X B XN XS I B-1N B-1 0 CN- CB B-1N - CB B-1 CB CN 0初初始始单单纯纯形形表表例例15、 在佳美公司例子中，设该公司又计划推出新产在佳美公司例子中，设该公司又计划推出新产品品，生产一单位产品，生产一单位产品，所需设备，所需设备A、B及调试工序及调试工序的时间分别为的时间分别为3小时、小时、4小时、小时、2小时，该产品的预期盈小时，该产品的预期盈利为利为3百元百元/单位，试分析该新产品是否值得投产；如投单位，试分析该新产品是否值得投产；如投产对该公司的最优生产计划有何变化

42、产对该公司的最优生产计划有何变化 。解：设新产品解：设新产品的生产数量为的生产数量为x6件，有：件，有： 36cTP)2 , 4 , 3(6将其反映到最终单纯形表中得表将其反映到最终单纯形表中得表 1 5/4 - 15/20 1/4 -1/20 -1/4 3/2342-702P P6 =B=B-1-1P P6 = = = x1 x2 x3 x4 x5 CB XB b CB j 2 1 0 0 0 x3x1x2 02115/2 0 0 1 5/4 -15/27/2 1 0 0 1/4 -1/23/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 j 51/4 0 7/2 1 3/

43、8 -9/4 07/2 1 0 0 1/4 -1/2 03/4 0 1/2 0 -1/8 3/4 1 0 -1/2 0 -1/8 -5/4 0 x3x1x6 0 2 3可见变化后的问题具有唯一最优解可见变化后的问题具有唯一最优解: X*=(7/2,0)T Z*=37/4,比原方案比原方案17/2获利多，所以值得生产获利多，所以值得生产-702x631(2) 减少决策变量的灵敏度分析减少决策变量的灵敏度分析 若减少的决策变量不在最优解的基变量之若减少的决策变量不在最优解的基变量之中，是非基变量，对这种情况可以认为决中，是非基变量，对这种情况可以认为决策变量本来就是多余的。减少这个变量不策变量本来

44、就是多余的。减少这个变量不影响最优解、最优值。影响最优解、最优值。 j -5-1513/7 0 1 4/7 -5/7 3/7 3/7 1 0 2/7 1/7 -2/7 0 0 -27/7 -10/7 -15/7x2x1 x1 x2 x3 x4 x5 CB XB b CB -15 -5 -11 0 0 减少决策变量减少决策变量x3，最优生产计划如何？，最优生产计划如何？(2) 减少决策变量的灵敏度分析减少决策变量的灵敏度分析 若减少的决策变量是基变量，要考若减少的决策变量是基变量，要考虑去掉这个变量的影响，可用单纯虑去掉这个变量的影响，可用单纯形法或对偶单纯形法重新求解。形法或对偶单纯形法重新求

45、解。 j -5-1513/7 0 1 4/7 -5/7 3/7 3/7 1 0 2/7 1/7 -2/7 0 0 -27/7 -10/7 -15/7x2x1 x1 x2 x3 x4 x5 CB XB b CB -15 -5 -11 0 0 j -11-1513/4 0 1 1 -5/4 3/4 -1/2 1 0 0 1/2 -1/2 0 0 0 -25/4 3/4x3x1 x1 x2 x3 x4 x5 CB XB b CB -15 -5 -11 0 0 引入人工变量引入人工变量x6，采用大，采用大M法继续求解法继续求解 减少决策变量减少决策变量x2，最优生产计划如何？，最优生产计划如何？四、四

46、、 系数矩阵的灵敏度分析系数矩阵的灵敏度分析 aij的变化使线形规划的约束系数矩阵的变化使线形规划的约束系数矩阵A发生变化。发生变化。若变量若变量xj在最终单纯性表中为非基变量，其约束在最终单纯性表中为非基变量，其约束条件中系数条件中系数aij的变化分析步骤可参照三中增加决的变化分析步骤可参照三中增加决策变量的情形；若变量策变量的情形；若变量xj在最终单纯性表中为基在最终单纯性表中为基变量，其约束条件中系数变量，其约束条件中系数aij的变化将使相应的的变化将使相应的B和和B-1发生变化，因此有可能出现原问题和对偶发生变化，因此有可能出现原问题和对偶问题均为非可行解的情况。出现这种情况时，需问题

47、均为非可行解的情况。出现这种情况时，需要引进人工变量先将原问题的解转化为可行解，要引进人工变量先将原问题的解转化为可行解，再用单纯性法求解。再用单纯性法求解。下面就变量下面就变量xj在最终单纯性表中为基变量这种在最终单纯性表中为基变量这种情形举例说明情形举例说明例例16、 在佳美公司的例子中，若产品在佳美公司的例子中，若产品每单位需设备每单位需设备A、B和调试工时和调试工时8小时、小时、4小时、小时、1小时，该产品的利润变为小时，该产品的利润变为3百元百元/单位，试重新确定该公司最优生产计划单位，试重新确定该公司最优生产计划.解：先将生产工时变化后的产品解：先将生产工时变化后的产品看作是一种新

48、产品，生产量为看作是一种新产品，生产量为x x2 ，按本节三的方法直接计算按本节三的方法直接计算2和和P P2 ：2=3-=3-（0 0，1/41/4，1/21/2） =3/2 =3/2 1 5/4 - 15/20 1/4 -1/20 -1/4 3/284111/21/21/2P P6= = =841将其反映到最终单纯形表中得表将其反映到最终单纯形表中得表 j最最终终单单纯纯形形表表bXS0Cj X B XN XS B N I CB CN 0 CB CN 0jB-1bXBCBCj X B XN XS I B-1N B-1 0 CN- CB B-1N - CB B-1 CB CN 0初初始始单单

49、纯纯形形表表 x1 x2 x3 x4 x5 x2 CB XB b CB j 2 1 0 0 0 3 x3x1x2 02115/2 0 0 1 5/4 -15/2 11/27/2 1 0 0 1/4 -1/2 1/23/2 0 1 0 -1/4 3/2 1/2 0 0 0 -1/4 -1/2 3/2原问题与对偶问题均为非可行解，故先设法使原问题变为可行解原问题与对偶问题均为非可行解，故先设法使原问题变为可行解 j -9 0 7/2 1 4 -24 0 2 1 0 0 1/2 - 2 0 3 0 1/2 0 -1/2 3 1 0 -1/2 0 1/2 -5 0 x3x1x2 0 2 3 j 3/8

50、 0 -1/24 -1/6 1 0 1/2411/4 1 -1/12 1/6 0 0 1/1215/8 0 1/8 0 0 1 -1/8 0 -5/24 - 1/3 0 0 -M+5/24x5x1x2 0 2 3 j 9 0 -1 -4 24 0 1 2 1 0 1/2 - 2 0 0 3 0 0 -1/2 3 1 0 0 -M 1/2-4M -5+24M 0 0 x6x1x2 -M 2 3 x1 x3 x4 x5 x2 x6 CB XB b CB 2 0 0 0 3 -Mx3+4x4-24x5 =-9-x3-4x4+24x5 +x6=9可见变化后的问题具有唯一最优解可见变化后的问题具有唯一最

51、优解: X*=(11/4,15/8)T Z*=89/8五、五、 增加或减少约束条件的灵敏度分析增加或减少约束条件的灵敏度分析 增加一个约束条件在实际问题中相当增添一道工序，增加一个约束条件在实际问题中相当增添一道工序，设在原线性规划问题中，增加一个新的约束条件设在原线性规划问题中，增加一个新的约束条件：1, 122, 111 , 1mnnmmmbxaxaxaTmxxxx),(*2*1*代入新增加的约束条件，如果条件满足，则原代入新增加的约束条件，如果条件满足，则原问题的最优解仍为新问题的最优解，结束问题的最优解仍为新问题的最优解，结束.如果条件不满足，则将新增加的约束条件直如果条件不满足，则将

52、新增加的约束条件直接反映到最终单纯形表中再进一步分析接反映到最终单纯形表中再进一步分析. 则首先把已求得的原问题的最优解则首先把已求得的原问题的最优解例例17、 假设产品假设产品、经调试后，还需经过一道环境经调试后，还需经过一道环境试验工序，产品试验工序，产品每单位须环境试验每单位须环境试验3小时，产品小时，产品每每单位须单位须2小时，又环境试验工序每天生产能力为小时，又环境试验工序每天生产能力为12小时，小时，试分析增加该工序后的佳美公司最优生产计划试分析增加该工序后的佳美公司最优生产计划.解：解：环境试验工序的约束条件为：环境试验工序的约束条件为： 3x x1 1+2x+2x2 21212

53、 将原问题的最优解将原问题的最优解: x: x1 1=7/2,x=7/2,x2 2=3/2 =3/2 代入环境试代入环境试验工序的约束条件：验工序的约束条件：3 3* *7/2+27/2+2* *3/2=27/23/2=27/2可见新增加的约束条件对原问题的最优解起作用，可见新增加的约束条件对原问题的最优解起作用，所以原问题的最优解不是本问题的最优解。所以原问题的最优解不是本问题的最优解。1212以以x x6 6为基变量将其反映到最终单纯形表中为基变量将其反映到最终单纯形表中将将3x x1 1+2x+2x2 21212化为标准型化为标准型 3x x1 1+2x+2x2 2+x+x6 6=12=

54、12 x1 x2 x3 x4 x5 CB XB b CB j 2 1 0 0 0 x3x1x202115/2 0 0 1 5/4 -15/27/2 1 0 0 1/4 -1/23/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/20 x6 12 3 2 0 0 0 0 x600010(1)(2)(3)(4)因为表中因为表中x1、x2 列不是单位向量，所以需要进行变换列不是单位向量，所以需要进行变换 x1 x2 x3 x4 x5 x6 CB XB b CB j 2 1 0 0 0 0 x3x1x202115/2 0 0 1 5/4 -15/2 07/2 1 0 0 1/4 -1/2

55、 03/2 0 1 0 -1/4 3/2 0 0 0 0 -1/4 -1/2 00 x6 -3/2 0 0 0 -1/4 -3/2 1 (1) (2) (3) (4) x1 x2 x3 x4 x5 x6 CB XB b CB j 2 1 0 0 0 0 x3x1x2021 15 0 0 1 5/2 0 -5 4 1 0 0 1/3 0 -1/3 0 0 1 0 -1/2 0 1 0 0 0 -1/6 0 -1/30 x5 1 0 0 0 1/6 1 -2/3 可见变化后的问题具有唯一最优解可见变化后的问题具有唯一最优解: X*=(4,0)T Z*=8例例18、 假设产品假设产品、经调试后，还需

56、经过一道环境经调试后，还需经过一道环境试验工序，产品试验工序，产品每单位须环境试验每单位须环境试验3小时，产品小时，产品每每单位须单位须2小时，又环境试验工序每天生产能力至少为小时，又环境试验工序每天生产能力至少为15小时，试分析增加该工序后的佳美公司最优生产计划小时，试分析增加该工序后的佳美公司最优生产计划.解：解：环境试验工序的约束条件为：环境试验工序的约束条件为： 3x x1 1+2x+2x2 21515 将原问题的最优解将原问题的最优解: x: x1 1=7/2,x=7/2,x2 2=3/2 =3/2 代入环境试代入环境试验工序的约束条件：验工序的约束条件：3 3* *7/2+27/2

57、+2* *3/2=27/23/2=27/2可见新增加的约束条件对原问题的最优解起作用，可见新增加的约束条件对原问题的最优解起作用，所以原问题的最优解不是本问题的最优解。所以原问题的最优解不是本问题的最优解。以以x x6 6为基变量将其反映到最终单纯形表中为基变量将其反映到最终单纯形表中将将3x x1 1+2x+2x2 2 1515化为标准型化为标准型 - -3x x1 1-2x-2x2 2+x+x6 6=-15=-15可以采用大M法，最好采用对偶单纯形法,避免用人工变量 x1 x2 x3 x4 x5 CB XB b CB j 2 1 0 0 0 x3x1x202115/2 0 0 1 5/4

58、-15/27/2 1 0 0 1/4 -1/23/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/20 x6 -15 -3 -2 0 0 0 0 x600010(1)(2)(3)(4)因为表中因为表中x1、x2 列不是单位向量，所以需要进行变换列不是单位向量，所以需要进行变换 x1 x2 x3 x4 x5 x6 CB XB b CB j 2 1 0 0 0 0 x3x1x202115/2 0 0 1 5/4 -15/2 07/2 1 0 0 1/4 -1/2 03/2 0 1 0 -1/4 3/2 0 0 0 0 -1/4 -1/2 00 x6 -3/2 0 0 0 1/4 3/

59、2 1 (1) (2) (3) (4)可见变化后的问题没有可可见变化后的问题没有可行解，对偶问题具有无界行解，对偶问题具有无界解解减少约束条件的灵敏度分析减少约束条件的灵敏度分析 减少一个约束条件在实际问题中相当去减少一个约束条件在实际问题中相当去掉一道工序，即在原线性规划问题中，掉一道工序，即在原线性规划问题中，去掉一个约束条件去掉一个约束条件反映到最终单纯形表中就是去掉反映到最终单纯形表中就是去掉一行，重新计算检验数行，可能一行，重新计算检验数行，可能利用单纯形法继续求解利用单纯形法继续求解 j x3x1x2 02115/2 0 0 1 5/4 -15/27/2 1 0 0 1/4 -1/

60、23/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 x1 x2 x3 x4 x5 CB 2 1 0 0 0终终表表 CB XB b 0 1 0 -1/2 1 该问题存在无界解该问题存在无界解假如去掉调试工序，原问题的最优假如去掉调试工序，原问题的最优生产方案如何？生产方案如何？以上的几种灵敏度分析，仅限于某数以上的几种灵敏度分析，仅限于某数值、变量、约束条件的变化对解的影值、变量、约束条件的变化对解的影响，这是一些基本的分析方法。若要响，这是一些基本的分析方法。若要考虑某区间上一个或几个参数作连续考虑某区间上一个或几个参数作连续变化的灵敏度分析，请同学们参阅线变化的灵敏度分