最小费用流问题的一种改进算法.pdfVIP

第 13 卷 　第 3 期 运 　筹 　与 　管 　理 Vol . 13 ,No . 3 2004 年 6 月 OPERA TION S R ESEARCH AND MANA GEM EN T SCIEN CE J un . 2004 　 　 最小费用流问题的一种改进算法 刘 冰 , 　卢虎生 , 　高学东 , 　尹阿东 (北京科技大学 管理学院 ,北京 100083) 摘 　要 :本文用顶点表和弧表描述和存储最小费用流的参数 ,借助 SQL 语言的优点提出了一种求解最小费用流 的简便算法 。文中提出了前沿节点和含潜弧的概念 ,并利用这些概念减少了最短路算法的迭代次数和每次迭代 的计算量 。最后给出了一个算例 。 关键词 :运筹学 ;最小费用流算法 ; SQL 语言 ;前沿节点 ;含潜弧 ( ) 中图分类号 :O157 . 5 　　　文章标识码 :A 　　　文章编号 :1007322 1 2004 An Imp roving Algorithm for Minimum Co st Flow s L IU Bing , L U Husheng , GAO Xuedong , YIN Adong ( S chool of M anagem en t , B eij i ng Univers ity of S cience an d Tech nology , B eij i ng 100083 , Chi na) Ab stract : The p aper uses vertices t able and arcs t able to store t he p arameter s of t he minimum co st flow , and p ropo ses a simple algorit hm in virt ue of t he merit s of SQL . The concept s of front vertex set and arcs wit h co st - reducing potential are int roduced , which decrease t he times of iterations and t he comp ut ation quantit y of each time . Finally , a sample is p resented . Key words :operational reseach ; minimum co st flow algorit hm ; SQL ; front vertex set ; arcs wit h co streduc ing potential 0 　引言 最小费用流是图论领域的一个重要问题 ,在物流 、通讯等许多领域有着十分广泛的应用 。文献[ 1 ,2 , 3 ,4 ]报道了多种求解最小费用流的算法 ,综观这些算法 ,其核心都集中在如何进一步提高寻找最短路和增 广这两个子过程的计算效率方面 。BellmanFor d 法是一种典型的最短路算法 ,可用于寻找从起点到所有 其他顶点的最短路 。算法的