Multi-index transportation problems with 1-nested structure

Abstract

Consideration was given to the solution of the multi-index transportation problems of linear and integer-linear programming. It was proposed to use the approach based on studying the reducibility of the multi-index transportation problems to the problem of the minimal cost in the treelike network. It was proved that within the framework of the reduction scheme the condition for 1-nesting of the multi-index problems is necessary and sufficient for reducibility to the problem of the minimal-cost flow problem on a treelike network. An algorithm was proposed to solve the 1-nested multi-index problems requiring as many computer operations as the square of variables in the original problem.