LP-duality 定理：线性规划问题的对偶定理。

【定理内容】

用于将线性规划问题转化为对偶问题，然后用算法解决。

给定矩阵 \(A,b,c\)，其中 \(b,c\) 都是只有一列的矩阵（可以当作列向量看）。

问题 1: 求向量（一组数）\(\vec{x}\)，要求 \(A\cdot \vec{x}\le \vec{b}\)
且 \(\vec{x}\ge 0\)，使得 \(c^T\cdot \vec{x}\) 最大。

问题 2: 求向量（一组数）\(\vec{y}\)，要求 \(A^T\cdot \vec{y}\ge \vec{c}\) 且 \(\vec{y}\ge 0\)，使得 \(b^T\cdot \vec{y}\) 最小。

这两个问题满足这两个性质：
弱对偶性：记问题 1 的任一组可行解 \(\vec{X}\) 和问题 2 的任一组可行解 \(\vec{Y}\)，则 \(c^T\cdot\vec{X}\le b^T\cdot\vec{Y}\)。

强对偶性：如果问题 1,2 都是有解的，则 1 的最优解（最大值）和 2 的最优解（最大值）相等。

线性规划问题其实可以看做给出一大堆不等式，求条件极值。

【定理应用其一：最大流最小割定理】

网络流问题就是天生的一类线性规划问题。

这里将用 LP-duality 定理粗略证明 MF=MC 定理。拿个例子。

\(e_1\sim e_5\) 是每条边的标号。\(x_1\sim x_5\) 表示各边的流量。令 \(cap_i\) 表示 \(e_i\) 的容量（图中未写）。

先把最大流问题改造成线性规划模式。