运输路线优化课件

运输路线优化

运输路线优化

11运输路线和时间安排的原则运输路线的选择影响到运输设备和人员的利用，正确地确定合理的运输路线可以降低运输成本，因此运输路线的确定是运输决策的一个重要领域。安排运输路线和时间的几个原则如下：将相互接近的停留点的货物装在一辆车上运送，以便停留点之间的运行距离最小化；车辆的运输路线应将邻近的停留点串起来，以使停留点之间的运输距离最小化，这样也就使总的路线上的运输时间最短。1运输路线和时间安排的原则运输路线的选择影响到运输设备和2运输路线优化课件3将集聚在一起的停留点安排同一天送货，要避免不是同一天送货的停留点在运行路线上重叠；将集聚在一起的停留点安排同一天送货，要避免不是同一天送货的停4运行路线从离仓库最远的停留点开始。运行路线从离仓库最远的停留点开始，送货车辆依次装载临近这个关键停留点的一些停留点的货物，这辆货车满载后，再安排另一辆货车装载另一个最远的停留点的货物。仓库运行路线从离仓库最远的停留点开始。仓库54.一辆货车顺次途径各停留点的路线尽量不交叉，要成泪滴状。●●●●●●●●●●●●●●●●●●●●●●●●6在多种规格车型的车队中，应优先使用载重量最大的货车。在运输货物时，最好是使用一辆载重量大到能将路线上所有停留点所要求运送的货物都装载的货车，这样可以将服务区停留点的总的运行距离或时间最小化。提货应混在送货过程中进行，而不要在运行路线结束后再进行。提货应尽可能在送货过程中进行，以减少交叉路程量，而在送货结束后再进行提货经常会发生路程交叉。在多种规格车型的车队中，应优先使用载重量最大的货车。7对偏离集聚停留点路线远的单独的停留点可专门安排车辆送货。偏离集聚停留点少，特别是那些送货量小的停留点一般要花费大量的时间和费用，因此适用小载重量的车辆专门为这些停留点送货是合理的。另一个可供选择的方案是租用车辆或采用公共服务（如邮政服务）为这些停车点送货。8.应当避免停留点工作时间太短的约束。停留点工作时间太短会迫使途经停留点的顺序偏离理想状态。对偏离集聚停留点路线远的单独的停留点可专门安排车辆送货。82运输路线决策运输路线决策就是，找到运输网络中的最佳路线，以尽可能缩短运输时间或运输距离，达到降低运输成本、改善运输服务的目标。运输路线决策问题有三种基本类型：

一是起点和终点不同的单一路径规划；二是多个起点和终点的路径规划；三是起点和终点相同的路径规划。2运输路线决策运输路线决策就是，找到运输网络中的最佳路线，9一、起点和终点不同的单一路径规划此类问题可以描述为在一个已知交通运输网络中，寻找从出发地到目的地的最佳路线。这里的“最佳”可以指距离最短、时间最省或是费用最少。数学模型——求网络图中二点之间的最短路问题。采用网络规划中求最短路Dijkstra算法（标号算法）。除了距离以外，还需要考虑通过交通网络的时间长短。一、起点和终点不同的单一路径规划10

对分离的、单个始发点和终点的网络运输路线选择问题，最简单和直观的方法是最短路线法。初始，除始发点外，所有节点都被认为是未解的，即均未确定是否在选定的运输路线上。始发点作为已解的点，计算从原点开始。

11

一般的计算方法是：(1)第n次迭代的目标。寻求第n次最近始发点的节点，重复n＝1，2，…，直到最近的节点是终点为止。(2)第n次迭代的输入值。(n—1)个最近始发点的节点是由以前的迭代根据离始发点最短路线和距离计算而得的。(3)第n个最近节点的侯选点。每个已解的节点由线路分支通向一个或多个尚未解的节点，这些未解的节点中有一个以最短路线分支连接的是候选点。

一般的计算方法是：12(4)第n个最近的节点的计算。将每个已解节点及其候选点之间的距离和从始发点到该已解节点之间的距离加起来，总距离最短的候选点即是第n个最近的节点。也就是始发点到达该点最短距离的路径。以下面的实例可以具体说明最短运输路线是怎样计算的。(4)第n个最近的节点的计算。将每个已解节点及13【例】如图所示是一张公路运输网示意图，其中A是起点，J是终点，B、C、D、E、G、H、I是网络中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点A到终点J的最短的运输路线。运输路线优化课件14●●●●●●●●●●A起点BEIJ终点HFC DG84908413834815648132150906013212648126●●●●●●●●●66120●●●●●●●●●●A起点BEIJ终点HFC DG8490815

我们首先列出一张如表格3—3所示的表格。第一个已解的节点就是起点或点A。与A点直接连接的解的节点有B、C和D点。第一步，我们可以看到B点是距A点最近的节点，记为AB。由于B点是唯一选择，所以它成为已解的节点。我们首先列出一张如表格3—3所示的表16运输路线优化课件17

