автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Нахождение потоков в транспортных сетях в условиях нечеткости и частичной неопределенности

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

Герасименко Евгения Михайловна

НАХОЖДЕНИЕ ПОТОКОВ В ТРАНСПОРТНЫХ СЕТЯХ В УСЛОВИЯХ НЕЧЕТКОСТИ И ЧАСТИЧНОЙ НЕОПРЕДЕЛЕННОСТИ

Специальность: 05.13.17 —Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Таганрог-2014 005557682

005557682

Работа выполнена в ФГАОУ ВО «Южный федеральный университет»

Научный руководитель:

Боженюк Александр Витальевич, доктор технических наук, профессор, ФГАОУ ВО «Южный федеральный университет», кафедра «Информационно-аналитические

системы безопасности», профессор

Официальные оппоненты:

Ковалев Сергей Михайлович, доктор технических наук, профессор, ФГБОУ ВПО «Ростовский государственный университет путей сообщения», кафедра «Автоматика и телемеханика на железнодорожном транспорте», профессор, г. Ростов-на-Дону

Чернов Андрей Владимирович, доктор технических наук, профессор, ФГБОУ ВПО «Ростовский государственный

строительный университет», кафедра «Прикладная математика и вычислительная техника», заведующий кафедрой, г. Ростов-на-Дону

Ведущая организация:

ФГБОУ ВПО «Ульяновский государственный технический университет», г. Ульяновск

Защита состоится «05» декабря 2014 г. в 14.30 на заседании диссертационного совета Д 212.208.21 при Южном федеральном университете по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344103, г.Ростов-на-Дону, ул. Зорге, 21 Ж.

Диссертация http://hub.sfedu.ru/diss/ar]

Автореферат

Ученый секретарь

диссертационного со^^^Э^^М.Й;, доктор технических

доступна по адресу:

Боженюк А.В.

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

Актуальность темы диссертационной работы

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

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

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

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

Решение данных задач опирается на теорию графов, которая представлена авторами Л. Форд, Д. Фалкерсон, Э. Майника, II. Кристофидес, Т. Ху, Дж. Эдмондс, Р. Карп, Р. Басакер, П. Гоуэн, М. Клейн,

Р. Ахыоджа, Дж. Орлин и другими авторами, а также на теорию нечетких множеств и нечеткой логики, представленную авторами Л. Заде, Х.-Ю. Диммерманн, А.Н. Мелихов, Л.С. Берштейн, А.Н. Борисов, Д. Дюбуа, Г. Прад и других авторов.

Цели и задачи диссертационной работы

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

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

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

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

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

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

Методы исследования опираются на применение теории нечеткой логики, а также теории графов.

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

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

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

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

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

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

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

Положения, выносимые на защиту

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

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

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

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

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

нечетким характером параметров транспортной сети, а также зависимостью верхних, нижних потоковых границ и стоимостей перевозок от времени.

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

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

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

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

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

Результаты диссертационной работы были использованы при выполнении грантов РФФИ: проект № 11-01-00011а «Решение оптимизационных задач в транспортных сетях в условиях нечеткости и частичной неопределенности», проект № 12-01-00032-а «Разработка принципов создания интеллектуальных геоинформационных систем для оптимизации поставок на основе нечётких темпоральных сетевых моделей», проект № 13-07-13103 офи_м_РЖД «Методы и средства образного представления знаний для принятия решений с использованием геоинформационных систем».

Апробация результатов диссертационной работы

Основные результаты диссертационной работы были представлены на различных международных и всероссийских конференциях: «Конгресс но интеллектуальным системам и информационным технологиям

«IS&IT'l 1»» (Россия, п. Дивноморское, 2011), «CDUD 2012 - Concept Discovery in Unstructured Data: Workshop co-located with the 10th International Conference on Formal Concept Analysis (ICFCA 2012)» (Belgium, Leuven, 2012), «The 10th International FLINS Conference on Uncertainty Modeling in Knowledge Engineering and Decision Making (FLINS 2012)» (Turkey, Istanbul, 2012), Тринадцатая национальная конференция но искусственному интеллекту с международным участием «КИИ-2012» (Россия, г. Белгород, 2012), «19th East West Fuzzy Colloquium 2012» (Germany, Zittau, 2012), VII Международная научно-техническая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Россия, г. Коломна, 2013).

