Алексей Юрьевич Озеров, студент
Кинель
Aleksey Yu. Ozerov, student
Samara
Олег Игоревич Курлыков, кандидат экономических наук, доцент, доцент кафедры «Государственное управление и деловое администрирование»
Кинель
Oleg I. Kurlykov, Candidate of Economic Sciences, Associate Professor, Associate Professor of the Department of Public Administration and Business Management
Samara
В работе исследуется проблема возрастания вычислительной сложности классического метода потенциалов при решении транспортных задач большой размерности. Предложена модификация алгоритма, позволяющая сократить временные затраты на вычисления без потери точности решения. Ключевым элементом новизны выступает эвристическое ограничение на количество пересчитываемых потенциалов в рамках каждой итерации, а также упрощенное правило выбора переменной, входящей в базис. На базе формальной постановки закрытой транспортной задачи проведен анализ традиционного алгоритма, выявлены наиболее ресурсоемкие операции. Программная реализация модифицированного алгоритма выполнена на языке C. Для верификации эффективности организована серия вычислительных экспериментов с синтетическими данными размерностью от 10×10 до 200×200. Эмпирические результаты демонстрируют сокращение времени решения на 15–25% для задач размерностью свыше 100×100. При этом отклонение стоимости полученного плана от эталонного решения не превышает 0,01%. Практическая значимость подтверждена на примере моделирования распределения медикаментов в Самарской области. Научная новизна состоит в разработке эвристики, адаптирующей точный метод потенциалов к работе с большими массивами данных. Результаты могут найти применение при совершенствовании информационных систем управления логистическими цепями.
This paper investigates the problem of increasing computational complexity of the classical potential method when solving large-scale transportation problems of linear programming. A modification of the algorithm is proposed that allows reducing computation time without losing solution accuracy. The key element of novelty is a heuristic limitation on the number of recalculated potentials within each iteration, as well as a simplified rule for selecting the variable entering the basis. Based on the formal statement of the closed transportation problem, an analysis of the traditional algorithm was conducted, and the most resourceintensive operations were identified. The software implementation of the modified algorithm was performed in C programming language. To verify the effectiveness, a series of computational experiments was organized using synthetic data with dimensions from 10×10 to 200×200. Empirical results demonstrate a 15–25% reduction in solution time for problems with dimensions exceeding 100×100. At the same time, the deviation of the obtained plan's cost from the reference solution does not exceed 0,01%. The practical significance is confirmed through modeling medication distribution in the Samara region. The scientific novelty consists in developing a heuristic that adapts the exact potential method to work with large data arrays. The results can be applied to improve information systems for managing logistics chains.
The authors declare that there are no conflicts of interest present.