Помощь студентам в учебе
Гиперграфовые модели и методы решения дискретных задач управления в условиях неопределенности
|
ВВЕДЕНИЕ 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. Оценки числа ребер в 1 -дольных 1 -однородных гиперграфах 61
2.2. Обоснование труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе 63
2.3. Оценки вычислительной сложности векторной задачи покрытия гиперграфа звездами 69
2.4. Алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе 75
2.5. Алгоритм выделения совершенных сочетаний в многодольном гиперграфе 88
2.6. Алгоритм нахождения множества допустимых решений задачи покрытия 1 -дольного 1 -однородного гиперграфа звездами 91
2.7. Выводы по второй главе 101
3
ГЛАВА 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
ГЛАВА 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. Оценки числа ребер в 1 -дольных 1 -однородных гиперграфах 61
2.2. Обоснование труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе 63
2.3. Оценки вычислительной сложности векторной задачи покрытия гиперграфа звездами 69
2.4. Алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе 75
2.5. Алгоритм выделения совершенных сочетаний в многодольном гиперграфе 88
2.6. Алгоритм нахождения множества допустимых решений задачи покрытия 1 -дольного 1 -однородного гиперграфа звездами 91
2.7. Выводы по второй главе 101
3
ГЛАВА 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}
определен гиперграф с множеством ребер Е = {еп ^ езЬ ei = (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)}, приводит к тому, что в
5
результате получается «ложный» треугольник, состоящий из ребер (2,3), (2,4), (3,4), приводящий к появлению несуществующего элемента в исходных данных гиперграфовой задачи.
Рис.1. 4-вершинный гиперграф G = (V,E), E = {e1,e2,e3}, e1 = (1,2,3), e = (1,3,4), e3 = (1,2,4)
2
Рис.2. Представление ребер гиперграфа на рис. 1 треугольниками, состоящими из графовых ребер
В качестве еще одной причины, по которой невозможно представить гиперграфовую задачу в виде теоретико-графовой, можно назвать реально существующее свойство неаддитивности функций, задающих веса ребер гиперграфов. Суть этого свойства заключается в том, что на практике оказывается нереальным определить правило или алгоритм, который представлял бы вес ребра гиперграфа в виде суммы весов вершин этого ребра или графовых ребер, определенных на множестве этих вершин.
6
Автором предлагается концепция двухуровневого моделирования рассматриваемых дискретных задач управления в условиях неопределенности. На нижнем уровне осуществляется моделирование исходных численных данных на базе экспертного оценивания [90]. Математическое моделирование верхнего уровня приводит к математическим постановкам многокритериальных задач на взвешенных гиперграфах. Весами ребер этих гиперграфов могут быть как действительные числа, так и интервалы или нечеткие множества. При этом заслуживают внимание следующие факты. Во-первых, к настоящему времени практически отсутствуют математические модели, сформулированные на базе теории гиперграфов, и тем более, отсутствуют алгоритмы (точные или приближенные) для экстремальных задач на гиперграфах. Известен лишь весьма ограниченный перечень задач на гиперграфах, относительно которых можно утверждать, что они являются NP-трудными [101]. Это утверждение в полной мере относится и к рассмотренной в диссертационной работе задаче о совершенных сочетаниях на многодольном гиперграфе и задаче покрытия многодольного однородного гиперграфа простыми звездами. Поэтому актуальной является разработка как точных переборных, так и приближенных малотрудоемких (полиномиальных) алгоритмов для решения этих задач. Наряду с этим актуальными также являются методы структурирования содержательных описаний дискретных задач управления в условиях неопределенности, для которых их данные в математической постановке заданы экспертными оценками.
Цель и задачи диссертационного исследования. Основной целью настоящей работы является разработка (на содержательном примере задачи обучения сотрудников организации, задачи назначения учителей в классы с учетом используемых технологий обучения, задачи управления космическим командно-измерительным комплексом, задачи выбора стратегии ведения строительства строительной компанией) двухуровневого подхода к математическому моделированию дискретных задач со сложной внутренней
7
структурой в условиях неопределенности. Поставленная цель требует решения следующих задач:
- разработка в качестве основной составляющей модели нижнего уровня новых методов структурирования данных на базе идеи метода аналитической иерархии [81];
- разработка на базе конкретных слабоструктурированных задач методов построения гиперграфовых моделей верхнего уровня;
- исследование структурной сложности гиперграфовых моделей, а также вычислительной сложности (на базе обоснования свойства полноты) алгоритмов распознавания и нахождения допустимых решений задач о совершенных сочетаниях и покрытии гиперграфа звездами;
- разработка алгоритмов распознавания и алгоритмов нахождения допустимых решений задачи о совершенных сочетаниях на гиперграфе и задачи покрытия гиперграфа звездами.
Методы исследования. Для решения поставленных в работе научных задач использованы методы теории алгоритмов с оценками, теории графов и гиперграфов, многокритериальной оптимизации, комбинаторного анализа и математического программирования, теории экспертных систем, теории нечетких множеств и интервального исчисления,
Для математического моделирования значительного количества дискретных систем оказывается вполне достаточным использование аппарата теории графов. Однако, не редки случаи, когда не удается достичь требуемой адекватности с его помощью, в силу чего возникает необходимость использования аппарата теории гиперграфов. Обычно попытка представить гиперграф в виде соответствующего графа приводит к появлению ложных «допустимых» решений. Например, на 4-вершинном множестве V = {1,2,3,4}
определен гиперграф с множеством ребер Е = {еп ^ езЬ ei = (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)}, приводит к тому, что в
5
результате получается «ложный» треугольник, состоящий из ребер (2,3), (2,4), (3,4), приводящий к появлению несуществующего элемента в исходных данных гиперграфовой задачи.
Рис.1. 4-вершинный гиперграф G = (V,E), E = {e1,e2,e3}, e1 = (1,2,3), e = (1,3,4), e3 = (1,2,4)
2
Рис.2. Представление ребер гиперграфа на рис. 1 треугольниками, состоящими из графовых ребер
В качестве еще одной причины, по которой невозможно представить гиперграфовую задачу в виде теоретико-графовой, можно назвать реально существующее свойство неаддитивности функций, задающих веса ребер гиперграфов. Суть этого свойства заключается в том, что на практике оказывается нереальным определить правило или алгоритм, который представлял бы вес ребра гиперграфа в виде суммы весов вершин этого ребра или графовых ребер, определенных на множестве этих вершин.
6
Автором предлагается концепция двухуровневого моделирования рассматриваемых дискретных задач управления в условиях неопределенности. На нижнем уровне осуществляется моделирование исходных численных данных на базе экспертного оценивания [90]. Математическое моделирование верхнего уровня приводит к математическим постановкам многокритериальных задач на взвешенных гиперграфах. Весами ребер этих гиперграфов могут быть как действительные числа, так и интервалы или нечеткие множества. При этом заслуживают внимание следующие факты. Во-первых, к настоящему времени практически отсутствуют математические модели, сформулированные на базе теории гиперграфов, и тем более, отсутствуют алгоритмы (точные или приближенные) для экстремальных задач на гиперграфах. Известен лишь весьма ограниченный перечень задач на гиперграфах, относительно которых можно утверждать, что они являются NP-трудными [101]. Это утверждение в полной мере относится и к рассмотренной в диссертационной работе задаче о совершенных сочетаниях на многодольном гиперграфе и задаче покрытия многодольного однородного гиперграфа простыми звездами. Поэтому актуальной является разработка как точных переборных, так и приближенных малотрудоемких (полиномиальных) алгоритмов для решения этих задач. Наряду с этим актуальными также являются методы структурирования содержательных описаний дискретных задач управления в условиях неопределенности, для которых их данные в математической постановке заданы экспертными оценками.
Цель и задачи диссертационного исследования. Основной целью настоящей работы является разработка (на содержательном примере задачи обучения сотрудников организации, задачи назначения учителей в классы с учетом используемых технологий обучения, задачи управления космическим командно-измерительным комплексом, задачи выбора стратегии ведения строительства строительной компанией) двухуровневого подхода к математическому моделированию дискретных задач со сложной внутренней
7
структурой в условиях неопределенности. Поставленная цель требует решения следующих задач:
- разработка в качестве основной составляющей модели нижнего уровня новых методов структурирования данных на базе идеи метода аналитической иерархии [81];
- разработка на базе конкретных слабоструктурированных задач методов построения гиперграфовых моделей верхнего уровня;
- исследование структурной сложности гиперграфовых моделей, а также вычислительной сложности (на базе обоснования свойства полноты) алгоритмов распознавания и нахождения допустимых решений задач о совершенных сочетаниях и покрытии гиперграфа звездами;
- разработка алгоритмов распознавания и алгоритмов нахождения допустимых решений задачи о совершенных сочетаниях на гиперграфе и задачи покрытия гиперграфа звездами.
Методы исследования. Для решения поставленных в работе научных задач использованы методы теории алгоритмов с оценками, теории графов и гиперграфов, многокритериальной оптимизации, комбинаторного анализа и математического программирования, теории экспертных систем, теории нечетких множеств и интервального исчисления,
В ходе проделанной исследовательской работы получены следующие основные результаты:
1. Обосновано свойство полноты задачи о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами.
2. Дан строгий вывод достижимых верхних оценок структурной сложности многодольных однородных гиперграфов: верхняя оценка количества ребер в полном многодольном однородном гиперграфе, оценка максимальной мощности множества совершенных сочетаний и максимальной мощности множества покрытий многодольного гиперграфа звездами.
3. Обоснована труднорешаемость задач о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами в многокритериальной постановке.
4. Построен полиномиальный алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе.
5. Построен алгоритм бесповторного перебора всех совершенных сочетаний в многодольном гиперграфе.
6. Построен полиномиальный алгоритм сведения задачи покрытия многодольного однородного гиперграфа звездами к задаче о совершенных сочетаниях на гиперграфе.
7. Сформулирована концепция двухуровневого моделирования дискретных задач в условиях неопределенности: на нижнем уровне осуществляется моделирование исходных данных для модели верхнего уровня, математическая модель верхнего уровня - это модель теории оптимизации, на базе которой строится и обосновывается наиболее
140
целесообразное управление рассматриваемым процессом. В качестве конкретной реализации двухуровневого моделирования представлена модель процесса выбора и принятия стратегии ведения строительства некоторой строительной компании.
8. Доказана неразрешимость с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенных сочетаниях с критериями вида MAXSUM на 3-дольных гиперграфах.
1. Обосновано свойство полноты задачи о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами.
2. Дан строгий вывод достижимых верхних оценок структурной сложности многодольных однородных гиперграфов: верхняя оценка количества ребер в полном многодольном однородном гиперграфе, оценка максимальной мощности множества совершенных сочетаний и максимальной мощности множества покрытий многодольного гиперграфа звездами.
3. Обоснована труднорешаемость задач о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами в многокритериальной постановке.
4. Построен полиномиальный алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе.
5. Построен алгоритм бесповторного перебора всех совершенных сочетаний в многодольном гиперграфе.
6. Построен полиномиальный алгоритм сведения задачи покрытия многодольного однородного гиперграфа звездами к задаче о совершенных сочетаниях на гиперграфе.
7. Сформулирована концепция двухуровневого моделирования дискретных задач в условиях неопределенности: на нижнем уровне осуществляется моделирование исходных данных для модели верхнего уровня, математическая модель верхнего уровня - это модель теории оптимизации, на базе которой строится и обосновывается наиболее
140
целесообразное управление рассматриваемым процессом. В качестве конкретной реализации двухуровневого моделирования представлена модель процесса выбора и принятия стратегии ведения строительства некоторой строительной компании.
8. Доказана неразрешимость с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенных сочетаниях с критериями вида MAXSUM на 3-дольных гиперграфах.