автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Разработка моделей и методов оптимизации для транспортных сетей с низкой проходимостью

005006101

На правах рукописи

ВАСИЛЬЕВ Олег Вячеславович

РАЗРАБОТКА МОДЕЛЕЙ И МЕТОДОВ ОПТИМИЗАЦИИ ДЛЯ ТРАНСПОРТНЫХ СЕТЕЙ С НИЗКОЙ ПРОХОДИМОСТЬЮ

Специальность: 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

1 5 ЦЕН 2011

Воронеж-2011

005006101

Работа выполнена в ФГБОУ ВПО «Воронежский государственный технический университет»

Научный руководитель доктор технических наук, профессор

Леденева Татьяна Михайловна

Официальные оппоненты: доктор технических наук, профессор

Подвальный Евгений Семенович;

кандидат технических наук, доцент Гаршина Вероника Викторовна

Ведущая организация ФГБОУ ВПО «Воронежский государ-

ственный университет инженерных технологий»

Защита состоится 29 декабря 2011 г. в 13~ часов в конференц-зале на заседании диссертационного совета Д212.037.01 ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский просп., 14.

С диссертацией можно ознакомиться в научно-технической библиотеке ФГБОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан «29» ноября 2011 г.

Ученый секретарь диссертационного совета

Барабанов В.Ф.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Когда говорят о задачах математического программирования (планирования), то имеют в виду задачи оптимизации, возникающие в связи с попыткой повысить эффективность промышленных, транспортных, военных, вычислительных систем за счет рационального расходования тех или иных ресурсов. Предназначенная для этих целей математическая модель включает два основных компонента - множество допустимых планов (вариантов решений) D и целевую функцию /(•), которая формализует критерий оптимальности. Таким образом, в модельном представлении задача математического программирования (оптимального планирования) есть задача вида extr fix),

xeD V '

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

Ярким представителем данного класса задач является транспортная задача, классическую постановку которой изучали такие ученые, как П.Н. Коробов, И.Я. Бирман, А. В. Кузнецов, Н. И. Холод, H.A. Орехов, JI. С. Костевич, Е.А. Горбунов. Стремление к учету некоторых дополнительных ограничений и условий приводит к специальным постановкам: транспортной задаче с фиксированными доплатами (JI.E. Каменецкий, А.Г. Левин, A.A. Корбут) и задаче со случайными коэффициентами (И.И. Еремин, Х.А. Taxa, В.И. Малыхин). Интервальная и нечеткая постановка данной задачи рассматриваются в работах П.Н. Коробова и H.A. Орехова. Существует определенная взаимосвязь транспортной задачи с задачами потокового программирования (Д.Р. Фалкерсон), для решения которых используются алгоритмы теории графов.

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

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

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

Тематика диссертационной работы соответствует одному из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет» - «Вычислительные комплексы и проблемно-ориентированные системы управления».

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

Для достижения поставленной цели решались следующие задачи:

1. Анализ подходов к решению проблем, возникающих при оптимизации управления выбором маршрутов, постановка задач исследования и разработка требований к качеству принимаемых решений.

2. Разработка комплекса методов для решения задачи составления оптимальных маршрутов на основе методов поиска кратчайшего пути на карте низкой проходимости с учетом обхода препятствий.

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

4. Разработка и тестирование программного комплекса, реализующего предложенные алгоритмы формирования оптимального плана перевозок и построения графиков движения по результатам расчетов.

Методы исследования основаны на дискретной математике, теории оптимизации, теории графов и теории нечетких множеств. При написании программного обеспечения использовалась технология объектно-ориентированного программирования.

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

• комплекс алгоритмов построения маршрутов, основанный на модификациях алгоритма А', волнового и муравьиного алгоритмов и позволяющий строить оптимальные маршруты на карте с квадратной сеткой и низкой проходимостью, учитывая клетки различной весовой стоимости;

• рекомендации по выбору метода формирования начального плана пе-

ревозок, позволяющие учитывать особенности стоимостной матрицы, уровень оптимальности полученного плана, временной фактор;

• комплекс моделей транспортной задачи, включающий модели с интервальным и нечетким представлением коэффициентов, что позволяет учитывать фактор неопределенности или приближенную информацию в планировании перевозок;

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

• структура программного комплекса «CyberAnalysis Railways» для оптимизации плана и маршрутов грузоперевозок, отличающаяся наличием автоматизированного программного механизма регулирования точности решения задачи в зависимости от временных ограничений и позволяющая, помимо решения задачи, моделировать различные варианты развития событий для предварительного обсчета с помощью специальной подсистемы.

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

Область исследования. Содержание диссертации соответствует следующим пунктам паспорта специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ»:

1. Развитие качественных и приближенных аналитических методов исследования математических моделей;

2. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента;

3. Комплексное исследование научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента.

з

Реализация и внедрение результатов работы. Теоретические результаты диссертации используются в учебном процесса ФГБОУ ВПО «Воронежский государственный технический университет» при чтении спецкурсов, выполнении дипломных проектов. Полученные в диссертации теоретические результаты и программный комплекс «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 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

Доказано, что алгоритм А' гарантированно находит кратчайший путь, пока эвристическое приближение И(п) является допустимым, т. е. он никогда не превышает действительного оставшегося расстояния до цели. Также был сделан вывод, что этот алгоритм наилучшим образом использует эвристику: ни один другой алгоритм не раскроет меньшее число узлов, не учитывая узлов с одинаковой стоимостью.

Обычно данный алгоритм применяется на карте, где большинство клеток не являются препятствиями. Но на карте с низкой проходимостью препятствия составляют значительный процент от общего количества клеток. В связи с этим алгоритм А' был модифицирован: в случае отклонения в сторону «препятствия» более чем на две клетки он прекращает работу в данном направлении. Модифицированный алгоритм способен обработать карту, соизмеримую по масштабу с европейской частью России, за несколько часов и «запомнить» направления, в которых не следует идти из определенных точек, что, в конечном итоге, позволяет сократить время на обсчет пути.

Также во второй главе рассматривается муравьиный алгоритм, который

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

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

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

Далее необходимо провести поиск решения. Вероятность перехода из вершины / в вершину } определяется по следующей формуле:

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

Р11,к«) =

МОГ -\плр

IМОГ \пц\р'

где р - интенсивность испарения; 1к (/) - цена текущего решения для А:-го

муравья; £> - цена оптимального решения; —--феромон, откладываемый

¿а (О

к-и муравьем, использующим ребро (/,у).

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

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

Третья глава диссертации посвящена проблеме оптимизации грузоперевозок и определения расписания работы каждого объекта на расчетный период. Для ее решения предложены обобщения классической постановки транспортной задачи для интервальной и нечеткой исходной информации. Классическая транспортная задача формулируется следующим образом. Имеется т пунктов производства (поставщиков) и п пунктов потребления (потребителей) однородного продукта. Заданы величины: - объем производства (запас) г -го поставщика (/ = 1,ти); Ь] - объем потребления (спрос) _/-го потребителя (у' = 1,и); с,у - стоимость перевозки (транспортные затраты) единицы продукта от /-го поставщика к у'-му потребителю. Требуется составить такой план перевозок, который, с одной стороны, удовлетворил бы спрос всех потребителей, а с другой - минимизировал общую суммарную стоимость всех перевозок.

Классическая математическая модель транспортной задачи имеет вид

т п

¡=1 7=1

п _ т ___ _

IX = а, ('= !.«), (/= 1,«), х1у>о(г = 1,т,у = 1,п).

У=1 Ы1

Ее решение ищется в виде матрицы Х-{х^}тт, каждый элемент которой Хц равен количеству груза, перевозимого от /-го поставщика к у'-му потребителю. Решение транспортной задачи состоит из двух этапов: сначала строится первоначальный план перевозок, а затем он оптимизируется методом потенциалов. Для нахождения первоначального плана можно использовать не-

сколько методов: метод минимальной стоимости, метод двойного предпочтения, аппроксимация Фогеля, метод северо-западного угла. Для выбора подходящего метода формирования первоначального плана был проведен вычислительный эксперимент и сравнительный анализ перечисленных выше методов. Сравнение проводилось на тестовых примерах по трем критериям: сложность алгоритма, время построения опорного плана и уровень оптимальности опорного плана. Под сложностью алгоритма в данном случае понимается количество шагов, необходимых для создания опорного плана, и количество переменных, которым оперирует метод. Наиболее прост в программировании метод северозападного угла: он оперирует минимумом переменных, а количество шагов составляет (ш + и-1), где /ихп - размерность таблицы. Метод минимальной стоимости несколько сложнее, но ненамного: появляется переменная стоимости, проводится дополнительное сканирование транспортной таблицы (что до-ш + и

бавляет в среднем —-— шагов). Метод двойного предпочтения немногим отличается от метода минимальной стоимости, так как фактически является его усовершенствованной версией; однако приходится оперировать метками, так что он имеет более высокую сложность: количество шагов увеличивается в

т +п „ ,

—-—2 = т + п раз за счет многочисленных повторных сканировании таблицы. Наконец, метод аппроксимации Фогеля является самым сложным, так как для него необходимо введение еще двух дополнительных переменных и постоянные промежуточные вычисления, которые увеличивают количество шагов в среднем в два раза относительно метода двойного предпочтения.

Для сравнения перечисленных алгоритмов был проведен вычислительный эксперимент (25 матриц размерности матрицы 200x300, заполняется случайным образом). Результаты исследования скорости работы алгоритмов можно сформулировать следующим образом. Расчет по методу северо-западного угла занял около 2 секунд, по методу минимальной стоимости - 21 секунду, по методу двойного предпочтения - 37 секунд, по аппроксимации Фогеля - 52 секунды.

Следующий критерий, оценивающий уровень оптимальности опорного плана, зависит от времени, затраченного на его построение. В рамках того же эксперимента была выявлена следующая зависимость: если построение по методу аппроксимации Фогеля принять за единицу, то оптимальность по методу двойного предпочтения в среднем будет равна 0.79, по методу минимальной стоимости - 0.54, по методу северо-западного угла - 0.12. Таким образом, метод Фогеля позволяет получить допустимый план перевозок, который в наибольшей степени близок к оптимальному.

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

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

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

к-м типом транспорта, к = 1,1, с.к - стоимость перевозки единицы продукта от г -го поставщика к } -му потребителю посредством к -го типа транспорта. Необходимо определить количество хцк продукта, перевозимого от /'-го поставщика к у'-му потребителю посредством к-го типа транспорта, при этом суммарная стоимость должна быть минимальной. Данная задача является стандартной задачей линейного программирования, а ее математическая модель имеет следующий вид:

т п I 1=1 к=I

и / . т I т п _

=■ч ('"=Н> =ъ, (у=и), =*,(*=1,/),

где = >0(] = Щ,ек>0(к = й).

Существование решения данной задачи гарантируется выполнением уст п I

ловия баланса = =^ек, причем допустимое базисное решение со-

/=| к=I

держит (т + п + 1- 2) ненулевых значений переменных.

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

т п I 1=1 ув! к=I

и I __щ / ___ т п _

0 4 ('■ =Н' 12л 0 (•/ = !'")' 11% 0 = Ь/),

|Ы /=1 М .Н

х11к > 0 для всех /, у, к, где 4 для / = 1,т, В] = для 7=1,и, Ек = [ек,ёк\ для ¿ = 1,/ -

промежутки возможных значений мощностей поставщиков, запросов потребителей и ограничений на тип транспорта соответственно. Заметим, что вместо обычного равенства здесь используется отношение □, которое определяется правилом: /0 [а,/?] <=> Зге[а,/?](/ = г).

Таким образом, / 0 [«,/?] тогда и только тогда, когда I е [«,/?]. Учитывая этот факт, предыдущую задачу можно переписать в виде

т п / Ы\ j=1 к=I

п I _ т I _ т п _

!=1 /Ы

¡=1 4=1 1=1

хук > 0 для всех I, ], к .

Разрешимость данной задачи определяется условием баланса в виде АглВГЛЕФ0,

где А = =

Х&>2>.

м

. М >1

Заметим, что если а, = «,, /ь = Ь) и е* =ел, то получим классическую постановку.

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

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

Рассмотрим нечеткую постановку данной задачи.

Пусть а, = (а,., а„ 1щ,га), А, = (б,.Д, 1Ь,ГЬ:), ё1 = (е^Ц, ) - нечеткие числа, соответствующие объему продукции в пунктах производства, потребностям в пунктах потребления и объемам перевозок, осуществляемых данным видом транспорта. Модель имеет следующий вид:

1X1

/=1 у=1 4=1 т I

1 -111 4 ' ... . 4 '

;=1 4=1

>1 ;=1

х* > 0 для всех 1,},к,

где 1 =(1,1,0,0) нечеткое число «1», = - отношение равенства между нечеткими числами в виде нечеткого отношения с функций принадлежности /4 (*,_>>).

На основе теоремы декомпозиции нечеткая задача может быть записана в следующем виде:

С!Л* тт

/4

7=1 4=1 ,1 V /=1 4=1 )

т » _ Л _

ЕХЧ'Л (=1 >/), х.к > 0 для всех /,у,£, /■ е [0,г],

V >=1 >1

где

г = йирт1п|/4

