用表上作业法求解简单物流运输问题

1、用表上作业法求解简单物流运输问题物流管理的本质要求就是求实效， 即以最少的消耗， 实现 最优的服务，达到最佳的经济效益。搞好物流管理，可以通过合 理的运输方案，使中间装卸搬运、储存费用降低、损失减少，在 其他条件不变的情况下， 降低物流成本就意味着扩大了企业的利 润空间， 提高了利润水平， 所以一个合理的运输方案有着重要的 意义。运输问题是线性规划的一种特殊形式， 运输问题主要是解决 这样的问题：在大宗物资调运时，有若干个产地，根据已知的运 输交通网，如何制定一个运输方案， 将这些物资运到各个销售地， 使得总运费最小。 运输问题模型提出后， 人们对其求解的方法进 行了大量的研究，并有了重大成果

2、，其中 Danzig 的表上作业法 是最简单和最常用的， 表上作业法本质就是单纯形法。 本文通过 对物流运输问题模型的分析， 讲解了表上作业法的求解过程， 并 进行实际操作。 1 运输问题的提出运输问题发展于线性规划问题， 属于线性函数在约束条件下 的最优化问题，在 1940 年 Hitchcock 提出运输问题。运输问题 属于线性规划问题的特殊情况， 既有线性规划问题的共性， 也有 自身的特点和算法。运输问题提出后， 1958 年 Kantorovich 对 运输问题做了早期的研究。1.1 运输问题的数学模型有m个供应点向n个需求点供应某种物资，这 m个供应点A1、A2、Am的供应量分别为

3、al、a2、am； n个需 求点B1、B2、Bn的需求量分别为 bl、b2、bn ;已 知从任一供应点 Ai 向任一需求点 Bj 运输一个单位物资的费用为 cij 。问采取什么样的物资调运方案才能使总运费最省？表 1-1 供求量及单位运价表销地产地 B1 B2 Bn 供应量A1 c11 c12 c1n a1A2 c21 c22 c2n a2Am cm1 cm2 cmn am需求量 b1 b2 bn建立数学模型为：（1）当时，即运输问题的总产量等于其总销量，这样的运 输问题称为产销平衡的运输问题。（2）当时，即运输问题的总产量不等于总销量，这样的运 输问题称为产销不平衡的运输问题。1.2 产销平

4、衡的运输问题的数学模型当时，即为产销平衡的运输问题，此时数学模型可化为：为了方便计算，只考虑产销平衡的情况；产销不平衡时，增 加虚拟的产销地及产量使其变为产销平衡的问题进行求解。1.3 运输问题数学模型的特点(1) 数学模型中有mn个决策变量，有(m+r)个约束条件；( 2)数学模型一定有最优解，且有有限个最优解；( 3)数学模型的系数矩阵为：(4)系数矩阵中元素只有1和0,且前m行有且仅有n个1, 其余为0,后n行有且仅有m个1,其余为0;每列有且仅有2 个 1 ，其余为 0。 2 表上作业法 表上作业法是指用列表的方法求解运输问题的计算方法, 是 线性规划一种求解方法, 其本质同单纯形法一

5、样。 首先要确定一 个初始调运方案, 不要求是最优的, 主要希望求解方法简便可行, 最常见的是西北角法、 最小元素法和 Vogel 法。然后采用检验数 来验证这个方案, 常用的方法是闭回路法和位势法, 若是最优方 案则计算结束, 否则就要用闭合回路法进行调整, 直至得到满意 的结果。这种列表求解方法就是表上作业法。2.1 表上作业法的求解步骤( 1 )建立产销平衡表,确定初始调运方案,常用的方法有 最小元素法、西北角法、 Vogel 法等；( 2)现行方案的最优性检验,常用方法有闭回路法,位势 法,计算出检验数,从而判别方案是否最优；( 3)现行方案的调整,即从当前方案出发去寻找另一个更好的调

