Методы покрытия гиперсети корневым деревом для оптимизации системы транспортных путей

• Автор: Воронова, Анна Михайловна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Петрозаводск
• Количество страниц: 125 с. : ил.

Содержание
Введение

Глава 1. Обзор источников по теме исследования

1.1 Анализ существующих математических моделей и алгоритмов на графовых, гиперграфовых и гиперсетевых структурах

1.2 Заключение по главе

Глава 2. Постановка задачи

2.1 Описание задачи размещения транспортных объектов на лесосеке

2.2 Общие рекомендации по размещению погрузочных пунктов и сети волоков на лесосеке
2.3 Сбор данных об особенностях лесосеки и применение рассчитанных схем волоков при проведении подготовительных и основных работ на лесосеке..

2.4 Заключение по главе

Глава 3. Математические модели в виде графовых, гиперграфовых и гиперсетевых структур для представления транспортной сети
3.1 Описание математической модели транспортной сети в виде взвешенного ориентированного графа
3.2 Математическая модель транспортной сети на основе гиперграфа
3.3 Математическая модель транспортной сети на основе двухуровневой гиперсети
3.4 Заключение по главе
Глава 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.4 Заключение по главе
Глава 5. Программный комплекс для построения информационной системы по проектированию схемы транспортных путей на лесосеке
5.1 Назначение программного комплекса
5.2 Описание генератора входных значений и анализ алгоритма построения
корневого покрывающего дерева гиперсети
5.3 Заключение по главе
Заключение
Список литературы
Приложение А (обязательное) Экспериментальные данные и рассчитанные
покрывающие деревья
Приложение Б (обязательное) Результаты экспериментальных данных
Приложение В (обязательное) Свидетельства о регистрации программ

Введение
Актуальность темы исследования
В практических приложениях для моделирования задач со сложной сетевой структурой все большее применение находят иерархические гиперсети. К таким задачам относятся строительство инженерных сетей электросвязи, сетей автомобильных дорог, нефтепроводных, газопроводных сетей и прочих. Гиперсетевая технология позволяет формализовать задачу оптимизации транспортной сети на земной поверхности с неоднородной территорией и свести ее к решению соответствующей задачи на иерархической гиперсети. Изобразительные возможности языка теории гиперсетей позволяют сформулировать сетевые задачи со сложной структурой.
Частным видом гиперсетей являются двухуровневые гиперсети. На первом уровне такой гиперсети находится гиперграф, на втором уровне -ориентированный граф, в котором дуги соединяют гиперребра первого уровня. Такая структура может быть применена к моделирования лесосеки и решению задачи проектирования схемы первичного транспорта леса при проведении лесозаготовительных работ. Это позволит учесть ряд факторов, не используемых в более простых моделях, таких как ограничение на форму лесосеки, форму и размеры территории набора пачки древесины, неравномерность произрастания леса на территории лесосеки, маневренность трелевочной техники. Схожие модели могут быть применены в задачах построения системы пожаротушения больших зданий.
Таким образом, актуальным является разработка и совершенствование моделей и методов иерархических гиперсетей.
Степень разработанности
Гиперсети рассмотрены в работах В.К. Попкова, Г.Ы. Токтошова и др. [67 -75, 86]. Введены основные понятия теории гиперсетей, рассмотрены задачи оптимизации некоторых систем сетевой структуры, приведены формальные

• прибор для точечного определения свойств грунта, доступ к системе со сверхвысокочастотным радиометрическим прибором, доступ к тематическим картам, полученным в ходе дистанционного зондирования и анализе снимков территории лесосеки.
• лесозаготовительная машина и трелевочный трактор, оборудованные навигаторами,
• программное обеспечение, осуществляющее расчет и поиск места размещения погрузочных пунктов и схемы волоков на лесосеке, обеспечивающее согласованную работу приборов, компьютера, навигатора.
На сегодняшний день комплектация лесозаготовительных машин и трелевочных тракторов позволяет оборудование кабины системой навигации на местности, однако возможности установленных систем ориентирования используются не полностью, чаще всего для установления места нахождения лесозаготовительных машин и трелевочных тракторов или точек, где находятся не вывезенные пачки леса. Более широкое применение предполагает управление траекторией движения лесозаготовительных машин и трелевочных тракторов в соответствие с заданной схемой маневрирования, которая рассчитывается с учетом особенностей каждой конкретной лесосеки. Необходимой компонентой такого взаимодействия является программное обеспечение, которое предназначено для расчета оптимальной схемы размещения погрузочных пунктов и волоков на лесосеке, исходя из характеристик грунта [27, 29].
2.4 Заключение по главе
Изучение задачи проектирования транспортных объектов на лесосеке с учетом особенностей конкретной лесосеки и параметров тревочного оборудования показало возможность моделирования транспортных объектов лесосеки (погрузочных пунктов, магистральных и пасечных волоков) в виде графовых структур, также представления задачи в виде многоуровневой