运筹学2.对偶理论与灵敏度分析

1、1第二章第二章 线性规划的对偶理论线性规划的对偶理论窗含西岭千秋雪，门泊东吴万里船窗含西岭千秋雪，门泊东吴万里船本章主要内容本章主要内容： 线性规划的对偶问题概念、理论及经济意义线性规划的对偶问题概念、理论及经济意义 线性规划的对偶单纯形法线性规划的对偶单纯形法 线性规划的灵敏度分析线性规划的灵敏度分析2第一节第一节 对偶问题的提出对偶问题的提出 材料材料产品产品甲甲乙乙丙丙丁丁单件单件收益收益A32112000B41324000C22343000限额限额600400300200假设工厂考虑不进行生产而把假设工厂考虑不进行生产而把全部资源都转让，问如何定价全部资源都转让，问如何定价这些资源，既

2、能使其获利不低这些资源，既能使其获利不低于安排生产所获得的收益，又于安排生产所获得的收益，又能使资源租让具有竞争力。能使资源租让具有竞争力。一、引例一、引例Max Z = 2000 x1+4000 x2+3000 x3 s.t. 3x1+4x2+2x3600 2x1+ x2+2x3400 x1+3x2+3x3300 x1+2x2+4x3200 x1, x2, x30 Min W =600y1+400y2+300y3+200y4 s.t. 3y1+2y2+ y3+ y42000 4y1+ y2+3y3+2y44000 2y1+2y2+3y3+4y43000 y1, y2, y3, y40 x1x

3、2x3y1 y2 y3 y43二、对偶问题二、对偶问题（1 1）对称）对称LPLP问题的定义问题的定义MaxZCXAXbS TX. .0 MinWYbYACS TY. .0 （2 2）对称）对称LPLP问题的对偶问题问题的对偶问题( )L()DMinWYbYACS TY. .0 第一类对称形式第一类对称形式第二类对称形式第二类对称形式MaxZCXAXbS TX. .0 原问题原问题对偶问题对偶问题4( )L()DMinWYbYACS TY. .0 MaxZCXAXbS TX. .0 原问题中目标函数的价值向量原问题中目标函数的价值向量C C，在对偶问题中是约束条，在对偶问题中是约束条件的右端常

4、数项；件的右端常数项；原问题中约束条件的右端常数项原问题中约束条件的右端常数项b b，在对偶问题中是目标，在对偶问题中是目标函数的价值系数；函数的价值系数；原问题中约束条件的系数矩阵在对偶问题中进行了转置。原问题中约束条件的系数矩阵在对偶问题中进行了转置。5Max Z = 2000 x1+4000 x2+3000 x3 s.t. 3x1+4x2+2x3600 2x1+ x2+2x3400 x1+3x2+3x3300 x1+2x2+4x3200 x1, x2, x30 Min W =600y1+400y2+300y3+200y4 s.t. 3y1+2y2+ y3+ y42000 4y1+ y2+

5、3y3+2y44000 2y1+2y2+3y3+4y43000 y1, y2, y3, y40 原问题中的原问题中的约束条件个数约束条件个数对应于对偶问题中的对应于对偶问题中的决策变量个数决策变量个数原问题中的原问题中的决策变量个数决策变量个数对应于对偶问题中的对应于对偶问题中的约束条件个数约束条件个数原问题原问题求极大化求极大化，对偶问题，对偶问题求极小化求极小化对于对称的对于对称的LP问题，如果原问题是求极大化问题，如果原问题是求极大化 其对偶问题的决策变量其对偶问题的决策变量的方向与原问题约束条的方向与原问题约束条件不等号的方向相反件不等号的方向相反 其对偶问题的约束条件其对偶问题的约束

6、条件不等号的方向与原问题不等号的方向与原问题决策变量的方向相同决策变量的方向相同6例例1 1 写出下列写出下列LPLP问题的对偶问题问题的对偶问题对偶对偶 Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1 ,x2 0 s.t. y1+4y2 2 2y1 +4y3 3 y1 ,y2,y3 0 I II设设 备备 1 2 8台时台时 原材料原材料A 4 0 16公斤公斤原材料原材料B 0 4 12公斤公斤设工厂每生产一件产品设工厂每生产一件产品I 可获利可获利2 2元，元，每生产一件产品每生产一件产品II 可获利可获利3 3元，问应元，问应如何安排生产使该

