对偶理论几个性质的证明

对偶理论的性质及证明性质1(对称性)对偶问题的对偶问题是原问题证明设原问题为maxz..0CXAXbstX(1)对偶问题为min..0wYbYACstX(2)对偶问题的对偶问题为max..0CUAUbstU(3)比较式(1)和式(3),显然二者是等价的,命题得证.性质2(弱对偶性)设原问题为式(1),对偶问题为式(2),X是原问题的任意一个可行解,Y是对偶问题的任意一个可行解,那么总有CXYb(4)证明根据式(1),由于AXb,又由于0Y,从而必有YAXYb(5)根据式(2),由于YAc,又由于0X,从而必有YAXCX(6)结合式(5)和式(6),立即可得CXYb,命题得证.性质3(最优性)设*X原问题式(1)的可行解,*Y是对偶问题式(2)的可行解,当是**CXYb时,*X是原问题式(1)的最优解,*Y是对偶问题式(2)的最优解.证明设X是式(1)的最优解,那么有*CXCX(7)由于**CXYb,那么*CXYb(8)根据弱对偶性质,又有*CXYb(9)从而*CXCX,也就是*X是原问题式(1)的最优解。同理，也可证明*Y是对偶问题式(2)的最优解。性质4(无界性)设原问题为无界解，则对偶问题无解。证明用反证法证明。设原问题为式(1)，对偶问题为式(2)。假定对偶问题有解，那么存在一个可行解为Y。这时对偶问题的目标函数值为YbT。由于原问题为无界解，那么一定存在一个可行解X满足CXT，因此CXYb。而根据弱对偶性，又有CXYb，发生矛盾。从而对偶问题没有可行解。性质5(强对偶性、对偶性定理)若原问题有最优解，那么对偶问题也有最优解，且最优目标函数值相等。证明设B为原问题式(1)的最优基，那么当基为B时的检验数为1BCCBA，其中BC为由基变量的价值系数组成的价值向量。既然B为原问题式(1)的最优基，那么有10BCCBA。令1BYCB，那么有0CYAYAC，从而1BYCB是对偶问题式(2)的可行解。这样一来，1BYCB是对偶问题的可行解，1BXBb是原问题的最优基可行解。由于1BBNNBCXCXCXCBb，而1BYbCBb，从而有CXYb。根据性质3，命题得证。性质6(对偶松弛定理、松弛性)若ˆˆ,XY分别是原问题和对偶问题的可行解，那么ˆ0sYX和ˆ0sYX，当且仅当ˆˆ,XY为最优解。证明设原问题和对偶问题的标准型是原问题对偶问题maxz..0CXAXbstXmin..0wYbYACstX将原问题目标函数中的系数向量C用sCYAY代替后，得到()ssZCXYAYXYAXYX(10)将对偶问题的目标函数中系数列向量，用sbAXX代替后，得到()ssYbYAXXYAXYX(11)若ˆ0sYX，ˆ0sYX，则ˆˆˆˆCXYAXYb，由最优性可知ˆˆ,XY分别是原问题和对偶问题的最优解。又若ˆˆ,XY分别是原问题和对偶问题的可行解，再根据最优性，则有ˆˆCXYb由式(10)和(11)，必有ˆ0sYX，ˆ0sYX。