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

На правах рукописиРассказова Варвара АндреевнаМатематическоемоделированиев задачахпланированияиорганизациижелезнодорожныхперевозокметодамитеории графовоптимизациии численныеметодыи комбинаторнойих решенияСпециальность 05.13.18 —«Математическое моделирование, численные методы и комплексыпрограмм»Авторефератдиссертации на соискание учёной степеникандидата физико–математических наукМосква — 2017Работа выполнена в Федеральном государственном бюджетномобразовательном учреждении высшего образования «Московскийавиационный институт (национальный исследовательский университет)»Научный руководитель:Официальные оппоненты:доктор физико–математических наук,профессор Кибзун Андрей ИвановичЛазарев Александр Алекссевичдоктор физико–математических наук, профес­сор, ФГБУН «Институт проблем управленияим.

В. А. Трапезникова РАН», заведущий ла­бораторией «Теория расписаний и дискретнойоптимизации»Жукова Галина Николаевнакандидат физико–математических наук, до­цент, ФГБОУ ВО «Московский политехни­ческий университет», доцент кафедры «При­кладная математика и моделирование си­стем»Ведущая организация:ФГБУН «Институт математики и меха­ники им.

Н. Н. Красовского Уральскогоотделения Российской академии наук»Защита состоится «29» сентября 2017 г. в 10 часов 00 минут на за­седании диссертационного совета Д 212.125.04 Московского авиационногоинститута по адресу: 125993, Москва, А–80, ГСП–3, Волоколамское шос­се, 4.С диссертацией можно ознакомиться в библиотеке Москов­ского авиационного института по адресу: 125993, Москва, А–80,ГСП–3, Волоколамское шоссе, 4 или на сайте МАИ по ссылке:https://www.mai.ru/events/defence.Автореферат разослан «28» июля 2017 г.Отзывы на автореферат в двух экземплярах, заверенные печатьюучреждения, просьба направлять по адресу: 125993, Москва, А–80, ГСП–3,Волоколамское шоссе, 4, Отдел Учёного и диссертационных советов.Ученый секретарь диссертационногосовета Д 212.125.04, кандидатфизико–математических наук, доцентН.

С. СеверинаОбщая характеристика работыАктуальность темы. В работе исследуются задача планированияжелезнодорожных перевозок на этапе формирования бесконфликтного на­бора нормативных ниток, и задача организации железнодорожных пере­возок на этапе назначения и перемещения локомотивов без учёта ограни­чений на использование и техническое обслуживание локомотивов. Ввидувысокой комбинаторной сложности прикладных задач управления пере­возками актуальной представляется область разработки математическихмоделей, в рамках которых исследуемые задачи могут быть решены с по­мощью классического математического аппарата.

Как правило точное ре­шение задач комбинаторной оптимизации большой размерности являетсяизбыточным с точки зрения практической реализации решения, и, кро­ме того, поиск точного решения требует колоссальных вычислительныхзатрат. В этой связи особый интерес представляет область разработки эф­фективных вычислительных алгоритмов поиска приближённого решения.В то же время любой эвристический подход требует подтверждения ра­ботоспособности, и, таким образом, неотъемлемым этапом исследованиявыступает разработка комплекса прикладных программ, на основе которо­го осуществляется ряд вычислительных экспериментов, подтверждающихэффективность предложенных подходов к решению исследуемых задач.В работах Гайнанова Д. Н., Сотского Ю.

Н., Gholami O., Ефимен­ко Ю. И., Осипова С. И., Орлова А. И., Берцуна В. Н., Шепитько Т. В.,Гасанова А. И., Бучкина В. А., Ивахненко А. Г., Гоманкова Ф. С. получилиобоснование графовый и комбинаторный методы математического модели­рования в приложении к решению прикладных задач управления железно­дорожными перевозками. Разработанные в диссертации теоретико–графо­вые модели, кроме структурных свойств железнодорожных сетей, учиты­вают также и комбинаторный характер исследуемых задач, что позволяетзначительно расширить область разработки вычислительных алгоритмоврешения.Задача планирования железнодорожных перевозок исследуется, втом числе посредством методов теории графов и комбинаторной оптими­зации, в контексте задач теории расписаний в работах Лазарева А.А., Га­фарова Е.Р., Мусатовой Е.Г., Кварацхелия А.Г., Севастьянова С.В., Сот­ского Ю.Н., Танаева В.С., Струсевича В.А.

