这个Excel功能太逆天了！我手动算了1小时，同 事点点鼠标10分钟就搞定！

在小花的上一篇文章中，分享了如何用 Excel 规划求解工具解决最优运费问题↓↓↓

同事为这个运费问题加班两小时，而我 10 分钟搞定！

今天，我们继续探讨另一运输问题——最短路径问题。

什么是最短路径问题？

最短路径问题（The Shortest Path Problem, SPP）是组合优化领域的经典问题之一，它是指在一个有向赋权网络中，给定一个起点和一个终点，求从起点到终点距离最短的一条路径及其长度。

举个例子，某公司需要将一批货物以最快的速度从起点 S 运往终点 T，中间有多个中转站点，每个站点间是否可通行及通行的距离不一。

我们将具体情况绘制成下图这样一个有向赋权网络，圆圈代表运输节点，带箭头线段代表运输路径方向（称为「弧」，如 SA、AD），数字代表距离。如弧 SA，其数字为 4，这代表 S 点可以往 A 点运输，运输距离为 4。

将货物从起点 S 运往终点 T 的可行路径有很多：

比如 S-A-E-T，其路径距离为 4+5+7=16；

再如 S-C-F-T，其路径距离为 5+55+=15。

显然，路径 S-C-F-T 更短，而在本案例要求得最短路径，就是要找出起点为 S、终点为 T 且各弧数值之和最小的那条折线。

最短路径问题在传统数学计算上是比较复杂的，如穷举、如图解……

好在，我们有 Excel 规划求解这样的神器。

如何使用规划求解解决？

▋STEP01 将有向赋权网络转换成表格形式，以便计算

我们需要依次把每条弧的起止点及距离录入到 Excel 中，如下图：

▋STEP02 建立可变单元格与规划目标之间的计算模型

显然，案例中的规划目标为每条路径经过的弧的距离之和。问题是，该如何确定当前路径包含哪些弧呢？

我们在 D 列中，使用 0 和 1 来做区分，0 代表不经过该弧，1 代表经过该弧。由于任何数乘以 0 都等于 0，任何数乘以 1 等于其本身，当前路径的距离之和即为 D 列与 C 列乘积之和，我们使用 SUMPRODUCT 函数来完成计算。

当前路径运输距离公式：
=SUMPRODUCT(D2:D18,C2:C18)

▋STEP03 明确限制条件

该案例的限制条件是起点必须为 S，终点必须为 T，这在 Excel 中该如何体现呢？

我们把某一节点作为出发点的次数与其作为到达点的次数的差额称为净流量，则各节点的净流量限制条件包含以下三个：

❶ 起始点 S 的净流量必须等于 1，这表明某一次从 S 出发后未再返回，结合第 3 点所述，S 即为起点；

❷ 终止点 T 的净流量必须等于-1，这表明某一次到达 T 点后，未再出发，结合第 3 点所述，S 即为终点；

❸ 其他途经点（A、B、C、D、E、F）的净流量必须等于 0，这表明每一次到达这些途经点后，总是再次出发，最终不停留在这些途经点上。

我们用 SUMIF 函数分别计算出每个节点作为出发点的次数和作为终止点的次数，二者相减，必须满足 S 点为 1，T 点为-1，其余点为 0。

于是，我们构建限制条件区域如下：

L2 单元格公式如下：
=SUMIF($A$2:$A$18,$K2,$D$2:$D$18)-SUMIF($B$2:$B$18,$K2,$D$2:$D$18)




▋STEP04 设置规划求解器，进行求解

❶ 点击【数据】-【规划求解】，<设置目标>选择 F16 单元格，规划目标设定为<最小值>，选择<可改变单元格>为 D2:D18；

❷ 添加约束条件 L2:L9=N2:N9；

❸ 勾选<使无约束变量为非负数>，选择求解方法为<单纯线性规划>，点击【求解】，得到结果后，点击【确定】即可。

到此，我们就完成了最优路径问题的求解，即 S-A-E-D-T，总运输距离为 14。

写在最后


以上就是小花分享的，使用规划求解完成最短路径问题的方法，你学会了吗？简单 4 步，即可轻松搞定哦！

❶ 将有向赋权网络转换成含起止点距离的表格形式；

❷ 建立表示是否经过的 0/1 变量和路径距离之间的计算模型；

❸ 明确起终点和途径点的净流量限制值，并设置净流量计算公式；

❹ 设置规划求解器，求解最短路径。

规划求解是一个功能强大的 Excel 加载项，只要我们将实际问题以合适的方式置入 Excel 表格中，设置基于变量的目标值及限制条件，我们就可以解决复杂的最优解问题。

后续有机会，小花还将持续分享其他经典的最优解问题 Excel 求解方案，敬请期待吧！

如果你还想了解更多的 Excel 知识，更轻松高效地解决求解问题， 我推荐你参加《3 天 Excel 集训营》！

为期 3 天的课程专为职场人准备，全部基于职场真实表格案例设计，还有很多超实用 Excel 技巧教学。

每天学习大概 30 分钟，从日常的功能出发，全程演示，一课一练，夯实进阶每一步。

3 天 Excel 集训营

原价 99 元

现在只需1元

现在报名还送

【35 个常用函数说明】

👇👇👇

*广告