| 求解运输问题的一种新算法 |
| |
| 引用本文： | 夏少刚,张建华.求解运输问题的一种新算法[J].运筹与管理,2007,16(1):32-36. |
| |
| 作者姓名： | 夏少刚 张建华 |
| |
| 作者单位： | 东北财经大学,数量经济系,辽宁,大连,116025 |
| |
| 摘 要： | 本文将求解分派问题的标号算法成功地用于运输问题,并证明其中的非负处理可以省略,从而把Dijk-stra算法扩展到可能出现负边权的运输问题。与通常方法比较,这种方法具有直观、简单、计算量少、及易于推广等优点;最后证明该算法是多项式的,计算复杂性仅为o(n3)(当m≤n时)。
|
| 关 键 词： | 运筹学 运输问题 最短路 Dijkstra标号算法 多项式算法 最小调整法 |
| 文章编号： | 23926893 |
| 修稿时间： | 06 8 2006 12:00AM |
New Algorithm for the Transportation Problem |
| |
| XIA Shao-gang,ZHANG Jian-hua.New Algorithm for the Transportation Problem[J].Operations Research and Management Science,2007,16(1):32-36. |
| |
| Authors: | XIA Shao-gang ZHANG Jian-hua |
| |
| Institution: | Dongbei University of Finance and Economics, Dalian 116025, China |
| |
| Abstract: | In this paper we successfully solve the transportation problem using the label method for the assignment problem and prove that its treatment of nonnegative can be omitted,thus extend Dijkstra algorithm to the transportation problem with possible negative weight of edge.Compared with other usual methods,the method is visualized,simple,costs less computational time and is easier to be generalized.Lastly,the algorithm is proved to be polynomial and complexity of computation is only. |
| |
| Keywords: | operations research transportation problem shortest path Dijkstra label algorithm polynomial algorithm minimum adjustment method |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
