管理数学方法在运输组织中的应用

1、 物流运输管理物流运输管理第八章第八章 管理数学方法在运输组织管理数学方法在运输组织中的应用中的应用n第一节第一节 表上作业法表上作业法n第二节第二节 图上作业法图上作业法n第三节第三节 最短路线问题最短路线问题第一节第一节 表上作业法表上作业法n一、数学模型一、数学模型 例例1：给出一个物资调运问题，如下表所示，：给出一个物资调运问题，如下表所示，试用线性规划法求解。试用线性规划法求解。运价运价 销地销地产地产地b1b2b3b4产量产量（t）a15310490a2169640a320105770销量销量（t）305080406060第一节第一节 表上作业法表上作业法二、表上作业法的步骤二、表

2、上作业法的步骤n1、确定初始基本可行解；、确定初始基本可行解；n2、求检验数，判断初始解是否最优解；、求检验数，判断初始解是否最优解；n3、若检验数全非负，则初始解即最优解，否则、若检验数全非负，则初始解即最优解，否则初始解不是最优解，要进行调整，得到新的可初始解不是最优解，要进行调整，得到新的可行解；行解；n4、重复、重复2、3两步，经有限次调整，得到最优解。两步，经有限次调整，得到最优解。 第一节第一节 表上作业法表上作业法三、确定初始基本可行解三、确定初始基本可行解n1、西北角法、西北角法n2、最小元素法、最小元素法n3、伏格尔法（、伏格尔法（vogel）最小元素法最小元素法n方法：列出

3、供需平衡表和运价表。按运价表方法：列出供需平衡表和运价表。按运价表依次挑选运费小的供需点尽量优先安排供应。依次挑选运费小的供需点尽量优先安排供应。（安排供应后划去运价表中不起作用的运价（安排供应后划去运价表中不起作用的运价并标注，再在剩余未划去的运价中选取最小并标注，再在剩余未划去的运价中选取最小的数值安排供应，以此类推。）的数值安排供应，以此类推。）例例2n某公司下属三个储存某种物资的料库，供应某公司下属三个储存某种物资的料库，供应四个工地的需要。三个料库的供应量和四个四个工地的需要。三个料库的供应量和四个工地的需求量以及各料库到诸工地调运单位工地的需求量以及各料库到诸工地调运单位物资的运价

4、（元物资的运价（元/吨）由表吨）由表1给出，试求运输费给出，试求运输费用最少的合理调运方案。用最少的合理调运方案。表表1：某公司物资供应状况表：某公司物资供应状况表运价运价 工地工地料库料库b1b2b3b4供应量供应量（t）a1311310700a21928400a374105900需求量需求量（t）300600500600西北角法西北角法b1b2b3b4供应量供应量（t）a1300400700a2200200400a3300600900需求量需求量（t）300600500600最小元素法最小元素法b1b2b3b4供应量供应量（t）a1400300700a2300100400a36003009

5、00需求量需求量（t）300600500600伏格尔法（伏格尔法（vogel）n1、计算出各行和各列的最小运费和次小运费、计算出各行和各列的最小运费和次小运费的差额；的差额；n2、从行和列差额中选出最、从行和列差额中选出最 （选：大或小）（选：大或小）者，选择它所在行或列中的最小元素，满足者，选择它所在行或列中的最小元素，满足需要；需要；n3、对未划去的再重复前两步，直到解出初始、对未划去的再重复前两步，直到解出初始方案为止。方案为止。大伏格尔法伏格尔法b1b2b3b4供应量供应量（t）a1500200700a2300100400a3600300900需求量需求量（t）300600500600

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

7、上例最小元素法所得初始方案为例，找闭回路。以上例最小元素法所得初始方案为例，找闭回路。b1b2b3b4供应量供应量（t）a1400300700a2300100400a3600300900需求量需求量（t）300600500600第一节第一节 表上作业法表上作业法四、求检验数四、求检验数2、闭回路法、闭回路法求检验数求检验数检验数：检验数：每条闭回路上调整单位运量而使运输费每条闭回路上调整单位运量而使运输费用发生变化的增减值，称为检验数。用发生变化的增减值，称为检验数。n 如果检验数小于零，表示在该空格的闭回路上如果检验数小于零，表示在该空格的闭回路上调整运量使运费减少；调整运量使运费减少；n

8、相反，如果检验数大于零，则会使运费增加。相反，如果检验数大于零，则会使运费增加。以上例最小元素法所得初始方案为例，求检验数。以上例最小元素法所得初始方案为例，求检验数。b1b2b3b4供应量供应量（t）a1400300700a2300100400a3600300900需求量需求量（t）300600500600第一节第一节 表上作业法表上作业法四、求检验数四、求检验数3、位势法位势法求检验数求检验数设设cij表示变量表示变量xij相应的运价，将初始调运方案中相应的运价，将初始调运方案中填有数值方格的填有数值方格的cij分解成两部分：分解成两部分：cij=ui+vj。其中，其中，ui和和vj分别称