6、运方案，常用的方法是闭回路法；（4）重复 2）、 3）步骤，直到得出最优调运方案为止。2.2 确定初始调运方案2.2.1 西北角法 西北角法是制定运输问题的初始调运方案（即初始基可行 解）的基本方法之一。 是从产销平衡表的西北角位置开始分配调 运量，依次安排m个产地和n个销地之间的运输业务， 从而得到 一个初始调运方案的方法。 西北角法遵循“优先安排产销平衡表 上编号最小的产地和销地之间的运输业务”的规则。 其操作步骤 如下：（1）建立产销平衡表，取表的西北角方格分配调运量，并 使其尽可能的大；（2）将西北角方格所对应的产销量均减去分配量，得到新 的产销量；（3）当新产销量为 0 时，划去其所

7、对应的行或者列；（4）重新选取表的西北角方格分配调运量，直至产销量分 配平衡为止。2.2.2 最小元素法 最小元素法是找出产销平衡表中最小的元素 （所谓元素就是 单位运价）所对应的方格，给此方格分配调运量，并使其尽可能 的大，若某行（列）的产量（销量）已满足，则把运价表中该运 价所在行（列）划去；找出未划去的产销平衡表中的最小元素所对应的方格，给其分配调运量，按此办法进行下去，直至得到一 个分配平衡为止。其操作步骤如下：（1）建立产销平衡表，取表中最小单位运价的方格分配调 运量，并使其尽可能的大；（2）将最小单位运价方格所对应的产销量均减去分配量， 得到新的产销量；（3）当新产销量为 0 时，

8、划去其所对应的行或者列；（4）重新选取表中最小单位运价的方格分配调运量，直至 产销量分配平衡为止。2.2.3Vogel 法最小元素法的缺点是， 为了节约一处的费用， 有时造成在其 他处要多花几倍的运费。伏格尔法又称差额法，该方法考虑到， 某产地的产品如不能按最小运费就近供应， 就考虑次小运费， 这 就有一个差额。差额越大，说明不能按最小运费调运时，运费增 加越多。因而对差额最大处，就应当采用最小运费调运。其操作 步骤如下：（ 1）建立产销平衡表，算出各行各列中最小元素和次小元素的差额， 并标出最大的差额 （若几个差额同为最 大，则可任取其一）；（2）取最大差额所对应行或列中的最小元素方格开始分

9、配 调运量，并使其尽可能的大；（3）将最小元素方格所对应的产销量均减去分配量，得到 新的产销量；（4）当新产销量为 0 时，划去其所对应的行或者列；（5）重新计算行差额和列差额，取最大差额所对应行或列 中的最小元素方格开始分配调运量，直至产销量分配平衡为止。2.3 现行方案的最优性检验2.3.1 闭回路法 所谓闭回路是在已给出的调运方案的运输表上从一个代表 非基变量的空格出发， 沿水平或垂直方向前进， 只有遇到代表基 变量的填入数字的格才能向左或右转 90 度（当然也可以不改变 方向）继续前进，这样继续下去，直至回到出发的那个空格，由 此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。闭回

10、路的特点：1）每行每列最多只有两个顶点；2）每一段折线都是水平或者垂直的；3）回路的转角点必须是一个基变量；4）每个非基变量有且仅有一条闭回路，与其方向无关。 所谓闭回路法， 就是对于代表非基变量的空格 （其调运量为 零），把它的调运量调整为 1，由于产销平衡的要求，我们必须 对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。 如果所 有代表非基变量的空格的检验数也即非基变量的检验数都大于 等于零，则已求得最优解，否则继续迭代找出最优解。2.3.2 位势法所谓位势法，我们对运输表上的每一行赋予一个数值 ui ， 对每一列赋予一个数值 vj ，它们的数值是由基变量 xij 的检验 数 所决定的，则非基变量 xij 的检验数就可以用公式求出。2.4 现行方案的调整在进行最优解检验时， 出现负检验数， 表明没有得出最优解， 方案需要进行改进， 常用的改进方法是闭回路调整法。 闭回路调