第二章-对偶规划.ppt

1、l 对偶规划对偶规划 1.1.对偶规划的定义对偶规划的定义 2.2.对偶规划定理对偶规划定理 3.3.互补松弛关系互补松弛关系 4.4.对偶单纯形法对偶单纯形法对偶规划的意义对偶规划的意义对偶规划与原问题的关系对偶规划与原问题的关系对偶规划的定理对偶规划的定理对偶单纯形法对偶单纯形法影子价格影子价格灵敏度分析灵敏度分析一、对偶问题的提出一、对偶问题的提出 例例2.1:2.1:某工厂拥有某工厂拥有A A、B B、C C三种类型的设备，生产甲、三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利

2、时数，每件产品可以获得的利润以及三种设备可利用的机时数如下表所示。求获最大利润的方案。用的机时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500 Max z=1500 xMax z=1500 x1 1+2500 x+2500 x2 2 s.t.3x s.t.3x1 1+2x+2x2 2 65 65 2x 2x1 1+x+x2 2 40 40 原问题原问题 3x3x2 2 75 75 x x1 1,x,x2 2 0 0 MinMin W =65y =65y1 1+

3、40y+40y2 2+75y+75y3 3 s.t.3y s.t.3y1 1+2y+2y2 2 15001500 （不少于甲产品的利润）（不少于甲产品的利润）2y2y1 1+y+y2 2+3y+3y3 3 2500 2500 对偶问题对偶问题 （不少于乙产品的利润）（不少于乙产品的利润）y y1 1,y,y2 2,y,y3 3 0 0 例如，某企业生产甲乙两种产品，生产例如，某企业生产甲乙两种产品，生产情况如表：问，如何安排生产使企业获利最大。情况如表：问，如何安排生产使企业获利最大。甲甲 乙乙资源限制资源限制原料原料15615原料原料22312获利获利47Max z=4x1+7x2s.t 5

4、x1+6x2 15 2x1+3x2 12 x1、x2 00 甲甲 乙乙资源限制资源限制原料原料15615原料原料22312获利获利47 甲甲 乙乙资源限制资源限制原料原料15615原料原料22312获利获利47 还是这个问题，我们从另一个方面还是这个问题，我们从另一个方面考虑该问题。计算企业的成本，购买两种原考虑该问题。计算企业的成本，购买两种原料各需单位费用为料各需单位费用为Y Y1 1，Y Y2 2元元如何安排生产使如何安排生产使企业总费用最低。企业总费用最低。Min W=15Y1+12Y2s.t 5Y1+2Y2 4 6Y1+3Y2 7 Y1、Y2 00Max z=4x1+7x2s.t 5

5、x1+6x2 15 2x1+3x2 12 x1、x2 00Min W=15Y1+12Y2s.t 5Y1+2Y2 4 6Y1+3Y2 7 Y1、Y2 0 0对对偶偶问问题题原原问问题题设以下线性规划问题设以下线性规划问题Max Z=CXs.t.AX b X0 为原问题，则为原问题，则：Min W=bTY s.t.ATY CT Y0称为原问题的对偶问题。称为原问题的对偶问题。Min W=Y b s.t.YA C Y0l其中其中Y为行向量为行向量如果：如果：Min Z=CTXs.t.AX b X0 为原问题，为原问题，则则：Max W=bTY s.t.ATY C Y0称为原问题的对偶问题。称为原问题

6、的对偶问题。对称形式：互为对偶 (LP)Max z=cT x (LD)Min W=bT y s.t.Ax b s.t.AT y c x 0 y 0 “Max-”“Min-”原问题原问题 Max Z=CX对偶问题对偶问题 Min W=Yb 变变量量 n 个个 00 0 无限制无限制约约束束条条件件 n 个个 =约约束束条条件件m个个 =变变量量m个个 无限制无限制Max z=4x1+7x2s.t 5x1+6x2 15 2x1+3x2 12 x1,x2 00Min W=15y1+12y2s.t 5y1+2y2 4 6y1+3y2 7 y1 ,y2 00Max z=x1+x2+x3s.t x1+x2

