运输路线优化课件.ppt

1、u运输路线的选择影响到运输设备和人员的利用，正确地运输路线的选择影响到运输设备和人员的利用，正确地确定合理的运输路线可以降低运输成本，因此运输路线确定合理的运输路线可以降低运输成本，因此运输路线的确定是运输决策的一个重要领域。安排运输路线和时的确定是运输决策的一个重要领域。安排运输路线和时间的几个原则如下：间的几个原则如下：l将将相互接近的停留点的货物装在一辆车上运送，以便停相互接近的停留点的货物装在一辆车上运送，以便停留点之间的运行距离最小化；留点之间的运行距离最小化；u车辆的运输路线应将邻近的停留点串起来，以使停留点之间的车辆的运输路线应将邻近的停留点串起来，以使停留点之间的运输距离最小化

2、，这样也就使总的路线上的运输时间最短。运输距离最小化，这样也就使总的路线上的运输时间最短。l将集聚在一起的停留点安排同一天送货，要避免不是同将集聚在一起的停留点安排同一天送货，要避免不是同一天送货的停留点在运行路线上重叠；一天送货的停留点在运行路线上重叠；l运行路线从离仓库最远的停留点开始。运行路线从离仓库最远的停留点开始。u运行路线从离仓库最远的停留点开始，送货车辆依次装载临运行路线从离仓库最远的停留点开始，送货车辆依次装载临近这个关键停留点的一些停留点的货物，这辆货车满载后，近这个关键停留点的一些停留点的货物，这辆货车满载后，再安排另一辆货车装载另一个最远的停留点的货物。再安排另一辆货车装

3、载另一个最远的停留点的货物。仓库仓库4.一辆货车顺次途径各停留点的路线尽量不交叉，要成泪滴一辆货车顺次途径各停留点的路线尽量不交叉，要成泪滴状。状。l在多种规格车型的车队中，应优先使用载重量最大的货在多种规格车型的车队中，应优先使用载重量最大的货车。车。u在运输货物时，最好是使用一辆载重量大到能将路线上所在运输货物时，最好是使用一辆载重量大到能将路线上所有停留点所要求运送的货物都装载的货车，这样可以将服有停留点所要求运送的货物都装载的货车，这样可以将服务区停留点的总的运行距离或时间最小化。务区停留点的总的运行距离或时间最小化。l提货应混在送货过程中进行，而不要在运行路线结束后提货应混在送货过程

4、中进行，而不要在运行路线结束后再进行。再进行。u提货应尽可能在送货过程中进行，以减少交叉路程量，而提货应尽可能在送货过程中进行，以减少交叉路程量，而在送货结束后再进行提货经常会发生路程交叉。在送货结束后再进行提货经常会发生路程交叉。l对偏离集聚停留点路线远的单独的停留点可专门安排车对偏离集聚停留点路线远的单独的停留点可专门安排车辆送货辆送货 。u偏离集聚停留点少，特别是那些送货量小的停留点一般要偏离集聚停留点少，特别是那些送货量小的停留点一般要花费大量的时间和费用，因此适用小载重量的车辆专门为花费大量的时间和费用，因此适用小载重量的车辆专门为这些停留点送货是合理的。这些停留点送货是合理的。l

5、另一个可供选择的方案是租用车辆或采用公共服务（如另一个可供选择的方案是租用车辆或采用公共服务（如邮政服务）为这些停车邮政服务）为这些停车点点送货。送货。8. 应当避免停留点工作时间太短的约束。应当避免停留点工作时间太短的约束。u停留点工作时间太短会迫使途经停留点的顺序偏离理想状停留点工作时间太短会迫使途经停留点的顺序偏离理想状态。态。运输路线决策就是，找到运输网络中的最佳路线，以尽可能缩短运输时间或运输距离，达到降低运输成本、改善运输服务的目标。 运输路线决策问题有三种基本类型：运输路线决策问题有三种基本类型： 一是起点和终点不同的单一路径规划； 二是多个起点和终点的路径规划； 三是起点和终点

