物流运输管理

第十一章 管理数学方法在运输组织中的应用 第一节 表上作业法 第二节 图上作业法 第三节 最短路线问题

第一节 表上作业法 一、数学模型

例1：给出一个物资调运问题，如下表所示，试用线性规划法求解。 运价 销地 产地 B1 B2 B3 B4 产量（t） A1 5 3 10 4 90 A2 1 6 9 40 A3 20 7 70 销量（t） 30 50 80 60 60

第一节 表上作业法 二、表上作业法的步骤 1、确定初始基本可行解； 2、求检验数，判断初始解是否最优解； 第一节 表上作业法 二、表上作业法的步骤 1、确定初始基本可行解； 2、求检验数，判断初始解是否最优解； 3、若检验数全非负，则初始解即最优解，否则初始解不是最优解，要进行调整，得到新的可行解； 4、重复2、3两步，经有限次调整，得到最优解。

第一节 表上作业法 三、确定初始基本可行解 1、西北角法 2、最小元素法 3、伏格尔法（vogel）

最小元素法 方法：列出供需平衡表和运价表。按运价表依次挑选运费小的供需点尽量优先安排供应。（安排供应后划去运价表中不起作用的运价并标注，再在剩余未划去的运价中选取最小的数值安排供应，以此类推。）

例2 某公司下属三个储存某种物资的料库，供应四个工地的需要。三个料库的供应量和四个工地的需求量以及各料库到诸工地调运单位物资的运价（元/吨）由表1给出，试求运输费用最少的合理调运方案。

表1：某公司物资供应状况表 B1 B2 B3 B4 供应量（t） A1 3 11 10 700 A2 1 9 2 8 400 A3 7 4 运价 工地 料库 B1 B2 B3 B4 供应量（t） A1 3 11 10 700 A2 1 9 2 8 400 A3 7 4 5 900 需求量（t） 300 600 500

西北角法 B1 B2 B3 B4 供应量（t） A1 300 400 700 A2 200 A3 600 900 需求量（t） 500

最小元素法 B1 B2 B3 B4 供应量（t） A1 400 300 700 A2 100 A3 600 900 需求量（t） 500

伏格尔法（vogel） 1、计算出各行和各列的最小运费和次小运费的差额； 2、从行和列差额中选出最 （选：大或小）者，选择它所在行或列中的最小元素，满足需要； 3、对未划去的再重复前两步，直到解出初始方案为止。 大

伏格尔法 B1 B2 B3 B4 供应量（t） A1 500 200 700 A2 300 100 400 A3 600 900 需求量（t）

第一节 表上作业法 四、求检验数 1、闭回路：以调运方案表上的一个空格出发，存在一条且仅一条以该空格（用Xij表示）为起点，以其他填有数字的点为其他顶点的闭合回路，称为闭回路。它具有下列性质： 每个顶点都是转角点； 闭合回路是一条封闭折线，每一条边都是水平或垂直的； 每一行（列）若有闭合回路的顶点，则必有两个。

以上例最小元素法所得初始方案为例，找闭回路。 B1 B2 B3 B4 供应量（t） A1 400 300 700 A2 100 A3 600 900 需求量（t） 500

第一节 表上作业法 四、求检验数 2、闭回路法求检验数 检验数：每条闭回路上调整单位运量而使运输费用发生变化的增减值，称为检验数。 第一节 表上作业法 四、求检验数 2、闭回路法求检验数 检验数：每条闭回路上调整单位运量而使运输费用发生变化的增减值，称为检验数。 如果检验数小于零，表示在该空格的闭回路上调整运量使运费减少； 相反，如果检验数大于零，则会使运费增加。

以上例最小元素法所得初始方案为例，求检验数。 B1 B2 B3 B4 供应量（t） A1 400 300 700 A2 100 A3 600 900 需求量（t） 500

第一节 表上作业法 四、求检验数 3、位势法求检验数 第一节 表上作业法 四、求检验数 3、位势法求检验数 设Cij表示变量Xij相应的运价，将初始调运方案中填有数值方格的Cij分解成两部分：Cij=Ui+Vj。 其中，Ui和Vj分别称为该方格对应于i行和j列的位势量。 任意给定一个未知位势量，计算出所有的Ui和Vj，那么空格处位势为对应的Ui和Vj之和，则空格处检验数为该处运价与位势之差，即Cij－Ui－Vj。

