第五章 物流系统规划(一).ppt

1、1,第5章 物流系统规划,5.1 概述 5.2 物流调运规划 5.3 物流分配规划 5.4 其它应用问题,2,5.1 概述,3,一. 物流系统规划概述,物流系统规划所关注的问题是如何合理、有效地利用或配置各种资源（劳动力、材料、设备、资金），使实现预定目标所需的费用最小（或资源最少），或者所获得的收益最大。 物流系统的规划一般都可以用优化模型来表达。其基本思想是在满足一定的约束条件下，使预定的目标值达到最优。 物流系统规划的数学基础主要是运筹学理论，常用的方法包括线性规划、整数规划、动态规划等。,4,二. 物流系统规划的目标任务,提高物流系统的吞吐能力以适应产量增长的要求； 建设一个柔性的物流

2、系统，以适应产品经常变化的情况； 对生产过程中可能出现的各种意外情况或随机变化做出及时的响应，保持均衡生产； 改善劳动条件，减轻劳动强度； 对物流系统中的货物进行实时跟踪； 对物流系统的货物进行分类或选配，为随后的处理(加工或包装)提供方便条件。,5,三. 评价物流系统规划的主要指标,经济性。包括初始投资、每年的运营费用、直接或间接的经济效益、投资回收期、全员劳动生产率等； 可靠性。包括单个环节的可靠性和整个系统的可靠性技术、设备故障率和排除故障所需的时间； 可维护性。维护保养所要求的技术水平、备件的供应情况、所需储备的备件数量； 灵活性或柔性。适应产品设计更改和产量变化的能力，物流系统各环节

3、与生产节奏相匹配的能力，调整物流路线的可能性； 可扩展性。在物流系统的服务范围和吞吐能力方面进步扩大的可能性； 安全性。包括产品的安全、人员的安全、以及正常运行和事故状态下的安全保障； 劳动强度。需要劳动力的数量、劳动者的疲劳程度； 易操作性。操作简单、不易出错，只需少量指令即可使设备和整个系统投入运行； 服务水平。对顾客的要求做出快速响应的能力； 环境保护。符合环境保护条理的要求，对周围环境的污染程度低。 敏感性。对外界条件变动的敏感程度和适应能力。,6,四. 物流系统规划中的变量,物流系统规划中的控制因素分为两类 不可控因素：设计人员无法左右的种种前提条件。 可控因素：可以由规划设计人员在

4、一定范围内选取的变量。 明确了物流系统中可控变量和不可控因素，就能知道加何去影响系统的性能，达到所追求的目标。 物流系统的规划一般是通过调整可控变量观察系统性能的变化趋势，从而选择可控变量的最佳匹配，达到系统的最佳效果。 物流系统的功能除了受可控变量的影响外，还与不可控因素有密切的关系。通常，不可控因素不是非常确定的。,7,5.2 物流系统调运规划,8,一. 问题描述,调运规划问题描述 设 某种要调运的物资，有一组供应点(产地或称发点)m个，一组需求点(销地或称收点)n个，如果每个供应点的供应量及每个需求点的需求量都已经确定，即第i个产地有ai 单位的物资发出，第j个需求点需要收进bj单位的物

5、资；并且从每个产地到每一个销地的单位运价是已知的，假定把单位物资从第i个产地调运到第j个销地去的单位运价为cij 。 调运规划问题也叫运输问题 物资调运规划的目的： 制订一个合理的调运方案； 确定m个产地与n个销地之间的供需联系和数量的最优搭配； 确定具体的运输路线，使总的运输费用最低。,9,二. 确定产销地之间的供需联系和收发量,1. 数学模型 设供应点为Ai，该供应点的供应量是ai，（i=1,2,m）； 设需求点为Bj，该需求点的需求量是bi，（j1,2,n）； cij为从第i个供应点到第j个需求点的单位运价； 由供应点Ai发往需求点Bj的物资调运量是xij单位。 假设m个供应点的总供应量

