运筹学对偶理论和灵敏度分析幻灯片.ppt
运筹学运筹学对偶理偶理论和灵敏度分析和灵敏度分析1第1页，共61页，编辑于2022年，星期三第一节第一节 对偶问题的提出对偶问题的提出 材料材料产品产品甲甲乙乙丙丙丁丁单件单件收益收益A32112000B41324000C22343000限额限额600400300200假设工厂考虑不进行生产而把假设工厂考虑不进行生产而把全部资源都转让，问如何定价全部资源都转让，问如何定价这些资源，既能使其获利不低这些资源，既能使其获利不低于安排生产所获得的收益，又于安排生产所获得的收益，又能使资源租让具有竞争力。能使资源租让具有竞争力。一、引例一、引例MaxZ=2000 x1+4000 x2+3000 x3s.t.3x1+4x2+2x36002x1+x2+2x3400 x1+3x2+3x3300 x1+2x2+4x3200 x1,x2,x30MinW=600y1+400y2+300y3+200y4s.t.3y1+2y2+y3+y420004y1+y2+3y3+2y440002y1+2y2+3y3+4y43000y1,y2,y3,y40 x1x2x3y1y2y3y42第2页，共61页，编辑于2022年，星期三二、对偶问题二、对偶问题（1 1）对称）对称LPLP问题的定义问题的定义（2 2）对称）对称LPLP问题的对偶问题问题的对偶问题第一类对称形式第一类对称形式第二类对称形式第二类对称形式3第3页，共61页，编辑于2022年，星期三例例1 1 写出下列写出下列LPLP问题的对偶问题问题的对偶问题对偶对偶MaxZ=2x1+3x2s.t.x1+2x284x1164x212x1,x2 0MinW=8y1+16y2+12y3s.t.y1+4y222y1+4y33y1,y2,y3 04第4页，共61页，编辑于2022年，星期三（3 3）对偶问题的对偶是原问题）对偶问题的对偶是原问题推导过程推导过程变形对偶变变形形对偶对偶对偶对偶变变形形MaxZ=CTXs.t.AXbX0MinW=bTYs.t.ATYCY0MaxW=-bTYs.t.-ATY-CY0MinZ=-CTXs.t.-(AT)TX-bX05第5页，共61页，编辑于2022年，星期三例例2 2 写出下列写出下列LPLP问题的对偶问题问题的对偶问题解解:上述上述LPLP问题的问题的 对偶问题为：对偶问题为：6第6页，共61页，编辑于2022年，星期三三、非对称三、非对称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第7页，共61页，编辑于2022年，星期三上述第一类对称形式上述第一类对称形式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第8页，共61页，编辑于2022年，星期三(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第9页，共61页，编辑于2022年，星期三例例3 3 直接写出直接写出LPLP问题的对偶问题问题的对偶问题10第10页，共61页，编辑于2022年，星期三11第11页，共61页，编辑于2022年，星期三第二节第二节 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第12页，共61页，编辑于2022年，星期三又又ATY(0)C,X(0)T0.所以所以 X(0)TATY(0)X(0)TC=CTX(0)(2)由（由（1），（），（2）得：得：CTX(0)bTY(0)13第13页，共61页，编辑于2022年，星期三推论推论1 1 若若LPLP问题有无界解，则其对偶问题无可行解；问题有无界解，则其对偶问题无可行解；若若LPLP问题无可行解，则对偶问题或有无界解或无可行解。问题无可行解，则对偶问题或有无界解或无可行解。推论推论2 2极大化问题的任何一个可行解所对应的目标极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题目标函数值的下界。函数值都是其对偶问题目标函数值的下界。极小化问题的任何一个可行解所对应的目标极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题目标函数值的上界。函数值都是其对偶问题目标函数值的上界。推论推论3 314第14页，共61页，编辑于2022年，星期三例例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+2x420 x1,x2,x3,x4 0MinW=20y1+20y2y1+2y21 2y1+y22 s.t.2y1+3y233y1+2y24 y1,y2015第15页，共61页，编辑于2022年，星期三定理定理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第16页，共61页，编辑于2022年，星期三例例5 5MaxZ=x1+2x2+3x3+4x4 x1+2x2+2x3+3x420s.t.2x1+x2+3x3+2x420 x1,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第17页，共61页，编辑于2022年，星期三定理定理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第18页，共61页，编辑于2022年，星期三则则(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第19页，共61页，编辑于2022年，星期三推论：推论：在用单纯形法求解在用单纯形法求解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+0 x3+0 x4+0 x5s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5020第20页，共61页，编辑于2022年，星期三cj23000CB XB bx1x2x3x4x52x1 0 x5 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第21页，共61页，编辑于2022年，星期三定理定理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第24页，共61页，编辑于2022年，星期三若若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第25页，共61页，编辑于2022年，星期三 1001/4000-21/21011/2-1/804422x1 0 x5 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第26页，共61页，编辑于2022年，星期三例例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第27页，共61页，编辑于2022年，星期三（1 1）告诉管理者增加何种资源对企业更有利；）告诉管理者增加何种资源对企业更有利；cj23000CB XB bx1x2x3x4x52x1 0 x5 3x24421001/4000-21/21011/2-1/80-1400-3/2-1/80（2 2）告诉管理者花多大代价买进资源或卖出资源是）告诉管理者花多大代价买进资源或卖出资源是合适的；合适的；（3 3）为新产品定价提供依据。）为新产品定价提供依据。二、影子价格的作用二、影子价格的作用28第28页，共61页，编辑于2022年，星期三一、对偶单纯形法的步骤一、对偶单纯形法的步骤(1)(1)化化LP问题的约束条件为问题的约束条件为“”形式形式,引入松弛变量引入松弛变量,建立初始表建立初始表;(2)(2)若所有常数项若所有常数项bi0，则最优解已经达到，否则，则最优解已经达到，否则bl=Minbi|bi0，选取选取bl所对应的变量为出基变量；所对应的变量为出基变量；(3)(3)计算计算k=Minj/alj|alj 0，即，即cj -j时，原最优解改变。时，原最优解改变。五、价值系数五、价值系数 C 的变化分析的变化分析公式推导公式推导 则则xj 的检验数为的检验数为47第47页，共61页，编辑于2022年，星期三例例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第48页，共61页，编辑于2022年，星期三解：最优单纯形表为解：最优单纯形表为从表中看到从表中看到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/549第49页，共61页，编辑于2022年，星期三2.2.基变量价值系数的改变基变量价值系数的改变五、价值系数五、价值系数 C 的变化分析的变化分析公式推导公式推导 若基变量的价值系数若基变量的价值系数 变为变为 则则即即50第50页，共61页，编辑于2022年，星期三例例7 7 下表为最优单纯形表下表为最优单纯形表,计算计算 c2变化的范围，使得原最变化的范围，使得原最优解不变。优解不变。c j23000CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80j00-3/2-1/80五、价值系数五、价值系数 C 的变化分析的变化分析例题例题 51第51页，共61页，编辑于2022年，星期三当当-3c21，即即 0c24时，原最优解不变。时，原最优解不变。c j23000CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80j00-3/2-1/80cj23+c2000CBXBbx1x2x3x4x52x141001/400 x5400-21/213+c2x22011/2-1/80j00-3/2-c2/2-1/8+c2/8052第52页，共61页，编辑于2022年，星期三1.1.增减变量增减变量(2)(2)删除变量删除变量删除非基变量最优解不变删除非基变量最优解不变删除基变量的处理方法：删除基变量的处理方法：将将xj 的系数的系数cj 变为变为-M，迫使，迫使xj0(1)(1)增加变量增加变量若所增加变量的检验数若所增加变量的检验数00，则原最优解不变；，则原最优解不变；否则，用单纯形法迭代求最优解。否则，用单纯形法迭代求最优解。六、技术矩阵六、技术矩阵 A 的变化分析的变化分析53第53页，共61页，编辑于2022年，星期三2.2.Pj 的变化的变化则最优解不变则最优解不变则原最优解改变则原最优解改变六、技术矩阵六、技术矩阵 A 的变化分析的变化分析54第54页，共61页，编辑于2022年，星期三3.3.增减约束条件增减约束条件(1)(1)删除约束条件删除约束条件当当n+1 1 0 0,n+2+2 0 0时最优解不变时最优解不变;否则否则,运用单纯形法迭代求运用单纯形法迭代求最优解。最优解。六、技术矩阵六、技术矩阵 A 的变化分析的变化分析55第55页，共61页，编辑于2022年，星期三(2)(2)增加约束条件增加约束条件六、技术矩阵六、技术矩阵 A 的变化分析的变化分析化约束条件为化约束条件为的形式，引入松弛变量的形式，引入松弛变量xn+1；把增加的约束条件直接写入最优表把增加的约束条件直接写入最优表(以松弛变量以松弛变量xn+1为基变量为基变量)，得到一个非标准表；，得到一个非标准表；化非标准表为标准表，若化非标准表为标准表，若b n+1，则最优解仍为最优解，则最优解仍为最优解，若若bn+1，则用对偶单纯形法迭代找出最优解。，则用对偶单纯形法迭代找出最优解。56第56页，共61页，编辑于2022年，星期三cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-11j-800-3-3-1例例8 8 已知某已知某LPLP问题的最优单纯形表如下：问题的最优单纯形表如下：如果增加约束条件如果增加约束条件x1+x32，最优解将如何变化？最优解将如何变化？六、技术矩阵六、技术矩阵 A 的变化分析的变化分析57第57页，共61页，编辑于2022年，星期三cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-110-800-3-3-10CBXBbx1x2x3x4x5x62x1110-13-103x22012-1100 x6-100-23-11-800-3-3-10 x6-2-10-1000 x6001非标准表非标准表标准表标准表 x1+x32-x1-x3+x6=-2 58第58页，共61页，编辑于2022年，星期三cj231000CBXBbx1x2x3x4x5x62x1210100-13x210102010 x51002-31-1-700-1-60-159第59页，共61页，编辑于2022年，星期三cj23100CBXBbx1x2x3x4x52x1110-13-13x22012-11-800-3-3-1课堂练习课堂练习 下面是某下面是某LPLP问题的最优单纯形表，当增加约束条件问题的最优单纯形表，当增加约束条件 x1+x24时时，最优解如何变化？，最优解如何变化？60第60页，共61页，编辑于2022年，星期三cj231000CBXBbx1x2x3x4x5x62x1110-13-103x22012-1100 x64110001-800-3-3-10cj231000CBXBbx1x2x3x4x5x62x1110-13-103x22011-1100 x6100-1-201-8000-3-10原最优解不变原最优解不变61第61页，共61页，编辑于2022年，星期三
