Модификация метода потенциалов для снижения вычислительной сложности при решении транспортных задач большой размерности

В работе исследуется проблема возрастания вычислительной сложности классического метода потенциалов при решении транспортных задач большой размерности. Предложена модификация алгоритма, позволяющая сократить временные затраты на вычисления без потери точности решения. Ключевым элементом новизны выступает эвристическое ограничение на количество пересчитываемых потенциалов в рамках каждой итерации, а также упрощенное правило выбора переменной, входящей в базис. На базе формальной постановки закрытой транспортной задачи проведен анализ традиционного алгоритма, выявлены наиболее ресурсоемкие операции. Программная реализация модифицированного алгоритма выполнена на языке C. Для верификации эффективности организована серия вычислительных экспериментов с синтетическими данными размерностью от 10×10 до 200×200. Эмпирические результаты демонстрируют сокращение времени решения на 15–25% для задач размерностью свыше 100×100. При этом отклонение стоимости полученного плана от эталонного решения не превышает 0,01%. Практическая значимость подтверждена на примере моделирования распределения медикаментов в Самарской области. Научная новизна состоит в разработке эвристики, адаптирующей точный метод потенциалов к работе с большими массивами данных. Результаты могут найти применение при совершенствовании информационных систем управления логистическими цепями.

1. Балашов В.Г. Линейное программирование и транспортные задачи. Санкт-Петербург : Питер, 352 с.

2. Гончаров Е.Б., Плотников А.В. Современные проблемы моделирования транспортно-логистических систем // Логистика и управление цепями поставок. 2022. № 3 (104). С. 15–27.

3. Лотов А.В., Поспелова И.И. Эвристические методы решения транспортных задач в региональной логистике // Вестник Самарского государственного экономического университета. 2022. № 4 (194). С. 78–89.

4. Жданов С.П. Оптимизационные методы в экономике. Самара : Самарский университет, 2021. 264 с.

5. Orlin J.B. A polynomial time primal network simplex algorithm for minimum cost flows // Mathematical Programming. 2019. Vol. 154 (1-2). Pp. 47–48.

6. Гаврилов Л.П., Гасанов Э.Э. Параллельные алгоритмы решения задач линейного программирования большой размерности // Программирование. 2022. № 4. С. 45–58.

7. Канторович Л.В. Математические методы организации и планирования производства. Москва : Наука, 2019. 368 с.

8. Таха Х.А. Введение в исследование операций. 9-е изд. Москва : Вильямс, 2021. 912 с.

9. Стронгин Р.Г., Баркалов К.А. Параллельные алгоритмы глобальной оптимизации для задач большой размерности // Вычислительные методы и программирование. 2020. Т. 21, № 3. С. 312–325.

10. Алексеев О.Г. Сложность вычислений и оптимизация алгоритмов. Москва : МЦНМО, 2019. 288 с.

11. Емеличев В.А., Кравцов М.К. Алгоритмы оптимизации транспортных потоков большой размерности // Программные продукты и системы. 2021. Т. 34, № 2. С. 245–256. doi:10.15827/0236235X.134.245-256.

12. Kratica J., Tošić D., Filipović V. An efficient implementation of the transportation simplex algorithm // Computational Optimization and Applications. 2021. Vol. 48. Pp. 227–245.