EP03. “Shortest Path Problem 最短路径问题”
🔒 登录后可标记已读- 这篇用 Solver 解经典的「最短路径问题」
- 一个由节点（node）和连接线（arc）组成的无向网络，要从起点 S 找出到终点 T 距离最短的走法
- 前置知识是 EP01 的 Solver 基本操作流程和 SUMIF/SUMPRODUCT 函数
- 学完能把同一套「建模→试算→求解」流程套用到路径规划类问题
重点内容
适用版本
桌面版通用（Excel 365 / 2021 / 2019 等）。Solver 加载项启用方式见 EP01。
第一步：建立模型
- 决策变量：每条连接线是否被选进最短路径（是=1，否=0）
- 约束条件：起点 S 只能有一条「出去」的线（净流量 Net Flow = 1）；终点 T 只能有一条「进来」的线（净流量 Net Flow = -1）
- 目标函数：让选中路径的总距离最小化
命名范围：
| 范围名称 | 用途 |
|---|---|
| From / To | 每条连接线的起点/终点 |
| Distance | 每条连接线的距离 |
| Go | 这条线是否被选中（0/1） |
| NetFlow | 每个节点的净流量 |
| SupplyDemand | 每个节点该有的净流量（起点 1、终点 -1、其余 0） |
| TotalDistance | 选中路径的总距离 |
用 SUMIF 算出每个节点的净流量，用 SUMPRODUCT 把 Distance 和 Go 相乘加总，算出总距离。
第二步：试算
先手动选一条路径试试看，例如 S→B→E→T，距离是 16。不需要非得手动试出答案，这一步只是帮助理解模型怎么运作。
第三步：用 Solver 求解
- Data 选项卡 → Solver
- Set Objective 选 TotalDistance，选 Min（最小化）
- By Changing Variable Cells 选 Go
- 加约束：NetFlow = SupplyDemand
- 勾选 Make Unconstrained Variables Non-Negative，Solving Method 选 Simplex LP
- 点击 Solve
[截图：Solver Parameters 对话框，NetFlow = SupplyDemand 约束已添加]
求解结果
最短路径是 S→A→D→C→T，总距离 11，比试算的 16 更短。
[截图：Go 变量结果，被选中的连接线显示 1、其余显示 0]
学完你会
- ✅ 用「净流量 = 供需」的约束给路径规划问题建模
- ✅ 用 SUMIF 算出每个节点的净流量，用 SUMPRODUCT 算出总距离
- ✅ 用 Solver 求出比手动试算更短的路径
常见错误
- 净流量的约束条件设反了方向（起点该是 +1 却设成 -1，或反过来）
- 没有理解「只是帮助理解模型」这一步的用途，误以为一定要手动试出正确答案才能进行下一步
- Go 变量没设成 0/1 二元变量，Solver 算出不合理的中间值
Sources
Blog / Website：