Герасименко Евгения Михайловна. Нахождение потоков в транспортных сетях в условиях нечеткости и частичной неопределенности

brief description

Герасименко Евгения Михайловна. Нахождение потоков в транспортных сетях в условиях нечеткости и частичной неопределенности: диссертация ... кандидата технических наук: 05.13.17 / Герасименко Евгения Михайловна;[Место защиты: Южный федеральный университет].- Таганрог, 2014.- 219 с.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
На правах рукописи

Герасименко Евгения Михайловна
НАХОЖДЕНИЕ ПОТОКОВ В ТРАНСПОРТНЫХ СЕТЯХ В УСЛОВИЯХ НЕЧЕТКОСТИ И ЧАСТИЧНОЙ НЕОПРЕДЕЛЕННОСТИ
Специальность:
05.13.17 - Теоретические основы информатики
Диссертация на соискание ученой степени
кандидата технических наук
доктор технических наук, профессор Боженюк А.В.
Таганрог 2014
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ 4
ГЛАВА 1 ПОТОКОВЫЕ ЗАДАЧИ В ТРАНСПОРТНЫХ СЕТЯХ В ЧЕТКИХ УСЛОВИЯХ 11
1.1 Основные понятия теории потоков 11
1.2 Описание методики расчета пропускных способностей дуг транспортной сети 12
1.2.1 Факторы, ведущие к постановкам потоковых задач в нечетких условиях 14
1.3 Нечеткая логика как основной инструмент оперирования неопределенностью 15
1.4 Потоковые задачи в транспортных сетях 21
1.4.1 Нахождение максимального потока в транспортной сети 21
1.4.2 Нахождение максимального потока в транспортной сети с учетом ненулевых нижних
потоковых границ 23
1.4.3 Нахождение потока минимальной стоимости в транспортной сети 24
1.4.4 Нахождение потока минимальной стоимости в транспортной сети с учетом ненулевых
нижних потоковых границ 27
1.5 Потоковые задачи в динамических транспортных сетях 28
1.5.1 Нахождение максимального потока в динамической транспортной сети с учетом нулевых
и ненулевых нижних потоковых границ 29
1.5.2 Нахождение потока минимальной стоимости в динамической транспортной сети с учетом
нулевых и ненулевых нижних потоковых границ 31
1.6 Выводы по главе 1 33
ГЛАВА 2 НАХОЖДЕНИЕ МАКСИМАЛЬНОГО ПОТОКА И ПОТОКА МИНИМАЛЬНОЙ СТОИМОСТИ В ТРАНСПОРТНОЙ СЕТИ В НЕЧЕТКИХ УСЛОВИЯХ 34
2.1 Нахождение максимального потока в транспортной сети с нечеткими пропускными
способностями 34
2.2 Методика выполнения арифметических операций над нечеткими числами 37
2.3 Нахождение максимального потока в транспортной сети с учетом ненулевых нижних и
верхних потоковых границ, представленных в нечетком виде 40
2.4 Нахождение потока минимальной стоимости в транспортной сети с нечеткими
пропускными способностями и стоимостями 47
2.4.1 Метод потенциалов для нахождения потока минимальной стоимости в транспортной сети с нечеткими пропускными способностями и стоимостями 50
2.5 Нахождение потока минимальной стоимости в транспортной сети с учетом нечетких
ненулевых нижних, верхних границ потоков и стоимостей 63
2.6 Выводы по главе 2 81
з
ГЛАВА З РЕШЕНИЕ ПОТОКОВЫХ ЗАДАЧ В ДИНАМИЧЕСКИХ ТРАНСПОРТНЫХ СЕТЯХ С НЕЧЕТКИМИ НИЖНИМИ, ВЕРХНИМИ ГРАНИЦАМИ ПОТОКОВ И СТОИМОСТЯМИ..83
3.1 Определение нечеткой динамической транспортной сети 83
3.2 Нахождение максимального потока в динамической транспортной сети с нечеткими
пропускными способностями, зависящими от времени 85
3.3 Нахождение максимального потока в динамической транспортной сети с учетом нечетких
ненулевых нижних и верхних потоковых границ, изменяющихся во времени 90
3.4 Нахождение потока минимальной стоимости в динамической транспортной сети с
зависящими от времени пропускными способностями и стоимостями, заданными в нечетком виде 110
3.5 Нахождение потока минимальной стоимости в динамической транспортной сети с учетом нечетких ненулевых нижних, верхних потоковых границ и стоимостей, зависящих от
времени 133
3.6 Выводы по главе 3 144
ГЛАВА 4 РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ, РЕАЛИЗУЮЩЕГО РЕШЕНИЕ ПОТОКОВЫХ ЗАДАЧ В ТРАНСПОРТНЫХ СЕТЯХ В НЕЧЕТКИХ УСЛОВИЯХ 146
4.1 Функциональное назначение разработанного программного модуля 146
4.2 Описание логической структуры программного модуля 149
4.3 Подготовка входных данных с использованием ГИС ObjectLand 152
4.4 Оценка временной сложности 152
4.5 Выводы по главе 4 153
ЗАКЛЮЧЕНИЕ 154
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ 156
ПРИЛОЖЕНИЕ А Численные примеры, реализующие решение потоковых задач 164
ПРИЛОЖЕНИЕ Б Свидетельство о государственной регистрации программ для ЭВМ 215
ПРИЛОЖЕНИЕ В Акты внедрения 216

