求解运输问题的一个算法.pdf.pdf

2
2 2 2
1
第 11 卷第 3 期运筹与管理 Vol. 11 ,No. 3
2002 年 6 月 OPERATIONS RESEARCH AND MANA GEMEN T SCIENCE J un. ,2002

2 2 求解运输问题的一个算法
2
谢凡荣
(南昌大学数理学院,江西南昌 330047)
摘要:给出一个求解问题的数值算法,证明了算法的理论依据,并举例说明算法的应用。
关键词:运输问题;典则型运输网络;最小费用最大流。
中图分类号:U113∶O224 文章标识码:A 文章编号:1007 3221 (2002) 03 0069 05
An Algorithm for Solving the Transportation Problem
XIE Fan rong
( School of Science , N anchang U niversity , N anchang 330047 , China)
Abstract :A numerical algorithm is presented to solve the problem of transportation. The theory
on which the algorithm depends is strictly proved. An example is given to demonstrate the use of
the algorithm.
Key words :the problem of transportation ; the standard work ; the minimal cost
and maximal flow.
0 引言
运输问题在文献[2 ]中已经提出,并就产销平衡和产销不平衡两种情形进行讨论,对产销
平衡的运输问题给出了“表上作业法”解法,对产销不平衡的运输问题给出了将它化为产销平
衡的运输问题的方法。表上作业法是单纯形法在求解运输问题时的一种简化方法,其实质是
单纯形法[2 ] ,主要适用于问题规模不大时进行手工计算,难于编程在计算机上实现;单纯形法
易于编程实现,但其计算量和计算机内存开销比较大。本文在分析问题特性的基础上,通过构
造典则型运输网络的办法,把运输问题转化为典则型运输网络中求最小费用最大流问题;再利
[5~10 ]
用文[8 ]中算法 X6 , 通过改进建立求解运输问题的数值算法 X11 。本文作者已将算法
X11用 Visual Basic5 0 在计算机上实现,利用它,只要输入该问题的相关信息,就能方便快捷地
求出运输问题的最优调运方案。文中的有关概念和记号参见文献[1~11 ] 。
收稿日期:2002 02 22
作者简介:谢凡荣(1966 ) ,男,湖南邵阳人,南昌大学讲师,硕士,研究方向为运筹学及其计算机应用。
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
6 6
6
6
6 6 6 6
07 运筹与管理 2002 年第 11 卷
1 问题及其数学模型
已知有 m 个生产地点(产地)