【运筹学】对偶理论 : 互补松弛性 ( 原问题与对偶问题标准形式 | 互补松弛定理 | 互补松弛定理示例说明 )

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

原问题 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 = 2 x 1 + 3 x 2 s . t { 2 x 1 + 2 x 2 ≤ 12 x 1 + 2 x 2 ≤ 8 4 x 1 ≤ 16 4 x 2 ≤ 12 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm maxZ = 2x_1 + 3x_2 \\\\ \rm s.t\begin{cases} \rm 2 x_1 + 2x_2 \leq 12 \\\\ \rm x_1 + 2x_2 \leq 8 \\\\ \rm 4 x_1 \leq 16 \\\\ \rm 4x_2 \leq 12 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} maxZ=2x1​+3x2​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​2x1​+2x2​≤12x1​+2x2​≤84x1​≤164x2​≤12x1​,x2​≥0​​

上述线性规划的最优解是 : ( 4 2 ) \begin{pmatrix} \quad \rm 4 \quad 2 \quad \\ \end{pmatrix} (42​) ;

甲产品生产 4 4 4 个单位 , 乙产品生产 2 2 2 个单位 ;

设备出租问题 ( 对偶问题 ) :

m i n W = 12 y 1 + 8 y 2 + 16 y 3 + 12 y 4 s . t { 2 y 1 + y 2 + 4 y 3 + 0 y 4 ≥ 2 2 y 1 + 2 y 2 + 0 y 3 + 4 y 4 ≥ 3 y 1 , y 2 , y 3 , y 4 ≥ 0 \begin{array}{lcl} \rm minW = 12y_1 + 8y_2 + 16y_3 + 12y_4 \\\\ \rm s.t\begin{cases} \rm 2 y_1 + y_2 + 4y_3 + 0y_4 \geq 2 \\\\ \rm 2 y_1 + 2y_2 + 0y_3 + 4y_4 \geq 3 \\\\ \rm y_1, y_2 , y_3 , y _4 \geq 0 \end{cases}\end{array} minW=12y1​+8y2​+16y3​+12y4​s.t⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​2y1​+y2​+4y3​+0y4​≥22y1​+2y2​+0y3​+4y4​≥3y1​,y2​,y3​,y4​≥0​​

上述线性规划最优解是 : ( 1 2 1 0 0 ) \begin{pmatrix} \quad \rm \cfrac{1}{2} \quad 1 \quad 0 \quad 0 \quad \\ \end{pmatrix} (21​100​) , 或 ( 0 2 3 1 8 0 ) \begin{pmatrix} \quad \rm 0 \quad \cfrac{2}{3} \quad \cfrac{1}{8} \quad 0 \quad \\ \end{pmatrix} (032​81​0​)

将上面两个线性规划的最优解代入目标函数 , 得到的值都是 14 14 14 ;

互补松弛定理 :

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

( 4 2 ) \begin{pmatrix} \quad \rm 4 \quad 2 \quad \\ \end{pmatrix} (42​) 是原问题 P \rm P P 的最优解 , 是 X 0 \rm X^0 X0 ,

Y s \rm Y_s Ys​ 是对偶问题 D \rm D D 的剩余变量 , { 2 y 1 + y 2 + 4 y 3 + 0 y 4 − y 5 = 2 2 y 1 + 2 y 2 + 0 y 3 + 4 y 4 − y 6 = 3 \begin{cases} \rm 2 y_1 + y_2 + 4y_3 + 0y_4 - y_5 = 2 \\\\ \rm 2 y_1 + 2y_2 + 0y_3 + 4y_4 - y_6 = 3 \end{cases} ⎩⎪⎨⎪⎧​2y1​+y2​+4y3​+0y4​−y5​=22y1​+2y2​+0y3​+4y4​−y6​=3​ , 两个剩余变量是 ( y 5 y 6 ) \begin{pmatrix} \quad \rm y_5 \quad \\ \quad \rm y_6 \quad \\ \end{pmatrix} (y5​y6​​) , 是 Y s \rm Y_s Ys​ ,

根据互补松弛定理 , Y s X 0 = 0 \rm Y_sX^0 = 0 Ys​X0=0 , 将真实值代入 :

Y s X 0 = ( 4 2 ) × ( y 5 y 6 ) = 4 y 5 + 2 y 6 = 0 \rm Y_sX^0 = \begin{pmatrix} \quad \rm 4 \quad 2 \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad \rm y_5 \quad \\ \quad \rm y_6 \quad \\ \end{pmatrix} =4 y_5 + 2y_6 = 0 Ys​X0=(42​)×(y5​y6​​)=4y5​+2y6​=0

y 5 , y 6 \rm y_5 , y_6 y5​,y6​ 都是大于等于 0 0 0 的 , 如果要满足 4 y 5 + 2 y 6 = 0 \rm 4 y_5 + 2y_6 = 0 4y5​+2y6​=0 , 则得到 y 5 = 0 , y 6 = 0 \rm y_5 = 0, y_6 = 0 y5​=0,y6​=0 结论 ;