《物流系统工程》第5章-1-物流系统规划课件

第5章物流系统规划5.1概述5.2物流调运规划5.3物流分配规划5.4其它应用问题1第5章物流系统规划5.1概述15.1概述25.1概述2一.物流系统规划概述物流系统规划所关注的问题是如何合理、有效地利用或配置各种资源（劳动力、材料、设备、资金），使实现预定目标所需的费用最小（或资源最少），或者所获得的收益最大。物流系统的规划一般都可以用优化模型来表达。其基本思想是在满足一定的约束条件下，使预定的目标值达到最优。物流系统规划的数学基础主要是运筹学理论，常用的方法包括线性规划、整数规划、动态规划等。3一.物流系统规划概述物流系统规划所关注的问题是如何合理、有二.物流系统规划的目标任务提高物流系统的吞吐能力以适应产量增长的要求；建设一个柔性的物流系统，以适应产品经常变化的情况；对生产过程中可能出现的各种意外情况或随机变化做出及时的响应，保持均衡生产；改善劳动条件，减轻劳动强度；对物流系统中的货物进行实时跟踪；对物流系统的货物进行分类或选配，为随后的处理(加工或包装)提供方便条件。4二.物流系统规划的目标任务提高物流系统的吞吐能力以适应产量三.评价物流系统规划的主要指标经济性。包括初始投资、每年的运营费用、直接或间接的经济效益、投资回收期、全员劳动生产率等；可靠性。包括单个环节的可靠性和整个系统的可靠性技术、设备故障率和排除故障所需的时间；可维护性。维护保养所要求的技术水平、备件的供应情况、所需储备的备件数量；灵活性或柔性。适应产品设计更改和产量变化的能力，物流系统各环节与生产节奏相匹配的能力，调整物流路线的可能性；可扩展性。在物流系统的服务范围和吞吐能力方面进—步扩大的可能性；安全性。包括产品的安全、人员的安全、以及正常运行和事故状态下的安全保障；劳动强度。需要劳动力的数量、劳动者的疲劳程度；易操作性。操作简单、不易出错，只需少量指令即可使设备和整个系统投入运行；服务水平。对顾客的要求做出快速响应的能力；环境保护。符合环境保护条理的要求，对周围环境的污染程度低。敏感性。对外界条件变动的敏感程度和适应能力。5三.评价物流系统规划的主要指标5四.物流系统规划中的变量物流系统规划中的控制因素分为两类不可控因素：设计人员无法左右的种种前提条件。可控因素：可以由规划设计人员在一定范围内选取的变量。明确了物流系统中可控变量和不可控因素，就能知道加何去影响系统的性能，达到所追求的目标。物流系统的规划一般是通过调整可控变量观察系统性能的变化趋势，从而选择可控变量的最佳匹配，达到系统的最佳效果。物流系统的功能除了受可控变量的影响外，还与不可控因素有密切的关系。通常，不可控因素不是非常确定的。6四.物流系统规划中的变量物流系统规划中的控制因素分为两类65.2物流系统调运规划75.2物流系统调运规划7一.问题描述调运规划问题描述

设某种要调运的物资，有一组供应点(产地或称发点)m个，一组需求点(销地或称收点)n个，如果每个供应点的供应量及每个需求点的需求量都已经确定，即第i个产地有ai单位的物资发出，第j个需求点需要收进bj单位的物资；并且从每—个产地到每一个销地的单位运价是已知的，假定把单位物资从第i个产地调运到第j个销地去的单位运价为cij。调运规划问题也叫运输问题物资调运规划的目的：制订一个合理的调运方案；确定m个产地与n个销地之间的供需联系和数量的最优搭配；确定具体的运输路线，使总的运输费用最低。8一.问题描述调运规划问题描述8二.确定产销地之间的供需联系和收发量1.数学模型设供应点为Ai，该供应点的供应量是ai，（i=1,2,…,m）；设需求点为Bj，该需求点的需求量是bi，（j＝1,2,…,n）；

cij为从第i个供应点到第j个需求点的单位运价；由供应点Ai发往需求点Bj的物资调运量是xij单位。假设m个供应点的总供应量等于n个需求点的总需求量，（这样，调运问题满足供需平衡，称为平衡运输问题）。这时，由各供应点Ai调出的物资总量应等于它的供应量ai(i=1,2,…,m)；而每一个需求点Bj调入的物资总量应等于它的需求量bj(j=1,2,…,n)。目标函数：约束条件9二.确定产销地之间的供需联系和收发量1.数学模型约束条二.确定产销地之间的供需联系和收发量2.模型求解用线性规划方法求解（如单纯形法）。用表上作业法求解（针对这类问题的一种特殊解法）3.表上作业法的主要步骤首先依据问题列出调运物资的供需平衡表以及运价表；其次确定一个初始的调运方案(当然不一定就是最优的方案)；然后根据一个判定法则，判定初始方案是否为最优方案。当判定初始方案不是最优方案时，再对这个方案进行调整。一般情况，每调整一次得到一个新的方案，而这个新方案的运费比前一个方案要少些，如此经过几次调整，就会得到最优方案。10二.确定产销地之间的供需联系和收发量2.模型求解10B1B2B3B4供应量(t)A1311310700A21928400A374105900需求量(t)3006005006002000工地料库运价表5-1某公司物资供应状况表二.确定产销地之间的供需联系和收发量4.表上作业法解题实例例题1某公司下属三个储存某种物资的仓库，供应四个工地的需要。三个仓库的供应量和四个工地的需求量以及由各仓库到各工地调运单位物资的运价(元／吨)由表5—1给出，试求运输费用最少的调运方案。11B1B2B3B4供应量(t)A1311310700A2192解：（1）列出物资调运平衡表和运价表

B1B2B3B4供应量(t)A1700A2400A3900需求量(t)3006005006002000需供运价表5-2供需平衡表表5-3运价表