I _ ^ (- I . .Л ( " . ^

ЕЕЦ»»« ££4*»®

V >=14=1 у V 1=1 4=1 у V ./=1 у J

т т " я I I

'=1 ¿=1 № >1 4=1 *=1

Таким образом, нечеткая ТТЗ сводится к системе интервальных задач.

В рамках проведенного вычислительного эксперимента было выяснено, что при использовании модели оптимизации грузоперевозок в форме транспортной задачи интервального типа можно повысить скорость расчетов почти на 50%, так как вместо нескольких проходов и сканирований транспортной таблицы вычисления производятся только один раз. Точность результата обоих типов задач одинакова. Ресурсные затраты для интервальной задачи в три раза ниже. Это обусловлено тем, что нет необходимости хранить гигантские объемы данных, как при работе классического алгоритма.

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

ставщиков», состоящие из станций выгрузки, потом - из станций ремонта и очистки, потом - из станций отстоя. Это позволяет определенным образом упорядочить матрицу стоимостей и приводит к уменьшению времени расчетов за счет уменьшения количества итераций.

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

В четвертой главе диссертации содержится описание программного комплекса «CyberAnalysis Railways», который состоит из следующих модулей:

- основной модуль «TransportTask», представляющий собой реализацию модифицированной транспортной задачи и определяющий глобальный план перевозок;

- основной модуль «BarrierMap», который работает над построением оптимальных локальных маршрутов и поиском кратчайшего пути с помощью модификации алгоритма А*;

- основной модуль «AntWay», в котором реализованы муравьиные алгоритмы для обработки различных типов местности с различным весовым коэффициентом (он требуется для работы с путями, которые имеют различную пропускную способность);

- вспомогательный модуль «WaveMap», который будет являться реализацией модификации волнового алгоритма для открытой карты и послужит для сравнения скорости результатов вычислений.

Структура работы алгоритма модуля формирования и оптимизации глобального плана перевозок представлена на рис. 3, структура работы алгоритма модуля прокладывания и оптимизации локальных маршрутов - на рис. 2.

Модчль разбиения карты на квадраты

Формирование локальных маршрутов

Модуль определения

проходимости квадратов

Модуль оптимизации пути алгоритмом А*

Оптимизация маршрута согласна проходимости

Рис. 2. Структура алгоритма прокладывания и оптимизации маршрутов

Модуль классической транспортной задачи

Модуль нечеткой транспортной задачи

Модуль оптимизации выходных данных

Формирование глобального плана перевшок

Вспомогательная подпрограмма "УУзуеМар"

Модуль анализа препятствий на карте

Модуль волнового алгоритма

Анализ правильности решения

Л

Оптимизация глобального плана перевозок

Подпрограмма вывода результатов

Рис. 3. Структура алгоритма формирования и оптимизации плана

Данный программный комплекс предназначен для а) формирования портфеля оптимальных направлений для грузоперевозок по железной дороге с помощью транспортной задачи; б) нахождения кратчайших локальных путей с помощью модулей «ВатегМар» и «Аги\¥ау»; в) построения графиков движения для каждого вагона, которые позволяют определить местонахождение каждого вагона в любой момент времени еще на стадии составления плана перевозок, что повышает эффективность диспетчерской службы.

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

Рис. 4. Подпрограмма моделирования транспортной сети

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

5. Разработан программный комплекс «CyberAnalysis Railways», включающий в себя разработанные системы взаимодействия методов поиска крат-

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

Основные результаты диссертации опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ:

1. Васильев О.В. Модифицированный алгоритм муравьиных колоний для решения задачи коммивояжера / О.В. Васильев, Т. М. Леденева // Системы управления и информационные технологии. -2011,- №3.2 - С. 45-55.

2. Васильев О.В. Транспортная задача и оптимизация грузоперевозок / О.В. Васильев, Т. М. Леденева // Вестник Воронежского государственного технического университета. -2011. - Т. 7, №11.1. - С. 82-84.

Статьи и материалы научных конференций:

3. Васильев О.В. Проблема концептуально-ориентированного информационного поиска в базах данных / О.В. Васильев, Т. М. Леденева // Новые технологии в научных исследованиях, проектировании, управлении, производстве: труды Всерос. конф. Воронеж: ВГТУ, 2008. - С. 177-178.

4. Васильев О.В. Базы знаний в интеллектуальных информационных системах / О.В. Васильев, Т. М. Леденева // Информатика: проблемы, методология, технологии: материалы VIII междунар. науч.-метод. конф. - Воронеж: ВГУ, 2008.-Т. 1.-С. 96-99.

5. Васильев О.В. Экспертные базы знаний в системе CB1R / О.В. Васильев, Т. М. Леденева // Новые технологии в научных исследованиях, проектировании, управлении, производстве: труды Всерос. конф. Воронеж: ВГТУ, 2009. -С. 176-177.

6. Васильев О.В. Применение системы интеллектуального поиска CBIR /

