Бесплатно скачать, заказать диплом, курсовую, диссертацию ГИПЕРГРАФОВЫЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ДИСКРЕТНЫХ ЗАДАЧ УПРАВЛЕНИЯ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

У нас уже 176407 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

Название	ГИПЕРГРАФОВЫЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ДИСКРЕТНЫХ ЗАДАЧ УПРАВЛЕНИЯ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

Количество страниц	141

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23559.doc

Содержание	Содержание ВВЕДЕНИЕ..............................................................................................................4 ГЛАВА 1. ОСНОВЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ СЛОЖНЫХ СИСТЕМ НА БАЗЕ ТЕОРИИ ГИПЕРГРАФОВ........24 1.1. Учет неопределенности параметров в математическом моделировании 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}, ^ = (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. Структурирование задачи управления в условиях неопределенности данных сложной системы методом двухуровневого моделирования. Алгоритм реализации метода аналитической иерархии для слабоструктурированной задачи выбора стратегии ведения строительства строительной компанией. 10 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 дан краткий анализ видов неопределенности информации, характерных для экономических, социальных и других систем, связанных с участием человека [10, 21, 51]. Для математического моделирования дискретных слабо структурированных процессов и систем, в которых присутствуют множественность критериев, стохастичность, интервальность или нечеткость значений исходных данных [5, 47, 49] , одним из наиболее подходящих математических инструментариев структурирования объектов моделирования является инструментарий теории гиперграфов. Математическое моделирование на гиперграфах позволяет отразить в системном единстве взаимосвязь и взаимодействие основных факторов, составляющих содержание исследуемой задачи. В главе 1 приведены основные понятия теории гиперграфов [28, 32], которые используются в работе, поскольку, в отличие от графов, в научной и учебной литературе на русском языке практически отсутствуют доступные публикации. Пусть V - конечное непустое множество, а Е = {e - некоторое семейство непустых подмножеств есК, тогда пара )(V, E называется гиперграфом )G = (V, E с множеством вершин }V = {v и множеством ребер Е = {e}. Гиперграф )G = (V, E называется l -дольным, если его множество вершин разбито на доли (подмножества) Vs, s = 1,2,...l, так, что: 1) всякая пара вершин из одной доли является не смежной; 2) у всякого ребра e е E каждая пара вершин v',v"ee принадлежат различным долям. Если в гиперграфе G нет кратных ребер и степень всякого ребра e е E равна l (e = l), то такой гиперграф называют l-однородным. Гиперграф G называется 3-дольным 3-однородным, если множество вершин V разбито на три подмножества Vs, s = 1,3 так, что в каждом ребре e = (v1,v2,v3) e E его вершины принадлежат различным долям, т.е. vs e Vs, s = 1,3. В этом случае гиперграф G будем обозначать через )G = (V1, V2, V3, E). Гиперграф G' = (V',Er) называется частью гиперграфа )G = (V,E, если F'cF и E <^Е. Часть G' = (у',Е') гиперграфа )G = (V,E называется его подгиперграфом, если он образуется из исходного гиперграфа G путем удаления некоторых его вершин вместе с инцидентными им ребрами. Часть G' = (V,Er) гиперграфа )G = (V, E назовем реберным подгиперграфом, если из G удаляются только ребра. Если в l -однородном гиперграфе )G = (V, E число вершин n = V кратно l, то совершенным сочетанием (l -сочетанием) называется такой его реберный подгиперграф х = (V,Ex, в котором каждая компонента связности представляет некоторое ребро e е E. Из этого следует, что мощность

Список литературы

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23559.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

15.04.24 Задачи, условия и этапы организации экспериментальной работы

15.04.24 Критерии качества преподавания

15.04.24 Категория нормы в обучающей деятельности

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2022. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.