物流系统规划概述.pptx

《物流系统规划概述.pptx》由会员分享，可在线阅读，更多相关《物流系统规划概述.pptx（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3-2 物流系统规划物流系统规划1 概述概述2 物流调运规划物流调运规划3 物流分配规划物流分配规划4 其它应用问题其它应用问题11 概述概述2一一.物流系统规划概述物流系统规划概述q物流系统规划所关注的问题是如何合理、有效地利用或配置各种资源（劳动力、材料、设备、资金），使实现预定目标所需的费用最小（或资源最少），或者所获得的收益最大。q物流系统的规划一般都可以用优化模型来表达。其基本思想是在满足一定的约束条件下，求目标函数的最优解。q物流系统规划的数学基础：运筹学理论。常用的方法包括线性规划、整数规划、动态规划等。3二二.物流系统规划的目标任务物流系统规划的目标任务q提高物流系统的吞吐能力

2、以适应产量增长的要求；q建设柔性的物流系统，以适应产品经常变化的情况；q对生产过程中可能出现的各种意外情况或随机变化做出及时的响应，保持均衡生产；q改善劳动条件，减轻劳动强度；q对物流系统中的货物进行实时跟踪；q对物流系统的货物进行分类或选配，为随后的处理(加工或包装)提供方便条件。4三三.评价物流系统规划的主要指标评价物流系统规划的主要指标1.经济性。包括初始投资、每年的运营费用、直接或间接的经济效益、投资回收期、全员劳动生产率等；2.可靠性。包括单个环节的可靠性和整个系统的可靠性技术、设备故障率和排除故障所需的时间；3.可维护性。维护保养所要求的技术水平、备件的供应情况、所需储备的备件数量

3、；4.灵活性或柔性。适应产品设计更改和产量变化的能力，物流系统各环节与生产节奏相匹配的能力，调整物流路线的可能性；5.可扩展性。在物流系统的服务范围和吞吐能力方面进步扩大的可能性；6.安全性。包括产品的安全、人员的安全、以及正常运行和事故状态下的安全保障；7.劳动强度。需要劳动力的数量、劳动者的疲劳程度；8.易操作性。操作简单、不易出错，只需少量指令即可使设备和整个系统投入运行；9.服务水平。对顾客的要求做出快速响应的能力；10.环境保护。符合环境保护条理的要求，对周围环境的污染程度低。11.敏感性。对外界条件变动的敏感程度和适应能力。5四四.物流系统规划中的变量物流系统规划中的变量q影响物流

4、系统的控制因素分为两类v不可控因素：设计人员无法左右的种种前提条件。v可控因素：可以由规划设计人员在一定范围内选取的变量。（可控变量）q物流系统规划中一般通过调整可控变量去影响系统性能，达到系统的预期目标。v物流系统规划：通过调整可控变量，观察系统性能的变化趋势，从而选择可控变量的最佳匹配，达到系统的最佳效果。v不可控因素与物流系统性能有密切关系，其特点是不确定和无法控制，但在物流系统规划中仍需对其进行考察。如：顾客到达的时间，船舶到达的时间和数量。如：顾客到达的时间，船舶到达的时间和数量。62 物流系统调运规划物流系统调运规划7一一.问题描述问题描述q调运规划问题描述调运规划问题描述 设某种

5、要调运的物资，有一组供应点(产地或称发点)m个，一组需求点(销地或称收点)n个，如果每个供应点的供应量及每个需求点的需求量都已经确定，即第i个产地有ai 单位的物资发出，第j个需求点需要收进bj单位的物资；并且从每个产地到每一个销地的单位运价是已知的，假定把单位物资从第i个产地调运到第j个销地去的单位运价为cij。q调运规划问题也叫运输问题调运规划问题也叫运输问题q物资调运规划的目的：物资调运规划的目的：v制订一个合理的调运方案；v确定m个产地与n个销地之间的供需联系和数量的最优搭配；v确定具体的运输路线，使总的运输费用最低。8二二.确定产销地供需联系和收发量的模型及求解确定产销地供需联系和收

