EP04. “Maximum Flow Problem 最大流量问题”
🔒 登录后可标记已读- 这篇用 Solver 解「最大流量问题」
- 一个有方向的网络（每条连接线只能单向通行），要算出从起点 S 到终点 T 最多能通过多少流量
- 前置知识是 EP01 的 Solver 基本操作流程和 SUMIF 函数
- 学完能处理管线、交通网络这类「找最大通量」的问题
重点内容
适用版本
桌面版通用（Excel 365 / 2021 / 2019 等）。
第一步：建立模型
- 决策变量：每条连接线上的流量（flow）
- 约束条件：中间节点的净流量必须等于 0（流进多少就要流出多少）；每条线的流量不能超过它的容量上限（Capacity）
- 目标函数：让从起点 S 出发的总流量最大化
命名范围：
| 范围名称 | 单元格 | 用途 |
|---|---|---|
| From | B4:B15 | 每条连接线的起点 |
| To | C4:C15 | 每条连接线的终点 |
| Flow | D4:D15 | 每条连接线目前的流量 |
| Capacity | F4:F15 | 每条连接线的容量上限 |
| SupplyDemand | K5:K9 | 每个节点该有的净流量（中间节点是 0） |
| MaximumFlow | D17 | 从起点出发的总流量 |
用 SUMIF 分别算出每个节点流入、流出的总量，两者相减得到净流量。
第二步：试算
先手动排一组流量方案试试看：S→A→D→T 流 2、S→C→T 流 4、S→B→E→T 流 2，总流量是 8。
第三步：用 Solver 求解
- Data 选项卡 → Solver
- Set Objective 选 MaximumFlow，选 Max（最大化）
- By Changing Variable Cells 选 Flow
- 加约束：中间节点的 NetFlow = 0；所有 Flow 都不能超过 Capacity
- 勾选 Make Unconstrained Variables Non-Negative，Solving Method 选 Simplex LP
- 点击 Solve
[截图：Solver 约束列表，NetFlow=0 和 Flow≤Capacity 两条约束都已添加]
求解结果
最大流量是 12，分布在 6 条路径上，各自流量不同。
[截图：Flow 列求解完成后，每条连接线的流量分配结果]
学完你会
- ✅ 用「中间节点净流量为 0」加「流量不超过容量」给通量问题建模
- ✅ 用 SUMIF 分别算出每个节点的流入、流出总量
- ✅ 分清最大流量问题（有方向网络）跟最短路径问题（无向网络）的建模差异
常见错误
- 忘记加「流量不能超过容量上限」这条约束，Solver 算出不现实的超容量流量
- 中间节点的净流量约束只加了流入或只加了流出，没有真正做到「流进=流出」
- 把「最大流量问题」（有方向网络）跟 EP03「最短路径问题」（无向网络）的建模逻辑搞混
Sources
Blog / Website：