第一节 表上作业法 五、初始方案的调整 1、闭回路法调整 第一节 表上作业法 五、初始方案的调整 1、闭回路法调整 在检验数为负的空格，找到它的闭回路，从空格出发，奇数次转角点（即偶数顶点）的最小调运量为调整量。空格加上调整量，其他格相应调整。

例3 某地区有3个煤矿，所产煤炭全部销往两座火力发电厂。各矿产量、电厂需求量及单位运价表如表所示，问如何安排运输可使总运费最省？

运价 电厂 煤矿 B1 B2 煤产量 A1 3 5 5000 A2 4 2 11000 A3 6 9 8000 需求量 10000 14000

例4 用表上作业法求下表给出的运输问题的最优解，并求最低运费为多少。 甲 乙 丙 丁 产量（t） 1 10 6 7 12 400 2 16 运价 销地 产地 甲 乙 丙 丁 产量（t） 1 10 6 7 12 400 2 16 5 9 900 3 4 销量（t） 500 200 600

供需不平衡的物资调运问题 1、供应量大于需求量 2、需求量大于供应量 处理：引入一个虚设的需求点，令其的需求量等于实际问题中供应量与需求量之差。实际中，相当于在某个供应点的仓库里将多余部分储存起来了。因此，可视其相应运价为 。 零 处理：引入一个虚设的供应点，令其的供应量等于实际问题中需求量与供应量之差。实际中，相当于在某个需求点内设立一个仓库，将不足部分另找出路供应好，预先储存起来了。相应运价为零。

例 某建筑公司有三个储砂仓，供应四个拌合场的混凝土搅拌机所需用砂。各拌合场估计需砂量合储砂仓的供应能力以及由第i砂仓运往第j拌合场的单位运价Cij（元/吨）见表。请为该公司找出一个运费最小的供砂调运方案。

Cij 拌合场 砂仓 B1 B2 B3 B4 ai（t） A1 0.12 0.10 0.08 0.11 5000 A2 0.09 0.13 10000 A3 0.14 0.03 12000 bj（t） 4000 7000 8000

第二节 图上作业法 利用表上作业法，可以确定物资的调运方向，即物资调运的发点和收点，但实施运输方案时，还会遇到运输路线的选择问题。 第二节 图上作业法 利用表上作业法，可以确定物资的调运方向，即物资调运的发点和收点，但实施运输方案时，还会遇到运输路线的选择问题。 在物资调运中，把某项物资从各发点调到各收点，调运方案很多，我们要找出使用运力最小的方案，即消灭对流和迂回两种不合理的运输。

第二节 图上作业法 一、交通图 1、交通图的符号： 第二节 图上作业法 一、交通图 1、交通图的符号： 发点用“ ”表示，并将发货量记在里面，收点用“ ”表示，并将收货量记在里面。两点间交通线的长度记在交通线旁边。 2、调运物资的流向图： 物资调运的方向（流向）用“ ”表示，并把“ ” 按调运方向画在交通线的右边，把调运物资的数量记在“ ”的右边并加上括号。

第二节 图上作业法 二、图上作业法 1、对流运输 2、迂回运输 第二节 图上作业法 二、图上作业法 1、对流运输 2、迂回运输 交通图成圈时，由于表示调运方向的箭头要按调运方向，画在交通线的右边，因此，在流向图中有些流向就在圈内，称为内圈流向，有些流向就在圈外，称为外圈流向。 如果流向图中，内圈流向的总长或外圈流向的总长超过整个圈长的一半，就称为迂回运输。

迂回运输的调整： 如果内流长超过圈长的一半，则在内圈各流量中减去内圈的最小流量，在外圈各流量中增加内圈的最小流量，同时在没有流量的线段上新添外圈该最小流量。 反之同理。

