Гиперграфовые модели и методы решения дискретных задач управления в условиях неопределенности

• Автор: Омельченко, Галина Георгиевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Черкесск
• Количество страниц: 163 с. : ил.

1.1. Учет неопределенности параметров в математическом моделировании

1.2. Гиперграфы. Некоторые определения и свойства

1.3. Формулировка и обоснование свойства полноты векторных задач на однородных гиперграфах.

1.4. Постановка задач и построение математических моделей на гиперграфах

1.4.1. Двукритериальная задача кадрового менеджмента.

1.4.2. Математическая модель задачи управления космическим командноизмерительным комплексом

1.4.3. Математическая модель обучения сотрудников организации

1.4.4. Математическая модель назначения учителей в классы с учетом технологий обучения

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

ГЛАВА 2. АЛГОРИТМЫ НАХОЖДЕНИЯ ВСЕХ СОВЕРШЕННЫХ

СОЧЕТАНИЙ И ПОКРЫТИЙ ЗВЕЗДАМИ МНОГОДОЛЬНЫХ ОДНОРОДНЫХ ГИПЕРГРАФОВ

2.1. Оценки числа ребер в дольных однородных гиперграфах
2.2. Обоснование труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе.
2.3. Оценки вычислительной сложности векторной задачи покрытия гиперграфа звездами
2.4. Алгоритм проверки выполнения необходимых условий существования совершенного сочетания в много дольном гиперграфе
2.5. Алгоритм выделения совершенных сочетаний в много дольном гиперграфе,
2.6. Алгоритм нахождения множества допустимых решений задачи покрытия дольного однородного гиперграфа звездами
2.7. Выводы по второй главе
ГЛАВА 3. АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ НАХОЖДЕНИЯ МНОЖЕСТВА АЛЬТЕРНАТИВ ДЛЯ ЗАДАЧИ О СОВЕРШЕННОМ СОЧЕТАНИИ В МНОГО ДОЛЬНОМ ГИГЕРГРАФЕ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
3.1. Проблема неопределенности в математическом моделировании
3.2. Двухуровневый подход в математическом моделировании.
3.2.1. Моделирование на нижнем уровне
3.2.2. Моделирование на верхнем уровне.
3.3. Интервальные модели и многокритериальность
3.3.1. Общая постановка интервальных оптимизационных задач на гиперграфах.
3.3.2. Сведение интервальной задачи к 2критериальной
3.3.3. О разрешимости задач многокритериальной оптимизации с помощью алгоритмов линейной свертки критериев.
3.3.4. Исследование разрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о сочетаниях с критериями вида МАХЗиМ на 3дольном гиперграфе
3.4. Выводы по третьей главе.
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


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