《物流管理定量分析》课件-学习情境五 物流运输规划

物流管理定量分析目录

CONTENTS情境二情境三情境四情境五课程认知物流需求预测物流资源配置规划物流任务指派情境六情境一物流运输规划物流项目管理情境五物流运输规划子情境1子情境3物资调运问题建模及求解运输最短路径问题及其求解运输网络最大流问题及其求解子情境2知识点知识点1．理解物资调运问题的经济含义。2．掌握物资调运问题的实质。3．掌握物资调运问题建模方法。掌握物资调运问题的求解。5．理解图、网络、链的基本概念。6．理解最短路问题的含义。7．掌握求解最短路问题的Dijkstra算法步骤。8．理解可行流、最大流、增广链的概念。9．掌握求解最大流问题的标号算法步骤。能力点1．能够将实际问题转换为物资调运问题（运输问题），并正确建立模型。2.能够利用软件求解物资调运模型，并解释调运方案。3．能够利用Dijkstra算法求解最短路问题。4.能够利用标号算法求解最大流问题。能力点水泥的合理调运问题下表５-１是1983年广东省转窑水泥调拨的数量和水泥厂到各地、市的单位运输成本。如果某一水泥厂至某一地区的运输是明显不合理或不可能，则这条路线上的运杂费被视为无穷大，表明“此路不通”，表中的空格，就是表示这种情况。试对该水泥调运问题进行求解，寻找最优的调运方案，并求出最低的总运输成本是多少？表5-1水泥调运的运输成本和供需量引导案例引导案例水泥厂用户广州英德英德（托盘）茂名进口（中转）进口（直达）需求量梅县59.0120.062.07290汕头47.179.749.521.036940潮州53.486.053.91090惠阳21.830.062.322.213140深圳21.222.021.350.021.66080韶关30.312.630.312780肇庆25.243.046.060.129.213680佛山12.321.051.028.016460江门21.237.051.128.01130珠海21.237.549.029.03800湛江47.112.647.521.012720茂名59.612.560.0335海南50.250.850.225.010830自治州54.370.054.740.05950广州12.612.652.125.022655供应量61520156801887056502756035600164880子情境1物资调运问题建模及求解一、物资调运问题的含义二、物资调运问题的数学模型三、物资调运问题的建模四、物资调运问题的求解及解释将库存物资运往需求者所在地，以满足需求者的要求，如何组织物资的运输，就是物资调运问题。物资调运问题物资调运问题的内容物资调运问题的内容是在几个供应点与几个需求点之间，运输品种、规格、质量等相同的货物时，选择最佳的运输方案，以达到总的运输费用最低或获得的利润最大等目标。一、物资调运问题的含义若某种物资有有m个产地

，和n个销地

，其总产量等于总销量。现在需要将该物资从各个产地运到各个销地，已知各产地的产量、各销地的销量以及各产地到各销地的运距（或单位运价）。问应如何组织调运，才能使总运输量（或总运输费用）最少？物资产销（供需）平衡的运输问题二、物资调运问题的数学模型假设产销平衡，即运输问题的数学模型二、物资调运问题的数学模型运输问题的数学模型二、物资调运问题的数学模型三、物资调运问题的建模-产销平衡问题例5-1

某物流公司运输产品，下设三个配送中心，每日的供应量分别是：A1为7吨，A2为4吨，A3为9吨。该公司将这些产品分别运往四个工厂。各工厂每日需求量：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各配送中心到各工厂的单位产品的运价，问该公司应如何调运产品，在满足各工厂需求量的前提下，使总运费最少？具体数据如表5-2所示。

表5-2B1B2B3B4产量A13113107A219254A3741059销量365620三、物资调运问题的建模-产销不平衡问题当产量大于销量（销量大于产量）时，应虚设一个销地（产地），使其销量（产量）为总产、销量的差额，单位运费为零，在不表上增加一列（行），即可化为平衡问题。反之，虚设一个产地。表5-10B1B2B3B4产量A1211347A2103595A378127销量2346例5-2