随后，找出距A点和B点最近的未解的节点。只要列出距各个已解的节点最近的连接点，我们有A--C，B—C。记为第二步。注意从起点通过已解的节点到某一节点所需的时间应该等于到达这个已解节点的最短时间加上已解节点与未解节点之间的时间，也就是说，从A点经过B点到达C的距离为AB+BC＝90+66＝156分，而从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起点BCDEFGHI终点2040606030605050505020453080100●●●●●●●●●●●●●●●●●●A起点BCDEFGHI终点20406060212、起迄点重合的问题物流管理人员经常遇到的一个路线选择问题是始发点就是终点的路线选择。这类问题通常在运输工具是同一部门所有的情况下发生。始发点和终点相合的路线选择问题通常被称为“旅行推销员”问题，对这类问题应用经验探试法比较有效。经验告诉我们，当运行路线不发生交叉时，经过各停留点的次序是合理的，同时，如有可能应尽量使运行路线形成泪滴状。图3—2所示是通过各点的运行路线示意图，其中图3—2(a)是不合理的运行路线，图3—2(b)是合理的运行路线。根据上述“运行路线不发生交叉”“运行路线形成泪滴状”两点原则。2、起迄点重合的问题物流管理人员经常遇到的一个路线选择问题是22运输路线优化课件23（1）人工计算方法——扫描法

问题：对于若干个停车点（客户）安排最优行车路线。第一步，将仓库（出发点）和所有的停车点位置画在地图上或坐标图上；第二步，通过仓库位置放置一直尺，然后顺时针或逆时针方向转动，直到直尺交到一个停车点。询问：累计的装货量是否超过送货的载重量或容积（首先要使用最大的送货车辆）。如是，最后的停车点排除，将路线确定下来。然后再从这个停车点开始继续扫描，开始一条新的路线。这样扫描下去，直至全部的停留点都被分配到路线上。第三步，对每条路线安排运行顺序，以求运行距离最小化。方案的误差率在10%左右。（1）人工计算方法——扫描法24扫描法是是开始将所有的停留点位置画在地图上选择适当的车辆装载这个停留点的货物然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。通过仓库位置放置一直尺，直尺指向任何方向均可是否超过车辆容积或体积的限度是否扫描完所有停留点安排下一辆车装载货物，得到一条运行线路结束继续转动直尺，扫描到下一个停留点，分配该车辆装载货物优化每条运行路线的停留点顺序，以求运行距离最小化否否扫描法是是开始将所有的停留点位置画在地图上选择适当的车辆装25扫描法【例】某公司从其所属的仓库用送货车辆到各客户点提货，然后将客户的货物运回仓库，以便集运成大的批量再进行远程运输。全天的提货量见下图，提货量以件为单位。送货车每次可运载1万件，完成一次运行路线一般需要一天时间。该公司要求确定：需多少条路线（即多少辆送货车）；每条路线上有哪几个客户点；送货车辆途经有关客户点的顺序。扫描法【例】某公司从其所属的仓库用送货车辆到各客户点提货，然26扫描法400010003000200010002000200020002000300020003000扫描法4000100030002000100020002002728【例】某运输公司为其客户企业提供取货服务，货物运回仓库集中后，将以更大的批量进行长途运输。所有取货任务均由载重量为10吨的货车完成。现在有13家客户有取货要求，各客户的去货量、客户的地理位置坐标见表7-10。运输公司仓库的坐标为（19.50，5.56）。要求合理安排车辆，并确定各车辆行驶路线，使总运输里程最短。

客户12345678910111213Di(吨)1.92.83.152.4232.252.51.82.151.62.61.5Xi20.018.818.319.118.818.619.519.9320.019.518.719.520.3Yi4.805.175.004.786.425.885.985.935.554.554.555.195.20表

客户数据信息28【例】某运输公司为其客户企业提供取货服务，货物运回仓库集2829图7-14客户位置及扫描法求出的结果行车路线制订的扫描法29图7-14客户位置及扫描法求出的结果行车路线制订的扫描29节约里程法节约里程法30

(2)节约里程法

基本原理基本原理是几何学中三角形一边之长必定小于另外两边之和。节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。

(2)节约里程法

基本原理31假如一家配送中心（DC）向两个用户A、B运货，配送中心到两用户的最短距离分别是La和Lb，A和B间的最短距离为Lab，A、B的货物需求量分别是Qa和Qb，且（Qa+Qb）小于运输装载量Q，如图所示，如果配送中心分别送货，那么需要两个车次，总路程为：L1=2（La+Lb）。ABDCLaLbABDCLaLb

