线性规划对偶问题、影子价格（shadow price）与单纯形法检验数（reduce cost）

#! https://zhuanlan.zhihu.com/p/597955786 # 线性规划对偶问题、影子价格（shadow price）与单纯形法检验数（reduce cost）

Lagrange对偶问题（包括线性规划对偶问题）实际上可以有一个经济学的解释（关于Lagrange对偶、线性规划对偶的数学推导可以看上一篇文章）。对于这样一个原问题

\[ \min f_0(x) \\ {s.t.} \begin{array}{l} f_i(x) \le 0,i=1,\dots,m \end{array} \]

可以把x理解为公式的某种经营策略，那么\(f_0(x)\)表示这种经营策略下的成本。而\(f_i(x)\le 0\)表示某种限制，比如公司的劳动力上限，仓库容量上限等等。那么这个优化问题就是找到最好的经营策略，它的成本最小。或者说利润最高。

接下来考虑另一种情况，约束是可以被违背的，但是对违背的部分有一些惩罚，或者说额外成本，与违背的部分成线性关系。即约束i被违背的部分\(f_i(x)\)带来的成本为\(\lambda_if_i(x)\)。相应的，如果约束不是紧的，公式会因此得到收益。即当\(f_i(x)<0\)，带来的成本是个负数（也就是获得收益）。系数\(\lambda_i\)的含义是违背\(f_i\)的价格。

在这种情况下，以x的方式运营，约束价格为\(\lambda\)，公司的总成本就为\(L(x,\lambda)=f_0(x)+\sum_{i=1}^m \lambda_i f_i(x)\)，这就是Lagrange函数。公式当然会选择最好的经营策略，使得成本最小，也就是\(g(\lambda) = \inf_x L(x,\lambda)\)，这就是Lagrange对偶函数。同时基于这种解释，也很好理解\(d^*\le p^*\)，因为在这个情况下公式实际上有了更多的选择，出售多余的约束，而购入需要的约束。

现在假设强对偶性成立（比如线性规划的情形），对偶问题的最优解\(\lambda^*\)可以看作这样的价格：在这个价格下，允许以这样的价格支付被违背的约束（或是通过不紧的约束获得收益）相比约束不能被违背时没有任何优势。实际上\(\lambda^*\)就是原问题的影子价格。

影子价格的通常定义表述为：当限制条件放宽一个单位之后，最适解决方案的真实价值的变化。可以看到这个定义和我们前面的描述是相容的。它反映了最优情况下资源的边际价值。

单纯形法检验数

在线性规划中，其实影子价格还与单纯形法的检验数有密切的联系。

单纯形算法角度

回忆一下单纯形法的步骤，根据线性规划基本定理，线性规划的最优解一定在顶点出现。而单纯形法给出了一个好的寻找最优顶点的算法，具体地，它是一种基于迭代的算法，每次根据检验数来选择一个入基出基变量。下面我们来具体描述一下关于检验数的部分。

对于这样一个标准形式的线性规划

\[ \min c^T x \\ {s.t.}\left \{ \begin{array}{l} Ax = b\\ x\ge 0 \end{array} \right. \]

我们把变量x拆分成基变量和非基变量（等于0的变量）

\[ x=\left[\begin{array}{l} x_B \\ x_N \end{array}\right] \]

其中\(x_B \in R^m\)是基变量，\(x_N \in R^{(n-m)}\)是非基变量。

那么原问题就可以写成

\[ \min c_B^T x_B + c^T_Nx_N \\ {s.t.}\left \{ \begin{array}{l} Bx_B + Nx_N = b\\ x_B\ge 0,x_N\ge 0 \end{array} \right. \]

根据约束我们有

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

注意这里取B的逆是不会出问题的，因为B是满秩的。我们要找到一个新解\(x'\)

\[ x' = x + \theta d \]

由于\(x'\)应该是\(x\)的相邻顶点，所以我们实际上是在非集变量中找到一个入基变量\(x_j\)，那么\(d\)中与非基变量对应的除了\(d_j\neq 0\)外，其它分量都为0。

又因为新解\(x'\)也应当满足约束，所以有\(A(x+\theta d)=b\)，我们知道x是可行解，所以\(Ax=b\)，那么\(Ad=0\)，因此

\[ 0 = Ad = Bd_B + A_j \]

所以可以导出基可行方向为

\[ d_B = -B^{-1}A_j \]

沿着这个可行方向，我们可以算出目标函数的变化量，通常情况下是减少量（因为我们会去可以选择使目标函数减少的入基变量）

\[ \Delta = c^Td = c^Td_B + c_j = c_j - c_B^TB^{-1}A_j \]

这个数在单纯形法中也被成为检验数。它实际上表示沿着某个可行方向，移动一个单位时目标函数的减少量。

对偶问题与影子价格角度

对于原问题，我们熟知它的对偶问题为

\[ \max -b^Tv \\ {s.t.} \begin{array}{l} A^Tv+c\ge0\\ \end{array} \]

当我们给原问题约束右侧的\(b\)做出一点调整，调整为\(b+d\)时。由于非退化情况下原问题满足\(x_B = B^{-1}b>0\)，由于调整是可以很细微的，所以我们可以找到\(B(b+d)>0\)。

由强对偶理论我们知道调整后也有\(p^* = d^*\)，也就是

\[ c_B^T B^{-1} (b+d) = -v^T(b+d) \]

得到对偶问题的最优解\(v^T = -c_B^TB^{-1}\)。

注意到检验数中也出现了这个结构。它们都是考察作出某种单位变化后对目标函数的影相值，而入基出基操作在某种程度上也可以和调整\(b\)联系起来。

另外，这也给出了一种求解单纯形法检验数的方法--我们可以通过求解对偶问题来间接的求解单纯形法检验数。在规模很大的时候求解\(B\)的逆并不是一件容易的事情，而求解对偶问题可能更简单一些。我们将在讲解列生成算法的时候更深入的分析这个问题。