线性规划转对偶网络流问题小记🐤

二元线性规划问题转网络流：对于 \(n\) 个变量 \(x_i\)，限制形如 \(x_i-x_j\ge b\) 或 \(x_i\ge b\) 或 \(x_i\le b\)，求 \(\sum c_ix_i\) 的最小值，可以转化成上下界最大费用流求解。

首先重温线性规划问题的一般形式（之一）：

\[\begin{aligned} &\textbf{minimize }c^Tx, \texttt{ where } Ax\ge b\\ \iff&\textbf{maximize }y^Tb, \texttt{ where } yA\le c^T \end{aligned} \]

当所有限制都形如 \(x_i-x_j\ge b\) 的时候，矩阵 \(A\) 的每一行都至多有一个 \(+\) 和一个 \(-\)。设向量 \(x\) 的长度为 \(n\)，矩阵 \(A\) 的大小为 \(m\times n\)。

考虑构造一个 \(n\) 个点 \(m\) 条边的网络流图（不包括源汇），令 \(y_i\) 表示第 \(i\) 条边流过的流量。那么 \(\textbf{maximize }y^Tb\) 的条件就代表第 \(i\) 条边的费用是 \(b_i\)，即连一条 \((u,v,+\infty,b_i)\) 的边，然后求最大费用流。

对于 \(yA\le c^T\)，可以发现 \(y\) 乘上 \(A\) 的每一列的信息可以视为关于那个节点的信息，\(+\) 代表从这个节点流出，\(-\) 表示流入。那么，如果 \(c_i\ge 0\)，条件即为 \(out-in\le c_i\)，可以用 \((S,i,c_i,0)\) 和 \((i,T,+\infty,0)\) 表示；如果 \(c_i< 0\)，条件即为 \(in-out\ge -c_i\)，可以用 \((i,T,[-c_i,+\infty),0)\) 表示。