Lab假如一家配送中心（DC）向两个用户A、B运货，配送中心到两用32如果改用一辆车对两客户进行巡回送货，则只需一个车次,行走的总路程为：L2=La+Lb+Lab有三角形的性质我们知道：Lab<（La+Lb）所以第二次的配送方案明显优于第一种，且行走总路程节约：ΔL=（La+Lb）－Lab如果配送中心的供货范围内还存在着：3,4,5，…，n个用户，在运载车辆载重和体积都允许的情况下，可将它们按着节约路程的大小依次连入巡回线路，直至满载为止，余下的用户可用同样方法确定巡回路线，另外派车。如果改用一辆车对两客户进行巡回送货，则只需一个车次,33例：由配送中心P向A—I等9个用户配送货物。图中连线上的数字表示公路里程（km）。靠近各用户括号内的数字，表示各用户对货物的需求量（t）。配送中心备有2t和4t载重量的汽车，且汽车一次巡回走行里程不能超过35km，设送到时间均符合用户要求，求该配送中心的最优送货方案。例：由配送中心P向A—I等9个用户配送货物。图中连线上的34运输路线优化课件35计算配送中心至各用户以及各用户之间的最短距离，列表得最短距离表：计算配送中心至各用户以及各用户之间的最短距离，列表得最短距离36

PABCDEFGHIPABCDEFGHI

11109671010875101418212113659152020181141019191716615161413917151414181712177PABC37由最短距离表，利用节约法计算出各用户之间的节约里程，编制节约里程表：A—B:LA+LB—LAB=11+10-5=16A—C:LA+LC—LAC=11+9-10=10A—D:LA+LD—LAD=11+6-14=3A—E:LA+LE—LAE=11+7-18=0A—F:LA+LF—LAF=11+10-21=0A—G:LA+LG—LAG=11+10-21=0……由最短距离表，利用节约法计算出各用户之间的节约里程，编38

ABCDEFGHIABCDEFGHI

16103000612147200061160000710008000600608节约里程表ABCD39根据节约里程表中节约里程多少的顺序，由大到小排列，编制节约里程顺序表，以便尽量使节约里程最多的点组合装车配送。根据节约里程表中节约里程多少的顺序，由大到小排列，编制40顺位号里程节约里程顺位号里程节约里程顺位号里程节约里程1A-B166H-I810F-G62B-C148B-D710G-H63A-I128D-E715A-D34C-D1110A-H616B-E25A-C1010B-I617D-F16E-F810C-E6顺位号里程节约里程顺位号里程节约里程顺位号里程节约里程1A-41

根据节约里程排序表和配车（车辆的载重和容积因素）、车辆行驶里程等约束条件，渐进绘出配送路径：ABCDEFGHIP(0.9)(1.2)(1.6)(1.1)(0.9)(0.9)(0.6)(1.7)(0.5)975586669101012路径A路径B路径C根据节约里程排序表和配车（车辆的载重和容积因素）、车42路径A：4t车，走行32km，载重量3.7t；路径B：4t车，走行31km，载重量3.9t；路径C：2t车，走行30km，载重量1.8t。

总共走行里程93km，共节约里程（16+14+12）+（8+7）+6=63km。路径A：4t车，走行32km，载重量3.7t；43优缺点分析优点：

节约法是一种简便、易行的方法，一方面体现出优化运输过程，与一般方法相比缩短了运输路程；另一方面，它也体现了物流配送网络的优势，实现了企业物流活动的整合，而且思路简单清晰、便于执行。优缺点分析优点：44缺点：

第一，利用节约法选择配送路线过于强调节约路程，而没考虑行程中的时间因素，在许多情况下，时间更能决定物流配送的成本与服务质量。例如城市间配送时对高速公路的选择，城市内部上下班时间的道路拥挤，一个巡回配送过程中的时间长短，直接影响配送人员的精神状态，而人员的精神状态又与交通事故和配送错误相连等，所以时间对配送路线的选择有时更重要。第二，利用节约法选择配送路线不能对客户的需求进行灵活多变的处理。由于现代的消费者的需求倾向于个性化，引起企业的生产、销售和配送也愈来愈倾向于小批量，多品种，多批次。而节约法更适合需求稳定或是需求的时间不紧迫，这显然不能满足现代多变得市场环境。

缺点：45节约法的改进建议

由以上的分析可知,节约法简便易行,同时也有一些弊端.是否可以通过改进使其成为一种最优的方法呢?在配送路线选择决策时,通常考虑较优的原则,而不是最优化原则.深入了解客户,加强与客户的信息交流。通过对客户需求的时间变化对其进行分类,以增加配送的灵活性。路线决策过程中实施多路线同步决策。节约法的实施过程,要综合考虑路程长短和时间因素。配送的总体过程实际上还会受商品分拣、装卸、搬运设备和货物组装的共同影响。节约法的改进建议由以上的分析可知,节约法简便易行,同时463、多起迄点问题如果有多个货源地可以服务于多个目的地时，那么我们面临的问题是，要指定为各目的地服务的供货地，同时要找到供货地、目的地之间的最佳路径。该问题常发生在多个供应商、工厂或仓库服务于多个客户的情况下。3、多起迄点问题如果有多个货源地可以服务于多个目的地时，那么47多个起点和终点的路径优化，需要确定各供求地点之间的最佳供应关系。运用线性规划,数学模型可以描述为：有m个产地Ai，i=1，2，…，m，可供应量分别为ai，i=1，2，…，m；有n个销地Bj，j=1，2，…，n，需要量分别为bj，j=1，2，…，n；产销平衡，从Ai到Bj