6、相同的路径规划。一、起点和终点不同的单一路径规划一、起点和终点不同的单一路径规划 此类问题可以描述为在一个已知交通运输网络中，寻找从出发地到目的地的最佳路线。这里的“最佳”可以指可以指距离最短、时间最省或是费用最少。距离最短、时间最省或是费用最少。数学模型求网络图中二点之间的最短路问题。采用网络规划中求最短路DijkstraDijkstra算法（标号算法）算法（标号算法）。除了距离以外，还需要考虑通过交通网络的时间长短时间长短。 对分离的、单个始发点和终点的网络运输路线对分离的、单个始发点和终点的网络运输路线选择问题，最简单和直观的方法是最短路线法。选择问题，最简单和直观的方法是最短路线法。初

7、始，除始发点外，所有节点都被认为是未解的，初始，除始发点外，所有节点都被认为是未解的，即均未确定是否在选定的运输路线上。始发点作即均未确定是否在选定的运输路线上。始发点作为已解的点，计算从原点开始。为已解的点，计算从原点开始。 一般的计算方法是：一般的计算方法是： (1) (1)第第n n次迭代的目标。寻求第次迭代的目标。寻求第n n次最近始发点的节点，次最近始发点的节点，重复重复n n1 1，2 2，直到最近的节点是终点为止。，直到最近的节点是终点为止。 (2) (2)第第n n次迭代的输入值。次迭代的输入值。(n1)(n1)个最近始发点的节点个最近始发点的节点是由以前的迭代根据离始发点最短

8、路线和距离计算而得的。是由以前的迭代根据离始发点最短路线和距离计算而得的。 (3) (3)第第n n个最近节点的侯选点。每个已解的节点由线路个最近节点的侯选点。每个已解的节点由线路分支通向一个或多个尚未解的节点，这些未解的节点中有分支通向一个或多个尚未解的节点，这些未解的节点中有一个以最短路线分支连接的是候选点。一个以最短路线分支连接的是候选点。 (4) (4)第第n n个最近的节点的计算。将每个已解节点及其个最近的节点的计算。将每个已解节点及其候选点之间的距离和从始发点到该已解节点之间的距离加候选点之间的距离和从始发点到该已解节点之间的距离加起来，总距离最短的候选点即是第起来，总距离最短的候

9、选点即是第n n个最近的节点。也就个最近的节点。也就是始发点到达该点最短距离的路径。是始发点到达该点最短距离的路径。 以下面的实例可以具体说明最短运输路线是怎样计算以下面的实例可以具体说明最短运输路线是怎样计算的。的。【例】如图所示是一张公路运输网示意图，其中【例】如图所示是一张公路运输网示意图，其中A是起点，是起点，J是终点，是终点，B、C、D、E、G、H、I是网是网络中的结点，结点与结点之间以线路连接，线路络中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表上标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点示。要求确定一条从起点A到终点到终点J

10、的最短的运输的最短的运输路线。路线。A起点起点BEIJ终点终点HFCDG8490841383481564813215090601321264812666120 我们首先列出一张如表格我们首先列出一张如表格3 33 3所示的表格。所示的表格。第一个已解的节点就是起点或点第一个已解的节点就是起点或点A A。与。与A A点直接连点直接连接的解的节点有接的解的节点有B B、C C和和D D点。第一步，我们可以看点。第一步，我们可以看到到B B点是距点是距A A点最近的节点，记为点最近的节点，记为ABAB。由于。由于B B点是唯点是唯一选择，所以它成为已解的节点。一选择，所以它成为已解的节点。 随后，找

11、出距随后，找出距A A点和点和B B点最近的未解的节点。只要列出点最近的未解的节点。只要列出距各个已解的节点最近的连接点，我们有距各个已解的节点最近的连接点，我们有A-CA-C，B BC C。记。记为第二步。注意从起点通过已解的节点到某一节点所需的为第二步。注意从起点通过已解的节点到某一节点所需的时间应该等于到达这个已解节点的最短时间加上已解节点时间应该等于到达这个已解节点的最短时间加上已解节点与未解节点之间的时间，也就是说，从与未解节点之间的时间，也就是说，从A A点经过点经过B B点到达点到达C C的距离为的距离为AB+BCAB+BC90+6690+66156156分，而从分，而从A A直