设有A1、A2、A3三个产地生产某种物资，其产量分别为7、5、7t，四个销地B1、 B2、B3、B4需用该种物资，销量分别为2、3、4、6t，又知各产销地之间的单位运价如表5-10所示。试确定总运费最省的调运方案。某工地有3个高地A1、A2、A3和4个洼地B1、B2、B3、B4，希望用高地的土有计划地填平洼地。设各个高地的出土量和各个洼地的填土量，各个高地与各个洼地之间的距离如表5-13所示。表5-13出填土距离及运量平衡表B1B2B3B4出土量A11052370A2431220A3563410填土量50251015100课堂练习四、物资调运问题的求解及解释插件安装输入模型求解模型最优方案情境五物流运输规划子情境2子情境3物资调运问题建模及求解运输最短路径问题及其求解运输网络最大流问题及其求解子情境1知识点知识点1．理解物资调运问题的经济含义。2．掌握物资调运问题的实质。3．掌握物资调运问题建模方法。掌握物资调运问题的求解。5．理解图、网络、链的基本概念。6．理解最短路问题的含义。7．掌握求解最短路问题的Dijkstra算法步骤。8．理解可行流、最大流、增广链的概念。9．掌握求解最大流问题的标号算法步骤。能力点1．能够将实际问题转换为物资调运问题（运输问题），并正确建立模型。2.能够利用软件求解物资调运模型，并解释调运方案。3．能够利用Dijkstra算法求解最短路问题。4.能够利用标号算法求解最大流问题。能力点下图是某乡下属的7个村间的公路交通图，各条边旁边的数字是该条公路的长度（单位：千米(km)）。已知各村的玉米产量为v1——30（kt下同），v2—40，v3—25，v4—20，v5—50，v6—60，v7—60，乡粮库建在哪个村子，才能使收购各村玉米时所用的千吨·千米(kt·km)数最小？引导案例粮库的选址问题v1v2v3v4v5v6v752762247136子情境2运输最短路径问题及其求解一、运输路径规划问题二、图的概念与模型

三、最短路的含义

四、最短路的Dijkstra算法运输路径规划：运输路径规划问题种类：一、运输路径规划问题路径是指物品运输的路线，网络是指物品运输的地点与路径的总和，运输路径规划是物流运输过程中的最重要环节，是在一定的运输网络（公路网、铁路线、水运航道和航空线）内，找到运输工具的最短运输线路、最大运输流量的线路分布、运输量最小的线路网布局、运输工作量最小的配送路线安排等路径规划方案。一是最短运输线路选择的最短路法；二是最大网络流量分布的最大流法；三是最小运输量线路网布局的最短树法；四是最佳配送线路策略制定的节约法。二、图的概念与模型图6-3所示是某地的公路交通图，vi表示城镇，城镇间的连线表示公路。例如连线v1v2

表示城镇v1和v2之间有公路相通，依此类推，v3和v5之间不存在连线，说明这两个城市时间没有直接的公路相通。v1v2v3v4v5图6-3某地的公路交通图二、图的概念与模型1．节点节点用来表示物理实体或事物，一般用vi

来表示。例如，图6-3中的节点就是各城镇。2．边边是节点间的连线，表示两节点之间有关系，一般用eij来表示。图6-3中的边就是各城镇之间的公路。二、图的概念与模型4．网络若对图的每一边定义一个表示连接关系的权值，用wij表示，则将该图称为网络。3．图

图是由一些节点和一些边组成的图形。所以，图一定是节点和边的集合。二、图的概念与模型5．链下图中相邻节点的序列

称为该图的一个链。如图6-5中的

就是一个链。v2v3v4v5e1v1e2e3e4e5e6e7图6-5连通图

线路选择问题：最短路问题的一般提法：三、最短路的含义在已知的物流网络（通过各段线路所需的时间、距离或费用为已知）中，有一货物发点（供应点）对一货物收点（客户）专门送货，在这种直送情况下找出货物运送所需的最少时间、最短距离或最少费用的路径问题。四、最短路的Dijkstra算法用dij表示图中两点i与j相邻时的距离，即边[i,j]的长度。若点i与j不相邻时，

dij=∞。显然dii=0。用

表示从点s到点i的最短路的长度。现在要求从点s到点t的最短路，相应的Dijkstra算法步骤如下：1从点s出发，逐一地给其它的点i标上记号：lsi

，把lsi

的数值标注在点i旁边的小方框内，表示点i已标号（标号说明点s到点i的最短路已找到）。首先，给点s标号lss=0。四、最短路的Dijkstra算法2找出与点s相邻的点中距离最小的一个，若有几个点同时达到最小，就都找出来。设找出的点为r，将lsr=lss+dsr