7、厂获利最多？如何安排生产使该厂获利最多？2 3y1y2y3Min W =8y1+16y2+12y37（3 3）对偶问题的对偶是原问题）对偶问题的对偶是原问题推导过程推导过程变形对偶变变形形对偶对偶对偶对偶变变形形( )LMax Z=CXs.t. AXb X0()DMin W=Ybs.t. YAC Y0Max W = -Ybs.t. -YA -C Y0Min Z = (-C)Xs.t. (-A)X (-b) X0()DDMax W = Y(-b)s.t. Y(-A) (-C) Y0加工加工81212312312312334334748:1,0MinWxxxxxxxxSTxxxxxx 123123

8、1231231237834334: 40,0MaxZyyyyyyyyySTyyyyyy 例例2 2 写出下列写出下列LPLP问题的对偶问题问题的对偶问题对于对称的对于对称的LP问题，如果原问题是求极小化问题，如果原问题是求极小化 其对偶问题的决策变量其对偶问题的决策变量的方向与原问题约束条的方向与原问题约束条件不等号的方向相同件不等号的方向相同 其对偶问题的约束条件其对偶问题的约束条件不等号的方向与原问题不等号的方向与原问题决策变量的方向相反决策变量的方向相反对偶对偶9三、非对称三、非对称LPLP问题的对偶问题问题的对偶问题例例3 3 写出下列写出下列LPLP问题的对偶问题问题的对偶问题解：用

9、解：用x2= -x2, x3=x3-x3代入上述代入上述LP问题，并将其问题，并将其化为第一类对称形式化为第一类对称形式Max Z = x1+2x2+x3 x1+x2-x3 2 s.t. x1 -x2+x3 = 1 2x1+x2+x3 2 x10, x20 ,x3无约束无约束 Max Z = x1-2x2 +x3-x3 x1 -x2 -x3+x3 2 x1+x2+x3 -x3 1s.t. -x1 -x2 -x3+x3 -1 -2x1+x2 -x3+x3 -2 x1, x2, x3, x3 0 x1 -x2+x3 1x1 -x2+x3 1x1 -x2+x3 1-x1 +x2-x3 - 1-2x1

10、-x2-x3 -210上述第一类对称形式上述第一类对称形式LP问题的对偶问题为：问题的对偶问题为：则上述问则上述问题变为：题变为：Min W =2y1+y2 -y3-2y4 y1+y2 -y3-2y4 1 -y1+y2 -y3 +y4 -2 s.t. -y1+y2 -y3 -y4 1 y1 -y2+y3 +y4 -1 y1, y2, y3, y4 0 Min W =2u1+u2+2u3 u1+u2+2u3 1 s.t. u1 -u2+ u3 2 -u1+u2+ u3 =1 u10, u30 ,u2无约束无约束 令令 u1= y1 u2=y2-y3 u3=-y4Max Z = x1-2x2 +x

11、3-x3 x1 -x2 -x3+x3 2 x1+x2+x3 -x3 1s.t. -x1 -x2 -x3+x3 -1 -2x1+x2 -x3+x3 -2 x1, x2, x3, x3 0 -y1+y2 -y3 -y4 1y1-y2+y3 -y4 211(D)Min W =2u1+u2+2u3 u1+u2+2u3 1 s.t. u1 -u2+ u3 2 -u1+u2+ u3 =1 u10, u30 ,u2无约束无约束 (L)Max Z = x1+2x2+x3 x1+x2-x3 2 s.t. x1 -x2+x3 = 1 2x1+x2+x3 2 x10, x20 ,x3无约束无约束 对偶关系：对偶关系

12、：一个问题第一个问题第i个变量的约束情况决定另一问题个变量的约束情况决定另一问题第第i个约束不等式的方向，反之亦然。个约束不等式的方向，反之亦然。正常的对正常的，不正常的对不正常的正常的对正常的，不正常的对不正常的 原问题约束条件是等式对应于对偶问题决策变原问题约束条件是等式对应于对偶问题决策变量无约束，反之亦然量无约束，反之亦然12例例3 3 直接写出直接写出LPLP问题的对偶问题问题的对偶问题1231231231231232 2 1:2 20,0,MaxZxxxxxxxxxSTxxxxxx 无无约束束12322MinWuuu123uuu1232uuu123uuu12 10u ，1:ST 2

