《对偶理论几个性质的证明.docx》由会员分享，可在线阅读，更多相关《对偶理论几个性质的证明.docx（5页珍藏版）》请在三一办公上搜索。
1、对偶理论几个性质的证明对偶理论的性质及证明 性质1(对称性) 对偶问题的对偶问题是原问题 证明 设原问题为 max z =CXAXbs.t.X0 (1) 对偶问题为 min w =YbYACs.t.X0 (2) 对偶问题的对偶问题为 max j =CUAUbs.tU0 (3) 比较式(1)和式(3), 显然二者是等价的, 命题得证. 性质2(弱对偶性) 设原问题为式(1),对偶问题为式(2),X是原问题的任意一个可行解,Y是对偶问题的任意一个可行解,那么总有 CXYb (4) 证明 根据式(1), 由于AXb, 又由于Y0, 从而必有 YAXYb (5) 根据式(2), 由于YAc, 又由于X
2、0, 从而必有 YAXCX (6) 结合式(5)和式(6), 立即可得CXYb,命题得证. 性质3(最优性) 设X*原问题式(1)的可行解,Y*是对偶问题式(2)的可行解,当是CX*=Y*b时,X*是原问题式(1)的最优解,Y*是对偶问题式(2)的最优解. 证明 设X是式(1)的最优解, 那么有 CXCX* (7) 由于CX*=Y*b,那么 CXY*b (8) 根据弱对偶性质, 又有 CXY*b (9) 从而CX=CX*, 也就是X*是原问题式(1)的最优解。 同理，也可证明Y*是对偶问题式(2)的最优解。 性质4(无界性) 设原问题为无界解，则对偶问题无解。 证明 用反证法证明。 设原问题为
3、式(1)，对偶问题为式(2)。 假定对偶问题有解，那么存在一个可行解为Y。这时对偶问题的目标函数值为Yb=T。 由于原问题为无界解，那么一定存在一个可行解X满足CXT，因此CXYb。 而根据弱对偶性，又有CXYb，发生矛盾。从而对偶问题没有可行解。 性质5(强对偶性、对偶性定理) 若原问题有最优解，那么对偶问题也有最优解，且最优目标函数值相等。 证明 设B为原问题式(1)的最优基，那么当基为B时的检验数为C-CBB-1A，其中CB为由基变量的价值系数组成的价值向量。 既然B为原问题式(1)的最优基，那么有C-CBB-1A0。 令Y=CBB-1，那么有C-YA0YAC，从而Y=CBB-1是对偶问
4、题式(2)的可行解。 这样一来，Y=CBB-1是对偶问题的可行解，XB=B-1b是原问题的最优基可行解。 1 由于CX=CBXB+CNXN=CBB-1b，而Yb=CB，从而有CX=Yb。根据性质3，命B-b题得证。 , Y分别是原问题和对偶问题的可行解，性质6(对偶松弛定理、松弛性) 若X=0和YX=0，当且仅当X, Y为最优解。 那么YXss证明 设原问题和对偶问题的标准型是 原问题 对偶问题 max z =CXAXbs.t.X0 min w =YbYACs.t.X0将原问题目标函数中的系数向量C用C=YA-Ys代替后，得到 Z=CX=(YA-Ys)X=YAX-YsX (10) 将对偶问题的目标函数中系数列向量，用b=AX+Xs代替后，得到 w=Yb=Y(AX+Xs)=YAX+YXs (11) =YAX=Yb，由最优性可知X=0，YX=0，则CX, Y分别是原问题和对偶问若YXss题的最优解。 =Yb , Y分别是原问题和对偶问题的可行解，再根据最优性，则有CX又若X=0，YX=0。 由式(10)和(11)，必有YXss
