“这题对偶之后就是思博题！”
看似坚不可催，换个角度，柳暗花明。
对偶线性规划的维基百科。这篇博客将尽量讲清楚线性规划对偶问题背后的直观理解。
线性规划对偶定理
线性规划的概念
众所周知，线性规划 (Linear Programming, LP) 是运筹学一类应用广泛的重要分支。其标准型是：
$$
\begin{aligned}
\max_{\boldsymbol{x}} \boldsymbol{c}^T \boldsymbol{x}\
s.t. \boldsymbol{Ax} \leq \boldsymbol{b}\
\boldsymbol{x} \geq \boldsymbol{0}
\end{aligned}
$$
其中 $\boldsymbol{x}$ 称为变量，$\boldsymbol{A}$ 的每一行代表一个不等式限制。求解线性规划常用单纯型法，这里不展开叙述。很多常见问题都是线性规划的特例，如最大流、最小费用流、最短路等。
对偶线性规划
线性规划对偶问题会将原规划的限制变成对偶规划的变量，把原规划变量变成对偶规划的限制。一般地，上面标准形的线性规划的对偶问题是：
$$
\begin{aligned}
\min_{\boldsymbol{y}} \boldsymbol{b}^T \boldsymbol{y}\
s.t. \boldsymbol{A^T y} \geq \boldsymbol{c}\
\boldsymbol{y} \geq \boldsymbol{0}
\end{aligned}
$$
然后就可以证明：
强对偶定理：线性规划与对偶规划的答案是相同的，即 $\displaystyle\max_{\boldsymbol{x}} \boldsymbol{c^T} \boldsymbol x = \min_{\boldsymbol y} \boldsymbol{b^T y}$
等等，为什么啊？我们先证明弱对偶定理，得到一些直观理解，从而能够把公式背下来。
弱对偶定理： $\displaystyle\max_{\boldsymbol{x}} \boldsymbol{c^T} \boldsymbol x \leq \min_{\boldsymbol y} \boldsymbol{b^T y}$
证明概要：我们考虑将 $Ax\leq b$ 代表的这些限制线性组合，如果组合之后得到的 $\boldsymbol{a^T x}$ 中， $a$ 的各个系数都不小于 $c$ 的，那么我们就得到了线性规划的一个上界。具体来说，假设我们是将 $A$ 第 $i$ 行乘以非负系数 $y_i$（不能是负的，否则不等号方向改变） ，然后把这些行向量相加就得到了 $\boldsymbol{a^T}$。如果满足 $\forall i, a_i \geq c_i$，那么 $\sum_{i} b_i y_i$ 就是答案的一个上界。如果把这些条见放在一起呢？实际上这就是最小化问题 $\min \boldsymbol{b^T y} \text{ }\ s.t. \boldsymbol{A^T y} \geq \boldsymbol{c}, \boldsymbol{y}\geq \boldsymbol{0}$，就是上面的对偶规划。
然后如何继续证明强对偶定理呢？这需要用到 KKT 条件，这里抛出一篇理论教程，此处留坑待填。
所以