【运筹学】对偶理论 : 总结 ( 对偶理论 |
您所在的位置:网站首页 › 目标函数值的增减方向与什么有关 › 【运筹学】对偶理论 : 总结 ( 对偶理论 |
文章目录
一、对偶理论1、对称性定理2、弱对偶定理3、最优性定理4、强对偶性5、互补松弛定理
二、原问题与对偶问题对应关系二、对偶理论的相关结论1、对偶问题存在2、对偶问题转化3、对偶问题的解4、互补松弛定理
一、对偶理论
1、对称性定理
对称性定理 : 原问题 ( L P LP LP ) 的 对偶 是 对偶问题 ( D P DP DP )对偶问题 ( D P DP DP ) 的 对偶 是 原问题 ( L P LP LP )原问题 和 对偶问题 互为对偶 ; 对偶问题是对称的 原问题 L P LP LP : m a x Z = C X s . t { A X ≤ b X ≥ 0 \begin{array}{lcl} maxZ = C X \\\\ s.t\begin{cases} AX \leq b \\\\ X \geq 0 \end{cases}\end{array} maxZ=CXs.t⎩⎪⎨⎪⎧AX≤bX≥0 对偶问题 D P DP DP : m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0 \begin{array}{lcl} minW = b^T Y \\\\ s.t\begin{cases} A^TY \geq C^T \\\\ Y \geq 0 \end{cases}\end{array} minW=bTYs.t⎩⎪⎨⎪⎧ATY≥CTY≥0 2、弱对偶定理弱对偶定理 : 假设 X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 问题 ( P ) \rm (P) (P) ( 目标函数求最大值 ) 和 问题 ( D ) \rm (D) (D) ( 目标函数求最小值 ) 的 可行解 , 则必有 C X 0 ≤ Y 0 b \rm CX^0 \leq Y^0 b CX0≤Y0b , 展开后为 ∑ j = 1 n c j x j ≤ ∑ i = 1 m y i b i \rm \sum_{j = 1}^n c_j x_j \leq \sum_{i = 1}^{m} y_i b_i ∑j=1ncjxj≤∑i=1myibi 弱对偶定理推论 1 : 原问题 任何一个 可行解 的目标函数值 , 都是其对偶问题 目标函数值的下界 ; 反之 , 对偶问题 任何一个 可行解 的目标函数值 , 都是其原问题 目标函数的上界 ; 弱对偶定理推论 2 : ( 对偶问题的无界性 ) 在一对 对偶问题 ( P ) \rm (P) (P) 和 ( D ) \rm (D) (D) 中 , 如果其中 一个线性规划问题可行 , 但是 目标函数无界 , 则 另外一个问题没有可行解 ; 如果其中 一个线性规划问题不可行 , 其 对偶问题不一定不可行 ; 弱对偶定理推论 3 : 在一对 对偶问题 ( P ) \rm (P) (P) 和 ( D ) \rm (D) (D) 中 , 如果其中 一个线性规划问题可行 , 而 另一个线性规划问题不可行 , 则 该可行问题的目标函数是无界的; 3、最优性定理最优性定理 : 如果 X 0 \rm X^0 X0 是 原问题的可行解 , Y 0 \rm Y^0 Y0 是 对偶问题的可行解 , 并且 两个可行解对应的目标函数值相等 , 即 C X 0 = B Y 0 \rm CX^0 = BY^0 CX0=BY0 , 即 z = w \rm z = w z=w , 则 X 0 \rm X^0 X0 是原问题的最优解 , Y 0 \rm Y^0 Y0 是对偶问题的最优解 ; 4、强对偶性强对偶性 : 如果 原问题 与 对偶问题 都有可行解 , 只要有一个问题有最优解 , 则 两个问题都有最优解 , 二者的最优解的目标函数值相等 ; 5、互补松弛定理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=0YsX0=0 其中 X s , Y s \rm X_s , Y_s Xs,Ys 是 松弛变量 或 剩余变量 ; 互补松弛定理简写 : " X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D 的 最优解 " ⇔ \Leftrightarrow ⇔ { 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=0YsX0=0 其中 X s , Y s \rm X_s , Y_s Xs,Ys 是 松弛变量 或 剩余变量 ; 二、原问题与对偶问题对应关系原问题与对偶问题对应关系 : 如果 原问题 有最优解 , 对偶问题也 有最优解 ; 如果 原问题 有 无界解 , 对偶问题 无可行解 ; 如果 原问题 无可行解 , 对偶问题 无法判断 ; 上述是根据弱对偶定理总结的 ; 二、对偶理论的相关结论 1、对偶问题存在任何 线性规划问题 , 都有一个对应的 对偶线性规划问题 ; 2、对偶问题转化原问题 P \rm P P : 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 ; \ \ \ \ \ \ \ \ \ \ \, 对偶问题 D \rm D D : 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 原问题与对偶问题对应关系 : 原问题第 i i i 个约束条件是 ≤ \leq ≤ 约束 , 其对偶问题的第 i i i 个变量的符号不确定 , 可能大于等于 0 0 0 , 也可能小于等于 0 0 0 ; 查看 约束变量的符号 与 其另外一个对偶问题的 约束方程的符号 一致性 , 来确定对偶问题的约束方程符号 ; 约束方程符号 : 如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 ≥ \geq ≥ , 因此 对偶问题的约束方程符号 与 原问题变量 符号一致 ; 如果当前线性规划问题 目标函数是求最小值 , 原问题就是下面的问题 , 其对偶问题 ( 上面的 ) 的约束方程符号是 ≤ \leq ≤ , 因此 对偶问题的约束方程符号 与 原问题变量 符号相反 ; 变量符号 : 如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 ≥ \geq ≥ , 因此 对偶问题的变量符号 与 原问题约束方程符号 符号相反 ; 如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 ≥ \geq ≥ , 因此 对偶问题的变量符号 与 原问题约束方程符号 符号一致 ; 3、对偶问题的解① 互为对偶的两个问题 , 或者同时都有最优解 , 或者同时都没有最优解 ; ② 对偶问题 有可行解 , 原问题 不一定有可行解 , 因为对偶问题的可行解可能是 无界解 , 原问题可能 无可行解 ; ③ 原问题有 多重解 , 对偶问题 可能有多重解 , 也 可能有唯一解 ; 多重解是 有无穷多最优解 ; ④ 对偶问题 有可行解 , 原问题 无可行解 , 则对偶问题 有无界解 ; 一对问题中 , 一个有可行解 , 一个无可行解 , 则有可行解的是无界解 ; ⑤ 原问题 没有最优解 , 对偶问题无法判断 ; 没有最优解有两种情况 , 一种是 无界解 , 一种是 无可行解 ; 如果原问题有无界解 , 则对偶问题无可行解 ; 如果原问题无可行解 , 则对偶问题无可行解 ; ⑥ 如果对偶问题没有可行解 , 对偶问题无法判断 , 无界解 或 无可行解 两种情况都有可能 ; ⑦ 如果原问题与对偶问题 都有可行解 , 则 都有最优解 ; 如果 原问题 有最优解 , 对偶问题也 有最优解 ; 如果 原问题 有 无界解 , 对偶问题 无可行解 ; 如果 原问题 无可行解 , 对偶问题 无法判断 ; 4、互补松弛定理如果 X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是原问题与对偶问题的最优解 , 则 Y 0 X s = Y s X 0 = 0 \rm Y^0 X_s = Y_sX^0 = 0 Y0Xs=YsX0=0 ; " X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D 的 最优解 " ⇔ \Leftrightarrow ⇔ { 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=0YsX0=0 其中 X s , Y s \rm X_s , Y_s Xs,Ys 是 松弛变量 或 剩余变量 ; |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |