Введение к работе
Актуальность темы. Когда говорят о задачах математического программирования (планирования), то имеют в виду задачи оптимизации, возникающие в связи с попыткой повысить эффективность промышленных, транспортных, военных, вычислительных систем за счет рационального расходования тех или иных ресурсов. Предназначенная для этих целей математическая модель включает два основных компонента - множество допустимых планов (вариантов решений) D и целевую функцию /(), которая формализует критерий оптимальности. Таким образом, в модельном представлении задача математического программирования (оптимального планирования) есть задача вида extrf(x),
методы решения которой весьма разнообразны и зависят от типа множества D, свойств целевой функции и функций, определяющих ограничения задачи. Если эти функции линейные, то имеем задачу линейного программирования, которая является основой для решения многих задач, возникающих не только в приложениях, но и в теоретических исследованиях. Данная задача имеет ряд важных модификаций, для которых разработаны еще более эффективные алгоритмы, чем симплексный метод. Одна из модификаций - это задачи целочисленной дискретной оптимизации, порождаемые такими факторами, как неделимость ресурсов, наличие логических отношений и связей между переменными.
Ярким представителем данного класса задач является транспортная задача, классическую постановку которой изучали такие ученые, как П.Н. Коробов, И.Я. Бирман, А. В. Кузнецов, Н. И. Холод, Н.А. Орехов, Л. С. Костевич, Е.А. Горбунов. Стремление к учету некоторых дополнительных ограничений и условий приводит к специальным постановкам: транспортной задаче с фиксированными доплатами (Л.Е. Каменецкий, А.Г. Левин, А.А. Корбут) и задаче со случайными коэффициентами (И.И. Еремин, Х.А. Таха, В.И. Малыхин). Интервальная и нечеткая постановка данной задачи рассматриваются в работах П.Н. Коробова и Н.А. Орехова. Существует определенная взаимосвязь транспортной задачи с задачами потокового программирования (Д.Р. Фалкерсон), для решения которых используются алгоритмы теории графов.
Значительный интерес представляет транспортная задача на сети, к основным приложениям которой относится оптимизация железнодорожных перевозок, при этом карта железных дорог может рассматриваться как транспортная сеть с низкой проходимостью, поскольку число направлений перемещения в каждом узле ограничено. Данная задача обладает и другими особенностями: большая размерность; наличие приоритетов в исполнении заявок; влияние неопределенности, которая является следствием как «человеческого фактора», так
и случайных факторов, обусловленных влиянием внешних обстоятельств. С практической точки зрения, решение данной задачи позволит снизить расходы на перевозки по карте с низкой проходимостью и уменьшить риски принимаемых управленческих решений.
Таким образом, актуальность диссертационного исследования обусловлена необходимостью разработки модельных и алгоритмических решений, учитывающих перечисленные факторы как в постановке транспортной задачи, так и в подходах к ее решению.
Тематика диссертационной работы соответствует одному из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет» - «Вычислительные комплексы и проблемно-ориентированные системы управления».
Цель работы и задачи исследования. Целью диссертационной работы является разработка комплекса моделей и методов для оптимизации маршрутов на карте с низкой проходимостью как основы автоматизированной системы, предназначенной для максимизации экономического эффекта грузоперевозок.
Для достижения поставленной цели решались следующие задачи:
-
Анализ подходов к решению проблем, возникающих при оптимизации управления выбором маршрутов, постановка задач исследования и разработка требований к качеству принимаемых решений.
-
Разработка комплекса методов для решения задачи составления оптимальных маршрутов на основе методов поиска кратчайшего пути на карте низкой проходимости с учетом обхода препятствий.
-
Формирование комплекса моделей для формализации оптимизационных задач, учитывающих различные особенности формирования плана перевозок с максимальной эффективностью.
-
Разработка и тестирование программного комплекса, реализующего предложенные алгоритмы формирования оптимального плана перевозок и построения графиков движения по результатам расчетов.
Методы исследования основаны на дискретной математике, теории оптимизации, теории графов и теории нечетких множеств. При написании программного обеспечения использовалась технология объектно-ориентированного программирования.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
комплекс алгоритмов построения маршрутов, основанный на модификациях алгоритма А', волнового и муравьиного алгоритмов и позволяющий строить оптимальные маршруты на карте с квадратной сеткой и низкой проходимостью, учитывая клетки различной весовой стоимости;
рекомендации по выбору метода формирования начального плана пе-
ревозок, позволяющие учитывать особенности стоимостной матрицы, уровень оптимальности полученного плана, временной фактор;
комплекс моделей транспортной задачи, включающий модели с интервальным и нечетким представлением коэффициентов, что позволяет учитывать фактор неопределенности или приближенную информацию в планировании перевозок;
модель и метод оптимального планирования перевозок по критерию максимальной доходности, отличающиеся возможностью динамического формирования тела алгоритма построения маршрута при случайных возмущениях параметров и позволяющие не только обеспечить выполнение заявок, но и сформировать план в зависимости от желаемой экономической эффективности;
структура программного комплекса «CyberAnalysis Railways» для оптимизации плана и маршрутов грузоперевозок, отличающаяся наличием автоматизированного программного механизма регулирования точности решения задачи в зависимости от временных ограничений и позволяющая, помимо решения задачи, моделировать различные варианты развития событий для предварительного обсчета с помощью специальной подсистемы.
Практическая значимость работы. В рамках диссертационного исследования разработан программный комплекс «CyberAnalysis Railways», позволяющий решать задачи, связанные с оптимальным планированием грузоперевозок и составлением маршрутов, обеспечивающих своевременное выполнение заявок клиентов, с одной стороны, и максимальную доходность, с другой. Программный комплекс «CyberAnalysis Railways» может быть использован в качестве прототипа автоматизированной информационной системы промышленного назначения. Предложенные в диссертации модели и методы графического представления выходной информации значительно повышают степень восприятия результатов работы программного комплекса и могут найти практическое применение в компаниях, организующих грузоперевозки.
Область исследования. Содержание диссертации соответствует следующим пунктам паспорта специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ»:
-
Развитие качественных и приближенных аналитических методов исследования математических моделей;
-
Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента;
-
Комплексное исследование научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента.
Реализация и внедрение результатов работы. Теоретические результаты диссертации используются в учебном процессе ФГБОУ ВПО «Воронежский государственный технический университет» при чтении спецкурсов, выполнении дипломных проектов. Полученные в диссертации теоретические результаты и программный комплекс «CyberAnalysis Railways» используются для оптимизации и мониторинга перевозок в ООО «ТрансИнформ».
Апробация работы. Основные результаты, полученные в диссертационной работе, докладывались и обсуждались на международных и всероссийских конференциях: всероссийской конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2008-2011); VIII - XI международных научно-методических конференциях «Информатика: проблемы, методология, технологии» (Воронеж, 2008-2011); а также на научных конференциях Воронежского государственного технического университета и Воронежского государственного университета (Воронеж, 2009-2011).
Публикации. Основные результаты диссертации опубликованы в 13 научных работах, в том числе 2 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат следующие результаты: [1] - модификация муравьиного алгоритма; [2] - алгоритм решения транспортной задачи большой размерности; [3, 4, 5] - методы использования баз знаний и экспертных баз знаний в системах поиска; [6, 13] - проведение расчетов и численного исследования модели; [7, 8, 10, 11] - модифицированные алгоритм решения задачи поиска кратчайшего пути на карте; [9, 12] - методы решения транспортной задачи, основанные на нечеткой логике.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, содержащего 72 наименования. Основная часть работы изложена на 123 страницах, и содержит 42 рисунка и 13 таблиц.