6、发量的模型及求解1.数学模型数学模型设供应点为Ai，该供应点的供应量是ai，（i=1,2,m）；设需求点为Bj，该需求点的需求量是bi，（j1,2,n）；cij为从第i个供应点到第j个需求点的单位运价；由供应点Ai发往需求点Bj的物资调运量是xij单位。假设m个供应点的总供应量等于n个需求点的总需求量，（供需平衡）。这时，由各供应点Ai调出的物资总量应等于它的供应量ai(i=1,2,m)；而每一个需求点Bj调入的物资总量应等于它的需求量bj(j=1,2,n)。目标函数：约束条件M个点的总供应n个点的总需求供应=需求（平衡问题）调运量非负92.模型求解模型求解v用线性规划方法求解（如单纯形法）。

7、用线性规划方法求解（如单纯形法）。v用表上作业法求解（针对这类问题的一种特殊解用表上作业法求解（针对这类问题的一种特殊解法）法）3.表上作业法的主要步骤表上作业法的主要步骤v首先依据问题列出调运物资的供需平衡表以及运价表；首先依据问题列出调运物资的供需平衡表以及运价表；v其次确定一个初始的调运方案其次确定一个初始的调运方案(当然不一定就是最优的方当然不一定就是最优的方案案)；v然后根据一个判定法则，判定初始方案是否为最优方案。然后根据一个判定法则，判定初始方案是否为最优方案。当判定初始方案不是最优方案时，再对这个方案进行调整。一般情况，每调整一次得到一个新的方案，而这个新方案的运费比前一个方案

8、要少些，如此经过几次调整，就会得到最优方案。10B1B2B3B4供应量供应量(t)A1311310700A21928400A374105900需求量需求量(t)3006005006002000工地工地料库料库运价运价表表5-1 某公司物资供应状况表某公司物资供应状况表4.4.表上作业法解题实例表上作业法解题实例例题1 某公司下属三个储存某种物资的仓库，供应四个工地的需要。三个仓库的供应量和四个工地的需求量以及由各仓库到各工地调运单位物资的运价(元吨)由表5-1给出，试求运输费用最少的调运方案。11解解：（：（1 1）列出物资调运平衡表和运价表）列出物资调运平衡表和运价表 B1B2B3B4供应量

9、供应量(t)A1700A2400A3900需求量需求量(t)3006005006002000需需供供运价运价表表5-2 供需平衡表供需平衡表表表5-3 运价表运价表B1B2B3B4A1311310A21928A374105料库料库运价运价工地工地v平衡表中填入的数字表示供需点之间的调运量；v空格表示双方不发生调运关系v平衡表和运价表是表上作业法的基本资料和运算的依据。v表上作业法的实质就是利用运价表在平衡表上进行求解。12（2 2）编制初始调运方案）编制初始调运方案 q物资调运规划其总的目的是寻求运输费用最少的最优调运方案。最优方案一般是由初始方案经过反复调整得到的。（因此，编制出较好的初始调

10、运方案非常重要。）q最好的调运方案是使运费最省少方案，因此用最小元素法来确定初始调运方案。最小元素法最小元素法：按运价表依次挑选运费少的供需点尽量优先安排供应的调运方法。13B1B2B3B4供应量供应量(t)A1700A2300400A3900需求量需求量(t)3006005006002000需需供供运量运量供需平衡表供需平衡表 运价表运价表B1B2B3B4A1311310A21928A374105料库料库运价运价工地工地1v 首先，在运价表内找出最小的运价，对本例而言，方格(2(2，1)1)数值是1，最小，这样，供应点A2尽可能地满足B1工地的需要，于是在平衡表中有(2(2，1)1)3003

11、00，即在空格(2，1)中填入数字300。v 此时，由于工地B1已经全部得到满足，不需要其他仓库供应给它了，运价表中的第一列数字己不起作用，因此将运价表第一列划去，并标注符号，14B1B2B3B4供应量供应量(t)A1700A2300100400A3900需求量需求量(t)3006005006002000需需供供运量运量供需平衡表供需平衡表 运价表运价表B1B2B3B4A1311310A21928A374105料库料库运价运价工地工地12v然后，在运价表未划去的各行、列中，再选取一个最小的运价，本例，即(2，3)2最小，让A2料库尽量供应满足B3工地的需要。由于A2库储量400t已供应给B1工