12、达直达C C的时间为的时间为138138分。现在分。现在C C也成了已解的节点。也成了已解的节点。 第三次迭代要找到与各已解节点直接连接的最近的未第三次迭代要找到与各已解节点直接连接的最近的未解节点。如表解节点。如表3 33 3所示，有三个候选点，从起点到这三个所示，有三个候选点，从起点到这三个候选点候选点D D、E E、F F所需的时间，相应为所需的时间，相应为348348、174174、228228分，其分，其中连接中连接BEBE的时间最短，为的时间最短，为174174分，因此正点就是第三次迭分，因此正点就是第三次迭代的结果。代的结果。 重复上述过程直到到达终点重复上述过程直到到达终点J

13、J，即第八步。最小的路，即第八步。最小的路线时间是线时间是384384分，连线在表分，连线在表3 33 3上以星上以星( (并并) )符号标出者，符号标出者，最优路线为最优路线为A-B-E-I-JA-B-E-I-J。 在节点很多时用手工计算比较繁杂，如果把网络的节在节点很多时用手工计算比较繁杂，如果把网络的节点和连线的有关数据存入数据库中，绝对的最短距离路径点和连线的有关数据存入数据库中，绝对的最短距离路径并不说明穿越网络的最短时间，因为该方法没有考虑各条并不说明穿越网络的最短时间，因为该方法没有考虑各条路线的运行质量。路线的运行质量。 因此，对运行时间和距离都设定权数就可以得出比较因此，对运

14、行时间和距离都设定权数就可以得出比较具有实际意义的路线。具有实际意义的路线。【练习】如图所示是一张公路运输网示意图，其中【练习】如图所示是一张公路运输网示意图，其中A是起点，是起点，I是终点，是终点，B、C、D、E、G、H是网络是网络中的结点，结点与结点之间以线路连接，线路上中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表示。标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点要求确定一条从起点A到终点到终点I的最短的运输路线。的最短的运输路线。A起点起点BCDEFGHI终点终点2040606030605050505020453080100物流管理人

15、员经常遇到的一个路线选择问题是始发点就是终物流管理人员经常遇到的一个路线选择问题是始发点就是终点的路线选择。这类问题通常在运输工具是同一部门所有点的路线选择。这类问题通常在运输工具是同一部门所有的情况下发生。始发点和终点相合的路线选择问题通常被的情况下发生。始发点和终点相合的路线选择问题通常被称为称为“旅行推销员旅行推销员”问题，对这类问题应用经验探试法比问题，对这类问题应用经验探试法比较有效。较有效。 经验告诉我们，当运行路线不发生交叉时，经过各经验告诉我们，当运行路线不发生交叉时，经过各停留点的次序是合理的，同时，如有可能应尽量使运行路停留点的次序是合理的，同时，如有可能应尽量使运行路线形

16、成泪滴状。图线形成泪滴状。图3 32 2所示是通过各点的运行路线示意图，所示是通过各点的运行路线示意图，其中图其中图3 32(a)2(a)是不合理的运行路线，图是不合理的运行路线，图3 32(b)2(b)是合理的是合理的运行路线。根据上述运行路线。根据上述“运行路线不发生交叉运行路线不发生交叉”“”“运行路线运行路线形成泪滴状形成泪滴状”两点原则。两点原则。（1 1）人工计算方法）人工计算方法扫描法扫描法 问题：对于若干个停车点（客户）安排最优行车路线。问题：对于若干个停车点（客户）安排最优行车路线。第一步，将仓库（出发点）和所有的停车点位置画在地图第一步，将仓库（出发点）和所有的停车点位置画

17、在地图上或坐标图上；上或坐标图上；第二步，通过仓库位置放置一直尺，然后顺时针或逆时针第二步，通过仓库位置放置一直尺，然后顺时针或逆时针方向转动，直到直尺交到一个停车点。询问：方向转动，直到直尺交到一个停车点。询问：累计的装货累计的装货量是否超过送货的载重量或容积（首先要使用最大的送货量是否超过送货的载重量或容积（首先要使用最大的送货车辆）车辆）。如是，最后的停车点排除，将路线确定下来。然。如是，最后的停车点排除，将路线确定下来。然后再从这个停车点开始继续扫描，开始一条新的路线。这后再从这个停车点开始继续扫描，开始一条新的路线。这样扫描下去，直至全部的停留点都被分配到路线上。样扫描下去，直至全部

