最大流问题
很多生产、物流类场景都可以建成弧上带流量上界的网络：在源点有供应、在汇点有需求或接收，希望在满足弧容量与平衡条件的前提下，从源到汇输送尽可能多的流量。这就是经典的最大流问题（Maximum Flow Problem, MFP）。
2.3.1 问题描述
下面借助油气输送的例子说明，如何把具体情景写成线性规划；同一类数例与表记在运筹与网络流文献中很常见（如 Winston and Goldberg, 2004 等同类写法可供对照）。
某油气加工公司需进行油料输送。输送网络为带源点 与汇点 的管道网络（见下图 2.4）。油料从源到汇中途径中间站点 、、。不同管段因管径等差异具有不同最大通过能力；表 2.1 给出各有向弧的容量，单位为百万桶/小时。希望建立线性规划模型，求该网络在例如「每小时能输送几百万桶」意义下的最大通过能力。
表 2.1 石油运输问题的弧容量（百万桶/时）
| 弧 | 容量 |
|---|---|
| 2 | |
| 3 | |
| 3 | |
| 4 | |
| 1 | |
| 2 |
2.3.2 问题建模及最优解
为便于在各节点上写出「入流 = 出流」的平衡式，常采用一种技巧：在汇点 到源点 之间人工添加一条有向弧（常见取向为自汇向源，记法与 一致；有的文献写作辅助弧）。设该人工弧上的流量为 （图 2.4 中有时把待最大化的总流量标注在回流弧上为 ，与 在含义上对应同一流量值）。该弧并不对应真实管输，只用于在模型中把净流量统一写成闭网络形式。
设 为弧 上每小时通过的流量（百万桶）。下面给出一组可行解（可对照图 2.5），有
- 人工/回流方向取 （与 同值，表示网络总流量为 2）
此配置下，网络最大流量为 2（百万桶/时）。
注：一般情形的弧与节点平衡见下两节；下述 (1)–(15) 是上述油气例子的完整 LP 展开，可与常见 MFP 入门叙述逐条对照。
一般约束形式
可行流需满足容量与非源汇节点的流量守恒（下文数值例中用 表示弧 的容量）。抽象写法：
（若节点集合与弧集用 叙述，也可写成「入减出为零」的净流量形式，见 2.3.3。）将人工弧 及其流量 显式放入模型，则极大化 就等价于极大化从 到 的可行输送量。对本例，得到如下 LP（ 为目标）。
弧容量（与表 2.1 一致）：
流量平衡（本网络拓扑）：
（人工弧 的流量即 ，与 (3) 中目标变量一致。）
注：(4)–(9) 为弧上容量；(10)–(14) 为在添加人工弧后的节点平衡；模型搭好后可用任意 LP 软件求解。上一段给出的数值解使 ，与「最大 2 百万桶/时」一致。
2.3.3 最大流问题的一般模型
设有向图 ， 为顶点、 为边集。对每条有向边 有上界容量 。设 为源、 为汇。在一般叙述中，用
- 决策变量 表示在边 上的流量；
- 标量 表示从 到 的总流量（即最大流问题要最大化的量）。
在流守恒表述下，可写为
其中 的取值为： 时 ； 时 ；其余中间节点上 。若采用与 2.3.2 相同的人工回流弧技巧，把 与某条 或等价标量对应起来，则一般模型与具体 LP 实现可一一对应。
注：(17) 中 、 分别表示离开、进入 的弧的集合，与最短路问题 中的 写法同型，各文献在大小写与「出/入」命名上可能略有不同。最大流是网络流与组合优化的核心模型之一，可用专门算法或 LP/ILP 求解器计算。