对偶理论

参考博客 :

1 . 对称形式特点 :

2 . 原问题 P P P 的线性规划模型是 :

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​​

对称形式 P P P 要求 :

相关系数 :

3 . 对偶问题 D D D 的线性规划模型是 :

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​​

对偶问题 D D D 要求 :

相关系数 :

等价方法 ( 快速理解 ) :

对偶有以下规律 : 假设原问题 L P LP LP 目标函数求最大值 m a x Z maxZ maxZ , 对偶问题 D P DP DP 求最小值 m i n W minW minW ;

约束条件与约束变量的对应关系 ( 目标函数求最大值 ) : 这里特别注意 , 约束条件与约束变量 大于小于符号是相反的 ;

约束变量与约束条件的对应关系 ( 目标函数求最大值 ) : 这里特别注意 , 约束变量与约束条件 大于小于符号是相同的 ;

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

补一张图 , 方便记忆 :

写出如下线性规划对偶问题 :

m a x Z = 2 x 1 − 3 x 2 + 4 x 3 s . t { 2 x 1 + 3 x 2 − 5 x 3 ≥ 2 3 x 1 + x 2 + 7 x 3 ≤ 3 − x 1 + 4 x 2 + 6 x 3 ≥ 5 x j ≥ 0 ( j = 1 , 2 , 3 ) \begin{array}{lcl} maxZ = 2x_1 - 3x_2 + 4x_3 \\\\ s.t\begin{cases} 2 x_1 + 3x_2 - 5x_3 \geq 2 \\\\ 3x_1 + x_2 + 7x_3 \leq 3 \\\\ -x_1 + 4x_2 + 6x_3 \geq 5 \\\\ x_j \geq 0 \quad ( j = 1, 2, 3 ) \end{cases}\end{array} maxZ=2x1​−3x2​+4x3​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​2x1​+3x2​−5x3​≥23x1​+x2​+7x3​≤3−x1​+4x2​+6x3​≥5xj​≥0(j=1,2,3)​​

将上述线性规划转为 对称形式 :

目标函数最大值 : 对称形式目标函数求最大值 , 上述线性规划符合该条件 , 不用进行修改 ;

约束方程小于等于不等式 : 对称形式的约束方程都是小于等于不等式 , 方程 1 1 1 和方程 3 3 3 都是大于等于不等式 , 不符合要求 ; 将不等式左右两边都乘以 − 1 -1 −1 , 可以将大于等于不等式转为小于等于不等式 ;

转换后的结果为 :

m a x Z = 2 x 1 − 3 x 2 + 4 x 3 s . t { − 2 x 1 − 3 x 2 + 5 x 3 ≤ − 2 3 x 1 + x 2 + 7 x 3 ≤ 3 x 1 − 4 x 2 − 6 x 3 ≤ − 5 x j ≥ 0 ( j = 1 , 2 , 3 ) \begin{array}{lcl} maxZ = 2x_1 - 3x_2 + 4x_3 \\\\ s.t\begin{cases} -2 x_1 - 3x_2 + 5x_3 \leq -2 \\\\ 3x_1 + x_2 + 7x_3 \leq 3 \\\\ x_1 - 4x_2 - 6x_3 \leq -5 \\\\ x_j \geq 0 \quad ( j = 1, 2, 3 ) \end{cases}\end{array} maxZ=2x1​−3x2​+4x3​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​−2x1​−3x2​+5x3​≤−23x1​+x2​+7x3​≤3x1​−4x2​−6x3​≤−5xj​≥0(j=1,2,3)​​

对称形式 的 目标函数的系数 为 C = ( 2 − 3 4 ) C = \begin{pmatrix} & 2 & -3 & 4 & \end{pmatrix} C=(​2​−3​4​​) , 约束方程的系数 为 A = ( − 2 − 3 5 3 1 7 1 − 4 − 6 ) A = \begin{pmatrix} &-2 & -3 & 5 & \\ &3 & 1 & 7 & \\ &1 & -4 & -6 & \\ \end{pmatrix} A=⎝⎛​​−231​−31−4​57−6​​⎠⎞​ , 约束方程常数 b = ( − 2 3 − 5 ) b = \begin{pmatrix} &-2 &\\ &3 & \\ &-5 & \\ \end{pmatrix} b=⎝⎛​​−23−5​​⎠⎞​ ;

对偶问题 的 目标函数系数 为 b T = ( − 2 3 − 5 ) b^T = \begin{pmatrix} & -2 & 3 & -5 & \end{pmatrix} bT=(​−2​3​−5​​) , 约束方程的系数 为 A T = ( − 2 3 1 − 3 1 − 4 5 7 − 6 ) A^T = \begin{pmatrix} &-2 & 3 & 1 & \\ &-3 & 1 & -4 & \\ &5 & 7 & -6 & \\ \end{pmatrix} AT=⎝⎛​​−2−35​317​1−4−6​​⎠⎞​ , 约束方程常数 C T = ( 2 − 3 4 ) C^T = \begin{pmatrix} & 2 &\\ &-3 & \\ &4 & \\ \end{pmatrix} CT=⎝⎛​​2−34​​⎠⎞​ ;

线性规划形式 :

对称形式 : 求目标函数最大值 , 约束方程是求小于等于不等式 ;

对偶问题 : 求目标函数求最小值 , 约束方程都是大于等于不等式 ;

根据上述分析 , 写出对偶形式 :

m i n W = − 2 y 1 + 3 y 2 − 5 y 3 s . t { − 2 y 1 + 3 y 2 + y 3 ≥ 2 − 3 y 1 + y 2 − 4 y 3 ≥ − 3 5 y 1 + 7 y 2 − 6 y 3 ≥ 4 y j ≥ 0 ( j = 1 , 2 , 3 ) \begin{array}{lcl} minW = -2y_1 + 3y_2 - 5y_3 \\\\ s.t\begin{cases} -2y_1 + 3y_2 + y_3 \geq 2 \\\\ -3y_1 + y_2 - 4y_3 \geq -3 \\\\ 5y_1 + 7y_2 - 6y_3 \geq 4 \\\\ y_j \geq 0 \quad ( j = 1, 2, 3 ) \end{cases}\end{array} minW=−2y1​+3y2​−5y3​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​−2y1​+3y2​+y3​≥2−3y1​+y2​−4y3​≥−35y1​+7y2​−6y3​≥4yj​≥0(j=1,2,3)​​

原问题 与 对偶问题线性规划分析 :

上述对偶问题线性规划 , 与原问题线性规划 , 明显不互为转置矩阵 ;

原问题线性规划系数为 ( 2 3 − 5 3 1 7 − 1 4 6 ) \begin{pmatrix} &2 & 3 & -5 & \\ &3 & 1 & 7 & \\ &-1 & 4 & 6 & \\ \end{pmatrix} ⎝⎛​​23−1​314​−576​​⎠⎞​ , 对偶问题线性规划系数为 ( − 2 3 1 − 3 1 − 4 5 7 − 6 ) \begin{pmatrix} &-2 & 3 & 1 & \\ &-3 & 1 & -4 & \\ &5 & 7 & -6 & \\ \end{pmatrix} ⎝⎛​​−2−35​317​1−4−6​​⎠⎞​ , 原问题的转置矩阵应该是 ( 2 3 − 1 3 1 4 − 5 7 6 ) \begin{pmatrix} &2 & 3 & -1 & \\ &3 & 1 & 4 & \\ &-5 & 7 & 6 & \\ \end{pmatrix} ⎝⎛​​23−5​317​−146​​⎠⎞​ , y 1 , y 3 y_1 , y_3 y1​,y3​ 系数的正负号与原问题的转置矩阵值的符号相反 ;

令 y 1 ′ = − y 1 y_1' = -y_1 y1′​=−y1​ , y 3 ′ = − y 3 y_3' = -y_3 y3′​=−y3​ , 则得到如下线性规划 :

m i n W = 2 y 1 ′ + 3 y 2 + 5 y 3 ′ s . t { 2 y 1 ′ + 3 y 2 − y 3 ′ ≥ 2 3 y 1 ′ + y 2 + 4 y 3 ′ ≥ − 3 − 5 y 1 ′ + 7 y 2 + 6 y 3 ′ ≥ 4 y 1 ′ ≤ 0 , y 2 ≥ 0 , y 3 ′ ≤ 0 \begin{array}{lcl} minW = 2y_1' + 3y_2 + 5y_3' \\\\ s.t\begin{cases} 2y_1' + 3y_2 - y_3' \geq 2 \\\\ 3y_1' + y_2 + 4y_3' \geq -3 \\\\ -5y_1' + 7y_2 + 6y_3' \geq 4 \\\\ y_1' \leq 0 , y_2 \geq 0 , y_3' \leq 0 \end{cases}\end{array} minW=2y1′​+3y2​+5y3′​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​2y1′​+3y2​−y3′​≥23y1′​+y2​+4y3′​≥−3−5y1′​+7y2​+6y3′​≥4y1′​≤0,y2​≥0,y3′​≤0​​

上图中的对偶问题线性规划 ( D P \rm DP DP ) 中的目标函数 y 3 ′ y_3' y3′​ 的系数应该是 + 5 +5 +5 , 这里在符号转换 y ′ = − y y' = -y y′=−y 时 , 将符合写错了 ;

参考博客 : 【运筹学】对偶理论 : 弱对偶性质 ( 弱对偶原理 | 弱对偶性 | 推论 1 | 推论 2 对偶问题的无界性 | 推论 3 )

弱对偶定理 :

假设 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=1n​cj​xj​≤∑i=1m​yi​bi​

弱对偶定理推论 1 :

原问题 任何一个 可行解 的目标函数值 , 都是其对偶问题 目标函数值的下界 ;

反之 ,

对偶问题 任何一个 可行解 的目标函数值 , 都是其原问题 目标函数的上界 ;

弱对偶定理推论 2 : ( 对偶问题的无界性 )

在一对 对偶问题 ( P ) \rm (P) (P) 和 ( D ) \rm (D) (D) 中 ,

如果其中 一个线性规划问题可行 , 但是 目标函数无界 , 则 另外一个问题没有可行解 ;

如果其中 一个线性规划问题不可行 , 其 对偶问题不一定不可行 ;

弱对偶定理推论 3 :

在一对 对偶问题 ( P ) \rm (P) (P) 和 ( D ) \rm (D) (D) 中 ,

如果其中 一个线性规划问题可行 , 而 另一个线性规划问题不可行 , 则 该可行问题的目标函数是无界的;

最优性定理 :

如果 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 是对偶问题的最优解 ;

两个互为对偶的线性规划问题 , 只要有一个有最优解 , 另一个也有最优解 ;

最优解 首先是可行解 , 其次该可行解使目标函数达到最优 ( 最小值 / 最大值 ) ;

互为对偶的两个问题 :

原问题的目标函数求最大值 , 该值不断增大 , 处于一个界限值下方 ; 其最大值就是界限值 ;

对偶问题的目标函数求最小值 , 该值不断减小 , 处于一个界限值上方 ; 其最小值就是界限值 ;

当上述 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 , 则说明 C X 0 = B Y 0 = 界 限 值 \rm CX^0 = BY^0 = 界限值 CX0=BY0=界限值 , 当前的目标函数值就是界限值 ;

该界限值就是 原问题 目标函数的最大值 , 同时也是 对偶问题目标函数的最小值 ;

强对偶性 : 如果 原问题 与 对偶问题 都有可行解 , 只要有一个问题有最优解 , 则 两个问题都有最优解 , 二者的最优解的目标函数值相等 ;

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 = 3 x 1 + 4 x 2 + x 3 { x 1 + 2 x 2 + x 3 ≤ 10 2 x 1 + 2 x 2 + x 3 ≤ 16 x 1 , x 2 , x 3 ≥ 0 \begin{array}{lcl} \rm maxZ = 3x_1 + 4x_2 + x_3 \\\\ \rm \begin{cases} \rm x_1 + 2x_2 + x_3 \leq 10 \\\\ \rm 2x_1 + 2x_2 + x_3 \leq 16 \\\\ \rm x_1,x_2, x_3 \geq 0 \end{cases}\end{array} maxZ=3x1​+4x2​+x3​⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​x1​+2x2​+x3​≤102x1​+2x2​+x3​≤16x1​,x2​,x3​≥0​​

上述线性规划的最优解是 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620​) , 求其对偶问题最优解 ;

方法一 : 写出上述线性规划的对偶问题 , 然后使用单纯形法求最优解 ,

首先写出 对偶问题 , 然后转为 标准形式 , 找 单位阵 作为基矩阵 , 然后得到基变量 , 假设非基变量为 0 0 0 求出 基解 ,

在单纯形表中计算 检验数 , 如果 检验数都小于 0 0 0 就是最优解 , 如果检验数都大于 0 0 0 , 则不是最优解 ;

根据检验数确定 出基变量 , 然后计算出 入基变量 , 进行下一次迭代 ;

方程组 同解变换, 构造单位阵 , 然后计算检验数 , 继续按照上述方法进行迭代 ;

该方法比较麻烦 ;

方法二 : 利用 互补松弛定理 计算 ;

写出原问题的对偶问题 :

m i n W = 10 y 1 + 16 y 2 { y 1 + 2 y 2 ≥ 3 2 y 1 + 2 y 2 ≥ 4 y 1 + y 2 ≥ 1 y 1 , y 2 ≥ 0 \begin{array}{lcl} \rm minW = 10y_1 + 16y_2 \\\\ \rm \begin{cases} \rm y_1 + 2y_2 \geq 3 \\\\ \rm 2y_1 + 2y_2 \geq 4 \\\\ \rm y_1 + y_2 \geq 1 \\\\ \rm y_1,y_2 \geq 0 \end{cases}\end{array} minW=10y1​+16y2​⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​y1​+2y2​≥32y1​+2y2​≥4y1​+y2​≥1y1​,y2​≥0​​

给对偶问题的约束方程添加剩余变量 :

{ y 1 + 2 y 2 − y 3 = 3 2 y 1 + 2 y 2 − y 4 = 4 y 1 + y 2 − y 5 = 1 y 1 , y 2 , y 3 , y 4 , y 5 ≥ 0 \begin{cases} \rm y_1 + 2y_2 - y_3 = 3 \\\\ \rm 2y_1 + 2y_2 - y_4 = 4 \\\\ \rm y_1 + y_2 - y_5 = 1 \\\\ \rm y_1,y_2, y_3 , y _4, y_5 \geq 0 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​y1​+2y2​−y3​=32y1​+2y2​−y4​=4y1​+y2​−y5​=1y1​,y2​,y3​,y4​,y5​≥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​=0Ys​X0=0​

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

原问题 P \rm P P 线性规划最优解是 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620​) ,

对偶问题的剩余变量是 Y s = ( y 3 y 4 y 5 ) \rm Y_s= \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix} Ys​=⎝⎜⎜⎜⎜⎛​y3​y4​y5​​⎠⎟⎟⎟⎟⎞​

互补松弛定理中 Y s X 0 = 0 \rm Y_sX^0 = 0 Ys​X0=0 , 将上述 X 0 \rm X^0 X0 和 Y s \rm Y_s Ys​ 代入上述式子得到 :

Y s X 0 = ( 6 2 0 ) × ( y 3 y 4 y 5 ) = 6 y 3 + 2 y 4 + 0 y 5 = 6 y 3 + 2 y 4 = 0 \rm Y_sX^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} \times \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix} = 6y_3 + 2y_4 + 0y_5 = 6y_3 + 2y_4 =0 Ys​X0=(620​)×⎝⎜⎜⎜⎜⎛​y3​y4​y5​​⎠⎟⎟⎟⎟⎞​=6y3​+2y4​+0y5​=6y3​+2y4​=0

已知 y 3 , y 4 ≥ 0 \rm y_3, y_4 \geq 0 y3​,y4​≥0 , 上述 6 y 3 + 2 y 4 = 0 \rm 6y_3 + 2y_4 = 0 6y3​+2y4​=0 , 因此 y 3 = 0 , y 4 = 0 \rm y_3 = 0 , y_4 = 0 y3​=0,y4​=0 ;

将 y 3 = 0 , y 4 = 0 \rm y_3 = 0 , y_4 = 0 y3​=0,y4​=0 代入到约束方程 { y 1 + 2 y 2 − y 3 = 3 2 y 1 + 2 y 2 − y 4 = 4 y 1 + y 2 − y 5 = 1 y 1 , y 2 , y 3 , y 4 , y 5 ≥ 0 \begin{cases} \rm y_1 + 2y_2 - y_3 = 3 \\\\ \rm 2y_1 + 2y_2 - y_4 = 4 \\\\ \rm y_1 + y_2 - y_5 = 1 \\\\ \rm y_1,y_2, y_3 , y _4, y_5 \geq 0 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​y1​+2y2​−y3​=32y1​+2y2​−y4​=4y1​+y2​−y5​=1y1​,y2​,y3​,y4​,y5​≥0​ 中 ;

得到 { y 1 + 2 y 2 = 3 2 y 1 + 2 y 2 = 4 \begin{cases} \rm y_1 + 2y_2 = 3 \\\\ \rm 2y_1 + 2y_2 = 4 \end{cases} ⎩⎪⎨⎪⎧​y1​+2y2​=32y1​+2y2​=4​ , 解上述方程 ,

① 变换 : { 2 y 1 + 4 y 2 = 6 2 y 1 + 2 y 2 = 4 \begin{cases} \rm 2y_1 + 4y_2 = 6 \\\\ \rm 2y_1 + 2y_2 = 4 \end{cases} ⎩⎪⎨⎪⎧​2y1​+4y2​=62y1​+2y2​=4​

② 求解 : { y 1 = 1 y 2 = 1 \begin{cases} \rm y_1 = 1 \\\\ \rm y_2 = 1 \end{cases} ⎩⎪⎨⎪⎧​y1​=1y2​=1​

上述求出的值就是最优解 , 即 Y 0 = ( 1 1 ) \rm Y^0 = \begin{pmatrix} \quad \rm 1 \quad 1 \quad \end{pmatrix} Y0=(11​) ;

互补松弛定理 :

" 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​=0Ys​X0=0​

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

原问题 P \rm P P 线性规划最优解是 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620​) ,

对偶问题的剩余变量是 Y s = ( y 3 y 4 y 5 ) \rm Y_s= \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix} Ys​=⎝⎜⎜⎜⎜⎛​y3​y4​y5​​⎠⎟⎟⎟⎟⎞​

最优解中不等于 0 0 0 的 , 对应的剩余变量中对应的一定为 0 0 0 ,

如果最优解中等于 0 0 0 , 那么剩余变量中的对应的值就不确定了 ;

已知原问题最优解求对偶问题最优解 , 已知线性规划 :

m i n W = 2 x 1 − x 2 + 2 x 3 { − x 1 + x 2 + x 3 = 4 − x 1 + x 2 − x 3 ≤ 6 x 1 ≤ 0 , x 2 ≥ 0 , x 3 无 约 束 \begin{array}{lcl} \rm minW= 2x_1 - x_2 + 2x_3 \\\\ \rm \begin{cases} \rm -x_1 + x_2 + x_3 = 4 \\\\ \rm -x_1 + x_2 - x_3 \leq 6 \\\\ \rm x_1 \leq 0 ,x_2 \geq 0 , x_3 无约束 \end{cases}\end{array} minW=2x1​−x2​+2x3​⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​−x1​+x2​+x3​=4−x1​+x2​−x3​≤6x1​≤0,x2​≥0,x3​无约束​​

上述线性规划的对偶问题的最优解是 Y 0 = ( 0 − 2 ) \rm Y^0 = \begin{pmatrix} \quad \rm 0 \quad \rm -2 \quad \end{pmatrix} Y0=(0−2​) , 求其原问题最优解 ;

互补松弛定理 :

" 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​=0Ys​X0=0​

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

分析 :

给出了对偶问题最优解 Y 0 = ( 0 − 2 ) \rm Y^0 = \begin{pmatrix} \quad \rm 0 \quad \rm -2 \quad \end{pmatrix} Y0=(0−2​) , 其互补松弛定理中对应原问题的松弛变量 X s = ( x 4 x 5 ) \rm X_s =\begin{pmatrix} \quad \rm x_4 \quad \\\\ \quad \rm x_5 \quad \end{pmatrix} Xs​=⎝⎛​x4​x5​​⎠⎞​ ;

根据公式有 ( 0 − 2 ) × ( x 4 x 5 ) = 0 \rm \begin{pmatrix} \quad \rm 0 \quad \rm -2 \quad \end{pmatrix} \times \begin{pmatrix} \quad \rm x_4 \quad \\\\ \quad \rm x_5 \quad \end{pmatrix} = 0 (0−2​)×⎝⎛​x4​x5​​⎠⎞​=0 0 x 4 − 2 x 5 = 0 \rm 0 x_4 - 2x_5= 0 0x4​−2x5​=0

− 2 x 5 = 0 \rm - 2x_5= 0 −2x5​=0

原问题添加松弛变量 ,

− x 1 + x 2 + x 3 = 4 \rm -x_1 + x_2 + x_3 = 4 −x1​+x2​+x3​=4 已经是等式了 , 添加一个 x 4 \rm x_4 x4​ 松弛变量 , x 4 = 0 \rm x_4 = 0 x4​=0 ,

− x 1 + x 2 − x 3 ≤ 6 \rm -x_1 + x_2 - x_3 \leq 6 −x1​+x2​−x3​≤6 添加松弛变量 x 5 \rm x_5 x5​ , 由于对应的最优解不为 0 0 0 , 是 − 2 -2 −2 , 其对应的松弛变量还是 0 0 0 , 即 x 5 = 0 x_5 = 0 x5​=0 ;

原问题的最优解满足 { − x 1 + x 2 + x 3 = 4 − x 1 + x 2 − x 3 = 6 \begin{cases} \rm -x_1 + x_2 + x_3 = 4 \\\\ \rm -x_1 + x_2 - x_3 = 6 \end{cases} ⎩⎪⎨⎪⎧​−x1​+x2​+x3​=4−x1​+x2​−x3​=6​ 方程 , 该方程组 2 2 2 个等式 , 3 3 3 个变量 , 如果再得到一个方程 , 就可以得到三个方程 ;

根据 对偶理论中的 强对偶性 , 如果 原问题 与 对偶问题 都有可行解 , 只要有一个问题有最优解 , 则 两个问题都有最优解 , 二者的最优解的目标函数值相等 ;

这里求一下对偶问题的目标函数值 , 对偶问题的目标函数与原问题的目标函数值相等 ;

对偶问题的目标函数是 m a x Z = 4 y 1 + 6 y 2 = 4 × 0 − 2 × 6 = − 12 \rm max Z = 4y_1 + 6y_2 = 4 \times 0 - 2 \times 6 = -12 maxZ=4y1​+6y2​=4×0−2×6=−12 ;

因此原问题的目标函数值也是 12 12 12 , 得到式子 m i n W = 2 x 1 − x 2 + 2 x 3 = − 12 \rm minW= 2x_1 - x_2 + 2x_3 = -12 minW=2x1​−x2​+2x3​=−12 ;

这里就得到了 3 3 3 个方程组 , 3 3 3 个变量 , 求解下面的方程组 , 最终结果就是最优解 ;

{ − x 1 + x 2 + x 3 = 4    ① − x 1 + x 2 − x 3 = 6    ② 2 x 1 − x 2 + 2 x 3 = − 12    ③ \begin{cases} \rm -x_1 + x_2 + x_3 = 4 \ \ ① \\\\ \rm -x_1 + x_2 - x_3 = 6 \ \ ② \\\\ 2x_1 - x_2 + 2x_3 = -12 \ \ ③ \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​−x1​+x2​+x3​=4  ①−x1​+x2​−x3​=6  ②2x1​−x2​+2x3​=−12  ③​

最终方程组的解是 :

{ x 1 = − 5 x 2 = 0 x 3 = − 1 \begin{cases} \rm x_1 = -5 \\\\ \rm x_2 = 0 \\\\ x_3 = -1 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​x1​=−5x2​=0x3​=−1​

最终的原方程的最优解是 ( − 5 0 − 1 ) \begin{pmatrix} \quad \rm -5 \quad 0 \quad \rm -1 \quad \end{pmatrix} (−50−1​)

目标函数值是 − 12 -12 −12

给定线性规划 , 给定一个问题的最优解 , 求另一个问题的最优解 ;

互补松弛定理 :

" 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​=0Ys​X0=0​

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

使用上述互补松弛定理 , 求出 给定的最优解 对应的对偶问题线性规划 松弛变量的值 ;

将 松弛变量 代入到 约束方程等式 中 , 求解出的值就是线性规划问题的最优解 ;

还有一种方式 , 就是根据给定的最优解 , 求出 本问题线性规划的 松弛变量值 ,

根据 本问题的松弛变量值 求对应 对偶问题的 最优解 ;

原问题与对偶问题对应关系 :

如果 原问题 有最优解 , 对偶问题也 有最优解 ;

如果 原问题 有 无界解 , 对偶问题 无可行解 ;

如果 原问题 无可行解 , 对偶问题 无法判断 ;

上述是根据弱对偶定理总结的 ;

任何 线性规划问题 , 都有一个对应的 对偶线性规划问题 ;

原问题 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 ≥ , 因此 对偶问题的变量符号 与 原问题约束方程符号 符号一致 ;

① 互为对偶的两个问题 , 或者同时都有最优解 , 或者同时都没有最优解 ;

② 对偶问题 有可行解 , 原问题 不一定有可行解 , 因为对偶问题的可行解可能是 无界解 , 原问题可能 无可行解 ;

③ 原问题有 多重解 , 对偶问题 可能有多重解 , 也 可能有唯一解 ; 多重解是 有无穷多最优解 ;

④ 对偶问题 有可行解 , 原问题 无可行解 , 则对偶问题 有无界解 ; 一对问题中 , 一个有可行解 , 一个无可行解 , 则有可行解的是无界解 ;

⑤ 原问题 没有最优解 , 对偶问题无法判断 ; 没有最优解有两种情况 , 一种是 无界解 , 一种是 无可行解 ; 如果原问题有无界解 , 则对偶问题无可行解 ; 如果原问题无可行解 , 则对偶问题无可行解 ;

⑥ 如果对偶问题没有可行解 , 对偶问题无法判断 , 无界解 或 无可行解 两种情况都有可能 ;

⑦ 如果原问题与对偶问题 都有可行解 , 则 都有最优解 ;

如果 原问题 有最优解 , 对偶问题也 有最优解 ;

如果 原问题 有 无界解 , 对偶问题 无可行解 ;

如果 原问题 无可行解 , 对偶问题 无法判断 ;

如果 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​=Ys​X0=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​=0Ys​X0=0​

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