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

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