6、等于n个需求点的总需求量，（这样，调运问题满足供需平衡，称为平衡运输问题）。这时，由各供应点Ai调出的物资总量应等于它的供应量ai(i=1,2,m)；而每一个需求点Bj调入的物资总量应等于它的需求量bj(j=1,2,n)。 目标函数：,约束条件,10,二. 确定产销地之间的供需联系和收发量,2. 模型求解 用线性规划方法求解（如单纯形法）。 用表上作业法求解（针对这类问题的一种特殊解法） 3.表上作业法的主要步骤 首先依据问题列出调运物资的供需平衡表以及运价表； 其次确定一个初始的调运方案(当然不一定就是最优的方案)； 然后根据一个判定法则，判定初始方案是否为最优方案。 当判定初始方案不是最优

7、方案时，再对这个方案进行调整。 一般情况，每调整一次得到一个新的方案，而这个新方案的运费比前一个方案要少些，如此经过几次调整，就会得到最优方案。,11,工地,料库,运价,表5-1 某公司物资供应状况表,二. 确定产销地之间的供需联系和收发量,4. 表上作业法解题实例 例题1 某公司下属三个储存某种物资的仓库，供应四个工地的需要。三个仓库的供应量和四个工地的需求量以及由各仓库到各工地调运单位物资的运价(元吨)由表51给出，试求运输费用最少的调运方案。,12,解：（1）列出物资调运平衡表和运价表,需,供,运价,表5-2 供需平衡表,表5-3 运价表,料库,运价,工地,平衡表中填入的数字表示供需点之

8、间的调运量； 空格表示双方不发生调运关系,平衡表和运价表是表上作业法的基本资料和运算的依据。 表上作业法的实质就是利用运价表在平衡表上进行求解。,二. 确定产销地之间的供需联系和收发量,13,（2）编制初始调运方案,物资调运规划其总的目的是寻求一个运输费用最少的最优调运方案。一般最优方案是由初始方案经过反复调整得到的。因此，编制出较好的初始调运方案非常重要。 最好的调运方案是使运费最省的方案，因此可以用最小元素法来确定初始调运方案。 所谓最小元素法，就是按运价表依次挑选运费少的供需点尽量优先安排供应的调运方法。,二. 确定产销地之间的供需联系和收发量,需,供,运量,供需平衡表,运价表,料库,运

9、价,工地,1,首先，在运价表内找出最小的运价，对本例而言，方格(2，1)数值是1，最小，这样，供应点A2尽可能地满足B1工地的需要，于是在平衡表中有(2，1)300，即在空格(2，1)中填入数字300。 此时，由于工地B1已经全部得到满足，不需要其他仓库供应给它了，运价表中的第一列数字己不起作用，因此将运价表第一列划去，并标注符号，,需,供,运量,供需平衡表,运价表,料库,运价,工地,1,2,然后，在运价表未划去的各行、列中，再选取一个最小的运价，本例，即(2，3)2最小，让A2料库尽量供应满足B3工地的需要。由于A2库储量400t已供应给B1工地300t了，所以最多还能供给B3工地100t。

10、于是在平衡表(2，3)空格填入100；相应地由于仓库A2所储物资已全部供应完毕，因此，在运价表中与A2同行的运价也不再起作用，所以也将它们划去，并标注符号。,需,供,运价,供需平衡表,运价表,料库,运价,工地,1,2,4,3,5,仿照前面的方法，一直作下去，就可得到如左图所示的运价表和平衡表。 此时，在运价表中只有方格(1，4)处的运价没有划掉，B4尚有300t的需求，而A1刚好还有300t的物资可以供应，为了满足供需平衡，所以最后在平衡表上应有(1，4)300。这样就得到表56的初始调运方案。,需,供,运量,表5-6 初始调运方案,3,5,2,4,根据初始调运方案的运输量和单位运价，可以计算

