ГИПЕРГРАФОВЫЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ДИСКРЕТНЫХ ЗАДАЧ УПРАВЛЕНИЯ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
|
Содержание
ВВЕДЕНИЕ 4
ГЛАВА 1. ОСНОВЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ СЛОЖНЫХ СИСТЕМ НА БАЗЕ ТЕОРИИ ГИПЕРГРАФОВ 24
1.1. Учет неопределенности параметров в математическом моделировании 24
1.2. Гиперграфы. Некоторые определения и свойства 28
1.3. Формулировка и обоснование свойства полноты векторных задач на однородных гиперграфах 34
1.4. Постановка задач и построение математических моделей на гиперграфах 38
1.4.1. Двукритериальная задача кадрового менеджмента 38
1.4.2. Математическая модель задачи управления космическим командно-измерительным комплексом 42
1.4.3. Математическая модель обучения сотрудников организации 48
1.4.4. Математическая модель назначения учителей в классы с учетом технологий обучения 52
1.5. Выводы по первой главе 60
ГЛАВА 2. АЛГОРИТМЫ НАХОЖДЕНИЯ ВСЕХ СОВЕРШЕННЫХ
СОЧЕТАНИЙ И ПОКРЫТИЙ ЗВЕЗДАМИ МНОГОДОЛЬНЫХ ОДНОРОДНЫХ ГИПЕРГРАФОВ 61
2.1. Оценки числа ребер в l -дольных l -однородных гиперграфах 61
2.2. Обоснование труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе 63
2.3. Оценки вычислительной сложности векторной задачи покрытия гиперграфа звездами 69
2.4. Алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе 75
2.5. Алгоритм выделения совершенных сочетаний в многодольном гиперграфе 88
2.6. Алгоритм нахождения множества допустимых решений задачи покрытия l -дольного l -однородного гиперграфа звездами 91
2.7. Выводы по второй главе 101
ГЛАВА 3. АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ НАХОЖДЕНИЯ МНОЖЕСТВА АЛЬТЕРНАТИВ ДЛЯ ЗАДАЧИ О СОВЕРШЕННОМ СОЧЕТАНИИ В МНОГОДОЛЬНОМ ГИПЕРГРАФЕ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ 103
3.1. Проблема неопределенности в математическом моделировании 103
3.2. Двухуровневый подход в математическом моделировании 108
3.2.1. Моделирование на нижнем уровне 109
3.2.2. Моделирование на верхнем уровне 121
3.3. Интервальные модели и многокритериальность 126
3.3.1. Общая постановка интервальных оптимизационных задач на гиперграфах 127
3.3.2. Сведение интервальной задачи к 2-критериальной 130
3.3.3. О разрешимости задач многокритериальной оптимизации с помощью алгоритмов линейной свертки критериев 132
3.3.4. Исследование разрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о сочетаниях с критериями вида
MAXSUMна 3-дольном гиперграфе. 133
3.4. Выводы по третьей главе 138
ЗАКЛЮЧЕНИЕ 139
ЛИТЕРАТУРА 141
ВВЕДЕНИЕ 4
ГЛАВА 1. ОСНОВЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ СЛОЖНЫХ СИСТЕМ НА БАЗЕ ТЕОРИИ ГИПЕРГРАФОВ 24
1.1. Учет неопределенности параметров в математическом моделировании 24
1.2. Гиперграфы. Некоторые определения и свойства 28
1.3. Формулировка и обоснование свойства полноты векторных задач на однородных гиперграфах 34
1.4. Постановка задач и построение математических моделей на гиперграфах 38
1.4.1. Двукритериальная задача кадрового менеджмента 38
1.4.2. Математическая модель задачи управления космическим командно-измерительным комплексом 42
1.4.3. Математическая модель обучения сотрудников организации 48
1.4.4. Математическая модель назначения учителей в классы с учетом технологий обучения 52
1.5. Выводы по первой главе 60
ГЛАВА 2. АЛГОРИТМЫ НАХОЖДЕНИЯ ВСЕХ СОВЕРШЕННЫХ
СОЧЕТАНИЙ И ПОКРЫТИЙ ЗВЕЗДАМИ МНОГОДОЛЬНЫХ ОДНОРОДНЫХ ГИПЕРГРАФОВ 61
2.1. Оценки числа ребер в l -дольных l -однородных гиперграфах 61
2.2. Обоснование труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе 63
2.3. Оценки вычислительной сложности векторной задачи покрытия гиперграфа звездами 69
2.4. Алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе 75
2.5. Алгоритм выделения совершенных сочетаний в многодольном гиперграфе 88
2.6. Алгоритм нахождения множества допустимых решений задачи покрытия l -дольного l -однородного гиперграфа звездами 91
2.7. Выводы по второй главе 101
ГЛАВА 3. АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ НАХОЖДЕНИЯ МНОЖЕСТВА АЛЬТЕРНАТИВ ДЛЯ ЗАДАЧИ О СОВЕРШЕННОМ СОЧЕТАНИИ В МНОГОДОЛЬНОМ ГИПЕРГРАФЕ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ 103
3.1. Проблема неопределенности в математическом моделировании 103
3.2. Двухуровневый подход в математическом моделировании 108
3.2.1. Моделирование на нижнем уровне 109
3.2.2. Моделирование на верхнем уровне 121
3.3. Интервальные модели и многокритериальность 126
3.3.1. Общая постановка интервальных оптимизационных задач на гиперграфах 127
3.3.2. Сведение интервальной задачи к 2-критериальной 130
3.3.3. О разрешимости задач многокритериальной оптимизации с помощью алгоритмов линейной свертки критериев 132
3.3.4. Исследование разрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о сочетаниях с критериями вида
MAXSUMна 3-дольном гиперграфе. 133
3.4. Выводы по третьей главе 138
ЗАКЛЮЧЕНИЕ 139
ЛИТЕРАТУРА 141
Актуальность проблемы. Диссертационная работа посвящена разработке методов математического моделирования дискретных слабо структурированных процессов, для которых характерны множественность критериев, стохастичность, интервальность или нечеткость значений исходных данных. Как часть этой проблемы в настоящей работе рассматриваются различные постановки дискретных задач управления: задача обучения сотрудников организации [20], задача назначения учителей в классы с учетом технологий обучения [77], задача управления космическим командно-измерительным комплексом [7], задача выбора стратегии ведения строительства строительной компанией [34]. Классические подходы моделирования таких задач оказываются недостаточными по той причине, что представление параметров и структуры этих задач с помощью инструментария классической теории графов [53] оказывается в принципе неадекватным в силу невозможности отразить в системном единстве сложную организацию их внутренних взаимосвязей, ограничиваясь только понятиями и обозначениями этой теории.
Для математического моделирования значительного количества дискретных систем оказывается вполне достаточным использование аппарата теории графов. Однако, не редки случаи, когда не удается достичь требуемой адекватности с его помощью, в силу чего возникает необходимость использования аппарата теории гиперграфов. Обычно попытка представить гиперграф в виде соответствующего графа приводит к появлению ложных «допустимых» решений. Например, на 4-вершинном множестве V= {1,2,3,4} определен гиперграф с множеством ребер E ={e1,e2,e3}, e1= (1,2,3), e2= (1,3,4) , e3= (1,2,4), изображенный на рис.1. Попытка представить эти ребра треугольниками, построенными из ребер графа на рис.2, составляющих множество {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}, приводит к тому, что в результате получается «ложный» треугольник, состоящий из ребер (2,3), (2,4), (3,4), приводящий к появлению несуществующего элемента в исходных данных гиперграфовой задачи.
В качестве еще одной причины, по которой невозможно представить гиперграфовую задачу в виде теоретико-графовой, можно назвать реально существующее свойство неаддитивности функций, задающих веса ребер гиперграфов. Суть этого свойства заключается в том, что на практике оказывается нереальным определить правило или алгоритм, который представлял бы вес ребра гиперграфа в виде суммы весов вершин этого ребра или графовых ребер, определенных на множестве этих вершин.
Автором предлагается концепция двухуровневого моделирования рассматриваемых дискретных задач управления в условиях неопределенности. На нижнем уровне осуществляется моделирование исходных численных данных на базе экспертного оценивания [90]. Математическое моделирование верхнего уровня приводит к математическим постановкам многокритериальных задач на взвешенных гиперграфах. Весами ребер этих гиперграфов могут быть как действительные числа, так и интервалы или нечеткие множества. При этом заслуживают внимание следующие факты. Во-первых, к настоящему времени практически отсутствуют математические модели, сформулированные на базе теории гиперграфов, и тем более, отсутствуют алгоритмы (точные или приближенные) для экстремальных задач на гиперграфах. Известен лишь весьма ограниченный перечень задач на гиперграфах, относительно которых можно утверждать, что они являются NP-трудными [101]. Это утверждение в полной мере относится и к рассмотренной в диссертационной работе задаче о совершенных сочетаниях на многодольном гиперграфе и задаче покрытия многодольного однородного гиперграфа простыми звездами. Поэтому актуальной является разработка как точных переборных, так и приближенных малотрудоемких (полиномиальных) алгоритмов для решения этих задач. Наряду с этим актуальными также являются методы структурирования содержательных описаний дискретных задач управления в условиях неопределенности, для которых их данные в математической постановке заданы экспертными оценками.
Цель и задачи диссертационного исследования. Основной целью настоящей работы является разработка (на содержательном примере задачи обучения сотрудников организации, задачи назначения учителей в классы с учетом используемых технологий обучения, задачи управления космическим командно-измерительным комплексом, задачи выбора стратегии ведения строительства строительной компанией) двухуровневого подхода к математическому моделированию дискретных задач со сложной внутренней структурой в условиях неопределенности. Поставленная цель требует решения следующих задач:
- разработка в качестве основной составляющей модели нижнего уровня новых методов структурирования данных на базе идеи метода аналитической иерархии [81];
- разработка на базе конкретных слабоструктурированных задач методов построения гиперграфовых моделей верхнего уровня;
- исследование структурной сложности гиперграфовых моделей, а также вычислительной сложности (на базе обоснования свойства полноты) алгоритмов распознавания и нахождения допустимых решений задач о совершенных сочетаниях и покрытии гиперграфа звездами;
- разработка алгоритмов распознавания и алгоритмов нахождения допустимых решений задачи о совершенных сочетаниях на гиперграфе и задачи покрытия гиперграфа звездами.
Методы исследования. Для решения поставленных в работе научных задач использованы методы теории алгоритмов с оценками, теории графов и гиперграфов, многокритериальной оптимизации, комбинаторного анализа и математического программирования, теории экспертных систем, теории нечетких множеств и интервального исчисления,
Научная новизна. Научную новизну диссертационного исследования содержат следующие положения:
1. Построены на базе аппарата теории гиперграфов математические модели многокритериальных задач обучения сотрудников организации,назначения учителей в классы с учетом используемых технологий обучения, управления космическим командно-измерительным комплексом, выбора стратегии ведения строительства строительной компанией.
2. Достижимые верхние оценки количества ребер в полном многодольном однородном гиперграфе, а также максимальной мощности множества совершенных сочетаний и множества покрытий звездами многодольных гиперграфов.
3. Обоснование свойства полноты задачи о совершенных сочетаниях и о покрытии звездами многодольного гиперграфа, а также обоснование труднорешаемости этих задач в многокритериальной постановке.
4. Полиномиальное сведение задачи о совершенных сочетаниях на многодольном гиперграфе к задаче о максимальной клике на специальном графе.
5. Полиномиальный алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе.
6. Алгоритм бесповторного перебора всех совершенных сочетаний в многодольном гиперграфе.
7. Полиномиальный алгоритм сведения задачи покрытия многодольного однородного гиперграфа звездами к задаче о совершенных сочетаниях на гиперграфе.
8. Обоснование неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенном сочетании с векторной целевой функцией, состоящей из критериев весового вида.
Практическая ценность полученных результатов и их реализация. Практическая значимость результатов исследования заключается в том, что полученные в работе результаты могут быть использованы при формировании систем поддержки принятия решений в процессе математического моделирования задач управления сложными системами в условиях неопределенности, в том числе задачи обучения сотрудников организации [68], задачи назначения учителей в классы с учетом технологий обучения [70], задачи управления космическим командно-измерительным комплексом [41, 42] и задачи выбора стратегии ведения строительства строительной компанией. Идеи обоснования неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенном сочетании на гиперграфе, обоснование представленных алгоритмов могут быть использованы в дальнейших исследованиях в области дискретной многокритериальной оптимизации.
На защиту выносятся следующие основные положения:
1. Обоснованное свойство полноты задачи о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами.
2. Вывод достижимых верхних оценок структурной сложности многодольных однородных гиперграфов, на которых базируются рассматриваемые в диссертации математические модели: верхняя оценка количества ребер в полном многодольном однородном гиперграфе, оценка максимальной мощности множества совершенных сочетаний и максимальной мощности множества покрытий многодольного гиперграфа звездами.
3. Обоснование труднорешаемости задач о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами в многокритериальной постановке.
4. Полиномиальный алгоритм проверки выполнения необходимых условий существования в многодольном однородном гиперграфе совершенного сочетания.
5. Алгоритм выделения всех совершенных сочетаний в многодольном однородном гиперграфе, включая вывод оценки вычислительной сложности этого алгоритма.
6. Полиномиальный алгоритм сведения задачи о покрытии l -дольного l - однородного гиперграфа звездами к задаче о совершенном сочетании.
7. Структурирование задачи управления в условиях неопределенности данных сложной системы методом двухуровневого моделирования. Алгоритм реализации метода аналитической иерархии для слабоструктурированной задачи выбора стратегии ведения строительства строительной компанией.
8. Доказательство неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенном сочетании на гиперграфе с целевой функцией весового вида.
Апробация работы. Результаты исследования и основные его положения докладывались и обсуждались на заседаниях научно¬методического семинара кафедры прикладной математики (КЧГТА, г. Черкесск, 2002-2004 гг.) и получили положительную оценку на следующих конференциях и симпозиумах, проводимых различными академическими учреждениями и высшими учебными заведениями России:
- на VIII Международном семинаре «Дискретная математика и ее приложения» (МГУ, 2004);
- на IV Международной конференции «Новые технологии в управлении, бизнесе и праве» (Невинномысск, 2004);
- на VIII Международной конференции «Образование. Экология. Экономика.
Информатика» (Астрахань, 2003);
- на IV Международной конференции молодых ученых и студентов (Самара,2003);
- на Международной научно-практической конференции «Наука и практика.
Диалоги нового века» (Набережные Челны, 2003);
- на III Международной конференции «Новые технологии в управлении, бизнесе и праве) (Невинномысск, 2003);
- на III Международной конференции молодых ученых и студентов (Самара,
2002);
- на Международной школе-семинаре по геометрии и анализу памяти Н.В. Ефимова (Абрау-Дюрсо, база отдыха Ростовского госуниверситета «Лиманчик», 2002);
- на 11-ой Всероссийской конференции молодых ученых «Математическое моделирование в естественных науках» (Пермь, ПГТУ, 2002);
- на Дальневосточной конференции студентов, аспирантов и молодых ученых по математическому моделированию (Владивосток, 2002);
- на V Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 2002);
- на X Международной конференции «Математика. Экономика. Образование». II Международный симпозиум «Ряды Фурье и их приложения» (Ростов-на-Дону, 2002);
- на IV научно-практической конференции «Решение научно-технических и социально-экономических проблем современности» (Черкесск, 2002);
А также на научно-исследовательских семинарах по графам и гипергафам под руководством проф. А.А.Зыкова (Одесса, 2002, 2003) [71].
Теоретические и практические результаты диссертационной работы использованы при выполнении НИР по гранту РФФИ, проект № 00-01-00652 «Математическое моделирование структуры слабо формализованных систем в условиях неопределенности», НИР Министерства Обороны РФ (в/ч 32103) «Исследование вопросов создания системы оценки космической обстановки для учета изменяющихся условий управления космическими аппаратами» [42] и «Исследование путей и способов повышения эффективности управления орбитальными группировками на основе адаптации системы управления КА к изменяющимся условиям космической обстановки» [41]. В результате внедрения разработанного научно-методического аппарата повышена оперативность решения задач управления космическими средствами на 20-25% при возможности сокращения на 7-12% трудозатрат, а использование разработанных в диссертации полиномиального алгоритма и алгоритма выделения всех совершенных сочетаний позволило на 53% повысить оперативность формирования исходных данных в системе поддержки принятия решений.
Материалы диссертации опубликованы в 13 научных статьях и в 14 тезисах докладов.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы, содержащего 101 наименование, а также приложений, включающих в себя программу реализации алгоритма проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе, описания нечеткой экспертной системы диагностики факторов выполнения работы, а также актов внедрения результатов диссертационной работы.
Для математического моделирования значительного количества дискретных систем оказывается вполне достаточным использование аппарата теории графов. Однако, не редки случаи, когда не удается достичь требуемой адекватности с его помощью, в силу чего возникает необходимость использования аппарата теории гиперграфов. Обычно попытка представить гиперграф в виде соответствующего графа приводит к появлению ложных «допустимых» решений. Например, на 4-вершинном множестве V= {1,2,3,4} определен гиперграф с множеством ребер E ={e1,e2,e3}, e1= (1,2,3), e2= (1,3,4) , e3= (1,2,4), изображенный на рис.1. Попытка представить эти ребра треугольниками, построенными из ребер графа на рис.2, составляющих множество {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}, приводит к тому, что в результате получается «ложный» треугольник, состоящий из ребер (2,3), (2,4), (3,4), приводящий к появлению несуществующего элемента в исходных данных гиперграфовой задачи.
В качестве еще одной причины, по которой невозможно представить гиперграфовую задачу в виде теоретико-графовой, можно назвать реально существующее свойство неаддитивности функций, задающих веса ребер гиперграфов. Суть этого свойства заключается в том, что на практике оказывается нереальным определить правило или алгоритм, который представлял бы вес ребра гиперграфа в виде суммы весов вершин этого ребра или графовых ребер, определенных на множестве этих вершин.
Автором предлагается концепция двухуровневого моделирования рассматриваемых дискретных задач управления в условиях неопределенности. На нижнем уровне осуществляется моделирование исходных численных данных на базе экспертного оценивания [90]. Математическое моделирование верхнего уровня приводит к математическим постановкам многокритериальных задач на взвешенных гиперграфах. Весами ребер этих гиперграфов могут быть как действительные числа, так и интервалы или нечеткие множества. При этом заслуживают внимание следующие факты. Во-первых, к настоящему времени практически отсутствуют математические модели, сформулированные на базе теории гиперграфов, и тем более, отсутствуют алгоритмы (точные или приближенные) для экстремальных задач на гиперграфах. Известен лишь весьма ограниченный перечень задач на гиперграфах, относительно которых можно утверждать, что они являются NP-трудными [101]. Это утверждение в полной мере относится и к рассмотренной в диссертационной работе задаче о совершенных сочетаниях на многодольном гиперграфе и задаче покрытия многодольного однородного гиперграфа простыми звездами. Поэтому актуальной является разработка как точных переборных, так и приближенных малотрудоемких (полиномиальных) алгоритмов для решения этих задач. Наряду с этим актуальными также являются методы структурирования содержательных описаний дискретных задач управления в условиях неопределенности, для которых их данные в математической постановке заданы экспертными оценками.
Цель и задачи диссертационного исследования. Основной целью настоящей работы является разработка (на содержательном примере задачи обучения сотрудников организации, задачи назначения учителей в классы с учетом используемых технологий обучения, задачи управления космическим командно-измерительным комплексом, задачи выбора стратегии ведения строительства строительной компанией) двухуровневого подхода к математическому моделированию дискретных задач со сложной внутренней структурой в условиях неопределенности. Поставленная цель требует решения следующих задач:
- разработка в качестве основной составляющей модели нижнего уровня новых методов структурирования данных на базе идеи метода аналитической иерархии [81];
- разработка на базе конкретных слабоструктурированных задач методов построения гиперграфовых моделей верхнего уровня;
- исследование структурной сложности гиперграфовых моделей, а также вычислительной сложности (на базе обоснования свойства полноты) алгоритмов распознавания и нахождения допустимых решений задач о совершенных сочетаниях и покрытии гиперграфа звездами;
- разработка алгоритмов распознавания и алгоритмов нахождения допустимых решений задачи о совершенных сочетаниях на гиперграфе и задачи покрытия гиперграфа звездами.
Методы исследования. Для решения поставленных в работе научных задач использованы методы теории алгоритмов с оценками, теории графов и гиперграфов, многокритериальной оптимизации, комбинаторного анализа и математического программирования, теории экспертных систем, теории нечетких множеств и интервального исчисления,
Научная новизна. Научную новизну диссертационного исследования содержат следующие положения:
1. Построены на базе аппарата теории гиперграфов математические модели многокритериальных задач обучения сотрудников организации,назначения учителей в классы с учетом используемых технологий обучения, управления космическим командно-измерительным комплексом, выбора стратегии ведения строительства строительной компанией.
2. Достижимые верхние оценки количества ребер в полном многодольном однородном гиперграфе, а также максимальной мощности множества совершенных сочетаний и множества покрытий звездами многодольных гиперграфов.
3. Обоснование свойства полноты задачи о совершенных сочетаниях и о покрытии звездами многодольного гиперграфа, а также обоснование труднорешаемости этих задач в многокритериальной постановке.
4. Полиномиальное сведение задачи о совершенных сочетаниях на многодольном гиперграфе к задаче о максимальной клике на специальном графе.
5. Полиномиальный алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе.
6. Алгоритм бесповторного перебора всех совершенных сочетаний в многодольном гиперграфе.
7. Полиномиальный алгоритм сведения задачи покрытия многодольного однородного гиперграфа звездами к задаче о совершенных сочетаниях на гиперграфе.
8. Обоснование неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенном сочетании с векторной целевой функцией, состоящей из критериев весового вида.
Практическая ценность полученных результатов и их реализация. Практическая значимость результатов исследования заключается в том, что полученные в работе результаты могут быть использованы при формировании систем поддержки принятия решений в процессе математического моделирования задач управления сложными системами в условиях неопределенности, в том числе задачи обучения сотрудников организации [68], задачи назначения учителей в классы с учетом технологий обучения [70], задачи управления космическим командно-измерительным комплексом [41, 42] и задачи выбора стратегии ведения строительства строительной компанией. Идеи обоснования неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенном сочетании на гиперграфе, обоснование представленных алгоритмов могут быть использованы в дальнейших исследованиях в области дискретной многокритериальной оптимизации.
На защиту выносятся следующие основные положения:
1. Обоснованное свойство полноты задачи о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами.
2. Вывод достижимых верхних оценок структурной сложности многодольных однородных гиперграфов, на которых базируются рассматриваемые в диссертации математические модели: верхняя оценка количества ребер в полном многодольном однородном гиперграфе, оценка максимальной мощности множества совершенных сочетаний и максимальной мощности множества покрытий многодольного гиперграфа звездами.
3. Обоснование труднорешаемости задач о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами в многокритериальной постановке.
4. Полиномиальный алгоритм проверки выполнения необходимых условий существования в многодольном однородном гиперграфе совершенного сочетания.
5. Алгоритм выделения всех совершенных сочетаний в многодольном однородном гиперграфе, включая вывод оценки вычислительной сложности этого алгоритма.
6. Полиномиальный алгоритм сведения задачи о покрытии l -дольного l - однородного гиперграфа звездами к задаче о совершенном сочетании.
7. Структурирование задачи управления в условиях неопределенности данных сложной системы методом двухуровневого моделирования. Алгоритм реализации метода аналитической иерархии для слабоструктурированной задачи выбора стратегии ведения строительства строительной компанией.
8. Доказательство неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенном сочетании на гиперграфе с целевой функцией весового вида.
Апробация работы. Результаты исследования и основные его положения докладывались и обсуждались на заседаниях научно¬методического семинара кафедры прикладной математики (КЧГТА, г. Черкесск, 2002-2004 гг.) и получили положительную оценку на следующих конференциях и симпозиумах, проводимых различными академическими учреждениями и высшими учебными заведениями России:
- на VIII Международном семинаре «Дискретная математика и ее приложения» (МГУ, 2004);
- на IV Международной конференции «Новые технологии в управлении, бизнесе и праве» (Невинномысск, 2004);
- на VIII Международной конференции «Образование. Экология. Экономика.
Информатика» (Астрахань, 2003);
- на IV Международной конференции молодых ученых и студентов (Самара,2003);
- на Международной научно-практической конференции «Наука и практика.
Диалоги нового века» (Набережные Челны, 2003);
- на III Международной конференции «Новые технологии в управлении, бизнесе и праве) (Невинномысск, 2003);
- на III Международной конференции молодых ученых и студентов (Самара,
2002);
- на Международной школе-семинаре по геометрии и анализу памяти Н.В. Ефимова (Абрау-Дюрсо, база отдыха Ростовского госуниверситета «Лиманчик», 2002);
- на 11-ой Всероссийской конференции молодых ученых «Математическое моделирование в естественных науках» (Пермь, ПГТУ, 2002);
- на Дальневосточной конференции студентов, аспирантов и молодых ученых по математическому моделированию (Владивосток, 2002);
- на V Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 2002);
- на X Международной конференции «Математика. Экономика. Образование». II Международный симпозиум «Ряды Фурье и их приложения» (Ростов-на-Дону, 2002);
- на IV научно-практической конференции «Решение научно-технических и социально-экономических проблем современности» (Черкесск, 2002);
А также на научно-исследовательских семинарах по графам и гипергафам под руководством проф. А.А.Зыкова (Одесса, 2002, 2003) [71].
Теоретические и практические результаты диссертационной работы использованы при выполнении НИР по гранту РФФИ, проект № 00-01-00652 «Математическое моделирование структуры слабо формализованных систем в условиях неопределенности», НИР Министерства Обороны РФ (в/ч 32103) «Исследование вопросов создания системы оценки космической обстановки для учета изменяющихся условий управления космическими аппаратами» [42] и «Исследование путей и способов повышения эффективности управления орбитальными группировками на основе адаптации системы управления КА к изменяющимся условиям космической обстановки» [41]. В результате внедрения разработанного научно-методического аппарата повышена оперативность решения задач управления космическими средствами на 20-25% при возможности сокращения на 7-12% трудозатрат, а использование разработанных в диссертации полиномиального алгоритма и алгоритма выделения всех совершенных сочетаний позволило на 53% повысить оперативность формирования исходных данных в системе поддержки принятия решений.
Материалы диссертации опубликованы в 13 научных статьях и в 14 тезисах докладов.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы, содержащего 101 наименование, а также приложений, включающих в себя программу реализации алгоритма проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе, описания нечеткой экспертной системы диагностики факторов выполнения работы, а также актов внедрения результатов диссертационной работы.
В ходе проделанной исследовательской работы получены следующие основные результаты:
1. Обосновано свойство полноты задачи о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами.
2. Дан строгий вывод достижимых верхних оценок структурной сложности многодольных однородных гиперграфов: верхняя оценка количества ребер в полном многодольном однородном гиперграфе, оценка максимальной мощности множества совершенных сочетаний и максимальной мощности множества покрытий многодольного гиперграфа звездами.
3. Обоснована труднорешаемость задач о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами в многокритериальной постановке.
4. Построен полиномиальный алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе.
". Построен алгоритм бесповторного перебора всех совершенных сочетаний в многодольном гиперграфе.
6. Построен полиномиальный алгоритм сведения задачи покрытия многодольного однородного гиперграфа звездами к задаче о совершенных сочетаниях на гиперграфе.
7. Сформулирована концепция двухуровневого моделирования дискретных задач в условиях неопределенности: на нижнем уровне осуществляется моделирование исходных данных для модели верхнего уровня, математическая модель верхнего уровня - это модель теории оптимизации, на базе которой строится и обосновывается наиболее целесообразное управление рассматриваемым процессом. В качестве конкретной реализации двухуровневого моделирования представлена модель процесса выбора и принятия стратегии ведения строительства некоторой строительной компании.
8. Доказана неразрешимость с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенных сочетаниях с критериями вида MAXSUMна 3-дольных гиперграфах.
1. Обосновано свойство полноты задачи о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами.
2. Дан строгий вывод достижимых верхних оценок структурной сложности многодольных однородных гиперграфов: верхняя оценка количества ребер в полном многодольном однородном гиперграфе, оценка максимальной мощности множества совершенных сочетаний и максимальной мощности множества покрытий многодольного гиперграфа звездами.
3. Обоснована труднорешаемость задач о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами в многокритериальной постановке.
4. Построен полиномиальный алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе.
". Построен алгоритм бесповторного перебора всех совершенных сочетаний в многодольном гиперграфе.
6. Построен полиномиальный алгоритм сведения задачи покрытия многодольного однородного гиперграфа звездами к задаче о совершенных сочетаниях на гиперграфе.
7. Сформулирована концепция двухуровневого моделирования дискретных задач в условиях неопределенности: на нижнем уровне осуществляется моделирование исходных данных для модели верхнего уровня, математическая модель верхнего уровня - это модель теории оптимизации, на базе которой строится и обосновывается наиболее целесообразное управление рассматриваемым процессом. В качестве конкретной реализации двухуровневого моделирования представлена модель процесса выбора и принятия стратегии ведения строительства некоторой строительной компании.
8. Доказана неразрешимость с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенных сочетаниях с критериями вида MAXSUMна 3-дольных гиперграфах.
Подобные работы
- Гиперграфовые модели и методы решения дискретных задач управления в условиях неопределенности
Диссертации (РГБ), математика. Язык работы: Русский. Цена: 470 р. Год сдачи: 2004
Заказать работу
Заявка на оценку стоимости
Это краткая форма заказа. После ее заполнения вы перейдете на полную форму заказа работы
Каталог работ (130032)
- Бакалаврская работа (31207)
- Диссертация (960)
- Магистерская диссертация (18174)
- Дипломные работы, ВКР (53041)
- Главы к дипломным работам (2108)
- Курсовые работы (9673)
- Контрольные работы (6188)
- Отчеты по практике (1308)
- Рефераты (1456)
- Задачи, тесты, ПТК (616)
- Ответы на вопросы (154)
- Статьи, Эссе, Сочинения (911)
- Бизнес-планы (49)
- Презентации (101)
- РГР (84)
- Авторефераты (РГБ) (1690)
- Диссертации (РГБ) (1879)
- Прочее (433)
Новости
06.01.2018
Помощь студентам и аспирантам в выполнении работ от наших партнеров
Помощь студентам и аспирантам в выполнении работ от наших партнеров
Помощь в выполнении учебных и научных работ на заказ ОФОРМИТЬ ЗАКАЗ
дальше»» Все новости
Статьи
- Где лучше заказывать диссертации и дипломные?
- Выполнение научных статей
- Подготовка диссертаций
- Подводные камни при написании магистерской работы
- Помощь в выполнении дипломных работ
»» Все статьи
Заказать работу
Заявка на оценку стоимости
Это краткая форма заказа. После ее заполнения вы перейдете на полную форму заказа работы