Публикации

По результатам диссертационной работы опубликовано 18 печатных работ, из них 8 статей в журналах, входящих в перечень ВАК, одна монография, свидетельство об официальной регистрации программ для ЭВМ (№ 201461001 б).

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, выводов по главам, заключения, списка литературы и приложений. Основное содержание работы изложено на 163 страницах текста, содержит 59 рисунков и 7 таблиц. Список использованных источников включает 116 наименований. В приложениях содержатся численные примеры, иллюстрирующие работу разработанных методов нахождения потоков в транспортных сетях в условиях нечеткости и частичной неопределенности, свидетельство о государственной регистрации программы для ЭВМ, акты внедрения результатов работы.

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

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

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

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

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

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

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

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

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

Постановка задачи нахождения потока минимальной стоимости в транспортной сети с учетом ненулевых нижних потоковых границ в нечетких условиях задается как (1)-(3):

(1)

( V, ,Л'; )€.-!

х1иГ(х1) х•.сГ'Сг,)

Р,х, =5, -Р,Х,=1, (2)

4.<4<г7,,У(х„^)е2 (3)

В модели (1)-(3) с,у - стоимость перевозки единицы потока по дуге

(я:., .г ); - нечеткая величина потока, протекающего по дуге (х,.,ху); р

- заданное значение потока, стоимость перевозки которого необходимо минимизировать, Г - нечеткая нижняя граница потока, протекающего по дуге (х, ), г7у - нечеткая верхняя граница потока, протекающего по дуге

Для решения данной задачи осуществляется переход к графу без нижних потоковых границ согласно правилу 1. Правило 1

Перейдем от заданного нечеткого динамического графа <5 = (X, А), имеющего ненулевые нижние потоковые границы, к нечеткому графу О' = (Х\Л') без нижних границ потоков. Для этого вводим в исходный граф С искусственные источник 5 и сток / , дугу (г,5) с й* =оо, 11=0, с * = б. Для каждой дуги (х^х/) в О, у которой

1ЦФ б , вводим следующие изменения: 1) уменьшаем до йц =й& , 1и до б, с * = су . 2) вводим дуги и (*,,/') с границами потоков,

равными й*. = ¿7* . = Т., /! = / *. = б , стоимостями с*. = с . = 0 . Дуги,

1 3 X] X, Г У 5 Х; дг/ ^ тг <

имеющие только верхние границы потоков (пропускные способности),

вводятся в граф О* без изменений.

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

Определение 1

Нечеткая остаточная сеть для графа Сг = (X , А ) без нижних потоковых границ для решения задачи нахождения потока минимальной стоимости с учетом нечетких ненулевых нижних, верхних грант/ потоков

