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

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,物流运输管理,第八章 管理数学方法在运输组织中的应用,第一节 表上作业法,第二节 图上作业法,第三节 最短路线问题,第一节 表上作业法,一、数学模型,例1：给出一个物资调运问题，如下表所示，试用线性规划法求解。,运价,销地,产地,B1,B2,B3,B4,产量（t）,A1,5,3,10,4,90,A2,1,6,9,6,40,A3,20,10,5,7,70,销量（t）,30,50,80,40,60,60,第一节 表上作业法,二、表上作业法的步骤,1、确定初始基本可行解；,2、求检验数，判断初始解是否最优解；,3、若检验数全非负，则初始解即最优解，否则初始解不是最优解，要进行调整，得到新的可行解；,4、重复2、3两步，经有限次调整，得到最优解。,第一节 表上作业法,三、确定初始基本可行解,1、西北角法,2、最小元素法,3、伏格尔法（vogel）,最小元素法,方法：列出供需平衡表和运价表。按运价表依次挑选运费小的供需点尽量优先安排供应。（安排供应后划去运价表中不起作用的运价并标注，再在剩余未划去的运价中选取最小的数值安排供应，以此类推。）,例2,某公司下属三个储存某种物资的料库，供应四个工地的需要。三个料库的供应量和四个工地的需求量以及各料库到诸工地调运单位物资的运价（元/吨）由表1给出，试求运输费用最少的合理调运方案。,表1：某公司物资供应状况表,运价,工地,料库,B1,B2,B3,B4,供应量（t）,A1,3,11,3,10,700,A2,1,9,2,8,400,A3,7,4,10,5,900,需求量（t）,300,600,500,600,西北角法,B1,B2,B3,B4,供应量（t）,A1,300,400,700,A2,200,200,400,A3,300,600,900,需求量（t）,300,600,500,600,最小元素法,B1,B2,B3,B4,供应量（t）,A1,400,300,700,A2,300,100,400,A3,600,300,900,需求量（t）,300,600,500,600,伏格尔法（vogel）,1、计算出各行和各列的最小运费和次小运费的差额；,2、从行和列差额中选出最 （选：大或小）者，选择它所在行或列中的最小元素，满足需要；,3、对未划去的再重复前两步，直到解出初始方案为止。,大,伏格尔法,B1,B2,B3,B4,供应量（t）,A1,500,200,700,A2,300,100,400,A3,600,300,900,需求量（t）,300,600,500,600,第一节 表上作业法,四、求检验数,1、,闭回路,：以调运方案表上的一个空格出发，存在一条且仅一条以该空格（用Xij表示）为起点，以其他填有数字的点为其他顶点的闭合回路，称为闭回路。它具有下列性质：,每个顶点都是转角点；,闭合回路是一条封闭折线，每一条边都是水平或垂直的；,每一行（列）若有闭合回路的顶点，则必有两个。,以上例最小元素法所得初始方案为例，找闭回路。,B1,B2,B3,B4,供应量（t）,A1,400,300,700,A2,300,100,400,A3,600,300,900,需求量（t）,300,600,500,600,第一节 表上作业法,四、求检验数,2、闭回路法,求检验数,检验数：,每条闭回路上调整单位运量而使运输费用发生变化的增减值，称为检验数。,如果检验数小于零，表示在该空格的闭回路上调整运量使运费减少；,相反，如果检验数大于零，则会使运费增加。,以上例最小元素法所得初始方案为例，求检验数。,B1,B2,B3,B4,供应量（t）,A1,400,300,700,A2,300,100,400,A3,600,300,900,需求量（t）,300,600,500,600,第一节 表上作业法,四、求检验数,3、,位势法,求检验数,设Cij表示变量Xij相应的运价，将初始调运方案中填有数值方格的Cij分解成两部分：Cij=Ui+Vj。,其中，Ui和Vj分别称为该方格对应于i行和j列的位势量。,任意给定一个未知位势量，计算出所有的Ui和Vj，那么空格处位势为对应的Ui和Vj之和，则空格处检验数为该处运价与位势之差，即CijUiVj。,第一节 表上作业法,五、初始方案的调整,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,10,5,9,900,3,5,4,10,10,400,销量（t）,500,200,400,600,第二节 图上作业法,利用表上作业法，可以确定物资的调运方向，即物资调运的发点和收点，但实施运输方案时，还会遇到,运输路线的选择问题,。,在物资调运中，把某项物资从各发点调到各收点，调运方案很多，我们要找出使用运力最小的方案，即,消灭对流和迂回,两种不合理的运输。,第二节 图上作业法,一、交通图,1、交通图的符号：,发点用“”表示，并将发货量记在里面，收点用“”表示，并将收货量记在里面。两点间交通线的长度记在交通线旁边。,2、调运物资的流向图：,物资调运的方向（流向）用“”表示，并把“”按调运方向画在交通线的,右边,，把调运物资的数量记在“”的右边并,加上括号,。,第二节 图上作业法,二、图上作业法,1、对流运输,2、迂回运输,交通图成圈时，由于表示调运方向的箭头要按调运方向，画在交通线的右边，因此，在流向图中有些流向就在圈内，称为内圈流向，有些流向就在圈外，称为外圈流向。,如果流向图中，内圈流向的总长或外圈流向的总长超过整个圈长的一半，就称为迂回运输。,迂回运输的调整：,如果,内流长,超过圈长的一半，则在,内圈,各流量中减去,内圈的最小,流量，在,外圈,各流量中增加,内圈的最小,流量，同时在没有流量的线段上新添,外圈,该最小流量。,反之同理。,第二节 图上作业法,三、图上作业法的步骤,1、交通图不含圈,不出现对流即是最优方案。,方法：作一个没有对流的流向图，即由各端点开始，,由外向里,，逐步进行各收发点之间的收发平衡。,例,有某物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7（单位：万吨），运往B1，B2，B3，B4，收量分别为8，1，3，5，收发量是平衡的，它的交通路线如图所示，问应如何调运，才能使运输吨千米最小。,5,2,3,7,8,1,3,5,A1,A2,B1,A3,B2,B3,A4,B4,第二节 图上作业法,2、交通图含圈,第一步：“去线破圈”，作一个没有对流的流向图，形成初始方案。,第二步：检查初始方案是否最优（即有无迂回）。,第三步：如有迂回，如果,内流长,超过圈长的一半，则在,内圈,各流量中减去,内圈的最小,流量，在,外圈,各流量中增加,内圈的最小,流量，同时在没有流量的线段上新添,外圈,该最小流量。,第四步：重复上述两步，直至得出最优方案。,例：交通图含圈的图上作业法,A,B,E,-20,C,D,I,H,G,F,(45),(23),(25),(36),(23),(13),(127),(29),+20,-30,+60,-30,-50,+20,+100,-70,(18),交通图含圈的图上作业法,1、去线破圈 先去掉AB段，形成一个初始的调运方案,A,B,E,-20,C,D,I,H,G,F,(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 外圈长大于圆圈周长/2,A,B,E,-20,C,D,I,H,G,F,(45),(23),(25),(36),(23),(13),(127),(29),+20,-30,+60,-30,-50,+20,+100,-70,(18),3、调整,选取外圈流向线中最小流量A-I的“20”，所以应在外圈的各段流向线上均减去“20”，同时在内圈的各段流向线及原来没有流向线的AB段分别加上“20”，这样就形成了一个新的调拨方案。,A,B,E,-20,C,D,I,H,G,F,(45),(23),(25),(36),(23),(13),(127),(29),+20,-30,+60,-30,-50,+20,+100,-70,(18),A,B,E,-20,C,D,I,H,G,F,(45),(23),(25),(36),(23),(13),(127),(29),+20,-30,+60,-30,-50,+20,+100,-70,(18),计算：例：设有A1、A2、A3三个配送点分别有化肥40t、30t、30t，需送往四个客户点B1、B2、B3、B4，而且已知各配送点和客户点的地理位置及它们之间的道路通阻情况，可据此制出相应的交通图，如图11-2所示。,第三节 最短路线问题,例：选择从A点到E点的最短路线。,A,B1,B2,B3,C1,C2,C3,D1,D2,E,3,6,4,7,7,4,5,6,5,3,4,2,3,6,5,3,4,方法：动态规划的逆序递推法,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,175,275,200,300,200,400,250,125,100,150,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,20,250,A3,2,14,16,18,50,销量,50,150,150,100,可以作为初始方案的调运方案，其填有数字的方格数目应是供应点个数加需求点个数之和再减一，即（m+n-1）。,在同时划去的那行