9、为该方格对应于分别称为该方格对应于i行和行和j列的位列的位势量。势量。任意给定一个未知位势量，计算出所有的任意给定一个未知位势量，计算出所有的ui和和vj，那么空格处位势为对应的那么空格处位势为对应的ui和和vj之和，则空格处检之和，则空格处检验数为该处运价与位势之差，即验数为该处运价与位势之差，即cijuivj。第一节第一节 表上作业法表上作业法五、初始方案的调整五、初始方案的调整n1、闭回路法调整、闭回路法调整n在检验数为负的空格，找到它的闭回路，从空在检验数为负的空格，找到它的闭回路，从空格出发，奇数次转角点（即偶数顶点）的最小格出发，奇数次转角点（即偶数顶点）的最小调运量为调整量。空格

10、加上调整量，其他格相调运量为调整量。空格加上调整量，其他格相应调整。应调整。例例3n某地区有某地区有3个煤矿，所产煤炭全部销往个煤矿，所产煤炭全部销往两座火力发电厂。各矿产量、电厂需求两座火力发电厂。各矿产量、电厂需求量及单位运价表如表所示，问如何安排量及单位运价表如表所示，问如何安排运输可使总运费最省？运输可使总运费最省？ 运价运价 电厂电厂煤矿煤矿b1b2煤产量煤产量a1355000a24211000a3698000需求量需求量1000014000例例4n用表上作业法求下表给出的运输问题的最优解，用表上作业法求下表给出的运输问题的最优解，并求最低运费为多少。并求最低运费为多少。运价运价 销

11、地销地产地产地甲甲乙乙丙丙丁丁产量产量（t）110671240021610599003541010400销量销量（t）500200400600第二节第二节 图上作业法图上作业法n利用表上作业法，可以确定物资的调运方向，利用表上作业法，可以确定物资的调运方向，即物资调运的发点和收点，但实施运输方案时，即物资调运的发点和收点，但实施运输方案时，还会遇到还会遇到运输路线的选择问题运输路线的选择问题。n在物资调运中，把某项物资从各发点调到各收在物资调运中，把某项物资从各发点调到各收点，调运方案很多，我们要找出使用运力最小点，调运方案很多，我们要找出使用运力最小的方案，即的方案，即消灭对流和迂回消灭对流

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

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

14、：n如果如果内流长内流长超过圈长的一半，则在超过圈长的一半，则在内圈内圈各流量各流量中减去中减去内圈的最小内圈的最小流量，在流量，在外圈外圈各流量中增加各流量中增加内圈的最小内圈的最小流量，同时在没有流量的线段上新流量，同时在没有流量的线段上新添添外圈外圈该最小流量。该最小流量。n反之同理。反之同理。第二节第二节 图上作业法图上作业法三、图上作业法的步骤三、图上作业法的步骤1、交通图不含圈、交通图不含圈n不出现对流即是最优方案。不出现对流即是最优方案。n方法：作一个没有对流的流向图，即由各端点方法：作一个没有对流的流向图，即由各端点开始，开始，由外向里由外向里，逐步进行各收发点之间的收，逐步进

15、行各收发点之间的收发平衡。发平衡。例例n有某物资有某物资17万吨，由万吨，由a1，a2，a3，a4发出，发出，发量分别为发量分别为5，2，3，7（单位：万吨），运（单位：万吨），运往往b1，b2，b3，b4，收量分别为，收量分别为8，1，3，5，收发量是平衡的，它的交通路线如图所示，收发量是平衡的，它的交通路线如图所示，问应如何调运，才能使运输吨问应如何调运，才能使运输吨千米最小。千米最小。52378135a1a2b1a3b2b3a4b4第二节第二节 图上作业法图上作业法2、交通图含圈、交通图含圈n第一步：第一步：“去线破圈去线破圈”，作一个没有对流的流，作一个没有对流的流向图，形成初始方案。