18、的停留点都被分配到路线上。 第三步，对每条路线安排运行顺序，以求运行距离最小化。第三步，对每条路线安排运行顺序，以求运行距离最小化。方案的误差率在方案的误差率在10%10%左右。左右。扫描法扫描法 是是是是开始开始将所有的停留点位置画在地图上将所有的停留点位置画在地图上选择适当的车辆装载这个停留点的货物选择适当的车辆装载这个停留点的货物然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。通过仓库位置放置一直尺，直尺指向任何方向均可通过仓库位置放置一直尺，直尺指向任何方向均可是否超过车辆容积或体积是否超过车辆容积或体积的限度的限度是否扫

19、描完所有是否扫描完所有停留点停留点安排下一辆车装载货物，得到一条运行线路安排下一辆车装载货物，得到一条运行线路结束结束继续转动直尺，扫描到下一个停留点，分配该车辆继续转动直尺，扫描到下一个停留点，分配该车辆装载货物装载货物优化每条运行路线的停留点顺序，以求运行距离最小优化每条运行路线的停留点顺序，以求运行距离最小化化否否否否l【例】某公司从其所属的仓库用送货车辆到各客户点提货，【例】某公司从其所属的仓库用送货车辆到各客户点提货，然后将客户的货物运回仓库，以便集运成大的批量再进行然后将客户的货物运回仓库，以便集运成大的批量再进行远程运输。全天的提货量见下图，提货量以件为单位。送远程运输。全天的提

20、货量见下图，提货量以件为单位。送货车每次可运载货车每次可运载1万件，完成一次运行路线一般需要一天万件，完成一次运行路线一般需要一天时间。该公司要求确定：需多少条路线（即多少辆送货时间。该公司要求确定：需多少条路线（即多少辆送货车）；每条路线上有哪几个客户点；送货车辆途经有关客车）；每条路线上有哪几个客户点；送货车辆途经有关客户点的顺序。户点的顺序。400040001000100030003000200020001000100020002000200020002000200020002000300030002000200030003000【例例】某运输公司为其客户企业提供取货服务，货物运回仓库某

21、运输公司为其客户企业提供取货服务，货物运回仓库集中后，将以更大的批量进行长途运输。所有取货任务均由集中后，将以更大的批量进行长途运输。所有取货任务均由载重量为载重量为1010吨的货车完成。现在有吨的货车完成。现在有1313家客户有取货要求，各家客户有取货要求，各客户的去货量、客户的地理位置坐标见表客户的去货量、客户的地理位置坐标见表7-107-10。运输公司仓。运输公司仓库的坐标为（库的坐标为（19.5019.50，5.565.56）。要求合理安排车辆，并确定各）。要求合理安排车辆，并确定各车辆行驶路线，使总运输里程最短。车辆行驶路线，使总运输里程最短。 3 2 2.4 2.8 3.11.8

22、2.5 2.25 2.6 2.11.5 1.9 1.6 1#线路 2#线路 3#线路 11 12 9 10 7 8 2 1 5 4 3 13 6 0 (2)节约里程法 基本原理 基本原理是几何学中三角形一边之长必定小于另外两边之和。 节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。 假如一家配送中心（DC）向两个用户A、B运货，配送中心到两用户的最短距离分别是La和Lb，A和B间的最短距离为Lab，A、B的货物需求量分别是Qa和Qb，且（Qa+Qb）小于运

23、输装载量Q，如图所示，如果配送中心分别送货，那么需要两个车次，总路程为：L1=2（La+Lb）。ABDCLaLbABDCLaLb Lab 如果改用一辆车对两客户进行巡回送货，则只需一个车次,行走的总路程为： L2=La+Lb+Lab 有三角形的性质我们知道： LabL/2lL外外75+70145L/2lL内内大于全圈长的一半，不是最优方案，应重新甩段大于全圈长的一半，不是最优方案，应重新甩段破圈，甩内圈运量最小区段破圈，甩内圈运量最小区段a A，寻找最优方案。，寻找最优方案。150100CAD17016010011080130Babcd130807090803020l计算内外圈长：计算内外圈长