12、地300t了，所以最多还能供给B3工地100t。于是在平衡表(2，3)空空格填入格填入100；相应地由于仓库A2所储物资已全部供应完毕，因此，在运价表中与A2同行的运价也不再起作用，所以也将它们划去，并标注符号。15B1B2B3B4供应量供应量(t)A1400700A2300100400A3600300900需求量需求量(t)3006005006002000需需供供运价运价供需平衡表供需平衡表 运价表运价表B1B2B3B4A1311310A21928A374105料库料库运价运价工地工地12435v仿照前面的方法，一直作下去，就可得到如左图所示的运价表和平衡表。v 此时，在运价表中只有方格(1

13、(1，4)4)处的运价没有划掉，B4尚有300t的需求，而A1刚好还有300t的物资可以供应，为了满足供需平衡，所以最后在平衡表上应有(1(1，4)4)300300。这样就得到表56的初始调运方案。16B1B2B3B4供应量供应量(t)A1400300700A2300100400A3600300900需求量需求量(t)3006005006002000需需供供运量运量表表5-6 初始调运方案初始调运方案3524根据初始调运方案的运输量和单位运价，可以计算初始调运方案的运输费用为：S=1*300+4*600+3*400+2*100+10*300+5*300=8600(元)110价格价格运量运量17

14、（3 3）初始方案的检验与调整）初始方案的检验与调整1）最优方案的数字表征）最优方案的数字表征检验数检验数q相关概念相关概念闭回路闭回路：对表上作业法的初始方案，从调运方案表上的一个对表上作业法的初始方案，从调运方案表上的一个空格出发，存在空格出发，存在条且仅存在一条以该空格条且仅存在一条以该空格(用用 xij 表示表示)为起为起点，以其他填有数字的点为其他顶点的闭合回路，简称闭回点，以其他填有数字的点为其他顶点的闭合回路，简称闭回路。路。v每个顶点都是闭合回路的转角点；v闭合回路是一条封闭折线，每一条边都是水平或垂直的；v每一行(列)若有闭合回路的顶点，则必有两个（起点所在的行（列）除外）。

15、v任一空格的闭合回路不仅是存在的，而且是唯一的。v只有从空格出发，其余各转角点所对应的方格内均填有数字时，所构成的闭合回路，才是我们这里所说的闭回路。18 空格空格(1，1)：(1，1)(1，3)(2，3)(2，1)一一(1，1)空格空格(3，1)：(3，I)(2，1)(2，3)(1，3)一一(1，4)(3，4)(3，1)对所有的空格，都可以用同样的方法画出一条闭回路。对所有的空格，都可以用同样的方法画出一条闭回路。B1B2B3B4供应量供应量(t)A1400300700A2300100400A3600300900需求量需求量(t)3006005006002000需需供供19 检验数检验数：调

16、运方案的每个空格所形成的闭回路上，作单位物资的运量调整，总可以计算出相应的运费是增加还是减少。把计算出来的每条闭回路上调整单位运量而使运输费用发生变化的增减值，称其为检验数。v如果检验数小于零，表示在该空格的闭回路上调整运量使运费减少；v如果检验数大于零，则表示在该空格的闭回路上调整运量会使运费增加。最优方案的判定准则：最优方案的判定准则：初始调运方案中，如果它所有的检验数都是非负的(=0)，那么这个初始调运方案一最优。否则。这一调运方案不一定是最优的。（如果所有空格的检验数都大于零，再对调运方案进行任何调整，都会增加运输费用）202）求检验数的方法）求检验数的方法位势法位势法将初始调运方案中

17、填有运量的方格填有运量的方格对应的运价cij分解为两部分，即：cij=ui+vj,(对应前面的例题，i=1,2,3;j=1,2,3,4)其中ui和vj分别为该方格对应于i行和j列的位势量.B1B2B3B4uiA1310U1=2A212U2=1A345U3=-3viv1=0v2=7v3=1v4=8需需供供C21=u2+v1=1C23=u2+v3=2C13=u1+v3=3C34=u3+v4=57个未知量，六个方程假定其中一个未知量为假定其中一个未知量为0（任意），如假定（任意），如假定v1=0,则可则可以根据左边的方程解出全部未知量。以根据左边的方程解出全部未知量。位势计算表位势计算表第第1 1步