B1B2B3B4A1311310A21928A374105料库运价工地平衡表中填入的数字表示供需点之间的调运量；空格表示双方不发生调运关系平衡表和运价表是表上作业法的基本资料和运算的依据。表上作业法的实质就是利用运价表在平衡表上进行求解。二.确定产销地之间的供需联系和收发量12解：（1）列出物资调运平衡表和运价表B1B2B3B4供应量（2）编制初始调运方案

物资调运规划其总的目的是寻求一个运输费用最少的最优调运方案。一般最优方案是由初始方案经过反复调整得到的。因此，编制出较好的初始调运方案非常重要。最好的调运方案是使运费最省的方案，因此可以用最小元素法来确定初始调运方案。所谓最小元素法，就是按运价表依次挑选运费少的供——需点尽量优先安排供应的调运方法。二.确定产销地之间的供需联系和收发量13（2）编制初始调运方案物资调运规划其总的目的是寻求一个运输B1B2B3B4供应量(t)A1700A2300400A3900需求量(t)3006005006002000需供运量供需平衡表运价表

B1B2B3B4A1311310A21928A374105料库运价工地1首先，在运价表内找出最小的运价，对本例而言，方格(2，1)数值是1，最小，这样，供应点A2尽可能地满足B1工地的需要，于是在平衡表中有(2，1)＝300，即在空格(2，1)中填入数字300。此时，由于工地B1已经全部得到满足，不需要其他仓库供应给它了，运价表中的第一列数字己不起作用，因此将运价表第一列划去，并标注符号①，14B1B2B3B4供应量(t)A1700A2300400A39B1B2B3B4供应量(t)A1700A2300100400A3900需求量(t)3006005006002000需供运量供需平衡表运价表

B1B2B3B4A1311310A21928A374105料库运价工地12然后，在运价表未划去的各行、列中，再选取一个最小的运价，本例，即(2，3)＝2最小，让A2料库尽量供应满足B3工地的需要。由于A2库储量400t已供应给B1工地300t了，所以最多还能供给B3工地100t。于是在平衡表(2，3)空格填入100；相应地由于仓库A2所储物资已全部供应完毕，因此，在运价表中与A2同行的运价也不再起作用，所以也将它们划去，并标注符号②。15B1B2B3B4供应量(t)A1700A2300100400B1B2B3B4供应量(t)A1400700A2300100400A3600300900需求量(t)3006005006002000需供运价供需平衡表运价表

B1B2B3B4A1311310A21928A374105料库运价工地12435仿照前面的方法，一直作下去，就可得到如左图所示的运价表和平衡表。此时，在运价表中只有方格(1，4)处的运价没有划掉，B4尚有300t的需求，而A1刚好还有300t的物资可以供应，为了满足供需平衡，所以最后在平衡表上应有(1，4)＝300。这样就得到表5—6的初始调运方案。16B1B2B3B4供应量(t)A1400700A2300100B1B2B3B4供应量(t)A1400300700A2300100400A3600300900需求量(t)3006005006002000需供运量表5-6初始调运方案3524根据初始调运方案的运输量和单位运价，可以计算初始调运方案的运输费用为：S=1*300+4*600+3*400+2*100+10*300+5*300=8600(元)110价格运量17B1B2B3B4供应量(t)A1400300700A2300（3）初始方案的检验与调整1）最优方案的数字表征——检验数相关概念

闭回路：对表上作业法的初始方案，从调运方案表上的一个空格出发，存在—条且仅存在一条以该空格(用xij表示)为起点，以其他填有数字的点为其他顶点的闭合回路，简称闭回路。每个顶点都是闭合回路的转角点；闭合回路是一条封闭折线，每一条边都是水平或垂直的；每一行(列)若有闭合回路的顶点，则必有两个（起点所在的行（列）除外）。任一空格的闭合回路不仅是存在的，而且是唯一的。只有从空格出发，其余各转角点所对应的方格内均填有数字时，所构成的闭合回路，才是我们这里所说的闭回路。二.确定产销地之间的供需联系和收发量18（3）初始方案的检验与调整1）最优方案的数字表征——检验数二