11、初始调运方案的运输费用为： S=1*300+4*600+3*400+2*100+10*300+5*300=8600(元),1,10,价格,运量,18,（3）初始方案的检验与调整,1）最优方案的数字表征检验数 相关概念 闭回路：对表上作业法的初始方案，从调运方案表上的一个空格出发，存在条且仅存在一条以该空格(用 xij 表示)为起点，以其他填有数字的点为其他顶点的闭合回路，简称闭回路。 每个顶点都是闭合回路的转角点； 闭合回路是一条封闭折线，每一条边 都是水平或垂直的； 每一行(列)若有闭合回路的顶点，则必有两个（起点所在的行（列）除外）。 任一空格的闭合回路不仅是存在的，而且是唯一的。 只有从

12、空格出发，其余各转角点所对应的方格内均填有数字时，所构成的闭合回路，才是我们这里所说的闭回路 。,二. 确定产销地之间的供需联系和收发量,19,空格(1，1)： (1，1)(1，3)(2，3)(2，1)一(1，1) 空格(3，1)： (3，I)(2，1)(2，3)(1，3)一(1，4)(3，4)(3，1) 对所有的空格，都可以用同样的方法画出一条闭回路。,需,供,二. 确定产销地之间的供需联系和收发量,20,检验数：调运方案的每个空格所形成的闭回路上，作单位物资的运量调整，总可以计算出相应的运费是增加还是减少。我们把所计算出来的每条闭回路上调整单位运量而使运输费用发生变化的增减值，称其为检验数

13、。 如果检验数小于零，表示在该空格的闭回路上调整运量使运费减少； 如果检验数大于零，则表示在该空格的闭回路上调整运量会使运费增加。,最优方案的判定准则： 初始调运方案中，如果它所有的检验数都是非负的，那么这个初始调运方案一最优。否则。这一调运方案不一定是最优的。 （如果所有空格的检验数都小于零，那么如果再对调运方案进行任何调整，都会增加运输费用）,二. 确定产销地之间的供需联系和收发量,2）用位势法求检验数,将初始调运方案中填有运量的方格对应的运价cij分解为两部分，即： cij =ui+vj ,(对应前面的例题，i=1,2,3; j=1,2,3,4) 其中ui和vj 分别为该方格对应于i行和

14、j列的位势量.,需,供,C21=u2+v1=1 C23=u2+v3=2 C13=u1+v3=3 C34=u3+v4=5 7个未知量，六个方程,假定其中一个未知量为0（任意），如假定v1=0,则可以根据左边的方程解出全部未知量。,位势计算表,第1步：求位势量,需,供,准检验数表,按ui+vj求出各空格的位势量，得到准检验数表（加方括号表示）,准检验数计算过程 空格（1，1）= u1+v1 = 2+0 = 2 （3，1）=u3+v1= -3+0 = -3 （1，2）=u1+v2= 2+7 = 9 （2，2）=u2+v2= 1+7 = 8 （3，3）=u3+v3= -3+1 = -2 （2，4）=u

15、2+v4= 1+8 = 9,第2步：求准检验数,第3步：求检验数,运价表,准检验数表,利用运价表与准检验数表求检验数,检验数表,“运价表” 减 “准检验数表”,检验结果：检验数出现负值，根据最优方案判断准则，该方案不是最优方案。,3）调整调运方案,当判定一个初始调运方案不是最优调运方案时，就要在检验数出现负值的该空格内进行调整。 如果检验数是负值的空格不只一个时，一般选择检验数为负值且绝对值最大的空格作为具体的调整对象。,调整过程： （1）作出负值所在空格的闭回路，本例为空格x24，闭回路如上图所示。 （2）沿闭回路在各奇数次转角点中挑选运量的最小数值作为调整量。本例是将x23方格的100作为

