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

максимальном независимом множестве (1пйерепде|П Яе1) подходящего графа, а задача о назначении локомотивов — к задаче об оптимальном покрытии маршрутами ориентированного графа (Ра1Ь Сочег). Таким образом, предложенные и обоснованные в работе алгоритмы представляют интерес и в плане развития теории аппроксимируемости этих известных труднорешаемых Таким образом, актуальность тематики данного исследования и научная значимость полученных автором результатов ие вызывают сомнений, Краткая характеристика работы Диссертационная работа состоит из введения, четырех глав и заключения. Во введении автор обосновывает актуальность темы диссертационной работы, формулирует цель и задачи диссертации, приводит обзор текущего состояния исследований по тематике работы и кратко описывает содержание последующих глав. В первой главе автор приводит понятия бесконфликтного расписания, нормативной нитки, задания на ж.д.

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

ПоФ видимому, наибольший интерес представляют: Алгоритм 1, для которого обосновано достаточное условие, при котором он находит точное решение задачи; Алгоритмы 2 и З„яв иющиеся при обоснованном автором условии приближенными алгоритмами с фиксированной абсолютной оценкой точности и эвристический Алгоритм 4. В третьей главе приводится описание нового эвристического алгоритма для приближенного решения задачи об оптимальном назначении локомотивов.

Четвертая глава содержит более детальное описание представленных в предыдущих главах алгоритмов 1с описанием деталей их реализации на уровне блок-схем) и примеров, иллюстрирующих применение разработанных программных комплексов. В заключении автором подводятся итоги диссертационного исследования и перечисляются результаты, выносимые на защиту.

Основные результаты 1. Разработана математическая модель для задачи планирования грузовых железнодорожных перевозок в терминах бесконфликтных наборов нормативных ниток, основанная на редукции этой задачи к задаче о максимальном независимом множестве в подходящем графе. 2. Разработана математическая модель для задачи организации железнодорожных перевозок в терминах оптимального назначения локомотивов, базирующаяся на редукции данной прикладной задачи к задаче Рай Сонг об оптимальном покрьггии путями подходящего орграфа. 3.

Разработана серия приближенных полиномиальных алгоритмов и эвристик для каждой из перечисленных выше задач. 4. Разработаны программные комплексы, содержащие эффективные реализации предложенных алгоритмов. Практическая ценность Полученные в работе результаты могут быть использованы специалистами в области математического моделирования и дискретной оптимизации в ИММ УРО РАН, ИПУ РАН, ИМ СО РАН„а также при подготовке соответствующих специальных курсов для студентов УРФУ, МАИ, УрГУПС и др.

по специальности математическое моделирование и исследование операций. Предложенные в диссертации алгоритмы и разработанные программные комплексы могут быть использованы для решения актуальных прикладных задач планирования грузовых железнодорожных перевозок, например, в рамках Свердловской железной дороги. Замечания 1. Комментарий к Алгоритму 1 (Глава 2, стр, 45-46) представляется не вполне точным. Согласно тексту диссертации, в нем утверждается, что возможна одна из двух альтернатив: либо алгоритм найдет максимальный верхний нуль исследуемой булевой функции, либо задача может быть сведена к аналогичной для графа меньшего порядка.

В то же время нетрудно привести пример графа, применение к которому данного алгоритма не приведет ни к одному из перечисленных выше исходов. 2. В четвертой главе автор приводит результаты численного тестирования разработанных алгоритмов и программных комплексов. Традиционно для этой цели используются либо реальные содержательные постановки (в нашем случае, возникающие при планировании работы конкретной железнодорожной сети), либо тестовые задачи, представленные в одной из общеизвестных публичных библиотек, либо случайные экземпляры, полученные с использованием детально описанных генераторов.

Природа же постановок, использованных автором, осталась в работе нераскрытой. 3. Задачи 1поерепоеп1 Яе1 и Ра1п Со~ег, к которым автор сводит исследуемые железнодорожные постановки, хорошо известны в комбинаторной оптимизации. Представляет интерес проведение анализа производительности известных методов в сравнении с алгоритмами, предложенными автором на примере изучаемых в работе постановок, возникающих в реальных задачах железнодорожного планирования. Отметим, что высказанные замечания ни в коей мере не снижают высокой квалификационной оценки настоящей диссертационной работы. Кроме того, замечание 3, по-видимому, следует рассматривать как пожелание к продолжению исследований.

Заключение Диссертационная работа представляет собой завершенную и целостную научноисследовательскую работу, выполненную на высоком научном уровне. Полученные в работе результаты новы и представляют как теоретический, так и практический интерес. Диссертация удовлетворяет всем требованиям и.

9 «Положения о порядке присуждения ученых степеней», утвержденного Постановлениями Правительства РФ от 24 сентября 2013 года №842 и 21.04.2016 № 335, предъявляемым к диссертациям на соискание ученой степени кандидата физикоматематических наук по специальности - 05.13.18 «Математическое моделирование, численные методы и комплексы программ». Зав. отделом математи доктор физико-матема проф. РАН ! Г1одп!«с««э,'«виряю«« ч~~о««~ «и «-екрота«оь АМ"..4 УРО РАЙ ия, М.Ю. Хачай Диссертация обсуждена на семинаре отдела математического программирования ИММ УРО РАН 30 июня 2017 года, протокол №542. .