物流系统规划一课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,*,物流系统规划一,物流系统规划一物流系统规划一,5.1,概述,2,一,.,物流系统规划概述,物流系统规划所关注的问题是如何合理、有效地利用或配置各种资源（劳动力、材料、设备、资金），使实现预定目标所需的费用最小（或资源最少），或者所获得的收益最大。,物流系统的规划一般都可以用优化模型来表达。其基本思想是在满足一定的约束条件下，使预定的目标值达到最优。,物流系统规划的数学基础主要是运筹学理论，常用的方法包括线性规划、整数规划、动态规划等。,3,二,.,物流系统规划的目标任务,提高物流系统的吞吐能力以适应产量增长的要求；,建设一个柔性的物流系统，以适应产品经常变化的情况；,对生产过程中可能出现的各种意外情况或随机变化做出及时的响应，保持均衡生产；,改善劳动条件，减轻劳动强度；,对物流系统中的货物进行实时跟踪；,对物流系统的货物进行分类或选配，为随后的处理,(,加工或包装,),提供方便条件。,4,三,.,评价物流系统规划的主要指标,经济性,。包括初始投资、每年的运营费用、直接或间接的经济效益、投资回收期、全员劳动生产率等；,可靠性,。包括单个环节的可靠性和整个系统的可靠性技术、设备故障率和排除故障所需的时间；,可维护性,。维护保养所要求的技术水平、备件的供应情况、所需储备的备件数量；,灵活性或柔性,。适应产品设计更改和产量变化的能力，物流系统各环节与生产节奏相匹配的能力，调整物流路线的可能性；,可扩展性,。在物流系统的服务范围和吞吐能力方面进,步扩大的可能性；,安全性,。包括产品的安全、人员的安全、以及正常运行和事故状态下的安全保障；,劳动强度,。需要劳动力的数量、劳动者的疲劳程度；,易操作性,。操作简单、不易出错，只需少量指令即可使设备和整个系统投入运行；,服务水平,。对顾客的要求做出快速响应的能力；,环境保护,。符合环境保护条理的要求，对周围环境的污染程度低。,敏感性,。对外界条件变动的敏感程度和适应能力。,5,四,.,物流系统规划中的变量,物流系统规划中的控制因素分为两类,不可控因素：设计人员无法左右的种种前提条件。,可控因素：可以由规划设计人员在一定范围内选取的变量。,明确了物流系统中可控变量和不可控因素，就能知道加何去影响系统的性能，达到所追求的目标。,物流系统的规划一般是通过调整可控变量观察系统性能的变化趋势，从而选择可控变量的最佳匹配，达到系统的最佳效果。,物流系统的功能除了受可控变量的影响外，还与不可控因素有密切的关系。通常，不可控因素不是非常确定的。,6,5.2,物流系统调运规划,7,一,.,问题描述,调运规划问题描述,设 某种要调运的物资，有一组供应点,(,产地或称发点,)m,个，一组需求点,(,销地或称收点,)n,个，如果每个供应点的供应量及每个需求点的需求量都已经确定，即第,i,个产地有,a,i,单位的物资发出，第,j,个需求点需要收进,b,j,单位的,物资；并且从每,个产地到每一个销地的单位运价是已知的，假定把单位物资从第,i,个产地调运到第,j,个销地去的单位运价为,c,ij,。,调运规划问题也叫运输问题,物资调运规划的目的：,制订一个合理的调运方案；,确定,m,个产地与,n,个销地之间的供需联系和数量的最优搭配；,确定具体的运输路线，使总的运输费用最低。,8,二,.,确定产销地之间的供需联系和收发量,1.,数学模型,设供应点为,A,i,，该供应点的供应量是,a,i,，,（,i=1,2,m,）,；,设需求点为,B,j,，该需求点的需求量是,b,i,，（,j,1,2,n,）；,c,ij,为从第,i,个供应点到第,j,个需求点的单位运价；,由供应点,A,i,发往需求点,B,j,的物资调运量是,x,ij,单位。,假设,m,个供应点的总供应量等于,n,个需求点的总需求量，（这样，调运问题满足供需平衡，称为平衡运输问题）。这时，由各供应点,A,i,调出的物资总量应等于它的供应量,a,i,(i=1,2,m),；而每一个需求点,B,j,调入的物资总量应等于它的需求量,b,j,(j=1,2,n),。,目标函数：,约束条件,9,二,.,确定产销地之间的供需联系和收发量,2.,模型求解,用线性规划方法求解（如单纯形法）。,用表上作业法求解（针对这类问题的一种特殊解法）,3.,表上作业法的主要步骤,首先依据问题列出调运物资的供需平衡表以及运价表；,其次确定一个初始的调运方案,(,当然不一定就是最优的方案,),；,然后根据一个判定法则，判定初始方案是否为最优方案。,当判定初始方案不是最优方案时，再对这个方案进行调整。,一般情况，每调整一次得到一个新的方案，而这个新方案的运费比前一个方案要少些，如此经过几次调整，就会得到最优方案。,10,B,1,B,2,B,3,B,4,供应量,(t),A,1,3,11,3,10,700,A,2,1,9,2,8,400,A,3,7,4,10,5,900,需求量,(t),300,600,500,600,2000,工地,料库,运价,表,5-1,某公司物资供应状况表,二,.,确定产销地之间的供需联系和收发量,4.,表上作业法解题实例,例题,1,某公司下属三个储存某种物资的仓库，供应四个工地的需要。三个仓库的供应量和四个工地的需求量以及由各仓库到各工地调运单位物资的运价,(,元吨,),由表,5,1,给出，试求运输费用最少的调运方案,。,11,解,：（,1,）列出物资调运平衡表和运价表,B,1,B,2,B,3,B,4,供应量,(t),A,1,700,A,2,400,A,3,900,需求量,(t),300,600,500,600,2000,需,供,运价,表,5-2,供需平衡表,表,5-3,运价表,B,1,B,2,B,3,B,4,A,1,3,11,3,10,A,2,1,9,2,8,A,3,7,4,10,5,料库,运价,工地,平衡表中填入的数字表示供需点之间的调运量；,空格表示双方不发生调运关系,平衡表和运价表是表上作业法的基本资料和运算的依据。,表上作业法的实质就是利用运价表在平衡表上进行求解。,二,.,确定产销地之间的供需联系和收发量,12,（,2,）编制初始调运方案,物资调运规划其总的目的是寻求一个运输费用最少的最优调运方案。一般最优方案是由初始方案经过反复调整得到的。因此，编制出较好的初始调运方案非常重要。,最好的调运方案是使运费最省的方案，因此可以用最小元素法来确定初始调运方案。,所谓最小元素法，就是按运价表依次挑选运费少的供,需点尽量优先安排供应的调运方法。,二,.,确定产销地之间的供需联系和收发量,13,B,1,B,2,B,3,B,4,供应量,(t),A,1,700,A,2,300,400,A,3,900,需求量,(t),300,600,500,600,2000,需,供,运量,供需平衡表,运价表,B,1,B,2,B,3,B,4,A,1,3,11,3,10,A,2,1,9,2,8,A,3,7,4,10,5,料库,运价,工地,1,首先，在运价表内找出最小的运价，对本例而言，方格,(2,，,1),数值是,1,，最小，这样，供应点,A,2,尽可能地满足,B,1,工地的需要，于是在平衡表中有,(2,，,1),300,，即在空格,(2,，,1),中填入数字,300,。,此时，由于工地,B,1,已经全部得到满足，不需要其他仓库供应给它了，运价表中的第一列数字己不起作用，因此将运价表第一列划去，并标注符号,，,B,1,B,2,B,3,B,4,供应量,(t),A,1,700,A,2,300,100,400,A,3,900,需求量,(t),300,600,500,600,2000,需,供,运量,供需平衡表,运价表,B,1,B,2,B,3,B,4,A,1,3,11,3,10,A,2,1,9,2,8,A,3,7,4,10,5,料库,运价,工地,1,2,然后，在运价表未划去的各行、列中，再选取一个最小的运价，本例，即,(2,，,3),2,最小，让,A,2,料库尽量供应满足,B,3,工地的需要。由于,A,2,库储量,400t,已供应给,B1,工地,300t,了，所以最多还能供给,B3,工地,100t,。于是在平衡表,(2,，,3),空格填入,100,；相应地由于仓库,A,2,所储物资已全部供应完毕，因此，在运价表中与,A,2,同行的运价也不再起作用，所以也将它们划去，并标注符号,。,B,1,B,2,B,3,B,4,供应量,(t),A,1,400,700,A,2,300,100,400,A,3,600,300,900,需求量,(t),300,600,500,600,2000,需,供,运价,供需平衡表,运价表,B,1,B,2,B,3,B,4,A,1,3,11,3,10,A,2,1,9,2,8,A,3,7,4,10,5,料库,运价,工地,1,2,4,3,5,仿照前面的方法，一直作下去，就可得到如左图所示的运价表和平衡表。,此时，在运价表中只有方格,(1,，,4),处的运价没有划掉，,B4,尚有,300t,的需求，而,A1,刚好还有,300t,的物资可以供应，为了满足供需平衡，所以最后在平衡表上应有,(1,，,4),300,。这样就得到表,5,6,的初始调运方案。,B,1,B,2,B,3,B,4,供应量,(t),A,1,400,300,700,A,2,300,100,400,A,3,600,300,900,需求量,(t),300,600,500,600,2000,需,供,运量,表,5-6,初始调运方案,3,5,2,4,根据初始调运方案的运输量和单位运价，可以计算初始调运方案的运输费用为：,S=1*300+4*600+3*400+2*100+10*300+5*300=8600(,元,),1,10,价格,运量,（,3,）初始方案的检验与调整,1,）最优方案的数字表征,检验数,相关概念,闭回路,：,对表上作业法的初始方案，从调运方案表上的一个空格出发，,存在,条且仅存在一条,以该空格,(,用,x,ij,表示,),为起点，以其他填有数字的点为其他顶点的闭合回路，简称闭回路。,每个顶点都是闭合回路的转角点；,闭合回路是一条封闭折线，每一条边 都是水平或垂直的；,每一行,(,列,),若有闭合回路的顶点，则必有两个（起点所在的行（列）除外）。,任一空格的闭合回路不仅是存在的，而且是唯一的。,只有从空格出发，其余各转角点所对应的方格内均填有数字时，所构成的闭合回路，才是我们这里所说的闭回路 。,二,.,确定产销地之间的供需联系和收发量,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),对所有的空格，都可以用同样的方法画出一条闭回路。,B,1,B,2,B,3,B,4,供应量,(t),A,1,400,300,700,A,2,300,100,400,A,3,600,300,900,需求量,(t),300,600,500,600,2000,需,供,二,.,确定产销地之间的供需联系和收发量,19,检验数,：,调运方案的每个空格所形成的闭回路上，作单位物资的运量调整，总可以计算出相应的运费是增加还是减少。我们把所计算出来的每条闭回路上调整单位运量而使运输费用发生变化的增减值，称其为检验数。,如果检验数小于零，表示在该空格的闭回路上调整运量使运费减少；,如果检验数大于零，则表示在该空格的闭回路上调整运量会使运费增加。,最优方案的判定准则：,初始调运方案中，如果它所有的检验数都是非负的，那么这个初始调运方案一最优。否则。这一调运方案不一定是最优的。,（如果所有空格的检验数都小于零，那么如果再对调运方案进行任何调整，都会增加运输费用）,二,.,确定产销地之间的供需联系和收发量,20,2,）用位势法求检验数,将初始调运方案中,填有运量的方格,对应的运价,c,ij,分解为两部分，即：,c,ij,=u,i,+v,j,(,对应前面的例题，,i=1,2,3; j=1,2,3,4),其中,u,i,和,v,j,分别为该方格对应于,i,行和,j,列的位势量,.,B,1,B,2,B,3,B,4,u,i,A,1,3,10,U,1,=2,A,2,1,2,U,2,=1,A,3,4,5,U,3,=-3,v,i,v,1,=0,v,2,=7,v,3,=1,v,4,=8,需,供,C,21,=u,2,+v,1,=1,C,23,=u,2,+v,3,=2,C,13,=u,1,+v,3,=3,C,34,=u,3,+v,4,=5,7,个未知量，六个方程,假定其中一个未知量为,0,（任意），如假定,v,1,=0,则可以根据左边的方程解出全部未知量。,位势计算表,第,1,步：求位势量,B,1,B,2,B,3,B,4,u,i,A,1,2,9,3,10,U,1,=2,A,2,1,8,2,9,U,2,=1,A,3,-3,4,-2,5,U,3,=-3,v,i,v,1,=0,v,2,=7,v,3,=1,v,4,=8,需,供,准检验数表,按,u,i,+v,j,求出各,空格的位势量,，得到,准检验数表,（加方括号表示）,准检验数计算过程,空格（,1,，,1,）,= u,1,+v,1,= 2+0 = 2,（,3,，,1,）,=u,3,+v,1,= -3+0 = -3,（,1,，,2,）,=u,1,+v,2,= 2+7 = 9,（,2,，,2,）,=u,2,+v,2,= 1+7 = 8,（,3,，,3,）,=u,3,+v,3,= -3+1 = -2,（,2,，,4,）,=u,2,+v,4,= 1+8 = 9,第,2,步：求准检验数,B,1,B,2,B,3,B,4,A,1,2,9,3,10,A,2,1,8,2,9,A,3,-3,4,-2,5,第,3,步：求检验数,运价表,B,1,B,2,B,3,B,4,A,1,3,11,3,10,A,2,1,9,2,8,A,3,7,4,10,5,准检验数表,利用运价表与准检验数表求检验数,检验数表,B,1,B,2,B,3,B,4,A,1,1,2,A,2,1,-1,A,3,10,12,“,运价表” 减,“准检验数表”,检验结果：,检验数出现负值，根据最优方案判断准则，该方案不是最优方案。,3,）调整调运方案,当判定一个初始调运方案不是最优调运方案时，就要,在检验数出现负值的该空格内进行调整,。,如果检验数是负值的空格不只一个时，一般选择检验数为负值且绝对值最大的空格作为具体的调整对象。,X,13,400+100=500,X,14,300-100=200,X,23,100-100=0,X,24,0+100=100,B,1,B,2,B,3,B,4,A,1,400,300,A,2,300,100,负,A,3,600,300,调整过程：,（,1,）作出负值所在空格的闭回路，本例为空格,x,24,，闭回路如上图所示。,（,2,）沿闭回路在各奇数次转角点中,挑选运量的最小数值作为调整量,。本例是将,x,23,方格的,100,作为调整量，将这个数填入空格,x,24,内，同时调整该闭回路中其他转角点上的运量，使各行、列保持原来的供需平衡这样使得到一个新的调运方案。,B,1,B,2,B,3,B,4,供应量,(t),A,1,500,200,700,A,2,300,0,100,400,A,3,600,300,900,需求量,(t),300,600,500,600,2000,需,供,运量,调整后的调运方案,1,3,5,2,4,10,8,B,1,B,2,B,3,B,4,A,1,2,2,A,2,4,1,A,3,9,12,调整后的检验数,通过计算其检验数全部非负，此方案为最优方案。,运输费用为：,S,3500,十,10200,十,8100,十,1300,十,4600,十,5300,8500(,元,),该值小于初始调运方案的总运费。,(4),表上作业法基本步骤小结,列出调运物资的供需,(,产销,),平衡表及运价表；,按最小元素法建立初始调运方案；,采用位势法计算初始方案每个空格的闭回路的检验数,x,ij,；,检查检验数，如果所有,x,ij,=0,，说明方案是最优的，已经得到我们想要的方案，结束求解；,如果有某个或某几个,x,ij,0,，则选择负检验数中绝对值最大的闭回路进行调整，建立新的方案；,重复,35,步，直至获得最优调运方案。,二,.,确定产销地之间的供需联系和收发量,26,(5),供需不平衡的物资调运问题,通过虚设一个供应点或者需求点，将其转化为平衡运输问题求解。,供应量大于需求量,引入一个虚设的需求点，令其的需求量等于实际问题中供应量与需求量之差，令其运价为,0,。,需求量大于供应量,虚设一个供应点。令这个虚设的供应点的供应量等于实际问题中需求量与供应量的差额，运价为,0,。,二,.,确定产销地之间的供需联系和收发量,27,三,.,运输线路选择,运输路线的选择也是物资调运规划的一个重要内容。,运输路线直接影响到运输效果的好坏，关系着物资能否及时运到指定地点。当单位输运输费用是以吨,公里来计算时，运输路线的长短就直接关系着运输费用的多少。,本节采用图上作业法来进行运输线路选择。,28,1.,交通示意图的表示方法,交通示意图用来表明收发点的大致位置、收发量、交通路线长度的图形。,图形表示方法,：,（,1,）发点（产地或仓库）用符号 表示，里面的数字表示发货量；,（,2,）收点用（需求地）用符号 表示，里面的数字表示收货量；,（,3,）两点间的连线为交通线，其长度记在交通线旁边。,（,4,）物资调运的方向,(,流向,),用符号 表示，并把 按物资调运方向画在,交通线的右边,，把调运物资的数量记在 的,右边,，并加上括号，以表示和交通线长度区别。,20,15,20,5,10,物资调运交通流向图,20,（,20,）,10,20,10,（,5,）,（,15,）,（,10,）,三,.,运输线路选择,29,2.,图上作业法,目的：根据交通流向图，找出运输力量最小的方案。,方法：消灭调运中的对流和迂回两种不合理运输。,三,.,运输线路选择,30,（,1,） 对流,即同一物资在同一线路上的往返运输。,如下面的图， 将某物资,10,吨，从,A,1,运到,B,2,，而又有同样的物资,10,吨，在同一期间从,A,2,运到,B,1,，于是,A,1,A,2,间就出现了对流现象。,10,10,10,30,30,40,30,（,10,）,（,10,）,A,1,A,2,B,1,B,2,如果从图上看，对流可以理解为同一条交通线上，有两条或两条以上的物资调运方向。,10,10,10,30,30,40,30,（,10,）,A,1,A,2,B,1,B,2,（,10,）,消除对流,运力：,30*10+20*10=600,运力：,30*10+40*10+40*10+30*10=1400,三,.,运输线路选择,31,（,2,）迂回,迂回： 在交通图成圈的时候，如果流向图中内圈流向的总长,(,简称内流长,),或外圈流向的总长,(,简称外流长,),超过整个圈长的,半，就称为迂回运输。,内、外圈的概念,：由于表示调运方向的箭头，要按调运方向，画在交通线的右边，因此,流向图中，有些流向就在圈外，称为外圈流向；有些流向在圈内，称为内圈流向。,5,5,6,千米,A,B,（,5,吨）,4,千米,5,5,6,千米,A,B,（,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=10,10,30,30,50,2,4,3,（,20,）,A,1,B,2,A,2,4,B,1,（,30,）,（,10,）,10,30,30,50,2,4,3,（,30,）,A,1,B,2,A,2,4,（,20,）,（,10,）,修改,三,.,运输线路选择,33,物资调运问题的图上作业法,消除运输过程中的对流和迂回，节省运输力量。,具体步骤：,先画出一个没有对流的运输方案,.,再检查有没有迂回，如果没有迂回，这方案就是最优方案；,如果有迂回，则对方案进行调整，直至消除迂回现象为止。,在实际的物资调运中，运输线路可以分为两种情况：,交通线路成圈,交通线路不成圈,三,.,运输线路选择,34,3.,交通路线不成圈,例题,3,有某物资,17,万吨，由,A1,，,A2,，,A3,，,A4,发出，发量分别为,5,，,2,，,3,，,7(,万吨,),，运往,B1,，,B2,，,B3,，,B4,，收量分别为,8,，,1,，,3,，,5(,万吨,),，收发量平衡，交通路线如图,5,8,所示，问应如何调运，才使运输吨千米最小？,5,5,8,（,5,）,A,1,B,1,2,7,3,1,3,A,2,A,3,A,4,B,2,B,3,B,4,5,5,8,A,1,B,1,2,7,3,1,3,A,2,A,3,A,4,B,2,B,3,B,4,交通线路图,调运流向图,解：该交通线路不成圈，只需要做一没有对流的调运图。,方法：从各端点开始，由外到里，逐步进行各收发点之间的平衡,（,2,）,（,1,）,（,2,）,（,1,）,（,7,）,（,5,）,4.,交通路线成圈,例题,4,有某物资,7,万吨，由,A1,，,A2,，,A3,发出，发量分别为,3,，,3,，,1(,万吨,),，运往,B1,，,B2,，,B3,，,B4,，收量分别为,2,，,3,，,1,，,1(,万吨,),，收发量平衡，交通路线如图,5,10,所示，问应如何调运，才使运输吨千米最小？,1,1,3,3,3,4,B,4,A,3,2,1,3,A,1,A,2,B,1,B,3,B,2,7,5,4,3,2,4,1,1,3,3,3,4,B,4,A,3,2,1,3,A,1,A,2,B,1,B,3,B,2,7,5,4,3,2,4,解,: (1),作一个没有对流的流向图,。,方法：用,“,去线破圈,”,的方法。去一线破一圈，有几个圈去掉几条线，把有圈的交通图，转化为不成圈的交通图。,技巧：一般先去掉长度最长的交通线，比如本例中去掉,A,1,B,4,(7,千米,),，破,A,1,B,1,B,2,A,3,B,4,圈；再去掉,A,3,B,3,线,(4,千米,),，破,B,2,A,2,B,3,A,3,圈。这样，原来有圈的交通图，变成了不成圈的交通图如图,5,11,所示。,从各个端点开始，做一个没有对流的流向图,1,1,3,3,3,4,B,4,A,3,2,1,3,A,1,A,2,B,1,B,3,B,2,7,5,4,3,2,4,（,1,）,（,3,）,（,1,）,（,2,）,（,1,）,(2),检查有无迂回,。,方法：对流向图中的各圈进行检查，如果没有迂回，则这个初始方案就是最优方案，如果其中某圈中有迂回，则不是最优方案，需要改进。,1,1,3,3,3,4,B,4,A,3,2,1,3,A,1,B,1,B,3,B,2,7,5,4,3,2,4,（,1,）,（,3,）,（,1,）,（,2,）,（,1,）,A,1,B,1,B,2,A,3,B,4,总圈长,=7+3+4+4+5=23,外流长,=5+4+3=12,存在迂回，需要调整,。,B,2,A,2,B,3,A,3,总圈长,=4+3+2+4=13,内流长,=3,外流长,=2,不存在迂回，不需要调整,A,2,1,1,3,3,3,4,B,4,A,3,2,1,3,A,1,B,1,B,3,B,2,7,5,4,3,2,4,（,1,）,（,3,）,（,1,）,（,2,）,A,2,调整方法：,1,）在外圈的各流量中，减去外圈的最小流量,1,万吨；,2,）在内圈的各流量中加上,1,万吨，在此圈中，因无内流量，故不加。,3,）在无流量的线路上，新添加内圈流量,1,万吨。,（,-1,）,（,-1,）,（,-1,）,（,+1,）,（,+1,）,（,1,）,1,1,3,3,3,4,B,4,A,3,2,1,3,A,1,B,1,B,3,B,2,7,5,4,3,2,4,（,2,）,（,2,）,A,2,（,1,）,（,1,）,A,1,B,1,B,2,A,3,B,4,总圈长,=7+3+4+4+5=23,外流长,=5,内流长,=7+4=11,不存在迂回,。,B,2,A,2,B,3,A,3,总圈长,=4+3+2+4=13,内流长,=3,外流长,=4+2=6,不存在迂回,此方案为最优调运方案,总运力：,1*7+2*5+1*4+2*3+1*2=29,万吨千米,（,1,）,四,.,最短路与最大流,1.,最短路线,例题,5,某家运输公司签定了一项运输合同，要把,A,市的一批货物运送到,B,市。该公司根据两个城市之间可选择的行车路线地图，绘制了图,5,13,的公路网络。要求从交通网络图中，寻找一条线路最短的运输路线。,1,A,市,4,5,2,3,7,6,9,8,10,B,市,100,150,175,300,275,200,175,275,200,300,200,400,250,125,100,150,图中 为结点，代表起点、目的地和与行车路线相交的其他城市，其中的数字为结点编号。,箭头为分支，代表两个结点之间的公路，箭头上标明的数字为运输里程。,公路网络,1,41,解：从终点开始逐步逆向推算。,(1),与终点,10,联接的结点有两个，即结点,9,和,8,；,从结点,9,到结点,10,只有一条线路，该线路为最短线路，长度,100,，记为：,（,9-10,）,100,；,同样，结点,8,到结点,10,的最短线路为,150,，记为,（,8-10,）,150,；,(2),结点,6,。与,6,联接的只有一个结点,9,，,6,至,9,的最短里程为,200,。而,9,至终点,10,的最短里程为,100,因此,6,至终点,10,的最短里程为,200,十,100,300,。记为：,(6-9-10)300,。,(3),结点,5,。与,5,联接的结点有,9,、,8,两个。,5,至,9,再至终点的最短里程为,400,十,100,500,，,5,至,8,再至终点的最短里程为,250,十,155,400,。,400,500,，所以,5,至终点的最短里程为,400,，记为：,(5-8-10)400,。,(4),结点,7,。至终点的最短里程为,125,十,150,275,，记为：,(7-8-10) 275,。,1,A,市,4,5,2,3,7,6,9,8,10,B,市,100,150,175,275,200,175,275,200,300,200,400,250,125,100,150,300,(5),结点,4,。与,4,联接的结点有,5,、,6,、,7,三个。,结点,4,至,6,再到终点的最短里程为,200,十,300=500,；,结点,4,至,5,再到终点的最短里程为,175,十,400,575,；,结点,4,至,7,再到终点的最短里程为,275,十,275,550,。,三个里程中以,500,为最小，所以结点,4,至,l 0,的最短里程记为,(4,6,9,10) 500,。,(6),结点,2,和,3,。,用同样的方法，得到：,结点,2,到终点的最短里程为,600,。记为：,(2,6,9,10)600,。,结点,3,到终点的最短里程为,575,。记为：,(3,7,8,10)575,。,(5),最后看结点,1,。结点,1,可以通过三个结点,2,、,3,、,4,连接到终点。,结点,1,通过结点,2,再到终点的最短里程,100,十,600,700,，路径为,（,1,2,6,9,10,）,700,；,结点,1,通过结点,4,再到终点的最短里程,150,十,500,650,，路径为,（,1,4,6,9,10,）,650,；,结点,1,通过结点,3,再到终点的最短里程,175,十,575,750,，路径为,（,1,3,7,8,10,）,750,。,以上三个里程中以,650,为最小，即,A,币到,B,市的最短里程，对应的最短路线为：,1,4,6,9,10,。,1,A,市,4,5,2,3,7,6,9,8,10,B,市,100,150,175,275,200,175,275,200,300,200,400,250,125,100,150,300,最短路线法的应用,物资的运输路线的选择,物流渠道的设计,电缆架设,管道铺设,个人旅行中,44,2.,最大流,当要把大量货物运输到指定的地点时，有时会希望找到一条交通量最大的路线，以使货物能在最短时间内到达。这就是要在有一个起点和一个终点的网络中，找出在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量问题。,1,5,2,3,4,5,6,6,4,3,3,5,7,2,起点,终点,1,结点,通过能力,交通线路,45,运输网络最大流量的计算,例题：某城市从北到南的交通，平时是利用,85,号公路进行的。目前因为,85,号公路要进行路面维修，车辆不能通过。技术人员查明：在维修期间可以利用市区的其它几条路线通行，现在需要确定这几条线路组成的交通网络能否满足每小时,6000,辆汽车的通过能力。,1,5,2,3,4,5,6,6,4,3,3,5,7,2,北,南,该市从北到南的临时交通网络如上图所示，交通线路,旁边的数字表示单位时间内汽车的通过能力（每小时千辆）。,现在要求从结点,1,通过公路网到结点,6,的最大通过能力（最大流量）。,8,46,计算方法,（,1,）任意选择一条从起点到终点的路线。例如，选择路线,1-2-5-6,。,首先找出这条路线上流量能力最小的支线。从图上可以看出：,5,6,支线流量最小，其流量为,2,，表明沿,“,1-2-5-6,”,支线南驶的汽车，每小时的最大流量只能是,2,千辆，因为,5-6,支线限制了全线的车流量。,其次把这条路线上每条支线的流量减去,2,。差值则表示该支线剩余的流量。,将差值其写在原来的流量能力的旁边，并把原来的流量划掉；,把减数,2,写在每条支线的终点，在减数,2,的右下角注上,(1),，如,2,（,1,）,，表示第一条路线的流量能力为,2,千辆。标注方式如图所示。,1,5,2,3,4,5,6,6 4,4 2,3,3,5,7,2 0,北,南,2,（,1,）,2,（,1,）,2,（,1,）,(2),另选一条从起点,1,到终点,6,的路线，如：,1-4-6,。,以该路线上最小的流量能力,3,为减数，减去各条支线上的流量。其差数、减数的记入方法同上。在差数,3,的右下角注上,(2),，表示第二条路线的流量能力为,3,千辆。,1,5,2,3,4,5,6,6 4,4 2,3 0,3,5,7 4,2 0,北,南,2,（,1,）,2,（,1,）,2,（,1,）,3,（,2,）,3,（,2,）,（,3,）再选一条从起点,1,到终点,6,的路线，如,1-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=8,千辆,/,小时。满足每小时,6000,辆的通过能力。,1,5 2,2,3,4,5,6,6 4,4 2,3 0,3 0,5,7 4 1,2 0,北,南,2,（,1,）,2,（,1,）,2,（,1,）,3,（,2,）,3,（,2,）,3,（,3,）,3,（,3,）,3,（,3,）,谢谢大家！,结 语,