最短路径问题

制定模型   |  反复试验   |  解决模型

在Excel中使用求解器可找到无向网络中从节点S到节点T 的最短路径。网络中的点称为节点（S，A，B，C，D，E和T）。网络中的线称为弧（SA，SB，SC，AC等）。

制定模型

我们要解决的模型在Excel中如下所示。

1.要制定最短路径问题，请回答以下三个问题。

一个。要做出什么决定？对于此问题，我们需要Excel找出圆弧是否在最短路径上（是= 1，否= 0）。例如，如果SB是最短路径的一部分，则单元格F5等于1。否则，单元格F5等于0。

b。这些决定受到哪些限制？每个节点的净流量（流出-流入）应等于供应/需求。节点S只能有一个输出弧（净流= 1）。节点T仅应具有一个进入弧（净流= -1）。如果其他节点位于最短路径（净流量= 0）或没有流量（净流量= 0），则所有其他节点都应有一个出弧和一个入弧。

C。这些决策的总体绩效指标是什么？性能的总体衡量标准是最短路径的总距离，因此目标是最小化此数量。

2.为了使模型更易于理解，请命名以下范围。

3.插入以下功能。

说明：SUMIF函数计算每个节点的净流。对于节点S，SUMIF函数将Go列中的值与From列中的“ S”相加。结果，只有单元格F4，F5或F6可以为1（一个出弧）。对于节点T，SUMIF函数将Go列中的值与To列中的“ T”相加。结果，只有单元格F15，F18或F21可以为1（一个传入弧）。对于所有其他节点，Excel将在“从”和“到”列中查找。总距离等于距离与行驶距离之和。

试错

使用这种公式，可以轻松分析任何试验解决方案。

1.例如，路径SBET的总距离为16。

不必使用反复试验。接下来，我们将描述如何使用Excel Solver快速找到最佳解决方案。

解决模型

要找到最佳解决方案，请执行以下步骤。

1.在“数据”选项卡上的“分析”组中，单击“求解器”。

注意：找不到规划求解按钮？单击此处加载规划求解加载项。

输入求解器参数（继续）。结果应与下图一致。

您可以选择键入范围名称或单击电子表格中的单元格。

2.输入目标的TotalDistance。

3.单击最小。

4.输入Go作为更改变量单元格。

5.单击添加输入以下约束。

6.选中“使非约束变量为负”，然后选择“ Simplex LP”。

7.最后，单击解决。

结果：

最佳解决方案：

结论：SADCT是最短路径，总距离为11。