24、：lL/2（220+180+65+80+70+60+75+90）/2420lL内内180+80+60+90410L/2lL外外70+75+220365L/2l将上述运输结果填入平衡表：将上述运输结果填入平衡表：运量运量abcd产量产量A8080B13020150C8090170D7030100销量销量130100160110500接收地接收地发送地发送地【练习】某地区物资供销情况如图所示，现要求得物【练习】某地区物资供销情况如图所示，现要求得物资调运的最优方案。资调运的最优方案。3020502030607010020364523251823ABCDEFGHI302050203060701002

25、02020802030304010ABCDEFGHIl根据图中箭头将内外圈货流里程汇总，检查是否超根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。过全圈长的一半。lL/2（45+23+25+18+23+36）/285lL内内25+18+2366L/2lL外外23+3659L/2l将上述运输结果填入平衡表：将上述运输结果填入平衡表：送货量送货量BCEGI产量产量A2020D2020F10302040100H303060销量销量3050207030200接收地接收地发送地发送地运量运量BCEGI产量产量A2020D2020F102070100H303060销量销量30502070302

26、00接收地接收地发送地发送地l当运输路线有几个圈的情况，应逐圈检查并调整，当运输路线有几个圈的情况，应逐圈检查并调整，直到每个圈都能符合要求，此时才能得到物资调拨直到每个圈都能符合要求，此时才能得到物资调拨的最优方案。的最优方案。【练习】【练习】29006002000100057ABCDEFHI900130032001000G1500900900784575132743257554174J166K290060020001000ABCDEFHI900130032001000G1500900900J150010009009009008005001009001500K距离距离ACEFGIJK销量销量

27、B15008009003200D5009006009002900H10010009002000产量产量15001300900600100010009009008100发送地发送地接收地接收地l表上作业法是单纯形法在求解运输问题时的一表上作业法是单纯形法在求解运输问题时的一种简化方法。它包括以下步骤：种简化方法。它包括以下步骤：l确定初始可行方案。方法比较多，一般希望方确定初始可行方案。方法比较多，一般希望方法既简单，又尽可能接近最优解，常用最小元法既简单，又尽可能接近最优解，常用最小元素法、伏格尔法和左上角法。素法、伏格尔法和左上角法。l最优方案的判别。判别的方法是计算空格的检最优方案的判别。

28、判别的方法是计算空格的检验数，常用闭回路法和位势法。验数，常用闭回路法和位势法。1.改进方案。常使用闭回路调整法进行调整以得改进方案。常使用闭回路调整法进行调整以得到最优的方案。到最优的方案。确定初始基可行解确定初始基可行解 |与一般的线性规划不同，与一般的线性规划不同，产销平衡的运输问产销平衡的运输问题一定具有可行解（同时也一定存在最优解题一定具有可行解（同时也一定存在最优解）。）。|最小元素法（最小元素法（the least cost rule）、伏格尔法）、伏格尔法（Vogels approximation method）和左上角）和左上角法。法。 z最小元素法的基本思想是就近供应，即从

29、单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止.最小元素法|找出最小运价，确定供求关系，最大量的供找出最小运价，确定供求关系，最大量的供应应 ；|划掉已满足要求的行或划掉已满足要求的行或 ( (和和) ) 列，如果需要列，如果需要同时划去行和列，必须要在该行或列的任意同时划去行和列，必须要在该行或列的任意位置填个位置填个“0”“0”；|在剩余的运价表中重复在剩余的运价表中重复1 1、2 2两步，直到得到两步，直到得到初始基可行解。初始基可行解。 最小元素法的基本步骤最小元素法的基本步骤|最小元素法最小元素法l最小元素法的基本思想是就近供应，即最小元素法的基本思想是就近

30、供应，即从单位运价表中最小的运价开始确定产从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方销关系，依此类推，一直到给出基本方案为止。案为止。l【例【例7】有某公司经销一产品，它下设三个加工厂，每日的产】有某公司经销一产品，它下设三个加工厂，每日的产量分别为量分别为A17吨、吨、A24吨，吨，A39吨，该公司把这些产品吨，该公司把这些产品分别运往四个销售点。各个销售点每日销量为分别运往四个销售点。各个销售点每日销量为B13吨，吨，B26吨，吨，B35吨，吨，B46吨，已知从各工厂到各销售点的单吨，已知从各工厂到各销售点的单位产品的运价如表所示，问该公司应如何调运产品，在满足位