16、调整量，将这个数填入空格x24内，同时调整该闭回路中其他转角点上的运量，使各行、列保持原来的供需平衡这样使得到一个新的调运方案。,需,供,运量,调整后的调运方案,1,3,5,2,4,10,8,调整后的检验数,通过计算其检验数全部非负，此方案为最优方案。 运输费用为： S3500十10200十8100十1300十4600十5300 8500(元) 该值小于初始调运方案的总运费。,26,(4)表上作业法基本步骤小结,列出调运物资的供需(产销)平衡表及运价表； 按最小元素法建立初始调运方案； 采用位势法计算初始方案每个空格的闭回路的检验数xij ； 检查检验数，如果所有xij =0，说明方案是最优的

17、，已经得到我们想要的方案，结束求解； 如果有某个或某几个xij0，则选择负检验数中绝对值最大的闭回路进行调整，建立新的方案； 重复35步，直至获得最优调运方案。,二. 确定产销地之间的供需联系和收发量,27,(5)供需不平衡的物资调运问题,通过虚设一个供应点或者需求点，将其转化为平衡运输问题求解。 供应量大于需求量 引入一个虚设的需求点，令其的需求量等于实际问题中供应量与需求量之差，令其运价为0。 需求量大于供应量 虚设一个供应点。令这个虚设的供应点的供应量等于实际问题中需求量与供应量的差额，运价为0。,二. 确定产销地之间的供需联系和收发量,28,三. 运输线路选择,运输路线的选择也是物资调

18、运规划的一个重要内容。 运输路线直接影响到运输效果的好坏，关系着物资能否及时运到指定地点。当单位输运输费用是以吨公里来计算时，运输路线的长短就直接关系着运输费用的多少。 本节采用图上作业法来进行运输线路选择。,29,1. 交通示意图的表示方法 交通示意图用来表明收发点的大致位置、收发量、交通路线长度的图形。 图形表示方法： （1）发点（产地或仓库）用符号 表示，里面的数字表示发货量； （2）收点用（需求地）用符号 表示，里面的数字表示收货量； （3）两点间的连线为交通线，其长度记在交通线旁边。 （4）物资调运的方向(流向)用符号 表示，并把 按物资调运方向画在交通线的右边，把调运物资的数量记在

19、 的右边，并加上括号，以表示和交通线长度区别。,20,15,20,5,10,物资调运交通流向图,20,（20）,10,20,10,（5）,（15）,（10）,三. 运输线路选择,30,2.图上作业法 目的：根据交通流向图，找出运输力量最小的方案。 方法：消灭调运中的对流和迂回两种不合理运输。,三. 运输线路选择,31,（1） 对流 即同一物资在同一线路上的往返运输。 如下面的图， 将某物资10吨，从A1运到B2，而又有同样的物资10吨，在同一期间从A2运到B1，于是A1A2间就出现了对流现象。,10,10,10,30,30,40,30,（10）,（10）,A1,A2,B1,B2,如果从图上看，

20、对流可以理解为同一条交通线上，有两条或两条以上的物资调运方向。,10,10,10,30,30,40,30,（10）,A1,A2,B1,B2,（10）,消除对流,运力： 30*10+20*10=600,运力： 30*10+40*10+40*10+30*10=1400,三. 运输线路选择,32,（2）迂回 迂回： 在交通图成圈的时候，如果流向图中内圈流向的总长(简称内流长)或外圈流向的总长(简称外流长)超过整个圈长的半，就称为迂回运输。 内、外圈的概念：由于表示调运方向的箭头，要按调运方向，画在交通线的右边，因此,流向图中，有些流向就在圈外，称为外圈流向；有些流向在圈内，称为内圈流向。,5,5,6

21、千米,A,B,（5吨）,4千米,5,5,6千米,A,B,（5吨）,4千米,迂回运输,无迂回运输,迂回运输：运力 6*5=30吨.千米 无迂回运输：运力 4*5=20吨.千米,三. 运输线路选择,33,例题，下图为一运输交通图,该交通图的运输线路构成圈。 圈的总长=2+3+4+4=13 内圈长=4+3=7 内圈长大于总圈长 的一半，为迂回运输 运力：3*30+4*20+4*10=210 修改后： 内圈长=3 外圈长=2+4=6 内圈长、外圈长都小于总圈长的一半，不存在迂回运输 运力：2*10+3*20+4*30=200 节省运力：210-200=10,10,30,30,50,2,4,3,（20）