18、：求位势量步：求位势量21B1B2B3B4uiA129310U1=2A21829U2=1A3-34-25U3=-3viv1=0v2=7v3=1v4=8需需供供准检验数表准检验数表按按ui+vj求出各求出各空格的位势量空格的位势量，得到，得到准检验数表准检验数表（加方括号表示）（加方括号表示）准检验数计算过程准检验数计算过程空格（1，1）=u1+v1=2+0=2 （3，1）=u3+v1=-3+0=-3 （1，2）=u1+v2=2+7=9 （2，2）=u2+v2=1+7=8 （3，3）=u3+v3=-3+1=-2 （2，4）=u2+v4=1+8=9第第2 2步：求准检验数步：求准检验数22B1B2

19、B3B4A129310A21829A3-34-25第第3 3步：求检验数步：求检验数 运价表运价表B1B2B3B4A1311310A21928A374105 准检验数表准检验数表 利用运价表与准检验数表求检验数利用运价表与准检验数表求检验数 检验数表检验数表B1B2B3B4A112A21-1A31012“运价表运价表”减减“准检验数表准检验数表”检验结果：检验结果：检检验数出现负值，验数出现负值，根据最优方案根据最优方案判断准则，该判断准则，该方案不是最优方案不是最优方案。方案。233）调整调运方案）调整调运方案q当判定一个初始调运方案不是最优调运方案时，就要在检验数出现负在检验数出现负值的该

20、空格内进行调整值的该空格内进行调整。q如果检验数是负值的空格不只一个时，一般选择检验数为负值且绝对值最大的空格作为调整对象。X13400+100=500X14300-100=200X23100-100=0X240+100=100B1B2B3B4A1400300A2300100负A3600300调整过程：（1）作出负值所在空格的闭回路，本例为空格x24，闭回路如上图所示。（2）沿闭回路在各奇数次转角点中挑选运量的最小数值作为调整量挑选运量的最小数值作为调整量。本例是将x x2323方格的方格的100100作为调整量，将这个数填入空格x24内，同时调整该闭回路中其他转角点上的运量，使各行、列保持原

21、来的供需平衡这样便得到一个新的调运方案。24B1B2B3B4供应量(t)A1500200700A23000100400A3600300900需求量(t)3006005006002000需需供供运量运量调整后的调运方案调整后的调运方案13524108B1B2B3B4A122A241A3912调整后的检验数调整后的检验数通过计算其检验数全部非负，此通过计算其检验数全部非负，此方案为最优方案。方案为最优方案。运输费用为：运输费用为：S3500十十10200十十8100十十1300十十4600十十5300 8500(元元)该值小于初始调运方案的总运费。该值小于初始调运方案的总运费。25(4)(4)表上

22、作业法基本步骤小结表上作业法基本步骤小结列出调运物资的供需(产销)平衡表及运价表；按最小元素法建立初始调运方案；采用位势法计算初始方案每个空格的闭回路的检验数xij；检查检验数，如果所有xij=0，说明方案是最优的，已经得到我们想要的方案，结束求解；如果有某个或某几个xij0，则选择负检验数中绝对值最大的闭回路进行调整，建立新的方案；重复35步，直至获得最优调运方案。26(5)(5)供需不平衡的物资调运问题供需不平衡的物资调运问题 求解思路：求解思路：通过虚设一个供应点或者需求点，将其转化通过虚设一个供应点或者需求点，将其转化为平衡运输问题求解。为平衡运输问题求解。供应量大于需求量供应量大于需