7、+x3 15 x1-x2+x3 =12 2x1+x2+x3 1 1 x1 0 0,x2 0,x3 无限制无限制Min W=15y1 +12y2+y3 y1+y2+2y3 1 y1-y2 +y3 1 y1+y2+y3 =1 y1 0,y2 无限制无限制,y3 0 Max z=x1+x2+x3 x1+x2+x3 15 x1-x2+x3 =12 2x1+x2+x3 1 1 x1 0,0,x2 0,x3 无限制无限制 3.3.写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型没有非负限制321432143143214321,0,1053042260272252375maxxxxxxxxxxx

8、xxxxxxxxz没有非负限制4321443214314321,0,051030422602722523xxxxxxxxxxxxxxxx 再根据非对称形式的对应关系，直接写出对偶规划解 先将约束条件变形为“”形式0,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf没有非负限制W原问题原问题 min Z=CX对偶问题对偶问题Max W=Yb 变变量量 n 个个 00 0 无限制无限制约约束束条条件件 n 个个 =约约束束条条件件m个个 =变变量量m个个 无限制无限制 X Xj jy yi i X X1 1

9、X X2 2 X Xn n 原问题原问题关系关系Min WMin Wy y1 1 y y2 2 y ym m a a11 11 a a12 12 a a1n1n a a21 21 a a22 22 a a2n2n a am1 m1 a am2 m2 a amnmn b b1 1 b b2 2b bm m对偶问对偶问题关系题关系 Max Z=Min WMax Z=Min WMax ZMax Z C C1 1 C C2 2 C Cn n 线性规划原问题与对偶问题的关系线性规划原问题与对偶问题的关系(标准式标准式)写出下列写出下列线性规划问题线性规划问题的的对偶问题对偶问题.Max z=x1+x2+

10、x3+x+xs.t x1+x2+x3+x+x x1+x2+x3 +x+x=2x1+x2+x3+x+x x1 0 0,x 0,x 无限制无限制l.Min z =x1-x2-x3 ls.t x1 +x2 -x3=l x1-x2+x -l x1 -x2+x3 l x1 0 0,x2 0,x3 无限制无限制没有非负限制321432143143214321,0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZMin定理一：定理一：设设 X X0 0、Y Y0 0 是原问题是原问题 和对偶问题的任一可行解和对偶问题的任一可行解 Max Z=CX,Max Z=CX,Min

