运输问题原设－对偶算法的一个改进

An Improvement on the Primal-Dual Algorithm for Transport Problem

本文对运输问题的原设－对偶算法运用推拉流思想进行改进，得到一个拟多项式时间算法。该算法使用的数据结构简单，运行时间界为Ｏ（Ｕ＿ｎ（ｍ＋ｎ）￣３），其中ｍ为产地数目，ｎ为销地数口，Ｕ表示整体待运量。

The primal-dual algorithm for transport problem is improved on using the idea of push-pull flow,The improverd algorithm runs with time limit O(U_n(n+m))and uses very simple data structure,where the considered transport problem has m vertices of supply,n vertices of demand and total supplies U.