31、产品的运价如表所示，问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费最少。各销点的需要量的前提下，使总运费最少。B1B2B3B4A1311310A21928A374105销地销地加工厂加工厂B1B2B3B4产量产量A13113107A219284A3741059销量销量3656销地销地加工厂加工厂314633B1B2B3B4A143A231A363销地销地加工厂加工厂l【例【例8】编制被运输商品的产销平衡表和单位运输价格如下表】编制被运输商品的产销平衡表和单位运输价格如下表所示，试用最小元素法求出最优运输方案的初始方案。所示，试用最小元素法求出最优运输方案的初始方案。ABCDE发

32、运量发运量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800销地销地加工厂加工厂ABCDE发运量发运量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800销地销地加工厂加工厂30010050010020025030050 应注意的问题 l【练习】最小元素法【练习】最小元素法123产量产量15181222411433674销量销量91011销地销地加工厂加工厂1011342l最小元素法的缺点是：为了节省一处的费用，最小元素法的缺点是：为了节

33、省一处的费用，有时造成在其它处要多花几倍的运费。有时造成在其它处要多花几倍的运费。l伏格尔法考虑到，一产地的产品假如不能按伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就最小运费就近供应，就考虑次小运费，这就有一个差额，有一个差额，差额越大，说明不能按最小运差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大费调运时，运费增加越多，因而对差额最大处，就应当采用最小运费调运处，就应当采用最小运费调运。伏格尔法的基本步骤：伏格尔法的基本步骤：1.1.计算每行、列两个最小运价的差；计算每行、列两个最小运价的差；2.2.找出最大差所在的行或列；找出最大差所在的行

34、或列；3.3.找出该行或列的最小运价，确定供求关系，最大量找出该行或列的最小运价，确定供求关系，最大量的供应的供应 ；4.4.划掉已满足要求的行或划掉已满足要求的行或 ( (和和) ) 列，如果需要同时划列，如果需要同时划去行和列，必须要在该行或列的任意位置填个去行和列，必须要在该行或列的任意位置填个“0”“0”；5.5.在剩余的运价表中重复在剩余的运价表中重复1414步，直到得到初始基可步，直到得到初始基可行解。行解。l【例【例9】试用伏格尔求运输的最优方案。】试用伏格尔求运输的最优方案。销地销地加工厂加工厂B1B2B3B4产量产量A13113107A219284A3741059销量销量36

35、56销地销地加工厂加工厂B1B2B3B4产量产量A13113107A219284A3741059销量销量365601125136行差额行差额列差额列差额销地销地加工厂加工厂B1B2B3B4产量产量A13113107A219284A3741059销量销量365625136行差额行差额列差额列差额0123销地销地加工厂加工厂B1B2B3B4产量产量A13113107A219284A3741059销量销量36562126行差额行差额列差额列差额01233销地销地加工厂加工厂B1B2B3B4产量产量A13113107A219284A3741059销量销量3656126行差额行差额列差额列差额76335

36、21销地销地加工厂加工厂B1B2B3B4产量产量A17A24A39销量销量365663352112345产量产量11023159252510152430315514715204201513M830销量销量2020301025l【练习】伏格尔法，【练习】伏格尔法，M为无穷大的正数为无穷大的正数销地销地加工厂加工厂行差额行差额列差额列差额12255310542512345产量产量11023159252510152430315514715204201513M830销量销量2020301025销地销地加工厂加工厂行差额行差额列差额列差额1225105154252012345产量产量1102315925

37、2510152430315514715204201513M830销量销量2020301025销地销地加工厂加工厂行差额行差额列差额列差额12251051542520100l（有时在产销平衡表上填入一个运量后，在单位运价表上同时（有时在产销平衡表上填入一个运量后，在单位运价表上同时划去一行和一列，这时需要添一个划去一行和一列，这时需要添一个“0”，它的位置可在对应同，它的位置可在对应同时划去的那行或列的任一空格处）时划去的那行或列的任一空格处）12345产量产量11023159252510152430315514715204201513M830销量销量2020301025销地销地加工厂加工厂行差

