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

ОТЗЫВ ОФИЦИАЛЬНОГО ОППОНЕНТА на диссертацию Рассказовой Варвары Андреевны «Математическое моделирование в задачах планирования и организации железнодорожных перевозок методами теории графов и комбинаторной оптимизации и численные методы их решения», представленной на соискание ученой степени кандидата физико- математических наук по специальности 05.13.18 — «Математическое моделирование, численные методы и комплексы программ» Актуальность темы диссертации. Прикладные задачи управления транспортными процессами характеризуются большой размерностью и комбинаторной сложностью. Подавляющее большинство задач планирования и организации железнодорожных перевозок являются ХР-трудными, поэтому нахождение точного решения представляется мало вероятным ~в предположении, что классы Р и МР не совпадают).

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

Многие задачи управления производственными и технологическими процессами могут быть описаны в терминах теории графов, в частности, в виде ориентированных и взвешенных графов. Таким образом, предложенный подход может быть применен для решения целого класса прикладных задач, что определяет актуальность темы диссертации. Достоверность положений приведенными математическими диссертации подтверждается доказательствами утверждений, !овцшй от„11-л м:,и, корректным применением математических методов и аппарата компьютерного моделирования.

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

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

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

По теме диссертации опубликовано 11 печатных работ, 4 из которых опубликованы в журналах из перечня ВАК. Полученные автором результаты были представлены на международных и всероссийских конференциях. Также был зарегистрирован комплекс программ для ЭВМ. Структура и содержание работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Во введении приводятся основные используемые понятия теории графов и комбинаторной оптимизации, В первой главе представлены результаты в области разработки математических моделей для решения исследуемых прикладных задач управления грузовыми железнодорожными перевозками.

Задача планирования сводится к задаче восстановления монотонной булевой функции, порожденной неориентированным графом, и задача организации сводится к задаче о покрытии вершин ориентированного графа минимальным числом путей. Во второй главе приводятся результаты разработки вычислительных алгоритмов для решения задачи формирования максимального верхнего нуля монотонной булевой функции, порожденной неориентированным графом.

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

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

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

Указанные замечания не снижают достоинств работы. Полученные результаты могут составить основу для дальнейшего исследования в области решения прикладных задач управления транспортными, производственными и технологическими процессами. Рассказова Варвара Андреевна владеет аппаратом математического моделирования, навыками разработки и компьютерной реализации численных методов решения сложных комбинаторных задач. Содержание диссертации в полной мере отражено в статьях, опубликованных в журналах из перечня ВАК.

Автореферат также в программ». Официальный оппонент заведующий лабораторией «Теории расписаний и дискретной оптимизации» ФГБУН «Институт проблем управления им. В. А. Трапезникова», доктор физико-математических наук 101.01.09— «Дискретная математика и математическая кибернетика»), профессор А.

А. Лазарев 117997, Москва, Профсоюзная ул., 65 тел.: 8 ~495) 334 — 87 — 51 е-пза11: ' Ь Ф '1 полной мере отражает содержание диссертации. Выполненная работа соответствует, на мой взгляд, требованиям Положения о присуждении ученых степеней, предъявляемых к кандидатским диссертациям, а ее автор— Рассказова Варвара Андреевна — заслуживает присуждения ей ученой степени кандидата физико-математических наук по специальности 05.13.18 — «Математическое моделирование, численные методы и комплексы .