对偶理论与灵敏度分析

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 y

3、1, y2, y3, y40 x1x2x3y1 y2 y3 y43比较上述模型，可以得出两者之间的一些关系：比较上述模型，可以得出两者之间的一些关系： 1. 两个问题，一个是极大化，另一个是极小化；两个问题，一个是极大化，另一个是极小化； 2. 一个问题的一个问题的变量变量数等于另一问题的数等于另一问题的方程方程数，反数，反之亦然；之亦然； 3. 一个问题的一个问题的目标目标函数系数是另一个问题的约束函数系数是另一个问题的约束方程方程右端右端常数，反之亦然；常数，反之亦然； 4. 两个问题的约束方程系数矩阵互为转置。两个问题的约束方程系数矩阵互为转置。称称变量变量yi为第为第 一个一个LP的第

4、的第i个对偶变量，个对偶变量，或第或第一个一个LP的第的第i个约束相应的对偶变量个约束相应的对偶变量4 对偶问题的提出有其理论依据，可由对偶问题的提出有其理论依据，可由“单纯单纯形法的矩阵描述形法的矩阵描述”加以解释。加以解释。 TTTBNBBBTBSBNNBSBNNBBBCYAAYCABCCXXYBCBCYBCNBCCBCXNBCCXBBCCXXbAXCXZ 002001LP00:0:0max11111111的的检检验验数数可可统统一一写写成成：、约约束束条条件件）（，由由令令决决策策变变量量）（问问题题如如下下：新新时时，得得最最优优解解。当当，其其检检验验数数可可表表示示为为：，对对于于

