2021, випуск 3, c. 15-33

Одержано 23.07.2021; Виправлено 14.08.2021; Прийнято 28.09.2021

Надруковано 30.09.2021; Вперше Online 25.10.2021

https://doi.org/10.34229/2707-451X.21.3.2

Попередня  |  Повний текст  |  Наступна

 

УДК 519.85

Задачі про найкоротші k-вершинні цикли та шляхи

П.І. Стецюк 1 * ORCID ID favicon Big,   Д.І. Соломон 2,   М.Ю. Григорак 3 ORCID ID favicon Big

1 Інститут кібернетики імені В.М. Глушкова НАН України, Київ

2 Інститут математики та інформатики Академії наук Молдови, Кишинеу

3 Національний авіаційний університет, Київ

* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Робота присвячена побудові математичних моделей для задач про найкоротші цикли та шляхи, які проходять через задану кількість вершин орієнтованого графа. Такі цикли та шляхи називаються k-вершинними, де 1<k<n, n – кількість вершин графа.

У розділі 1 сформульовано дві задачі для пошуку найкоротшого k-вершинного циклу – задача змішаного булевого і лінійного програмування та задача дискретного програмування. Обидві задачі включають обмеження від класичної задачі про призначення, які описують одноразовий вхід в вершину та одноразовий вихід з вершини для тих  вершин, через які проходить цикл. Зв’язність циклу в першій задачі забезпечується завдяки моделюванню задачі про потік, а в другій задачі забезпечується завдяки використанню обмежень А. Таккера для задачі комівояжера. У розділі 2 встановлено зв'язок формулювань обох задач з розділу 1 із задачею комівояжера та досліджено ефективність їх розв’язання за допомогою сучасних версій програм gurobi і cplex та мови моделювання AMPL.

У розділі 3 наведено формулювання задачі про найкоротший k-вершинний шлях, яка представлена задачею змішаного булевого і лінійного програмування. З її допомогою знайдено оптимальні маршрути для відвідування пунктів виноробства Малопольського винного шляху в напрямку Львів – Вроцлав –Львів (розділ 4). Тут наведено карту для 20 найбільш відвідуваних пунктів виноробства Мало-польського винного шляху та таблицю відстаней між ними і відстаней від них до Львова та Вроцлава, які обчислені за допомогою веб-сервісу Google Maps.

Розроблені математичні моделі задач знаходження найкоротших k-вершинних шляхів і циклів та розроблене програмне забезпечення на мові моделювання AMPL можуть  бути використані при проектуванні і компонуванні технічних об'єктів, оптимізації транспортування товарів, аналізі та прогнозуванні економічних процесів, визначенні оптимальних маршрутів при плануванні пасажирських і вантажних перевезень, оптимальній організації процесу управління множиною транзакцій та запитів при їх реалізації в мережевих базах даних та інших класів прикладних задач оптимізації.

 

Ключові слова: орграф, найкоротший шлях, булева змінна, лінійне програмування, гамільтонів цикл, гамільтонів шлях, задача комівояжера, AMPL, gurobi, cplex.

 

Цитувати так: Стецюк П.І., Соломон Д.І., Григорак М.Ю. Задачі про найкоротші k-вершинні цикли та шляхи. Cybernetics and Computer Technologies. 2021. 3. С. 15–33. https://doi.org/10.34229/2707-451X.21.3.2

 

