线性规划对偶问题：理论推导和实际应用

之前在很多地方，都看到过“对偶”这两个字眼，总觉得这个词很高大上。对偶理论的百度百科中甚至写到：“在线性规划早期发展中最重要的发现是对偶问题”。所以，既然已经到了线性规划这里，那对偶问题自然也值得深入学习一下。

大概了解了一下网上关于对偶问题的介绍，差不多可以分为两类：一类是直接介绍线性规划对偶问题，另一类是从拉格朗日对偶问题开始，然后再表达线性规划作为一种特殊的优化问题，有着特殊的性质。鉴于这段时间都是线性规划方面的内容，个人觉得还是第一类比较适合我。

先举个例子，来直观认识一下对偶问题。

家具公司A生产书桌、餐桌和椅子。每种家具的生产都需要木材和两种熟练劳动：抛光和木工。制作每种家具所需的各种资源的数量、可用资源量以及每种家具的售价如下表所示。

求该公司应如何安排生产，才能使得收入最大化。

该问题的求解并不困难。设书桌的产量为 x 1 x_1 x1​，餐桌的产量为 x 2 x_2 x2​，椅子的产量为 x 3 x_3 x3​，此时模型可以描述为 m a x f = 600 x 1 + 300 x 2 + 200 x 3 s.t 8 x 1 + 6 x 2 + x 3 ≤ 48 4 x 1 + 2 x 2 + 1.5 x 3 ≤ 20 2 x 1 + 1.5 x 2 + 0.5 x 3 ≤ 8 x 1 , x 2 , x 3 ≥ 0 , 且取整数 max \quad f=600x_1+300x_2+200x_3 \\ \text{s.t} \quad 8x_1+6x_2+x_3≤48 \\\nonumber \quad \quad \quad4x_1+2x_2+1.5x_3≤20\\\nonumber \quad\quad\quad 2x_1+1.5x_2+0.5x_3≤8\\\nonumber \quad\quad\quad x_1,x_2,x_3≥0,且取整数\\ maxf=600x1​+300x2​+200x3​s.t8x1​+6x2​+x3​≤484x1​+2x2​+1.5x3​≤202x1​+1.5x2​+0.5x3​≤8x1​,x2​,x3​≥0,且取整数 显然该问题是个整数规划问题，我们使用ortools求解，代码如下

运行代码，可以得到最优解如下

对比一下原问题和对偶问题的最优解，我们发现一个有趣的现象 f ∗ = z ∗ f^{\ast}=z^{\ast} f∗=z∗ 即，原问题和对偶问题的最优目标函数值相等。事实上，这并不是特例，只是线性规划对偶问题的性质之一。

上一章的实例让我们对对偶问题有了一些直观的认知，本节通过一些偏理论的推导，来研究清楚线性规划中对偶问题和原问题之间具有怎样的关系和性质。

回顾一下线性规划的标准型 m i n f ( x ) = c T x s.t A x = b x ≥ 0 min \quad f(\pmb x)=\pmb c^T\pmb x \\ \text{s.t} \quad \pmb A\pmb x=\pmb b \\\nonumber \quad \quad \pmb x ≥ 0\\ minf(x)=cTxs.tAx=bx≥0

在推导单纯形法时，有如下的公式 f = c B T B − 1 b − ( c B T B − 1 N − c N T ) x N f=\pmb c_B^T\pmb B^{-1}\pmb b-(\pmb c_B^T\pmb B^{-1}\pmb N-\pmb c_N^T)\pmb x_N f=cBT​B−1b−(cBT​B−1N−cNT​)xN​ 定义 R = c B T B − 1 N − c N T \pmb R=\pmb c_B^T\pmb B^{-1}\pmb N-\pmb c_N^T R=cBT​B−1N−cNT​ 如果线性规划已经达到最优解，则 R ≤ 0 \pmb R≤\pmb 0 R≤0。此时，令 w T = c B T B − 1 \pmb w^T = \pmb c_B^T\pmb B^{-1} wT=cBT​B−1，上式可以写为 w T N ≤ c N T w^T\pmb N≤\pmb c_N^T wTN≤cNT​ 再看一下 w T B \pmb w^T\pmb B wTB项 w T B = c B T B − 1 B = c B T \pmb w^T\pmb B=\pmb c_B^T\pmb B^{-1} \pmb B=\pmb c_B^T wTB=cBT​B−1B=cBT​ 因为 A = [ B , N ] \pmb A=[\pmb B,\pmb N] A=[B,N]，结合上述两式，可以得到 w T A ≤ c T \pmb w^T\pmb A≤\pmb c^T wTA≤cT 加个转置，得到 A T w ≤ c A^T \pmb w ≤ \pmb c ATw≤c

再看另一组推导 w T b = w T A x ≤ c T x \pmb w^T \pmb b=\pmb w^T \pmb A \pmb x≤\pmb c^T\pmb x wTb=wTAx≤cTx

基于上面两个公式，如果我们把 w \pmb w w作为变量，可以构建出一个新的优化问题 m a x b T w s.t A T w ≤ c max \quad \pmb b^T\pmb w \\ \text{s.t} \quad \pmb A^T\pmb w≤\pmb c maxbTws.tATw≤c

该优化问题就是原线性规划问题的对偶问题。对照原问题看， A , b \pmb A,\pmb b A,b和 c \pmb c c都还在，只是换了位置；同时 x ≥ 0 \pmb x≥0 x≥0但是 w \pmb w w没有约束。

对偶问题既然可以从原问题推导而来，他们之间自然也存在一些相互关系。