13、u无无约束束，30u 13 12312312312312322212:10,0MinWuuuuuuuuuSTuuuuuu 无无约束束1232MaxZxxx:ST 123xxx123xxx1232xxx21210 x 20 x 3x 无无约束束 14原问题原问题对偶问题对偶问题目标函数目标函数Max zMin w变量变量n个约束条件约束条件n个=00无约束无约束约束条件约束条件m个=变量变量m个00无约束无约束约束条件右端项约束条件右端项目标函数的价值系数目标函数的价值系数目标函数的价值系数目标函数的价值系数约束条件右端项约束条件右端项15第二节第二节 LPLP问题的对偶理论问题的对偶理论若若X

14、(0),Y(0)分别为分别为(L),(D)的可行解，则有的可行解，则有CX(0)Y(0)b 定理定理1(1(弱对偶定理弱对偶定理): ): 极大化原问题目标函数值总是不极大化原问题目标函数值总是不大于其对偶问题的目标函数值。大于其对偶问题的目标函数值。证明：证明：max z=CX;AXb;X0(L) min w=Yb;YAC;Y0(D)由于由于X(0)是是(L)的可行解，有的可行解，有AX(0)b, X(0)0.由于由于Y(0)是是(D)的可行解，有的可行解，有Y(0)0. Y(0)左乘不等式组左乘不等式组AX(0)b的两边得：的两边得：Y(0)AX(0) Y(0)b (1)16 min w=

15、Yb;YAC;Y0(D)又又Y(0)AC用用X(0)(X(0)0)右乘上式，得右乘上式，得Y(0)AX(0) CX(0) (2)由（由（1），（），（2）得：得：CX(0)Y(0)AX(0)Y(0)b所以所以 CX(0)Y(0)b17推论推论1(P57)1(P57) 若若LPLP问题有无界解，则其对偶问题无可行解问题有无界解，则其对偶问题无可行解( (弱对偶性弱对偶性) )； 若若LPLP问题无可行解，则对偶问题或有无界解或无可行解。问题无可行解，则对偶问题或有无界解或无可行解。x2x111-1-1y2y111-1-1( (书书P57)P57)原问题原问题对偶问题对偶问题18推论推论2 2极大

16、化问题（极大化问题（L）的任何一个可行解所对应的目标函）的任何一个可行解所对应的目标函数值都是其对偶问题数值都是其对偶问题（D）目标函数值的下界。目标函数值的下界。极小化问题（极小化问题（D）的任何一个可行解所对应的目标）的任何一个可行解所对应的目标函数值都是其对偶问题函数值都是其对偶问题（L）目标函数值的上界。目标函数值的上界。推论推论3 3YbCX(0)CX Y(0)bmax z=CX; AXb; X0(L) min w=Yb; YAC; Y0(D)19例例4 4 考虑下面一对考虑下面一对LPLP问题问题其对偶问题为：其对偶问题为：由于由于X(0) =(1,1,1,1)T,Y(0)=(1,

17、1)T分别为分别为(L),(D)的可行解，的可行解，Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3+2x4 20 x1,x2,x3,x4 0 Min W = 20y1+20y2 y1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y20Z(0)=10W(0)=40W10推论推论2Z40推论推论3故故Z40,W10.20P59（书（书 例例4 4）12123123123max221,0zxxxxxxxxxxx 利用推论利用推论1 1 min W = 2y1+y2 - y1- 2y2 1

18、 s.t. y1+ y2 1 y1- y2 0 y1, y20X=(0, 0, 0)s.t.若若LP问题无可行解，则对偶问题或有无界解或无可行解。问题无可行解，则对偶问题或有无界解或无可行解。21定理定理2 2（最优性准则）（最优性准则） 当当LPLP问题目标函数值与其对偶问问题目标函数值与其对偶问题目标函数值相等时，各自的可行解即为最优解。题目标函数值相等时，各自的可行解即为最优解。(P57)(P57)若若X(0),Y(0)分别为分别为(L)，(D)的可行解的可行解, ,且且CX(0)Y(0)b,则则X(0),Y(0)分别为分别为(L)，(D)的最优解。的最优解。证明：证明：由定理由定理1