的值标注给点r，表明点r也已标号，同时把边[s,r]加粗。3从已标号的点出发，找出与这些点相邻的所有未标号的点。把每个已标号点旁标注的数字和与之相邻的点到这个已标号点间的距离加起来，从所有这些和中选出一个最小的来。再找出最小和对应的未标号点，然后给这个未标号点比如q标号：Lsq=lsk+dkg,，同时加粗边[k,q]。四、最短路的Dijkstra算法4重复第（3）步，直到给点t标上号

，而且相应的t的关联边加粗为止。例6-1

用Dijkstra算法求图6-1中从

到

的最短路。v1v2v3v4v5v6v752762247136四、最短路的Dijkstra算法v4v1v2v3v5v6v7527622471360图6-1（a）四、最短路的Dijkstra算法图6-1（b）v1v2v3v4v5v6v75276224713620四、最短路的Dijkstra算法图6-1（c）v1v2v3v4v5v6v752762247136205四、最短路的Dijkstra算法图6-1（d）v1v2v3v4v5v6v7527622471362605四、最短路的Dijkstra算法图6-1（e）v1v2v3v4v5v6v752762247136260577四、最短路的Dijkstra算法图6-1（f）v1v2v3v4v5v6v75276224713626057710四、最短路的Dijkstra算法★最短路问题在物流规划中处于很重要的地位下图是某乡下属的7个村间的公路交通图，各条边旁边的数字是该条公路的长度（单位：千米(km)）。已知各村的玉米产量为v1——30（kt下同），v2—40，v3—25，v4—20，v5—50，v6—60，v7—60，乡粮库建在哪个村子，才能使收购各村玉米时所用的千吨·千米(kt·km)数最小？引导案例粮库的选址问题v1v2v3v4v5v6v752762247136情境五物流运输规划子情境3子情境2物资调运问题建模及求解运输最短路径问题及其求解运输网络最大流问题及其求解子情境1知识点知识点1．理解物资调运问题的经济含义。2．掌握物资调运问题的实质。3．掌握物资调运问题建模方法。掌握物资调运问题的求解。5．理解图、网络、链的基本概念。6．理解最短路问题的含义。7．掌握求解最短路问题的Dijkstra算法步骤。8．理解可行流、最大流、增广链的概念。9．掌握求解最大流问题的标号算法步骤。能力点1．能够将实际问题转换为物资调运问题（运输问题），并正确建立模型。2.能够利用软件求解物资调运模型，并解释调运方案。3．能够利用Dijkstra算法求解最短路问题。4.能够利用标号算法求解最大流问题。能力点下图是某乡下属的7个村间的公路交通图，各条边旁边的数字是该条公路的长度（单位：千米(km)）。已知各村的玉米产量为v1——30（kt下同），v2—40，v3—25，v4—20，v5—50，v6—60，v7—60，乡粮库建在哪个村子，才能使收购各村玉米时所用的千吨·千米(kt·km)数最小？引导案例粮库的选址问题v1v2v3v4v5v6v752762247136子情境3运输网络最大流问题及其求解一、最大流的含义二、最大流的标号算法运输网最大流量分布问题：最大流问题的一般提法：一、最大流的含义在已知的物流网络（各段线路的通过能力、运输费用或运输时间为已知）中，有一货物发点（供应点）和一货物收点（客户），在这种情况下找出最佳流量安排（线路流量分配）方案，使通过网络的流量达到最大（或运输费用最省、或运输时间最小）。在有一个起点和一个终点的网络中，最大流问题是企图找出，在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量（不管它是物资、卡车、飞机、液体或电流）。即最大流问题，就是在一定条件下，要求流过网络的流量为最大的问题。一、最大流的含义（一）网络流量在一定条件下流过一个网络的总流量，它等于起点的总发量或终点的总收量。网络流量记作

，网络边上的实际流量记作fij。一、最大流的含义（二）可行流满足以下条件的流叫可行流（记为可行流f）：一、最大流的含义（三）最大流在一个网络中，流量达到最大值的可行流。求网络的最大流，就是指在满足上述（二）中条件1、2、3的前提下，使的值达到最大。一、最大流的含义（四）增广链如果从网络的发点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得不到标号，这表明该网