5、 5为原问题的对偶问题。为原问题的对偶问题。，问题问题而后出现的而后出现的为原问题，为原问题，问题问题称首先出现的称首先出现的问题可写成：问题可写成：新的新的故故义义目标函数取最小才有意目标函数取最小才有意的上界为无限大的上界为无限大则则由由目标函数目标函数）（0minLP0maxLP0.minLP,)(311 YCYAYbWXbAXCXZYCYAtsYbWYCYAZbBCbYYbYbBCYTTTTTTTTBTTTTBT6二、对偶问题二、对偶问题1. 对称形式的定义对称形式的定义必须满足下列条件：必须满足下列条件： （1）变量为非负；）变量为非负； （2）约束条件为不等式。）约束条件为不等式。

6、 对于对于max ，约束为，约束为“ ” ； 对于对于min，约束为，约束为“ ” 原问题原问题 (Primal Problem)PP： max Z=CX s.t. AXb X0对偶问题对偶问题 (Dual Problem)DP： min W=bTY s.t. ATYCT Y07), 2 , 1(0), 2 , 1(. .max11njxmibxatsxcZjnjijijnjjj ), 2 , 1(0), 2 , 1(.min11miynjcyatsybWimijiijmiii 2. 对称对称LPLP问题的对偶问题问题的对偶问题)(PP 0.maxXbAXtsCXZ)(DP 0.minYCYA

7、tsYbWTTT8例例1 1 写出下列写出下列LPLP问题的对偶问题问题的对偶问题对偶对偶 Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1 ,x2 0 Min W =8y1+16y2+12y3 s.t. y1+4y2 2 2y1 +4y3 3 y1 ,y2,y3 09 0.minYCYAtsYbWTTT推导过程推导过程变形 0.maxXbAXtsCXZ)(PP对偶)(DP 0.maxYCYAtsYbWTTT3. 求求对偶问题的对偶对偶问题的对偶10对偶)(DP 0)(.)(minXbXAtsXCZTTTT 0.maxXbAXtsCXZ变形 0.max

8、YCYAtsYbWTTT结论结论：对偶问题的对偶是原问题。：对偶问题的对偶是原问题。111212312312312334334748:1,0MinWxxxxxxxxSTxxxxxx 1231231231231237834334: 40,0MaxZyyyyyyyyySTyyyyyy 例例2 2 写出下列写出下列LPLP问题的对偶问题问题的对偶问题解解: : 上述上述LPLP问题的问题的 对偶问题为：对偶问题为：12三、非对称三、非对称LPLP问题的对偶问题问题的对偶问题例例3 3 写出下列写出下列LPLP问题的对偶问题问题的对偶问题解：用解：用x2= -x2, x3=x3-x3代入上述代入上述L

9、P问题，并将其问题，并将其化为第一类对称形式化为第一类对称形式Max Z = x1+2x2+x3 x1+x2-x3 2 s.t. x1 -x2+x3 = 1 2x1+x2+x3 2 x10, x20 ,x3无约束无约束 Max Z = x12x2 +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-x2-x3 -213上述第一类对称形式上述第一类对称形式LP问题的对偶问题为：

10、问题的对偶问题为：则上述问则上述问题变为：题变为：Min W =2y1+y2 y32y4 y1+y2 y32y4 1 y1+y2 y3 +y4 -2 s.t. y1+y2 y3y4 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=y2y3 u3=y4Max Z = x12x2 +x3 x3 x1 x2 x3+x3 2 x1+x2+x3 x3 1s.t. x1 x2 x3+x3 1 2x1+x

11、2 x3+x3 2 x1, x2, x3, x3 0 -y1+y2 -y3 -y4 1y1-y2+y3 -y4 214(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无约束无约束 对偶关系：对偶关系：一个问题第一个问题第i个变量的约束情况决定另一问题个变量的约束情况决定另一问题第第i个约束不等式的方向，反之亦然。个约束不等式的方

12、向，反之亦然。正常的对正常的，不正常的对不正常的正常的对正常的，不正常的对不正常的 原问题约束条件是等式对应于对偶问题决策变量无原问题约束条件是等式对应于对偶问题决策变量无约束，反之亦然约束，反之亦然15例例3 3 直接写出直接写出LPLP问题的对偶问题问题的对偶问题1231231231231232 2 1:2 20,0,MaxZxxxxxxxxxSTxxxxxx 无无约束束12322MinWuuu123uuu1232uuu123uuu12 10u ，1:ST 2u无无约束束，30u 16 12312312312312322212:10,0MinWuuuuuuuuuSTuuuuuu 无无约束束

13、1232MaxZxxx:ST 123xxx123xxx1232xxx21210 x 20 x 3x 无无约束束 17原问题原问题对偶问题对偶问题目标函数目标函数Max zMin w变量变量n个约束条件约束条件n个=00无约束约束条件约束条件m个=变量变量m个00无约束约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项原问题原问题对偶问题对偶问题18第二节第二节 LPLP问题的对偶理论问题的对偶理论若若X(0),Y(0)分别为分别为(L),(D)的可行解，则有的可行解，则有CX(0)Y(0)b 定理定理1(1(弱对偶定

14、理弱对偶定理):):在双方都是可行解的情况下，极大化问在双方都是可行解的情况下，极大化问题的目标函数值总不大于其对偶问题目标函数值。题的目标函数值总不大于其对偶问题目标函数值。证明：证明：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)19 min w=Yb;YAC;Y0(D)又又Y(0)AC用用X(0)(X(0)0)右乘上式，

15、得右乘上式，得Y(0)AX(0) CX(0) (2)由（由（1），（），（2）得：得：CX(0)Y(0)AX(0)Y(0)b所以所以 CX(0)Y(0)b20推论推论1 1 若对偶问题有无界解，则其原问题无可行解；若对偶问题有无界解，则其原问题无可行解； 若对偶问题无可行解，则其原问题或有无界解或无可行解。若对偶问题无可行解，则其原问题或有无界解或无可行解。 若若LPLP问题有无界解，则其对偶问题无可行解问题有无界解，则其对偶问题无可行解( (弱对偶性弱对偶性) )； 若若LPLP问题无可行解，则对偶问题或有无界解或无可行解。问题无可行解，则对偶问题或有无界解或无可行解。21x2x111-1-

16、1y2y111-1-1原问题原问题对偶问题对偶问题12121212min11,0zxxxxxxx x 12121212max11,0wyyyyyyy y 22推论推论2 2极大化问题（极大化问题（L）的任何一个可行解所对应的目标函）的任何一个可行解所对应的目标函数值都是其对偶问题数值都是其对偶问题（D）目标函数值的下界。目标函数值的下界。极小化问题（极小化问题（D）的任何一个可行解所对应的目标）的任何一个可行解所对应的目标函数值都是其对偶问题函数值都是其对偶问题（L）目标函数值的上界。目标函数值的上界。推论推论3 3YbCX(0)CX Y(0)bmax z=CX; AXb; X0(L) min

17、 w=Yb; YAC; Y0(D)23例例4 4 考虑下面一对考虑下面一对LPLP问题问题其对偶问题为：其对偶问题为：由于由于X(0) =(1,1,1,1)T,Y(0)=(1,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故故1010Z，

18、W4024 P59（书（书 例例4 4）12123123123max221,0zxxxxxxxxxxx 试用对偶理论证明上述线性规划问题无最优解试用对偶理论证明上述线性规划问题无最优解 证明：首先看到该问题存在可行解，如证明：首先看到该问题存在可行解，如X=(0,0,0)上述问题的对偶问题为上述问题的对偶问题为1212121212min22110,0 wyyyyyyyyyy 由第一约束条件知对偶问题无可行解，因原问题有可行解，由第一约束条件知对偶问题无可行解，因原问题有可行解，由推论由推论1，原问题无最优解。，原问题无最优解。若对偶问题无可行解，则若对偶问题无可行解，则其原问题或有无界解或无其

19、原问题或有无界解或无可行解。可行解。25定理定理2 2（最优性准则）（最优性准则） 当当LPLP问题目标函数值与其对偶问题问题目标函数值与其对偶问题目标函数值相等时，各自的可行解即为最优解。目标函数值相等时，各自的可行解即为最优解。(P57)(P57)若若X(0),Y(0)分别为分别为(L)，(D)的可行解的可行解, ,且且CX(0)Y(0)b,则则X(0),Y(0)分别为分别为(L)，(D)的最优解。的最优解。证明：证明：由定理由定理1 1可知，对于可知，对于(L)的任意可行解的任意可行解X，有，有CX Y(0)b 由于由于CX(0) =Y(0)b，CX CX(0) ，故故X(0)为为 (L

20、) 的最优解；的最优解；同理，同理，由定理由定理1 1可知，可知，对于对于(D)的任意可行解的任意可行解Y，有，有YbCX(0)，由于由于CX(0) =Y(0)b，YbY(0)b，Y(0)为为(D)的最优的最优解。解。26例例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 y1+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/

21、5,1/5)T是是(L)，(D)的的可行解且可行解且 CX(0)=bTY(0)=28，所以，所以X(0),Y(0)分别为分别为(L)，(D)的最优解。的最优解。27课堂作业课堂作业。应应用用对对偶偶理理论论证证明明不不限限如如下下：已已知知10,02212.2maxLP*321321321321321 ZxxxxxxxxxxxxtsxxxZ28CCBXBbXBXNXS-Z0XSbCBCN0BCNNIcB00CCBXBbXBXNXS-ZCBXBB-1bCBCN0ICN-CBB-1NB-1NB-10-CBB-1-CBB-1b29定理定理3 3（强对偶定理）（强对偶定理） 若若(L)，(D)均有可行

22、解，则均有可行解，则(L)，(D)均有最优解，均有最优解，且目标函数最优值相等。且目标函数最优值相等。证明：证明： 设设X(0),Y(0)分别为分别为(L)，(D)的可行解的可行解, ,由弱对偶定理由弱对偶定理( (推论推论3)3)，对于，对于(L)的任意可行解的任意可行解X，有，有CX Y(0)b，所以，所以CX在可行域内有上界，故在可行域内有上界，故(L)有最优解。有最优解。 同理，对于同理，对于(D)的任意可行解的任意可行解Y，由弱对偶定理由弱对偶定理（推（推论论2 2），有有Y bCX(0)，所以，所以Yb在可行域内有下界，故在可行域内有下界，故(D)有最优解。有最优解。设设(L)的的

23、基最优解基最优解为为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. (2). (2)令令Y(0)=CBB-1，由由(1)、(2)(2)知知Y(0)是是(D)的可行解的可行解. .因为因为CX(0)=(

24、CB, CN) XB(0) =CBXB(0)+CNXN(0) = CBB-1b XN(0)而而Y(0)b = CBB-1b 则则CX(0)=Y(0)b ，由最优性准则知，由最优性准则知， X(0),Y(0)分别为分别为(L)，(D)的最优解的最优解, , 且目标函数最优值相等。且目标函数最优值相等。31课堂作业课堂作业都都存存在在最最优优解解。和和应应用用对对偶偶理理论论证证明明，如如下下：已已知知DPPP03142342.23maxLP2121212121 xxxxxxxxtsxxZ32推论：推论： 在用单纯形法求解在用单纯形法求解LPLP问题问题(L)的最优单纯形表中，的最优单纯形表中，松

25、弛变量的检验数的相反数就是其对偶问题松弛变量的检验数的相反数就是其对偶问题(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-1b

26、33 X(0) (0,0,8,16,12)T以以1为主元素进行旋转运算，为主元素进行旋转运算，x1为换入变量，为换入变量， x3为换出变量为换出变量 0 q qi 3 0 0 x5 x2 x3 x40 x4 x3XB b j 0 x1CB 2 cj x1 cj x2 x3 x4 x5 1 4 0 2 0 4 1 0 0 0 1 0 0 0 1 2 3 0 0 0 b816 12 XB x3 x4 x5 CB 0 0 0以以4为主元素进行旋转运算，为主元素进行旋转运算，x2为换入变量，为换入变量，x5为换出变量为换出变量 j 2 3 0 0 0 q qi 8/2 12/44 x2 3 0 0 0

27、 1/43 1 4 0 1 016 0 0 1 1 0 -1/22X(1) (0,3,2,16,0)T 2 0 0 -3/4 016/4 2/1 1Y(0) (0,0,0,-2,-3)TY(1) (0,0,3/4,-2,0)T34此时达到最优解。此时达到最优解。X*=(4,2), max Z=14。 0 q qi 3 0 0 x5 x2 x3 x40 x4 x23 XB b j x1CB 2 cj 0 q qi 3 0 0 x5 x2 x3 x4x23 x1XB b j 2 x1CB 2 cj 0 0 0 1/43 10 -2 0 1/4 0 x1 2 0 1 1 0 -1/22 2 0-4

28、128 08/2 12 x50 0 -2 1/2 14 0 1 0 1/4 04 0 1/2 -1/8 0 02 10 -3/2 -1/8 0 0X(3) (4,2,0,0,4)TX(2) (2,3,0,8,0)T以以2为主元素进行旋转运算，为主元素进行旋转运算，x5为为换入变量，换入变量，x4为换出变量为换出变量Y(2) (2,0,-1/4,0,0)TY(3) (3/2,1/8,0,0,0)T35重要提示：重要提示： 由上述实例可以看出：在用单纯形法求解由上述实例可以看出：在用单纯形法求解LPLP问问题时，题时，PPPP没有得到最优解之前，每迭代一步得到一没有得到最优解之前，每迭代一步得到一

29、个基可行解，此时个基可行解，此时DPDP得到的是一个基解；而当得到的是一个基解；而当PPPP得得到最优解时，到最优解时，DPDP才得到一个基可行解。根据才得到一个基可行解。根据强对偶强对偶定理定理，DPDP得到的这个基可行解一定是得到的这个基可行解一定是DPDP的最优解。的最优解。36 推论：对偶问题的最优解对应于原问题的最优推论：对偶问题的最优解对应于原问题的最优单纯型表中松弛变量检验数的相反数或剩余变单纯型表中松弛变量检验数的相反数或剩余变量的检验数。量的检验数。37Min z=2x1+3x2 x1+x2 350 x1 1252x1+x2 600 x1, x2 0Max w=350y1+1

30、25y2+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*=800例例38定理定理4 4：互补松驰定理：互补松驰定理条条件件是是的的最最优优解解充充要要、分分别别为为、则则问问题题的的可可行行解

31、解、分分别别为为、设设）（）（）（）（DPPPDPPP0000YXYX miliillCyax1)0()0(, 0 则则若若) 1 ()2(0,)0(1)0( lmiliilxCya则则若若)3( njkjkjkbxay1)0()0(, 0 则则若若)4(0,)0(1)0( knjkjkjybxa则则若若有有),1,1(,nlmklk 0PP)2)(1(* XYYSS之间的关系。即之间的关系。即方程中的方程中的变量与相应的对偶变量与相应的对偶为为0PP)4)(3(* SSXYX。即。即的对偶变量之间的关系的对偶变量之间的关系与相应与相应方程中的方程中的为为39( )L例例7 7 考虑下面问题考

32、虑下面问题Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3+2x4 20 x1,x2,x3,x4 0()D Min W = 20y1+20y2 y1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y20已知已知(D)的的最优解为最优解为 Y*=(6/5,1/5)T 用互补松弛定理用互补松弛定理求出求出(L)的最优解。的最优解。40*123422320(1)xxxx *123423220(2)xxxx *.1221 20 41 61yy *.1222 40 22 62yy *342320

33、 xx *343220 xx x1*=x2*=0. 解：由于解：由于y1* 0, y2* 0, ,由互补松弛性知由互补松弛性知解得解得x3*= x4*=4. 所以所以(L)的最优解为的最优解为X*=(0,0,4,4)T因为因为代入代入(1),(2)得得由互补松弛性知，由互补松弛性知，41第三节第三节 对偶问题的经济解释对偶问题的经济解释-影子价格影子价格*YbWCXZT 由由于于是是变变化化的的，则则假假设设mbbb,211、 y*i的数学含义的数学含义mmbZybZybZy *2*21*1,的的变变化化量量。问问题题的的最最优优目目标标函函数数值值单单位位时时，变变化化可可以以理理解解成成当

34、当资资源源PP1*iyi*22*11*mmybybybZ 所所以以428例最最优优单单纯纯形形表表问问题题的的右右面面是是该该 LPTY)0 ,125. 0 , 5 . 1(* 则则对对偶偶问问题题的的最最优优解解为为 0 q qi 3 0 0 x5 x2 x3 x40 x5x23 x1XB b j 2 x1CB 2 cj 0 -2 1/2 14 0 1 0 1/4 04 0 1/2 -1/8 0 02 10 -3/2 -1/8 0 0 0,12416482. .32max21212121xxxxxxtsxxZ 5 , 4 , 3 , 2 , 1, 01241648232max35224113

35、2121jxyxxyxxyxxxxxZj对对偶偶变变量量标准化标准化43X* =(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=148X1* =(4, 2.5)T，Z1*=15.5X2* =(4.25, 1.875)T，Z2* =14.125X3* =(4, 2)T，Z3* =140,125.0,5 .1*3*2*1 yyy则则没没有有变变化化。个个单单位位，则则变变化化；变变化化个个单单位位，则则变变化化；变变化化个个单单位位，则则变变化化表

36、表明明：根根据据影影子子价价格格的的含含义义，*3*2*11125.015 .11ZbZbZb44 (1)对偶问题的最优解对偶问题的最优解买主的最低出价。买主的最低出价。 (2)原问题资源的影子价格原问题资源的影子价格当该资源增加当该资源增加1单位时引起单位时引起的总收入的增量的总收入的增量卖主的内控价格。卖主的内控价格。 (3)代表在资源最优利用条件下对单位第代表在资源最优利用条件下对单位第i种资源的估价，种资源的估价，这种估价不是资源的市场价格，而是根据资源在最优生产配置这种估价不是资源的市场价格，而是根据资源在最优生产配置中作出的贡献而作的估价，为区别起见，称为影子价格中作出的贡献而作的

37、估价，为区别起见，称为影子价格（shadow price)。 资源影子价格资源影子价格资源市场价格资源市场价格 资源的市场价格是已知数，相对比较稳定，而它的影子价资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。产品结构等情况发生变化，资源的影子价格也随之改变。即：市场价格由市场确定；影子价格由生产企业确定。即：市场价格由市场确定；影子价格由生产企业确定。2、 y*i的经济学含义的经济学含义45(4)资源的影子价格实际上又是一种机会成本。

38、资源的影子价格实际上又是一种机会成本。 在完全市场经济条件下在完全市场经济条件下,当：当： 资源的市场价格资源的市场价格影子价格，应卖出这种资源影子价格，应卖出这种资源 随着资源的买进卖出，它的影子价格也将随之发生变化，随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。一直到影子价格与市场价格保持同等水平时，才处于平衡状态。46资源的影子价格是针对具体生产或具体企业而言的：资源的影子价格是针对具体生产或具体企业而言的：1.1.同一种资源在不同的生产条件下或不同的范围内可同一种资源在不同的生产条件下或不同的范围内可能有不同的影子价格；能有不

39、同的影子价格；A A2.2.产品的市场价格发生变化，资源的影子价格也会发产品的市场价格发生变化，资源的影子价格也会发生变化；生变化；C C3.3.资源的数量结构不同，资源的影子价格也不同。资源的数量结构不同，资源的影子价格也不同。b b I II设设 备备 1 2 8台时台时 原材料原材料A 4 0 16公斤公斤原材料原材料B 0 4 12公斤公斤2 3a21=3 (1.5, 1/6, 0)c2=4 (2, 0, 0)b1=10 (0, 0.5, 0.75)47（1 1）告诉管理者增加何种资源对企业更有利；）告诉管理者增加何种资源对企业更有利；cj 2 3 0 0 0 CB XB b x1 x

40、2 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（2 2）告诉管理者花多大代价买进资源或卖出资源是合适的）告诉管理者花多大代价买进资源或卖出资源是合适的（3 3）为新产品定价提供依据。）为新产品定价提供依据。 二、影子价格的作用二、影子价格的作用48第四节第四节 对偶单纯形法对偶单纯形法 正则解：正则解：设设X(0)是线性规划问题是线性规划问题(Max)的一个的一个基解基解，如，如果它的检验数果它的检验数j0(jJ)，则称，则称X(0)是该线性规划问题的是该线性规划

41、问题的一个正则解。相应的基称为正则基。一个正则解。相应的基称为正则基。cj CB XBb x1x2x3x4x5x6j 0 x40 x50 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正则解若是可行解，则它是最优解。正则解若是可行解，则它是最优解。49第四节第四节 对偶单纯形法对偶单纯形法 从一基可行解从一基可行解( (BbBb-1-10)0)出发，在满足可行解的基础出发，在满足可行解的基础上，通过逐次基可行解的转换，直至上，通过逐次基可行解的转换，直至j j0(0(j jJ)J)成成立立（

42、对（对maxmax问题）问题），即达到可行的正则解，从而判断，即达到可行的正则解，从而判断是否得到最优解或无最优解。是否得到最优解或无最优解。 从一正则解从一正则解( (j j0(0(j jJ J)出发出发（对（对maxmax问题）问题），在满，在满足正则解的基础上，通过逐次转换，直至足正则解的基础上，通过逐次转换，直至BbBb-1-100成立，成立，即达到满足正则解条件的可行解，从而判断是否得到最即达到满足正则解条件的可行解，从而判断是否得到最优解或无最优解。优解或无最优解。单纯形法的基本思想单纯形法的基本思想：对偶单纯形法的基本思想：对偶单纯形法的基本思想：50例例9 9 用对偶单纯形法求

43、解下列用对偶单纯形法求解下列LPLP问题问题解：原问题变形为解：原问题变形为Min Z = x1+2x2+3x3 s.t. x1 -x2+ 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 一、对偶单纯形法的举例一、对偶单纯形法的举

44、例第一类对称形式第一类对称形式51cj CB XBb x1x2x3x4x5x6j 0 x40 x50 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 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-152*6 2 0X T T（ ， ， ）cj-1 -2-3000 CB XBb x1x2x3x4x

45、5x6-1 x16100-10-10 x500 03112-2 x2201-100-1j 10 0 0 -5 -1 0 -3Z* = x1* +2x2*+3x3*=10所以所以注意：注意：对偶单纯形法不可理解成是求解对偶问题的单对偶单纯形法不可理解成是求解对偶问题的单纯形法，而是根据对偶理论，允许原问题从初始非可纯形法，而是根据对偶理论，允许原问题从初始非可行基开始迭代求解原问题的单纯形法。行基开始迭代求解原问题的单纯形法。 53二、对偶单纯形法的步骤二、对偶单纯形法的步骤 (以最大化为例以最大化为例):为为换换出出变变量量；所所对对应应的的基基变变量量选选取取否否则则，令令停停止止计计算算；

46、，则则最最优优解解已已经经达达到到，所所有有常常数数项项若若所所有有法法求求解解；，则则不不能能用用对对偶偶单单纯纯形形若若存存在在）（liiilijjbbbbb,0|min0002 ;DPPP0,0|min)3(为为无无界界解解无无可可行行解解，为为换换入入变变量量；若若所所有有所所对对应应的的非非基基变变量量选选取取计计算算 ljkljljjjkaaaq q q q转转第第二二步步算算作作为为主主元元素素进进行行旋旋转转运运以以,)4(lka建建立立初初始始表表；，形形式式，且且引引入入松松弛弛变变量量问问题题的的约约束束条条件件为为化化 LP)1(54建初始表建初始表是否最优？是否最优？

47、 结束结束选出换出和换入选出换出和换入变量进行运算变量进行运算YN55三、几个问题的讨论三、几个问题的讨论1.1.对偶单纯形法适用于具有正则解的对偶单纯形法适用于具有正则解的LPLP问题。问题。 正则解所对应的对偶问题的解是对偶问题的基可行解正则解所对应的对偶问题的解是对偶问题的基可行解2.2.对偶单纯形法所包含的创新思想：原问题的初始可行解对偶单纯形法所包含的创新思想：原问题的初始可行解不一定要是基可行解，可以从非基可行解开始迭代。不一定要是基可行解，可以从非基可行解开始迭代。3.3.当变量多于约束条件时，对这样的线性规划问题用对偶当变量多于约束条件时，对这样的线性规划问题用对偶单纯形法计算

48、可以减少工作量。单纯形法计算可以减少工作量。4.4.在灵敏度分析时，有时需要用对偶单纯形法。在灵敏度分析时，有时需要用对偶单纯形法。56单纯形法单纯形法原问题原问题对偶问题对偶问题基可行解基可行解非可行解非可行解基可行解基可行解基可行解基可行解对偶单纯对偶单纯形法形法原问题原问题对偶问题对偶问题非可行解非可行解基可行解基可行解基可行解基可行解基可行解基可行解57第五节第五节 灵敏度分析灵敏度分析 模型中的参数模型中的参数AbC一般是预测估计的确定值，而一般是预测估计的确定值，而在计划实施时，这些值一般不可能正好是事先估计的在计划实施时，这些值一般不可能正好是事先估计的值，因此有必要在求解后，分

49、析这些参数值在将来可值，因此有必要在求解后，分析这些参数值在将来可能变化后对最优性的影响。能变化后对最优性的影响。灵敏度分析就是计算为保灵敏度分析就是计算为保持原最优性质不变，模型中某一个参数（持原最优性质不变，模型中某一个参数（Cj或或bi或或aij）单独变化的允许范围。单独变化的允许范围。 问问题题当当LP 0:maxXbAXSTCXZ一、定义一、定义58011 jBjjPBCC 、021* bBXB、二、灵敏度分析常用的两个公式二、灵敏度分析常用的两个公式最优性条件：最优性条件： 1.1.可行条件：可行条件：XB 02.2.最优条件：最优条件： j0（maxmax） 灵敏度分析就是求出在

50、上述两个最优条件仍成立的灵敏度分析就是求出在上述两个最优条件仍成立的情况下，参数情况下，参数bicjaij的变化范围。这需要将上述两的变化范围。这需要将上述两式写成含有参数的表达式。式写成含有参数的表达式。 59改改变变、最最优优基基不不变变，最最优优解解2、最最优优解解不不变变1、最最优优基基改改变变3三、灵敏度分析的几种结果三、灵敏度分析的几种结果可行条件：可行条件：XB =B-1b0。当当bi发生变化时，只影响可行性。发生变化时，只影响可行性。用用XB =B-1b0 求出求出bi的变化量，此时的变化量，此时最优基不变最优基不变（XB中中的基变量名称没有变，但数值一般会改变）。的基变量名称

51、没有变，但数值一般会改变）。 最优条件：最优条件： j0。当当cj发生变化时，只影响最优性，用发生变化时，只影响最优性，用 j0( j=cj-ciaij=cj-CBPj )求出求出cj的变化量，此时只是的变化量，此时只是Z值值会改变，而会改变，而最优解不变最优解不变（最优基和基变量值均不变）。（最优基和基变量值均不变）。60直接用单纯形表求直接用单纯形表求B-1四、右端项四、右端项 b 的变化分析的变化分析求求B-1由由AXb AX+IXS=b （初始表）初始表）两边左乘两边左乘B-1得得B-1AX+ B-1XS= B-1b （最优表）最优表）例例1 1 LP LP问题问题 Max Z =2x

52、1+3x2 x1+ 2x28 s.t. 4x1 16 4x2 12 x1 ,x2 0 的初始单纯形表和最优单纯形表如下的初始单纯形表和最优单纯形表如下61最优表：最优表：四、右端项四、右端项 b 的变化分析的变化分析求求B-1cj23000CBXBbx1x2x3x4x50 x38121000 x416400100 x51204001j 23000CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80j-1400-3/2-1/80初始表：初始表： 最优基最优基 的逆的逆B-11 0 2 -14 0 00 1 4B-1b=1 0 2 -1 8 4

53、4 0 0 16 = 40 1 4 12 2B-1A=1 0 2 -1 1 2 1 04 0 0 4 0 = 0 00 1 4 0 4 0 1 B-1I=B-162 cj4517000CBXBbx1x2x3x4x5x6x70 x512084611000 x63013220100 x715038520014517000例例2 2 下面是求解同一下面是求解同一LPLP问题的初始单纯形表和最优单纯形表，问题的初始单纯形表和最优单纯形表，求求b b1 1, ,b b2 2, ,b b3 3的变化范围的变化范围( (假设只有一个变化假设只有一个变化) )，使原最优基不变。，使原最优基不变。初始表初始表

54、cj4517000CBXBbx1x2x3x4x5x6x74x11411/32/302/15-1/1507x4804/32/31-1/158/1500 x792013/35/30-4/15-13/1510-17/3-19/30-1/15-52/150最优表最优表四、右端项四、右端项 b 的变化分析的变化分析例题例题 63解：解：b1105120 B12101515180151541311515BbbBbBb 111()对对b1，有，有bbb11121 401 51801 549 201 5 b 121015151418800151592413101515 064解：解：213801513b B1

55、2101515180151541311515BbbBbBb 111()对对b2，有，有22211 401 58801 51 39 201 5bbb 221001515141880151592413101515b 065解：解：392b B12101515180151541311515BbbBbBb 111()对对b3，有，有3321 4008001 39 201 5bbb 221001515141880015159241311515b 066cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-11 -800-3-3-1例例3 3 下面是某下面是某LPLP问题的单纯

56、形表，问题的单纯形表，x4, x5为松弛变量。为松弛变量。（1 1）求）求的取值范围，使得原最优基仍为最优基；的取值范围，使得原最优基仍为最优基；（2 2）求）求为何值时，使得原最优基不变而目标函数值最大。为何值时，使得原最优基不变而目标函数值最大。假设原来的假设原来的b被被 b + + b 代替，其中代替，其中 b= 1 -1四、右端项四、右端项 b 的变化分析的变化分析例题例题 B-1-CBB-167解解: (1) : (1) B-1= 3 -1 -1 1所以所以 -1/41。XB* = B-1 ( b + + b ) = B-1b + +B-1 - - = 1 + 3 -1 2 -1 1

57、 - - = 1+4 00 2 -2*( ) *()()( , )111283 182BBBZC BbbC B bC Bb 当当1时，时，Z*=10，达到最大。达到最大。68 0,12416482. .32max:21212121xxxxxxtsxxZOBJ解：解：（1 1）设设I、II两种产两种产品的产量分别为品的产量分别为x1, x2。建建立该问题的数学模型为立该问题的数学模型为: :例例4 4 I II设设 备备 1 2 8台时台时 原材料原材料A 4 0 16公斤公斤原材料原材料B 0 4 12公斤公斤工厂每生产一件产品工厂每生产一件产品I可获利可获利2 2元，每生产一件产品元，每生产

58、一件产品II可获利可获利3 3元。元。（1 1）应如何安排生产使该厂获利最多？）应如何安排生产使该厂获利最多？（2 2）工厂新增）工厂新增2424公斤原材料公斤原材料A A，问如何安排新的生产计划以使获，问如何安排新的生产计划以使获利最多？利最多？四、右端项四、右端项 b 的变化分析的变化分析例题例题69cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 0 x5 3 x2 4 4 2 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 j -14 0 0 -3/2 -1/8 0用单纯形法求得最优单纯形表如下：用单纯形法求得最优单纯形表

59、如下：最优生产计划为：生产最优生产计划为：生产4件产品件产品I，2件产品件产品II；最大利润为；最大利润为14。B-170（2）工厂新增工厂新增2424公斤原材料公斤原材料A A，则，则/101 4081021 2140161 21 80121B b cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 0 x5 3 x2 10 16 -1 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 j -17 0 0 -3/2 -1/8 0新的最优生产计划为：生产新的最优生产计划为：生产8件产品件产品I，0件产品件产品II；最大利润为；最大利润

60、为16。将其代入原最优表，并利用对偶单纯形法迭代：将其代入原最优表，并利用对偶单纯形法迭代：2 x1 0 x5 0 x48128 1 2 1 0 0 0 4 0 0 1 0 -8 -4 1 0j-16 0 -1 -2 0 0(-8)x4 0,12440482. .32max:21212121xxxxxxtsxxZOBJ71cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-11 00-3-3-1例例5 5 下面是一张下面是一张LPLP问题的最优单纯形表问题的最优单纯形表, ,观察其目标函数观察其目标函数系数的改变对检验数的影响系数的改变对检验数的影响五、价值系数五