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

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

2、表上作业法的步骤1、确定初始根本可行解；、确定初始根本可行解；2、求检验数，判别初始解能否最优解；、求检验数，判别初始解能否最优解；3、假设检验数全非负，那么初始解即最优解，否、假设检验数全非负，那么初始解即最优解，否那么初始解不是最优解，要进展调整，得到新那么初始解不是最优解，要进展调整，得到新的可行解；的可行解；4、反复、反复2、3两步，经有限次调整，得到最优解。两步，经有限次调整，得到最优解。 第一节第一节 表上作业法表上作业法三、确定初始根本可行解三、确定初始根本可行解1、西北角法、西北角法2、最小元素法、最小元素法3、伏格尔法、伏格尔法vogel最小元素法最小元素法n方法：列出供需平

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

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

5、300600500600伏格尔法伏格尔法vogeln1、计算出各行和各列的最小运费和次小运费、计算出各行和各列的最小运费和次小运费的差额；的差额；n2、从行和列差额中选出最、从行和列差额中选出最 选：大或小选：大或小者，选择它所在行或列中的最小元素，满足者，选择它所在行或列中的最小元素，满足需求；需求；n3、对未划去的再反复前两步，直到解出初始、对未划去的再反复前两步，直到解出初始方案为止。方案为止。大伏格尔法伏格尔法B1B2B3B4供应量供应量（t）A1500200700A2300100400A3600300900需求量需求量（t）300600500600第一节第一节 表上作业法表上作业法四

6、、求检验数四、求检验数1、闭回路：以调运方案表上的一个空格出发，存在、闭回路：以调运方案表上的一个空格出发，存在一条且仅一条以该空格用一条且仅一条以该空格用Xij表示为起点，以表示为起点，以其他填有数字的点为其他顶点的闭合回路，称为其他填有数字的点为其他顶点的闭合回路，称为闭回路。它具有以下性质：闭回路。它具有以下性质：每个顶点都是转角点；每个顶点都是转角点；闭合回路是一条封锁折线，每一条边都是程度或垂闭合回路是一条封锁折线，每一条边都是程度或垂直的；直的；每一行列假设有闭合回路的顶点，那么必有两每一行列假设有闭合回路的顶点，那么必有两个。个。以上例最小元素法所得初始方案为例，找闭回路。以上例

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

8、检验数大于零，那么会使运费添加。以上例最小元素法所得初始方案为例，求检验数。以上例最小元素法所得初始方案为例，求检验数。B1B2B3B4供应量供应量（t）A1400300700A2300100400A3600300900需求量需求量（t）300600500600第一节第一节 表上作业法表上作业法四、求检验数四、求检验数3、位势法求检验数、位势法求检验数设设Cij表示变量表示变量Xij相应的运价，将初始调运方案中相应的运价，将初始调运方案中填有数值方格的填有数值方格的Cij分解成两部分：分解成两部分：Cij=Ui+Vj。其中，其中，Ui和和Vj分别称为该方格对应于分别称为该方格对应于i行和行和j

9、列的位列的位势量。势量。恣意给定一个未知位势量，计算出一切的恣意给定一个未知位势量，计算出一切的Ui和和Vj，那么空格处位势为对应的那么空格处位势为对应的Ui和和Vj之和，那么空格处之和，那么空格处检验数为该处运价与位势之差，即检验数为该处运价与位势之差，即CijUiVj。第一节第一节 表上作业法表上作业法五、初始方案的调整五、初始方案的调整1、闭回路法调整、闭回路法调整在检验数为负的空格，找到它的闭回路，从空格在检验数为负的空格，找到它的闭回路，从空格出发，奇数次转角点即偶数顶点的最小调出发，奇数次转角点即偶数顶点的最小调运量为调整量。空格加上调整量，其他格相应运量为调整量。空格加上调整量，

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

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

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

13、输、对流运输2、迂回运输、迂回运输交通图成圈时，由于表示调运方向的箭头要按调交通图成圈时，由于表示调运方向的箭头要按调运方向，画在交通线的右边，因此，在流向图运方向，画在交通线的右边，因此，在流向图中有些流向就在圈内，称为内圈流向，有些流中有些流向就在圈内，称为内圈流向，有些流向就在圈外，称为外圈流向。向就在圈外，称为外圈流向。假设流向图中，内圈流向的总长或外圈流向的总假设流向图中，内圈流向的总长或外圈流向的总长超越整个圈长的一半，就称为迂回运输。长超越整个圈长的一半，就称为迂回运输。n迂回运输的调整：迂回运输的调整：n假设内流长超越圈长的一半，那么在内圈各流假设内流长超越圈长的一半，那么在内

