Задача о лесах на графах и гиперграфах и ее приложение

• Автор: Шапошникова, Ольга Ивановна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Ставрополь
• Количество страниц: 132 с. : ил

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.
Глава 1. ТЕОРЕТИКОГРАФОВАЯ МОДЕЛЬ ЗАДАЧИ ПРОЕКТИРОВАНИЯ ОРОСИТЕЛЬНЫХ СЕТЕЙ И ОЦЕНКИ ЕЕ СЛОЖНОСТИ .

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

1.2. Общая постановка векторной задачи об остовных деревьях

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

1.3. Оценка вычислительной сложности задачи об остовных деревьях . Глава 2. АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ ВЕКТОРНОЙ ЗАДАЧИ ОБ ОСТОВНЫХ ДЕРЕВЬЯХ.

2.1. Математическая постановка проблемы

2.2. Описание алгоритма а3

2.3. Вероятностный анализ алгоритма а3.

2.4. Вероятностный анализ применения алгоритма а3 к множеству МпуЯуА.

2.5. Статистически эффективный алгоритм а0.
2.6. Обоснование условий статистической эффективности алгоритма а0 . Глава 3. ИНТЕРВАЛЬНЫЕ ЗАДАЧИ ОБ ОСТОВНЫХ ДЕРЕВЬЯХ И ИХ НЕРАЗРЕШИМОСТЬ С ПОМОЩЬЮ АЛГОРИТМОВ ЛИНЕЙНОЙ СВЕРТКИ
3.1. Отображение неопределенности значений параметров моделей средствами интервальной математики.
3.2. Сведение интервальной задачи к задаче многокритериальной оптимизации .
3.3. Неразрешимость интервальных задач с помощью алгоритма линейной свертки.
Глава 4. ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЙ КЛАСС ЗАДАЧ ОБ ОСТОВНЫХ ДЕРЕВЬЯХ С ТОПОЛОГИЧЕСКИМ КРИТЕРИЕМ
4.1. Математическая постановка задачи об остовных деревьях
4.2. Полиномиальная разрешимость однокритериальных задач об остовных деревьяях с топологическими критериями
4.3. Полиномиальная разрешимость 2критериальных задач, в которых один критерий является топологическим
Глава 5. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ВОДОПОЛЬЗОВАНИЯ НА ГИПЕРГРАФАХ С ИНТЕРВАЛЬНЫМИ ДАННЫМИ
5.1. Основные определения теории гиперграфов.
5.2. Математическая постановка задачи
5.3. Сведение задачи с интервальными данными к многокритериальной задачи .
5.4. Сведение задачи на гиперграфе к задаче на графе.
5.5. Оценки вычислительной сложности исследуемых задач.
5.6. Полиномиально разрешимые постановки.
5.7. Исследование задачи 3.
5.8. Иллюстративный пример решения конкретной 2критериальной задачи водопользования.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Выделенный в ходе исследования полиномиально разрешимый подкласс задач представляет собой базис для разработки методик проектирования оросительной системы. Построенная модель задачи водопользования может применяться при принятии решения снабжения питьевой водой, как малых населенных пунктов, так и больших регионов. Построены малотрудоемкие приближенные алгоритмы нахождения такого решения задачи 3ОС, которое представляется остовным деревом степени 3. Доказана неразрешимость алгоритмами линейной свертки задачи закрытой оросительной системы, представляемой остовным деревом степени 3, если веса заданы интервалами. Выделен полиномиально разрешимый подкласс задач об остовном дереве с топологическим критерием как для однокритериальных постановок, учитывающих степень и радиус остовного дерева, так и для дву критериальных постановок, с критериями М1НМАХ и радиуса остовного дерева. Построена и исследована многокритериальная гиперграфовая модель, способная отражать зависимость показателя здоровья населения от состояния окружающей среды, в частности, потребляемой населением питьевой воды. Апробация работы. Основные результаты работы обсуждались на заседаниях научно-методического семинара кафедры прикладной математики (КЧГТИ, г. Черкесск, -г. КЧГТИ, г. Черкесск, -гг. Северо-Кавказских научных конференциях аспирантов и молодых ученых «Перспектива - » (КБГУ, г. Нальчик, г. III и IV Всероссийском симпозиуме «математическое моделирование и компьютерные технологии» (КИ-ЭП, г. Кисловодск, -гг. Всероссийской научной конференции «Математическое моделирование в научных исследованиях» (СГУ, г. Ставрополь, г. Реализация результатов исследования. Теоретические и практические результаты диссертационной работы использованы при выполнении НИР по гранту РФФИ, проект № 2 «Математическое моделирование структуры слабоформализованных систем в условиях неопределенности». Публикации. По теме диссертации опубликовано печатных работ - 2 статьи в реферируемых журналах, 2 статьи в сборниках научных трудов, 1 депонированная рукопись, 8 тезисов докладов на международных и всероссийских конференциях. Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка используемой литературы, содержащего наименований. Содержание работы изложено на 2 странице. Во введении обоснована актуальность темы диссертационного исследования, сформулирована его цель, описана структура и проведен обзор результатов работы, изложены положения, выносимые на защиту. В главе 1 дано содержательное описание задачи проектирования оросительных сетей и представлена ее теоретико-графовая модель. Содержательная суть рассматриваемой задачи состоит в следующем. Исходя из заданных координат пунктов потребления воды (гидрантов) и водозабора, зон запрета на прокладку трасс трубопроводов, расходов и напоров воды на гидрантах, описания поверхности территории орошения, задаваемого сортамента труб для прокладки трубопроводов и марок насосно-силовых установок, следует выбрать такое соединение гидрантов с насосной станцией трубопроводами, указав по каждому из них материалы, марки, диаметры, толщины стенок используемых труб, и так выбрать марки и количество насосно-силовых установок насосной станции, чтобы при этом общие затраты на создание и эксплуатацию ЗОС в течении заданного количества лет были наименьшими. Математическая модель ЗОС в традиционной постановке представляет собой экстремальную, т. Вместе с тем, эффективность того или другого допустимого варианта ЗОС в полной мере можно отразить не одним, а целым рядом показателей или критериев, которые являются принципиально разнородными. Используемые в системах автоматизированного проектирования оросительных сетей алгоритмы относятся фактически к направленному перебору остовов графа возможных соединений узлов сети друг с другом. Таким образом возникает проблема разработки достаточно эффективных алгоритмов для соответствующих экстремальных задач на графах, относящихся к известному классу так называемых ЫР-трудных задач. Проектирование ведется на реально заданном сортаменте труб и сортаменте насосно-силовых агрегатов.