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

1第二章线性规划的对偶理论窗含西岭千秋雪，门泊东吴万里船本章主要内容：•线性规划的对偶问题概念、理论及经济意义•线性规划的对偶单纯形法•线性规划的灵敏度分析2第一节对偶问题的提出材料产品甲乙丙丁单件收益A32112000B41324000C22343000限额600400300200假设工厂考虑不进行生产而把全部资源都转让，问如何定价这些资源，既能使其获利不低于安排生产所获得的收益，又能使资源租让具有竞争力。一、引例MaxZ=2000x1+4000x2+3000x3s.t.3x1+4x2+2x3≤6002x1+x2+2x3≤400x1+3x2+3x3≤300x1+2x2+4x3≤200x1,x2,x3≥0MinW=600y1+400y2+300y3+200y4s.t.3y1+2y2+y3+y4≥20004y1+y2+3y3+2y4≥40002y1+2y2+3y3+4y4≥3000y1,y2,y3,y4≥0x1x2x3y1y2y3y43二、对偶问题（1）对称LP问题的定义..0TMaxZCXAXbSTX..0TTMinWbYAYCSTY（2）对称LP问题的对偶问题()L()D..0TTMinWbYAYCSTY第一类对称形式第二类对称形式..0TMaxZCXAXbSTX4例1写出下列LP问题的对偶问题对偶MaxZ=2x1+3x2s.t.x1+2x2≤84x1≤164x2≤12x1,x2≥0MinW=8y1+16y2+12y3s.t.y1+4y2≥22y1+4y3≥3y1,y2,y3≥05（3）对偶问题的对偶是原问题推导过程变形对偶变形对偶对偶变形()LMaxZ=CTXs.t.AX≤bX≥0()DMinW=bTYs.t.ATY≥CY≥0MaxW’=-bTYs.t.-ATY≤-CY≥0MinZ’=-CTXs.t.-(AT)TX≥-bX≥0()DD61212312312312334334748:1,,0MinWxxxxxxxxSTxxxxxx1231231231231237834334:40,,0MaxZyyyyyyyyySTyyyyyy例2写出下列LP问题的对偶问题解:上述LP问题的对偶问题为：7三、非对称LP问题的对偶问题例3写出下列LP问题的对偶问题解：用x2=-x2’,x3=x3’-x3’’代入上述LP问题，并将其化为第一类对称形式MaxZ=x1+2x2+x3x1+x2-x3≤2s.t.x1-x2+x3=12x1+x2+x3≥2x1≥0,x2≤0,x3无约束MaxZ=x1-2x2’+x3’-x3’’x1-x2’-x3’+x3’’≤2x1+x2’+x3’-x3’’≤1s.t.-x1-x2’-x3’+x3’’≤-1-2x1+x2’-x3’+x3’’≤-2x1,x2’,x3’,x3’’≥08上述第一类对称形式LP问题的对偶问题为：则上述问题变为：MinW=2y1+y2-y3-2y4y1+y2-y3-2y4≥1-y1+y2-y3+y4≥-2s.t.-y1+y2-y3-y4≥1y1-y2+y3+y4≥-1y1,y2,y3,y4≥0MinW=2u1+u2+2u3u1+u2+2u3≥1s.t.u1-u2+u3≤2-u1+u2+u3=1u1≥0,u3≤0,u2无约束令u1=y1u2=y2-y3u3=-y49(D)MinW=2u1+u2+2u3u1+u2+2u3≥1s.t.u1-u2+u3≤2-u1+u2+u3=1u1≥0,u3≤0,u2无约束(L)MaxZ=x1+2x2+x3x1+x2-x3≤2s.t.x1-x2+x3=12x1+x2+x3≥2x1≥0,x2≤0,x3无约束对偶关系：一个问题第i个变量的约束情况决定另一问题第i个约束不等式的方向，反之亦然。正常的对正常的，不正常的对不正常的10例3直接写出LP问题的对偶问题123123123123123221:220,0,MaxZxxxxxxxxxSTxxxxxx无约束12322MinWuuu123uuu1232uuu123uuu1210u，1:ST2u无约束，30u1112312312312312322212:10,,0MinWuuuuuuuuuSTuuuuuu无约束1232MaxZxxx:ST123xxx123xxx1232xxx21210x20x3x无约束12第二节LP问题的对偶理论若X(0),Y(0)分别为(L),(D)的可行解，则有CTX(0)≤bTY(0)定理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）13又ATY(0)≥C,X(0)T≥0.所以X(0)TATY(0)≥X(0)TC=CTX(0)(2)由（1），（2）得：CTX(0)≤bTY(0)14推论1若LP问题有无界解，则其对偶问题无可行解；若LP问题无可行解，则对偶问题或有无界解或无可行解。推论2极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题目标函数值的下界。极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题目标函数值的上界。推论315例4考虑下面一对LP问题其对偶问题为：由于X(0)=(1,1,1,1)T,Y(0)=(1,1)T分别为(L),(D)的可行解，故Z≤40,W≥10.MaxZ=x1+2x2+3x3+4x4x1+2x2+2x3+3x4≤20s.t.2x1+x2+3x3+2x4≤20x1,x2,x3,x4≥0MinW=20y1+20y2y1+2y2≥12y1+y2≥2s.t.2y1+3y2≥33y1+2y2≥4y1,y2≥016定理2（最优性准则）当LP问题目标函数值与其对偶问题目标函数值相等时，各自的可行解即为最优解。若X(0),Y(0)分别为(L)，(D)的可行解,且CTX(0)＝bTY(0)，则X(0),Y(0)分别为(L)，(D)的最优解。证明：由定理1可知，对于(L)的任意可行解X，有CTX≤bTY(0)由于CTX(0)=bTY(0)，故X(0)为(L)的最优解。同理Y(0)为(D)的最优解。17例5()DMaxZ=x1+2x2+3x3+4x4x1+2x2+2x3+3x4≤20s.t.2x1+x2+3x3+2x4≤20x1,x2,x3,x4≥0MinW=20y1+20y2y1+2y2≥12y1+y2≥2s.t.2y1+3y2≥33y1+2y2≥4y1,y2≥0由于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)的最优解。18定理3（强对偶定理）若(L)，(D)均有可行解，则(L)，(D)均有最优解，且目标函数最优值相等。证明：设X(0),Y(0)分别为(L)，(D)的可行解,由弱对偶定理，对于(L)的任意可行解X，有CTX≤bTY(0)，所以CTX在可行域内有上界，故(L)有最优解。同理，对于(D)的任意可行解Y，有bTY≥CTX(0)，所以bTY在可行域内有下界，故(D)有最优解。设(L)的最优解为X(0)，且X(0)所对应的最优基为B，X(0)可以表示为X(0)=XB(0)=B-1bXN(0)019则(σAT,σST)=(CT,0T)–CBTB-1(A,I)≤0由于CT–CBTB-1A≤0，所以CBTB-1A≥CT即AT(CBTB-1)T≥C(1)又0T–CBTB-1I≤0，故(CBTB-1)T≥0.(2)令Y(0)=(CBTB-1)T，由(1)(2)知Y(0)是(D)的可行解.因为CTX(0)=(CBT,CNT)XB(0)=CBTXB(0)+CNTXN(0)=CBTB-1bXN(0)而bTY(0)=bT(CBTB-1)T=CBTB-1b则CTX(0)=bTY(0)，由最优性准则知，X(0),Y(0)分别为(L)，(D)的最优解,且目标函数最优值相等。20推论：在用单纯形法求解LP问题(L)的最优单纯形表中，松弛变量的检验数的相反数就是其对偶问题(D)的最优解。证明：因为σsT=0T-CBTB-1I=-CBTB-1y*T=CBTB-1所以y*=-σs例5求下列问题对偶问题的最优解MaxZ=2x1+3x2s.t.x1+2x2≤84x1≤164x2≤12x1,x2≥0解：化为标准型MaxZ=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥021cj23000CBXBbx1x2x3x4x52x10x53x24421001/4000-21/21011/2-1/80-1400-3/2-1/80此时达到最优解X*=(4,2)T,MaxZ=14。对偶问题的最优解为Y*=(3/2,1/8,0)T运用单纯形法计算得原问题的最终表如下：22定理4（互补松弛定理）在最优情况下，原问题的第i个决策变量与其对偶问题第i个约束中的松弛变量的乘积恒为零。设X(0),Y(0)分别为(L),(D)的可行解，则X(0),Y(0)分别为(L),(D)的最优解的充要条件为,有m(1)若xl(0)0，则∑ailyi(0)=Cli=1m(2)若∑ailyi(0)Cl，则xl(0)=0i=1n(3)若yk(0)0，则∑akjxj(0)=bkj=1n(4)若∑akjxj(0)bk，则yk(0)=0j=123()L()D例6考虑下面问题MaxZ=x1+2x2+3x3+3x4x1+2x2+2x3+3x4≤20s.t.2x1+x2+3x3+2x4≤20x1,x2,x3,x4≥0MinW=20y1+20y2y1+2y2≥12y1+y2≥2s.t.2y1+3y2≥33y1+2y2≥4y1,y2≥0已知(D)的最优解为Y*=(6/5,1/5)T用互补松弛定理求出(L)的最优解。24****123422320(1)xxxx****123423220(2)xxxx**...1221204161yy**...1222402262yy**342320xx**343220xx所以x1*=x2*=0.解：由于y1*0,y2*0,由互补松弛性知解得x3*=x4*=4.所以(L)的最优解为X*=(0,0,4,4)T因为代入(1),(2)得25若X*,Y*分别为(L),(D)的最优解，那么CTX*=bTY*。由Z*=bTY*=b1y1*+b2y2*++bmym*可知Z*/bi=yi*yi*表示资源量bi变化1个单位对目标函数最优值Z产生的影响，称之为第i种资源的影子价格。第三节对偶问题的经济解释----影子价格一、影子价格1.定义影子价格是最优配置下资源的理想价格。2.含义261001/4000-21/21011/2-1/804422x10x53x2x1x2x3x4x5CBXBb23000cj-1400-3/2-1/80例7下面是一张LP问题的最优单纯形表，其中x3,x4,x5为松弛变量则对偶问题的最优解为Y*=(1.5,0.125,0)T27例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.5