运输单位货物的运价（也可以是时间或距离）为cij。问如何调运这些货物，使得运费（或时间、吨公里数）最少？

多个起点和终点的路径优化，需要确定各供求地点之间的最481、单纯形法

2、图表分析法4、表上作业法5、供求不平衡运输模型3、图上作业法常见的解决方法有：

1、单纯形法2、图表分析法4、表上作业法5、供求不平衡49图上作业法图上作业法根据交通图的点和线的关系，把各种路线归纳为道路不成圈（无圈）和道路成圈两类。道路不成圈，就是没有回路的“树”形路线，包括直线、丁字线、交叉线、分支线等；无圈的流向图只要消灭对流，就近送货，就是最优流向图。道路成圈，就是形成闭合回路的“环”状路线，包括一个圈和多个圈；成圈的流向图要达到既没有对流，又没有迂回的要求才是最优流向图。图上作业法图上作业法根据交通图的点和线的关系，把各种路线归纳501、消灭对流运输；

2、消灭迂回运输。（一）图上作业法要解决的问题511、消灭对流运输；（一）图上作业法要解决的问题51回顾一下什么是对流运输？20303020243(20)(20)(30)(30)这是对流20303020243(20)(20)(30)(30)(10)52回顾一下什么是对流运输？20303020243(20)(20206040402463(20)(20)(40)圈长：圈上每一条边的长度之和（记为l）l=15先用“丢边破圈”方法，得到无圈图，再产生一个没有对流的方案。内圈长

l内=8外圈长

l外=4是最优解码？称为迂回运输调整方案：对内圈各流量中最小调运量，进行反向调运(40)(20)(20)准则：内外圈长都小于圈长的一半的无对流的调运方案为最优方案什么又是迂回运输呢？53206040402463(20)(20)(40)圈长：圈上每三、图上作业法（二）交通图1、交通图的符号

发点用“

”表示，并将发货量记在里面，收点用“

”表示，并将收货量记在里面。两点间交通线的长度记在交通线旁边。2、调运物资的流向图

物资调运的方向（流向）用“

”表示，并把

“

”按调运方向画在交通线的右边，把调运物资的数量记在“

”的右边并加上括号。在交通图成圈时，若运输方向沿逆时针方向，则需将流向“”画在圈外，称为外圈流向，反之，若运输方向沿顺时针方向，则需将流向“”画在圈内，称为内圈流向，54三、图上作业法（二）交通图1、交通图的符号54道路不成圈任何一张交通网络图，其线路分布形状可分成圈和不成圈两类，对于不成圈的交通网络图，根据线性规划原理，物资调拨或空车调运线路的确定可依据“就近调空”原则进行。

没有对流运输即是最优方案。

方法：作一个没有对流的流向图，即由各端点开始，由外向里，逐步进行各收发点之间的收发平衡。道路不成圈任何一张交通网络图，其线路分布形状可分成圈和不成圈55【例4】有一种商品从A地运出40吨，从B地运出70吨，从C地运出30吨，从D地运出60吨，供给a、b、c三地的数量分别为70吨、80吨、50吨，应用图上作业法选择该商品的合理运输路线。ABCD调入量a70b80c50调出量40703060200运出地运入地【例4】有一种商品从A地运出40吨，从B地运出70吨，从C地5640707080506030BDCabcA40303020602040707080506030BDCabcA40303020657ABCD调入量a403070b206080c203050调出量40703060200ABCD调入量a403070b206080c203050调出58【例5】设产地甲、乙、丙、丁产量分别为70吨、40吨、90吨、50吨；销地A、B、C、D、E需求分别为30吨、70吨、50吨、60吨、40吨，试求合理的运输方案。ABCDE产量甲70乙40丙90丁50销量3070506040250销地产地【例5】设产地甲、乙、丙、丁产量分别为70吨、40吨、90吨59703040507050乙丁甲CBA6090丙ED4050304050703040507050乙丁甲CBA6090丙ED4050360404070乙甲B10D403010404070乙甲B10D40301061ABCDE产量甲304070乙301040丙504090丁5050销量3070506040250ABCDE产量甲304070乙301040丙504090丁562道路成圈对于成圈的交通网络，只要先假设某两点间线路“不通”，将成圈问题化为不成圈问题考虑，这样就可得到一个初始的调运方案。然后进一步作优化处理，其原则是：里圈、外圈分别算，要求不过半圈长；如若超过半圈长，应甩运量最小段；反复求算最优方案。道路成圈对于成圈的交通网络，只要先假设某两点间线路“不通”，63【例6】有某商品发送点A、B、C、D四处，与四个接收点a、b、c、d成圈状，其距离及供需量如表所示，试求最优运输路线。距离abcd产量A658080B180220150C9075170D6070100销量130100160110500接收地发送地【例6】有某商品发送点A、B、C、D四处，与四个接收点a、b64150100CAD17016010011080130Babcd15020100109070100150100CAD17016010011080130Babc65根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。L/2＝（220+180+65+80+70+60+75+90）/2＝420L内＝180+65+80+60+90＝445>L/2L外＝75+70＝145<L/2L内大于全圈长的一半，不是最优方案，应重新甩段破圈，甩内圈运量最小区段aA，寻找最优方案。根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。66150100CAD17016010011080130Babcd130807090803020150100CAD17016010011080130Babc67计算内外圈长：L/2＝（220+180+65+80+70+60+75+90）/2＝420L内＝180+80+60+90＝410<L/2L外＝70+75+220＝365<L/2将上述运输结果填入平衡表：计算内外圈长：68运量abcd产量A8080B13020150C8090170D7030100销量130100160110500接收地发送地运量abcd产量A8080B13020150C809017069【练习】某地区物资供销情况如图所示，现要求得物资调运的最优方案。3020502030607010020364523251823ABCDEFGHI【练习】某地区物资供销情况如图所示，现要求得物资调运的最优方7030205020306070100202020802030304010ABCDEFGHI30205020306070100202020802030371根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。L/2＝（45+23+25+18+23+36）/2＝85L内＝25+18+23＝66<L/2L外＝23+36＝59<L/2将上述运输结果填入平衡表：根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。72送货量BCEGI产量A2020D2020F10302040100H303060销量3050207030200接收地发送地送货量BCEGI产量A2020D2020F10302040173运量BCEGI产量A2020D2020F102070100H303060销量3050207030200接收地发送地运量BCEGI产量A2020D2020F102070100H74当运输路线有几个圈的情况，应逐圈检查并调整，直到每个圈都能符合要求，此时才能得到物资调拨的最优方案。【练习】29006002000100057ABCDEFHI900130032001000G1500900900784575132743257554174J166K当运输路线有几个圈的情况，应逐圈检查并调整，直到每个圈都能符75290060020001000ABCDEFHI900130032001000G1500900900J150010009009009008005001009001500K290060020001000ABCDEFHI900130076距离ACEFGIJK销量B15008009003200D5009006009002900H10010009002000产量15001300900600100010009009008100发送地接收地距离ACEFGIJK销量B15008009003200D5077表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法。它包括以下步骤：确定初始可行方案。方法比较多，一般希望方法既简单，又尽可能接近最优解，常用最小元素法、伏格尔法和左上角法。最优方案的判别。判别的方法是计算空格的检验数，常用闭回路法和位势法。改进方案。常使用闭回路调整法进行调整以得到最优的方案。表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法78确定初始基可行解

与一般的线性规划不同，产销平衡的运输问题一定具有可行解（同时也一定存在最优解）。最小元素法（theleastcostrule）、伏格尔法（Vogel’sapproximationmethod）和左上角法。

最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止.最小元素法确定初始基可行解与一般的线性规划不同，产销平衡的运输问题一79找出最小运价，确定供求关系，最大量的供应；划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；在剩余的运价表中重复1、2两步，直到得到初始基可行解。最小元素法的基本步骤找出最小运价，确定供求关系，最大量的供应；最小元素法的基80最小元素法最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止。最小元素法最小元素法的基本思想是就近供应，即从单位运价表中最81【例7】有某公司经销一产品，它下设三个加工厂，每日的产量分别为A1＝7吨、A2＝4吨，A3＝9吨，该公司把这些产品分别运往四个销售点。各个销售点每日销量为B1＝3吨，B2＝6吨，B3＝5吨，B4＝6吨，已知从各工厂到各销售点的单位产品的运价如表所示，问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费最少。B1B2B3B4A1311310A21928A374105销地加工厂最小元素法【例7】有某公司经销一产品，它下设三个加工厂，每日的产量分别82B1B2B3B4产量A13113107A219284A3741059销量3656销地加工厂314633B1B2B3B4产量A13113107A219284A37483B1B2B3B4A143A231A363销地加工厂B1B2B3B4A143A231A363销地加工厂84【例8】编制被运输商品的产销平衡表和单位运输价格如下表所示，试用最小元素法求出最优运输方案的初始方案。ABCDE发运量甲32353100乙33134300丙78422600丁54778800需求量2503003504005001800销地加工厂【例8】编制被运输商品的产销平衡表和单位运输价格如下表所示，85ABCDE发运量甲32353100乙33134300丙78422600丁54778800需求量2503003504005001800销地加工厂30010050010020025030050ABCDE发运量甲32353100乙33134300丙78486在供需关系格（i，j）处填入一数字，刚好使第i个产地的产品调空，同时也使第j个销地的需求得到满足。填入一数字同时划去了一行和一列，那么最终必然无法得到一个具有m+n-1个数字格（基变量）的初始基可行解。应注意的问题

为了使在产销平衡表上有m+n-1个数字格，这时需要在第行或第列此前未被划掉的任意一个空格上填一个“0”。填“0”格虽然所反映的运输量同空格没有什么不同；但它所对应的变量却是基变量，而空格所对应的变量是非基变量。在供需关系格（i，j）处填入一数字，刚好使第i87【练习】最小元素法123产量15181222411433674销量91011销地加工厂1011342【练习】最小元素法123产量151812224114336788伏格尔法最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大处，就应当采用最小运费调运。伏格尔法最小元素法的缺点是：为了节省一处的费用，有时造成在其89伏格尔法的基本步骤：1.计算每行、列两个最小运价的差；2.找出最大差所在的行或列；3.找出该行或列的最小运价，确定供求关系，最大量的供应；4.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；5.在剩余的运价表中重复1~4步，直到得到初始基可行解。伏格尔法的基本步骤：1.计算每行、列两个最小运价的差；90【例9】试用伏格尔求运输的最优方案。销地加工厂B1B2B3B4产量A13113107A219284A3741059销量3656【例9】试用伏格尔求运输的最优方案。销地加工厂B1B2B3B91销地加工厂B1B2B3B4产量A13113107A219284A3741059销量365601125136行差额列差额销地加工厂B1B2B3B4产量A13113107A2192892销地加工厂B1B2B3B4产量A13113107A219284A3741059销量365625136行差额列差额0123销地加工厂B1B2B3B4产量A13113107A2192893销地加工厂B1B2B3B4产量A13113107A219284A3741059销量36562126行差额列差额01233销地加工厂B1B2B3B4产量A13113107A2192894销地加工厂B1B2B3B4产量A13113107A219284A3741059销量3656126行差额列差额7633521销地加工厂B1B2B3B4产量A13113107A2192895销地加工厂B1B2B3B4产量A17A24A39销量3656633521销地加工厂B1B2B3B4产量A17A24A39销量36569612345产量11023159252510152430315514715204201513M830销量2020301025【练习】伏格尔法，M为无穷大的正数销地加工厂行差额列差额12255310542512345产量110231592525101524303159712345产量11023159252510152430315514715204201513M830销量2020301025销地加工厂行差额列差额1225105154252012345产量110231592525101524303159812345产量11023159252510152430315514715204201513M830销量2020301025销地加工厂行差额列差额12251051542520100（有时在产销平衡表上填入一个运量后，在单位运价表上同时划去一行和一列，这时需要添一个“0”，它的位置可在对应同时划去的那行或列的任一空格处）12345产量110231592525101524303159912345产量11023159252510152430315514715204201513M830销量2020301025销地加工厂行差额列差额12951017252010202550012345产量1102315925251015243031510012345产量125230320430销量2020301025销地加工厂252010202550012345产量125230320430销量202030102101【练习】伏格尔法123产量15181222411433674销量91011销地加工厂413行差额136列差额11【练习】伏格尔法123产量15181222411433674102【练习】123产量15181222411433674销量91011销地加工厂423行差额13列差额1110342【练习】123产量15181222411433674销量91103

左上角法

除了最小费用法外，左上角法也是求得运输初始方案的一种途径，并通过霍撤克法则最终得出最优运输方案。具体做法是：

［例］现有三个生产地A、B、C供应某种商品；有四个销售地1、2、3、4，各自供应量和需求量如表所示，试用左上角法求出最优运输方案。左上角法104运输路线优化课件105

第一步以运输表左上角的格子作为开端。第二步对这一格子可用的供应量与需求量作比较，安排两个值中较小的一个作为运量，然后，把这个数字圈起来。这一格可用的供应量(或需求量)减去安排的运量就是剩余的供应量(或需求量)。上表中有50个单位的供应量和30个单位的需求量。因此，可以安排30单位的运量到A1格。第三步如果安排运量的格子正好是在运输表的最右下角，就停止安排。这时，初始方案已找到。如果这一格不在最右下角，就进入到第四步。第一步以运输表左上角的格子作为开端。106

第四步根据以下规划，移到下一格：a．如果已安排的这一格行和列比较，供应量超过需求量，下一格移到同一行相邻的格子。b．如果需求量超过供应量，下一格移到同一列相邻的格子。c．如果需求量等于供应量，下一格是对角线上相邻的格子。

d．回到第二步。

根据左上角法求出运输初始方案后，为了进一步算出最优方案，仍需要运用霍撒克法则进行优化第四步根据以下规划，移到下一格：107运输路线优化课件108运输路线优化课件109运输路线优化课件110运输路线优化课件111单位销地运价产地产量4124111621039108511522销量814121448练习

某部门有3个生产同类产品的工厂（产地）,生产的产品由4个销售点（销地）出售，各工厂的生产量、个销售点的销售量（假定单位均为t)以及各工厂到个销售点的单位云价（元/t)示于下表，试研究如何调运才能使总的运费最小？单位销地产量412411162103910851(1)