38、额行差额列差额列差额12951017252010202550012345产量产量125230320430销量销量2020301025销地销地加工厂加工厂2520102025500l【练习】伏格尔法【练习】伏格尔法123产量产量15181222411433674销量销量91011销地销地加工厂加工厂413行差额行差额136列差额列差额11l【练习】【练习】123产量产量15181222411433674销量销量91011销地销地加工厂加工厂423行差额行差额13列差额列差额1110342 左上角法左上角法 除了最小费用法外，左上角法也是求得运输初始除了最小费用法外，左上角法也是求得运输初始方案的

39、一种途径，并通过霍撤克法则最终得出最方案的一种途径，并通过霍撤克法则最终得出最优运输方案。具体做法是：优运输方案。具体做法是： 例现有三个生产地例现有三个生产地A、B、C供应某种商品；供应某种商品；有四个销售地有四个销售地1、2、3、4，各自供应量和需求量，各自供应量和需求量如表所示，试用左上角法求出最优运输方案。如表所示，试用左上角法求出最优运输方案。 第一步第一步 以运输表左上角的格子作为开端。以运输表左上角的格子作为开端。 第二步第二步 对这一格子可用的供应量与需求量作对这一格子可用的供应量与需求量作比较，安排两个值中较小的一个作为运量，然比较，安排两个值中较小的一个作为运量，然后，把这

40、个数字圈起来。这一格可用的供应量后，把这个数字圈起来。这一格可用的供应量( (或需求量或需求量) )减去安排的运量就是剩余的供应量减去安排的运量就是剩余的供应量( (或需求量或需求量) )。上表中有。上表中有5050个单位的供应量和个单位的供应量和3030个单位的需求量。因此，可以安排个单位的需求量。因此，可以安排3030单位的运单位的运量到量到A1A1格。格。 第三步第三步 如果安排运量的格子正好是在运输表如果安排运量的格子正好是在运输表的最右下角，就停止安排。这时，初始方案已的最右下角，就停止安排。这时，初始方案已找到。如果这一格不在最右下角，就进入到第找到。如果这一格不在最右下角，就进入

41、到第四步。四步。 第四步第四步 根据以下规划，移到下一格：根据以下规划，移到下一格： a a如果已安排的这一格行和列比较，供应如果已安排的这一格行和列比较，供应量超过需求量，下一格移到同一行相邻的量超过需求量，下一格移到同一行相邻的格子。格子。 b b如果需求量超过供应量，下一格移到同如果需求量超过供应量，下一格移到同一列相邻的格子。一列相邻的格子。 c c如果需求量等于供应量，下一格是对角如果需求量等于供应量，下一格是对角线上相邻的格子线上相邻的格子。 d d回到第二步。回到第二步。 根据左上角法求出运输初始方案后，为了进根据左上角法求出运输初始方案后，为了进一步算出最优方案，仍需要运用霍撒

42、克法一步算出最优方案，仍需要运用霍撒克法则进行优化则进行优化单位单位 销地销地 运价运价 产地产地产量产量4124111621039108511522销量销量8141214484321 BBBB321AAA练习 某部门有3个生产同类产品的工厂（产地）,生产的产品由4个销售点（销地）出售，各工厂的生产量、个销售点的销售量（假定单位均为t)以及各工厂到个销售点的单位云价（元/t)示于下表，试研究如何调运才能使总的运费最小？ (1) 最小元素法 (2)西北角法 2 2 最优方案的判别最优方案的判别n对初始基可行解的最优性检验有对初始基可行解的最优性检验有闭合回路法闭合回路法和和位势法位势法两种基本方

43、法。两种基本方法。n闭合回路法具体、直接，并为方案调整指明闭合回路法具体、直接，并为方案调整指明了方向；了方向；n而位势法具有批处理的功能，提高了计算效而位势法具有批处理的功能，提高了计算效率。率。|所谓闭合回路法，就是对于代表非基变量的所谓闭合回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整空格（其调运量为零），把它的调运量调整为为1 1，由于产销平衡的要求，由于产销平衡的要求, ,我们必须对这个我们必须对这个空格的闭回路的顶点的调运量加上或减少空格的闭回路的顶点的调运量加上或减少1 1。最后我们计算出由这些变化给整个运输方案最后我们计算出由这些变化给整个运输方案的总运输