23、求量 引入一个虚设的需求点，令其的需求量等于实际问题中引入一个虚设的需求点，令其的需求量等于实际问题中供应量与需求量之差，令其运价为供应量与需求量之差，令其运价为0 0。需求量大于供应量需求量大于供应量 虚设一个供应点。令这个虚设的供应点的供应量等于实虚设一个供应点。令这个虚设的供应点的供应量等于实际问题中需求量与供应量的差额，运价为际问题中需求量与供应量的差额，运价为0 0。27三三.运输线路选择运输线路选择q运输路线的选择是物资调运规划的一个重要内容。运输路线的选择是物资调运规划的一个重要内容。运输路线直接影响到运输效果的好坏，关系着物资能否及时运到指定地点。当单位运输费用以吨吨公里公里来

24、计算时，运输路线的长短就直接关系着运输费用的多少。求解运输线路选择的方法很多，本书采用图上作业法来进行运输线路选择。281.交通示意图的表示方法交通示意图的表示方法 交通示意图用来表明收发点的大致位置、收发量、交通路线长度的图形。图形表示方法图形表示方法：（1）发点（产地或仓库）用符号表示，里面的数字表示发货量；（2）收点用（需求地）用符号表示，里面的数字表示收货量；（3）两点间的连线为交通线，其长度记在交通线旁边。（4）物资调运的方向(流向)用符号表示，并把按物资调运方向画在交通交通线的右边线的右边，把调运物资的数量记在的右边右边，并加上括号，以表示和交通线长度区别。201520510物资调

25、运交通流向图20（20）102010（5）（15）（10）292.图上作业法图上作业法v目的：根据交通流向图，找出运输力量最小的方案。v方法：通过消除调运中的对流和迂回两种不合理运输。30（1 1）对流对流 同一物资在同一线路上的往返运输。同一物资在同一线路上的往返运输。如下面的图，将某物资10吨，从A1运到B2，而又有同样的物资10吨，在同一期间从A2运到B1，于是A1A2间就出现了对流现象。10101030304030（10）（10）A1A2B1B2 如果从图上看，对流可以理解为同一条交通线上，有两条或两条以上的物资调运方向。10101030304030（10）A1A2B1B2（10）消除

26、消除对流对流运力：30*10+20*10=600运力：30*10+40*10+40*10+30*10=140031（2 2）迂回）迂回 迂回：迂回：在交通图成圈的时候，如果流向图中内圈流向的总长在交通图成圈的时候，如果流向图中内圈流向的总长(简称内简称内流长流长)或外圈流向的总长或外圈流向的总长(简称外流长简称外流长)超过整个圈长的超过整个圈长的半，就称为迂半，就称为迂回运输。回运输。内、外圈的概念内、外圈的概念：由于表示调运方向的箭头，要按调运方向画在交通线的右边，因此,流向图中，有些流向就在圈外（称为外圈流向）；有些流向在圈内（称为内圈流向）。556千米千米AB（5吨）吨）4千米千米556

27、千米千米AB（5吨）吨）4千米千米迂回运输迂回运输无迂回运输无迂回运输迂回运输：运力 6*5=30吨.千米无迂回运输：运力 4*5=20吨.千米32例题，下图为一运输交通图例题，下图为一运输交通图该交通图的运输线路构成圈。圈的总长=2+3+4+4=13内圈长=4+3=7内圈长大于总圈长的一半，为迂回运输运力：3*30+4*20+4*10=210修改后：内圈长=3外圈长=2+4=6内圈长、外圈长都小于总圈长的一半，不存在迂回运输运力：2*10+3*20+4*30=200节省运力：210-200=1010303050243（20）A1B2A24B1（30）（10）10303050243（30）A1

28、B2A24（20）（10）修改修改33物资调运问题的图上作业法物资调运问题的图上作业法q消除运输过程中的对流和迂回，节省运输力量。q具体步骤：v先画出一个没有对流的运输方案.v再检查有没有迂回，如果没有迂回，这方案就是最优方案；v如果有迂回，则对方案进行调整，直至消除迂回现象为止。q在实际的物资调运中，运输线路可以分为两种情况：交通线路成圈交通线路不成圈343.交通路线不成圈交通路线不成圈例题3有某物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7(万吨)，运往B1，B2，B3，B4，收量分别为8，1，3，5(万吨)，收发量平衡，交通路线如图58所示，问应如何调运，才使运输吨

