运输问题表上作业法改进思路研究论述

摘 要：运输问题的表上作业法是求解运输问题的重要方法，实质是一种单纯形法，其中，运输问题的基本性质对运输问题表上作业法的改进有着重要的意义。但是，在实际的表上作业法运作中对运输问题的性质分析不够，经过有关人员的分析，提出了最小元素法给出的初始方案是解决运输问题的可行性操作，同时，也解决了运输问题的退化情况。文章通过对运输问题表作业法现状的分析，对经典表上作业法的阐释，结合运输问题的性质，对运输问题表上作业法求解初始解方法以及调运检验方案的调整两个方面的改进思路进行研究。

关键词：运输问题；表上作业法；改进思路

随着我国经济的发展，物流业也得到了快速的发展，在我国经济活动中发挥了重要的作用。物流业的发展对交通运输问题提出了更高的要求，在此情况下，运输问题中引用了一门现代学科中的运筹学。运筹学是指利用数学的手段对所需要处理的问题进行规划和分析，最终实现对问题的最优化解决。其中，应用到运输问题中的是运筹学中线性规划方面的表上作业法。表上作业法是在一些线性规划问题采用图上作业难以直观规划的情况下，通过各元素的排列组成表格，并将表格作为一种初始方案，在此基础上利用闭合回路法、位势法获取检验数来对方案检验，最终获得最优化的解决办法。

1 运输问题性质、现状及表上作业法现状

1.1 运输问题的性质

运输问题中的运输表中行列、数列会随着相异变量的延伸而进行改变，变量序列之间形成了一种闭合路。运输问题的系数矩阵及其增广矩阵的秩均为m+n-1。其中，运输问题中的变量列向的充要条件不包括闭合路。在对运输问题求解时，主要采用最小元素法的原理，通过对初始方案的确定来实现可行解。

1.2 运输问题研究现状

随着交通运输事业的发展，物资配送问题的求解引起了有关人员的关注。运输问题是一种特殊的线性规划形式，在上个世纪四十年代的时候，苏联数学家提出了一种线性的运输规划方法，是一种基于线性约束的基础上关于目标函数极大、极小值的数学理论，具有非常重要的现实意义。运输问题的规划发生了由单目标运输向多目标运输的转变，很多学者也相继采取不同的算法来解决多目标的优化问题。国内的运输问题研究较晚，关键是研究是通过寻找最小让步值来获得目标冲突的解决和优化，将多目标运输问题转为单目标运输问题，主要采用表上作业法的形式来进行求解。

1.3 表上作业法研究现状

表上作业法是指在平衡表中进行求解，是一种经典的求解单目标运输问题的较为成熟的求解方法，具有简单、易操作的优势。现阶段的国内表上作业法研究较少，因此，需要有关人员通过对运输问题的分析，针对表上作业法效率的提高和改进等方面，进行方案的研究，从而提高运输的效率。

2 经典的运输问题表上作业法原理

表上作业法是求解交通运输问题的经典算法，主要的步骤是将问题转化在供求平衡表中来实现求解。首先要先确定初始解，然后按照一定规则进行初始方案的调整和改进得到新解，再对新解进行改进，直到寻求到最优方案。

2.1 初始解

初始解的确定能够影响后期方案的更迭，其简单易行能够减少方案的更迭，具有重要的现实意义。初始解的设定具体步骤如下：首先，在供需平衡表中选取单元格，令xij=min{ai，bj}使行或列在允许的范围内尽量饱和，即使一个约束方程得以满足。之后调整横列和数列的供应量，当ai=0时，删掉相应的行，bj=0时，删掉相应的列，在运输量选定的时候实现行、列的满足，实现运输问题的初始基本可行解。

2.2 求解初始解的方法

2.2.1 最小元素法。最小元素法是指在交通运输的物流配送中，实现每次配送路径单位运价的最小化。通过找出运价表中的最小元素，在运量表内填入允许范围内的最大数，如果某列的产量或者销量已经满足，则要将该运价所在的行或者列划去最小值，从而得到可行解的方法。