44、费带来的变化。的总运输费带来的变化。如果所有代表非基如果所有代表非基变量的空格的检验数也即非基变量的检验数变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续都大于等于零，则已求得最优解，否则继续迭代找出最优解。迭代找出最优解。( (1 1) ). .闭合回路法闭合回路法 ijij 0 表示运费增加。表示运费增加。l所谓所谓闭合回路闭合回路是是在已给出的调运方案的在已给出的调运方案的运输表上从一个代表非基变量的空格出运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，发，沿水平或垂直方向前进，只有遇到只有遇到代表基变量的填入数字的格才能向左或代表基变量的填入数字

45、的格才能向左或右转右转9090度（当然也可以不改变方向）继度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做的那个空格，由此形成的封闭折线叫做闭合回路闭合回路。一个空格存在唯一的闭回路一个空格存在唯一的闭回路。例一、某运输资料如下表所示：例一、某运输资料如下表所示：单位单位 销地销地 运价运价 产地产地产量产量311310719284741059销量销量36564321 BBBB321AAAB1B2B3B4产量产量A13113107A219284A3741059销量销量3656销地销地加工厂加工厂314633B1B

46、2B3B4A143A231A363销地销地加工厂加工厂B1B2B3B4产量产量A17A24A39销量销量3656313463（1）（1）（1）（1） 计算如下：空格处（计算如下：空格处（ A1 B1 ） (13) (1)3 (12) (1)1 1 此数即为该空格处的检验数。此数即为该空格处的检验数。1B1B2B3B4产量产量A17A24A39销量销量365631363124B1B2B3B4产量产量A17A24A39销量销量36563136312-14B1B2B3B4产量产量A17A24A39销量销量365631363121-14B1B2B3B4产量产量A17A24A39销量销量36563136

47、3121-1124B1B2B3B4产量产量A17A24A39销量销量365631363121-112104 检验数中有负数，说明原方案不是最优解。检验数中有负数，说明原方案不是最优解。B1B2B3B4产量产量A17A24A39销量销量365600000121-112100l使用位势法求出检验数，若检验数都不使用位势法求出检验数，若检验数都不为负数，则原方案为最优解，若有负检为负数，则原方案为最优解，若有负检验数存在，则负检验数所在空格需进行验数存在，则负检验数所在空格需进行调整。调整。l只有没有运量的空格处需要计算检验数。只有没有运量的空格处需要计算检验数。l检验数的计算方法如下：检验数的计算

48、方法如下：l设有运量的格子数最多的行或列的位势设有运量的格子数最多的行或列的位势0l有运量格子的运价行位势有运量格子的运价行位势+列位势列位势l空格的检验数运价空格的检验数运价-（行位势（行位势+列位势）列位势） 接上例：接上例：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表成本表B1B2B3B4A1293100A218291A33425529310 u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令：令： u10u10 v12u2 1 v2 9u3 5 v3 3 v4 10 (ui+vj) 按按ij=

49、cij(ui+vj) 计算检验数，并以计算检验数，并以ij0 检验，检验，或用或用(ui+vj) cij 0 检验。检验。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A334-25(ui+vj)B1B2B3B4A11200A20101A3100120表中还有负数，表中还有负数，说明还未得到最说明还未得到最优解，应继续调优解，应继续调整。整。ijABCDE发运量发运量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800销地销地加工厂加工厂3001005005

50、050250250300l【练习】下面是用最小元素法的得出的运输方案，【练习】下面是用最小元素法的得出的运输方案，试用位势法判断是否最优。试用位势法判断是否最优。 ABCDE行位势行位势甲甲32 3 53乙乙331 34丙丙7842 2 丁丁5 4 77 8列位势列位势销地销地加工厂加工厂0547-25-4-5700-2230179421l从负检验数所在格子出发找一条闭合回路，从负检验数所在格子出发找一条闭合回路，用水平或垂直线向前划，每碰到数字格可以用水平或垂直线向前划，每碰到数字格可以转转90度，然后继续前进，直到回到起始空格度，然后继续前进，直到回到起始空格为止。为止。l并从出发格开始依