0.В. Васильев, Т. М. Леденева // Информатика: проблемы, методология, технологии: материалы IX междунар. науч.-метод. конф. - Воронеж: ВГУ, 2009. - Т.

1.-С. 150-153.

7. Васильев О.В. Алгоритм поиска кратчайшего пути на карте / О.В. Васильев, Т. М. Леденева // Информатика: проблемы, методология, технологии: материалы X междунар. науч.-метод. конф. - Воронеж: ВГУ, 2010. - Т. 1. — С. 428-429.

8. Васильев О.В. Интеллектуальный поиск объектов на карте / О.В. Ва-

сильев, Т. М. Ледеиева, A.A. Дубинин // Новые технологии в научных исследованиях, проектировании, управлении, производстве: труды Всерос. конф. Воронеж: ВГТУ, 2010. - С. 178-179.

9. Васильев О.В. Моделирование нечеткой системы электрокардиографической диагностики / О.В. Васильев, Т. М. Леденева, A.A. Дубинин // Информатика: проблемы, методология, технологии: материалы X междунар. науч,-метод. конф. - Воронеж: ВГУ, 2010. - Т. 1. - С. 430-433.

10. Васильев О.В. Технология GoogleMaps в RRWMap / О.В. Васильев, Т. М. Леденева // Информатика: проблемы, методология, технологии: материалы XI междунар. науч.-метод. конф,-Воронеж: ВГУ, 2011.-Т. 1.-С. 144-146.

11. Васильев О.В. Муравьиные алгоритмы и оптимальный путь / О.В. Васильев, Т. М. Леденева // Новые технологии в научных исследованиях, проектировании, управлении, производстве: труды Всерос. конф. Воронеж: ВГТУ, 2011.-С. 176-177.

12. Васильев О.В. Свойства метода Мариноса для анализа функций нечетких переменных / О.В. Васильев, Т. М. Леденева, A.A. Дубинин // Информатика: проблемы, методология, технологии: материалы XI междунар. науч.-метод. конф. - Воронеж: ВГУ, 2011. - Т. 1. - С. 433-436.

Зарегистрированные программные модули:

13. Васильев О.В. Программный модуль «Оболочка для создания и редактирования банка карт» / О.В. Васильев, Т. М. Леденева // ФГУП ВНТИЦ. Per. №50200801160 от 04.06.2008. Москва, ВНТИЦ, 2008.

Подписано в печать 29.11.11. Формат 60x84 !/,6. Усл. псч. л. 1. Тираж 90 экз. Заказ 1521.

Отпечатано с готового оригннал-макета в типографии Издательско-полиграфичсского центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3

Введение

1. Оптимизация железнодорожных перевозок

1.1 Сущность проблемы перевозок

1.2 Алгоритмы для оптимизации маршрутов перевозок

1.3 Цели и задачи исследования

2. Реализация поиска кратчайшего пути

2.1 Волновой алгоритм

2.2 Реализация анализа препятствий и их обхода

2.3 Муравьиные алгоритмы в поиске оптимального пути

3. Транспортная задача в оптимизации маршрутов перевозок

3.1 Математическая модель транспортной задачи

3.2 Нахождение опорного плана транспортной задачи

3.3 Оптимизация опорного плана

3.4 Нечеткая и трехиндексная транспортная задача

4. Программный комплекс «CyberAnalysis Railways»

4.1. Основа программного комплекса

4.2 Модуль «TransportTask»

4.3 Модуль «BarrierMap»

4.4 Модуль «WaveMap» 116 Заключение 121 Литература

Актуальность темы. Когда говорят о задачах математического программирования (планирования), то имеют в виду задачи оптимизации, возникающие в связи с попыткой повысить эффективность промышленных, транспортных, военных, вычислительных систем за счет рационального расходования тех или иных ресурсов. Предназначенная для этих целей математическая модель включает два основных компонента — множество допустимых планов (вариантов решений) D и целевую функцию /, которая формализует критерий оптимальности. Таким образом, в модельном пред> . ставлении задача математического программирования (оптимального планирования), методы решения которой весьма разнообразны и'зависят от типа множества D, свойств целевой функции и функций; определяющих ограничения задачи. Если эти функции линейные, то имеем задачу линейного, программирования, которая является'основой для решения многих задач, возникающих не только в приложениях, но и в теоретических исследовани- , ях. Данная задача имеет ряд важных модификаций, для которых разработаны еще более эффективные алгоритмы, чем симплексный метод. Одна из. модификаций — это задачи целочисленной дискретной оптимизации, порождаемые такими факторами как неделимость ресурсов, наличие логических. отношений и связей между переменными.

