摘 要
求解运输问题可以使用线性规划中的单纯形法，其中较为简单、便利的表上作业法是针对运输问题特殊条件而产生的一种求解方法。本文介绍了表上作业法的概念、方法、步骤及在货物运输中的运用。
关键词:表上作业法，货物运输组织，最优解
目 录
1１ 表上作业法
概念
表上作业法求解思路
表上作业法的类型
2２ 表上作业法的模型建立与求解
初始方案的确定
西北角法
73表上作业法在物流运输中的应用
初始方案的求解
初始方案的判别与调整
13结 论
14参考文献
１ 表上作业法
概念
用列表的方法求解线性规划问题中运输模型的计算方法。是指线性规划一种求解方法。当某些线性规划问题采用图上作业法难以进行直观求解时，就可以将各元素列成相关表，作为初始方案，然后采用检验数来验证这个方案，否则就要采用闭回路法、位势法或矩形法等方法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。
表上作业法求解思路
首先应根据给定条件确定初始方案，继而判断是否有最优解。若有，则初始方案即为最优方案；若无，则应对初始方案进行改进调整，并判断是否有最优解，若有则确定最优方案，若无则继续进行调整，直至确定最优方案。
是
否
图 求解思路
表上作业法的类型
在实际应用中，表上作业法可以分为产销平衡运输问题和产销不平衡的运输问题。产销平衡运输问题相对而言比较简单，而遇到产销不平衡运输问题时，应采用以下方法解决。当供大于求时，引入虚拟需求点，其需求量等于实际供应量与需求量之差，该点运价为零。当求大于供时，引入虚拟供应点，其供应量等于实际需求量与供应量之差，该点运价为零。
２ 表上作业法的模型建立与求解
表上作业法是求解运输问题的一种简便而有效的方法，其实质是单纯型法。但在其迭代计算过程中，初始方案确定、方案的调整改进处理不一样，计算工作量就不一样，有时相差很大。那么，怎样才能使迭代计算工作量尽可能小？迭代次数尽可能少？下面将分别予以探讨。
初始方案的确定
初始方案的确定，常用的方法有三种：最小元素法、西北角法、Vogel法。一般地，Vogel法确定的初始方案质量最好，最接近最优解；最小元素法次之；西北角法最差。常用Vogel法确定的初始方案作运输问题最优解的近似解。
Vogel法
（1）用Vogel法求初始方案时，最大罚数有2个以上。理论上，由任意最大罚数所在行或所在列的最小运价确定填运量格均可。但若最大罚数所在行或所在列的各最小运价不等，那么，由此确定的初始方案质量就不一样。笔者认为，由最大罚数所在行或所在列的各最小运价的最小者，确定填运量格而获得的初始调运方案质量最好，即由此迭代而获得最优方案的迭代次数最少。
（2）确定初始方案，填某一运量格时，若同时满足其所在行和所在列的供销关系，则为保证初始方案的填运量格为m + n -1(m为产地数，n为销地数)个，应在何处填一个0？理论上，应在该填运量格的所在行或所在列的未划去或未填运量格中，任找一格填上一个O即可。但该填O的位置不一样，由此而获得的初始方案的质量就不一样。应在该填运量格的所在行或所在列的未划去或未填运量格中找一运价最小的空格填0，由此而获得的初始调运方案质量较好。因为，若由此而获得的初始方案不是最优解，在以后的迭代中，该填运量格的所在行或所在列的其他未划去或未填运量格，对应变量成为进基变量的可能性将减少，从而减少迭代次数，提高由此而获得的初始方案的质量。
例1 有3个产地A１、A２、A３、B１、B２、B３、B４的产销平衡运输问题，见表。试用表上作业法求最优调运方案。
表 产销平衡运输问题
B１
B２
B３
B４
产量/t
A１
3
6
2
4
70
A２
5
3
3
4
80
A３
1
7
5
2
50
销量/t
40
30
70
60
200
解：用Vogel法确定初始调运方案，按上述方法处理可得初始调运方案，见表。可检验该调运方案为最优调运方案，但若不按上述方法处理，获得的初始调运方案可能不是最优调运方案。
表 初始调运方案
B１
B２
B３
B４
产量/t
A１
70
70
A２
30
0
50
80
A３
40
10
50
销量/t
40
30
70
60
200
调运方案的检验
调运方案的检验通过检验数来完成。常用的求检验数的方法有闭回路法和位势法，而位势法计算检验数要简便得多，所以实际中常使用位势法计算检验数。任意空格对应变量Xij的检验数σij，即
σij = Cij - （μi+νj） （）
式中：Cij为该空格的单位运价；μi、νj分别为该空格所在行的行位势和所在列的列位势。
由位势法原理，μi、νj（i=1,2,…，m；j=1，2，…，n）不能唯一确定，需先确定其中一个的值，其余m + n—1个的值才能唯一确定。那么，对同一调运方案(基可行解)，确定不同的μi或νj的值，所得的各变量的检验数σij是相同的，可由“任意空格一定存在除空格外其余顶点均为有数字格的闭回路”证明。
设计一空格存在的其余顶点均为有数字格的闭回路：Xij，Xij1，Xi1j1，Xi1j2，…，Xisjs，Xisj。有数字格对应变量为基变量，而基变量的检验数为0，所以
该闭回路上有数字格顶点的个数一定为奇数个。所以
（）
为一已知的常数。所以，的值无论先确定的哪一个值都是一样的。
为此，为简化用位势法求检验数的计算，常常任意指定某一位势等于一个较小的整数或零。
调运方案的调整改进
(1)若某一调运方案对应空格变量存在负检验数，则该调运方案不是最优调运方案，需对该调运方案进行调整改进。方案调整改进，是以绝对值最大的负检验数对应空格对应变量为进基变量，但当绝对值最大的负检验数对应空格对应变量有2个或2个以上时，应以哪一个变量作进基变量为最佳？
理论上取绝对值最大的负检验数，对应空格对应变量的任一变量作进基变量均可。但若绝对值最大的负检验数对应空格对应变量的最大可调整量不一样，由此调整而获得的新调运方案的质量就不一样。应以可增加调运量最多的绝对值最大的负检验数，对应空格对应变量作进基变量进行方案调整而得的新方案质量较好，因为这样可使目标函数值减少最多，从而减少迭代次数。
(2)进基变量确定以后，进行方案调整。在以进基变量对应空格为顶点，其余顶点均为有数字格的闭回路上，以空格为始点，顺时针或逆时针方向给闭回路上各顶点编号，偶数顶点即为调运量减少的格子，奇数顶点即为调运量增加的格子，闭回路上各顶点调运量的调整量即为该闭回路上偶数顶点的最小调运量θ。若对应θ有2个或2个以上顶点，则应以哪一个顶点对应变量作出基变量(即不填数的空格)为最佳？
理论上以θ对应的任一顶点对应的变量，作出基变量均可。但若θ对应各顶点的单位运价不一样，由此调整而获得新调运方案的质量就不一样。
应取θ对应各顶点的单位运价最大者，对应变量作出基变量进行方案调整，而得的新方案质量较好。因为，如此确定的出基变量是可作为出基变量中单位运价最大的，因此，在以后的迭代中其再成为进基变量的可能性将减少，从而减少迭代次数。
西北角法
西北角法确定初始调运方案求解例1。
解：用西北角法确定初始调运方案，见表；用位势法求得该初始调运方案的检验数，见表(表中只列出非基变量即空格的检验数，基变量的检验数为0，未列出)
表 初始调运方案
B１
B２
B３
B４
产量/t
A１
40
30
0
70
A２
70
10
80
A３
50
50
销量/t
40
30
70
60
200
表 检验数
B１
B２
B３
B４
A１
1
0
A２
0
-4
1
A３
-2
2
4
-1
4
6
2
3
以绝对值最大的负检验数对应变量X２２作进基变量，进行方案调整，得新的调运方案，见表；及其对应的各非基变量的检验数，见表。
表 调运方案
B１
B２
B３
B４
产量/t
A１
40
30
70
A２
30
40
10
80
A３
50
50
销量/t
40
30
70
60
200
表 检验数
B１
B２
B３
B４
A１
4
1
0
A２
0
1
A３
-2
6
4
-1
4
2
2
3
以绝对值最大的负检验数对应变量翔作进基变量，并按调整方案的检验中调整方案的确定原则进行方案调整，得新的调运方案，见表。可检验该调运方案为最优调运方案，但若不按上述方法处理，获得的调运方案就不是最优调运方案，还需迭代。
表 调运方案
B１
B２
B３
B４
产量/t
A１
70
0
70
A２
30
0
50
80
A３
40
10
50
销量/t
40
30
70
60
200
3表上作业法在物流运输中的应用
初始方案的求解
实例求解：有三个产地A１、A２、A３，四个销地B１、B２、B３、B４，产销鼍和运价见表，求初始调运方案。
表 产销量及运价表
B１
B２
B３
B４
产量
A１
3
11
3
10
7
A２
1
9
2
7
3
A３
7
4
10
5
9
销量
2
6
5
6
19
解：用vogel法求解
(1)首先，列出每行及每列最小运价与次小运价之间的差额，得B２列差额5为最大，对应列中最小运价为4，由A３运到B２， A３产量为9，B２销量为6，则在空格中填6，划去B２列。对表l中未划去的元素再分别计算出每行及每列最小运价与次小运价之间的差额，这时发现A３行B１列、B４列的差额均为2，最大。按照上面所介绍的处理原则，最大罚数不止一个时．由最大罚数所在行或所在列的各最小运价的最大者来确定运量的分配，同时综合考虑运费差额，由此得5，即由A３运到B４，由于A３已运到B２6个单位，因此在空格中填3，划去A３行，得表。
表 出现相同最大罚数时的处理
B１
B２
B３
B４
产量
A１
7
A２
3
A３
6
3
9
销量
2
6
5
6
19
(2)继续对表中未划去的元素再分别计算出每行及每列最小运价与次小运价之间的差额，这时发现B４列的差额最大，为3，对应最小运价为7，由A２运到B４，由于A２产最为3，而B４恰巧还需要3个，因此产销量相等，要同时划去，出现退化现象。为保证有闭合回路，按照上面介绍的处理原则，在A２行和B４列中剩下未划去或未填写的空格中寻找最小的运价，为1，则在对应空格A２B１中填0，得表。
表 出现退化现象时的处理
B１
B２
B３
B４
产量
A１
7
A２
0
3
3
A３
6
3
9
销量
2
6
5
6
19
(3)继续上述步骤，可得初始调运方案，如表所示。
可计算得总成本为81。
表 初始调运方案
B１
B２
B３
B４
产量
A１
2
5
7
A２
0
3
3
A３
6
3
9
销量
2
6
5
6
19
(4)若在第(1)步解题过程中，当出现2个相等的最大罚数时，未遵循本文所介绍的处理原则，即未能按照由最大罚数所在行或所在列的各最小运价的最大者，并且未能综合考虑运费差额来确定运量的分配，这时得初始方案，如表所示。可计算得总成本为83。
表 未按最大罚数处理原则解得的初始调运方案
B１
B２
B３
B４
产量
A１
5
2
7
A２
2
1
3
A３
6
3
9
销量
2
6
5
6
19
(5)若在第(2)步解题过程中，当出现退化现象时，未按照本文所介绍的原则填0，如选择空格A２B３填0，如表所示。
表 未按出现退化的处理原则解得的初始调运方案
B１
B２
B３
B４
产量
A１
2
5
7
A２
3
3
3
A３
6
3
9
销量
2
6
5
6
19
虽然所得到的初始调运方案与表实质上是相同的方案，但在采用位势法判断该方案是否为最优方案时，表可以直接判断出为最优方案，而表则不能确定，还需多进行一次迭代才能得到表的结果，虽然调整的货运量为0，但这显然增加了工作量。
(6)若用最小元素法求解，可得如下初始调运方案。如表所示。计算得总成本为85，可见使用Vogel法比最小元素法所求的初始调运方案质量更好，而且在计算中若能遵循本文所介绍的两个原则，所得方案将更接近最优方案。事实上，经检验，本例中用Vogel所求得的初始调运方案即为最优方案。
表 最小元素法求得初始调运方案
B１
B２
B３
B４
产量
A１
4
3
7
A２
2
1
3
A３
6
3
9
销量
2
6
5
6
19
初始方案的判别与调整
1、出现相同最小负检验数时的处理原则。按照位势法原理，通过设置行位势和列位势，由基变量的检验数等于0，求得非基变量的检验数
。 （）
若所有的非基变量检验数均为正值，则表明此初始方案已为最优方案。若有检验数为负值，表明未得到最优解，须以它对应的空格为调入格进行调整。若有两个和两个以上的负检验数，一般选其中最小的负检验数所对应的空格为调入格进行调整。然而，当同时存在两个或两个以上相同的最小负检验数时，以哪一个检验数对应的空格进行调整并未说明，而这也会影响到新的调运方案的质量。
建议选择可增加调运量最多的最小负检验数，以其所对应空格为调入格进行方案调整，因为这样可使目标函数值减少最多，因此得到的新方案质量较好，从而减少迭代次数。
2、出现退化时的处理原则。针对方案调整时出现的退化现象，在用闭叫路法调整时，在闭回路上出现两个和两个以上的具有(-1)标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后，得到退化解。这时有一个数字格必填上一个0，表明它是基变量。可以看出，它并没指明填“0”的确切位置，而这也将影响新调运方案的质量。
建议选取有(-1)标记的相等的最小值中对应单位运价最大者，对应变量作出基变量．填0进行方案调整，因为该出基变量是所有可作为出基变量中单位运价最大的，在以后的迭代中其再成为进基变量的可能性将减少，从而减少迭代次数，因此所得的新方案质量较好。
实例求解：有三个产地A１、A２、A３，四个销地B１、B２、B３、B４，产销量和运价见表，现给定初始方案见表，试判断该初始方案是否为最优解，若不是，请进行相应调整以成为最优解。
表产销量及运价表
B１
B２
B３
B４
产量
A１
3
7
6
4
40
A２
2
4
4
2
20
A３
4
3
8
5
20
销量
30
20
20
20
90
表初始调运方案
B１
B２
B３
B４
A１
10
20
10
A２
20
A３
20
10
解：
利用位势法进行判断，得各空格的检验数，见表。
表 检验数表
B１
B２
B３
B４
A１
5
A２
3
-1
-1
A３
0
1
(2) A２B３、A２B４均为-1，按照出现相同的最小负检验数时的处理原则，选择可增加调运量最多的最小负检验数，以其所对应空格为调入格进行方案调整。A１B１——A２B１——A２B３——A１B３组成的闭合回路中，可增加调运量20，而在A１B１——A２B１——A２B４——A１B４组成的闭合回路中，可增加调运量10，选择空格A２B３作为调入格，见表。
在此闭合同路中，由于调整量为20，A２B１、A１B３均变为0，出现退化，按照出现退化时的处理原则，选取两者中对应单位运价最大者，即A１B３作基变量，所在空格处填0。见表。
表 出现相同最小负检验数及退化时的处理
B１
B２
B３
B４
A１
30
0
10
A２
20
A３
20
10
（3）再次利用位势法进行判断，可得此方案即为最优解，总运费为320。
（4）若在第(2)步解题过程中，选择闭合同路A１B１一一A２B１——A２B４——A１B４，则得调整方案，见表。
表 未按出现相同最小负检验数的原则处理
B１
B２
B３
B４
A１
20
20
A２
10
10
A３
20
10
这时，总费用为330。
(5)在第(2)步解题过程中，当出现退化现象时，选择A２B１作基变量，填0，虽然该方案与表“实质相同，但在进行最优解判断时，不能立即判断出其为最优解，还需进行一次迭代，但是调整量为0，这增加了工作量。
结 论
随着物流行业的发展，物流公司迅速增加，各个物流公司之间的竞争日趋激烈。加强物流管理，减少物流成本已成为各物流企业的核心问题之一。利用表上作业法，可以合理地计算出贴近实际的物流配送方案，可以有效地解决物流公司的配送问题，提升物流公司的市场竞争力。
参考文献
[1] 胡运权.运筹学教程［M］.北京：清华大学出版社,2004.
[2] 韩伯棠.管理运筹学[M].北京：高等教育出版社，2000.
[3] 运筹学教材编写组.运筹学（第三版）[M].北京：清华大学出版社，2005.
[4] 李永生.国际物流学[M].机械工业出版社，2004.
[5] 钱颂迪等.运筹学[M].清华大学出版社，2007.
[6] 胡列格.物流运筹学.北京：人民交通出版社，2007.
PAGE
PAGE 1
