第二章第二章线性规划的对偶理论线性规划的对偶理论窗窗含含西西岭岭千千秋秋雪雪，门门泊泊东东吴吴万万里里船船本章主要内容本章主要内容：线性规划的对偶问题概念、理论及经济意义线性规划的对偶问题概念、理论及经济意义线性规划的对偶单纯形法线性规划的对偶单纯形法线性规划的灵敏度分析线性规划的灵敏度分析1第一节第一节 对偶问题的提出对偶问题的提出 材料材料产品产品甲甲乙乙丙丙丁丁单件单件收益收益A32112000B41324000C22343000限额限额600400300200假设工厂考虑不进行生产而把假设工厂考虑不进行生产而把全部资源都转让，问如何定价全部资源都转让，问如何定价这些资源，既能使其获利不低这些资源，既能使其获利不低于安排生产所获得的收益，又于安排生产所获得的收益，又能使资源租让具有竞争力。能使资源租让具有竞争力。一、引例一、引例MaxZ=2000x1+4000x2+3000x3s.t.3x1+4x2+2x36002x1+x2+2x3400x1+3x2+3x3300 x1+2x2+4x3200x1, x2,x30MinW=600y1+400y2+300y3+200y4s.t.3y1+2y2+y3+y420004y1+y2+3y3+2y440002y1+2y2+3y3+4y43000y1, y2,y3,y40x1x2x3y1y2y3y42二、对偶问题二、对偶问题（1 1）对称）对称LPLP问题的定义问题的定义（2 2）对称）对称LPLP问题的对偶问题问题的对偶问题第一类对称形式第一类对称形式第二类对称形式第二类对称形式3例例1 1 写出下列写出下列LPLP问题的对偶问题问题的对偶问题对偶对偶MaxZ=2x1+3x2s.t.x1+2x284x1164x212x1,x2 0MinW=8y1+16y2+12y3s.t.y1+4y222y1+4y33y1,y2,y3 04（3 3）对偶问题的对偶是原问题）对偶问题的对偶是原问题推导过程推导过程变形对偶变变形形对偶对偶对偶对偶变变形形MaxZ=CTXs.t.AXbX0MinW=bTYs.t.ATYCY0MaxW =-bTYs.t.-ATY-CY0MinZ =-CTXs.t.-(AT)TX-bX05例例2 2 写出下列写出下列LPLP问题的对偶问题问题的对偶问题解解: : 上述上述LPLP问题的问题的 对偶问题为：对偶问题为：6三、非对称三、非对称LPLP问题的对偶问题问题的对偶问题例例3 3 写出下列写出下列LPLP问题的对偶问题问题的对偶问题解：用解：用x2=-x2,x3=x3-x3代入上述代入上述LP问题，并将其问题，并将其化为第一类对称形式化为第一类对称形式MaxZ=x1+2x2+x3 x1+x2-x32s.t.x1-x2+x3=1 2x1+x2+x32x10, x20,x3无约束无约束MaxZ=x1-2x2 +x3-x3x1-x2 -x3+x3 2 x1+x2+x3 -x3 1s.t. -x1-x2 -x3+x3 -1 -2x1+x2 -x3+x3 -2 x1, x2,x3,x3 07上述第一类对称形式上述第一类对称形式LP问题的对偶问题为：问题的对偶问题为：则上述问则上述问题变为：题变为：MinW=2y1+y2 -y3-2y4y1+y2 -y3-2y41 -y1+y2 -y3+y4-2s.t.-y1+y2 -y3-y41y1-y2+y3+y4-1 y1, y2,y3,y40MinW=2u1+u2+2u3 u1+u2+2u31s.t.u1-u2+u32 -u1+u2+u3=1u10, u30,u2无约束无约束令令 u1= y1u2=y2-y3 u3=-y48(D)MinW=2u1+u2+2u3 u1+u2+2u31s.t.u1-u2+u32 -u1+u2+u3=1u10, u30,u2无约束无约束(L)MaxZ=x1+2x2+x3 x1+x2-x32s.t.x1-x2+x3=1 2x1+x2+x32x10, x20,x3无约束无约束对偶关系：对偶关系：一个问题第一个问题第i个变量的约束情况决定另一问题个变量的约束情况决定另一问题第第i个约束不等式的方向，反之亦然。个约束不等式的方向，反之亦然。正常的对正常的，不正常的对不正常的正常的对正常的，不正常的对不正常的9例例3 3 直接写出直接写出LPLP问题的对偶问题问题的对偶问题1011第二节第二节 LPLP问题的对偶理论问题的对偶理论若若X(0),Y(0)分别为分别为(L),(D)的可行解，则有的可行解，则有CTX(0)bTY(0) 定理定理1(1(弱对偶定理弱对偶定理): ): 极大化原问题目标函数值总是不极大化原问题目标函数值总是不大于其对偶问题的目标函数值。大于其对偶问题的目标函数值。证明：证明：由于由于X(0)是是(L)的可行解，有的可行解，有AX(0)b,X(0)0.由于由于Y(0)是是(D)的可行解，有的可行解，有Y(0)0. Y(0)T左乘不等式组左乘不等式组AX(0)b的两边得：的两边得：Y(0)TAX(0)Y(0)Tb.两边同时转置得两边同时转置得X(0)TATY(0)bTY(0)（1）12又又ATY(0)C,X(0)T0.所以所以 X(0)TATY(0)X(0)TC = CTX(0)(2)由（由（1），（），（2）得：得：CTX(0)bTY(0)13推论推论1 1 若若LPLP问题有无界解，则其对偶问题无可行解；问题有无界解，则其对偶问题无可行解； 若若LPLP问题无可行解，则对偶问题或有无界解或无可行解。问题无可行解，则对偶问题或有无界解或无可行解。推论推论2 2极大化问题的任何一个可行解所对应的目标极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题目标函数值的下界。函数值都是其对偶问题目标函数值的下界。极小化问题的任何一个可行解所对应的目标极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题目标函数值的上界。函数值都是其对偶问题目标函数值的上界。推论推论3 314例例4 4 考虑下面一对考虑下面一对LPLP问题问题其对偶问题为：其对偶问题为：由于由于X(0)=(1,1,1,1)T,Y(0)=(1,1)T分别为分别为(L),(D)的可行解，的可行解，故故Z40,W10.MaxZ=x1+2x2+3x3+4x4 x1+2x2+2x3+3x420s.t.2x1+x2+3x3+2x420x1,x2,x3,x4 0MinW = 20y1+20y2y1+2y21 2y1+y22 s.t. 2y1+3y233y1+2y24 y1,y2015定理定理2 2（最优性准则）（最优性准则） 当当LPLP问题目标函数值与其对偶问问题目标函数值与其对偶问题目标函数值相等时，各自的可行解即为最优解。题目标函数值相等时，各自的可行解即为最优解。若若X(0),Y(0)分别为分别为(L)，(D)的可行解的可行解, ,且且CTX(0)bTY(0)，则则X(0),Y(0)分别为分别为(L)，(D)的最优解。的最优解。证明：证明：由定理由定理1 1可知，对于可知，对于(L)的任意可行解的任意可行解X，有，有CTXbTY(0)由于由于CTX(0)=bTY(0)，故，故X(0)为为(L)的最优解。的最优解。同理同理Y(0)为为(D)的最优解。的最优解。16例例5 5MaxZ=x1+2x2+3x3+4x4 x1+2x2+2x3+3x420s.t.2x1+x2+3x3+2x420x1,x2,x3,x4 0MinW = 20y1+20y2y1+2y21 2y1+y22 s.t. 2y1+3y233y1+2y24 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)的最优解。的最优解。17定理定理3 3（强对偶定理）（强对偶定理） 若若(L)，(D)均有可行解，则均有可行解，则(L)，(D)均有最优解，均有最优解，且目标函数最优值相等。且目标函数最优值相等。证明：证明： 设设X(0),Y(0)分别为分别为(L)，(D)的可行解的可行解, ,由弱对偶定理，由弱对偶定理，对于对于(L)的任意可行解的任意可行解X，有，有CTXbTY(0)，所以，所以CTX在可在可行域内有上界，故行域内有上界，故(L)有最优解。有最优解。 同理，对于同理，对于(D)的任意可行解的任意可行解Y，有有bTYCTX(0)，所，所以以bTY在可行域内有下界，故在可行域内有下界，故(D)有最优解。有最优解。设设(L)的最优解为的最优解为X(0)，且，且X(0)所对应的最优基为所对应的最优基为B，X(0)可以表示为可以表示为X(0)= = XB(0)= = B-1b XN(0)018则则( (AT, ,ST)=( (CT, ,0T)CBTB-1(A,I)0由于由于CTCBTB-1A0，所以所以CBTB-1A CT即即AT(CBTB-1)TC (1)又又0TCBTB-1I 0，故故(CBTB-1)T0. (2). (2)令令Y(0)=(CBTB-1)T，由由(1)(2)(2)知知Y(0)是是(D)的可行解的可行解. .因为因为CTX(0)=(CBT,CNT)XB(0)=CBTXB(0)+CNTXN(0)=CBTB-1b XN(0)而而bTY(0)=bT(CBTB-1)T=CBTB-1b则则CTX(0)=bTY(0)，由最优性准则知，由最优性准则知，X(0),Y(0)分别为分别为(L)，(D)的最优解的最优解, , 且目标函数最优值相等。且目标函数最优值相等。19推论：推论： 在用单纯形法求解在用单纯形法求解LPLP问题问题(L)的最优单纯形表中，的最优单纯形表中，松弛变量的检验数的相反数就是其对偶问题松弛变量的检验数的相反数就是其对偶问题(D)的最优解。的最优解。证明：因为证明：因为sT=0T-CBTB-1I=-CBTB-1y*T=CBTB-1所以所以y*=-s例例5 5 求下列问题对偶问题的最优解求下列问题对偶问题的最优解MaxZ=2x1+3x2s.t.x1+2x284x1164x212x1,x2 0解：化为标准型解：化为标准型MaxZ=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2 ,x3,x4,x5020cj23000CB XB bx1x2x3x4x52x1 0x5 3x24421001/4000-21/21011/2-1/80-1400-3/2-1/80此时达到最优解此时达到最优解X*=(4,2)T,MaxZ=14。对偶问题的最优解为对偶问题的最优解为Y*=(3/2,1/8,0)T运用单纯形法计算得原问题的最终表如下：运用单纯形法计算得原问题的最终表如下：21定理定理4 4（互补松弛定理）（互补松弛定理）在最优情况下，原问题的第在最优情况下，原问题的第i个决策变个决策变量与其对偶问题第量与其对偶问题第i个约束中的松弛变量的乘积恒为零个约束中的松弛变量的乘积恒为零。 设设X(0),Y(0)分别为分别为(L),(D)的的可行解，则可行解，则X(0),Y(0)分别为分别为(L),(D)的最优解的充要条件为的最优解的充要条件为 , ,有有 m(1)(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)0,y2*0, ,由互补松弛性知由互补松弛性知解得解得x3*=x4*=4.所以所以(L)的最优解为的最优解为X*=(0,0,4,4)T因为因为代入代入(1),(2)得得24若若X*,Y* 分别为分别为(L),(D)的最优解，那么的最优解，那么CTX*=bTY* 。由由 Z*= bTY* =b1y1*+b2y2*+bmym* 可知可知 Z*/ bi =yi* yi*表示资源量表示资源量bi 变化变化1 1个单位对目标函数最优值个单位对目标函数最优值Z 产生的影产生的影响，称之为响，称之为第第i 种资源的影子价格种资源的影子价格。 第三节第三节 对偶问题的经济解释对偶问题的经济解释-影子价格影子价格一、影子价格一、影子价格1.1.定义定义 影子价格是最优配置下资源的理想价格。影子价格是最优配置下资源的理想价格。2.2.含义含义25 1001/4000-21/21011/2-1/804422x1 0x5 3x2 x1x2x3x4x5 CB XB b 2300 0cj-1400-3/2-1/80例例7 7 下面是一张下面是一张LPLP问题的最优单纯形表，其中问题的最优单纯形表，其中x3,x4,x5为为松弛变量松弛变量则对偶问题的最优解为则对偶问题的最优解为Y*=(1.5,0.125,0)T26例例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=14MaxZ=2x1+3x2 x1+2x28s.t.4x1164x212x1,x2 08X1* =(4,2.5)T，Z1*=15.5X2* =(4.25,1.875)T，Z2*=14.125X3* =(4,2)T，Z3*=1427（1 1）告诉管理者增加何种资源对企业更有利；）告诉管理者增加何种资源对企业更有利；cj23000CB XB bx1x2x3x4x52x1 0x5 3x24421001/4000-21/21011/2-1/80-1400-3/2-1/80（2 2）告诉管理者花多大代价买进资源或卖出资源）告诉管理者花多大代价买进资源或卖出资源是合适的；是合适的；（3 3）为新产品定价提供依据。）为新产品定价提供依据。 二、影子价格的作用二、影子价格的作用28一、对偶单纯形法的步骤一、对偶单纯形法的步骤(1)(1)化化LP问题的约束条件为问题的约束条件为“”形式形式, ,引入松弛变量引入松弛变量, ,建立初始表建立初始表; ;(2)(2)若所有常数项若所有常数项bi0，则最优解已经达到，否则，则最优解已经达到，否则bl=Minbi|bi0，选取选取bl所对应的变量为出基变量；所对应的变量为出基变量；(3)(3)计算计算k=Minj /alj|alj 0，即，即cj - -j时，原最优解改变。时，原最优解改变。五、价值系数五、价值系数 C 的变化分析的变化分析公式推导公式推导 则则xj 的检验数为的检验数为47例例6 6 MaxZ=-2x1-3x2-4x3s.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x50五、价值系数五、价值系数 C 的变化分析的变化分析例题例题 最优单纯形表为最优单纯形表为cj-2-3-400CBXBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5j00-9/5-8/5-1/5为使原最优解不变，求为使原最优解不变，求 c3的变化范围。的变化范围。48解：最优单纯形表为解：最优单纯形表为从表中看到从表中看到3=-9/5+c3 , ,可见可见, ,当当c39/5，即，即 c3-49/5-11/5时，原最优解不变。时，原最优解不变。cj-2-3-400CBXBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5j00-9/5-8/5-1/5cj-2-3-4+c300CBXBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5j00-9/5+c3-8/5-1/5492.2. 基变量价值系数的改变基变量价值系数的改变五、价值系数五、价值系数 C 的变化分析的变化分析公式推导公式推导 若基变量的价值系数若基变量的价值系数 变为变为 则则即即50例例7 7 下表为最优单纯形表下表为最优单纯形表, ,计算计算 c2变化的范围，使得变化的范围，使得原最优解不变。原最优解不变。c j23000CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80j00-3/2-1/80五、价值系数五、价值系数 C 的变化分析的变化分析例题例题 51当当-3c21，即即 0c24时，原最优解不变。时，原最优解不变。c j23000CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80j00-3/2-1/80cj23+c2000CBXBbx1x2x3x4x52x141001/400x5400-21/213+c2x22011/2-1/80j00-3/2-c2/2-1/8+c2/80521.1.增减变量增减变量(2)(2)删除变量删除变量删除非基变量最优解不变删除非基变量最优解不变删除基变量的处理方法：删除基变量的处理方法： 将将xj 的系数的系数cj 变为变为-M，迫使，迫使xj0(1)(1)增加变量增加变量若所增加变量的检验数若所增加变量的检验数00，则原最优解不变；，则原最优解不变；否则，用单纯形法迭代求最优解。否则，用单纯形法迭代求最优解。六、技术矩阵六、技术矩阵 A 的变化分析的变化分析532.2.Pj 的变化的变化则最优解不变则最优解不变则原最优解改变则原最优解改变六、技术矩阵六、技术矩阵 A 的变化分析的变化分析543.3.增减约束条件增减约束条件(1)(1)删除约束条件删除约束条件当当n+1 1 0 0, ,n+2+2 0 0时最优解不变时最优解不变; ;否则否则, ,运用单纯形法运用单纯形法迭代求最优解。迭代求最优解。六、技术矩阵六、技术矩阵 A 的变化分析的变化分析55(2)(2)增加约束条件增加约束条件六、技术矩阵六、技术矩阵 A 的变化分析的变化分析化约束条件为化约束条件为的形式，引入松弛变量的形式，引入松弛变量xn+1；把增加的约束条件直接写入最优表把增加的约束条件直接写入最优表( (以松弛变量以松弛变量xn+1为基为基变量变量) )，得到一个非标准表；，得到一个非标准表；化非标准表为标准表，若化非标准表为标准表，若b n+1 ，则最优解仍为最优，则最优解仍为最优解，解，若若bn+1，则用对偶单纯形法迭代找出最优解。，则用对偶单纯形法迭代找出最优解。56cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-11j-800-3-3-1例例8 8 已知某已知某LPLP问题的最优单纯形表如下：问题的最优单纯形表如下：如果增加约束条件如果增加约束条件x1+x32，最优解将如何变化？最优解将如何变化？六、技术矩阵六、技术矩阵 A 的变化分析的变化分析57cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-110-800-3-3-10CBXBbx1x2x3x4x5x62x1110-13-103x22012-1100x6-100-23-11-800-3-3-10 x6-2-10-1000x6001非标准表非标准表标准表标准表 x1+x32-x1-x3+x6=-2 58cj231000CBXBbx1x2x3x4x5x62x1210100-13x210102010x51002-31-1-700-1-60-159cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-11-800-3-3-1课堂练习课堂练习 下面是某下面是某LPLP问题的最优单纯形表，当增加约束条问题的最优单纯形表，当增加约束条件件 x1+x24时时，最优解如何变化？，最优解如何变化？60cj231000CBXBbx1x2x3x4x5x62x1110-13-103x22012-1100x64110001-800-3-3-10cj231000CBXBbx1x2x3x4x5x62x1110-13-103x22011-1100x6100-1-201-8000-3-10原最优解不变原最优解不变61