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

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.