个人看来，最基本的关系应该就是弱对偶定理了：若 x \pmb x x是原问题的可行解， w \pmb w w是对偶问题的可行解，则有 c T x ≥ b T w \pmb c^T\pmb x ≥ \pmb b^T \pmb w cTx≥bTw。

该定理从刚刚的推演中，其实已经证明了，这里通过如下的过程再描述一遍 c T x = x T c ≥ x T A T w = b T w \pmb c^T\pmb x = \pmb x^T\pmb c ≥ \pmb x^T\pmb A^T\pmb w=\pmb b^T \pmb w cTx=xTc≥xTATw=bTw

基于弱对偶定理可以得到一个推论：若 x ∗ \pmb x^\ast x∗是原问题的可行解， w ∗ \pmb w^\ast w∗是对偶问题的可行解，且有 c T x ∗ = b T w ∗ \pmb c^T\pmb x^\ast=\pmb b^T\pmb w^\ast cTx∗=bTw∗，则 x ∗ \pmb x^\ast x∗是原问题的最优解， w ∗ \pmb w^\ast w∗是对偶问题的最优解。

由弱对偶定理可知 c T x ≥ b T w ∗ \pmb c^T\pmb x≥\pmb b^T\pmb w^\ast cTx≥bTw∗ 同时 c T x ∗ = b T w ∗ \pmb c^T\pmb x^\ast=\pmb b^T\pmb w^\ast cTx∗=bTw∗ 所以 x ∗ \pmb x^\ast x∗是原问题的最优解。

同样的方法，可以证明， w ∗ \pmb w^\ast w∗是对偶问题的最优解。

最后是实际应用中最重要的强对偶定理：若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。

假设原问题最优解为 x ∗ \pmb x^\ast x∗，对偶变量 w T = c B T B − 1 \pmb w^T = \pmb c_B^T\pmb B^{-1} wT=cBT​B−1。因为 x ∗ \pmb x^\ast x∗是最优解，所以 R = A T w − c ≤ 0 \pmb R=\pmb A^T\pmb w-\pmb c≤0 R=ATw−c≤0 所以 w \pmb w w是对偶问题的可行解。同时 x \pmb x x是一个基本可行解，可做如下推演 c T x = c B T x B = c B T B − 1 b = w T b = b T w \pmb c^T\pmb x=\pmb c_B^T\pmb x_B=\pmb c_B^T\pmb B^{-1}\pmb b=\pmb w^T\pmb b=\pmb b^T\pmb w cTx=cBT​xB​=cBT​B−1b=wTb=bTw 结合之前的推论可知， w \pmb w w是对偶问题的最优解。

对偶问题的应用是非常多的，不过大部分都是用于理论推导和证明的，在实际应用中比较常见的是影子价格。

根据强对偶定理，原问题和对偶问题同时有最优解时，两者的目标函数值相等，即 f = c T x ∗ = z = b T w ∗ f=\pmb c^T\pmb x^\ast=z=\pmb b^T\pmb w^\ast f=cTx∗=z=bTw∗ 写成分量的形式 f = w 1 ∗ b 1 + w 2 ∗ b 2 + ⋅ ⋅ ⋅ + w m ∗ b m f=w_1^\ast b_1+w_2^\ast b_2+···+w_m^\ast b_m f=w1∗​b1​+w2∗​b2​+⋅⋅⋅+wm∗​bm​ 对 b i b_i bi​求导 ∂ f ∂ b i = w i ∗ , i = 1 , 2 , ⋅ ⋅ ⋅ , m \frac{\partial f}{\partial b_i}=w_i^\ast, \quad i=1,2,···,m ∂bi​∂f​=wi∗​,i=1,2,⋅⋅⋅,m 右边显然就是我们求解对偶问题时得到的最优解；而左边可以直观理解为目标函数值相对于资源变量的梯度值，该值越小，表明相应资源增加后能够带来的目标函数值的降低幅度越大。

接下来举个实例直观说明一下影子价格的含义。

原问题： m i n f ( x ) = − 5 x 1 − 4 x 2 s.t x 1 + 3 x 2 + x 3 = 90 2 x 1 + x 2 + x 4 = 80 x 1 + x 2 + x 5 = 45 x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0 min \quad f(\pmb x)= -5x_1-4x_2 \\ \text{s.t} \quad x_1+3x_2+x_3=90 \\ \nonumber \quad \quad 2x_1+x_2+x_4=80 \\ \nonumber \quad \quad x_1+x_2+x_5=45 \\ \nonumber \quad \quad \quad x_1,x_2,x_3,x_4,x_5≥0 minf(x)=−5x1​−4x2​s.tx1​+3x2​+x3​=902x1​+x2​+x4​=80x1​+x2​+x5​=45x1​,x2​,x3​,x4​,x5​≥0 调用ortools求解

运行代码后，得到最优解为

对偶问题： m a x z ( w ) = 90 w 1 + 80 w 2 + 45 w 3 s.t w 1 + 2 w 2 + w 3 ≤ − 5 3 w 1 + w 2 + w e 3 ≤ − 4 w 1 , w 2 , w 3 ≤ 0 max \quad z(\pmb w)= 90w_1+80w_2+45w_3 \\ \text{s.t} \quad w_1+2w_2+w_3≤-5 \\ \nonumber \quad \quad 3w_1+w_2+w_e3≤-4 \\ \nonumber w_1,w_2,w_3≤0 maxz(w)=90w1​+80w2​+45w3​s.tw1​+2w2​+w3​≤−53w1​+w2​+we​3≤−4w1​,w2​,w3​≤0 还是调用ortools求解