一、对称性质

对称性定理 :

• 原问题 ( $LP$ ) 的 对偶 是 对偶问题 ( $DP$ )
• 对偶问题 ( $DP$ ) 的 对偶 是 原问题 ( $LP$ )

原问题 和 对偶问题 互为对偶 ;

对偶问题是对称的

原问题 $LP$ :

m a x Z = C X s . t { A X ≤ b X ≥ 0

对偶问题 $DP$ :

m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0

二、对称性质推导

将上述 对偶问题 $DP$ 转为求最大值 ;

m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0

转换过程 :

• 目标函数转为取最大值 : 转换后的结果如下 , 就是相当于在目标函数的左右两端乘以 $-1$ ;

m a x Z = − b T Y s . t { A T Y ≥ C T Y ≥ 0

• 根据下面表格中的对偶问题写法 , 写出上述线性规划的对偶问题 :
  • 目标函数由最大值转为最小值 ( 目标函数求最大值前提 ) : $minW=CX$
  • $LP$ 约束条件与 $DP$ 约束变量符号相反 ( 目标函数求最大值前提 ) : 上述线性规划问题的 约束条件是大于等于不等式 , 那么对应的 约束变量小于等于 $0$ ; 约束变量 $X\le 0$
  • $LP$ 约束变量 与 $DP$ 约束条件符号相同 ( 目标函数求最大值前提 ) : 上述线性规划问题的 约束变量大于等于 $0$ , 那么对应的 约束条件也是大于等于不等式 ; 约束条件是 $AX\ge -b$
  • 最终得到的线性规划为 :

m i n W = C X s . t { A X ≥ − b X ≤ 0

记住一条 : 目标函数求最大值 , $LP$ 约束条件与 $DP$ 约束变量符号相反 , $LP$ 约束变量 与 $DP$ 约束条件符号相同 ;

对如下线性规划作代换 :

m i n W = C X s . t { A X ≥ − b X ≤ 0

代换内容 : 引入变量 $X^{\prime }=-X$ , 使用 $-X^{\prime }$ 替换上述线性规划中的 $X$ ;

• 目标函数 : 代换后为 $minW=-C{X}^{\prime }$ , 此时两边乘以 $-1$ 即可得到 $maxZ=C{X}^{\prime }$ ;
• 约束方程 : 代换后为 $-A{X}^{\prime }\ge -b$ , 左右两边乘以 $-1$ 即可得到 $A{X}^{\prime }\le b$ ;
• 约束变量 : 代换后为 $-X^{\prime }\le 0$ , 左右变量乘以 $-1$ 即可得到 $X^{\prime }\ge 0$

最终代换结果为 :

m a x Z = C X ′ s . t { A X ′ ≤ b X ′ ≥ 0

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/107722928