模块六 运输与配送网络优化-6课件讲解

港口物流优化模块六目录

CONTENTS模块三模块四模块五物流决策优化认知物流管理决策分析物流资源配置优化物流任务指派优化模块二模块七模块一物资调运方案优化运输与配送网络优化物流项目计划优化模块六运输与配送网络优化任务1网络图认知任务2最小费用流问题任务3最大流问题任务4最小费用最大流问题任务5最短路问题任务6最小支撑树问题任务7节约里程法模块知识点了解网络图的相关基本概念及含义了解节约里程法的基本原理和求解步骤掌握节约里程法的求解方法掌握最小费用流、最大流、最小费用最大流、最短路、最小支撑树、货郎担、中国邮路等问题的基本描述、数学模型特点及应用情境模块能力点掌握最小费用流、最大流、最小费用最大流、最短路、最小支撑树、货郎担、中国邮路等问题的表格模型建模及求解节约里程法求解配送问题任务6最小支撑树问题点边无向图链：无向网络中，前后相继点和边的交替序列称为一条链。圈：闭合的链称为一个圈。无向图中任意两点之间，至少有一条链，则为连通图，否则为不连通图。树（针对无向图）：无圈的连通图支撑树：与图G顶点相同，边是图的一部分的树。支撑树的权：在赋权图中，构成其支撑树各边权的总和。最小支撑树：具有最小权的支撑树，简称最小树。v2v1v3(a)925v2v1v3(b)95v2v1v3(c)25图

连通图a与部分树b、c注：树的边数=图的顶点数-1任务6最小支撑树问题v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)v1v2v3v4v5v6v7e1e6e7e9e10e11(c)任务6最小支撑树问题许多网络问题可以归结为最小支撑树问题。例如，设计长度最短的公路网，把若干城市（乡村）联系起来；设计用料最省的电话线网（光纤），把有关单位联系起来；等等。这种问题的目标是设计网络。虽然节点已经给出，但必须决定在网络中要加入哪些边。特别要指出的是，向网络中插入的每一条可能的边都有成本。为了使每两个节点之间有连接，需要提供足够的边。目标就是以某种方法完成网络设计，使得边的总成本最小。这种问题称为最小支撑树问题。任务6最小支撑树问题例7某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。v1v2v3v4v5v6651572344任务6最小支撑树问题5v1v2v3v4v5v612344避圈法：每步从图中未选的边中选取边e,使它与已选边中的最小权边不构成圈,直到选够n-1（n为顶点数）条边为止.破圈法：在图G中任意取一个圈，从圈上任意舍弃一条边（通常选权最大者）,将此圈破掉。重复此步骤直到图G中没有圈为止。v1v2v3v4v5v6651572344v1v2v3v4v5v6651572344电话线铺设线路最短为最小支撑树的权，即5+1+2+3+4=15.，铺设方法如图所示。任务6最小支撑树问题v1v2v3v4v5v6651572344电子表格模型如下:可知，铺设方法为(v1,v2),(v2,v3),(v2,v4),(v4,v5),(v5,v6),费用最省为15.任务6最小支撑树问题解：使用Excel软件求解最小生成树的基本步骤如下：（1）输入网络图到Excel工作表中。表中左上角是一个6×6的对称权矩阵。例如单元格C2位置的“5”代表从v1点到v2点的距离；同样，单元格B3位置的“5”代表的是从v2点到点v1的距离。矩阵中“1000”代表距离是无穷大，意味着相应两点间没有路。（2）输入6×6的变量矩阵。矩阵中的元素只能取“0”和“1”，“0”代表没有选中，“1”代表被选中。（3）输入约束条件：1）变量矩阵的每行的行和大于等于1。这意味着一个节点至少与其它一个节点相连。

2）变量矩阵的每列的列和=相应的行和（对称矩阵）。3）总边数等于顶点数减1，这是树的定义。总边数就是B10：G15的所有元素和除以“2”（因为每条边有两个节点重复计算了一次，所有要除以“2”）。（4）输入目标函数：总铺设费用最小。总铺设费用等于选中路径的权重之和，即SUMPRODUCT(B2:G7，B10:G15)/2。（5）求解：目标函数：Min（总建设费用最小）;约束条件：变量矩阵=bin;总边数=顶点个数-1=5;行和大于等于1;行和等于列和6、如图所示，A、B、C、D、E、F、G代表某集团公司及下属的工厂，它们之间的连线代表彼此之间的道路交通情况，连线旁的数字代表相应道路的长度。现在要沿道路铺设通讯电缆，使公司、各工厂彼此之间都能通上电话，问应如何铺设才能使线路总长度最短。（分别采用破圈法、避圈法和EXCEL求解）练一练ABEDCG7564F5289783参考答案解：用破圈法求解该问题的过程和结果分别见图6-16，6-17，6-18