Ярким представителем данного класса задач является транспортная задача, классическую постановку которой изучали такие ученые, как П.Н. Коробов, И.Я. Бирман, А. В. Кузнецов, Н. И. Холод, H.A. Орехов, JI. С. Кос-тевич, Е.А. Горбунов. Стремление к учету некоторых дополнительных ограничений и условий приводит к специальным постановкам: транспортной задаче с фиксированными доплатами (Каменецкий JI.E., А.Г. Левин, Корбут

A.A.) и задаче со случайными коэффициентами (Еремин И.И., Х.А. Taxa,

B.И. Малыхин). Интервальная и нечеткая постановка данной задачи рассматриваются в работах П.Н. Коробова и H.A. Орехова. Существует определенная взаимосвязь транспортной задачи с задачами потокового программирования (Д.Р. Фалкерсон), для решения которых используются алгоритмы теории графов.

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

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

Тематика диссертационной работы соответствует одному из основных научных направлений Воронежского государственного технического университета - «Вычислительные комплексы и проблемно-ориентированные системы управления».

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

Для достижения поставленной цели решались следующие задачи:

- анализ подходов к решению проблем, возникающих при оптимизации управлениявыбором-маршрутов,-постановка задач исследования и разработка: требований к качеству принимаемых решений.

- разработка комплекса методов для решения задачи;^составлениямоптимальных маршрутов, на;основе методов поиска кратчайшего пути на карте низкой-проходимости с учетом обхода препятствий.

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

- разработка и тестирование программного комплекса, реализующего предложенные алгоритмы формирования оптимального плана перевозок и построения графиков движения по результатам расчетов.

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

Научная новизна.

В диссертации.получены следующие результаты, характеризующиеся научной новизной:

- комплекс моделей для транспортной задачи, отличающейся применением, мод ел ей с интервальным и нечетким представлением коэффициентов; что позволяет учитывать фактор неопределенности или приближенную информацию в планировании перевозок;

- комплекс алгоритмов построения маршрутов, основанный на модификациях алгоритма А*, волнового и муравьиного алгоритмов и позволяющий строить оптимальные маршруты на карте с квадратной сеткой и низкой проходимостью, учитывая клетки различной весовой стоимости;

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

- структура программного комплекса «CyberAnalysis Railways» для оптимизации плана и маршрутов грузоперевозок, отличающаяся наличием автоматизированного программного механизма регулирования точности решения задачи в зависимости от временных ограничений и позволяющего, помимо решения задачи, моделировать различные варианты развитиясобы-тий для предварительного обсчета с помощью специальной.подсистемы.

Практическая значимость работы.

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

Область исследования.

Содержание диссертации соответствует следующим пунктам паспорта специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ».

3.Развитие качественных и приближенных аналитических методов исследования математических моделей;

5. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента;

6. Комплексное исследование научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента.

Реализация и внедрение результатов работы.

Теоретические результаты диссертации используются в учебном процессе Воронежского государственного технического университета при чтении спецкурсов, выполнении дипломных проектов. Полученные в диссертации теоретические результаты и программный комплекс «CyberAnalysis Railways» используются для оптимизации и мониторинга перевозок в ООО «ТрансИнформ».

Апробация работы.

Основные результаты, полученные в диссертационной работе, докладывались и обсуждались на международных и всероссийских конференциях: Всероссийская конференция «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2008-2011гг.); VIII - XI Международная научно-методическая конференция «Информатика: проблемы, методология, технологии» (Воронеж, 2008-2011гг.); а также на научных конференциях Воронежского государственного технического университета и Воронежского государственного университета.

Публикации. Основные результаты диссертации опубликованы в 13 научных работах, в том числе 2 - в изданиях, рекомендованных ВАК РФ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, содержащего 72 наименования. Основная часть работы изложена на 123 страницах, и содержит 42 рисунка и 13 таблиц.

Выводы.

1. Разработан программный комплекс «CyberAnalysis Rail Ways», предназначенный для оптимизационных расчетов для маршрутов грузоперевозок на карте низкой проходимости.

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

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

121

ЗАКЛЮЧЕНИЕ

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

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

В качестве практически-прикладного результата был разработан программный комплекс, реализующий^предложенные алгоритмы: создание плана перевозок, его оптимизацию, построение графиков движения вагонов по результатам расчетов. Данный программный комплекс «СуЬегАпа1уз1з ЯаП\Уауз» может быть использован в качестве прототипа АИС промышленного назначения. В данное время он используется для оптимизации и мониторинга железнодорожных перевозок в ООО «Трансинформ».

122

