📄Работа №7336
Тема: Гиперграфовые модели и методы решения дискретных задач управления в условиях неопределенности
Тип работы
Диссертации (РГБ)
Предмет
Математика
Объем:
161стр. листов
Год:
2004
Просмотров:
1070
470
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 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-дольных гиперграфах.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.