文章目录
一、互补松弛性
二、证明 互补松弛性
一、互补松弛性
X 0 \rm X^0X
0
和 Y 0 \rm Y^0Y
0
分别是 原问题 P \rm PP 问题 和 对偶问题 D \rm DD 的 可行解 ,
这两个解各自都是对应 线性规划问题 的 最优解
的 充要条件是 : { Y 0 X s = 0 Y s X 0 = 0
⎧⎩⎨Y0Xs=0YsX0=0
{Y0Xs=0YsX0=0
⎩
⎪
⎨
⎪
⎧
Y
0
X
s
=0
Y
s
X
0
=0
其中 X s , Y s \rm X_s , Y_sX
s
,Y
s
是 松弛变量 或 剩余变量 ;
二、证明 互补松弛性
原问题 :
m a x Z = C X s . t { A X ≤ b X ≥ 0
maxZ=CXs.t⎧⎩⎨AX≤bX≥0
maxZ=CXs.t{AX≤bX≥0
maxZ=CX
s.t
⎩
⎪
⎨
⎪
⎧
AX≤b
X≥0
对偶问题 :
m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0
minW=bTYs.t⎧⎩⎨ATY≥CTY≥0
minW=bTYs.t{ATY≥CTY≥0
minW=b
T
Y
s.t
⎩
⎪
⎨
⎪
⎧
A
T
Y≥C
T
Y≥0
松弛变量 与 剩余变量 :
将原问题的约束方程变为等式 , A X ≤ b \rm AX \leq bAX≤b , 添加 松弛变量 , A X + X s = b \rm AX + X_s = bAX+X
s
=b ; 其中 X s ≥ 0 \rm X_s \geq 0X
s
≥0 ;
将对偶问题的约束方程变为等式 , A T Y ≥ C T \rm A^TY \geq C^TA
T
Y≥C
T
, 减去 剩余变量 , A T Y − Y s = C T \rm A^TY - Y_s = C^TA
T
Y−Y
s
=C
T
; 其中 Y s ≥ 0 \rm Y_s \geq 0Y
s
≥0 ;
代入可行解到约束方程中 :
X 0 \rm X^0X
0
是原问题的可行解 , Y 0 \rm Y^0Y
0
是对偶问题的可行解 ;
将 X 0 \rm X^0X
0
代入到 A X + X s = b \rm AX + X_s = bAX+X
s
=b 等式中 , 可以得到 X s 0 \rm X_s^0X
s
0
的一个可行解 ,
将 Y 0 \rm Y^0Y
0
代入到 A T Y − Y s = C T \rm A^TY - Y_s = C^TA
T
Y−Y
s
=C
T
等式中 , 可以得到 Y s 0 \rm Y_s^0Y
s
0
的一个可行解 ;
根据 对偶理论中的 强对偶定理 , 只要 " X 0 \rm X^0X
0
和 Y 0 \rm Y^0Y
0
分别是 原问题 P \rm PP 问题 和 对偶问题 D \rm DD 的 最优解 "
那么其目标函数就是最大值与最小值的界限值 , 将这两个最优解代入到对应的目标函数中 , 求得的两个值是相等的 ;
将 X 0 \rm X^0X
0
代入到 m a x Z = C X \rm maxZ = C XmaxZ=CX 目标函数中 , 得到 C X 0 \rm CX^0CX
0
;
将 Y 0 \rm Y^0Y
0
代入到 m i n W = b T Y \rm minW = b^TYminW=b
T
Y 目标函数中 , 得到 b T Y 0 \rm b^TY^0b
T
Y
0
;
上述两个值相等 :
C X 0 = b T Y 0 \rm CX^0 = b^TY^0
CX
0
=b
T
Y
0
将 A X + X s = b \rm AX + X_s = bAX+X
s
=b 和 A T Y − Y s = C T \rm A^TY - Y_s = C^TA
T
Y−Y
s
=C
T
代入到上述等式中 , 得到 Y 0 X s = − Y s X 0 \rm Y^0 X_s = - Y_sX^0Y
0
X
s
=−Y
s
X
0
其中 Y 0 , X s , Y s , X 0 \rm Y^0 , X_s , Y_s , X^0Y
0
,X
s
,Y
s
,X
0
都是大于等于 0 00 的 , 但上述等式 Y 0 X s = − Y s X 0 \rm Y^0 X_s = - Y_sX^0Y
0
X
s
=−Y
s
X
0
中符号相反 , 说明 等号两边的值都是 0 00 ;