14、圈各流量中减去内圈的最小流量，在外圈各流量中添量中减去内圈的最小流量，在外圈各流量中添加内圈的最小流量，同时在没有流量的线段上加内圈的最小流量，同时在没有流量的线段上新添外圈该最小流量。新添外圈该最小流量。n反之同理。反之同理。第二节第二节 图上作业法图上作业法三、图上作业法的步骤三、图上作业法的步骤1、交通图不含圈、交通图不含圈不出现对流即是最优方案。不出现对流即是最优方案。方法：作一个没有对流的流向图，即由各端点开方法：作一个没有对流的流向图，即由各端点开场，由外向里，逐渐进展各收发点之间的收发场，由外向里，逐渐进展各收发点之间的收发平衡。平衡。例例n有某物资有某物资17万吨，由万吨，由A

15、1，A2，A3，A4发出，发出，发量分别为发量分别为5，2，3，7单位：万吨，运单位：万吨，运往往B1，B2，B3，B4，收量分别为，收量分别为8，1，3，5，收发量是平衡的，它的交通道路如下图，问收发量是平衡的，它的交通道路如下图，问应如何调运，才干使运输吨应如何调运，才干使运输吨千米最小。千米最小。52378135A1A2B1A3B2B3A4B4第二节第二节 图上作业法图上作业法2、交通图含圈、交通图含圈第一步：第一步：“去线破圈，作一个没有对流的流向图，去线破圈，作一个没有对流的流向图，构成初始方案。构成初始方案。第二步：检查初始方案能否最优即有无迂回。第二步：检查初始方案能否最优即有无

16、迂回。第三步：如有迂回，假设内流长超越圈长的一半，第三步：如有迂回，假设内流长超越圈长的一半，那么在内圈各流量中减去内圈的最小流量，在那么在内圈各流量中减去内圈的最小流量，在外圈各流量中添加内圈的最小流量，同时在没外圈各流量中添加内圈的最小流量，同时在没有流量的线段上新添外圈该最小流量。有流量的线段上新添外圈该最小流量。 。第四步：反复上述两步，直至得出最优方案。第四步：反复上述两步，直至得出最优方案。例：交通图含圈的图上作业法例：交通图含圈的图上作业法ABE-20CDIHGF(45)(23)(25)(36)(23)(13)(127)(29)+20-30+60-30-50+20+100-70(

17、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 外圈长大于圆圈周长外圈长大于圆圈周长/2ABE-20CDIHGF(45)(23)(25)(36)(23)(13

18、)(127)(29)+20-30+60-30-50+20+100-70(18)n3、调整、调整n 选取外圈流向线中最小流量选取外圈流向线中最小流量A-I的的“20，所，所以应在外圈的各段流向线上均减去以应在外圈的各段流向线上均减去“20，同时在内，同时在内圈的各段流向线及原来没有流向线的圈的各段流向线及原来没有流向线的AB段分别加上段分别加上“20，这样就构成了一个新的调拨方案。，这样就构成了一个新的调拨方案。ABE-20CDIHGF(45)(23)(25)(36)(23)(13)(127)(29)+20-30+60-30-50+20+100-70(18)ABE-20CDIHGF(45)(23

19、)(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，而且知，而且知各配送点和客户点的地理位置及它们之间的道路通阻情各配送点和客户点的地理位置及它们之间的道路通阻情况，可据此制出相应的交通图，如图况，可据此制出相应的交通图，如图11-211-2所示。所示。第三节第三节 最短道路问题最短道路问题n例：选择从例：选择从A点到点到E点的

20、最短道路。点的最短道路。AB1B2B3C1C2C3D1D2E36477456534236534方法：动态规划的逆序递推法方法：动态规划的逆序递推法K=1K=2K=3K=4n例：某家运输公司签署了一项运输合同，要把例：某家运输公司签署了一项运输合同，要把A市的一批货物运到市的一批货物运到B市。该公司根据可选择的市。该公司根据可选择的行车道路的地图绘制了公路网络如以下图，如行车道路的地图绘制了公路网络如以下图，如何选择运输道路，才干使总路程最短？何选择运输道路，才干使总路程最短？12436579810100150175300275200175275200300200400250125100150A

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

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

23、才干。汽车为单位的该行车道的流量才干。计算方法：计算方法：1、恣意选择一条从起点、恣意选择一条从起点1到终点到终点6的道路，首先的道路，首先找出这条道路上流量才干最小的支线，即为找出这条道路上流量才干最小的支线，即为该道路的最大流量。把它记在每条支线的终该道路的最大流量。把它记在每条支线的终点并在右下角标注，如：点并在右下角标注，如：21 。其次把这。其次把这条道路上的每条支线的流量才干减去该数，条道路上的每条支线的流量才干减去该数，差数表示该支线剩余的流量才干。将其写在差数表示该支线剩余的流量才干。将其写在原来的流量才干的旁边，并把原流量划掉。原来的流量才干的旁边，并把原流量划掉。2、重新选择，反复上述操作。直至没有可行道、重新选择，反复上述操作。直至没有可行道路为止。路为止。思索题n知运输问题的产销平衡