В рамках разработанной теоре­тико–графовой модели исследуемая прикладная задача планирования сво­дится к задаче расшифровки монотонной булевой функции, порождённойнеориентированным графом. В работах Гайнанова Д.Н., Тягунова Л.И.,Хачая М.Ю., Ерёмина И.И., Мазурова Вл.Д., Астафьева Н.Н., Мирзое­ва Р.Г., Новокшенова В.Ю. получены важные результаты в теории проти­воречивых систем условий, множество максимальных совместных подси­стем которых может быть специальным образом поставлено в соответствие3множеству максимальных по размеру клик графа.

Этот подход получилпродолжение в разработке вычислительных алгоритмов для формирова­ния верхнего нуля монотонной булевой функции, особенностью которыхявляется оценка точности приближённого решения.В работах Кибзуна А. И., Наумова А. В., Буянова М.

В., Азано­ва В. М., Иванова C. В., Осокина А. В. задача организации железнодорож­ных перевозок на этапе назначения и перемещения локомотивов сводитсяк задаче стохастического программирования. Постановка задачи организа­ции без учёта ограничений на использование и техническое обслуживаниелокомотивов имеет определённое практическое обоснование в части ниж­ней оценки точности решения. В рамках разработанной теоретико–графо­вой модели, исследуемая прикладная задача организации сводится к за­даче покрытия вершин ориентированного графа минимальным числом пу­тей.

Структурные свойства специфического ориентированного графа сов­местимости заданий на перевозку позволяют ограничиться рассмотрениеммножества максимальных по включению путей для покрытия вершин гра­фа, и, таким образом, размерность задачи может быть существенно сниже­на.В области разработки алгоритмов комбинаторной оптимизации, ли­нейного, целочисленного и динамического программирования, а также ал­горитмов на графах, в том числе приближённых алгоритмов, существен­ные результаты получены Дасгупта С., Пападимитриу Х., Вазирани У.,Корте Б., Фиген Й., Скиена С.

Вычислительные алгоритмы формирова­ния верхнего нуля монотонной булевой функции, порождённой неориенти­рованным графом, и алгоритм покрытия вершин ориентированного гра­фа — суть комбинаторный и комбинаторно–графовый алгоритмы, на ос­нове которых в диссертационной работе разработаны проблемно–ориенти­рованные программные комплексы для решения исследуемых прикладныхзадач планирования и организации железнодорожных перевозок.Целью работы является разработка математических моделей и вы­числительных алгоритмов для решения прикладных задач планирова­ния и организации железнодорожных перевозок, а также разработка про­блемно–ориентированных программных комплексов, реализующих разра­ботанные вычислительные алгоритмы.

.Для достижения поставленной цели решаются следующие задачи:1) разработка математической модели для решения задачи планиро­вания железнодорожных перевозок на этапе формирования бесконфликт­ного набора нормативных ниток. Исследование свойств неориентированно­го графа конфликтов и сведение исходной задачи к задаче расшифровкимонотонной булевой функции, порождённой неориентированным графом,2) исследование свойств максимального верхнего нуля и разработкавычислительного алгоритма формирования верхнего нуля монотонной бу­левой функции, порождённой неориентированным графом,43) разработка математической модели для решения задачи органи­зации железнодорожных перевозок на этапе назначения и перемещениялокомотивов без учёта ограничений на использование и техническое об­служивание локомотивов.

Исследование свойств ориентированного графасовместимости заданий на перевозку и сведение исходной задачи к зада­че минимального покрытия вершин ориентированного графа множествомпутей,4) исследование свойств минимального покрытия и разработка вы­числительного алгоритма покрытия вершин ориентированного графа мно­жеством максимальных по включению путей,5) разработка и тестирование программных комплексов, реализую­щих алгоритм формирования верхнего нуля монотонной булевой функции,порождённой неориентированным графом, и алгоритм покрытия вершинориентированного графа множеством максимальных по включению путей.Научная новизна. В рамках исследования получены следующиеновые результаты:1) разработана математическая модель для решения задачи планиро­вания железнодорожных перевозок на этапе формирования бесконфликт­ного набора нормативных ниток,2) доказано утверждение об оценке числа единиц в максимальномверхнем нуле и разработан вычислительный алгоритм формирования верх­него нуля монотонной булевой функции, порождённой неориентированнымграфом, и получена оценка вычислительной сложности разработанного ал­горитма,3) разработана математическая модель для решения задачи органи­зации железнодорожных перевозок на этапе назначения и перемещениялокомотивов без учёта ограничений на использование и техническое обслу­живание локомотивов,4) доказано утверждение о свойствах минимального покрытия и раз­работан вычислительный алгоритм покрытия вершин ориентированногографа множеством максимальных по включению путей.Практическая значимость.