空格(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)对所有的空格，都可以用同样的方法画出一条闭回路。B1B2B3B4供应量(t)A1400300700A2300100400A3600300900需求量(t)3006005006002000需供二.确定产销地之间的供需联系和收发量19空格(1，1)：(1，1)—(1，3)—(2，3)—(检验数：调运方案的每个空格所形成的闭回路上，作单位物资的运量调整，总可以计算出相应的运费是增加还是减少。我们把所计算出来的每条闭回路上调整单位运量而使运输费用发生变化的增减值，称其为检验数。如果检验数小于零，表示在该空格的闭回路上调整运量使运费减少；如果检验数大于零，则表示在该空格的闭回路上调整运量会使运费增加。

最优方案的判定准则：初始调运方案中，如果它所有的检验数都是非负的，那么这个初始调运方案一最优。否则。这一调运方案不一定是最优的。

（如果所有空格的检验数都小于零，那么如果再对调运方案进行任何调整，都会增加运输费用）二.确定产销地之间的供需联系和收发量20检验数：调运方案的每个空格所形成的闭回路上，作单位物资的2）用位势法求检验数将初始调运方案中填有运量的方格对应的运价cij分解为两部分，即：cij=ui+vj,(对应前面的例题，i=1,2,3;j=1,2,3,4)其中ui和vj分别为该方格对应于i行和j列的位势量.B1B2B3B4uiA1310U1=2A212U2=1A345U3=-3viv1=0v2=7v3=1v4=8需供C21=u2+v1=1C23=u2+v3=2C13=u1+v3=3……C34=u3+v4=57个未知量，六个方程假定其中一个未知量为0（任意），如假定v1=0,则可以根据左边的方程解出全部未知量。位势计算表第1步：求位势量212）用位势法求检验数将初始调运方案中填有运量的方格对B1B2B3B4uiA1[2][9]310U1=2A21[8]2[9]U2=1A3[-3]4[-2]5U3=-3viv1=0v2=7v3=1v4=8需供准检验数表按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）=u2+v4=1+8=9第2步：求准检验数22B1B2B3B4uiA1[2][9]310U1=2A21[8B1B2B3B4A1[2][9]310A21[8]2[9]A3[-3]4[-2]5第3步：求检验数运价表B1B2B3B4A1311310A21928A374105准检验数表利用运价表与准检验数表求检验数检验数表B1B2B3B4A112A21-1A31012“运价表”减“准检验数表”检验结果：检验数出现负值，根据最优方案判断准则，该方案不是最优方案。23B1B2B3B4A1[2][9]310A21[8]2[9]A3）调整调运方案当判定一个初始调运方案不是最优调运方案时，就要在检验数出现负值的该空格内进行调整。如果检验数是负值的空格不只一个时，一般选择检验数为负值且绝对值最大的空格作为具体的调整对象。X13400+100=500X14300-100=200X23100-100=0X240+100=100

B1B2B3B4A1

400300A2300

100

负A3

600

300调整过程：（1）作出负值所在空格的闭回路，本例为空格x24，闭回路如上图所示。（2）沿闭回路在各奇数次转角点中挑选运量的最小数值作为调整量。本例是将x23方格的100作为调整量，将这个数填入空格x24内，同时调整该闭回路中其他转角点上的运量，使各行、列保持原来的供需平衡．这样使得到一个新的调运方案。243）调整调运方案当判定一个初始调运方案不是最优调运方案时，就B1B2B3B4供应量(t)A1500200700A23000100400A3600300900需求量(t)3006005006002000需供运量调整后的调运方案13524108B1B2B3B4A122A241A3912调整后的检验数通过计算其检验数全部非负，此方案为最优方案。运输费用为：S＝3×500十10×200十8×100十1×300十4×600十5×300＝8500(元)该值小于初始调运方案的总运费。25B1B2B3B4供应量(t)A1500200700A2300(4)表上作业法基本步骤小结①列出调运物资的供需(产销)平衡表及运价表；②按最小元素法建立初始调运方案；③采用位势法计算初始方案每个空格的闭回路的检验数xij；④检查检验数，如果所有xij>=0，说明方案是最优的，已经得到我们想要的方案，结束求解；⑤如果有某个或某几个xij<0，则选择负检验数中绝对值最大的闭回路进行调整，建立新的方案；⑥重复3—5步，直至获得最优调运方案。二.确定产销地之间的供需联系和收发量26(4)表上作业法基本步骤小结①列出调运物资的供需(产销)平衡(5)供需不平衡的物资调运问题通过虚设一个供应点或者需求点，将其转化为平衡运输问题求解。①供应量大于需求量引入一个虚设的需求点，令其的需求量等于实际问题中供应量与需求量之差，令其运价为0。

②需求量大于供应量虚设一个供应点。令这个虚设的供应点的供应量等于实际问题中需求量与供应量的差额，运价为0。

二.确定产销地之间的供需联系和收发量27(5)供需不平衡的物资调运问题通过虚设一个供应点或者需求点，三.运输线路选择运输路线的选择也是物资调运规划的一个重要内容。

运输路线直接影响到运输效果的好坏，关系着物资能否及时运到指定地点。当单位输运输费用是以吨·公里来计算时，运输路线的长短就直接关系着运输费用的多少。本节采用图上作业法来进行运输线路选择。28三.运输线路选择运输路线的选择也是物资调运规划的一个重要内1.交通示意图的表示方法

交通示意图用来表明收发点的大致位置、收发量、交通路线长度的图形。图形表示方法：（1）发点（产地或仓库）用符号表示，里面的数字表示发货量；（2）收点用（需求地）用符号表示，里面的数字表示收货量；（3）两点间的连线为交通线，其长度记在交通线旁边。（4）物资调运的方向(流向)用符号表示，并把按物资调运方向画在交通线的右边，把调运物资的数量记在的右边，并加上括号，以表示和交通线长度区别。201520510物资调运交通流向图20（20）102010（5）（15）（10）三.运输线路选择291.交通示意图的表示方法201520510物资调运交通流向2.图上作业法目的：根据交通流向图，找出运输力量最小的方案。方法：消灭调运中的对流和迂回两种不合理运输。三.运输线路选择302.图上作业法三.运输线路选择30（1）对流

即同一物资在同一线路上的往返运输。

如下面的图，将某物资10吨，从A1运到B2，而又有同样的物资10吨，在同一期间从A2运到B1，于是A1A2间就出现了对流现象。

10101030304030（10）（10）A1A2B1B2

如果从图上看，对流可以理解为同一条交通线上，有两条或两条以上的物资调运方向。10101030304030（10）A1A2B1B2（10）消除对流运力：30*10+20*10=600运力：30*10+40*10+40*10+30*10=1400三.运输线路选择31（1）对流10101030304030（10）（10）A（2）迂回

迂回：在交通图成圈的时候，如果流向图中内圈流向的总长(简称内流长)或外圈流向的总长(简称外流长)超过整个圈长的—半，就称为迂回运输。

内、外圈的概念：由于表示调运方向的箭头，要按调运方向，画在交通线的右边，因此,流向图中，有些流向就在圈外，称为外圈流向；有些流向在圈内，称为内圈流向。556千米AB（5吨）4千米556千米AB（5吨）4千米迂回运输无迂回运输迂回运输：运力6*5=30吨.千米无迂回运输：运力4*5=20吨.千米三.运输线路选择32（2）迂回556千米AB（5吨）4千米556千米A例题，下图为一运输交通图该交通图的运输线路构成圈。圈的总长=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=1010303050243（20）A1B2A24B1（30）（10）10303050243（30）A1B2A24（20）（10）修改三.运输线路选择33例题，下图为一运输交通图该交通图的运输线路构成圈。10303物资调运问题的图上作业法消除运输过程中的对流和迂回，节省运输力量。具体步骤：先画出一个没有对流的运输方案.再检查有没有迂回，如果没有迂回，这方案就是最优方案；如果有迂回，则对方案进行调整，直至消除迂回现象为止。在实际的物资调运中，运输线路可以分为两种情况：交通线路成圈交通线路不成圈三.运输线路选择34物资调运问题的图上作业法三.运输线路选择343.交通路线不成圈例题3有某物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7(万吨)，运往B1，B2，B3，B4，收量分别为8，1，3，5(万吨)，收发量平衡，交通路线如图5—8所示，问应如何调运，才使运输吨．千米最小？558（5）A1B127313A2A3A4B2B3B4558A1B127313A2A3A4B2B3B4交通线路图调运流向图解：该交通线路不成圈，只需要做一没有对流的调运图。方法：从各端点开始，由外到里，逐步进行各收发点之间的平衡（2）（1）（2）（1）（7）（5）353.交通路线不成圈例题3有某物资17万吨，由A1，A4.交通路线成圈例题4有某物资7万吨，由A1，A2，A3发出，发量分别为3，3，1(万吨)，运往B1，B2，B3，B4，收量分别为2，3，1，1(万吨)，收发量平衡，交通路线如图5—10所示，问应如何调运，才使运输吨．千米最小？113334B4A3213A1A2B1B3B2754324364.交通路线成圈例题4113334B4A3213A1A113334B4A3213A1A2B1B3B2754324解:(1)作一个没有对流的流向图。方法：用“去线破圈”的方法。去一线破一圈，有几个圈去掉几条线，把有圈的交通图，转化为不成圈的交通图。技巧：一般先去掉长度最长的交通线，比如本例中去掉A1B4(7千米)，破A1B1B2A3B4圈；再去掉A3B3线(4千米)，破B2A2B3A3圈。这样，原来有圈的交通图，变成了不成圈的交通图．如图5—11所示。从各个端点开始，做一个没有对流的流向图113334B4A3213A1A2B1B3B2754324（1）（3）（1）（2）（1）37113334B4A3213A1A2B1B3B2754324解

(2)检查有无迂回。

方法：对流向图中的各圈进行检查，如果没有迂回，则这个初始方案就是最优方案，如果其中某圈中有迂回，则不是最优方案，需要改进。113334B4A3213A1B1B3B2754324（1）（3）（1）（2）（1）A1B1B2A3B4总圈长=7+3+4+4+5=23外流长=5+4+3=12存在迂回，需要调整。B2A2B3A3总圈长=4+3+2+4=13内流长=3外流长=2不存在迂回，不需要调整A238(2)检查有无迂回。

方法：对流向图中的各圈进行检查，113334B4A3213A1B1B3B2754324（1）（3）（1）（2）A2调整方法：1）在外圈的各流量中，减去外圈的最小流量1万吨；2）在内圈的各流量中加上1万吨，在此圈中，因无内流量，故不加。3）在无流量的线路上，新添加内圈流量1万吨。（-1）（-1）（-1）（+1）（+1）（1）39113334B4A3213A1B1B3B2754324（1）113334B4A3213A1B1B3B2754324（2）（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）40113334B4A3213A1B1B3B2754324（2）四.最短路与最大流

1.最短路线例题5某家运输公司签定了一项运输合同，要把A市的一批货物运送到B市。该公司根据两个城市之间可选择的行车路线地图，绘制了图5—13的公路网络。要求从交通网络图中，寻找一条线路最短的运输路线。1A市4523769810B市100150175300275200175275200300200400250125100150图中为结点，代表起点、目的地和与行车路线相交的其他城市，其中的数字为结点编号。箭头为分支，代表两个结点之间的公路，箭头上标明的数字为运输里程。公路网络141四.最短路与最大流1.最短路线1A市452376981解：从终点开始逐步逆向推算。(1)与终点10联接的结点有两个，即结点9和8；从结点9到结点10只有一条线路，该线路为最短线路，长度100，记为：（9-10）100；同样，结点8到结点10的最短线路为150，记为（8-10）150；(2)结点6。与6联接的只有一个结点9，6至9的最短里程为200。而9至终点10的最短里程为100．因此6至终点10的最短里程为200十100＝300。记为：(6-9-10)300。(3)结点5。与5联接的结点有9、8两个。5至9再至终点的最短里程为400十100＝500，5至8再至终点的最短里程为250十155＝400。400＜500，所以5至终点的最短里程为400，记为：(5-8-10)400。(4)结点7。至终点的最短里程为125十150＝275，记为：(7-8-10)275。

1A市4523769810B市10015017527520017527520030020040025012510015030042解：从终点开始逐步逆向推算。1A市4523769810B市1(5)结点4。与4联接的结点有5、6、7三个。结点4至6再到终点的最短里程为200十300=500；结点4至5再到终点的最短里程为175十400＝575；结点4至7再到终点的最短里程为275十275＝550。三个里程中以500为最小，所以结点4至l0的最短里程记为(4—6—9—10)500。(6)结点2和3。用同样的方法，得到：结点2到终点的最短里程为600。记为：(2—6—9—10)600。结点3到终点的最短里程为575。记为：(3—7—8—10)575。(5)最后看结点1。结点1可以通过三个结点2、3、4连接到终点。结点1通过结点2再到终点的最短里程100十600＝700，路径为（1—2—6—9—10）700；结点1通过结点4再到终点的最短里程150十500＝650，路径为（1—4—6—9—10）650；结点1通过结点3再到终点的最短里程175十575＝750，路径为（1—3—7—8—10）750。以上三个里程中以650为最小，即A币到B市的最短里程，对应的最短路线为：1—4—6—9—10。1A市4523769810B市10015017527520017527520030020040025012510015030043(5)结点4。与4联接的结点有5、6、7三个。1A市4523最短路线法的应用物资的运输路线的选择物流渠道的设计电缆架设管道铺设个人旅行中44最短路线法的应用442.最大流当要把大量货物运输到指定的地点时，有时会希望找到一条交通量最大的路线，以使货物能在最短时间内到达。这就是要在有一个起点和一个终点的网络中，找出在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量问题。15234566433572起点终点1结点通过能力交通线路452.最大流15234566433572起点终点1结点通过能运输网络最大流量的计算例题：某城市从北到南的交通，平时是利用85号公路进行的。目前因为85号公路要进行路面维修，车辆不能通过。技术人员查明：在维修期间可以利用市区的其它几条路线通行，现在需要确定这几条线路组成的交通网络能否满足每小时6000辆汽车的通过能力。15234566433572北南该市从北到南的临时交通网络如上图所示，交通线路旁边的数字表示单位时间内汽车的通过能力（每小时千辆）。现在要求从结点1通过公路网到结点6的最大通过能力（最大流量）。846运输网络最大流量的计算15234566433572北南该市从计算方法（1）任意选择一条从起点①到终点⑥的路线。例如，选择路线1-2-5-6。首先找出这条路线上流量能力最小的支线。从图上可以看出：5—6支线流量最小，其流量为2，表明沿“1-2-5-6”支线南驶的汽车，每小时的最大流量只能是2千辆，因为5-6支线限制了全线的车流量。其次把这条路线上每条支线的流量减去2。差值则表示该支线剩余的流量。将差值其写在原来的流量能力的旁边，并把原来的流量划掉；把减数2写在每条支线的终点，在减数2的右下角注上(1)，如2（1），表示第一条路线的流量能力为2千辆。标注方式如图所示。15234566442335720北南2（1）2（1）2（1）47计算方法15234566442335720北南2(2)另选一条从起点1到终点6的路线，如：1-4-6。以该路线上最小的流量能力3为减数，减去各条支线上的流量。其差数、减数的记入方法同上。在差数3的右下角注上(2)，表示第二条路线的流量能力为3千辆。1523456644230357420北南2（1）2（1）2（1）3（2）3（2）48(2)另选一条从起点1到终点6的路线，如：1-4-6。152（3）再选一条从起点1到终点6的路线，如1-3-4-6。以该路线上最小的流量能力3为减数，减去各条支线上的流量，其差数、减数的记入方式同上。第三条路线的流量能力为3干辆（4）在剩下的流量图中，已经找不到一条完整的路线，满足所有支路流量大于0的条件，因此能够通行的交通路线已经全部标出。（5）网络的最大交通能力第一条线路1-2-5-6，流量2千辆/小时；第二条线路1-4-6，流量3千辆/小时；第三条线路1-3-4-6，流量3千辆/小时；该交通网络的从北到南的最大通行流量为2+3+3=8千辆/小时。满足每小时6000辆的通过能力。1522345664423030574120北南2（1）2（1）2（1）3（2）3（2）3（3）3（3）3（3）49（3）再选一条从起点1到终点6的路线，如1-3-4-6。15第5章物流系统规划5.1概述5.2物流调运规划5.3物流分配规划5.4其它应用问题50第5章物流系统规划5.1概述15.1概述515.1概述2一.物流系统规划概述物流系统规划所关注的问题是如何合理、有效地利用或配置各种资源（劳动力、材料、设备、资金），使实现预定目标所需的费用最小（或资源最少），或者所获得的收益最大。物流系统的规划一般都可以用优化模型来表达。其基本思想是在满足一定的约束条件下，使预定的目标值达到最优。物流系统规划的数学基础主要是运筹学理论，常用的方法包括线性规划、整数规划、动态规划等。52一.物流系统规划概述物流系统规划所关注的问题是如何合理、有二.物流系统规划的目标任务提高物流系统的吞吐能力以适应产量增长的要求；建设一个柔性的物流系统，以适应产品经常变化的情况；对生产过程中可能出现的各种意外情况或随机变化做出及时的响应，保持均衡生产；改善劳动条件，减轻劳动强度；对物流系统中的货物进行实时跟踪；对物流系统的货物进行分类或选配，为随后的处理(加工或包装)提供方便条件。53二.物流系统规划的目标任务提高物流系统的吞吐能力以适应产量三.评价物流系统规划的主要指标经济性。包括初始投资、每年的运营费用、直接或间接的经济效益、投资回收期、全员劳动生产率等；可靠性。包括单个环节的可靠性和整个系统的可靠性技术、设备故障率和排除故障所需的时间；可维护性。维护保养所要求的技术水平、备件的供应情况、所需储备的备件数量；灵活性或柔性。适应产品设计更改和产量变化的能力，物流系统各环节与生产节奏相匹配的能力，调整物流路线的可能性；可扩展性。在物流系统的服务范围和吞吐能力方面进—步扩大的可能性；安全性。包括产品的安全、人员的安全、以及正常运行和事故状态下的安全保障；劳动强度。需要劳动力的数量、劳动者的疲劳程度；易操作性。操作简单、不易出错，只需少量指令即可使设备和整个系统投入运行；服务水平。对顾客的要求做出快速响应的能力；环境保护。符合环境保护条理的要求，对周围环境的污染程度低。敏感性。对外界条件变动的敏感程度和适应能力。54三.评价物流系统规划的主要指标5四.物流系统规划中的变量物流系统规划中的控制因素分为两类不可控因素：设计人员无法左右的种种前提条件。可控因素：可以由规划设计人员在一定范围内选取的变量。明确了物流系统中可控变量和不可控因素，就能知道加何去影响系统的性能，达到所追求的目标。物流系统的规划一般是通过调整可控变量观察系统性能的变化趋势，从而选择可控变量的最佳匹配，达到系统的最佳效果。物流系统的功能除了受可控变量的影响外，还与不可控因素有密切的关系。通常，不可控因素不是非常确定的。55四.物流系统规划中的变量物流系统规划中的控制因素分为两类65.2物流系统调运规划565.2物流系统调运规划7一.问题描述调运规划问题描述

设某种要调运的物资，有一组供应点(产地或称发点)m个，一组需求点(销地或称收点)n个，如果每个供应点的供应量及每个需求点的需求量都已经确定，即第i个产地有ai单位的物资发出，第j个需求点需要收进bj单位的物资；并且从每—个产地到每一个销地的单位运价是已知的，假定把单位物资从第i个产地调运到第j个销地去的单位运价为cij。调运规划问题也叫运输问题物资调运规划的目的：制订一个合理的调运方案；确定m个产地与n个销地之间的供需联系和数量的最优搭配；确定具体的运输路线，使总的运输费用最低。57一.问题描述调运规划问题描述8二.确定产销地之间的供需联系和收发量1.数学模型设供应点为Ai，该供应点的供应量是ai，（i=1,2,…,m）；设需求点为Bj，该需求点的需求量是bi，（j＝1,2,…,n）；

cij为从第i个供应点到第j个需求点的单位运价；由供应点Ai发往需求点Bj的物资调运量是xij单位。假设m个供应点的总供应量等于n个需求点的总需求量，（这样，调运问题满足供需平衡，称为平衡运输问题）。这时，由各供应点Ai调出的物资总量应等于它的供应量ai(i=1,2,…,m)；而每一个需求点Bj调入的物资总量应等于它的需求量bj(j=1,2,…,n)。目标函数：约束条件58二.确定产销地之间的供需联系和收发量1.数学模型约束条二.确定产销地之间的供需联系和收发量2.模型求解用线性规划方法求解（如单纯形法）。用表上作业法求解（针对这类问题的一种特殊解法）3.表上作业法的主要步骤首先依据问题列出调运物资的供需平衡表以及运价表；其次确定一个初始的调运方案(当然不一定就是最优的方案)；然后根据一个判定法则，判定初始方案是否为最优方案。当判定初始方案不是最优方案时，再对这个方案进行调整。一般情况，每调整一次得到一个新的方案，而这个新方案的运费比前一个方案要少些，如此经过几次调整，就会得到最优方案。59二.确定产销地之间的供需联系和收发量2.模型求解10B1B2B3B4供应量(t)A1311310700A21928400A374105900需求量(t)3006005006002000工地料库运价表5-1某公司物资供应状况表二.确定产销地之间的供需联系和收发量4.表上作业法解题实例例题1某公司下属三个储存某种物资的仓库，供应四个工地的需要。三个仓库的供应量和四个工地的需求量以及由各仓库到各工地调运单位物资的运价(元／吨)由表5—1给出，试求运输费用最少的调运方案。60B1B2B3B4供应量(t)A1311310700A2192解：（1）列出物资调运平衡表和运价表

B1B2B3B4供应量(t)A1700A2400A3900需求量(t)3006005006002000需供运价表5-2供需平衡表表5-3运价表

B1B2B3B4A1311310A21928A374105料库运价工地平衡表中填入的数字表示供需点之间的调运量；空格表示双方不发生调运关系平衡表和运价表是表上作业法的基本资料和运算的依据。表上作业法的实质就是利用运价表在平衡表上进行求解。二.确定产销地之间的供需联系和收发量61解：（1）列出物资调运平衡表和运价表B1B2B3B4供应量（2）编制初始调运方案

物资调运规划其总的目的是寻求一个运输费用最少的最优调运方案。一般最优方案是由初始方案经过反复调整得到的。因此，编制出较好的初始调运方案非常重要。最好的调运方案是使运费最省的方案，因此可以用最小元素法来确定初始调运方案。所谓最小元素法，就是按运价表依次挑选运费少的供——需点尽量优先安排供应的调运方法。二.确定产销地之间的供需联系和收发量62（2）编制初始调运方案物资调运规划其总的目的是寻求一个运输B1B2B3B4供应量(t)A1700A2300400A3900需求量(t)3006005006002000需供运量供需平衡表运价表

B1B2B3B4A1311310A21928A374105料库运价工地1首先，在运价表内找出最小的运价，对本例而言，方格(2，1)数值是1，最小，这样，供应点A2尽可能地满足B1工地的需要，于是在平衡表中有(2，1)＝300，即在空格(2，1)中填入数字300。此时，由于工地B1已经全部得到满足，不需要其他仓库供应给它了，运价表中的第一列数字己不起作用，因此将运价表第一列划去，并标注符号①，63B1B2B3B4供应量(t)A1700A2300400A39B1B2B3B4供应量(t)A1700A2300100400A3900需求量(t)3006005006002000需供运量供需平衡表运价表

B1B2B3B4A1311310A21928A374105料库运价工地12然后，在运价表未划去的各行、列中，再选取一个最小的运价，本例，即(2，3)＝2最小，让A2料库尽量供应满足B3工地的需要。由于A2库储量400t已供应给B1工地300t了，所以最多还能供给B3工地100t。于是在平衡表(2，3)空格填入100；相应地由于仓库A2所储物资已全部供应完毕，因此，在运价表中与A2同行的运价也不再起作用，所以也将它们划去，并标注符号②。64B1B2B3B4供应量(t)A1700A2300100400B1B2B3B4供应量(t)A1400700A2300100400A3600300900需求量(t)3006005006002000需供运价供需平衡表运价表

B1B2B3B4A1311310A21928A374105料库运价工地12435仿照前面的方法，一直作下去，就可得到如左图所示的运价表和平衡表。此时，在运价表中只有方格(1，4)处的运价没有划掉，B4尚有300t的需求，而A1刚好还有300t的物资可以供应，为了满足供需平衡，所以最后在平衡表上应有(1，4)＝300。这样就得到表5—6的初始调运方案。65B1B2B3B4供应量(t)A1400700A2300100B1B2B3B4供应量(t)A1400300700A2300100400A3600300900需求量(t)3006005006002000需供运量表5-6初始调运方案3524根据初始调运方案的运输量和单位运价，可以计算初始调运方案的运输费用为：S=1*300+4*600+3*400+2*100+10*300+5*300=8600(元)110价格运量66B1B2B3B4供应量(t)A1400300700A2300（3）初始方案的检验与调整1）最优方案的数字表征——检验数相关概念

闭回路：对表上作业法的初始方案，从调运方案表上的一个空格出发，存在—条且仅存在一条以该空格(用xij表示)为起点，以其他填有数字的点为其他顶点的闭合回路，简称闭回路。每个顶点都是闭合回路的转角点；闭合回路是一条封闭折线，每一条边都是水平或垂直的；每一行(列)若有闭合回路的顶点，则必有两个（起点所在的行（列）除外）。任一空格的闭合回路不仅是存在的，而且是唯一的。只有从空格出发，其余各转角点所对应的方格内均填有数字时，所构成的闭合回路，才是我们这里所说的闭回路。二.确定产销地之间的供需联系和收发量67（3）初始方案的检验与调整1）最优方案的数字表征——检验数二

空格(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)对所有的空格，都可以用同样的方法画出一条闭回路。B1B2B3B4供应量(t)A1400300700A2300100400A3600300900需求量(t)3006005006002000需供二.确定产销地之间的供需联系和收发量68空格(1，1)：(1，1)—(1，3)—(2，3)—(检验数：调运方案的每个空格所形成的闭回路上，作单位物资的运量调整，总可以计算出相应的运费是增加还是减少。我们把所计算出来的每条闭回路上调整单位运量而使运输费用发生变化的增减值，称其为检验数。如果检验数小于零，表示在该空格的闭回路上调整运量使运费减少；如果检验数大于零，则表示在该空格的闭回路上调整运量会使运费增加。

最优方案的判定准则：初始调运方案中，如果它所有的检验数都是非负的，那么这个初始调运方案一最优。否则。这一调运方案不一定是最优的。

（如果所有空格的检验数都小于零，那么如果再对调运方案进行任何调整，都会增加运输费用）二.确定产销地之间的供需联系和收发量69检验数：调运方案的每个空格所形成的闭回路上，作单位物资的2）用位势法求检验数将初始调运方案中填有运量的方格对应的运价cij分解为两部分，即：cij=ui+vj,(对应前面的例题，i=1,2,3;j=1,2,3,4)其中ui和vj分别为该方格对应于i行和j列的位势量.B1B2B3B4uiA1310U1=2A212U2=1A345U3=-3viv1=0v2=7v3=1v4=8需供C21=u2+v1=1C23=u2+v3=2C13=u1+v3=3……C34=u3+v4=57个未知量，六个方程假定其中一个未知量为0（任意），如假定v1=0,则可以根据左边的方程解出全部未知量。位势计算表第1步：求位势量702）用位势法求检验数将初始调运方案中填有运量的方格对B1B2B3B4uiA1[2][9]310U1=2A21[8]2[9]U2=1A3[-3]4[-2]5U3=-3viv1=0v2=7v3=1v4=8需供准检验数表按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）=u2+v4=1+8=9第2步：求准检验数71B1B2B3B4uiA1[2][9]310U1=2A21[8B1B2B3B4A1[2][9]310A21[8]2[9]A3[-3]4[-2]5第3步：求检验数运价表B1B2B3B4A1311310A21928A374105准检验数表利用运价表与准检验数表求检验数检验数表B1B2B3B4A112A21-1A31012“运价表”减“准检验数表”检验结果：检验数出现负值，根据最优方案判断准则，该方案不是最优方案。72B1B2B3B4A1[2][9]310A21[8]2[9]A3）调整调运方案当判定一个初始调运方案不是最优调运方案时，就要在检验数出现负值的该空格内进行调整。如果检验数是负值的空格不只一个时，一般选择检验数为负值且绝对值最大的空格作为具体的调整对象。X13400+100=500X14300-100=200X23100-100=0X240+100=100

B1B2B3B4A1

400300A2300

100

负A3

600

300调整过程：（1）作出负值所在空格的闭回路，本例为空格x24，闭回路如上图所示。（2）沿闭回路在各奇数次转角点中挑选运量的最小数值作为调整量。本例是将x23方格的100作为调整量，将这个数填入空格x24内，同时调整该闭回路中其他转角点上的运量，使各行、列保持原来的供需平衡．这样使得到一个新的调运方案。733）调整调运方案当判定一个初始调运方案不是最优调运方案时，就B1B2B3B4供应量(t)A1500200700A23000100400A3600300900需求量(t)3006005006002000需供运量调整后的调运方案13524108B1B2B3B4A122A241A3912调整后的检验数通过计算其检验数全部非负，此方案为最优方案。运输费用为：S＝3×500十10×200十8×100十1×300十4×600十5×300＝8500(元)该值小于初始调运方案的总运费。74B1B2B3B4供应量(t)A1500200700A2300(4)表上作业法基本步骤小结①列出调运物资的供需(产销)平衡表及运价表；②按最小元素法建立初始调运方案；③采用位势法计算初始方案每个空格的闭回路的检验数xij；④检查检验数，如果所有xij>=0，说明方案是最优的，已经得到我们想要的方案，结束求解；⑤如果有某个或某几个xij<0，则选择负检验数中绝对值最大的闭回路进行调整，建立新的方案；⑥重复3—5步，直至获得最优调运方案。二.确定产销地之间的供需联系和收发量75(4)表上作业法基本步骤小结①列出调运物资的供需(产销)平衡(5)供需不平衡的物资调运问题通过虚设一个供应点或者需求点，将其转化为平衡运输问题求解。①供应量大于需求量引入一个虚设的需求点，令其的需求量等于实际问题中供应量与需求量之差，令其运价为0。

②需求量大于供应量虚设一个供应点。令这个虚设的供应点的供应量等于实际问题中需求量与供应量的差额，运价为0。

二.确定产销地之间的供需联系和收发量76(5)供需不平衡的物资调运问题通过虚设一个供应点或者需求点，三.运输线路选择运输路线的选择也是物资调运规划的一个重要内容。

运输路线直接影响到运输效果的好坏，关系着物资能否及时运到指定地点。当单位输运输费用是以吨·公里来计算时，运输路线的长短就直接关系着运输费用的多少。本节采用图上作业法来进行运输线路选择。77三.运输线路选择运输路线的选择也是物资调运规划的一个重要内1.交通示意图的表示方法

交通示意图用来表明收发点的大致位置、收发量、交通路线长度的图形。图形表示方法：（1）发点（产地或仓库）用符号表示，里面的数字表示发货量；（2）收点用（需求地）用符号表示，里面的数字表示收货量；（3）两点间的连线为交通线，其长度记在交通线旁边。（4）物资调运的方向(流向)用符号表示，并把按物资调运方向画在交通线的右边，把调运物资的数量记在的右边，并加上括号，以表示和交通线长度区别。201520510物资调运交通流向图20（20）102010（5）（15）（10）三.运输线路选择781.交通示意图的表示方法201520510物资调运交通流向2.图上作业法目的：根据交通流向图，找出运输力量最小的方案。方法：消灭调运中的对流和迂回两种不合理运输。三.运输线路选择792.图上作业法三.运输线路选择30（1）对流

即同一物资在同一线路上的往返运输。

如下面的图，将某物资10吨，从A1运到B2，而又有同样的物资10吨，在同一期间从A2运到B1，于是A1A2间就出现了对流现象。

10101030304030（10）（10）A1A2B1B2

如果从图上看，对流可以理解为同一条交通线上，有两条或两条以上的物资调运方向。10101030304030（10）A1A2B1B2（10）消除对流运力：30*10+20*10=600运力：30*10+40*10+40*10+30*10=1400三.运输线路选择80（1）对流10101030304030（10）（10）A（2）迂回

迂回：在交通图成圈的时候，如果流向图中内圈流向的总长(简称内流长)或外圈流向的总长(简称外流长)超过整个圈长的—半，就称为迂回运输。

内、外圈的概念：由于表示调运方向的箭头，要按调运方向，画在交通线的右边，因此,流向图中，有些流向就在圈外，称为外圈流向；有些流向在圈内，称为内圈流向。556千米AB（5吨）4千米556千米AB（5吨）4千米迂回运输无迂回运输迂回运输：运力6*5=30吨.千米无迂回运输：运力4*5=20吨.千米三.运输线路选择81（2）迂回556千米AB（5吨）4千米556千米A例题，下图为一运输交通图该交通图的运输线路构成圈。圈的总长=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=1010303050243（20）A1B2A24B1（30）（10）10303050243（30）A1B2A24（20）（10）修改三.运输线路选择82例题，下图为一运输交通图该交通图的运输线路构成圈。10303物资调运问题的图上作业法消除运输过程中的对流和迂回，节省运输力量。具体步骤：先画出一个没有对流的运输方案.再检查有没有迂回，如果没有迂回，这方案就是最优方案；如果有迂回，则对方案进行调整，直至消除迂回现象为止。在实际的物资调运中，运输线路可以分为两种情况：交通线路成圈交通线路不成圈三.运输线路选择83物资调运问题的图上作业法三.运输线路选择343.交通路线不成圈例题3有某物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7(万吨)，运往B1，B2，B3，B4，收量分别为8，1，3，5(万吨)，收发量平衡，交通路线如图5—8所示，问应如何调运，才使运输吨．千米最小？558（5）A1B127313A2A3A4B2B3B4558A1B127313A2A3A4B2B3B4交通线路图调运流向图解：该交通线路不成圈，只需要做一没有对流的调运图。方法：从各端点开始，由外到里，逐步进行各收发点之间的平衡（2）（1）（2）（1）（7）（5）843.交通路线不成圈例题3有某物资17万吨，由A1，A4.交通路线成圈例题4有某物资7万吨，由A1，A2，A3发出，发量分别为3，3，1(万吨)，运往B1，B2，B3，B4，收量分别为2，3，1，1(万吨)，收发量平衡，交通路线如图5—10所示，问应如何调运，才使运输吨．千米最小？113334B4A3213A1A2B1B3B2754324854.交通路线成圈例题4113334B4A3213A1A113334B4A3213A1A2B1B3B2754324解:(1)作一个没有对流的流向图。方法：用“去线破圈”的方法。去一线破一圈，有几个圈去掉几条线，把有圈的交通图，转化为不成圈的交通图。技巧：一般先去掉长度最长的交通线，比如本例中去掉A1B4(7千米)，破A1B1B2A3B4圈；再去掉A3B3线(4千米)，破B2A2B3A3圈。这样，原来有圈的交通图，变成了不成圈的交通图．如图5—11所示。从各个端点开始，做一个没有对流的流向图113334B4A3213A1A2B1B3B2754324（1）（3）（1）（2）（1）86113334B4A3213A1A2B1B3B2754324解

(2)检查有无迂回。

方法：对流向图中的各圈进行检查，如果没有迂回，则这个初始方案就是最优方案，如果其中某圈中有迂回，则不是最优方案，需要改进。113334B4A3213A1B1B3B2754324（1）（3）（1）（2）（1）A1B1B2A3B4总圈长=7+3+4+4+5=23外流长=5+4+3=12存在迂回，需要调整。B2A2B3A3总圈长=4+3+2+4=13内流长=3外流长=2不存在迂回，不需要调整A287(2)检查有无迂回。

方法：对流向图中的各圈进行检查，113334B4A3213A1B1B3B2754324（1）（3）（1）（2）A2调整方法：1）在外圈的各流量中，减去外圈的最小流量1万吨；2）在内圈的各流量中加上1万吨，在此圈中，因无内流量，故不加。3）在无流量的线路上，新添加内圈流量1万吨。（-1）（-1）（-1）（+1）（+1）（1）88113334B4A3213A1B1B3B2754324（1）113334B4A3213A1B1B3B2754324（2）（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）89113334B4A3213A1B1B3B2754324（2）四.最短路与最大流

1.最短路线例题5某家运输公司签定了一项运输合同，要把A市的一批货物运送到B市。该公司根据两个城市之间可选择的行车路线地图，绘制了图5—13的公路网络。要求从交通网络图中，寻找一条线路最短的运输路线。1A市4523769810B市1001501753002