Volume 18, No 1, 2011, P. 20-26
UDC 519.87+519.854
V. T. Dementiev, Yu. V. Shamardin
On a polinomial solving case of decentralized transportation problem
Abstract:
A case of decentralized transportation problem is considered, where a cost matrix has $n$ lines, $2n$ columns and a diagonal structure. An algorithm based on dynamic programming is proposed, that solves the problem with complexity $O(n^2)$.
Bibliogr. 1.
Keywords: decentralized transportation problem, dynamic programming.
Dementiev Vladimir Tikhonovich 1,2
Shamardin Yurii Vladislavovich 1
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: demvt@math.nsc.ru, orlab@math.nsc.ru
|