19、1可知，对于可知，对于(L)的任意可行解的任意可行解X，有，有CX Y(0)b 由于由于CX(0) =Y(0)b，CX CX(0) ，故故X(0)为为 (L) 的最优解；的最优解；同理，同理，由定理由定理1 1可知，可知，对于对于(D)的任意可行解的任意可行解Y，有，有YbCX(0)，由于由于CX(0) =Y(0)b，YbY(0)b，Y(0)为为(D)的最优的最优解。解。22例例5 5( )L()DMax Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3+2x4 20 x1,x2,x3,x4 0 Min W = 20y1+20y2 y

20、1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y20由于由于X(0)=(0,0,4,4)T, Y(0)=(6/5,1/5)T是是(L)，(D)的的可行解且可行解且 CX(0)=bTY(0)=28，所以，所以X(0),Y(0)分别为分别为(L)，(D)的最优解。的最优解。23线性规划的矩阵表示线性规划的矩阵表示Max Z=CXs.t. AX b X0令令A=(B,N), X= XB ,C=(CB,CN) XN由由AX+IXs=b (B,N,I) XB =b BXB+NXN+IXs=b BXB=b-NXN-IXs XN Xs XB=B-1b-B-1NX

21、N -B-1Xs (1)将将(1)式代入目标函数得式代入目标函数得Z=CX = (CB,CN) XB =CBXB+CNXN= CB (B-1b-B-1NXN -B-1Xs)+CNXN XN = CBB-1b+(CN-CBB-1N)XN -CB B-1Xs (2) Max Z=CX+0Xss.t. AX+IXs=b X, Xs0用非基变量表示基变量用非基变量表示基变量用非基变量表示目标函数用非基变量表示目标函数24=(0, CN-CBB-1N, -CB B-1) =(C-CBB-1A, -CB B-1)(C-CBB-1A, -CB B-1)= (C-CBB-1(B,N), -CB B-1)=(C

22、B-CBB-1B, CN-CBB-1N, -CB B-1)=(0, CN-CBB-1N, -CB B-1)若若CN-CBB-1N0, -CB B-10,则则Z为最优解为最优解令令XN=0, Xs=0，可以得到基可以得到基B的基可行解和目标函数值的基可行解和目标函数值XB=B-1b-B-1NXN -B-1XsZ= CBB-1b+(CN-CBB-1N)XN -CB B-1XsX=(XB, XN, Xs)=(B-1b,0,0)Z= CBB-1b25CCBXBbXBXNXS-ZCBXBB-1bCBCN0ICN-CBB-1NB-1NB-10-CBB-1-CBB-1b26初始单纯形表初始单纯形表cj CB

23、 XB b x1 x2 x3 x4 x5 j cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 0 x4 3 x2 2 16 3 1 0 1 0 -1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 -j -9 2 0 0 0 -3/40 x3 0 x4 0 x52 3 0 0 0 8 1612 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 2 3 0 0 004-3经过一次迭代经过一次迭代初始基初始基 第一轮第一轮迭代后迭代后的基的基P3 P4 P51 0 00 1 00 0 1B=P3 P4 P21 0 20 1 00 0 4B=1 0

24、 -1/20 1 00 0 1/4B-1=27初始单纯形表初始单纯形表cj CB XB b x1 x2 x3 x4 x5 j cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 0 x4 3 x2 2 16 3 1 0 1 0 -1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 -j -9 2 0 0 0 -3/40 x3 0 x4 0 x52 3 0 0 0 8 1612 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 2 3 0 0 004-3经过一次迭代经过一次迭代1 0 -1/20 1 00 0 1/4B-1=B-1 b=1 0 -1

25、/20 1 00 0 1/48 16122 16 3=Z= CBB-1b=928初始单纯形表初始单纯形表cj CB XB b x1 x2 x3 x4 x5 j cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 0 x4 3 x2 2 16 3 1 0 1 0 -1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 -j -9 2 0 0 0 -3/40 x3 0 x4 0 x52 3 0 0 0 8 1612 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 2 3 0 0 004-3经过一次迭代经过一次迭代1 0 -1/20 1 00 0 1/

26、4B-1=B-1A=-CBB-1=(0, 0, -3/4)A29定理定理3 3（强对偶定理）（强对偶定理） 若若(L)，(D)均有可行解，则均有可行解，则(L)，(D)均有最优解，均有最优解，且目标函数最优值相等。且目标函数最优值相等。证明：证明： 设设X(0),Y(0)分别为分别为(L)，(D)的可行解的可行解, ,由弱对偶定理由弱对偶定理( (推论推论3)3)，对于，对于(L)的任意可行解的任意可行解X，有，有CX Y(0)b，所以，所以CX在可行域内有上界，故在可行域内有上界，故(L)有最优解。有最优解。 同理，对于同理，对于(D)的任意可行解的任意可行解Y，由弱对偶定理由弱对偶定理（推