最小元素法(1)

最小元素法(2)西北角法(2)西北角法2最优方案的判别对初始基可行解的最优性检验有闭合回路法和位势法两种基本方法。闭合回路法具体、直接，并为方案调整指明了方向；而位势法具有批处理的功能，提高了计算效率。2最优方案的判别对初始基可行解的最优性检验有闭合回路法115所谓闭合回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为1，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。(1).闭合回路法

σij<0表示运费减少，σij>0表示运费增加。所谓闭合回路法，就是对于代表非基变量的空格（其调运量为零），116所谓闭合回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭合回路。一个空格存在唯一的闭回路。所谓闭合回路是在已给出的调运方案的运输表上从一个代表非基变量117例一、某运输资料如下表所示：单位销地运价产地产量311310719284741059销量3656例一、某运输资料如下表所示：单位销地产量3113B1B2B3B4产量A13113107A219284A3741059销量3656销地加工厂314633B1B2B3B4产量A13113107A219284A374119B1B2B3B4A143A231A363销地加工厂B1B2B3B4A143A231A363销地加工厂120B1B2B3B4产量A17A24A39销量3656313463（＋1）（＋1）（－1）（－1）①②③③

计算如下：空格处（A1

B1

）＝

(1×3)＋｛(－1)×3｝＋(1×2)＋｛(－1)×1｝＝1