Список літератури

           1.     Кристофидес Н. Теория графов. Алгоритмический подход. M: Мир, 1978. 432 с.

           2.     Ермольев Ю.М. Кратчайшие допустимые пути. Кибернетика. 1966. № 3. С. 88–95.

           3.     Ермольев Ю.М., Мельник И.М. Кратчайшие допустимые пути. II. Кибернетика. 1967. № 1. С. 63–71.

           4.     Ермольев Ю.М., Мельник И.М. Экстремальные задачи на графах. Киев: Наукова думка, 1968. 176 с.

           5.     Стецюк П.И., Петрухин В.А., Бугров Н.В., Хрипко К.Ю. Метод эллипсоидов и условно-оптимальный маршрут. Міжнародна наукова конференція "Сучасна інформатика: проблеми, досягнення та перспективи розвитку", присвячена 90-річчю від дня народження академіка В.М. Глушкова (12–13 вересня 2013 року). Київ: Інститут кібернетики імені В.М. Глушкова НАН України. 2013. С. 111–113.

           6.     Gavish B., Graves S.C. The travelling salesman problem and related problems. Working Paper OR-078-78, 1978. Operations Research Center. MIT. Cambridge. MA.

           7.     Miller C.E., Tucker A.W., Zemlin R.A. Integer programming formulation of travelling salesman problem. J. ACM. 1960. 3. P. 326–329.

           8.     Алексеева Е.В. Построение математических моделей целочисленного линейного программирования. Примеры и задачи: Учеб. пособие / Новосиб. гос. ун-т. Новосибирск, 2012. 131 с.

           9.     Гамецкий А.Ф., Соломон Д.И. Исследование операций. Том II. Кишинэу, Эврика, 2008. 592 с.

       10.     Стецюк П.И. Формулировки задач для кратчайшего k-вершинного пути и кратчайшего k-вершинного цикла в полном графе. Кибернетика и системный анализ. 2016. № 1. С. 78–82.

       11.     Стецюк П.И. Две задачи о кратчайшем k-вершинном цикле. Матеріали ХIII Міжнародної науково-практичної конференції «Математичне та програмне забезпечення інтелектуальних систем (MPZIS–2015)» (18–20 листопада 2015. Дніпропетровськ). C. 215–221.

       12.     Стецюк П.И., Соломон Д.И. Вычислительные аспекты задачи коммивояжера. Тези доповідей VIII Міжнародної науково-технічної конференції «Інформаційно-компьютерні технології 2016» (2223 квітня 2016 року). Житомир: ЖДТУ, 2016. С. 9192.

       13.      Solomon Dumitru. Transporturi rutiere de mărfuri si pasageri. Cartea I. Organizarea transporturilor rutiere de mărfuri. (Proiect de an) Ch.: Evrica, 2014. 170 p.

       14.     Gurobi Optimization, Inc. Gurobi Optimizer Reference Manual. 2014. http://www.gurobi.com/

       15.     CPLEX Optimizer. High-performance mathematical programming solver for linear programming, mixed-integer programming and quadratic programming. https://www.ibm.com/analytics/cplex-optimizer

       16.     NEOS Solver. https://neos-server.org/neos/solvers/

       17.     Fourer R., Gay D., Kernighan B. AMPL, A Modeling Language for Mathematical Programming. Belmont: Duxburry Press, 2003. 517 p.

       18.     Стецюк П.И., Лефтеров А.В., Федосеев А.И. Кратчайший k-вершинный путь. Компьютерная математика. 2015. № 2. С. 3–11.

       19.     Стецюк П.И., Лефтеров А.В., Лиховид А.П., Федосеев А.И. Оптимизационный сервис для выбора винных маршрутов. Математическое моделирование, оптимизация и информационные технологии: материалы V Международной научной конференции (Кишинэу, 22–25 марта 2016 г.). Кишинэу: Эврика, 2016. T. II. С. 337–344.

       20.     Андрианова Е.Г., Раев В.К., Фильгус Д.И. Определение кратчайших гамильтоновых путей в произвольных графах распределенных баз данных. Российский технологический журнал. 2019. Т. 7, 4. С. 7–20. https://doi.org/10.32362/2500-316X-2019-7-4-7-20

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  Повний текст  |  Наступна

 

 

            Випуски

 

© Вебсайт та оформлення. 2019-2024,

Інститут кібернетики імені В.М. Глушкова НАН України,

Національна академія наук України.