16、向图，形成初始方案。n第二步：检查初始方案是否最优（即有无迂第二步：检查初始方案是否最优（即有无迂回）。回）。n第三步：如有迂回，如果第三步：如有迂回，如果内流长内流长超过圈长的一超过圈长的一半，则在半，则在内圈内圈各流量中减去各流量中减去内圈的最小内圈的最小流量，流量，在在外圈外圈各流量中增加各流量中增加内圈的最小内圈的最小流量，同时在流量，同时在没有流量的线段上新添没有流量的线段上新添外圈外圈该最小流量。该最小流量。 。n第四步：重复上述两步，直至得出最优方案。第四步：重复上述两步，直至得出最优方案。例：交通图含圈的图上作业法例：交通图含圈的图上作业法abe-20cdihgf(45)(23

17、)(25)(36)(23)(13)(127)(29)+20-30+60-30-50+20+100-70(18)交通图含圈的图上作业法交通图含圈的图上作业法1 、去线破圈、去线破圈 先去掉先去掉ab段，形成一个初始段，形成一个初始的调运方案的调运方案abe-20cdihgf(45)(23)(25)(36)(23)(13)(127)(29)+20-30+60-30-50+20+100-70(18)交通图含圈的图上作业法交通图含圈的图上作业法2、检验、检验 圈周长圈周长/2=36+23+18+25+23+45=170/2=85 外圈长外圈长=45+25+18+23=111 内圈长内圈长=23 外圈长

18、大于圆圈周长外圈长大于圆圈周长/2abe-20cdihgf(45)(23)(25)(36)(23)(13)(127)(29)+20-30+60-30-50+20+100-70(18)n3、调整、调整 选取外圈流向线中最小流量选取外圈流向线中最小流量a-i的的“20”，所以应，所以应在外圈的各段流向线上均减去在外圈的各段流向线上均减去“20”，同时在内圈的，同时在内圈的各段流向线及原来没有流向线的各段流向线及原来没有流向线的ab段分别加上段分别加上“20”，这样就形成了一个新的调拨方案。这样就形成了一个新的调拨方案。abe-20cdihgf(45)(23)(25)(36)(23)(13)(127

19、)(29)+20-30+60-30-50+20+100-70(18)abe-20cdihgf(45)(23)(25)(36)(23)(13)(127)(29)+20-30+60-30-50+20+100-70(18)计算：例：设有计算：例：设有a1a1、a2a2、a3a3三个配送点分别有化肥三个配送点分别有化肥40t40t、30t30t、30t30t，需送往四个客户点，需送往四个客户点b1b1、b2b2、b3b3、b4b4，而且已，而且已知各配送点和客户点的地理位置及它们之间的道路通阻知各配送点和客户点的地理位置及它们之间的道路通阻情况，可据此制出相应的交通图，如图情况，可据此制出相应的交通图

20、，如图11-211-2所示。所示。第三节第三节 最短路线问题最短路线问题n例：选择从例：选择从a点到点到e点的最短路线。点的最短路线。ab1b2b3c1c2c3d1d2e36477456534236534方法：动态规划的逆序递推法方法：动态规划的逆序递推法k=1k=2k=3k=4n例：某家运输公司签订了一项运输合同，要把例：某家运输公司签订了一项运输合同，要把a市的一批货物运到市的一批货物运到b市。该公司根据可选择的市。该公司根据可选择的行车路线的地图绘制了公路网络如下图，如何行车路线的地图绘制了公路网络如下图，如何选择运输路线，才能使总路程最短？选择运输路线，才能使总路程最短？1243657

21、9810100150175300275200175275200300200400250125100150a市市b市市最大流问题最大流问题n当我们要把货物运输到指定的地点时，有时当我们要把货物运输到指定的地点时，有时会希望找到一条会希望找到一条交通量最大交通量最大的路线，以使货的路线，以使货物能在物能在最短时间内到达最短时间内到达。n这就要在有一个起点和一个终点的网络中，这就要在有一个起点和一个终点的网络中，找出在一定时期内，能在起点进入，并通过找出在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量问题。这个网络，在终点输出的最大流量问题。例题：例题：n美国北卡罗来纳州杜哈姆市周围

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

23、北往南的几条路线。结点旁边的数字表明以每小时千辆汽车为单结点旁边的数字表明以每小时千辆汽车为单位的该行车道的流量能力。位的该行车道的流量能力。计算方法：计算方法：n1、任意选择一条从起点、任意选择一条从起点1到终点到终点6的路线，首的路线，首先找出这条路线上流量能力最小的支线，即先找出这条路线上流量能力最小的支线，即为该路线的最大流量。把它记在每条支线的为该路线的最大流量。把它记在每条支线的终点并在右下角标注，如：终点并在右下角标注，如：2（1） 。其次把这。其次把这条路线上的每条支线的流量能力减去该数，条路线上的每条支线的流量能力减去该数，差数表示该支线剩余的流量能力。将其写在差数表示该支线剩余的流量能力。将其写在原来的流量能力的旁边，并把原流量划掉。原来的流量能力的旁边，并把原流量划掉。n2、重新选择，重复上述操作。直至没有可行、重新选择，重复上述操作。直至没有可行路线为止。路线为止。思考题n已知运输问题的产销平衡表、单位运