此数即为该空格处的检验数。1B1B2B3B4产量A17A24A39销量365631346B1B2B3B4产量A17A24A39销量365631363124B1B2B3B4产量A17A24A39销量365631363B1B2B3B4产量A17A24A39销量36563136312-14B1B2B3B4产量A17A24A39销量365631363B1B2B3B4产量A17A24A39销量365631363121-14B1B2B3B4产量A17A24A39销量365631363B1B2B3B4产量A17A24A39销量365631363121-1124B1B2B3B4产量A17A24A39销量365631363B1B2B3B4产量A17A24A39销量365631363121-112104

检验数中有负数，说明原方案不是最优解。B1B2B3B4产量A17A24A39销量365631363B1B2B3B4产量A17A24A39销量365600000121-112100B1B2B3B4产量A17A24A39销量3656000002、最优方案的判别——位势法使用位势法求出检验数，若检验数都不为负数，则原方案为最优解，若有负检验数存在，则负检验数所在空格需进行调整。只有没有运量的空格处需要计算检验数。2、最优方案的判别——位势法使用位势法求出检验数，若检验数都1282、最优方案的判别——位势法检验数的计算方法如下：设有运量的格子数最多的行或列的位势＝0有运量格子的运价＝行位势+列位势空格的检验数＝运价-（行位势+列位势）

