Решение некоторых сетевых задач в среде Excel
DOI: 10.34130/2070-4992-2019-1-150-159
УДК 519.677
Н. В. Катаргин, к. ф.-м. н., доцент, Финансовый университет при Правительстве Российской Федерации (Москва, Россия)
Цель данной работы – разработка методов решения актуальных задач сетевого моделирования. Предложены принципиально новые алгоритмы для решения в среде Excel двух задач: выбор маршрута в дорожной сети (задача коммивояжёра), размещение и подключение к потребителям электроподстанций с обеспечением минимизации потерь в электросетях. Авторские know how: «короткий план» в задаче о выборе маршрута, позволяющий резко сократить количество варьируемых компьютером переменных, нетривиальное использование сервиса “Поиск решения” (Solver) с применением метода градиентного спуска для варьирования двоичных переменных, а также совместное варьирование действительных и двоичных переменных в задаче о размещении. Решена проблема появления «островов» в задаче о выборе маршрута – узлов, не связанных с основным маршрутом. В алгоритм заложено недопущение возврата по той же дороге, кроме особых случаев – звёздных маршрутов из некоторых пунктов. Алгоритмы реализованы в среде MS Excel, для их использования не требуется программирование, а только заполнение таблиц исходных данных и несложные действия: копирование и суммирование. Выбор маршрута и размещение подстанций опробованы на сетях с 15 узлами, что достаточно для практики. Проложены оптимальные маршруты через реальную дорожную сеть, как без возвращения в исходный пункт, так и кольцевой маршрут, как в классической задаче коммивояжёра. В задаче о размещении объектов также использованы реальные карты (Yandex). Проработаны два варианта – с ограничением подстанций по мощности и без ограничения. Данный алгоритм можно использовать для оптимизации размещения, например баз снабжения топливом и товарами. При размещении объектов в узлах дорожной сети их координаты заменяются на двоичные переменные с незначительными изменениями алгоритма. Результаты могут быть использованы для практической работы в области транспортной логистики и размещения новых производств, а также обучения студентов методам решения производственных задач с использованием математического моделирования и информационных технологий.
Ключевые слова: сетевое моделирование, маршрут, задача коммивояжёра, размещение объектов, электросети, Excel.
Список литературы
1. Дыбская В. В., Зайцев Е. И., Сергеев В. И. Логистика. Полный курс МВА: учебник. М.: Эксмо, 2008. С. 30–39.
2. Экономико-математическое моделирование / под ред. И. Н. Дрогобыцкого: учебник. М.: Экзамен, 2006. 798 с.
3. Кремер Н. Ш.и др. Исследование операций в экономике: учебник. М.: Юрайт, 2014. 424 с.
4. Рубчинский А. А. Методы и модели принятия управленческих решений. М.: Юрайт, 2015. С. 111–113.
5. Решение задачи коммивояжёра рекурсивным полным перебором. URL: www.habr.com/ru/post/151151/ (да-та обращение: 10.09.2012.)
6. Майника Э. Алгоритмы оптимизации на сетях и графах: монография. М.: Мир, 1981. C. 241–264.
7. Bellmore M., Nemhuser G. L., 1968. The Travelling Salesman Problem: A Survey. Operations Research, vol. 16, 3: 538–558.
8. Garfinkel R., Namhauser G. L., 1972. Integer Programming. New York: John Wiley, Inc., pp: 354–360.
9. Held M., Karp R., 1971. The Travelling-Salesman Problem and Minimum Spanning Trees, Part II. Math. Programming, vol. 1, 1: 6-25.
10. Steckhan H. A., 1970. Theorem on Symmetric Travelling Salesman Problems. Operations Research, vol. 18, 6: 1163–1167.
11. Галяутдинов Р. Р. Задача коммивояжёра – метод ветвей и границ. galyautdinov.ru/post/zadacha-kommivoyazhera (дата обращения: 18.11.2013)
12. Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы. Построение и анализ: монография. М.: МЦНМО, 2002. С. 845–846.
13. Matai, R., Singh, S., & Lal, M., 2010. Traveling salesman problem: An overview of applications, formulations, and solu-tion approaches. In D. Davendra (Ed.), Traveling Salesman Problem, Theory and Applications. InTech. Р. 356.
14. Junger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., & Wolsey, L. (Eds.). 2009. 50 years of integer programming, 1958–2008: The early years and state-of-the-art surveys. Heidelberg: Springer. Р. 785.
15. Cook, W. 2007. History of the TSP. The Traveling Salesman Problem. URL: www.math.uwaterloo.ca/tsp/history/index.htm (дата обращение: 20.03.2019)
16. Laporte, G. 1992. The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231–247.
17. DAA – Travelling Salesman Problem. URL: www.tutorialspoint.com/design_and_analysis_of_algorithms/ design_and_analysis_of_algorithms_travelling_salesman_problem.htm (дата обращения: 23.11.2016)
18. Lee Jacobson. Applying a genetic algorithm to the traveling salesman problem. 2012. URL: www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5 (дата обраще-ния: 20.03.2019)
Для цитирования: Катаргин Н. В. Решение некоторых сетевых задач в среде Excel // Корпоративное управление и инновационное развитие экономики Севера: Вестник Научно-исследовательского центра корпоративного права, управления и венчурного инвестирования Сыктывкарского государственного университета. 2019. № 1. С. 150–159. DOI: 10.34130/2070-4992-2019-1-150-159