29、千米最小？558（5）A1B127313A2A3A4B2B3B4558A1B127313A2A3A4B2B3B4交通线路图交通线路图调运流向图调运流向图解：该交通线路不成圈，只需要做一没有对流的调运图。方法：从各端点开始，由外到里，逐步进行各收发点之间的平衡（2）（1）（2）（1）（7）（5）354.4.交通路线成圈交通路线成圈例题4 有某物资7万吨，由A1，A2，A3发出，发量分别为3，3，1(万吨)，运往B1，B2，B3，B4，收量分别为2，3，1，1(万吨)，收发量平衡，交通路线如图510所示，问应如何调运，才使运输吨千米最小？113334B4A3213A1A2B1B3B27543243

30、6113334B4A3213A1A2B1B3B2754324解:(1)作一个没有对流的流向图作一个没有对流的流向图。方法：用“去线破圈”的方法。去一线破一圈，有几个圈去掉几条线，把有圈的交通图，转化为不成圈的交通图。技巧：一般先去掉长度最长的交通线，比如本例中去掉A1B4(7千米)，破A1B1B2A3B4圈；再去掉A3B3线(4千米)，破B2A2B3A3圈。这样，原来有圈的交通图，变成了不成圈的交通图如图511所示。从各个端点开始，做一个没有对流的流向图113334B4A3213A1A2B1B3B2754324（1）（3）（1）（2）（1）37(2)(2)检查有无迂回检查有无迂回。方法：对流向

31、图中的各圈进行检查，如果没有迂回，则这个初始方案就是最优方案，如果其中某圈中有迂回，则不是最优方案，需要改进。113334B4A3213A1B1B3B2754324（1）（3）（1）（2）（1）A1B1B2A3B4总圈长=7+3+4+4+5=23外流长=5+4+3=12存在迂回，需要调整存在迂回，需要调整。B2A2B3A3总圈长=4+3+2+4=13内流长=3外流长=2不存在迂回，不需要调整不存在迂回，不需要调整A238113334B4A3213A1B1B3B2754324（1）（3）（1）（2）A2调整方法：1）在外圈的各流量中，减去外圈的最小流量1万吨；2）在内圈的各流量中加上1万吨，在此

32、圈中，因无内流量，故不加。3）在无流量的线路上，新添加内圈流量1万吨。（-1）（-1）（-1）（+1）（+1）（1）39113334B4A3213A1B1B3B2754324（2）（2）A2（1）（1）A1B1B2A3B4总圈长=7+3+4+4+5=23外流长=5内流长=7+4=11不存在迂回不存在迂回。B2A2B3A3总圈长=4+3+2+4=13内流长=3外流长=4+2=6不存在迂回不存在迂回此方案为最优调运方案此方案为最优调运方案总运力：1*7+2*5+1*4+2*3+1*2=29万吨千米（1）40四四.最短路与最大流最短路与最大流 1.最短路线最短路线例题5某家运输公司签定了一项运输合同

33、，要把A市的一批货物运送到B市。该公司根据两个城市之间可选择的行车路线地图，绘制了图513的公路网络。要求从交通网络图中，寻找一条线路最短的运输路线。1A市市4523769810B市市100150175300275200175275200300200400250125100150q 图中 为结点，代表起点、目的地和与行车路线相交的其他城市，其中的数字为结点编号。q箭头为分支，代表两个结点之间的公路，箭头上标明的数字为运输里程。公路网络公路网络141解：从终点开始逐步逆向推算。(1)与终点10联接的结点有两个，即结点9和8；从结点9到结点10只有一条线路，该线路为最短线路，长度100，记为：（9

34、-10）100；同样，结点8到结点10的最短线路为150，记为（8-10）150；(2)结点6。与6联接的只有一个结点9，6至9的最短里程为200。而9至终点10的最短里程为100因此6至终点10的最短里程为200十100300。记为：(6-9-10)300。(3)结点5。与5联接的结点有9、8两个。5至9再至终点的最短里程为400十100500，5至8再至终点的最短里程为250十155400。400500，所以5至终点的最短里程为400，记为：(5-8-10)400。(4)结点7。至终点的最短里程为125十150275，记为：(7-8-10)275。1A市市4523769810B市市1001