2.2.2 西北角法。西北角法是运筹学中制定运输问题的求解初始解的基本方法之一，是指从运价表的西北角开始依次安排多个产地和多个销售地之间的运输业务，从而得到可行解的方法。西北角的运输应用遵循优先安排运价表上标号最小产地和销售地之间的运输原则。

2.2.3 伏格尔法。伏格尔法又叫做差值法，是指在不能按照最小运费供应的产地进行次小运费的使用，在运费之间的差额最大处进行最小运费的调运。以差值法确定的初始方案作为解决运输问题的最优解，能够有效减少迭代次数，从而削减不必要的计算工作量，甚至还会直接实现最优解的目标，但这种方法会造成为了节约某处的运费而无形中增大其他运费的弊端。

3 运输问题表上作业法中求解初始法的改进

求解初始解的方法中差值法是最实用的一种方法，能够最快速度获得最优解的近似值，减少迭代次数，提高工作效率。但是差值法由于没有实现和单位运价的联系，不能每次都实现无需调运方案的调整直接获得最优解的近似值。因此，需要对运输问题表上作业法中最为常用的求解初始法进行改进。比如在进行变量的确定时不仅要考虑变量单位的绝对值，还要考虑变量的可调运量，在调配的开始阶段要对中次小元素和最小元素之间的运费差进行计算，然后在最大差额的行中以最小元素作为基本量，同时，可以不必对竖行进行计算。

差值法中求解初始法的改进要遵循以下几方面的原则：首先，当行列的元素可调运量大于等于最小元素的可调运量时，运费差要等于最小元素的可调运量和行列的元素以及最小元素运价差相乘的结果。其次，当行列的元素可调运量小于最小元素的可调运量时，运费差通常要由两部分组成。

4 运输问题表上作业法中调运方案的检验调整

调运方案的检验是在运输问题三种求解初始法可行解的基础上经过最优性检验来进一步对目标函數值的判断。通过这种检验能够发现当前方案是否实现了最优，比如当所有的检验数在大于等于零的时候就是获得了检验的最优解。常见的判断最优解的方法主要有闭回路法和位势法两种。闭回路法是指在平衡表中的一个空格和多个有数字格的用水平和垂直连线包围而成的封闭回路。位势法是将运价分解为行位势量ui与列位势量vj，再通过位势量的计算得出检验数的检验方法。

闭回路法和位势法在实际的运输问题优化调整中，都需要对空栏的检验数进行计算，这种计算过程较为复杂，影响了实际应用效果。因此，借助水往低处流的规律，提出了流水原理求解的运输问题。流水原理求解解决了传统闭回路法和位势法求解中出现的退化问题，当基本可行解的一个或者多个分量出现零时，可以采用加零的方法来解决退化问题。利用流水原理的可行解减少了不必要的检验数的计算，简化了检验方法，优化了调配的运输问题，具有很重要的实际应用价值。

5 结束语

运输问题的表上作业法是一个较为简便的计算方法，差值法的求解初始法虽然具有一定的现实意义，但是其使用也不能实现对最优解的快速获得，同时，传统运输问题的调运方案的检验也存在较为复杂的问题。因此，有关人员需要在不断提升个人技能的基础上加强对运输问题表上作业法求解初始法和调运方案检验等方面的改进，从而有效减少运输问题表上作业法的工作量，实现运输问题最优解的快速获得。

参考文献

[1]李时椿.运输问题表上作业法的改进研究[J].南京航空航天大学学报，2000，3：324-329.

[2]蒋宏峰.运输问题表上作业法的改进[J].长沙大学学报，2002，2：47-48.

[3]刘大为，张方华.运输问题表上作业法的改进[J].科技资讯，2008，12：248-249.

作者简介：邢建平（1974，7-），女，出生湖南益阳人，硕士，湖南广播电视大学副教授，研究方向：应用数学。