陈海伟，陶庆玲

(商丘工学院管理学院，河南商丘 476000)

表上作业法在有转运的物资运输问题中的应用

陈海伟，陶庆玲

(商丘工学院管理学院，河南商丘 476000)

讨论了产销平衡运输问题的表上作业法，利用Vogel法求初始方案，位势法求检验数，闭回路法对可行解进行调整和改进.提出了带有转运的物资运输问题的求解方法，将所有产地、中间转运站、销地都可以看做产地，又可看做销地，把整个问题当做一个扩大的运输问题处理.

表上作业法;Vogel法;位势法;检验数

1 运输问题的数学模型［1］

产销平衡问题的数学模型为

这是一个线性规划问题，可以用单纯形法来求解运输问题.如果用单纯形法来解运输问题，就要在每个约束条件中加入一个人工变量，即使对于m=3，n=4这样如此简单的运输问题，变量数目也有19个，运算量非常大，因此一般使用简单有效的表上作业法.

2 表上作业法在运输问题中的应用

表上作业法的求解工作是在运输表上进行的一种迭代法，迭代步骤为:先找出一个初始可行解，然后对初始可行解做最优性检验，如果不是最优解，就在运输表上对它进行调整和改进，得到一个新的可行解，再进行判别和改进，直至得到最优解为止.

2.1初始可行解的确定［2］

常用的初始可行解的确定方法有3种:西北角法、最小元素法和Vogel法.通常情况下，用Vogel法确定的初始解质量最好，最接近最优解，最小元素法次之，西北角法最差.所以常用Vogel法来确定初始可行解，步骤如下:

(1)计算运输表中每一行和每一列次小单位运价和最小单位运价之间的差值，称之为相应的行罚数和列罚数，圈出其中的最大罚数;

(2)若同时出现两个以上的最大罚数，则圈出其所在行或所在列的最小运价为最小者的最大罚数;

(3)根据最大罚数值的位置在运输表中的适当格中填入一个尽可能大的运输量，并划去相应的一行或一列;

(4)当运输问题某部分的产量和销量相等时，在运输表中相应空格处填入运量，需同时划去运输表的一行和一列，这时最终运输表上的数字格就会小于m+n－1，为使迭代工作顺利进行，规定只能划去一行(或一列)，在未被划去的一行或一列的某个空格中填入数字0;

(5)重复以上步骤，从而得到一个初始可行解.

2.2 解的最优性检验

对初始可行解的最优性检验可仿照单纯形法，求可行解的各非基变量的检验数.若有某空格(Ai，Bj)的检验数σij为负，说明将xij作为基变量会使总运费减少，故当前解不是最优解，需要调整.若所有空格的检验数全部非负，则不管怎样调整都不会使总的运输费用降低，该可行解就是最优解，所对应的调运方案为最优方案.

求检验数的常用方法有两种:位势法和闭回路法，其中利用位势法求检验数相对来说运算量比较小.根据线性规划的对偶规划矩阵描述，运输问题xij的检验数σij=cij－(ui+vj)，cij、ui、vj分别为xij所在空格的单位运价及空格所在行的行位势和所在列的列位势.对于运输问题的一个初始可行解，其基变量是xi1j1，xi2j2，…，xisjs，s=m+n－1，得方程组

2.3 解的调整和改进［3］

若经过最优性检验，可行解不是最优解，则需要进一步改进.改进的方法是在运输表中做出最小负检验数对应空格的闭回路Lij，在满足约束条件的前提下，使xij尽可能增大并相应调整闭回路上其他顶点处的运量，得到一个更好的可行解.解调整改进的步骤如下.

(1)在运输表中做出最小负检验数δij对应空格的闭回路; (2)以空格(Ai，Bj)为初始点，沿顺时针方向依次对闭回路上的顶点进行编号;

(5)对得到的新可行解进行最优性检验，如不是最优解，重复以上步骤进行调整和改进，直到得出最优解为止.

例1某公司从3个产地A1、A2、A3将物品运往4个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表1所示，问如何调运，可使得总运输费最低?

解(1)Vogel法求初始方案，见表2.

表1 运输费用表Tab.1Transport freight list

表2 运输问题的初始方案Tab.2Initial solution for transportation problem

(2)用位势法求检验数，见表3.

表3 检验数Tab.3Test number

由表3可知，u1+v3=c13=3，u1+v4=c14=10，u2+v1=c21=1，u2+v4=c24=8，u3+v2=c32=4，u3+v4=c34=5，得

再用σij=cij－(ui+vj)求非基变量检验数δ11=0，σ12=2，σ22=2，σ23=1，σ31=9，σ33=12.

所有的非基变量检验数非负，所以方案最优.

3 有转运的运输问题

在上述讨论中，我们假定物品由产地直接运到销地，不经中间转运，这是一种理想的情况，而实际上往往是先将物品由产地运到某个中转站(可以是另外的产地、销地或中间转运仓库)，然后再转运到销售地.假定有m个产地A1，A2，…，Am，n个销地B1，B2，…，Bn，产地和销地都可以作为中转站使用，物品的产地和销地都有m+n个，这就成为一个扩大了的运输问题.定义以下符号:ai为第i个产地的产量(净供应量)，bj为第j个销地的销量(净需求量)，cij为由第i个发送地运到第j个接收地的单位运价，xij为由第i个发送地运到第j个接收地的物品数量，ci为第i个地点转运单位物品的费用.

将产地和销地统一编号，并把产地排在前面，销地排在后面，则有

例2已知各产地、销地、中间转运站及相互之间每吨产品的运价如表5所示，则在考虑产销地之间直接运输和非直接运输各种可能方案的情况下，如何将3个厂每天生产的产品运往销售地，使总的运费最少.

表5 带有转运运输问题的运输表Tab.5The transport table of transportation problem with transshipment

解(1)由于问题中所有产地、中间转运站、销地都可以看做产地，又可看做销地，因此把整个问题当做有11个产地和11个销地的扩大的运输问题.

(2)对扩大的运输问题建立单位运价表.将表中不可能出现的运输方案的运价用任意大的正数M代替.

(3)所有中间转运站的产量等于销量.运费最少时不可能出现一批物资来回倒运的现象，所以每个转运站的转运数不超过20 t.

(4)规定T1，T2，T3，T4的产量和销量均为20 t.

然后用表上作业法求解(见表6)即可.

表6 扩大的运输问题的单位运价表Tab.6The unit price table of expanded transportation problem

［1］胡运权.运筹学教程［M］.3版.北京:清华大学出版社，2007:80－94.

［2］谢凡荣.产销平衡运输问题的表上作业法解法的一个注记［J］.运筹与管理，2005，14(4):44－46.

［3］何莉敏，李玉，于涛，等.Vogel法求解最大值问题［J］.郑州大学学报:理学版，2011，43(1):26－28.

Application of Table Algorithm in the Cargoes Transportation Problem with Transshipment

CHEN Hai-wei，TAO Qing-ling

(Department of Management，Shangqiu Institute of Technology，Shangqiu 476000，China)

The table algorithm on transportation problem of the production and sale balance is discussed.Vogel method is used to get the initial solution，potential method to get test number，and closed-loop method to adapt and improve the feasible solutions.And a method for the transportation problem with transshipment is proposed，with all the places of production，the middle station and pins regarded as the places of production and pins，so the problem can be solved as an expanded transport problem.

table algorithm;Vogel method;potential method;test number

O224

A

1007－0834(2012)02－0020－04

10.3969/j.issn.1007－0834.2012.02.006

2011－12－29

陈海伟(1983—)，男，河南商丘人，商丘工学院管理学院教师.