《物流数据分析》课件-任务6.2 最短路径问题规划求解

任务6.2最短路径问题规划求解【任务目的】1.掌握最短路径规划问题的目的和意义；2.掌握SUMIF函数的应用；3.掌握使用规划求解工具进行最短路径问题规划的操作步骤。【工作任务】MY搬家公司接受KE物业公司的委托，为其把办公室家具和设备搬运到新总部，道路网络图（单位：公里）如图6-6所示。假如你是MY搬家公司的调度员，你会推荐那条线路？SABCDET4108148282101464道路网络图【知识链接】1.最短路径问题的概念最短路径问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路线。通俗来讲，就是在所有的路线中找到一条距离最短的路线。它在生活中有极其重要的意义与运用，广泛应用于交通工程、通信工程、计算机科学、系统工程、运筹学、信息论、控制理论等众多领域。2.最短路径的问题的数学表达式3.最短路径的问题的求解从最短路径问题的数学模型可以看出，其本质上是一个线性规划模型。因此，可以考虑使用电子表格的规划求解工具进行求解。4.最短距离问题本质是路线最优问题通常所讲的最短路径问题不仅包括地理上的距离最短，还包括费用最少或者时间最短等问题。如选址、管道铺设时的选线、设备更新、投资等问题，都可以归结为求最短路的问题。【实施步骤】1.建立数学模型设决策为s.t.

2.在电子表格中输入基础数据在B4:E15区域输入各段路线及其距离。将B4:B15命名为“从”，将C4:C15命名为“至”，将D4:D15命名为“距离”，将E4:E15命名为“是否选择”。3.编辑目标函数在C18单元格输入公式“=SUMPRODUCT(距离,是否选择)”。思考与点拨：公式“=SUMPRODUCT(距离,是否选择)”应该如何理解？SUMPRODUCT(

)函数是是在给定的几组数组中，将数组间对应的元素相乘，并返回乘积之和。其语法形式为“=SUMPRODUCT(array1,

[array2],

[array3],

...)”，数组参数个数为2到255个。在任务中，公式“=SUMPRODUCT(距离,是否选择)”与公式“=sum(D4:D15*

E4:E15)”或公式“=D4*E4+D5*E5+D6*E6+……+D15*E15)”

的计算结果相同，但使用数组公式可以为类似于

SUMPRODUCT(

)函数的计算提供更通用的解法。需要注意的是：数组参数必须具有相同的维数，否则，函数SUMPRODUCT(

)将返回错误值

#VALUE!；函数SUMPRODUCT(

)将非数值型的数组元素作为0处理。4.编辑约束条件式在区域G4:G10输入各个节点的名称，在H4单元格输入公式“=SUMIF(从,G4,是否选择)-SUMIF(至,G4,是否选择)”。将该公式向下填充到H10。在J4单元格输入“1”，在J10单元格输入“-1”，在J5:J9区域输入“0”。5.使用规划求解工具求解选中目标函数单元格C18,点击“数据|分析|规划求解”，出现如图所示的对话框，设置目标为单元格C18到“最小值”，通过可更改单元格设置为“E4:E15”，如图所示。点击遵守约束右侧的“添加”按钮，弹出添加约束对话框，单元格引用选择输入“$H$4:$H$10

”，约束输入“$J$4:$J$10”，点击约束类型右侧的箭头，在下拉菜单中选择“=”，点击“添加”，继续添加新约束条件。单元格引用输入“E4:E10”，点击约束类型右侧的箭头，在下拉菜单中选择“bin”，即设置决策变量为“二进制”（变量只能取值0或1），点击“确定”，如图所示。勾选使无约束变量为非负数，点击选择求解方法右侧箭头，在下拉菜单中选择“单纯线性规划”，如图所示。点击“求解”，弹出规划求解结果对话框，如图所示。保留默认选项“保留规划求解的解”，选中“运算结果报告”，点击“确定”即可得到规划求解的解及运算结果报告如图所示。从上图可以得出，最短路径为S→A→B→E→D→T,最短距离为26公里。所以，应当选择路线S→A→B→E→D→T作为推荐路线。【任务小结】最短路径问题广泛应用于交通、电路、通讯等实际领域。它的目标是从起点到终点寻找一条总长度最短的路。在一些实际应用中，长度指的是距离，所以最短路的目标就是总行进距离最短。但是，另一些最短路径的应用的目标则是使得一系列活动的总成本或总时间最短。最短路径问题是一类特殊的线性规划问题，在Excel中可以利用Solver求解器解决最短路径问题的关键是将如何将问题描述为线性规划模型，难点是约束条件中关于节点净流量计算公式“=SUMIF(从,**,是否选择)-SUMIF(至,**,是否选择)”的理解。【实践训练】某物流公司计划从产地O出发，将