1. 线性规划（Linear Programming）

1.1 问题形式

在线性约束条件下，求一个线性目标函数的最大值或最小值：

$$ \begin{aligned} \max \quad & z = \sum_{j=1}^{n} c_j x_j \\ \text{s.t.} \quad & \sum_{j=1}^{n} a_{ij} x_j \le b_i \quad (i = 1, 2, \dots, m) \\ & x_j \ge 0 \quad (j = 1, 2, \dots, n) \end{aligned} $$
  • 可行解：满足全部约束条件的解；
  • 最优解：使目标函数取得极值的可行解；
  • 可行域：所有可行解构成的集合，是一个凸多边形（凸多面体）。

1.2 重要结论

  • 线性规划的可行域是凸集；
  • 若线性规划有最优解，则最优解一定可以在可行域的顶点上取得；
  • 单纯形法（Simplex）的基本思想就是沿着可行域的顶点迭代，每次移动到一个使目标函数值更优的相邻顶点。

1.3 整数线性规划

若要求 $x_j$ 取整数，则为整数线性规划（ILP），属于 NP 难问题，不能直接用单纯形法求解，需要分支限界法或割平面法。0-1 背包问题就是一种特殊的 0-1 整数规划。

2. 网络流（Network Flow）

2.1 基本概念

  • 网络：有向图 $G = (V, E)$，每条边 $(u, v)$ 有容量 $c(u, v) \ge 0$，含源点 $s$ 和汇点 $t$；
  • 可行流：满足容量限制 $0 \le f(u,v) \le c(u,v)$ 与流量守恒（除 $s$、$t$ 外，每个顶点流入量等于流出量）的函数 $f$；
  • 最大流：从 $s$ 到 $t$ 的总流量最大的可行流；
  • 割（Cut）：把顶点集划分为含 $s$ 的 $S$ 与含 $t$ 的 $T$，割的容量为所有从 $S$ 指向 $T$ 的边的容量之和。

2.2 最大流最小割定理

定理：网络中从源点到汇点的最大流量等于最小割的容量。

即 $\max f = \min c(S, T)$，这是网络流理论的核心结论。

2.3 主要算法

算法思路复杂度
Ford-Fulkerson反复寻找增广路径并沿路增广$O(e \cdot \max f)$
Edmonds-Karp用 BFS 找最短增广路径$O(ve^2)$
Dinic分层图 + 阻塞流，多路增广$O(v^2 e)$
最小费用最大流在最大流基础上，用 SPFA/势能 Dijkstra 找单位费用最小的增广路$O(f \cdot ve)$ 量级

2.4 常见建模方法

网络流的难点在于建模，常见技巧：

  • 拆点：把顶点拆成入点与出点，中间连一条容量为 1 的边，用于限制「每个点只能经过一次」（如节点容量约束）；
  • 超级源点 / 超级汇点：多源多汇问题转化为单源单汇；
  • 二分图匹配：源点连左侧点（容量 1），左侧点连右侧点，右侧点连汇点（容量 1），最大流即为最大匹配数（König 定理）；
  • 上下界网络流：把下界转化为必要流量，先做可行流判定，再求最大流/最小流。

3. 典型问题

问题所属解法
最大流网络流Dinic / Edmonds-Karp
二分图最大匹配网络流匈牙利算法 / 最大流建模
最小路径覆盖网络流拆点 + 二分图匹配
最大权闭合子图网络流最小割建模
生产计划问题线性规划单纯形法
运输问题线性规划表上作业法