Методы решения многоиндексных транспортных задач высокой размерности

Abstract

In the general formulation, the transportation problem consists in finding an optimal plan for the transportation of some homogeneous cargo to consumers, which leads to a two-index problem. In real transportation problems, it is necessary to take into account not only differences in points of production and consumption, but also of intermediate centers, type of goods, type of vehicles, etc. Such a problem is described by a multi-index model of the transportation problem. The exact solution of a multiindex transportation problem can be obtained by the method of potentials. However, the practical implementation of this method is laborious, and the computational complexity of obtaining a solution grows rapidly with the increase in the dimension of the problem. This circumstance stimulates the development of approximate methods for solving multi-index transportation problems, which make it easier to carry out the improvement of the problem current plan. In this regard, the paper proposes an iterative procedure for improving the problem's plan, based on elementary matrix transformations and easily realized, by a simple search of submatrices. The features of the procedure are illustrated by the special case of the three-index transportation problem. In this case, an effective technique was used to construct the initial basic plan of the problem consisting in the zero transformation of the initial value matrix, which is generalized in the case of a transportation problem of arbitrary index. Using the method leads to the fact that the initial basic plan is closer to the optimal one, that substantially reduces the number of iterations of the solution of the problem. The proposed methods are useful to be used both at the stage of construction of the initial basic plan, and during its iterative improvement. The effectiveness of the proposed methods for solving multi-index transportation problems of high dimension is illustrated by an example.