Разработанные в диссертационной ра­боте вычислительные алгоритмы решения исследуемых задач лежат воснове программных комплексов для технических управляющих систем,реализация которых и внедрение в эксплуатацию позволит добиться су­щественного экономического эффекта в области рационального распре­деления ресурсов. В рамках исследования разработаны на языке VisualBasic проблемно–ориентированные программные комплексы «Алгоритмрасшифровки монотонной булевой функции, порождённой неориентиро­ванным графом» для решения задачи планирования железнодорожных пе­ревозок, и «Алгоритм покрытия вершин ориентированного графа множе­ством максимальных по включению путей» для решения задачи организа­ции железнодорожных перевозок.5Mетоды исследования. Для разработки математических моделейдля решения исследуемых задач используются методы теории графов. Дляразработки алгоритмов на графах, вычислительного алгоритма формиро­вания верхнего нуля монотонной булевой функции, порождённой неориен­тированным графом, а также для разработки вычислительного алгоритмапокрытия вершин ориентированного графа, используются методы комби­наторной оптимизации.

Для разработки проблемно–ориентированных про­граммных комплексов, реализующих алгоритмы решения исследуемых за­дач, и для проведения вычислительных экспериментов используются ком­пьютерные технологии.Достоверность полученных результатов обеспечивается использова­нием классического аппарата моделирования и адекватностью приложениявыбранной методологии в исследуемых задачах. Реализация посредствомкомпьютерных технологий подтверждает корректность разработанных ал­горитмов, кроме того, исходные данные для вычислительных эксперимен­тов отвечают реальным планам перевозок для существующих железнодо­рожных транспортных сетей и апробированы на примере оптимизации пла­нирования железнодорожных перевозок для Московской железной дороги,имеющей наиболее развитый и сложный граф сети среди всех дорог ОАОРЖД.Апробация работы.

Основные результаты работы докладыва­лись на следующих научных конференциях: 1) Международная научнаяконференция «Гагаринские чтения» (Москва, 2016, 2017), 2) Международ­ная научная конференция «Системный анализ, управление и навигация»(Евпатория, 2016, 2017), 3) Всероссийская научная конференция «Управ­ление большими системами» (Самара, 2016), 4) Международная научнаяконференция «Математика, информатика и физика и их приложения внауке и образовании» (Москва, 2016).Личный вклад. Автором работы сформулированы утверждение обоценке числа единиц в максимальном верхнем нуле монотонной булевойфункции, порождённой неориентированным графом, и утверждение о свой­стве специфического ориентированного графа, на основе которых, совмест­но с Гайнановым Д. Н., разработаны вычислительные алгоритмы решенияисследуемых задач. Посредством программных комплексов на языке VisualBasic автором реализованы разработанные алгоритмы, проведены вычис­лительные эксперименты и анализ полученных результатов.Публикации.

Основные результаты по теме диссертации изложеныв 11 работах, 4 из которых опубликованы в журналах, рекомендованныхВАК [1–4], в том числе 2 опубликованы в журналах, цитируемых между­народной базой Web of Science [1–2], 6 из которых опубликованы в тезисахдокладов [5–10], и 1 из которых — программа для ЭВМ [11].Объем и структура работы. Диссертация состоит из введения, че­тырех глав и заключения. Полный объем диссертации 128 страниц текста6с 11 рисунками и 2 таблицами. Список литературы содержит 71 наимено­вание.Содержание работыВо введении обоснована актуальность исследования, проводимогов рамках работы, приводится обзор существующих результатов по темеисследования, формулируется цель и задачи, решаемые в рамках достиже­ния цели работы, обоснована научная новизна и практическая значимостьработы, а также выбор методологии исследования.В первой главе приводятся основные понятия теории графов и свой­ства объектов теории графов, используемых в работе, разработаны теоре­тико–графовые модели для решения исследуемых прикладных задач пла­нирования и организации железнодорожных перевозок.Вводится в рассмотрение ориентированный граф железнодорожнойтранспортной сети→−Γ = (, ) ,где множество вершин = { : = 1,2, .