и стоимостей - это сеть = (Х'", А''), где Х"^ = X' с добавлением искусственных вершин - множество вершин нечеткой остаточной сети, а А р — {< / (х/1, х^') >} - нечеткое множество ребер сети О '',

построенное по следующим правилам: для всех дуг, если < , то

включаем соответствующую дугу в О '' с пропускной способностью й^' — й^ ~ , модифицированной стоимостью с)}И ' с^ . Для всех дуг,

если > 0, то включаем соответствующую дугу к О '' с пропускной

способностью й? — , модифицированной стоимостью с^ = —су .

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

Правило 2

Для всех дуг, если < Гс", то включаем соответствующую дугу в

Сг"(£) с пропускной способностью Щ - Щ модифицированной

стоимостью сЦ ~ с1}. Для всех дуг, если > /у, то включаем

соответствующую дугу в (}"{£,) с м'у — — , модифицированной

стоимостью с') = —с^ .

Доказана теорема 1. Теорема 1

Если максимальный поток минимальной стоимости в графе С равен сумме нижних границ потоков <т = ^■ следовательно, в

К

исходном графе (5 существует поток значения <х — .

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

условиях частичной неопределенности. Предлагается рассматривать задачи в нечетких динамических транспортных сетях, которые задаются согласно определению 2, в отличие от нечетких «стационарно-динамических» (определение 3), рассматриваемых в классической литературе по потокам.

Определение 2

Нечеткой динамической транспортной сетью называется транспортная сеть б = (Х,Л),где X = - множество вершин,

А = {< //, < > / < xj,xJ >},<х,,х, >е Х\рА < х1,х) > - нечеткое множество ребер, где /JA(xi,xj)- степень принадлежности ориентированного ребра <xi,xj > нечеткому множеству ориентированных

ребер А . Каждому ребру поставлены в соответствие два числа: зависящая от момента отправления потока пропускная способность ?7,-,■(#) и время

прохождения потока по дуге г,..(0), где Г = {0,1,...,/?}- момент

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

Нечеткой стационарно-динамической транспортной сетью называется транспортная сеть, представленная в виде нечеткого

ориентированного графа С = (Х,А), где X = (х,,х2,...,*„} - множество вершин, А = {< //-, < х,,X; > / < х,,xj >},<х,,х^ >е X2,/¿- <х,,ху > -нечеткое множество ребер, где /¿л(х,,х/) - степень принадлежности ориентированного ребра <X■,xJ > нечеткому множеству ориентированных ребер А. В качестве ¿J-4(x]УxJ) применяется нечеткая пропускная способность . При этом каждому ребру поставлено в соответствие время прохождения потока , а также задан временной горизонт Г = {0,1,...,/?}, определяющий, что все единицы потока, посланные из источника, должны прибыть в сток не позднее, чем во время р. Полагаем, что г;/ -

положительное число.

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

параметров сети от времени. Учитывая при этом четкий характер параметра времени прохождения потока по дугам динамической сети и нечеткий характер остальных параметров динамических транспортных сетей, приходим к постановкам потоковых задач в динамических транспортных сетях в условиях частичной неопределенности.

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

Разработаны и обоснованы методы нахождения потока минимальной стоимости в динамической транспортной сети, позволяющие учесть зависимость нечетких пропускных способностей дуг сети и стоимостей перевозок от момента отправления потока. Постановка задачи нахождения потока минимальной стоимости в динамической транспортной сети с учетом нечетких пропускных способностей и стоимостей перевозок, зависящих от момента отправления потока, представляет собой (4)-(8):

Мпппиге £ £ с,^ (0)^(0), V (*„*,) е А,в е Т, (4)

О-0(х,,х,)еЛ

Г Л

I £ Е ^{в-т^т =р{р),х1=з, (5)

0=0^ .=/-(*•,) х.еГ-'и,) ,

£ I !,(*)- Z

0=0 1 л,еГ(л:,) л-, еГ"'«»-,)

= 0,;е,. (6)

X Z Ш- Z

= -p(p),xi=t, (7)

0 < 1(в) < il,J (в)У(х„х..) е А,в е Т.

(8)

В модели (4)-(8) ctj (0) — стоимость прохождения единицы потока по дуге (хпх -) в момент отправления 0, ^ (0) - величина потока, покидающая вершину х. в момент времени 0, г7у(#) - пропускная способность дуги (Xj,Xj) в момент отправления 0, р{р) - заданное

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

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

Правило 3

Переходим от заданного нечеткого динамического графа С-{Х,А) к «развернутому во времени» на р интервалов нечеткому статическому графу 6 =(Хр,Ар) путем «растягивания во времени» исходного динамического графа за заданное количество временных интервалов путем создания отдельной копии каждой вершины х е X в каждый рассматриваемый момент времени в е Т . Множество вершин Xр

графа задается как Хр = {(х,,в): (х,,в) & X х 7"} . Множество дуг А ставит в соответствие дугам (х,, х;) а А исходного динамическою графа дуги, идущие из каждой пары «вершина-время» (х~,0) е X р в каждую пару «вершина-время» вида (ху О+ тг/ (О)), где xJ.eГ(xl) и Э = в + ти{в) < р . Пропускные способности дуг {¡(х^х^в^Э), соединяющие пары «вершина-время» (х., в) с (х^З) в , равны ( 0), стоимость перевозки ¿(х^х^О^З) единицы потока по дуге, соединяющей пару «вершина-время» (х,<9) с {х).,3 = в + г,.(в)), равна су(<9) Параметры времени прохождения потока г(х;,ху,£, 9), соединяющие пары

вершин (х„0) с (Xj, 3) в равны исходным в динамическом 1ра<[)е

■

Переходим от исходных стоимостей к «приведенным» согласно определению 4.

Определение 4

Пусть /?(х,(<9)),(л;,в) е Xр,/ = 1,...,п - некоторые заданные веса

вершин (потенциалы вершин). Зададим т.н. «приведенные» или уменьшенные стоимости, связанные с дугами остаточной сети:

Приведенные стоимости в нечеткой остаточной сети, построенной согласно «развернутому во времени» варианту динамического графа, задаются, как:

где модифицированные стоимости с*' ^¡^¿,0,3) задаются согласно потоку, идущему по дугам графа Ср и согласно правилу 4. Правило 4

Нечеткая остаточная сеть Ср = (Хр, Ар) строится по

«развернутой во времени» сети Ор в зависимости от величин потоков

в,Э), идущих по дугам последней следующим образом: если

|(х,, xJ, О,3) < йИ (х,, xJ,0, 3) для дуг, соединяющих пары «вершина-

время» (х.,0) с (х^,3) в (тр , то включаем дугу, соединяющую пары

«вершина-время» (х/',0) с парами «вершина-время» (х>] ,3) в Ср с остаточной пропускной способностью

?7"(х,.,x¡,0,3) = /7(х,-,х^0,3) — ^(х~,xJ,0,3), временем прохождения

потока по данной дуге т"(х],х,,3,0) = -т(х^х1,0,3) и приведенной

стоимостью с'т(х,,xJ ,0,3) = с"(х,,ху ,0,3)- л{х,(0)) + л(х/ (3)) , где

с"{х,,хпв,Э)=с(х1,х],в,3). Если %(Х1,Х;,0,3)> 0 для дуг,

соединяющих пары «вершина-время» (хп0) с (Xj,3) в Ор , то включаем

дугу, соединяющую пары «вершина-время» (х^1,3) с (х;",0) в Ор с

остаточной пропускной способностью й, х,. ,3,0) = £(х;, ,0,3), временем прохождения потока по данной дуге г" (.XV, х; ,3,0) = -г(х; ,х},0,3) и приведенной стоимостью

с'^,х1л9) = с4х^х1,9,в) + я{х£в))-л{х;(&)), где

В главе доказываются следующие свойства и леммы. Для некоторого цикла Н^ в справедливо:

2 с'{х„х;,в,9)= X сЧх.^ЛЭ).

(.г,.Х;,в,э)<ЕЙ>;

Свойство 1

Поток (х.,х^,9,3) оптимален только тогда, когда существует векторов потенциалов, такой что с" (,г;, .г;, в, 3) > 0 для

Для потока в, 3) и вершины (х. ,0) с X состояние

вершины (х.,9) задается согласно следующему выражению:

ё(х1,О) = р(х„0) + £ ¿¡{х„х},е,Э)- X (9)

(х, .хгв.Я)чЛр {х,.х,,Э.вЧЛр

Согласно выражению (9):

Если ё(хп9) > 0, то состояние в вершине называют излишком. Если ё(х. , 9) < 0, то состояние в вершине называют дефицитом. Если ё(х1,0) = 0, то состояние в вершине называют балансом. Делит 1

Предположим, что поток (х,,xj,в, 3) и потенциалы,

приписанные вершинам, удовлетворяют критерию оптимальности приведенных стоимостей

с'(х„xJ ,9,3) = с" (х,,X; ,9,3)- л(х,, 9) + Я(х,, 3) > б для

\/(х>',х>!,9,3)еЛ^. Для каждой вершины (х^ ,3) е X" пусть

у''(я,хпд,9) определяет длину кратчайшего нуги из (я в (х'- ,3) в

Сг"г , полагая с7 (л'(, .г; ,0,3) длинами путей. Тогда справедливы следующие свойства.

1. Поток с (х., х;. ,0,3) удовлетворяет критерию оптимальности

приведенных стоимостей по отношению к потенциалам согласно следующему выражению:

л (х., 3) = /гЦ, 3) - у" (s , Xj, д, 3) для V (Xj ,3)еХ.

2. Приведенные стоимости с* (x¡,xj,0,3) равны 0 для \/(Х;,ху.,0,3) е в кратчайшем пути от s к t'.

Лемма 2

Пусть поток ^(x¡,xj,0,3) и потенциалы, приписанные вершинам л, удовлетворяют критерию оптимальности приведенных стоимостей с'т (х,., Xj ,0,3) = с" (X,- ,х},0,3)- л(Х,, 0) + ñ{Xj ,3)> б для

V(xi,xj,0,3)eJp . Пусть ¿; (x¿,xj,0,3) - поток, полученный

увеличением потока вдоль кратчайшей цепи. Тогда поток Е, (x¡,Х-,0,3)

также удовлетворяет критерию оптимальности приведенных стоимостей по отношению к Л .

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

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

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

В заключении изложены основные результаты работы.

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

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

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

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

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

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

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

6. Разработан программный модуль, применяемый при нахождении максимального потока с учетом нулевых и ненулевых нижних потоковых границ, заданных нечетко, и рассчитанный на использование совместно с ГИС ОЬуесЛапё. Приведена оценка временной сложности разработанных алгоритмов с помощью измерения времени работы их программной реализации для различных входных данных.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК:

1. Божешок, А.В. Подход к нахождению максимального потока в нечеткой транспортной сети / А.В. Боженюк, И.Н. Розенберг, Е.М. Рогушина // Известия ЮФУ. Технические науки. 2011. - № 5 (118).- С. 83-88.

2. Герасименко, Е. Нахождение потока минимальной стоимости в транспортной сети методом ранжирования математического ожидания нечетких функций стоимостей / Е. Герасименко // Известия ЮФУ. Технические науки. - 2012. - № 4 (129). - С. 247-251.

3. Боженюк, А. Алгоритм нахождения нечеткого потока в транспортной сети с нечеткими стоимостями и пропускными способностями / А. Боженюк, Е. Герасименко, И. Розенберг // Известия ЮФУ. Технические науки. - 2012. - № 5 (130). - С. 118-122.

4. Боженюк, А. Разработка алгоритма нахождения максимального потока минимальной стоимости в нечеткой динамической транспортной сети / А. Боженюк, Е. Герасименко // Инженерный вестник Дона. - 2013. -№ 1.-12 с.

5. Боженюк, А.В. Определение потока минимальной стоимости в нечетком динамическом графе / А.В. Боженюк, Е.М. Герасименко, И.Н Розенберг // Известия Южного федерального университета. Технические науки.-2013,-№5. С. 149-154.

6. Bozhenyuk, A. Methods for Máximum and Mínimum Cost Flow Detennining in Fuzzy Conditions / A. Bozhenyuk, E. Gerasimenko // World Applied Sciences Journal (Special Issue on Techniques and Technologies). -2013. -Vol.22.-P. 76-81.-DOI: 10.5829/idosi.wasj.2013.22.tt.22143.

7. Bozhenyuk, A. FIows Finding in Networks in Fuzzy Conditions / A. Bozhenyuk, E. Gerasimenko // Supply Chain Management Under Fuzzines, Studies in Fuzziness and Soft Computing / Cengiz Kahraman and Basar Üztaysi (Eds). - Springer-Verlag Berlín Heidelberg, 2014. - Vol. 313. - Part III. - P. 269-291. - DOI: 10.1007/978-3-642-53939-8_12.

8. Герасименко, Е.М. Метод потенциалов для определения заданного потока минимальной стоимости в нечетком динамическом графе i Е.М. Герасименко // Известия Южного федерального университета. Технические науки. - 2014. - № 4. С. 83-89.

Свидетельство о государственной регистрации программы для

ЭВМ:

9. Герасименко, Е.М. Программа нахождения максимального потока в нечеткой транспортной сети: свидетельство о государственной регистрации программы для ЭВМ / Е.М. Герасименко // Свидетельство о

государственной регистрации программы для ЭВМ № 2014610016. Зарегистрировано в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности РФ от 09.01.2014.

Публикации в других изданиях:

10. Bozhenyuk, Л. Method of maximum llow finding in fuzzy temporal network / A. Bozhenyuk, E. Rogushira // European researcher. Multidisciplinary scientific periodical. - 2011. - № 5-1 (7). - P. 582-583.

11. Bozhenyuk, A. The method of the maximum flow determination in the transportation network in fuzzy conditions / A. Bozhenyuk, I. Rozenberg, E. Rogushina // Proceedings of the Congress on intelligent systems and information technologies «IS&IT'll». - Scientific publication in 4 volumes. - Moscow: Physmathlit, 2011. - Vol. 4. - P. 17-24.

12. Bozhenyuk, A. The methods of maximum flow and minimum cost flow finding in fuzzy network / A. Bozhenyuk, E. Gerasimenko, I. Rozenberg // Proceedings of the Concept Discovery in Unstructured Data (CDUD 2012): workshop co-located with the 10th International Conference on Formal Concept Analysis (ICFCA 2012), May 2012, Leuven, Belgium. - P. 1-12.

13. Bozhenyuk, A. The task of minimum cost flow finding in transportation networks in fuzzy conditions / A. Bozhenyuk, E. Gerasimenko, I. Rozenberg // Proceedings of the 10th International FLINS Conference on Uncertainty Modeling in Knowledge Engineering and Decision Making Word Scientific, Istanbul, Turkey, 26-29 August 2012. - P. 354-359.

14. Герасименко, E. Нахождение максимального потока в нечеткой динамической транспортной сети с нижними и верхними границами потоков / Е. Герасименко // Тринадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2012, (16-20 октября 2012 г., г. Белгород, Россия): Труды конференции. Т.З. - Белгород: Изд-во БГТУ, 2012. - С. 40-47.

15. Bozhenyuk, A. Algorithm of maximum dynamic flow finding in a fuzzy transportation network / A. Bozhenyuk, E. Gerasimenko, I. Rozenberg // Proceedings of East West Fuzzy Colloquium 2012 19tb Fuzzy Colloquium 5-7 September. - P. 125-132.

16. Герасименко, E.M. Нахождение максимального потока минимальной стоимости в нечеткой динамической транспортной сети с учетом нижних и верхних границ / Е.М. Герасименко // Интегрированные модели и мягкие вычисления в искусственном интеллекте: Сборник научных трудов VII-й Международной научно-технической конференции (Коломна, 20-22 мая 2013г.). - В 3-х томах. - Т1. - М.: Фнзматлит, 2013. -С. 410-419.

17.- Bozhenyuk, A. Algorithm for Monitoring Minimum Cost in Fuzzy Dynamic Networks / A. Bozhenyuk, E. Gerasimenko // Information Technology and Management Science. - 2013. - Vol. 16 (1). - P. 53-59. - DOI: 10.2478/itms-2013-0008.

18. Нечеткие методы управления потоками в геоинформационных системах / C.JI. Беляков, А.В. Боженюк, Л.А. Гинис, ЕМ. Герасименко. - Таганрог: Изд-во ЮФУ, 2013. - 176 с.

Личный вклад автора в работах, опубликованных в соавторстве: [1,3,6,11,12] — разработка математических моделей потоковых задач в нечетких условиях, модификация метода построения нечеткой остаточной сети для нахождения максимального потока и потока минимальной стоимости; методика оперирования нечеткими числами; [4, 5] — разработка математических моделей задач, введение правил перехода к «развернутому во времени» графу, построения нечеткой остаточной сети, перехода к графу с допустимым потоком; [7, 10,15] - разработка алгоритмов нахождения максимального потока с учетом нулевых и ненулевых нижних потоковых границ в динамических сетях; [13, 17, 18] -модификация алгоритмов нахождения максимального потока и потока минимальной стоимости для применения в нечетких условиях.

Соискатель H&1AJ — Герасименко Е.М.

Типогр. ИПК ЮФУ Заказ №/75?тир./^0экз.