bibliography

ЗАКЛЮЧЕНИЕ
Основной научный результат диссертационной работы заключается в разработанных методах нахождения максимального потока и потока минимальной стоимости в статических транспортных сетях, учитывающих нечеткий характер параметров сетей, а также наличие ненулевых нижних потоковых границ, и динамических транспортных сетях, в которых нижние, верхние границы потоков, стоимости перевозок, представленные нечетко, и параметры времени прохождения потока по дугам, могут меняться во времени. В ходе работы решены следующие научные задачи:
1. Разработаны и обоснованы методы нахождения максимального потока в транспортной сети с учетом нулевых и ненулевых нижних потоковых границ. Данные методы позволяют, в отличие от существующих, находить максимальный поток с учетом нулевых и ненулевых нижних и верхних границ потока, заданных нечетко.
2. Разработаны и обоснованы методы нахождения потока минимальной стоимости в транспортной сети, параметрами которой являются нулевые и ненулевые нижние, верхние границы потока и стоимости перевозок, которые позволяют, в отличие от существующих, находить поток минимальной стоимости с учетом нечетких нижних, верхних границ потока и стоимостей перевозок.
3. Разработаны методы нахождения максимального потока в динамической транспортной сети с нечеткими нулевыми и ненулевыми нижними и верхними границами потока, отличающиеся от аналогов тем, что позволяют учесть зависимость нечетких нижних и верхних границ потока от времени.
4. Разработаны и обоснованы методы нахождения потока минимальной стоимости в динамической транспортной сети с учетом нечетких пропускных способностей и стоимостей перевозок, отличающиеся от аналогов тем, что позволяют учесть зависимость нечетких пропускных способностей дуг сети и стоимостей перевозок от времени.
5. Разработаны методы нахождения потока минимальной стоимости в динамической транспортной сети с учетом ненулевых нижних границ потока, отличающиеся от аналогов тем, что позволяют учесть зависимость нечетких верхних границ потока, ненулевых нижних границ потока и стоимостей перевозок от времени.
6. Разработан программный модуль, применяемый при нахождении максимального потока с учетом нулевых и ненулевых нижних потоковых границ, заданных нечетко, и рассчитанный на использование совместно с ГИС ObjectLand. Приведена оценка временной сложности разработанных алгоритмов с помощью измерения времени работы их программной реализации для различных входных данных.
7. Разработанные в диссертации методы внедрены в научно-исследовательской деятельности НТЦ «Интех» ЮФУ, ЗАО «Интехгеотранс», а также ФГАОУ ВО «Южный
федеральный университет», что подтверждено актами о внедрении. По теме диссертации опубликовано 18 печатных работ, из них 8 статей в ведущих рецензируемых изданиях, рекомендованных ВАК