35、5017527520017527520030020040025012510015030042(5)结点4。与4联接的结点有5、6、7三个。结点4至6再到终点的最短里程为200十300=500；结点4至5再到终点的最短里程为175十400575；结点4至7再到终点的最短里程为275十275550。三个里程中以500为最小，所以结点4至l 0的最短里程记为(46910)500(46910)500。(6)结点2和3。用同样的方法，得到：结点2到终点的最短里程为600。记为：(26910)600(26910)600。结点3到终点的最短里程为575。记为：(37810)575(37810)575。(5)

36、最后看结点1。结点1可以通过三个结点2、3、4连接到终点。结点1通过结点2再到终点的最短里程100十600700，路径为（126910126910）700700；结点1通过结点4再到终点的最短里程150十500650，路径为（146910146910）650650；结点1通过结点3再到终点的最短里程175十575750，路径为（137810137810）750750。以上三个里程中以650为最小，即A币到B市的最短里程，对应的最短路线为：146910146910。1A市市4523769810B市市1001501752752001752752003002004002501251001503004

37、3q最短路线法的应用最短路线法的应用v物资的运输路线的选择v物流渠道的设计v电缆架设v管道铺设v个人旅行中442.最大流最大流v当要把大量货物运输到指定的地点时，有时会希望找到一条交通量最大的路线，以使货物能在最短时间内到达。这就是要在有一个起点和一个终点的网络中，找出在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量问题。15234566433572起点起点终点终点1结点通过能力交通线路45运输网络最大流量的计算运输网络最大流量的计算 例题：某城市从北到南的交通，平时是利用85号公路进行的。目前因为85号公路要进行路面维修，车辆不能通过。技术人员查明：在维修期间可以利用市区的其

38、它几条路线通行，现在需要确定这几条线路组成的交通网络能否满足每小时6000辆汽车的通过能力。15234566433572北北南南该市从北到南的临时交通网络如上图所示，交通线路旁边的数字表示单位时间内汽车的通过能力（每小时千辆）。现在要求从结点1通过公路网到结点6的最大通过能力（最大流量）。846计算方法计算方法（1）任意选择一条从起点到终点的路线。例如，选择路线1-2-5-61-2-5-6。v首先找出这条路线上流量能力最小的支线。从图上可以看出：56支线流量最小，其流量为2，表明沿“1-2-5-6”支线南驶的汽车，每小时的最大流量只能是2千辆，因为5-6支线限制了全线的车流量。v其次把这条路线

39、上每条支线的流量减去2。差值则表示该支线剩余的流量。将差值其写在原来的流量能力的旁边，并把原来的流量划掉；把减数2写在每条支线的终点，在减数2的右下角注上(1)，如2（1），表示第一条路线的流量能力为2千辆。标注方式如图所示。15234566 44 233572 0北北南南2（1）2（1）2（1）47(2)另选一条从起点1到终点6的路线，如：1-4-61-4-6。以该路线上最小的流量能力3为减数，减去各条支线上的流量。其差数、减数的记入方法同上。在差数3的右下角注上(2)，表示第二条路线的流量能力为3千辆。15234566 44 23 0357 42 0北北南南2（1）2（1）2（1）3（2）

40、3（2）48（3）再选一条从起点1到终点6的路线，如1-3-4-61-3-4-6。以该路线上最小的流量能力3为减数，减去各条支线上的流量，其差数、减数的记入方式同上。第三条路线的流量能力为3干辆（4）在剩下的流量图中，已经找不到一条完整的路线，满足所有支路流量大于0的条件，因此能够通行的交通路线已经全部标出。（5）网络的最大交通能力第一条线路1-2-5-6，流量2千辆/小时；第二条线路1-4-6，流量3千辆/小时；第三条线路1-3-4-6，流量3千辆/小时；该该交交通通网网络络的的从从北北到到南南的的最最大大通通行行流流量量为为2+3+3=82+3+3=8千千辆辆/小小时时。满满足足每每小时小时60006000辆的通过能力。辆的通过能力。15 2234566 44 23 03 057 4 12 0北北南南2（1）2（1）2（1）3（2）3（2）3（3）3（3）3（3）49