2、最优方案的判别——位势法检验数的计算方法如下：129接上例：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表B1B2B3B4A1293100A21829－1A3－34－25－529310u2+v1=1

u2+v3=2

u3+v2=4u1+v4=10

u1+v3=3u3+v4=5

令：u1＝0u1＝0v1＝2u2＝－1v2＝9u3＝－5v3＝3v4＝10(ui+vj)接上例：B1B2B3B4A1310u1A212u2A345u

按σij=cij－(ui+vj)

计算检验数，并以σij≥0

检验，或用(ui+vj)

－cij

≤0检验。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A3－34-25(ui+vj)－B1B2B3B4A11200A2010－1A3100120＝表中还有负数，说明还未得到最优解，应继续调整。σij按σij=cij－(ui+vj)计算检验数ABCDE发运量甲32353100乙33134300丙78422600丁54778800需求量2503003504005001800销地加工厂3001005005050250250300【练习】下面是用最小元素法的得出的运输方案，试用位势法判断是否最优。ABCDE发运量甲32353100乙33134300丙784132ABCDE行位势甲32•3•53乙331•34丙7842•2•丁5•4•77•8列位势销地加工厂0547-25-4-5700-2230179421ABCDE行位势甲32•3•53乙331•34丙7841333、改进方案——闭合回路调整法从负检验数所在格子出发找一条闭合回路，用水平或垂直线向前划，每碰到数字格可以转90度，然后继续前进，直到回到起始空格为止。并从出发格开始依次标上正负号。将所有标有负号的转角格中的最小运量作为调整数。各正号加上调整数，负号减去调整数。3、改进方案——闭合回路调整法从负检验数所在格子出发找一条闭134【例11】使用闭合回路法对例10进行调整。B1B2B3B4行位势A13113•10•A21•92•8A374•105•列位势销地加工厂0310-1-529121-11012【例11】使用闭合回路法对例10进行调整。B1B2B3B4行135B1B2B3B4产量A13113107A219284A3741059销量3656销地加工厂314633++--152B1B2B3B4产量A13113107A219284A374136ABCDE行位势甲32•3•53乙331•34丙7842•2•丁5•4•77•8列位势销地加工厂0547-25-4-5700-2230179421【练习】使用闭合回路法对上一个练习题进行调整。ABCDE行位势甲32•3•53乙331•34丙784137ABCDE发运量甲32353100乙33134300丙78422600丁54778800需求量2503003504005001800销地加工厂3001005005050250250300+++---ABCDE发运量甲32353100乙33134300丙784138ABCDE发运量甲32353100乙33134300丙78422600丁54778800需求量2503003504005001800销地加工厂3001504505050300250250+++---ABCDE发运量甲32353100乙33134300丙784139【例12】试用伏格尔法求，并检验，得出最优运输方案。1234供应量A1067124B1610599C5410104销量5246销地加工厂费用【例12】试用伏格尔法求，并检验，得出最优运输方案。12341401234供应量A1067124B1610599C5410104销量5246销地加工厂费用行差额14列差额2115241234供应量A1067124B1610599C5410101411234供应量A1067124B1610599C5410104销量5246销地加工厂费用行差额14列差额23164411234供应量A1067124B1610599C5410101421234供应量A1067124B1610599C5410104销量5246销地加工厂费用行差额14列差额2344141234供应量A1067124B1610599C5410101431234供应量A1067124B1610599C5410104销量5246销地加工厂费用行差额61列差额2344142151234供应量A1067124B1610599C5410101441234行位势A106712B161059C541010列位势销地加工厂费用414215010612-3-58-1973731234行位势A106712B161059C541010列位1451234行位势A106712B161059C541010列位势销地加工厂费用414215+-+-1361234行位势A106712B161059C541010列位1461234行位势A106712B161059C541010列位势销地加工厂费用41213601067-2-5111863841234行位势A106712B161059C541010列位1471234行位势ABC列位势销地加工厂运量412136最优运输方案如下1234行位势ABC列位势销地加工厂运量412136最优运输148【练习】试用伏格尔法求，并检验，得出最优运输方案。1234供应量A1518191350B2014151730C2512172270销量30602040150销地加工厂费用【练习】试用伏格尔法求，并检验，得出最优运输方案。1234供1491234供应量A1518191350B2014151730C2512172270销量30602040150销地加工厂费用行差额215列差额5224601234供应量A1518191350B2014151730C1501234供应量A1518191350B2014151730C2512172270销量30602040150销地加工厂费用行差额225列差额522460301234供应量A1518191350B2014151730C1511234供应量A1518191350B2014151730C2512172270销量30602040150销地加工厂费用行差额625列差额52246030201234供应量A1518191350B2014151730C1521234供应量A1518191350B2014151730C2512172270销量30602040150销地加工厂费用行差额25列差应量A1518191350B2014151730C1531234行位势A15•181913•B201415•17•C2512•17•22列位势销地加工厂费用015134116612814431234行位势A15•181913•B201415•11541234供应量A50B30C70销量30602040150销地加工厂运量603020201010最优运输方案如下1234供应量A50B30C70销量30602040150销155【练习】试用最小元素法求，并检验，得出最优运输方案。123供应量A51312B24114C3674销量91011销地加工厂费用【练习】试用最小元素法求，并检验，得出最优运输方案。123供156123供应量A51312B24114C3674销量91011销地加工厂费用1011342123供应量A51312B24114C3674销量91011157123行位势A513B241C367列位势销地加工厂费用10113420523-4-1-1675123行位势A513B241C367列位势销地加工厂费用10158123行位势A513B241C367列位势销地加工厂费用1011342+-+-123行位势A513B241C367列位势销地加工厂费用10159123行位势A513B241C367列位势销地加工厂费用10954+-+-2123行位势A513B241C367列位势销地加工厂费用10160123行位势A513B241C367列位势销地加工厂费用109542013-24-11565123行位势A513B241C367列位势销地加工厂费用10161123行位势ABC列位势销地加工厂运量109542最优运输方案如下123行位势ABC列位势销地加工厂运量109542最优运输方162供求不均衡运输在运输的实际工作中，由于经济活动和市场环境的多变性，经常会存在供求不平衡的现象，此时应对上述的方法进行一定的修正。修正的基本思路是：化不均衡为均衡，如果出现供求不平衡，则设一个虚销点或虚发点，得出最优方案后再去掉虚设的点。供求不均衡运输在运输的实际工作中，由于经济活动和市场环境的多163【例12】1234供应量A1518191350B2014151755C2512172270销量30602040销地加工厂费用【例12】1234供应量A1518191350B201415164【例12】12345供应量20141517055C25121722070销量30