27、（推论论2 2），有有Y bCX(0)，所以，所以Yb在可行域内有下界，故在可行域内有下界，故(D)有最优解。有最优解。设设(L)的最优解为的最优解为X(0)，且，且X(0)所对应的最优基为所对应的最优基为B，X(0)可以表示为可以表示为X(0) = = XB(0) = = B-1b XN(0) 0max z=CX; AXb; X0(L) min w=Yb; YAC; Y0(D)30则则( (A, ,S)= ( (C, ,0) CBB-1(A, I)=( (C CBB-1A, CBB-1)0由于由于CCBB-1A0，所以所以CBB-1A C (1)(1)又又CBB-10，故故CBB-10. (

28、2). (2)令令Y(0)=CBB-1，由由(1)、(2)(2)知知Y(0)是是(D)的可行解的可行解. .因为因为CX(0)=(CB, CN) XB(0) =CBXB(0)+CNXN(0) = CBB-1b XN(0)Y(0)A CY(0)0 而而Y(0)b = CBB-1b 则则CX(0)=Y(0)b ，由最优性准则知，由最优性准则知， X(0),Y(0)分别为分别为(L)，(D)的最优解的最优解, , 且目标函数最优值相等。且目标函数最优值相等。31推论：推论： 在用单纯形法求解在用单纯形法求解LPLP问题问题(L)的最优单纯形表中，的最优单纯形表中，松弛变量的检验数的相反数就是其对偶问

29、题松弛变量的检验数的相反数就是其对偶问题(D)的最优解。的最优解。例例5 5 求下列问题对偶问题的最优解求下列问题对偶问题的最优解Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1 ,x2 0 解：化为标准型解：化为标准型Max Z =2x1+3x2+0 x3+0 x4+0 x5 s.t. x1+ 2x2+x3 = 8 4x1 +x4 =16 4x2 +x5=12 x1 ,x2 , x3, x4, x50 CCBXBbXBXNXS-ZCBXBB-1bCBCN0ICN-CBB-1NB-1NB-10-CBB-1-CBB-1b32cj 2 3 0 0 0 CB

30、 XB b x1 x2 x3 x4 x5 2 x1 0 x5 3 x244 2 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0此时达到最优解此时达到最优解X*=(4, 2)T, Max Z=14。对偶问题的最优解为对偶问题的最优解为Y*=(3/2, 1/8, 0)T运用单纯形法计算得原问题的最终表如下：运用单纯形法计算得原问题的最终表如下：33 推论：对偶问题的最优解对应于原问题的最优推论：对偶问题的最优解对应于原问题的最优单纯型表中松弛变量检验数的相反数或剩余变单纯型表中松弛变量检验数的相反数或剩余变量的检验数。量的检验

31、数。34Min z=2x1+3x2 x1+x2 350 x1 1252x1+x2 600 x1, x2 0Max w=350y1+125y2+600y3 s.t. y1+ y2+2y32 y1 + y3 3 y1 ,y2 0 ;y3 0cj 2 3 0 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 3 x2 2 x1 0 x4100250125 0 1 -2 0 -1 2 0 1 0 1 0 1 -1 0 0 0 1 1 1 -1 -1 原问题的最优单纯型表如下所示：原问题的最优单纯型表如下所示： 0 0 4 0 1 -4+M MY*=(4, 0, -1)Tw*=8

32、00例例35定理定理4 4（互补松弛定理）（互补松弛定理）在最优情况下，原问题的第在最优情况下，原问题的第i个决策变个决策变量与其对偶问题第量与其对偶问题第i个约束中的松弛变量的乘积恒为零个约束中的松弛变量的乘积恒为零。 , (1,1)k lkmln 设设X(0),Y(0)分别为分别为(L),(D)的的可行解，则可行解，则X(0),Y(0)分别为分别为(L),(D)的最优解的充要条件为的最优解的充要条件为 , ,有有(y1(0), , yk(0) , , ym(0) )xn+1xn+kxn+m= 0(ym+1, , ym+l , , ym+n)x1(0)xl(0)xn(0)= 036 m(1)

33、(1)若若xl(0) 0，则则ail yi(0) = Cl i=1 m(2)(2)若若ail yi(0) Cl ，则则xl(0) = 0 i=1 n(3)(3)若若yk(0) 0，则则akj xj(0) = bk j=1 n(4)(4)若若akj xj(0) 0y*40y*5=0y*6=040*123422320(1)xxxx *123423220(2)xxxx *342320 xx *343220 xx 所以所以x1*=x2*=0. 解：由互补松弛性知解：由互补松弛性知解得解得x3*= x4*=4. 所以所以(L)的最优解为的最优解为X*=(0,0,4,4)T由于由于代入代入(L)得得(y1

34、*, y2*) x5 =0 x6y30, y40， x1*(y3,y4,y5,y6) x2* =0 x3* x4*由于由于y1* 0, y2* 0, , 所以，所以，x5=0, x6=0代入代入(1)、(2)得得41若若X*,Y* 分别为分别为(L),(D)的最优解，那么的最优解，那么CX*=Y*b。由由 Z*= Y*b =y1*b1+y2*b2+ym*bm 可知可知 Z*/ b= Y* yi*= = Z*/ bi yi*表示资源量表示资源量bi 变化变化1 1个单位对目标函数最优值个单位对目标函数最优值Z 产生的影产生的影响，称之为响，称之为第第i 种资源的影子价格种资源的影子价格。 第三节

35、第三节 对偶问题的经济解释对偶问题的经济解释-影子价格影子价格一、影子价格一、影子价格 (Shadow Price)1.1.定义定义 影子价格是最优配置下资源的理想价格。影子价格是最优配置下资源的理想价格。2.2.含义含义 对偶问题的最优解实际上就是右端常数项的单位变化所引对偶问题的最优解实际上就是右端常数项的单位变化所引起的目标值的变化。起的目标值的变化。42 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 4422 x1 0 x5 3 x2 x1 x2 x3 x4 x5 CB XB b 2 3 0 0 0 cj-14 0 0 -3/2 -1/8 0例例7 7

36、 下面是一张下面是一张LPLP问题的最优单纯形表，其中问题的最优单纯形表，其中x3, x4, x5为为松弛变量松弛变量则对偶问题的最优解为则对偶问题的最优解为Y*=(1.5, 0.125, 0)T43例例8 8X* =(4, 2)T，Z* =14Q(4, 2)Z=14x1x24x1=164x2=12x1+2x2=844083Q(4.25, 1.875)Z=14.125Q(4, 2.5)Z=15.5Q(4, 2)Z=14 Max Z =2x1+3x2 x1+ 2x28 s.t. 4x1 16 4x2 12 x1 ,x2 0 8X1* =(4, 2.5)T，Z1*=15.5X2* =(4.25,

37、1.875)T，Z2* =14.125X3* =(4, 2)T，Z3* =1444资源的影子价格是针对具体生产或具体企业而言的：资源的影子价格是针对具体生产或具体企业而言的：1.1.同一种资源在不同的生产条件下或不同的范围内可同一种资源在不同的生产条件下或不同的范围内可能有不同的影子价格；能有不同的影子价格；A A2.2.产品的市场价格发生变化，资源的影子价格也会发产品的市场价格发生变化，资源的影子价格也会发生变化；生变化；C C3.3.资源的数量结构不同，资源的影子价格也不同。资源的数量结构不同，资源的影子价格也不同。b b I II设设 备备 1 2 8台时台时 原材料原材料A 4 0 1

38、6公斤公斤原材料原材料B 0 4 12公斤公斤2 3a21=3 (1.5, 1/6, 0)c2=4 (2, 0, 0)b1=10 (0, 0.5, 0.75)45（2 2）告诉管理者增加何种资源对企业更有利）告诉管理者增加何种资源对企业更有利(择优分配择优分配) )；cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 0 x5 3 x244 2 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0（1 1）告诉管理者花多大代价买进资源或卖出资源）告诉管理者花多大代价买进资源或卖出资源是合适的；是合适

39、的；二、影子价格的作用二、影子价格的作用 （3 3）要提高资源的影子价格，可以对生产工艺进行革要提高资源的影子价格，可以对生产工艺进行革新，以降低这种资源的单耗，从而增加企业的利润新，以降低这种资源的单耗，从而增加企业的利润。市市 影影46第四节第四节 对偶单纯形法对偶单纯形法 正则解：正则解：设设X(0)是线性规划问题是线性规划问题(Max)的一个基本解，的一个基本解，如果它的检验数如果它的检验数j0(jJ)，则称，则称X(0)是该线性规划问题是该线性规划问题的一个正则解。相应的基称为正则基。的一个正则解。相应的基称为正则基。cj CB XBb x1x2x3x4x5x6j 0 x40 x50

40、 x6-48-2-1 1 -1 1 0 0 1 1 2 0 1 0 0 -1 1 0 0 10 -1 -2 -3 0 0 0-1 -2 -3 0 0 0正则解若是可行解，则它是最优解。正则解若是可行解，则它是最优解。47第四节第四节 对偶单纯形法对偶单纯形法 从一基可行解从一基可行解( (BbBb-1-10)0)出发，在满足可行解的基础出发，在满足可行解的基础上，通过逐次基可行解的转换，直至上，通过逐次基可行解的转换，直至j j0(0(j jJ)J)成成立立（对（对maxmax问题）问题），即达到可行的正则解，从而判断，即达到可行的正则解，从而判断是否得到最优解或无最优解。是否得到最优解或无最

41、优解。 从一正则解从一正则解( (j j0(0(j jJ J)出发出发（对（对maxmax问题）问题），在，在满足正则解的基础上，通过逐次转换，直至满足正则解的基础上，通过逐次转换，直至BbBb-1-100成成立，即达到满足正则解条件的可行解，从而判断是否立，即达到满足正则解条件的可行解，从而判断是否得到最优解或无最优解。得到最优解或无最优解。单纯形法的基本思想单纯形法的基本思想：对偶单纯形法的基本思想：对偶单纯形法的基本思想：48例例9 9 用对偶单纯形法求解下列用对偶单纯形法求解下列LPLP问题问题解：原问题变形为解：原问题变形为Min Z = x1+2x2+3x3 s.t. x1 -x2

42、+ x34 x1+x2+2x38 x2 - x32 x1, x2, x30 Max Z = -x1-2x2-3x3 s.t. -x1+x2 - x3-4 x1+x2+2x38 -x2+ x3-2 x1, x2, x30 Max Z = -x1-2x2-3x3 s.t. -x1+x2 - x3+x4 =-4 x1+x2+2x3 +x5 = 8 -x2+ x3 +x6=-2 x1, x2, x3, x4, x5, x60 一、对偶单纯形法的举例一、对偶单纯形法的举例第一类对称形式第一类对称形式49cj CB XBb x1x2x3x4x5x6j 0 x40 x50 x6-48-2-1 1 -1 1

43、0 0 1 1 2 0 1 0 0 -1 1 0 0 10 -1 -2 -3 0 0 0cj-1 -2-3000 CB XBb x1x2x3x4x5x6-1 x141-11-1000 x540 211100 x6-20-11001j 4 0 -3 -2 -1 0 0-1 -2 -3 0 0 0Min-4，-2=Min -1-1-3-1,Min-2=Min -3-150*6 2 0X T T（ ， ， ）cj-1 -2-3000 CB XBb x1x2x3x4x5x6-1 x16100-10-10 x500 03112-2 x2201-100-1j 10 0 0 -5 -1 0 -3Z* = x

44、1* +2x2*+3x3*=10所以所以51二、对偶单纯形法的步骤二、对偶单纯形法的步骤(1)(1)化化LP问题的约束条件为问题的约束条件为“”形式形式, ,引入松弛变量引入松弛变量, ,建立初始表建立初始表; ;(2)(2)若所有常数项若所有常数项bi0，则最优解已经达到，否则，则最优解已经达到，否则bl=Minbi|bi0， 选取选取bl所对应的变量为出基变量；所对应的变量为出基变量；(3)(3)计算计算k=Minj /alj |alj 0，即，即cj - -j 时，原最优解改变。时，原最优解改变。五、价值系数五、价值系数 C 的变化分析的变化分析公式推导公式推导 则则xj 的检验数由的检

45、验数由j= cj -CBB-1Pj 变为变为1()jBjjcC B Pc 69例例6 6 Max Z = -2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1, x2, x3, x4, x5 0五、价值系数五、价值系数 C 的变化分析的变化分析例题例题 最优单纯形表为最优单纯形表为cj-2-3-400CBXBbx1x2x3x4x5-3 x2 2/501-1/5-2/51/5-2 x1 11/5107/5-1/5-2/5j00-9/5-8/5-1/5为使原最优解不变，求为使原最优解不变，求 c3 的变化范围。的变化范围

46、。70解：最优单纯形表为解：最优单纯形表为从表中看到从表中看到3=-9/5+c3 , ,可见可见, ,当当c3 9/5 ，即，即 c3 -49/5-11/5时，原最优解不变。时，原最优解不变。cj-2-3-400CBXBbx1x2x3x4x5-3 x2 2/501-1/5-2/51/5-2 x1 11/5107/5-1/5-2/5j00-9/5-8/5-1/5cj-2-3-4+c300CBXBbx1x2x3x4x5-3 x2 2/501-1/5-2/51/5-2 x1 11/5107/5-1/5-2/5j00-9/5+c3-8/5-1/5712.2. 基变量价值系数的改变基变量价值系数的改变五

47、、价值系数五、价值系数 C 的变化分析的变化分析公式推导公式推导 11(,)kkmjBBBBjcccccB P 1100(,)( , )kmkjBBBBjcccccB P 1kjBjBkjcC B Pc a kjBkjc a 0 00|kjjkjBkjkjkjMaxacMinaaa kBkjjc a 即即1jjBjcCB P 若基变量若基变量 的价值系数的价值系数 变为变为 则则,kkkBBBccc kBckBx11(,)TjjkjmjB Paaa 非基变量非基变量xj的检验数由的检验数由j= cj -CBB-1Pj 变为变为72例例7 7 下表为最优单纯形表下表为最优单纯形表, ,计算计算

48、c2 变化的范围，使得变化的范围，使得原最优解不变。原最优解不变。c j23000CBXBbx1x2x3x4x52 x1 41001/400 x5 400-21/213 x2 2011/2-1/80j00-3/2 -1/80五、价值系数五、价值系数 C 的变化分析的变化分析例题例题 73当当-3c21，即即 0c24 时，原最优解不变。时，原最优解不变。c j23000CBXBbx1x2x3x4x52 x1 41001/400 x5 400-21/213 x2 2011/2-1/80j00-3/2 -1/80cj23+c2000CBXBbx1x2x3x4x52 x1 41001/400 x5

49、400-21/213+c2 x2 2011/2-1/80j00-3/2 -c2/2-1/8+c2/803=0-20+0(-2)+ (3+c2)1/2=-3/2 -c2/2 04=0-21/4+01/2+(3+c2)(-1/8)=-1/8+c2/8 0741.1.增减变量增减变量(2)(2)删除变量删除变量(1)(1)增加变量增加变量若所增加变量的检验数若所增加变量的检验数00，则原最优解不变；，则原最优解不变；否则，用单纯形法迭代求最优解。否则，用单纯形法迭代求最优解。六、技术矩阵六、技术矩阵 A 的变化分析的变化分析75P66 P66 例例9 91231231323123:max235228

50、4616. .4312,0OBJZxxxxxxxxs txxx x x c j23000CBXBbx1x2x3x4x52 x1 41001/400 x5 400-21/213 x2 2011/2-1/80j00-3/2 -1/80 I II设设 备备 1 2 8台时台时 原材料原材料A 4 0 16公斤公斤原材料原材料B 0 4 12公斤公斤 263 利润利润( (元元) 2 3) 2 35 55x3B-176P66 P66 例例9 9c j23000CBXBbx1x2x3x4x52 x1 41001/400 x5 400-21/213 x2 2011/2-1/80j00-3/2 -1/805

51、x3/./.1301 4021 521 21621 21 8030 25B P 1.520.253= c3-CBB-1P3 =5-(2, 0, 3)(1.5, 2, 0.25)T=1.2501.25说明增加产品说明增加产品的生产，可以提高企业的的收益。的生产，可以提高企业的的收益。利用单纯形法进行迭代利用单纯形法进行迭代77P66 P66 例例9 9c j23000CBXBbx1x2x3x4x52 x1 1101.5-0.125-0.755x3200-10.250.53 x2 1.5010.75-0.1875-0.125j00-0.25-0.4375-0.6255x30100 最优生产计划：最优生产计划：生产产品生产产品I 1I 1件件 产品产品II 1.5II 1.5件件 产品产品III 2III 2件件总利润为：总利润为：16.516.5元。元。78jjPP2.2.Pj 的变化的变化10jjBjcC B P 10jjBjcC BP则最优解不变则最优解不变则原最优解改变则原