大规模线性规划的对偶

去年寒假牛牛开始接触精确求解算法，小谷哥给牛牛推荐了一本绝世好书——《运筹优化常用模型、算法及案例实战》（刘兴禄 主编），于是牛牛开始日夜攻读，写了好多篇笔记。这篇笔记也是参（照）考（搬）这本书写的。

1. 原问题与对偶问题的关系

1.1 借助原问题与对偶问题的关系写对偶问题

当原问题不是标准形时，可以借助表4.1写出原问题的对偶，或者可以转成标准形再写对偶。

1.2 使用标准形式写对偶问题

表 4.1用于检查比较方便，但是用于写对偶问题可能有些烦琐。因此，可以首先把原问题全部化成统一的形式。如下：

• （1）\(max\)问题，变量都≥0，约束都≤0 （粗略理解为：资源都是有限的）。

• （2）\(min\)问题，变量都≥0，约束都≥0 （粗略理解为：需求至少要被满足）。

符号说明：

• 原问题有\(n\)个决策变量和\(m\)个约束条件

• \(c\)：目标函数系数向量，为一个\(n\)维列向量，\(c^T=(c_1,c_2,\dots,c_n)\)，\(c\in\mathbb{R^n}\)。\(c^T=\left[\begin{matrix}c^T_B&c^T_N\end{matrix}\right]\)

  • \(c_B\)：目标函数中，基变量的系数向量，为一个列向量

  • \(c_N\)：目标函数中，非基变量的系数向量，为一个列向量

• \(x\)：决策变量向量，是一个\(n\)维列向量，\(x^T=(x_1,x_2,\dots,x_n)\)，\(x\in\mathbb{R^n}\).\(x=\left[\begin{matrix}x_B\\x_N\end{matrix}\right]\)

  • \(x_B\)：基变量，为一个列向量

  • \(x_N\)：非基变量，为一个列向量

• \(A\)：线性规划的约束系数矩阵，\(A\in\mathbb{R^{m×n}}\)。\(A=\left[\begin{matrix}B&N\end{matrix}\right]\)

  • \(B\)：基变量的约束系数矩阵

  • \(N\)：非基变量的约束系数矩阵

• \(b\)：约束条件右端的常数向量，为一个\(m\)维列向量，\(b\in\mathbb{R^m}\)

原问题：

\[max\quad{Z}=c^Tx\tag{1} \]

\[s.t.\quad{Ax}\leq{b}\tag{2} \]

\[\quad\quad{x}\geq0\tag{3} \]

对偶问题：

\[min\quad{W}=b^Ty\tag{4} \]

\[s.t.\quad{A^Ty}\geq{c}\tag{5} \]

\[\quad\quad{y}\geq0\tag{6} \]

2. 对偶理论相关的重要定理

首先用矩阵的形式给出线性规划的解的一些重要公式：

\[max\quad{z}=\left[\begin{matrix}c^T_B&c^T_N\end{matrix}\right]\left[\begin{matrix}x_B\\x_N\end{matrix}\right]\tag{7} \]

\[s.t.\quad\left[\begin{matrix}B&N\end{matrix}\right]\left[\begin{matrix}x_B\\x_N\end{matrix}\right]=b\tag{8} \]

对于模型的约束（8），有：

\[Bx_B+Nx_N=b \]

两边左乘\(B^{-1}\)有：

\[B^{-1}Bx_B+B^{-1}Nx_N=B^{-1}b \]

\[x_B=B^{-1}b-B^{-1}Nx_N\tag{9} \]

在解中，令所有非基变量均为\(0\)，即：

\[x_N=0 \]

其中，\(0\)是一个维数为非基变量个数的零向量。因此根据上述表达式，可以得到模型的解。

把（9）代入目标函数中，化简得到：

\[z=c^T_BB^{-1}b+(c^T_N-c^T_BB^{-1}N)x_N\tag{10} \]

在（10）中，\(c^T_N-c^T_BB^{-1}N\)就是检验数（reduced cost）

• 具体由来可以看单纯形法的推导

然后考虑下面的原问题和对偶问题：

其中，\(c,y,x\)均是列向量。并且在任一次的单纯形表迭代中，单纯形表的第0行 (row 0) 都是下面的形式。

在原问题中，检验数\(\sigma_j=c_j-z_j=c_j-\sum^m_{i=1}c_ia_{ij}\)，\(j\)代表第\(j\)个决策变量。\(i\)代表第\(i\)个基变量（也可以理解为第\(i\)条约束条件），原问题中共有\(m\)个基变量

需要明确一下几点对应关系：

• 1. 变量\(x_j\)的检验数\(reduced\,cost_j\)和raw 0中信息的对应关系为：

\[reduced\,cost_j=-(z_j-c_j)\tag{11} \]

• 2. \(z_j-c_j\)的值就对应对偶问题第\(j\)条约束的剩余变量(surplus variable)（或松弛变量(slack variable)，对应min问题）

定理1    弱对偶性(Weak duality property)：如果\(x\)是原问题(最大化问题)的一个可行解，并且\(y\)是对偶问题的一个可行解，则：

