On polynomial solvability of the decentralized transportation problem with block matrices of profits of customers

Under study is a particular case of the decentralized transportation problem. Matrices of profits of customers consists of $n$ rows and $kn$ columns and has a block structure. A way of solution is algorithm based on the method of dynamic programming with time complexity $O(k^2n+kn^2)$.