求解运输问题的一种新算法_夏少刚 - 副本.pdf

第16 卷 第1 期 运 筹 与 管 理 Vol. 16, N o. 1 2007 年2 月 OPERATIONS RESEARCH AND MANAGEMENT SCIENCE Feb. 2007 夏少刚, 张建华 ( , 116025) :, , Dijk- stra , 3 ; , o(n ) ( m[ n ) : ; ; ; Dijkstra ; ; : O221. 1 : A : 1007-3221(2007) 01-0032-05 New Algorithm for the T ransportation Problem XIA Shao- gang, ZHANG Jian-hua (Dong bei Univ ersity of F inance and E conomics, Dalian 116025, China ) Abstract: In this paper w e 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 al- gorithm to the transportation problem w ith possible negative w eight of edge. Compared w ith 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 . Key words: operations research; transportation problem; shortest path; Dijkstra label algorithm; poly- nomial algorithm; minimum adjustment method 0 : n 1 E ji = ai , (i = 1, ,, m) j = 1 ( 2) B 1 B2 , Bn