【运筹学】对偶理论 : 互补松弛定理应用 ( 原问题与对偶问题标准形式 | 已知原问题最优解求对偶问题最优解 | 使用单纯形法求解 | 使用互补松弛定理公式一求解 | 互补松弛定理公式二无效 ) ★★

一、原问题与对偶问题标准形式

原问题 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​​

等价方法 :

• 生产 : 目标函数追求 利润最大化 , 约束方程设备的使用时长受约束 , 小于等于 某个时间值 ;
• 出租设备 : 目标函数追求 租金最小化 , 约束方程设备产生的利润要 大于等于 生产的利润 , 不能亏钱 ;

二、互补松弛定理

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​ 是 松弛变量 或 剩余变量 ;

上面 " 五、使用互补松弛定理公式一求解 " 小节 使用的是 Y s X 0 = 0 \rm Y_sX^0 = 0 Ys​X0=0 公式进行求解 , 在本小节中使用 Y 0 X s = 0 \rm Y^0 X_s = 0 Y0Xs​=0 公式进行求解 ;

原问题 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​) , 将该最优解代入原问题的约束条件中 , 求出原问题的约束变量 X s \rm X_s Xs​ ;

原问题 :

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

原问题添加松弛变量后 :

m a x Z = 3 x 1 + 4 x 2 + x 3 { x 1 + 2 x 2 + x 3 + x 4 = 10 2 x 1 + 2 x 2 + x 3 + x 5 = 16 x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0 \begin{array}{lcl} \rm maxZ = 3x_1 + 4x_2 + x_3 \\\\ \rm \begin{cases} \rm x_1 + 2x_2 + x_3 + x_4 = 10 \\\\ \rm 2x_1 + 2x_2 + x_3 + x_5 =16 \\\\ \rm x_1,x_2, x_3, x_4 , x_5 \geq 0 \end{cases}\end{array} maxZ=3x1​+4x2​+x3​⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​x1​+2x2​+x3​+x4​=102x1​+2x2​+x3​+x5​=16x1​,x2​,x3​,x4​,x5​≥0​​

将最优解 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620​) 代入原问题 :

{ 6 + 2 × 2 + 0 + x 4 = 10 2 × 6 + 2 × 2 + 0 + x 5 = 16 \begin{cases} \rm 6 + 2\times 2 + 0 + x_4 = 10 \\\\ \rm 2 \times 6 + 2 \times 2 + 0 + x_5 = 16 \end{cases} ⎩⎪⎨⎪⎧​6+2×2+0+x4​=102×6+2×2+0+x5​=16​

得到 : { x 4 = 0 x 5 = 10 \begin{cases} \rm x_4 = 0 \\\\ \rm x_5 = 10 \end{cases} ⎩⎪⎨⎪⎧​x4​=0x5​=10​

X s = ( 0 0 ) \rm X_s = \begin{pmatrix} \quad \rm 0 \quad \\\\ \quad \rm 0 \quad \end{pmatrix} Xs​=⎝⎛​00​⎠⎞​

这个信息是无用的 , 根据这个 X s \rm X_s Xs​ 乘以任意的 Y 0 \rm Y^0 Y0 值都是 0 0 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​​⎠⎟⎟⎟⎟⎞​

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

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