第二节 图上作业法 三、图上作业法的步骤 1、交通图不含圈 不出现对流即是最优方案。 第二节 图上作业法 三、图上作业法的步骤 1、交通图不含圈 不出现对流即是最优方案。 方法：作一个没有对流的流向图，即由各端点开始，由外向里，逐步进行各收发点之间的收发平衡。

例 有某物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7（单位：万吨），运往B1，B2，B3，B4，收量分别为8，1，3，5，收发量是平衡的，它的交通路线如图所示，问应如何调运，才能使运输吨·千米最小。

5 2 3 7 8 1 A1 A2 B1 A3 B2 B3 A4 B4

第二节 图上作业法 2、交通图含圈 第一步：“去线破圈”（一般去掉长度最长的交通线），作一个没有对流的流向图，形成初始方案。 第二节 图上作业法 2、交通图含圈 第一步：“去线破圈”（一般去掉长度最长的交通线），作一个没有对流的流向图，形成初始方案。 第二步：检查初始方案是否最优（即有无迂回）。 第三步：若无迂回则为最优方案；如有迂回，进行调整。 第四步：重复上述两步，直至得出最优方案。

例：助理物流师P84 3 1 2 A1 A2 B1 A3 B2 B3 B4 7 5 4

第三节 最短路线问题 例：选择从A点到E点的最短路线。 方法：动态规划的逆序递推法 A B1 B2 B3 C1 C2 C3 D1 D2 E 第三节 最短路线问题 例：选择从A点到E点的最短路线。 A B1 B2 B3 C1 C2 C3 D1 D2 E 3 6 4 7 5 2 K=1 K=2 K=3 K=4 方法：动态规划的逆序递推法

例：某家运输公司签订了一项运输合同，要把A市的一批货物运到B市。该公司根据可选择的行车路线的地图绘制了公路网络如下图，如何选择运输路线，才能使总路程最短？ 1 2 4 3 6 5 7 9 8 10 100 150 175 300 275 200 400 250 125 A市 B市

最大流问题 当我们要把货物运输到指定的地点时，有时会希望找到一条交通量最大的路线，以使货物能在最短时间内到达。 这就要在有一个起点和一个终点的网络中，找出在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量问题。

例题： 美国北卡罗来纳州杜哈姆市周围从北到南的交通，平时是利用85号公路通行的。后来，有两个星期因为85号公路要进行路面维修，车辆不能行驶，因而北卡罗来纳州公路委员会的工程技术人员需要查明，穿过杜哈姆市区的几条路线，是不是有把握让每小时6000辆汽车穿过，这些汽车在正常情况下，是利用85号公路南驶的。 下图标出了穿过该市从北往南的几条路线。结点旁边的数字表明以每小时千辆汽车为单位的该行车道的流量能力。

计算方法： 1、任意选择一条从起点1到终点6的路线，首先找出这条路线上流量能力最小的支线，即为该路线的最大流量。把它记在每条支线的终点并在右下角标注，如：2（1） 。其次把这条路线上的每条支线的流量能力减去该数，差数表示该支线剩余的流量能力。将其写在原来的流量能力的旁边，并把原流量划掉。 2、重新选择，重复上述操作。直至没有可行路线为止。

思考题 已知运输问题的产销平衡表、单位运价表，求最优调运方案。并求（1）从A2到B2的单位运价C22在什么范围变化时，上述最优调运方案不变？（2）A2到B4的单位运价C24变为何值时，有多解，至少再写出其它一个解。 Cij 销地 产地 B1 B2 B3 B4 产量 A1 10 1 20 11 150 A2 12 7 9 250 A3 2 14 16 18 50 销量 100

可以作为初始方案的调运方案，其填有数字的方格数目应是供应点个数加需求点个数之和再减一，即（m+n-1）。 在同时划去的那行或那列的任一空格处，添加一个“0”，并将它和其他填有数字的格子同等看待，而不能视为空格。

货郎担问题 有一个串村走户卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄，问应如何选择行走路线，能使总的行程最短？

例：求解四个城市旅行推销员问题，其距离矩阵如表。当推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按怎样的路线走，能使总的行程距离最短？最短距离为多少？ 距离 i j 1 2 3 4 8 5 6 7 9