模块二 运 输 问 题之表上作业法内容提要 运输问题模型的特点 产销平衡运输问题的表上作业法 产销不平衡运输问题的转化 表上作业法在物流管理中的典型应用CHAPTER 运输管理是物流管理中重要的环节之一， 物流企业的物流成本中，运输与配送管理的成 本比重约占80%左右。因此，合理的优化配送路径不仅可以简化 配送程序、减少配送频率，而且更重要的是可 以降低配送费用，从而带来更大的效益，因此 调运物资配送方案的优化选择引起了各界人士 注意。运 输 问 题物流配送方式在物流管理过程中，组织物流配送与运输 工作应该以及时、准确、经济、安全为原则。 配送与运输方式有：铁路、公路、水路、航空 、管道等。问题提出：问题提出：表销销地 产产地 B1 B2 B3 B4 产产 量 A1 3113107 A2 19284 A3 741059销销 量 3656 20 20 求解此类问题可用“表上作业法”在求解之前了解一下运输问题中的一些概念2.1 2.1 运输问题模型运输问题模型对某种物资，其计量单位可以是重量、包括单 位或其他。设有m个产地A1, A2, , Am，称它们为发 点，其对应产量为a1, a2, , am，称它们为产量；另 有n个销地B1, B2, , Bn，称它们为收点，其对应销 量为b1, b2, , bn，称它们为销量。又知，从产地（ 发点）Ai运至销地（收点）Bj，该种物资每单位的 运价为ci j（ci j0）。试问：应如何安排调运方案，在满足一定要求 的前提下，使总运费最低？ 2.1 2.1 运输问题模型运输问题模型根据上述参量的意义列出产销运价，如下表表2.3 产销运价表 销销地 产产地 B1 B2 Bn 产产量 A1 c11 c12 c1n a1 A2 c21 c22 c2n a2 Am cm1 cm2 cmn am 销销量 b1 b2 bn aibj 2.1 2.1 运输问题模型运输问题模型表的右下角 ai表示各产地产量的总和，即 总产量或总发量； bj表示各销地销量的总和， 即总销量或总收量。这里有两种可能： （1） ai bj（总产量总销量），即产销平衡 问题。 （2） ai bj（总产量总销量），即产销不 平衡问题。它又可分为两种情况：产大于销， 即 ai bj ；销大于产，即 ai bj。下面先讨论产销平衡问题，再讨论产销不 平衡问题。 2.1 2.1 运输问题模型运输问题模型令xij表示某物资从发点Ai到收点Bj的调拨量（运 输量），可以列出产销平衡表如表2.4所示。表2.4 产销平衡表 销 地 产 地 B1 B2 Bn 产 量 A1 x11 x12 x1n a1 A2 x21 x22 x2n a2 Am xm1 xm2 xmn am 销量 b1 b2 bn aibj 2.1 2.1 运输问题模型运输问题模型将产销运价表2.3和产销平衡表2.4两个表合在一起，得到 的一个新表，被称为运输表（或称为产销矩阵表），如 表2.5所示。表2.5 运输表（产销矩阵表） 销地 产地 B1 B2 Bn 产量 A1 x11 c11 x12 c12 x1n c1n a1 A2 x21 c21 x22 c22 x2n c2n a2 Am xm1 cm1 xm2 cm2 xmn cmn am 销量 b1 b2 bn ai bj 转化为求费用最小的数学模 型。2.1 2.1 运输问题模型运输问题模型求上述总运费最小问题就等于求下面数学模型的 解，即求：xij（i1, 2, , m；j1, 2, , n）（2-1） 2.1 2.1 运输问题模型运输问题模型约束条件个数减 去线性相关的 条件个数2.2 2.2 运输问题的表上作业法运输问题的表上作业法 我国数学家研究出在表上进行分析、计 算、判断的解决“一批物资从几个生产地供 应给若干个消费地，各地产量和销量都是 已知的，各地运费也已知，如何调运才能 使总运费（货总吨公里数）最小”的问题的 方法（即表上作业法）。2.2.12.2.1产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法的基本计算步骤： 1. 编制产销运价表（或运费表和产销平衡表）； 2. 根据产销平衡表和运价表编制出可行的初始调运 方案；（最小元素法、Vogel法） 3. 判断初始方案是否最好，若不是最好的，则在初始方 案的基础上进行调整。通常每调整一次所得到的新方案（基本可行解 ）就比原方案好一些，经过若干次调整，最后必能 得到最好的调运方案（最优解）。2.2.12.2.1产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法解（1）根据题意编制产销运价表 表2.6 产销运价表 单位：吨， 万元 /吨销销地 产产地 B1 B2 B3 B4 产产 量 A1 3113107 A2 19284 A3 741059销销 量 3656 20 20 2.2.12.2.1产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法示例示例2.2.12.2.1产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法示例示例（2）编制初始方案： 初始方案确定的方法一：最小元素法。 最小元素法的基本思想就是就近供应，即从 单位运价表中最小的运价处开始确定供销关系； 当需求已得到满足或产量已分配完毕，将此列或 此行划去；然后从剩下的运价中找最小元素确定 供销关系，依此类推，直到所有的元素都划去， 得出全部方案为止。 2.2.12.2.1产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法示例示例解（2）将用最小元素法得到的初始调运方案显示于下图 表2.7 调运方案表2.2.12.2.1产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法示例示例2.2.12.2.1产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法示例示例2.2.12.2.1产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法示例示例2.2.12.2.1产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法示例示例2.8 初始调运方案表但此方案是否为最优呢？需 要对方案进行检验！2.2.12.2.1产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法说明：一般调运方案表每填一个数，划去单位运价表中的一行 或一列。但往往出现下述情况，选定的最小元素所在行的产 量等于所在列销量，这时在产销平衡表上填一个数，运价表 上就要同事划去一行和一列。为了使调运方案中的有数字格 仍为m+n-1个，需要在同时划去的该行或该列的任一空格处 补填一个“0”。产销平衡问题表上作业法内容回顾产销平衡问题表上作业法内容回顾最小元素法编制初始方案： 1、编制产销运价表； 2、从产销运价表中最小元素处开始找初始方案； 3、检验方案是否最优（未学习）最小元素法的基本思想。 就近供应，即从单位运价表中最小的运价处开始确定 供销关系；当需求已得到满足或产量已分配完毕，将此列 或此行划去；然后从剩下的运价中找最小元素确定供销关 系，依此类推，直到所有的元素都划去，得出全部方案为 止。 2.2.22.2.2产销平衡运输问题的产销平衡运输问题的Vogel表上作业表上作业 法法 （2）编制初始方案： 初始方案确定的方法二： Vogel法（沃格尔法 ） 。 Vogel法的步骤是：从运价表上分别找出每行 与每列的最小的两个元素之差，再从差值最大的 行或列中找出最小运价确定供需关系和供应数量 。当产地或销地中有一方数量上供应完毕或得到 满足时，划去运价表中对应的行或列；然后从剩 下的元素中找出每行每列的最小元素之差，依次 重复上述步骤直到找出初始方案。仍以上面仍以上面2.12.1例子来说明用例子来说明用vogelvogel法编制初始方案法编制初始方案步骤（步骤（2 2）2.2.22.2.2产销平衡运输问题的产销平衡运输问题的Vogel表上作业表上作业 法法用Vogel法求解初始调运方案总运费75万元。哪个是最优的？或者都不是，如何进行最优检验呢？2.2.22.2.2产销平衡运输问题的产销平衡运输问题的Vogel表上作业法表上作业法2.32.3产销平衡运输问题表上作业法的产销平衡运输问题表上作业法的检验检验通过计算各空格处的检验数来对初始方案进行检验。一、闭回路法通过构造闭回路计算各空格处的检验数，根据检验数是否全部非负来判断方案是否最优。二、位势法通过构造闭回路计算各空格处的检验数，根据检验数是否全部非负来判断方案是否最优。2.32.3产销平衡运输问题表上作业法的产销平衡运输问题表上作业法的检验检验2.32.3产销平衡运输问题表上作业法的产销平衡运输问题表上作业法的检验检验2.32.3产销平衡运输问题表上作业法的产销平衡运输问题表上作业法的检验检验2.32.3产销平衡运输问题表上作业法的产销平衡运输问题表上作业法的检验检验2.32.3产销平衡运输问题表上作业法的产销平衡运输问题表上作业法的检验检验此方法计算检验数较麻烦！方案的调整：思路：尽量增加检验数为负值格的运量（当有两个以上负的检验数时，从绝对值大的负检验数出发）。步骤：一、找出检验数为负数格所在的闭回路中二、尽量增加检验数为负值格的运量，减小其闭回路中 相邻格的运量。得到新的调运方案。注意：其中运量的增加、减小量是闭回路中最小的运量调整后的方案是否最优，需进一步计算检 验数对方案进行检验。！2.32.3产销平衡运输问题表上作业法的产销平衡运输问题表上作业法的检验检验2.32.3产销平衡运输问题表上作业法的产销平衡运输问题表上作业法的检验检验2.32.3产销平衡运输问题表上作业法的产销平衡运输问题表上作业法的检验检验若检验数全非负，则方案为最有；若检验数有负值 ，则需要对方案进行调整。2.32.3产销平衡运输问题表上作业法的产销平衡运输问题表上作业法的检验检验2.42.4产销平衡运输问题表上作业法小结产销平衡运输问题表上作业法小结最小元素法编制初始方案的步骤如下。 （1）编制产销运价表 （2）从运价表中的最小元素出发确定供需关系 和供需量，依次进行下去找出初始方案。 （3）求检验数。 （4）若检验数不全大于0，则调整方案。2.42.4产销平衡运输问题表上作业法小结产销平衡运输问题表上作业法小结vogel法编制初始方案的步骤如下。 （1）编制产销运价表 （2）计算运价表中每行、每列最小的两个元素 的差值，从最大的差值对应的行、列中找最小 的元素处确定供需关系。依次进行下去找出初 始方案。 （3）求检验数。 （4）若检验数不全大于0，则调整方案。2.52.5产销不平衡运输问题表上作业法产销不平衡运输问题表上作业法2.52.5产销不平衡运输问题表上作业法产销不平衡运输问题表上作业法此例表中A1，A2，A3的总发量为19t，B1，B2，B3，B4的总收 量为15t，总发量比总收量多出4t，不论怎样，总库存量都是4t ，这是不变的。这样，我们就表中收点处增加一列库存，同时 运费表中也增加一列都是零的运费，如表2-31所示。2.52.5产销不平衡运输问题表上作业法产销不平衡运输问题表上作业法2.52.5产销不平衡运输问题表上作业法产销不平衡运输问题表上作业法2.52.5产销不平衡运输问题表上作业法产销不平衡运输问题表上作业法分析：分析：1、对于求最大值问题，用什么方法求初始方案？用于求最小化问题的最小元素法与vogel法是否 可以用来求最大化问题？2、对初始方案检验的方法与判别方案最优的准则是什 么？思考：1、求最大值问题，用最小（最大