论运输问题表上作业法

中图分类号:F502 文献标识:A 文章编号:1009-4202(2010)10-286-02

摘 要 运输问题是运筹学的经典问题,而表上作业法是运输问题中的重要算法,具有广泛的应用.本文对运输问题表上作业法进行了一些必要的探讨,利用闭回路的唯一性,给出了一种新的闭回路构建方法,简化了求解运输问题最优解的过程。

关键词 运输问题 运筹学 表上作业法 闭回路

一、引言

运输问题的数学模型为:

设某产品有 个产地 和 个销地 .在产地 的产量为 ,在销地 的销量为 ,从 到 运送一个单位货物的运费为 .假设产销平衡,即 ,试确定一个调运方案,使总运费最小。

假设产地 供给销地 的货物量为 ,上述问题可用以下数学模型表示:

的前 行对应 个产地,后 行对应 个销地。 的增广矩阵记作 。由于产销不平衡运输问题均可转化为产销平衡运输问题,因此本文仅研究产销平衡运输问题。

二、运输问题的基本性质

定理1:销平衡的运输问题必存在有限最优解。

定理2:运输问题的系数矩阵 和增广矩阵 的秩均为 。

定理3:运输问题中, 的任何方子矩阵的行列式为-1,0或1。

三、表上作业法求解运输问题

运输问题是线性规划问题的特殊情形,其约束条件具有特殊结构,除了可用一般的单纯形方法求解外,还可用简单有效的表上作业法求解.表上作业法就是一种求解运输问题的有效的迭代法.按照迭代法的基本思想,表上作业法的步骤可归纳如下:

(1)确定初始基本可行解,得到 个基变量。

求解初始基本可行解的方法很多,最常见的是西北角法,最小元素法和差额法。一般情况,差额法确定的基本可行解质量最好,最接近最优解。

(2)判定是否最优。用位势法判别可行解是否为最优解,如果所有判别数非正,说明得到最优解,否则转入(3)。

(3)若是最优,则问题得解;若不是最优,则按闭回路法对运输方案进行调整。

a.从具有最大的判别数的空格作为闭回路的第一格.

b.第二格的确定。找出基向量,找基向量中与第一格中同在的行(列)的元素,作为第二格。

c.第k格的确定。在基向量中寻找,与第k-1格同在一列(行)的元素,若存在,则选择其一作为第k格,令k=k+1,转入第d步;否则令k=k-1,转入第d步。

d.找与第k-1格同在一行(列)的元素,判断是否与第k格在同一列(行),若在同一列(行),则得到闭回路;否则转入第c步。

四、实例

给定运输问题如表1,其中 为产地, 为产量, 为销地, 为销量,每个方格右上角数字为费用系数 ,试确定一个运输方案,使总运输费用最小。

解:首先用差额法求初始基本可行解,计算结果如表2,其基变量为( )=(0,10,1,11,4,5)目标函数值为f=148。

五、总结

运输问题是运筹学的经典问题,而表上作业法是运输问题中的重要算法,具有广泛的应用.本文主要提出了闭回路构建的新算法,改进了之前的算法涉及到每个格,降低了构建闭回路的计算时间。

参考文献:

[1]陈宝林.最优化理论与算法.清华大学出版社.2005.

[2]钱颂迪.运筹学.清华大学出版社.北京.1990.

[3]韩伟一.运输问题表上作业法的一点驻记.运筹与管理.2009.18(4):7-9.