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

• Автор: Ястребинская, Дина Николаевна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Таганрог
• Количество страниц: 229 с. : ил.

ВВЕДЕНИЕ.
ГЛАВА 1. ИСПОЛЬЗОВАНИЕ ГЕОИНФОРМАЦИОННЫХ СИСТЕМ ПРИ РЕШЕНИИ ОПТИМИЗАЦИОННЫХ ЗАДАЧ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

1. Г Поня тие геоинформационнон системы

1.2. Представление нечетких данных в ГИС

1.3. Построение графовых моделей транспортных сетей.

1.4. Решение оптимизационных задач в транспортных сетях с помощью ГИС

1.5.Выводы по главе 1.

ГЛАВА 2. ОПРЕДЕЛЕНИЕ ЖИВУЧЕСТИ ТРАНСПОРТНОЙ СЕТИ

2.1. Понятие живучести транспортной сети

2.2. Определение степени живучести транспортной сети, представленной нечетким графом второго рода.
2.3. Нахождение степени живучести транспортной сети, представленной нечетким графом второго рода.
2.4. Увеличение степени живучести транспортной сети, представленной нечетким графом второго рода.
2.5. Увеличение степени живучести транспортной сети с минимальными затратами.
2.5.1. Увеличение степени живучести транспортной сети, представленной нечетким графом первого рода, с минимальными затратами.
2.5.2. Увеличение степени живучести транспортной сети, представленной нечетким графом второго рода, с минимальными затратами.
2.6. Выводы по главе
ГЛАВА 3. НАХОЖДЕНИЕ ЦЕНТРОВ ОБСЛУЖИВАНИЯ И МАКСИМАЛЬНЫХ ПОТОКОВ В СЕТЯХ С ЗАДАННОЙ С ТЕПЕНЬЮ ЖИВУЧЕСТИ
3.1. Нахождение центров обслуживания в транспортной ееги с наибольшей степенью живучести
3.2. Алгоритм нахождения центров обслуживания транспортной сети, представленной нечетким графом второго
3.3. Нахождение центров обслуживания в транспортной сети, представленной нечетким интервальным графом
3.4. Определение максимального потока в транспортной сети с заданной степенью живучести.
3.5. Выводы по главе
ГЛАВА 4. ПРИЛОЖЕНИЕ РАЗРАБОТАННЫХ МЕТОДОВ И АЛГОРИТМОВ ОПРЕДЕЛЕНИЯ ЖИВУЧЕСТИ И НАХОЖДЕНИЯ ЦЕНТРОВ ОБСЛУЖИВАНИЯ В ТРАНСПОРТНОЙ СЕТИ
4.1. Описание реализации рассматриваемых задач с нечеткими исходными данными.
4.2. Модуль работы с ГИС . Извлечение информации из пространственной БД.
4.2.1. Работа с ГБД.
4.2.2. Определение объектов сети дорог и связей между ними на карте.
4.2.3. Переход от карты к нечеткому графу.
4.3. Описание модуля реализации алгоритмов с учетом нечетких данных
4.3.1. Определение живучести транспортной сети
4.3.2. Увеличение степени живучести транспортной сети.
4.3.3. Увеличение степени живучести с минимальной стоимостью
4.3.4.0прсдсление оптимальных мест размещения центров
обслуживания.
4.4. Оценка эффективности программного модуля.
4.5. Выводы по главе
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Построение же моделей в рамках нечеткого подхода позволяет сравнивать модели и придавать точный смысл таким понятиям как значимый и пренебрежимый. Появляется возможность формализации неточных знаний о предметной области, внесения в модель сведений о неполноте информации. Так как при рассмотрении различного рода задач в транспортных сетях мы будем оперировать нечеткими данными, то необходимо рассмотреть, какие тины нечетких данных известны на данный момент, какие операции можно производить над ними и как можно представлять их в ГБД. Понятие нечеткого числа базируется на понятии нечеткого подмножества. Определение 1. Пусть X множество произвольной природы. Нечетким множеством С пзХ называется совокупность упорядоченных пар вида рс хх , где х е X , дсхе0,1. С . Определение 1. Нечетким числом С называется нечеткое подмножество С множества всех действительных чисел X , имеющее нормальную и выпуклую функцию принадлежности х, хе X 3. Определение 1. Бир . V 1 . Определение 1. Ат, 1 Ях2 ттрхх,рх2, хх,х2 е Х,Л е 0,1. Часто на практике используются следующие виды нечетких чисел интервалы, нечеткие треугольные числа и нечеткие трапециевидные числа. Все эти виды являются достаточно простыми и позволяют упрощать вычисления и довольно точно формализовать большое количество ситуаций. Интервал является самым простым видом нечеткого числа. Интервал 1 задается его левой 1, и правой с1г границами, то есть 3 ,грис. Рис. Способы представления нечетких чисел а интервал, б нечеткое треугольное число, в нечеткое трапециевидное число Определим операции сравнения, сложения и вычитания нечетких интервалов. Пусть нечеткие числа представляют собой интервалы с, с1п,сгХ и дг 2г2. Зх с1,2Ус1г г2. X 2,тахл,2. Для определения минимального из двух интервалов , и 2 , необходимо проверить следующее условие если 2 и 2, то 2, ,. Если x2, го проверяется фетье условие 7, 2, если x 2, где 5, II 2 2 2. Таким образом, сначала проверяется, выполняются ли одновременно условия 1 и 2, затем проверяется условие 3. Если и этого недостаточно, сравнивается ширина интервалов. Нечеткие треугольные числа это частный случай нечетких чисел, к тому же более упрощенный, по сравнению с нечеткими фапециевидными числами. Их особенность состоит в . Они могут быть заданы двумя способами , тремя величинами ,,,, причем меньше значения , значений быть не может, больше значения также не может быть значений, а величина определяет максимальный уровень принадлежности значением , соответствующим максимальному уровню принадлежности, а так же значениями отклонений а и 7, то есть ,, 3 рис. Рассмофим теперь некоторые операции над нечеткими чреугольными числами. Х с1т 2 у сгХ 2. Л с1т2 у с1гХ С . С2 у стХ 1т2, 2 . Для сравнения нечетких треугольных чисел можно использовать индекс, отображающий центр тяжести треугольника. Нечеткие трапециевидные числа это также частный случай нечетких чисел. Они также мо1ут быть заданы двумя способами , четырьмя значениями 3 X2 где левая граница нулевого уровня достоверности, правая граница нулевого уровня достоверности, X2 соответегвенно левая и правая границы интервала достоверности, соответствующего уровню принадлежности, равного 1 значениями X и 2, соответствующими
максимальному уровню принадлежности, а также значениями отклонений а и 0, то есть 3 2,3 рис. Для случая нечетких трапециевидных чисел обобщим операции над нелегкими треугольными числами и получим следующие формулы. X 2, X 2 . X 2, X 2 . X 2, X 2 . X 2, X 2 . XX. Определение 1. Лингвистической переменной называется пятерка ,Т, X, , М . Здесь р наименование лингвистической переменной Т множество ее значений терммножество, представляющих собой наименования нечетких переменных. Множество X называется базовым терммножеством лингвистической переменной синтаксическая процедура грамматика, позволяющая генерировать новые термы. Множество Т Ти называется расширенным терммножеством лингвистической переменной М семантическая процедура, позволяющая превратить каждое новое значение лингвистической переменной, образуемое процедурой , в нечеткую переменную, т.