22、,A1,B2,A2,4,B1,（30）,（10）,10,30,30,50,2,4,3,（30）,A1,B2,A2,4,（20）,（10）,修改,三. 运输线路选择,34,物资调运问题的图上作业法 消除运输过程中的对流和迂回，节省运输力量。 具体步骤： 先画出一个没有对流的运输方案. 再检查有没有迂回，如果没有迂回，这方案就是最优方案； 如果有迂回，则对方案进行调整，直至消除迂回现象为止。 在实际的物资调运中，运输线路可以分为两种情况： 交通线路成圈 交通线路不成圈,三. 运输线路选择,3. 交通路线不成圈,例题3 有某物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7(万吨)

23、，运往B1，B2，B3，B4，收量分别为8，1，3，5(万吨)，收发量平衡，交通路线如图58所示，问应如何调运，才使运输吨千米最小？,5,5,8,（5）,A1,B1,2,7,3,1,3,A2,A3,A4,B2,B3,B4,5,5,8,A1,B1,2,7,3,1,3,A2,A3,A4,B2,B3,B4,交通线路图,调运流向图,解：该交通线路不成圈，只需要做一没有对流的调运图。 方法：从各端点开始，由外到里，逐步进行各收发点之间的平衡,（2）,（1）,（2）,（1）,（7）,（5）,4. 交通路线成圈,例题4 有某物资7万吨，由A1，A2，A3发出，发量分别为3，3，1(万吨)，运往B1，B2，B

24、3，B4，收量分别为2，3，1，1(万吨)，收发量平衡，交通路线如图510所示，问应如何调运，才使运输吨千米最小？,1,1,3,3,3,4,B4,A3,2,1,3,A1,A2,B1,B3,B2,7,5,4,3,2,4,1,1,3,3,3,4,B4,A3,2,1,3,A1,A2,B1,B3,B2,7,5,4,3,2,4,解: (1)作一个没有对流的流向图。 方法：用“去线破圈”的方法。去一线破一圈，有几个圈去掉几条线，把有圈的交通图，转化为不成圈的交通图。 技巧：一般先去掉长度最长的交通线，比如本例中去掉A1B4(7千米)，破A1B1B2A3B4圈；再去掉A3B3线(4千米)，破B2A2B3A3

25、圈。这样，原来有圈的交通图，变成了不成圈的交通图如图511所示。,从各个端点开始，做一个没有对流的流向图,1,1,3,3,3,4,B4,A3,2,1,3,A1,A2,B1,B3,B2,7,5,4,3,2,4,（1）,（3）,（1）,（2）,（1）,(2)检查有无迂回。 方法：对流向图中的各圈进行检查，如果没有迂回，则这个初始方案就是最优方案，如果其中某圈中有迂回，则不是最优方案，需要改进。,1,1,3,3,3,4,B4,A3,2,1,3,A1,B1,B3,B2,7,5,4,3,2,4,（1）,（3）,（1）,（2）,（1）,A1B1B2A3B4总圈长 =7+3+4+4+5=23 外流长=5+4

26、+3=12 存在迂回，需要调整。 B2A2B3A3总圈长 =4+3+2+4=13 内流长=3 外流长=2 不存在迂回，不需要调整,A2,1,1,3,3,3,4,B4,A3,2,1,3,A1,B1,B3,B2,7,5,4,3,2,4,（1）,（3）,（1）,（2）,A2,调整方法： 1）在外圈的各流量中，减去外圈的最小流量1万吨； 2）在内圈的各流量中加上1万吨，在此圈中，因无内流量，故不加。 3）在无流量的线路上，新添加内圈流量1万吨。,（-1）,（-1）,（-1）,（+1）,（+1）,（1）,1,1,3,3,3,4,B4,A3,2,1,3,A1,B1,B3,B2,7,5,4,3,2,4,（2

