运输路线优化课件

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运输路线优化,运输路线优化,1,1 运输路线和时间安排的原则,运输路线的选择影响到运输设备和人员的利用，正确地确定合理的运输路线可以降低运输成本，因此运输路线的确定是运输决策的一个重要领域。安排运输路线和时间的几个原则如下：,将,相互接近的停留点的货物装在一辆车上运送，以便停留点之间的运行距离最小化；,车辆的运输路线应将邻近的停留点串起来，以使停留点之间的运输距离最小化，这样也就使总的路线上的运输时间最短。,1 运输路线和时间安排的原则运输路线的选择影响到运输设备和,2,运输路线优化课件,3,将集聚在一起的停留点安排同一天送货，要避免不是同一天送货的停留点在运行路线上重叠；,将集聚在一起的停留点安排同一天送货，要避免不是同一天送货的停,4,运行路线从离仓库最远的停留点开始。,运行路线从离仓库最远的停留点开始，送货车辆依次装载临近这个关键停留点的一些停留点的货物，这辆货车满载后，再安排另一辆货车装载另一个最远的停留点的货物。,仓库,运行路线从离仓库最远的停留点开始。仓库,5,4.一辆货车顺次途径各停留点的路线尽量不交叉，要成泪滴状。,6,在多种规格车型的车队中，应优先使用载重量最大的货车。,在运输货物时，最好是使用一辆载重量大到能将路线上所有停留点所要求运送的货物都装载的货车，这样可以将服务区停留点的总的运行距离或时间最小化。,提货应混在送货过程中进行，而不要在运行路线结束后再进行。,提货应尽可能在送货过程中进行，以减少交叉路程量，而在送货结束后再进行提货经常会发生路程交叉。,在多种规格车型的车队中，应优先使用载重量最大的货车。,7,对偏离集聚停留点路线远的单独的停留点可专门安排车辆送货。,偏离集聚停留点少，特别是那些送货量小的停留点一般要花费大量的时间和费用，因此适用小载重量的车辆专门为这些停留点送货是合理的。,另一个可供选择的方案是租用车辆或采用公共服务（如邮政服务）为这些停车,点,送货。,8.应当避免停留点工作时间太短的约束。,停留点工作时间太短会迫使途经停留点的顺序偏离理想状态。,对偏离集聚停留点路线远的单独的停留点可专门安排车辆送货。,8,2 运输路线决策,运输路线决策就是，找到运输网络中的最佳路线，以尽可能缩短运输时间或运输距离，达到降低运输成本、改善运输服务的目标。,运输路线决策问题有三种基本类型：,一是起点和终点不同的单一路径规划；,二是多个起点和终点的路径规划；,三是起点和终点相同的路径规划。,2 运输路线决策运输路线决策就是，找到运输网络中的最佳路线，,9,一、起点和终点不同的单一路径规划,此类问题可以描述为在一个已知交通运输网络中，寻找从出发地到目的地的最佳路线。这里的,“,最佳,”,可以指距离最短、时间最省或是费用最少。,数学模型,求网络图中二点之间的最短路问题。采用网络规划中求最短路,Dijkstra算法（标号算法）,。,除了距离以外，还需要考虑通过交通网络的,时间长短,。,一、起点和终点不同的单一路径规划,10,对分离的、单个始发点和终点的网络运输路线选择问题，最简单和直观的方法是最短路线法。初始，除始发点外，所有节点都被认为是未解的，即均未确定是否在选定的运输路线上。始发点作为已解的点，计算从原点开始。,11,一般的计算方法是：,(1)第n次迭代的目标。寻求第n次最近始发点的节点，重复n1，2，直到最近的节点是终点为止。,(2)第n次迭代的输入值。(n1)个最近始发点的节点是由以前的迭代根据离始发点最短路线和距离计算而得的。,(3)第n个最近节点的侯选点。每个已解的节点由线路分支通向一个或多个尚未解的节点，这些未解的节点中有一个以最短路线分支连接的是候选点。,一般的计算方法是：,12,(4)第n个最近的节点的计算。将每个已解节点及其候选点之间的距离和从始发点到该已解节点之间的距离加起来，总距离最短的候选点即是第n个最近的节点。也就是始发点到达该点最短距离的路径。,以下面的实例可以具体说明最短运输路线是怎样计算的。,(4)第n个最近的节点的计算。将每个已解节点及,13,【例】如图所示是一张公路运输网示意图，其中A是起点，J是终点，B、C、D、E、G、H、I是网络中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点A到终点J的最短的运输路线。,运输路线优化课件,14,A起点,B,E,I,J终点,H,F,C,D,G,84,90,84,138,348,156,48,132,150,90,60,132,126,48,126,66,120,A起点BEIJ终点HFCDG84908,15,我们首先列出一张如表格3,3所示的表格。第一个已解的节点就是起点或点A。与A点直接连接的解的节点有B、C和D点。第一步，我们可以看到B点是距A点最近的节点，记为AB。由于B点是唯一选择，所以它成为已解的节点。,我们首先列出一张如表格33所示的表,16,运输路线优化课件,17,随后，找出距A点和B点最近的未解的节点。只要列出距各个已解的节点最近的连接点，我们有A-C，B,C。记为第二步。注意从起点通过已解的节点到某一节点所需的时间应该等于到达这个已解节点的最短时间加上已解节点与未解节点之间的时间，也就是说，从A点经过B点到达C的距离为AB+BC90+66156分，而从A直达C的时间为138分。现在C也成了已解的节点。,第三次迭代要找到与各已解节点直接连接的最近的未解节点。如表3,3所示，有三个候选点，从起点到这三个候选点D、E、F所需的时间，相应为348、174、228分，其中连接BE的时间最短，为174分，因此正点就是第三次迭代的结果。,随后，找出距A点和B点最近的未解的节点。只,18,重复上述过程直到到达终点J，即第八步。最小的路线时间是384分，连线在表3,3上以星(并)符号标出者，最优路线为A-B-E-I-J。,在节点很多时用手工计算比较繁杂，如果把网络的节点和连线的有关数据存入数据库中，绝对的最短距离路径并不说明穿越网络的最短时间，因为该方法没有考虑各条路线的运行质量。,因此，对运行时间和距离都设定权数就可以得出比较具有实际意义的路线。,重复上述过程直到到达终点J，即第八步。最小,19,【练习】如图所示是一张公路运输网示意图，其中A是起点，I是终点，B、C、D、E、G、H是网络中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点A到终点I的最短的运输路线。,【练习】如图所示是一张公路运输网示意图，其中A是起点，I是终,20,A起点,B,C,D,E,F,G,H,I终点,20,40,60,60,30,60,50,50,50,50,20,45,30,80,100,A起点BCDEFGHI终点20406060,21,2、起迄点重合的问题,物流管理人员经常遇到的一个路线选择问题是始发点就是终点的路线选择。这类问题通常在运输工具是同一部门所有的情况下发生。始发点和终点相合的路线选择问题通常被称为,“,旅行推销员,”,问题，对这类问题应用经验探试法比较有效。,经验告诉我们，当运行路线不发生交叉时，经过各停留点的次序是合理的，同时，如有可能应尽量使运行路线形成泪滴状。图3,2所示是通过各点的运行路线示意图，其中图3,2(a)是不合理的运行路线，图3,2(b)是合理的运行路线。根据上述,“,运行路线不发生交叉,”“,运行路线形成泪滴状,”,两点原则。,2、起迄点重合的问题物流管理人员经常遇到的一个路线选择问题是,22,运输路线优化课件,23,（1）人工计算方法,扫描法,问题：对于若干个停车点（客户）安排最优行车路线。,第一步，将仓库（出发点）和所有的停车点位置画在地图上或坐标图上；,第二步，通过仓库位置放置一直尺，然后顺时针或逆时针方向转动，直到直尺交到一个停车点。询问：,累计的装货量是否超过送货的载重量或容积（首先要使用最大的送货车辆）,。如是，最后的停车点排除，将路线确定下来。然后再从这个停车点开始继续扫描，开始一条新的路线。这样扫描下去，直至全部的停留点都被分配到路线上。,第三步，对每条路线安排运行顺序，以求运行距离最小化。,方案的误差率在10%左右。,（1）人工计算方法扫描法,24,扫描法,是,是,开始,将所有的停留点位置画在地图上,选择适当的车辆装载这个停留点的货物,然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。,通过仓库位置放置一直尺，直尺指向任何方向均可,是否超过车辆容积或体积的限度,是否扫描完所有,停留点,安排下一辆车装载货物，得到一条运行线路,结束,继续转动直尺，扫描到下一个停留点，分配该车辆装载货物,优化每条运行路线的停留点顺序，以求运行距离最小化,否,否,扫描法 是是开始将所有的停留点位置画在地图上选择适当的车辆装,25,扫描法,【例】某公司从其所属的仓库用送货车辆到各客户点提货，然后将客户的货物运回仓库，以便集运成大的批量再进行远程运输。全天的提货量见下图，提货量以件为单位。送货车每次可运载1万件，完成一次运行路线一般需要一天时间。该公司要求确定：需多少条路线（即多少辆送货车）；每条路线上有哪几个客户点；送货车辆途经有关客户点的顺序。,扫描法【例】某公司从其所属的仓库用送货车辆到各客户点提货，然,26,扫描法,4000,1000,3000,2000,1000,2000,2000,2000,2000,3000,2000,3000,扫描法400010003000200010002000200,27,28,【,例,】,某运输公司为其客户企业提供取货服务，货物运回仓库集中后，将以更大的批量进行长途运输。所有取货任务均由载重量为,10,吨的货车完成。现在有,13,家客户有取货要求，各客户的去货量、客户的地理位置坐标见表,7-10,。运输公司仓库的坐标为（,19.50,，,5.56,）。要求合理安排车辆，并确定各车辆行驶路线，使总运输里程最短。,客户,1,2,3,4,5,6,7,8,9,10,11,12,13,D,i,(,吨,),1.9,2.8,3.15,2.4,2,3,2.25,2.5,1.8,2.15,1.6,2.6,1.5,X,i,20.0,18.8,18.3,19.1,18.8,18.6,19.5,19.93,20.0,19.5,18.7,19.5,20.3,Y,i,4.80,5.17,5.00,4.78,6.42,5.88,5.98,5.93,5.55,4.55,4.55,5.19,5.20,表,客户数据信息,28【例】某运输公司为其客户企业提供取货服务，货物运回仓库集,28,29,图,7-14,客户位置及扫描法求出的结果,行车路线制订的扫描法,29图7-14 客户位置及扫描法求出的结果行车路线制订的扫描,29,节约里程法,节约里程法,30,(2),节约里程法,基本原理,基本原理是几何学中三角形一边之长必定小于另外两边之和。,节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。,(2)节约里程法基本原理,31,假如一家配送中心（,DC,）向两个用户,A,、,B,运货，配送中心到两用户的最短距离分别是,L,a,和,L,b,，,A,和,B,间的最短距离为,L,ab,，,A,、,B,的货物需求量分别是,Q,a,和,Q,b,，且（,Q,a,+Q,b,）小于运输装载量,Q,，如图所示，如果配送中心分别送货，那么需要两个车次，总路程为：,L,1,=2,（,L,a,+L,b,）。,A,B,DC,L,a,L,b,A,B,DC,L,a,L,b,L,ab,假如一家配送中心（DC）向两个用户A、B运货，配送中心到两用,32,如果改用一辆车对两客户进行巡回送货，则只需一个车次,行走的总路程为：,L,2,=L,a,+L,b,+L,ab,有三角形的性质我们知道：,L,ab,L/2,L,外,75+70145L/2,L,内,大于全圈长的一半，不是最优方案，应重新甩段破圈，甩内圈运量最小区段a A，寻找最优方案。,根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。,66,150,100,C,A,D,170,160,100,110,80,130,B,a,b,c,d,130,80,70,90,80,30,20,150100CAD17016010011080130Babc,67,计算内外圈长：,L/2（220+180+65+80+70+60+75+90）/2420,L内180+80+60+90410L/2,L外70+75+220365L/2,将上述运输结果填入平衡表：,计算内外圈长：,68,运量,a,b,c,d,产量,A,80,80,B,130,20,150,C,80,90,170,D,70,30,100,销量,130,100,160,110,500,接收地,发送地,运量abcd产量A8080B13020150C8090170,69,【练习】某地区物资供销情况如图所示，现要求得物资调运的最优方案。,30,20,50,20,30,60,70,100,20,36,45,23,25,18,23,A,B,C,D,E,F,G,H,I,【练习】某地区物资供销情况如图所示，现要求得物资调运的最优方,70,30,20,50,20,30,60,70,100,20,20,20,80,20,30,30,40,10,A,B,C,D,E,F,G,H,I,302050203060701002020208020303,71,根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。,L/2（45+23+25+18+23+36）/285,L,内,25+18+2366L/2,L,外,23+3659L/2,将上述运输结果填入平衡表：,根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。,72,送货量,B,C,E,G,I,产量,A,20,20,D,20,20,F,10,30,20,40,100,H,30,30,60,销量,30,50,20,70,30,200,接收地,发送地,送货量BCEGI产量A2020D2020F103020401,73,运量,B,C,E,G,I,产量,A,20,20,D,20,20,F,10,20,70,100,H,30,30,60,销量,30,50,20,70,30,200,接收地,发送地,运量BCEGI产量A2020D2020F102070100H,74,当运输路线有几个圈的情况，应逐圈检查并调整，直到每个圈都能符合要求，此时才能得到物资调拨的最优方案。,【练习】,2900,600,2000,1000,57,A,B,C,D,E,F,H,I,900,1300,3200,1000,G,1500,900,900,78,45,75,132,74,32,57,55,41,74,J,166,K,当运输路线有几个圈的情况，应逐圈检查并调整，直到每个圈都能符,75,2900,600,2000,1000,A,B,C,D,E,F,H,I,900,1300,3200,1000,G,1500,900,900,J,1500,1000,900,900,900,800,500,100,900,1500,K,290060020001000ABCDEFHI9001300,76,距离,A,C,E,F,G,I,J,K,销量,B,1500,800,900,3200,D,500,900,600,900,2900,H,100,1000,900,2000,产量,1500,1300,900,600,1000,1000,900,900,8100,发送地,接收地,距离ACEFGIJK销量B15008009003200D50,77,表上作业法,表上作业法是单纯形法在求解运输问题时的一种简化方法。它包括以下步骤：,确定初始可行方案。方法比较多，一般希望方法既简单，又尽可能接近最优解，常用最小元素法、伏格尔法和左上角法。,最优方案的判别。判别的方法是计算空格的检验数，常用闭回路法和位势法。,改进方案。常使用闭回路调整法进行调整以得到最优的方案。,表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法,78,确定初始基可行解,与一般的线性规划不同，,产销平衡的运输问题一定具有可行解（同时也一定存在最优解）。,最小元素法（,the least cost rule,）、伏格尔法（,Vogels approximation method,）和左上角法。,最小元素法的基本思想是,就近供应,，即从单位,运价表中最小的运价开始确定产销关系，依此,类推，一直到给出基本方案为止,.,最小元素法,确定初始基可行解 与一般的线性规划不同，产销平衡的运输问题一,79,找出最小运价，确定供求关系，最大量的供应；,划掉已满足要求的行或,(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；,在剩余的运价表中重复1、2两步，直到得到初始基可行解。,最小元素法的基本步骤,找出最小运价，确定供求关系，最大量的供应；最小元素法的基,80,最小元素法,最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止。,最小元素法最小元素法的基本思想是就近供应，即从单位运价表中最,81,【例7】有某公司经销一产品，它下设三个加工厂，每日的产量分别为A17吨、A24吨，A39吨，该公司把这些产品分别运往四个销售点。各个销售点每日销量为B13吨，B26吨，B35吨，B46吨，已知从各工厂到各销售点的单位产品的运价如表所示，问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费最少。,B1,B2,B3,B4,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,销地,加工厂,最小元素法,【例7】有某公司经销一产品，它下设三个加工厂，每日的产量分别,82,B1,B2,B3,B4,产量,A1,3,11,3,10,7,A2,1,9,2,8,4,A3,7,4,10,5,9,销量,3,6,5,6,销地,加工厂,3,1,4,6,3,3,B1B2B3B4产量A13113107A219284A374,83,B1,B2,B3,B4,A1,4,3,A2,3,1,A3,6,3,销地,加工厂,B1B2B3B4A143A231A363销地加工厂,84,【例8】编制被运输商品的产销平衡表和单位运输价格如下表所示，试用最小元素法求出最优运输方案的初始方案。,A,B,C,D,E,发运量,甲,3,2,3,5,3,100,乙,3,3,1,3,4,300,丙,7,8,4,2,2,600,丁,5,4,7,7,8,800,需求量,250,300,350,400,500,1800,销地,加工厂,【例8】编制被运输商品的产销平衡表和单位运输价格如下表所示，,85,A,B,C,D,E,发运量,甲,3,2,3,5,3,100,乙,3,3,1,3,4,300,丙,7,8,4,2,2,600,丁,5,4,7,7,8,800,需求量,250,300,350,400,500,1800,销地,加工厂,300,100,500,100,200,250,300,50,ABCDE发运量甲32353100乙33134300丙784,86,在供需关系格（i，j）处填入一数字，刚好使第 i个产地的产品调空，同时也使第j个销地的需求得到满足。填入一数字同时划去了一行和一列，那么最终必然无法得到一个具有m+n-1个数字格（基变量）的初始基可行解。,应注意的问题,为了使在产销平衡表上有m+n-1个数字格，这时需要在第行或第列此前未被划掉的任意一个空格上填一个“0”。填“0”格虽然所反映的运输量同空格没有什么不同；但它所对应的变量却是基变量，而空格所对应的变量是非基变量。,在供需关系格（i，j）处填入一数字，刚好使第 i,87,【练习】最小元素法,1,2,3,产量,1,5,1,8,12,2,2,4,1,14,3,3,6,7,4,销量,9,10,11,销地,加工厂,10,11,3,4,2,【练习】最小元素法123产量1518122241143367,88,伏格尔法,最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运费。,伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额，,差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大处，就应当采用最小运费调运,。,伏格尔法最小元素法的缺点是：为了节省一处的费用，有时造成在其,89,伏格尔法的基本步骤：,1.计算每行、列两个最小运价的差；,2.找出最大差所在的行或列；,3.找出该行或列的最小运价，确定供求关系，最大量的供应；,4.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；,5.在剩余的运价表中重复14步，直到得到初始基可行解。,伏格尔法的基本步骤：1.计算每行、列两个最小运价的差；,90,【例9】试用伏格尔求运输的最优方案。,销地,加工厂,B1,B2,B3,B4,产量,A1,3,11,3,10,7,A2,1,9,2,8,4,A3,7,4,10,5,9,销量,3,6,5,6,【例9】试用伏格尔求运输的最优方案。销地加工厂B1B2B3B,91,销地,加工厂,B1,B2,B3,B4,产量,A1,3,11,3,10,7,A2,1,9,2,8,4,A3,7,4,10,5,9,销量,3,6,5,6,0,1,1,2,5,1,3,6,行差额,列差额,销地加工厂B1B2B3B4产量A13113107A21928,92,销地,加工厂,B1,B2,B3,B4,产量,A1,3,11,3,10,7,A2,1,9,2,8,4,A3,7,4,10,5,9,销量,3,6,5,6,2,5,1,3,6,行差额,列差额,0,1,2,3,销地加工厂B1B2B3B4产量A13113107A21928,93,销地,加工厂,B1,B2,B3,B4,产量,A1,3,11,3,10,7,A2,1,9,2,8,4,A3,7,4,10,5,9,销量,3,6,5,6,2,1,2,6,行差额,列差额,0,1,2,3,3,销地加工厂B1B2B3B4产量A13113107A21928,94,销地,加工厂,B1,B2,B3,B4,产量,A1,3,11,3,10,7,A2,1,9,2,8,4,A3,7,4,10,5,9,销量,3,6,5,6,1,2,6,行差额,列差额,7,6,3,3,5,2,1,销地加工厂B1B2B3B4产量A13113107A21928,95,销地,加工厂,B1,B2,B3,B4,产量,A1,7,A2,4,A3,9,销量,3,6,5,6,6,3,3,5,2,1,销地加工厂B1B2B3B4产量A17A24A39销量3656,96,1,2,3,4,5,产量,1,10,2,3,15,9,25,2,5,10,15,2,4,30,3,15,5,14,7,15,20,4,20,15,13,M,8,30,销量,20,20,30,10,25,【练习】伏格尔法，M为无穷大的正数,销地,加工厂,行差额,列差额,1,2,2,5,5,3,10,5,4,25,12345产量11023159252510152430315,97,1,2,3,4,5,产量,1,10,2,3,15,9,25,2,5,10,15,2,4,30,3,15,5,14,7,15,20,4,20,15,13,M,8,30,销量,20,20,30,10,25,销地,加工厂,行差额,列差额,1,2,2,5,10,5,1,5,4,25,20,12345产量11023159252510152430315,98,1,2,3,4,5,产量,1,10,2,3,15,9,25,2,5,10,15,2,4,30,3,15,5,14,7,15,20,4,20,15,13,M,8,30,销量,20,20,30,10,25,销地,加工厂,行差额,列差额,1,2,2,5,10,5,1,5,4,25,20,10,0,（有时在产销平衡表上填入一个运量后，在单位运价表上同时划去一行和一列，这时需要添一个“0”，它的位置可在对应同时划去的那行或列的任一空格处）,12345产量11023159252510152430315,99,1,2,3,4,5,产量,1,10,2,3,15,9,25,2,5,10,15,2,4,30,3,15,5,14,7,15,20,4,20,15,13,M,8,30,销量,20,20,30,10,25,销地,加工厂,行差额,列差额,1,2,9,5,10,1,7,25,20,10,20,25,5,0,0,12345产量11023159252510152430315,100,1,2,3,4,5,产量,1,25,2,30,3,20,4,30,销量,20,20,30,10,25,销地,加工厂,25,20,10,20,25,5,0,0,12345产量125230320430销量202030102,101,【练习】伏格尔法,1,2,3,产量,1,5,1,8,12,2,2,4,1,14,3,3,6,7,4,销量,9,10,11,销地,加工厂,4,1,3,行差额,1,3,6,列差额,11,【练习】伏格尔法123产量15181222411433674,102,【练习】,1,2,3,产量,1,5,1,8,12,2,2,4,1,14,3,3,6,7,4,销量,9,10,11,销地,加工厂,4,2,3,行差额,1,3,列差额,11,10,3,4,2,【练习】123产量15181222411433674销量91,103,左上角法,除了最小费用法外，左上角法也是求得运输初始方案的一种途径，并通过霍撤克法则最终得出最优运输方案。具体做法是：,例现有三个生产地A、B、C供应某种商品；有四个销售地1、2、3、4，各自供应量和需求量如表所示，试用左上角法求出最优运输方案。,左上角法,104,运输路线优化课件,105,第一步 以运输表左上角的格子作为开端。,第二步 对这一格子可用的供应量与需求量作比较，安排两个值中较小的一个作为运量，然后，把这个数字圈起来。这一格可用的供应量(或需求量)减去安排的运量就是剩余的供应量(或需求量)。上表中有50个单位的供应量和30个单位的需求量。因此，可以安排30单位的运量到A1格。,第三步 如果安排运量的格子正好是在运输表的最右下角，就停止安排。这时，初始方案已找到。如果这一格不在最右下角，就进入到第四步。,第一步 以运输表左上角的格子作为开端。,106,第四步 根据以下规划，移到下一格：,a如果已安排的这一格行和列比较，供应量超过需求量，下一格移到同一行相邻的格子。,b如果需求量超过供应量，下一格移到同一列相邻的格子。,c如果需求量等于供应量，下一格是对角线上相邻的格子,。,d回到第二步。,根据左上角法求出运输初始方案后，为了进一步算出最优方案，仍需要运用霍撒克法则进行优化,第四步 根据以下规划，移到下一格：,107,运输路线优化课件,108,运输路线优化课件,109,运输路线优化课件,110,运输路线优化课件,111,单位 销地,运价,产地,产量,4,12,4,11,16,2,10,3,9,10,8,5,11,5,22,销量,8,14,12,14,48,练习 某部门有,3,个生产同类产品的工厂（产地）,生产的产品由,4,个销售点（销地）出售，各工厂的生产量、个销售点的销售量（假定单位均为,t),以及各工厂到个销售点的单位云价（元,/t),示于下表，试研究如何调运才能使总的运费最小？,单位 销地产量412411162103910851,(1),最小元素法,(1)最小元素法,(2),西北角法,(2)西北角法,2,最优方案的判别,对初始基可行解的最优性检验有,闭合回路法,和,位势法,两种基本方法。,闭合回路法具体、直接，并为方案调整指明了方向；,而位势法具有批处理的功能，提高了计算效率。,2 最优方案的判别对初始基可行解的最优性检验有闭合回路法,115,所谓闭合回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为,1，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。,如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。,(,1,),.闭合回路法,ij,0,表示运费增加。,所谓闭合回路法，就是对于代表非基变量的空格（其调运量为零），,116,所谓,闭合回路,是,在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，,只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭合回路,。,一个空格存在唯一的闭回路。,所谓闭合回路是在已给出的调运方案的运输表上从一个代表非基变量,117,例一、某运输资料如下表所示：,单位 销地,运价,产地,产量,3,11,3,10,7,1,9,2,8,4,7,4,10,5,9,销量,3,6,5,6,例一、某运输资料如下表所示：单位 销地产量3113,B1,B2,B3,B4,产量,A1,3,11,3,10,7,A2,1,9,2,8,4,A3,7,4,10,5,9,销量,3,6,5,6,销地,加工厂,3,1,4,6,3,3,B1B2B3B4产量A13113107A219284A374,119,B1,B2,B3,B4,A1,4,3,A2,3,1,A3,6,3,销地,加工厂,B1B2B3B4A143A231A363销地加工厂,120,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,4,6,3,（,1,）,（,1,）,（,1,）,（,1,）,计算如下：空格处（,A,1,B,1,）,(13),(,1)3,(12),(,1)1,1,此数即为该空格处的检验数。,1,B1B2B3B4产量A17A24A39销量365631346,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,4,B1B2B3B4产量A17A24A39销量365631363,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,-1,4,B1B2B3B4产量A17A24A39销量365631363,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,1,-1,4,B1B2B3B4产量A17A24A39销量365631363,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,1,-1,12,4,B1B2B3B4产量A17A24A39销量365631363,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,1,3,6,3,1,2,1,-1,12,10,4,检验数中有负数，说明原方案不是最优解。,B1B2B3B4产量A17A24A39销量365631363,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,0,0,0,0,0,1,2,1,-1,12,10,0,B1B2B3B4产量A17A24A39销量365600000,2、最优方案的判别,位势法,使用位势法求出检验数，若检验数都不为负数，则原方案为最优解，若有负检验数存在，则负检验数所在空格需进行调整。,只有没有运量的空格处需要计算检验数。,2、最优方案的判别位势法使用位势法求出检验数，若检验数都,128,2、最优方案的判别,位势法,检验数的计算方法如下：,设有运量的格子数最多的行或列的位势0,有运量格子的运价行位势+列位势,空格的检验数运价-（行位势+列位势）,2、最优方案的判别位势法检验数的计算方法如下：,129,接上例：,B,1,B,2,B,3,B,4,A,1,3,10,u,1,A,2,1,2,u,2,A,3,4,5,u,3,v,1,v,2,v,3,v,4,成本表,B,1,B,2,B,3,B,4,A,1,2,9,3,10,0,A,2,1,8,2,9,1,A,3,3,4,2,5,5,2,9,3,10,u,2,+,v,1,=1,u,2,+,v,3,=2,u,3,+,v,2,=4,u,1,+,v,4,=10,u,1,+,v,3,=3,u,3,+,v,4,=5,令：,u,1,0,u,1,0 v,1,2,u,2,1 v,2,9,u,3,5 v,3,3,v,4,10,(u,i,+v,j,),接上例：B1B2B3B4A1310u1A212u2A345u,按,ij,=c,ij,(u,i,+v,j,),计算检验数，并以,ij,0,检验，或用,(u,i,+v,j,),c,ij,0,检验。,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,c,ij,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,(u,i,+v,j,),B,1,B,2,B,3,B,4,A,1,1,2,0,0,A,2,0,1,0,1,A,3,10,0,12,0,表中还有负数，说明还未得到最优解，应继续调整。,ij,按ij=cij(ui+vj)计算检验数,A,B,C,D,E,发运量,甲,3,2,3,5,3,100,乙,3,3,1,3,4,300,丙,7,8,4,2,2,600,丁,5,4,7,7,8,800,需求量,250,300,350,400,500,1800,销地,加工厂,300,100,500,50,50,250,250,300,【练习】下面是用最小元素法的得出的运输方案，试用位势法判断是否最优。,ABCDE发运量甲32353100乙33134300丙784,132,A,B,C,D,E,行位势,甲,3,2,3,5,3,乙,3,3,1,3,4,丙,7,8,4,2,2,丁,5,4,7,7,8,列位势,销地,加工厂,0,5,4,7,-2,5,-4,-5,7,0,0,-2,2,3,0,1,7,9,4,2,1,ABCDE行位势甲32 3 53乙331 34丙784,133,3、改进方案,闭合回路调整法,从负检验数所在格子出发找一条闭合回路，用水平或垂直线向前划，每碰到数字格可以转90度，然后继续前进，直到回到起始空格为止。,并从出发格开始依次标上正负号。,将所有标有负号的转角格中的最小运量作为调整数。,各正号加上调整数，负号减去调整数。,3、改进方案闭合回路调整法从负检验数所在格子出发找一条闭,134,【例11】使用闭合回路法对例10进行调整。,B1,B2,B3,B4,行位势,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,列位势,销地,加工厂,0,3,10,-1,-5,2,9,1,2,1,-1,10,12,【例11】使用闭合回路法对例10进行调整。B1B2B3B4行,135,B1,B2,B3,B4,产量,A1,3,11,3,10,7,A2,1,9,2,8,4,A3,7,4,10,5,9,销量,3,6,5,6,销地,加工厂,3,1,4,6,3,3,+,+,-,-,1,5,2,B1B2B3B4产量A13113107A219284A374,136,A,B,C,D,E,行位势,甲,3,2,3,5,3,乙,3,3,1,3,4,丙,7,8,4,2,2,丁,5,4,7,7,8,列位势,销地,加工厂,0,5,4,7,-2,5,-4,-5,7,0,0,-2,2,3,0,1,7,9,4,2,1,【练习】使用闭合回路法对上一个练习题进行调整。,ABCDE行位势甲32 3 53乙331 34丙784,137,A,B,C,D,E,发运量,甲,3,2,3,5,3,100,乙,3,3,1,3,4,300,丙,7,8,4,2,2,600,丁,5,4,7,7,8,800,需求量,250,300,350,400,500,1800,销地,加工厂,300,100,500,50,50,250,250,300,+,+,+,-,-,-,ABCDE发运量甲32353100乙33134300丙784,138,A,B,C,D,E,发运量,甲,3,2,3,5,3,100,乙,3,3,1,3,4,300,丙,7,8,4,2,2,600,丁,5,4,7,7,8,800,需求量,250,300,350,400,500,1800,销地,加工厂,300,150,450,50,50,300,250,250,+,+,+,-,-,-,ABCDE发运量甲32353100乙33134300丙784,139,【例12】试用伏格尔法求，并检验，得出最优运输方案。,1,2,3,4,供应量,A,10,6,7,12,4,B,16,10,5,9,9,C,5,4,10,10,4,销量,5,2,4,6,销地,加工厂,费用,【例12】试用伏格尔法求，并检验，得出最优运输方案。1234,140,1,2,3,4,供应量,A,10,6,7,12,4,B,16,10,5,9,9,C,5,4,10,10,4,销量,5,2,4,6,销地,加工厂,费用,行差额,1,4,列差额,2,1,1,5,2,4,1234供应量A1067124B1610599C541010,141,1,2,3,4,供应量,A,10,6,7,12,4,B,16,10,5,9,9,C,5,4,10,10,4,销量,5,2,4,6,销地,加工厂,费用,行差额,1,4,列差额,2,3,1,6,4,4,1,1234供应量A1067124B1610599C541010,142,1,2,3,4,供应量,A,10,6,7,12,4,B,16,10,5,9,9,C,5,4,10,10,4,销量,5,2,4,6,销地,加工厂,费用,行差额,1,4,列差额,2,3,4,4,1,4,1234供应量A1067124B1610599C541010,143,1,2,3,4,供应量,A,10,6,7,12,4,B,16,10,5,9,9,C,5,4,10,10,4,销量,5,2,4,6,销地,加工厂,费用,行差额,6,1,列差额,2,3,4,4,1,4,2,1,5,1234供应量A1067124B1610599C541010,144,1,2,3,4,行位势,A,10,6,7,12,B,16,10,5,9,C,5,4,10,10,列位势,销地,加工厂,费用,4,1,4,2,1,5,0,10,6,12,-3,-5,8,-1,9,7,3,7,3,1234行位势A106712B161059C541010列位,145,1,2,3,4,行位势,A,10,6,7,12,B,16,10,5,9,C,5,4,10,10,列位势,销地,加工厂,费用,4,1,4,2,1,5,+,-,+,-,1,3,6,1234行位势A106712B161059C541010列位,146,1,2,3,4,行位势,A,10,6,7,12,B,16,10,5,9,C,5,4,10,10,列位势,销地,加工厂,费用,4,1,2,1,3,6,0,10,6,7,-2,-5,11,1,8,6,3,8,4,1234行位势A106712B161059C541010列位,147,1,2,3,4,行位势,A,B,C,列位势,销地,加工厂,运量,4,1,2,1,3,6,最优运输方案如下,1234行位势ABC列位势销地加工厂运量412136最优运输,148,【练习】试用伏格尔法求，并检验，得出最优运输方案。,1,2,3,4,供应量,A,15,18,19,13,50,B,20,14,15,17,30,C,25,12,17,22,70,销量,30,60,20,40,150,销地,加工厂,费用,【练习】试用伏格尔法求，并检验，得出最优运输方案。1234供,149,1,2,3,4,供应量,A,15,18,19,13,50,B,20,14,15,17,30,C,25,12,17,22,70,销量,30,60,20,40,150,销地,加工厂,费用,行差额,2,1,5,列差额,5,2,2,4,60,1234供应量A1518191350B2014151730C,150,1,2,3,4,供应量,A,15,18,19,13,50,B,20,14,15,17,30,C,25,12,17,22,70,销量,30,60,20,40,150,销地,加工厂,费用,行差额,2,2,5,列差额,5,2,2,4,60,30,1234供应量A1518191350B2014151730C,151,1,2,3,4,供应量,A,15,18,19,13,50,B,20,14,15,17,30,C,25,12,17,22,70,销量,30,60,20,40,150,销地,加工厂,费用,行差额,6,2,5,列差额,5,2,2,4,60,30,20,1234供应量A1518191350B2014151730C,152,1,2,3,4,供应量,A,15,18,19,13,50,B,20,14,15,17,30,C,25,12,17,22,70,销量,30,60,20,40,150,销地,加工厂,费用,行差额,2,5,列差额,2,5,60,30,20,20,10,10,1234供应量A1518191350B2014151730C,153,1,2,3,4,行位势,A,15,18,19,13,B,20,14,15,17,C,25,12,17,22,列位势,销地,加工厂,费用,0,15,13,4,11,6,6,12,8,1,4,4,3,1234行位势A15 181913 B201415 1,154,1,2,3,4,供应量,A,50,B,30,C,70,销量,30,60,20,40,150,销地,加工厂,运量,60,30,20,20,10,10,最优运输方案如下,1234供应量A50B30C70销量30602040150销,155,【练习】试用最小元素法求，并检验，得出最优运输方案。,1,2,3,供应量,A,5,1,3,12,B,2,4,1,14,C,3,6,7,4,销量,9,10,11,销地,加工厂,费用,【练习】试用最小元素法求，并检验，得出最优运输方案。123供,156,1,2,3,供应量,A,5,1,3,12,B,2,4,1,14,C,3,6,7,4,销量,9,10,11,销地,加工厂,费用,10,11,3,4,2,123供应量A51312B24114C3674销量91011,157,1,2,3,行位势,A,5,1,3,B,2,4,1,C,3,6,7,列位势,销地,加工厂,费用,10,11,3,4,2,0,5,2,3,-4,-1,-1,6,7,5,123行位势A513B241C367列位势销地加工厂费用10,158,1,2,3,行位势,A,5,1,3,B,2,4,1,C,3,6,7,列位势,销地,加工厂,费用,10,11,3,4,2,+,-,+,-,123行位势A513B241C367列位势销地加工厂费用10,159,1,2,3,行位势,A,5,1,3,B,2,4,1,C,3,6,7,列位势,销地,加工厂,费用,10,9,5,4,+,-,+,-,2,123行位势A513B241C367列位势销地加工厂费用10,160,1,2,3,行位势,A,5,1,3,B,2,4,1,C,3,6,7,列位势,销地,加工厂,费用,10,9,5,4,2,0,1,3,-2,4,-1,1,5,6,5,123行位势A513B241C367列位势销地加工厂费用10,161,1,2,3,行位势,A,B,C,列位势,销地,加工厂,运量,10,9,5,4,2,最优运输方案如下,123行位势ABC列位势销地加工厂运量109542最优运输方,162,供求不均衡运输,在运输的实际工作中，由于经济活动和市场环境的多变性，经常会存在供求不平衡的现象，此时应对上述的方法进行一定的修正。,修正的基本思路是：,化不均衡为均衡，如果出现供求不平衡，则设一个虚销点或虚发点，得出最优方案后再去掉虚设的点,。,供求不均衡运输在运输的实际工作中，由于经济活动和市场环境的多,163,【例12】,1,2,3,4,供应量,A,15,18,19,13,50,B,20,14,15,17,55,C,25,12,17,22,70,销量,30,60,20,40,销地,加工厂,费用,【例12】1234供应量A1518191350B201415,164,【例12】,1,2,3,4,5,供应量,A,15,18,19,13,0,50,B,20,14,15,17,0,55,C,25,12,17,22,0,70,销量,30,60,20,40,25,销地,加工厂,费用,解决供求不均衡问题时，可使用,西北角法,来求得初始可行方案。,30,20,40,15,5,40,25,【例12】12345供应量A15181913050B2014,165,【例12】,1,2,3,4,5,行位势,A,15,18,19,13,0,B,20,14,15,17,0,C,25,12,17,22,0,列位势,销地,加工厂,费用,30,20,40,15,5,40,25,0,0,22,17,-2,16,2,13,0,-9,-2,9,-3,12,-4,2,【例12】12345行位势A151819130B201415,166,【例12】,1,2,3,4,5,