《物流运筹方法与工具》第3版 课件 模块六单元四 线路网布局的最小树法

物流运筹方法与工具（第3版）目录

CONTENTS物流运筹方法与工具概述物流决策分析物流资源配置规划物流任务指派运输方案优化运输路径规划物流项目计划物流需求预测库存水平控制模块六模块二模块三模块四模块五模块七模块八模块九模块一模块六运输路径规划运输路径规划概述应用举例线路选择的最短路法运输网流量分布的最大流法线路网布局的最小树法车辆配送路线的安排单元一单元三单元二单元四单元六单元五知识点1．理解图、网络、链、连通图、图模型的概念。2．理解最短路问题的含义；掌握求解最短路问题的Dijkstra算法步骤。3．理解可行流、最大流、增广链的概念；掌握求解最大流问题的标号算法步骤。4．理解最小树、图的中心和重心的含义；掌握最小树问题的逐步生长法步骤。5．理解单、多车辆配送路线安排问题及启发式算法的含义。6．掌握单回路路线优化的最近邻点法和最近插入法的求解步骤。7．掌握多回路路线优化的扫描法、节约法的求解步骤。本单元知识点能力点、素质点能力点：1．能够把相应的实际问题归结为最短路问题，并能够熟练运用Dijkstra算法求解。2．能够把相应的实际问题归结为最大流问题，并能熟练运用标号算法求解。3．能够把相应的实际问题归结为最小树问题，并能熟练运用逐步生长法求解。4．能够把相应的实际问题归结为回路运输路线优化问题，并能熟练运用最近邻点法和最近插入法、扫描法、节约法求解。素质点：1．提高对大数据及云计算、物联网、人工智能等新科技的应用兴趣，勇于实践创新。2．加强“互联网+高效物流”和“降本增效”理念。单元四线路网布局的最小树法

一、最小树的含义

二、最小树的逐步生长法

三、最小树的破圈法1．树所谓树（树图），就是没有圈的连通图。一、最小树的含义2．部分树如果树T是图G的一个部分图，则称树T是图G的部分树。v2v1v3(a)925v2v1v3(b)95v2v1v3(c)25图6-12连通图a与部分树b、c3．最小树在赋权图中，构成其部分树各边权的总和称为部分树的权，如图6-12（b）对应的部分树的权为14，6-12（c）为7。具有最小权的部分树，称为最小部分树，简称最小树。一、最小树的含义二、最小树的逐步生长法例6-4

某天然气公司计划在如图6-13(a)所示的网络中铺设天然气管道，向五个居民小区v1、v2、v3、v4、v5

供气，网络中各边的权代表相应小区之间所铺设天然气管道的实际长度（公里）。试问：应如何铺设管道，既能保证向五个居民小区供应天然气，又能使管道的总长度最短从而使费用最省？v1v2v3v5v45613849109图6－13(a)二、最小树的逐步生长法解：1．先将图6-13所示网络图列出相应的矩阵。二、最小树的逐步生长法2．从v1出发，于是除去D中的v1列，保留v1

行做图表F（1），如图6-14所示。956V4V3V5V3V4V5∞994V2V3V4V4V5F(1)V1V1V1V1∞85F(2)V1V2V198V5F(3)V2V39V5F(4)V22行V4V51063行V5134行图6-14逐步生长法求解过程图6-14逐步生长法求解过程二、最小树的逐步生长法3．在F（1）左部上面一行中，填写v1行的元素值；而下面一行中全部填写v1

，表示上面一行的数值全部来自v1

行。然后，在F（1）左部上面一行找出最小值4，即由v1点

到v2点

的距离d12=4为最小，因此把4圈起来，说明可以从v1点

到v2点

铺设一条管道，记作

。接着，除去D的第二列（v2列）元素，保留第二行余下的元素做F（1）右面部分的副表。二、最小树的逐步生长法二、最小树的逐步生长法最后，可按最小树铺设管道，其距离总长为：4+5+6+9=24为最短，图6-13（b）所示为最小树示意图。图6-14（b）三、最小树的破圈法破圈法在连通图G中任意选取一个回路，从该回路中去掉一条权数最大的边（如果权数最大的边不唯一，则任意选取其中一条）。在余下的图中，重复这一步骤，直到得到一个不含回路的连通图（有n个顶点、n-1条边），该连通图便是最小部分树。三、最小树的破圈法例6-5如图6-15所示，A、B、C、D、E、F、G代表某集团公司及下属的工厂，它们之间的连线代表彼此之间的道路交通情况，连线旁的数字代表相应道路的长度。现在要沿道路铺设通讯电缆，使公司、各工厂彼此之间都能通上电话，问应如何铺设才能使线路总长度最短。ABEDCG7564F5289783图6-16三、最小树的破圈法解：用破圈法求解该问题的过程和结果分别见图6-16，6-17，6-18所示，铺设线路的最短长度是8+2+5+4+3+7=29，其中，打