Decomposition method for a class of transport-type problems with a quadratic objective function

Abstract

A class of transport problems with a quadratic criterion without any restrictions on the sign of unknown variables is considered. An iterative algorithm based on the consecutive modification of the coefficients of the objective function is used. The problem is reduced to successively solving pairs of problems from various groups of restrictions. These problems have one connecting variable and are solved analytically by the method of Lagrange multipliers. If the negative components appear in the course of solving them, the problem with one or several restrictions from one group and all restrictions from the other group is considered. These problems can also be easily solved for large dimensions, and in this way the dimension is reduced.