《物流运筹方法与工具》第3版 课件 模块六单元三 运输网流量分布的最大流法

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

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

运输网流量分布的最大流法一、最大流的含义二、最大流的标号算法三、最大流的图解算法运输网最大流量分布问题：最大流问题的一般提法：一、最大流的含义在已知的物流网络（各段线路的通过能力、运输费用或运输时间为已知）中，有一货物发点（供应点）和一货物收点（客户），在这种情况下找出最佳流量安排（线路流量分配）方案，使通过网络的流量达到最大（或运输费用最省、或运输时间最小）。在有一个起点和一个终点的网络中，最大流问题是企图找出，在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量（不管它是物资、卡车、飞机、液体或电流）。即最大流问题，就是在一定条件下，要求流过网络的流量为最大的问题。一、最大流的含义（一）网络流量在一定条件下流过一个网络的总流量，它等于起点的总发量或终点的总收量。网络流量记作

，网络边上的实际流量记作fij。一、最大流的含义（二）可行

流满足以下条件的流叫可行流（记为可行流f）：一、最大流的含义（三）最大

流在一个网络中，流量达到最大值的可行流。求网络的最大流，就是指在满足上述（二）中条件1、2、3的前提下，使的值达到最大。一、最大流的含义（四）增广

链如果从网络的发点s到收点t能找出一条链，在这条链上，所有指向为s→t的边（称为前向边），其上的流量都小于容量，而所有指向为t→s的边（称为后向边），其上的流量都大于0，则称这样的链为增广链，如图6-8所示。f45>0f23>0f34<c34v5v3fs2<cs2sv2v4tf5t<c5t图6-8网络中的一条增广链一、最大流的含义（四）增广

链如果从网络的发点s到收点t能找出一条链，在这条链上，所有指向为s→t的边（称为前向边），其上的流量都小于容量，而所有指向为t→s的边（称为后向边），其上的流量都大于0，则称这样的链为增广链，如图6-8所示。f45>0f23>0f34<c34v5v3fs2<cs2sv2v4tf5t<c5t图6-8网络中的一条增广链二、最大流的标号算法1先给发点s标号

，其中s是发点，此前还没有已标号点，所以给s标的第一个记号是0，第二个记号

可取∞。2找出和已标号点i相邻的所有未标号点，比如j。二、最大流的标号算法3重复步骤2，可能出现两种结局：（1）标号过程中断，即t得不到标号，这表明该网络中不存在增广链，此时的可行流已是最大流，计算即告结束。（2）t得到标号，这时可用反向追踪法在网络中找出一条从s→t的由标号点及相应的边连接而成的增广链，接下去转入步骤4。二、最大流的标号算法5抹掉图上所有标号，重复第1到第4步，直到图中找不出任何增广链，即出现第3步的结局（1）为止，这时，网络中的可行流就是最大流。4调整网络中的可行流f的流量：对增广链上的前向边，其流量增加

，对增广链上的后向边，其流量减少

，增广链以外的边上的流量不变。这样得到一个新的可行流f`。二、最大流的标号算法例6-2

用标号算法求图6-7中s→t的最大流，图中边旁数字为。9(4)2(0)9(9)6(1)5(5)10(8)5(4)7(5)8(8)sv1v2v3v4t图6-7二、最大流的标号算法解：1．先给发点s标号：（0，∞），见图6-9；图6-9v4v1(v4，1)(v1，2)v2(s，2)(v3-，1)(v2-，2)(0，∞)s9(4)2(0)9(9)6(1)5(5)10(8)5(4)7(5)8(8)v3t二、最大流的标号算法解：二、最大流的标号算法解：二、最大流的标号算法解：非增广链上所有边的流量都不变，这样便得到网络的一个新的可行流，其流量分布情况见图6-10所示。二、最大流的标号算法图6-10新可行流的流量分布方案s9(5)2(0)9(9)6(0)5(5)10(9)5(3)7(6)8(8)v1v2v3v4t解：三、最大流的图解算法图解算法就是根据最大流问题的网络图来寻找从

到

所允许流过的最大流量。其具体步骤是：01020304任意选择从

到

的通路，一般从最外层开始。接着找出该通路中允许通过的最小流量，并给该通路中各边上安排这个最小流量。将上述具有最小流量的边删去，余下的重新画出网络图。重复上述步骤，直到从

到

已无通路时为止。05将以上所得的通路最小流量值相加，即得该网络的最大流量。例6-3某地区从北到南的交通，平时是利用高速公路通行的。现在，将有一个月的时间因为高速公路要进行路面修理，车辆不能行驶，因此该地区公路管理部门的工程技术人员需要查明，穿过该地区的其它几条道路，是不是有把握每小时通过6000辆汽车，这些汽车在正常情况下，是走高速公路通行的。图6-11所示是穿过该地区的道路通行情况，每条道路的通行能力用每小时千辆汽车为单位来表示。各支线每小时流量能力为：1——2线：6000辆；1——3线：5000辆；1——4线：3000辆；2——5线：4000辆；2——3线：7000辆；3——5线：5000辆；3——4线：3000辆；4——6线：7000辆；5——6线：2000辆；试计算该地区的道路通行能力有多大？三、最大流的图解算法三、最大流的图解算法3（3）5（0）7（0）3（3）5（3）7（3+3）6（2）1234564（2）2（2）图6-11该地区汽车通过能力的计算解：该问题实质就是求解图6-11的最大流问题。计算过程如下：1．任意选择从起点到终点的第一条路线（即增广链）。这里，选择路线1-2-5-6。该路线上支线5-6的流量能力最小，为每小时2000辆，用2表示。因此该路线的每小时的最大流量是2000辆。给该路线上每条支线安排流量2000辆，图中线路旁的数字为

，见图6-11所示。支线5-6已无剩余能力，从图中划掉。三、最大流的图解算法解：

2．另选第二条从起点到终点的路线，如1-4-6。该路线上支线1-4的流量能力最小，其最小流量能力为3。因此第二条路线的最大流量是3。给该路线上每条支线安排流量3，见图6-11所示。支线1-4已无剩余能力，从图中划掉。3．另选第三条从起点到终点的路线，如1-3-4-6。该路线上支线3-4的流量能力最小，其最小流量能力为3。因此第三条路线的最大流量是3。给该路线上每条支线安排流量3，见图6-11所示。支线3-4已无剩余能力，从图中划掉。三、最大流的图解算法解：