11、W=Yb Min W=Yb AXb AXb YAC YAC X0X0 Y0 Y0 则有：则有：C CX X0 0 Y Y0 0b b原原问问题题对对偶偶问问题题证明：将式证明：将式 AXb 同时左乘一个同时左乘一个Y Y0 0 Y Y0 0AXAX0 0 Y Y0 0b=b=W W 式式 YAC同时同时右乘一个右乘一个X X0 0 Y Y0 0A AX X0 0 C CX X0 0 =Z Z C CX X0 0 Y Y0 0A AX X0 0 Y Y0 0b b C CX X0 0 Y Y0 0b b 最大化的目标函数值不超过最小化的目标函最大化的目标函数值不超过最小化的目标函 数值。数值。(

12、弱弱 原问题的目标函数值是其对偶目标函数值的原问题的目标函数值是其对偶目标函数值的下限，对偶问题的目标函数值是原问题目标下限，对偶问题的目标函数值是原问题目标函数值的上限。函数值的上限。如果如果X X0 0、Y Y0 0 分别是原问分别是原问题和对偶问题的可行解，并题和对偶问题的可行解，并且它们对应的目标函数值相且它们对应的目标函数值相同同CXCX0=0=Y Y0 0b b，则则X X0 0、Y Y0 0 分别是分别是原问题和对偶问题的最优解。原问题和对偶问题的最优解。如果原始问题和对偶问题中如果原始问题和对偶问题中的任一个目标函数无界，则另一的任一个目标函数无界，则另一个必定无可行解。个必定

13、无可行解。请注意推论请注意推论2 2之逆命题不存在之逆命题不存在即一个问题无可行解，不能推得即一个问题无可行解，不能推得另一个问题目标函数无界。另一个问题目标函数无界。如果如果X X0 0、Y Y0 0 分别是原始问题和对偶问分别是原始问题和对偶问题的可行解，并且它们对应的，题的可行解，并且它们对应的，CXCX0=0=Y Y0 0b b则则 X X0 0、Y Y0 0 分别是原始问题和对偶问题的分别是原始问题和对偶问题的最优解。最优解。证明：由弱对偶性可以看出对原问题证明：由弱对偶性可以看出对原问题和对偶问题可行解的关系和对偶问题可行解的关系 C CX X0 0 YY0 0b b，设原问题和对

14、偶问题的最优解为设原问题和对偶问题的最优解为XX、YY CX CX C CX X0 0 Yb Yb Y Y0 0 b b C CX X0 0 Y Y0 0b b CX CX C CX X0 0 Y Y0 0 b Ybb Yb CX=Yb CX=Yb换句话说：换句话说：当对偶问题和原问题目标函当对偶问题和原问题目标函数值相同时数值相同时 Z=W Z=W，则，则 XX和和 YY一定是一定是对偶问题和原问题的最优解。或者说如对偶问题和原问题的最优解。或者说如果对偶问题和原问题有最优解，那么它果对偶问题和原问题有最优解，那么它们的目标函数值一定相等。们的目标函数值一定相等。如果原问题有最优解，则其对如

15、果原问题有最优解，则其对偶问题也有最优解，则它们对应的偶问题也有最优解，则它们对应的两个目标函数最优值相等。两个目标函数最优值相等。如果如果X X0 0、Y Y0 0 分别是原问题和对偶问题的分别是原问题和对偶问题的可行解，并且有最优解，则可行解，并且有最优解，则 X X0 0、Y Y0 0 分别是原分别是原始问题和对偶问题的最优解始问题和对偶问题的最优解,则它们的最优值则它们的最优值相同，即对应的，相同，即对应的，CXCX0=0=Y Y0 0b b。l1.原问题有确定的最优解原问题有确定的最优解,对偶问题就有对偶问题就有确定的最优解确定的最优解,且最优值相等且最优值相等;l2.原问题有可行解

16、但无最优解原问题有可行解但无最优解,对偶问题对偶问题无可行解无可行解,更无最优解更无最优解;l3.原问题无可行解原问题无可行解,对偶问题有可行解但对偶问题有可行解但无最优解无最优解;l4.原问题无可行解原问题无可行解,对偶问题无可行解对偶问题无可行解,更更无最优解无最优解。问题与解的状态问题与解的状态对偶对偶问题问题有最优解有最优解无界解无界解无可行解无可行解原原问问题题有最优解有最优解一定一定不可能不可能不可能不可能无界解无界解不可能不可能不可能不可能可能可能无可行解无可行解不可能不可能可能可能可能可能对偶问题对偶问题Min W=Yb s.t.YAC Y0设设X X0 0 、Y Y0 0 分

17、别为原问题和对偶问题的分别为原问题和对偶问题的可行解可行解,则则X X0 0 、Y Y0 0分别为分别为原问题和对偶原问题和对偶问题问题最优解的充要条件是：最优解的充要条件是：YSX X0 0=0 =0 和和 Y Y0 0X XS S =0=0原问题原问题Max Z=CX s.t.AX b X0原问题原问题Max z=CX Max z=CX AX+X AX+XS S=b=b X,XX,XS S 0 0 把把AX+XAX+XS S=b=b 左乘一个左乘一个Y YYAX+YXYAX+YXS S=Yb=YbYb=YAX+YXYb=YAX+YXS S 对偶问题对偶问题Min W=YbMin W=Yb

18、YA-YYA-YS S=C=C Y,Y Y,YS S 0 0 把把 YA-YYA-YS S=C=C 右乘一个右乘一个X X YAX-Y YAX-YS SX X =CX=CX CX=YAX-YCX=YAX-YS SX X Yb=Yb=AXAXY Y+X+XS SY Y CX=CX=AYAYX X-Y-YS S X X 两式相减两式相减W-W-Z=XZ=XS SY Y+Y YS S X X如果有最优解如果有最优解 Z=WZ=W Y YS SX X+X XS SY=0 Y=0 由于非负性由于非负性 Y YS SX=XX=XS SY Y=0=0结论：如果结论：如果 Y YS SX=XX=XS SY Y

19、=0 =0 则则 X X、Y Y 分别是原问题和对偶问题的分别是原问题和对偶问题的最优解。最优解。Max z=x1+2x2+3x3+4x4s.t x1+2x2+2x3+3x3+xS1=20 2x1+x2+3x3+2x4+xS2=20 xj 0 j=1,20 j=1,24 4 xs1,2 0 0 写出其对偶问题写出其对偶问题:对偶问题为：对偶问题为：Min W=20yMin W=20y1 1+20y+20y2 2s.t ys.t y1 1+2y+2y2 2 1 1 2y 2y1 1+y+y2 2 2 2 2y 2y1 1+3y+3y2 2 3 3 3y 3y1 1+2y+2y2 2 4 4 y

20、y1 1、y y2 2 0 0用图解法求得用图解法求得最优解最优解:y y1 1=1=12 2，y y2 2=0=02,Min W=282,Min W=28由于松弛互补由于松弛互补 Y YS SX=X=Y YX XS S =0=0 对偶问题标准化为：对偶问题标准化为：Min z=20yMin z=20y1 1+20y+20y2 2s.t ys.t y1 1+2y+2y2 2-y-ys1 s1=1=1 2y 2y1 1+y+y2 2-y-ys2 s2 =2 2 2y 2y1 1+3y+3y2 2-y-ys3 s3=3=3 3y 3y1 1+2y+2y2 2-y-ys4 s4=4 4 y y1 1

21、,y,y2 2,y,ys1-s4 s1-s4 0 0 1 1、y y1 1=1=12 2 0 0，y y1 1 x xs1s1=0 x=0 xs1s1=0=02 2、y y2 2=0=02 2 0 0，y y2 2 x xs2s2=0 =0 x xs2s2=0=03 3、y y1 1+2y+2y2 2=1=16 6 隐含隐含y ys s0 0 x x1 1=0=04 4、2y2y1 1+y+y2 2=2=26 6 隐含隐含y ys2s20 x0 x2 2=0=05 5、2y2y1 1+3y+3y2 2=3 =3 隐含隐含y ys3s3 =0 0 考虑考虑 y ys3s3x x3 3=0 x=0

22、 x3 3=0=0 或为任意或为任意6 6、3y3y1 1+2y+2y2 2=4 =4 隐含隐含y ys4 s4 =0 0 考虑考虑 y ys4s4x x4 4=0 x=0 x4 4=0 =0 或为任意或为任意据上所述：x x1 1=0=0，x x2 2=0=0，x x3 3、x x4 4任意任意计算计算x x3 3、x x4 4的值的值 2x2x3 3+3x+3x3 3 =20=20 3x 3x3 3+2x+2x4 4 =20 20得出：得出：x x3 3=4=4，x x4 4=4 4，Max z=z=2828原问题原问题Max Z=CX AX+XS=b X,XS 0对偶问题对偶问题Min

23、W=Yb YA-YS=C Y,YS 0 则原问题单纯形表中的检验则原问题单纯形表中的检验数行对应其对偶问题的一个基本数行对应其对偶问题的一个基本解解,其对应关系如下表：其对应关系如下表：原问题原问题 Max z=CMax z=CB BX XB B+C CN NX XN N BX BXB B+N+NX XN N+X+XS S=b b X XB B、X XN N、X XS S00对偶问题对偶问题 Min W=Min W=Y b b st:YA-Y st:YA-YS S=C,=C,YS=(YS1，YS2)把它分解为：把它分解为：YB-YYB-YS1 S1=C=CB B YN-Y YN-YS2 S2=

24、C=CN N Y,Y Y,YS1S1，Y YS2S2 0 0注：注：Y YS1 S1 原问题中基变量原问题中基变量X XB B的剩余变量的剩余变量，Y YS2 S2 原问题中非基变量原问题中非基变量X XN的剩余变量。的剩余变量。j=Cj=CN N-C-CB BB B-1-1N=Cj Zj =Cj Zj 原问题的检验数原问题的检验数令：令：Y=CBB-1 并把它们代入对偶问题中：并把它们代入对偶问题中：YB-YYB-YS1 S1=CBB-1B-YB-YS1 S1=C=CB B CB-Y-YS1 S1=C=CB B计算结果：计算结果：Y YS1 S1=0=0（基变量的剩余（基变量的剩余变量变量=

25、0=0）YN-YYN-YS2 S2=CBB-1N-YN-YS2 S2=C=CN N Y YS2 S2=-=-（C CN N CBB-1N N）因为是求最小值因为是求最小值 Y YS2 S2 =-j Y,Y Y,YS1S1，Y YS2S2 0 0结论：结论：基变量的剩余变量基变量的剩余变量Y YS1S1=0=0，对偶问题非基变量的检验数与对偶问题非基变量的检验数与原问题非基变量的检验数值原问题非基变量的检验数值相同符号相反，相同符号相反，Y YS2S2=-jj 说明对偶问题的检验数只说明对偶问题的检验数只有小于有小于0 0时才可以继续迭代。时才可以继续迭代。对偶问题最优解是原对偶问题最优解是原问

26、题剩余非基变量检验数问题剩余非基变量检验数的相反数的相反数 Y=Y=C CB BB B-1-1具体如下表具体如下表:原问题原问题变量变量 XB XN XS原问题原问题检验数检验数0 CN-CB B-1 N=N-CB B-1=S对偶问对偶问题变量题变量YS1=0YS2=-（CN-CB B-1 N）=-NY=CB B-1=-S结论：基变量的剩余变量为结论：基变量的剩余变量为0 0，非基变量的，非基变量的剩余变量与原问题的检验数符号相反。剩余变量与原问题的检验数符号相反。1.弱对偶性弱对偶性两个问题的可行解对应的目标函数值互为上下两个问题的可行解对应的目标函数值互为上下界。界。(最大化的目标函数值不

27、超过最小化的目标函数值最大化的目标函数值不超过最小化的目标函数值)2.最优性最优性两个问题最优解的目标函数值必相等。两个问题最优解的目标函数值必相等。3.强对偶性强对偶性两个问题都有可行解时则两个问题必都有最优两个问题都有可行解时则两个问题必都有最优解。解。4.互补松弛性互补松弛性两个问题最优解中，一个问题中某个变量取两个问题最优解中，一个问题中某个变量取值非零，则该变量在对偶问题中对应的某个约束条件必为值非零，则该变量在对偶问题中对应的某个约束条件必为紧约束；反之，如果约束条件为松约束，则其对应的对偶紧约束；反之，如果约束条件为松约束，则其对应的对偶变量一定取值为零。因此，该定理又称为松紧定

28、理。变量一定取值为零。因此，该定理又称为松紧定理。5.原问题的检验数与对偶问题解的关系原问题的检验数与对偶问题解的关系6.对称性对称性原始问题与对偶问题是两个互为对偶的问题。原始问题与对偶问题是两个互为对偶的问题。lMax z =2x1+4x2+x3+x4ls.t x1 +3x2 +x4 8l 2x1 +x2 6l x1 +x2+x3 9l x2+x3+x4 6l x1401.试写出该问题的试写出该问题的对偶问题对偶问题。2.2.已知原已知原问题的最优解为问题的最优解为X=2 2 4 0T。试根据对试根据对偶理论，直接求出对偶问题的偶理论，直接求出对偶问题的最优解。最优解。二、对偶单纯形法及特

29、点二、对偶单纯形法及特点三、对偶单纯形法的求解步骤和计算举例三、对偶单纯形法的求解步骤和计算举例四、对偶单纯形法和单纯形法区别四、对偶单纯形法和单纯形法区别五、对偶单纯形法的适用范围五、对偶单纯形法的适用范围六、对偶单纯形法的优点六、对偶单纯形法的优点 对偶单纯形法的基本思想是：从对偶单纯形法的基本思想是：从原问题原问题的一个的一个基本解基本解出发，此基本解不一定可出发，此基本解不一定可行，但它对应着一个对偶可行解（检验行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个数非正），所以也可以说是从一个对偶对偶可行解可行解出发；然后检验原问题的基本解出发；然后检验原问题的基本解是否可

30、行，即是否有负的分量，如果有是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可基本解，此基本解对应着另一个对偶可行解（检验数非正）。行解（检验数非正）。l如果得到的基本解的分量皆非负则如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），对偶解的可行性（即检验数非正），使原问题的基本解由不可行逐步变使原问题的基本解由不可行逐步变为可行，当同时得到对偶问题与原为可行，当同时得到对偶问题

31、与原问题的可行解时，便得到原问题的问题的可行解时，便得到原问题的最优解。最优解。应用前提：应用前提：有一个基，其对应的基有一个基，其对应的基满足满足:1.1.单纯形表的检验数行全部非正（对偶单纯形表的检验数行全部非正（对偶可行）；可行）；2.2.变量取值可有负数（非可行解）。变量取值可有负数（非可行解）。注：注：通过矩阵行变换运算，使所有相应变量通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。取值均为非负数即得到最优单纯形表。1.1.对偶单纯形法对偶单纯形法 利用对偶原理求解利用对偶原理求解原问题原问题的一种方的一种方 法。而不是用单纯形法求解对偶问法。而不是用单纯形法求解

32、对偶问 题。题。(不是对偶问题的单纯形法不是对偶问题的单纯形法)2.2.对偶单纯形法的特点：对偶单纯形法的特点：1 1、始终保持原问题的可行性、始终保持原问题的可行性 2 2、始终保持检验数的非正、始终保持检验数的非正 3 3、在迭代过程中直到、在迭代过程中直到基变量取值基变量取值(常数项常数项)逐渐变为非负为止。逐渐变为非负为止。例：例：Min w=XMin w=X1 1+4X+4X2 2+3X+3X4 4s.t Xs.t X1 1+2X+2X2 2-X-X3 3+X+X4 4 3 3 -2X -2X1 1-X-X2 2+4x+4x3 3+X+X4 4 2 2 X X1 1 X X4 4 0

33、 0该问题可以用两阶段法或大该问题可以用两阶段法或大M M法法(人工变量法人工变量法)求解，但很麻烦，求解，但很麻烦，下面用对偶单纯形法求解。下面用对偶单纯形法求解。三、对偶单纯形法的求解步骤和计算举例三、对偶单纯形法的求解步骤和计算举例1.1.把原问题化标准型把原问题化标准型2.2.给定一个初始对偶可行的基本解给定一个初始对偶可行的基本解,建立初始对偶单建立初始对偶单纯形表纯形表,对应一个基本解对应一个基本解,所有检验数均非正所有检验数均非正,转转3 3；3.3.进行最优性检验进行最优性检验:若若b0,b0,则得到最优解则得到最优解,停止停止;若所有若所有a akjkj0(j=1,2,0(j

34、=1,2,n),n)，则原问题无可行解，则原问题无可行解,更无最优解更无最优解,停止停止;否则若有否则若有a akjkj0,0,则转则转4 4；4.4.换基迭代换基迭代(1)首先确定出基变量首先确定出基变量:出基出基用限定性常数进行判断，用限定性常数进行判断，若有若有b0,b0,取取min(bb)所对所对应的应的k k行的基行的基变量为出基变量变量为出基变量XK,转转5 5；(2)确定入基变量：确定入基变量：入基入基若所有若所有a akjkj0(j=1,2,0(j=1,2,n),n)，则原问题无可行解，则原问题无可行解,更无最优解更无最优解,停止停止;否则否则,若有若有a akjkj0 0 则

35、选则选 =min=minj/a/akjkjaakjkj00=r r/a/akrkr那么那么所对应的变量所对应的变量x xr r为进基变量为进基变量,转转5 5；5.5.换基迭代运算换基迭代运算以以a akrkr为主元素为主元素,作矩阵行变换使其变为作矩阵行变换使其变为1,1,该列其他元该列其他元素变为素变为0,0,转转3 3。6.6.进行最优性检验进行最优性检验:最优解：最优解：基变量的检验数为基变量的检验数为0l 非基变量的检验数小于等于非基变量的检验数小于等于0l 限定性常数大于限定性常数大于0l得出原问题与对偶问题的最优解和最优值得出原问题与对偶问题的最优解和最优值l7.7.否则转否则转

36、4,4,重复进行。重复进行。l8.8.对于非对称型对偶问题的解与原问题对于非对称型对偶问题的解与原问题检验数的关系需要换算。检验数的关系需要换算。Min w=XMin w=X1 1+4X+4X2 2+3X+3X4 4s.t -Xs.t -X1 1-2X-2X2 2+X+X3 3-X-X4 4 -3 3 2X 2X1 1+X+X2 2-4x-4x3 3-X-X4 4 -2-2 X X1 1 X X4 4 0 0 Max Max-w=-X w=-X1 1-4X-4X2 2-3X-3X4 4 -X -X1 1-2X-2X2 2+X+X3 3-X-X4 4+X X5 5 =-=-3 3 2X 2X1

37、1+X+X2 2-4x-4x3 3-X-X4 4+X X6 6 =-2-2 X X1 1 X X6 6 0 0 C Cj j -1 -4 0 -3 0 0bbC CB BX XB B X X1 1 X X2 2 X X3 3 X X4 4 X X5 5 X X6 6 0 0X X5 5X X6 6-1 -2 1 -1 1 0 2 1 -4 -1 0 1-3-2j j-1 -4 0 -3 0 0Z=0 C Cj j -1 -4 0 -3 0 0bbC CB BX XB B X X1 1 X X2 2 X X3 3 X X4 4 X X5 5 X X6 6-1 0X X1 1X X6 6 1 2

38、1 -1 -1 0 0 -3 -2 -3 2 1 3-8j j 0 -2 -1 -2 -1 0Z=-3 C Cj j X X1 1 X X2 2 X X3 3 X X4 4 X X5 5 X X6 6bb C CB B XB B -1 -4 0 -3 0 0-10X X1 1X X6 6 1 2 1 -1 -1 0 0 -3 -2 -3 2 1 3-8j j 0 -2 -1 -2 -1 0Z=-3 C Cj j X X1 1 X X2 2 X X3 3 X X4 4 X X5 5 X X6 6bb C CB B XB B-1 -4 0 -3 0 0-1 0X X1 1X X3 3 1 7/2

39、0 2/5 -2 -1/2 0 3/2 1 3/2 -1 -1/2 7 4j j 0 -2 -1 -2 -1 0Z=-7Min W=2xMin W=2x1 1+3x+3x2 2+4x+4x3 3 S.t.xS.t.x1 1+2x+2x2 2+x+x3 3 3 3 2x 2x1 1-x-x2 2+3x+3x3 3 4 4 x x1 1,x,x2 2,x,x3 3 0 0 标准化：标准化：Max z=-2xMax z=-2x1 1-3x-3x2 2 -4x-4x3 3 s.t.s.t.-x-x1 1-2x-2x2 2-x-x3 3+x+x4 4=-3=-3 -2x -2x1 1+x+x2 2-3x

40、-3x3 3+x+x5 5=-4=-4 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5 0 0单纯形法单纯形法:1.求解原问题求解原问题2.建立初始建立初始单纯形表单纯形表3.3.可行基可行基4.4.基本可行解基本可行解5.5.凸集顶点开始凸集顶点开始6.6.初始初始单纯形表单纯形表最终表最终表7.7.可行基可行基 最优基最优基8.8.基本可行解基本可行解 迭代迭代基本可行解基本可行解(最优解最优解)9.9.凸集顶点凸集顶点 迭代迭代凸集顶点凸集顶点1.求解原问题求解原问题2.建立初始建立初始单纯形表单纯形表3.可行基可行基4.可行的可行的基本解基本解5.非凸集顶点开始非

41、凸集顶点开始6.初始初始单纯形表单纯形表最终表最终表7.可行基可行基 最优基最优基8.非可行解非可行解 迭代迭代基本可行解基本可行解(最优解最优解)9.非凸集顶点非凸集顶点 迭代迭代凸集顶点凸集顶点10.b b0 0 j0 0 b 0 b 0 j 0 010.b 0,j 0 b 0 j 0单纯形法单纯形法:是是是是是是是是否否否否否否否否所有所有所有所有得到得到最优解最优解计算计算计算计算典式对应原规划的基典式对应原规划的基本解是可行的本解是可行的典式对应原规划的典式对应原规划的基本解的检验数基本解的检验数所有所有所有所有计算计算计算计算以为中心元素进行迭代以为中心元素进行迭代以为中心元素进行

42、迭代以为中心元素进行迭代停停没没有有最最优优解解没没有有最最优优解解单纯形法单纯形法对偶单纯形法对偶单纯形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min 对偶单纯形法适合于解如下形式的线性规对偶单纯形法适合于解如下形式的线性规划问题划问题njxmibxacxcfjnjijijnjjjj,2,1,0,2,10min11W 在引入松弛变量化为标准型之后，在引入松弛变量化为标准型之后，约束等式约束等式两侧同乘两侧同乘-1-1，能够立即得到检验数全部非正能够立即得到检验数全部非正的问题基本解，可以直接建立初始对偶单纯的问题

43、基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。形表进行求解，非常方便。对于有些线性规划模型，如果在开始对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这为使检验数全部非正而作的许多工作。从这个意义上看，可以说，个意义上看，可以说，对偶单纯形法是单纯对偶单纯形法是单纯形法的一个补充。形法的一个补充。除此之外，在对线性规划除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形进行灵敏度分析中有时也要用到对偶单纯形

44、方法，可以简化计算。方法，可以简化计算。l1.可尽量避免人工变量法可尽量避免人工变量法l2.减少计算工作量减少计算工作量l 对偶问题的经济解释对偶问题的经济解释l l 影子价格影子价格1.1.影子价格的概念：影子价格的概念：在最优决策中，增加某种在最优决策中，增加某种资源的投入时，目标函数的提资源的投入时，目标函数的提高量，称为这种资源的影子价高量，称为这种资源的影子价格。格。也就是说影子价格反映的也就是说影子价格反映的是增加单位的投入与带来的产是增加单位的投入与带来的产出量之间的关系。出量之间的关系。影子价格也称机会价格影子价格也称机会价格 Max Z=CX=YbY 表示资源在生产中的价格，

45、而不是市场表示资源在生产中的价格，而不是市场价，价，b 表示资源的数量，当价格发生变化表示资源的数量，当价格发生变化是对目标函数值的影响，是对目标函数值的影响，Y 的这种变化对的这种变化对目标函数的影响称为影子价格。目标函数的影响称为影子价格。对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解Y称为称为m种资源的种资源的影子价格（影子价格（Shadow Price）增加单位资源可以增加利润增加单位资源可以增加利润减少一件产品可以节省资源减少一件产品可以节省资源减少一件产品可以节省的资源可以增加利润减少一件产品可以节省的资源可以增加利润 如果线性规划问题的最优基为如

46、果线性规划问题的最优基为B B，则最优解：则最优解：X XB B=B B-1-1b Z=Cb Z=CB B B B-1-1b b 对偶问题：对偶问题：Y=CY=CB B B B-1 -1 W=Yb=CW=Yb=CB B B B-1-1b b 如果资源增加如果资源增加 b b则目标函数则目标函数的增量为：的增量为：Z=CZ=CB B B B-1-1 b b =Y =Y b b当当 b=1b=1时时 Z=Y Z=Y Z=YZ=Y Z/Z/b=(yb)=yb=(yb)=y说明对偶问题的最优解，既为说明对偶问题的最优解，既为原问题目标函数的增加量。原问题目标函数的增加量。Y Y即影子价格即影子价格Y

47、Y值是原问题剩余松弛变量检验值是原问题剩余松弛变量检验数的相反数数的相反数 (1)(1)影子价格是对现有资源实现最大效益影子价格是对现有资源实现最大效益时的一种估价。时的一种估价。企业可以根据现有资源的影子价格，对企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可产能力

48、，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。考虑买进该设备，否则不宜买进。（2 2）影子价格表明资源增加对总效益产生的影子价格表明资源增加对总效益产生的影响。根据推论影响。根据推论“设设x x0 0和和y y0 0分别为原规划分别为原规划（LPLP）和对偶规划（）和对偶规划（LDLD）的可行解，当）的可行解，当cxcx0 0=b=bT Ty y0 0时，时，x x0 0、y y0 0分别是两个问题的最优解分别是两个问题的最优解”可知，在最优解的情况下，有关系可知，在最优解的情况下，有关系 因此，可以将因此，可以将z z*看作是看作是b bi i,i=1,2,i=1,2，,m,

49、m的函数，的函数，对对b bi i求偏导数可得到求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函数值的增这说明，如果右端常数增加一个单位，则目标函数值的增量将是量将是*22*11*mmybybybfZmiybZii,2,1,*miyi,2,1,*l影子价格反映了不同的局部影子价格反映了不同的局部或个体的增量可以获得不同或个体的增量可以获得不同的整体经济效益。如果为了的整体经济效益。如果为了扩大生产能力，考虑增加设扩大生产能力，考虑增加设备，就应该从备，就应该从影子价格高的影子价格高的设备入手。设备入手。这样可以用较少这样可以用较少的局部努力，获得较大的整的局部努力，获得较大的整体效益

50、。体效益。需要指出，影子价格不是固定不变需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变变化时，有可能使影子价格发生变化。另外，影子价格的经济含义化。另外，影子价格的经济含义（2 2），是指资源在一定范围内增），是指资源在一定范围内增加时的情况，当某种资源的增加超加时的情况，当某种资源的增加超过了这个过了这个“一定的范围一定的范围”时，总利时，总利润的增加量则不是按照影子价格给润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。将在灵敏度分析一节中讨论。.资源