X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D 的 可行解 ,

这两个解各自都是对应 线性规划问题 的 最优解

的 充要条件是 : { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} ⎩⎪⎨⎪⎧​Y0Xs​=0Ys​X0=0​

其中 X s , Y s \rm X_s , Y_s Xs​,Ys​ 是 松弛变量 或 剩余变量 ;

原问题 :

m a x Z = C X s . t { A X ≤ b X ≥ 0 \begin{array}{lcl} \rm maxZ = C X \\\\ \rm s.t\begin{cases} \rm AX \leq b \\\\ \rm X \geq 0 \end{cases}\end{array} maxZ=CXs.t⎩⎪⎨⎪⎧​AX≤bX≥0​​

对偶问题 :

m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0 \begin{array}{lcl} \rm minW = b^T Y \\\\ \rm s.t\begin{cases} \rm A^TY \geq C^T \\\\ \rm Y \geq 0 \end{cases}\end{array} minW=bTYs.t⎩⎪⎨⎪⎧​ATY≥CTY≥0​​

松弛变量 与 剩余变量 :

将原问题的约束方程变为等式 , A X ≤ b \rm AX \leq b AX≤b , 添加 松弛变量 , A X + X s = b \rm AX + X_s = b AX+Xs​=b ; 其中 X s ≥ 0 \rm X_s \geq 0 Xs​≥0 ;

将对偶问题的约束方程变为等式 , A T Y ≥ C T \rm A^TY \geq C^T ATY≥CT , 减去 剩余变量 , A T Y − Y s = C T \rm A^TY - Y_s = C^T ATY−Ys​=CT ; 其中 Y s ≥ 0 \rm Y_s \geq 0 Ys​≥0 ;

代入可行解到约束方程中 :

X 0 \rm X^0 X0 是原问题的可行解 , Y 0 \rm Y^0 Y0 是对偶问题的可行解 ;

将 X 0 \rm X^0 X0 代入到 A X + X s = b \rm AX + X_s = b AX+Xs​=b 等式中 , 可以得到 X s 0 \rm X_s^0 Xs0​ 的一个可行解 ,

将 Y 0 \rm Y^0 Y0 代入到 A T Y − Y s = C T \rm A^TY - Y_s = C^T ATY−Ys​=CT 等式中 , 可以得到 Y s 0 \rm Y_s^0 Ys0​ 的一个可行解 ;

根据 对偶理论中的 强对偶定理 , 只要 " X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D 的 最优解 "

那么其目标函数就是最大值与最小值的界限值 , 将这两个最优解代入到对应的目标函数中 , 求得的两个值是相等的 ;

将 X 0 \rm X^0 X0 代入到 m a x Z = C X \rm maxZ = C X maxZ=CX 目标函数中 , 得到 C X 0 \rm CX^0 CX0 ;

将 Y 0 \rm Y^0 Y0 代入到 m i n W = b T Y \rm minW = b^TY minW=bTY 目标函数中 , 得到 b T Y 0 \rm b^TY^0 bTY0 ;

上述两个值相等 :

C X 0 = b T Y 0 \rm CX^0 = b^TY^0 CX0=bTY0

将 A X + X s = b \rm AX + X_s = b AX+Xs​=b 和 A T Y − Y s = C T \rm A^TY - Y_s = C^T ATY−Ys​=CT 代入到上述等式中 , 得到 Y 0 X s = − Y s X 0 \rm Y^0 X_s = - Y_sX^0 Y0Xs​=−Ys​X0

其中 Y 0 , X s , Y s , X 0 \rm Y^0 , X_s , Y_s , X^0 Y0,Xs​,Ys​,X0 都是大于等于 0 0 0 的 , 但上述等式 Y 0 X s = − Y s X 0 \rm Y^0 X_s = - Y_sX^0 Y0Xs​=−Ys​X0 中符号相反 , 说明 等号两边的值都是 0 0 0 ;