27、）,（2）,A2,（1）,（1）,A1B1B2A3B4总圈长 =7+3+4+4+5=23 外流长=5 内流长=7+4=11 不存在迂回。 B2A2B3A3总圈长 =4+3+2+4=13 内流长=3 外流长=4+2=6 不存在迂回 此方案为最优调运方案 总运力：1*7+2*5+1*4+2*3+1*2=29万吨千米,（1）,41,四. 最短路与最大流,1. 最短路线 例题5 某家运输公司签定了一项运输合同，要把A市的一批货物运送到B市。该公司根据两个城市之间可选择的行车路线地图，绘制了图513的公路网络。要求从交通网络图中，寻找一条线路最短的运输路线。,1,A市,4,5,2,3,7,6,9,8,1

28、0,B市,100,150,175,300,275,200,175,275,200,300,200,400,250,125,100,150,图中 为结点，代表起点、目的地和与行车路线相交的其他城市，其中的数字为结点编号。 箭头为分支，代表两个结点之间的公路，箭头上标明的数字为运输里程。,公路网络,1,解：从终点开始逐步逆向推算。 (1)与终点10联接的结点有两个，即结点9和8； 从结点9到结点10只有一条线路，该线路为最短线路，长度100，记为：（9-10）100； 同样，结点8到结点10的最短线路为150，记为（8-10）150； (2)结点6。与6联接的只有一个结点9，6至9的最短里程为20

29、0。而9至终点10的最短里程为100因此6至终点10的最短里程为200十100300。记为：(6-9-10)300。 (3)结点5。与5联接的结点有9、8两个。 5至9再至终点的最短里程为400十100500， 5至8再至终点的最短里程为250十155400。 400500，所以5至终点的最短里程为400，记为：(5-8-10)400。 (4) 结点7。至终点的最短里程为125十150275，记为：(7-8-10) 275。,1,A市,4,5,2,3,7,6,9,8,10,B市,100,150,175,275,200,175,275,200,300,200,400,250,125,100,15

30、0,300,(5)结点4。与4联接的结点有5、6、7三个。 结点4至6再到终点的最短里程为200十300=500； 结点4至5再到终点的最短里程为175十400575； 结点4至7再到终点的最短里程为275十275550。 三个里程中以500为最小，所以结点4至l 0的最短里程记为(46910) 500。 (6)结点2和3。 用同样的方法，得到： 结点2到终点的最短里程为600。记为：(26910)600。 结点3到终点的最短里程为575。记为：(37810)575。 (5)最后看结点1。结点1可以通过三个结点2、3、4连接到终点。 结点1通过结点2再到终点的最短里程100十600700，路径

31、为（126910）700； 结点1通过结点4再到终点的最短里程150十500650，路径为（146910）650； 结点1通过结点3再到终点的最短里程175十575750，路径为（137810）750。 以上三个里程中以650为最小，即A币到B市的最短里程，对应的最短路线为：146910。,1,A市,4,5,2,3,7,6,9,8,10,B市,100,150,175,275,200,175,275,200,300,200,400,250,125,100,150,300,44,最短路线法的应用 物资的运输路线的选择 物流渠道的设计 电缆架设 管道铺设 个人旅行中,45,2. 最大流 当要把大量货物运输到指定的地点时，有时会希望找到一条交通量最大的路线，以使货物能在最短时间内到达。这就是要在有一个起点和一个终点的网络中，找出在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量问题。,1,5,2,3,4,5,6,6,4,3,3,5,7,2,起点,终点,1,结点,通过能力,交通线路,46,运输网络最大流量的计算 例题：某城市从北到南的交通，平时是利用85号公