\[c^Tx\leq{y^T}b\tag{12} \]

• 证明

  • 原问题约束：\(Ax\leq{b}\)，两边左乘\(y^T\)：\(y^TAx\leq{y^T}b\)

  • 对偶问题约束：\(A^Ty\geq{c}\)，两边取转置：\((A^Ty)^T\geq{c^T}\)，即\(y^TA\geq{c^T}\)；两边右乘\(x\)，得：\(y^TAx\geq{c^T}x\)

  • 所以：\(c^Tx\leq{y^T}b\)

定理2    强对偶性(Strong duality property)：如果\(x^*\)是原问题（最大化问题）的一个最优解，并且\(y^*\)是对偶问题的一个最优解，则：

\[c^Tx^*=(y^*)^Tb\tag{13} \]

• 证明：由(10)得原问题最优值为：\(z=c^T_BB^{-1}b+(c^T_N-c^T_BB^{-1}N)x_N\)

  • 若原问题达到最优，则所有非基变量的检验数都小于等于0，即：\(c^T_N-c^T_BB^{-1}N\leq0\)，也就是\(c^T_BB^{-1}N\geq{c^T_N}\)

  • 又因为\(c^T_BB^{-1}B=c^T_B\)

  • 所以：\(c^T_BB^{-1}\left[\begin{matrix}B&N\end{matrix}\right]=\left[\begin{matrix}c^T_BB^{-1}B&c^T_BB^{-1}N\end{matrix}\right]\geq\left[\begin{matrix}c^T_B&c^T_N\end{matrix}\right]\)

  • 即\(c^T_BB^{-1}A\geq{c^T}\)，等价于\(y^TA\geq{c^T}\)

  • 这说明，当原问题达到最优解时，对应的对偶问题的解\(y^*\)同时是对偶问题的可行解。

• 证明此时原问题的目标函数和对偶问题的目标函数值相同

  • 已知\(z=c^T_BB^{-1}b+(c^T_N-c^T_BB^{-1}N)x_N\)，原问题取得最优解时，非基变量\(x_N\)取\(0\)，因此原问题的目标值为：

\[z_{Primal}=c^T_BB^{-1}b=y^Tb=z_{Dual} \]

• 综上：

  • 原问题取得最优解时，对应的对偶问题的解是可行解

  • 并且此时原问题的目标函数的值和对偶问题的目标函数的值相同

定理3    互补松弛性(Complementary slackness property)：如果\(x^*\)是原问题的一个最优解，对应的松弛变量值为\(x_s\)；\(y^*\)是对偶问题的一个最优解，对应的松弛变量值为\(y_s\)，则：

\[x^T_sy^*=0 \]

\[(x^*)^Ty_s=0 \]

定理4    互补最优解性质(Complementary optimal solutions property)：在最后一次的迭代中，单纯形算法同时得到了一个原问题的最优解\(x^*\)和对偶问题的一个互补最优解\(y^*\)（就是row 0中，原问题松弛变量的系数），并且有：\(c^Tx^*=(y^*)^Tb\)。此时，\(y^*\)其实就是原问题对应约束的影子价格(shadow price)

3. 写在后面

牛牛认为，对偶理论是自己目前在运筹优化领域中接触到的最难理解、却又极为基础的理论，它像一扇大门，连接着“运筹学课本”和“用运筹学解决实际问题”。刚开始学习运筹学时，老师只会告诉牛牛，照着4.1这张表把原问题的对偶问题写出来就好了（挠头）。等到有一定基础后，牛牛又把对偶相关的性质证了一遍，但依然觉得这玩意儿很抽象。

于是，牛牛去请教了L大佬，他提供了一种理解角度：

假设线性规划问题表述为：

[原问题]

\[max\quad{cx} \]

\[s.t.\quad{Ax}\leq{b}\tag{14} \]

\[\quad\quad{x}\geq0 \]

约束 (14) 的两边左乘一个各元素均为非负的向量（或矩阵）\(u\)，可得：

\[uAx\leq{ub}\tag{15} \]

由于原问题是一个求最大值的问题，我们希望式 (15) 能够给目标函数值提供一个上界。也就是说，希望对任意可行解 \(x\)，都有：

\[cx\leq{uAx} \]

这就要求：

\[uA\geq{c} \]

在该条件下，可进一步得到：

\[cx\leq{uAx}\leq{ub} \]

这表明，只要满足 \(uA \geq{c}\)，原问题任一可行解对应的目标函数值都不会超过 \(ub\)，因此 \(ub\) 是原问题目标函数值的一个上界。

为了使\(ub\)这个上界尽可能紧，我们希望在满足上述约束条件的前提下，选择合适的 \(u\)，以使 \(ub\) 尽可能小。那么这个问题可以描述为：

[对偶问题]

\[min\quad{ub} \]

\[s.t.\quad{uA}\geq{c} \]

\[\quad\quad{u}\geq{0} \]

我们将上面这一优化问题称为原问题的对偶问题。