1. Агаев Р. П. Модели обобщенного интервального выбора : Диссертация . канд. техн. наук: 05.13.10. -М.: ИЛУ РАН, 1995.-153 с.

2. Алескеров Ф.Т. Пороговая полезность, выбор и бинарные отношения // Автоматика и телемеханика. — 2002. № 3. С. 8-27.

3. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987.-360 с.

4. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях. Тюмень: Изд-во ТГУ, 2000. 352 с.

5. Афанасьев В.Н., Колмановский В.Б., Носов В.Р. Математическая теория конструирования систем управления : Учебник для вузов М.: Высшая школа, 1998.-574 с.

6. Ашманов С.А. Линейное программирование. М.: Наука, 1981. 304с.

7. Ащепков JT.T. Редукции интервальной задачи нелинейного программирования // Журн. вычисл. матем. и матем. физики. 2006. Т. 46. — № 7.-С 1248-1256.

8. Ащепков Л.Т., Гуторова C.B., Карпачев A.A., Ли С. Интервальные матричные игры // Дальневосточный математический журнал. 2003. Т.4. -N2.-C. 276-288.

9. Ащепков Л.Т., Давыдов Д.В. Показатель интервального неравенства: свойства и применение // Вычислительные технологии. 2006. Том 11. — №4.-С. 13-22.

10. Ащепков Л.Т., Давыдов Д.В. Редукции интервальных некооперативных игр // Журн. вычисл. матем. и матем. физики. — 2006. — Т. 46. — № 11. С. 2001-2008.

11. Ащепков Л.Т., Давыдов Д.В. Стабилизация линейной стационарной системы управления с интервальными коэффициентами // Дальневосточный математический сборник. 1999. № 8. - С. 32-38.

12. Ащепков Л.Т., Давыдов Д.В. Стабилизация наблюдаемой линей-ной.системы управления с постоянными интервальными коэффициентами // Изв. ВУЗов. Математика. 2002. № 2 (477). - С. 11-17.

13. Ащепков Л:Т., Давыдов Д.В. Универсальные решения интервальных задач оптимизации исправления. М.: Наука; 2006. -151 с.

14. Ащепков Л.Т., Долгий Д.В. Управление линейными многошаговыми системами в условиях неопределенности // Дальневосточный математический сборник. 1997. Вып. 4. - С. 95-104.

15. Ащепков Л.Т., Колпакова Г.Э., Стегостенко Ю.Б. Стабилизация нестационарной линейной дискретной системы управления с интервальными коэффициентами по наблюдениям фазовых состояний // Автоматика и телемеханика. 2002. № 5. - С. 3-11.

16. Ащепков Л.Т., Косогорова И:Б. Минимизация квадратичной функции с интервальными коэффициентами^// Журн. вычисл. матем. и матем. физики. -2002. Т.42. № 5. - С. 653-664;

17. Ащепков Л.Т., Стегостенко Ю.Б. Стабилизация линейной дискретной системы управления с интервальными коэффициентами // Изв. вузов. Математика. 1998. -№ 12 (439). С. 3-10.

18. Ащепков Л.Т., Стегостенко Ю.Б. Стабилизация наблюдаемой'линейной дискретной системы с интервальными коэффициентами^// Автоматика и телемеханика. 1999. № 7. - С. 85-95.

19. Боровков A.A. Теория вероятностей: — М.: Наука, 1986. 432 с.

20. Бирман И.Я. Транспортная задача линейного программирования. — М.: Экономиздат, 1959. 346 с.

21. Бирман И.Я. Транспортная.задача линейного программирования.

22. М.: Экономиздат, 1959. 346 с.

23. Бирман И.Я. Оптимальное программирование. — М.: Экономика, 1968.- 152 с.

24. Бирман И.Я. Методология оптимального планирования. —М.: Экономика, 1968. 281 с.

25. Бирман И.Я. Применение математики и электронной техники в планировании. — М.: Изд-во экономической литературы, 1961. 129 с.

26. Бирман И.Я. Методические указания по определению оптимальных схем перевозок, снабжения и размещения предприятий с помощью линейного программирования. — М.: Экономика, 1964. 410 с.

27. Бирман И.Я. Математические методы и проблемы размещения производства. — М.: Экономика, 1963. 385 с.

28. Бирман И.Я. Оптимальный план отрасли. — М.: Экономика, 1970.- 267 с.

29. Булавский В .А., Звягина P.A., Яковлева М.А. Численные методы линейного программирования. М.: Наука, 1977. 367 с.

30. Вагнер Г. Основы исследования операций :: В 3-х тт. —М.: Мир, 1972. -Т.1.-336 с.

31. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998.- 176 с.

32. Васильев О.В., Леденева Т.М. Транспортная задача с интервальными входными данными // Вестник БГТУ им. В'.Г. Шухова. 2011. - № 5 -С. 39-47.

33. Васильев О.В., Леденева Т.М. Технология GoogleMaps в RRWMap // Информатика: проблемы, методология, технологии. Материалы XI международной научно-методической конференции — Воронеж: Воронежский государственный университет, 2011. — Т. 1. — С. 144—146.

34. Ватолин A.A. О задачах линейного программирования с интервальными коэффициентами // Журн. вычисл. матем. и матем. физики. 1984. -Т.24. -№ 11.-С. 1629-1637.

35. Ватолин A.A. О линейных моделях с неоднозначно заданной информацией / Методы выпуклого программирования и некоторые приложения : Сб. науч. трудов. — Свердловск, 1992. — С. 3-18.127 ■ .

36. Facc С. Линейное программирование (методы и приложения). М.: Физматгиз, 1961.-303 с.

37. Голылтейн ЕЛ'., Юдин Д.Б. Новые направления в линейном программировании. М.: Сов. радио, 1966. - 524 с.

38. Давыдов Д.В. Идентификация параметров линейных интервальных управляемых систем с интервальным наблюдением // Известия РАН. Теория и системы управления. -2008. -№ 6. С. 25-29.

39. Давыдов Д.В. Локальная,стабилизация»интервально наблюдаемой системы с неопределенными параметрами1// Вычислительные технологии. -2003.-Т. 8. -№ 1. С.44-51.

40. Давыдов Д.В. Локальная стабилизация интервально наблюдаемой системы с неопределенными параметрами / Конференция молодых ученыхпо математике, математическому моделированию и информатике.Тез. док»ладов. Новосибирск, 2001. С. 24.

41. Давыдов Д.В. Методология принятия экономических решений с позиций субъективной неопределенности // Вестник Российской экономической академии им. Г.В. Плеханова. 2009. № 2(26). - С. 111 -120.

42. Давыдов Д.В. Некоторые подходы к решению интервальной трансIпортной задачи / III Всероссийская конференция^«Проблемы оптимизации и экономические приложения». Тезисы докладов. Омск, 2006. -С. 86.

43. Люгер Д; Интеллект машины. — М.: Мир, 2003. — 690 с.

44. Катречко С.Л». От логических исчислений к интеллектуальнымсистемам. — М.: МГУ, 2006. — 183 с.

45. Кононенко И.С., Сидорова Е.А. Обработка и распознавание изображений. —7 М.: "Логос", 2004. — 115 с.

46. Кузин Е. С. Концепция информационной'технологии функцио-нально-ориентирован-ного проектирования прикладных информационных систем. — М.: МГУ, 2006. — 183 с.

47. Найман B.C., Скрылев В.В. GPS-навигация. М: NT Press, 2010.384 с.

48. Седжвик Р. Фундаментальные алгоритмы на С. Алгоритмы на графах. — СПб.: ДиаСофтЮП, 2003. — 480 с.

49. Стокман Д, Шапиро Л.Компьютерное зрение. — М.: Бином, 2006. — 752 с.

50. Bonavear Е., Dorigo M. Swarm Intelligence: from Natural to Artificial Systems.- Oxford University Press, 1999.- 307 c.

51. Caro G. D., Dorigo M. Anet: a Mobile Agents Approach to Adaptive Routing. Technical Report IRIDA 97-12. IRIDA Universite Libre de Brusseles.-Brussels, Belgium, 1997.- 27 c.

52. Cherix D. Note préliminaire sur la structure, la phenologie et le regime alimentaire d'une super-colonie de Formica lugubris Zett. // Insects Sociaux 27, 1980. c. 226-236.

53. Corne D., Dorigo M., Glover F. New Ideas in Optimization.- McGrav-Hill, 1999.

54. Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization// Reader for CEU Summer University Course «Complex System».- Budapest, Central European University, 2001.- с. 1-38.

55. Reimann M. Ant Based Optimization in Good Transportation. PhD Thesis. University of Vienna.- Vienna, Austria, 2002.- 149 c.

56. ОБЩЕСТВО С ОГРАНИЧЕННО ОТВЕТСТВЕННОСТЬЮ «Транс Информ» (ООО «Транс Информ»)1. T*F>AHCZ І/іНФар1. НФОРМ

57. Почтовый адрес: 394030, г. Воронеж, ул. Пограничная, 2 тел. (473) 260-65-55, 261-02-23; факс (473) 261-02-24 e-mail: info@transinform.vrn.ru