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

Актуальность проблемы. Диссертационная работа посвящена разработке методов математического моделирования дискретных слабо структурированных процессов, для которых характерны множественность критериев, стохастичность, интервальность или нечеткость значений исходных данных. Как часть этой проблемы в настоящей работе рассматриваются различные постановки дискретных задач управления: задача обучения сотрудников организации [20], задача назначения учителей в классы с учетом технологий обучения [77], задача управления космическим командно-измерительным комплексом [7], задача выбора стратегии ведения строительства строительной компанией [34]. Классические подходы моделирования таких задач оказываются недостаточными по той причине, что представление параметров и структуры этих задач с помощью инструментария классической теории графов [53] оказывается в принципе неадекватным в силу невозможности отразить в системном единстве сложную организацию их внутренних взаимосвязей, ограничиваясь только понятиями и обозначениями этой теории.

Для математического моделирования значительного количества дискретных систем оказывается вполне достаточным использование аппарата теории графов. Однако, не редки случаи, когда не удается достичь требуемой адекватности с его помощью, в силу чего возникает необходимость использования аппарата теории гиперграфов. Обычно попытка представить гиперграф в виде соответствующего графа приводит к появлению ложных «допустимых» решений. Например, на 4-вершинном множестве V = {1,2,3,4} определен гиперграф с множеством ребер Е = {е1,е2,е3}, ех = (1,2,3), е2= (1,3,4), е3= (1,2,4), изображенный на рис. 1. Попытка представить эти ребра треугольниками, построенными из ребер графа на рис. 2, составляющих множество {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}, приводит к тому, что в результате получается «ложный» треугольник, состоящий из ребер (2,3), (2,4), (3,4), приводящий к появлению несуществующего элемента в исходных данных гиперграфовой задачи.

Рис. 1. 4-вершинный гиперграф G = (V, E), Е = {ех, е2, е3}, ех = (1,2,3), е2= (1,3,4), (1,2,4) 4.

Рис. 2. Представление ребер гиперграфа на рис. 1 треугольниками, состоящими из гоасЬовых оебео.

В качестве еще одной причины, по которой невозможно представить гиперграфовую задачу в виде теоретико-графовой, можно назвать реально существующее свойство неаддитивности функций, задающих веса ребер гиперграфов. Суть этого свойства заключается в том, что на практике оказывается нереальным определить правило или алгоритм, который представлял бы вес ребра гиперграфа в виде суммы весов вершин этого ребра или графовых ребер, определенных на множестве этих вершин.

Автором предлагается концепция двухуровневого моделирования рассматриваемых дискретных задач управления в условиях неопределенности. На нижнем уровне осуществляется моделирование исходных численных данных на базе экспертного оценивания [90]. Математическое моделирование верхнего уровня приводит к математическим постановкам многокритериальных задач на взвешенных гиперграфах. Весами ребер этих гиперграфов могут быть как действительные числа, так и интервалы или нечеткие множества. При этом заслуживают внимание следующие факты. Во-первых, к настоящему времени практически отсутствуют математические модели, сформулированные на базе теории гиперграфов, и тем более, отсутствуют алгоритмы (точные или приближенные) для экстремальных задач на гиперграфах. Известен лишь весьма ограниченный перечень задач на гиперграфах, относительно которых можно утверждать, что они являются NP-трудными [101]. Это утверждение в полной мере относится и к рассмотренной в диссертационной работе задаче о совершенных сочетаниях на многодольном гиперграфе и задаче покрытия много дольного однородного гиперграфа простыми звездами. Поэтому актуальной является разработка как точных переборных, так и приближенных малотрудоемких (полиномиальных) алгоритмов для решения этих задач. Наряду с этим актуальными также являются методы структурирования содержательных описаний дискретных задач управления в условиях неопределенности, для которых их данные в математической постановке заданы экспертными оценками.

Цель и задачи диссертационного исследования. Основной целью настоящей работы является разработка (на содержательном примере задачи обучения сотрудников организации, задачи назначения учителей в классы с учетом используемых технологий обучения, задачи управления космическим командно-измерительным комплексом, задачи выбора стратегии ведения строительства строительной компанией) двухуровневого подхода к математическому моделированию дискретных задач со сложной внутренней структурой в условиях неопределенности. Поставленная цель требует решения следующих задач:

— разработка в качестве основной составляющей модели нижнего уровня новых методов структурирования данных на базе идеи метода аналитической иерархии [81];

— разработка на базе конкретных слабоструктурированных задач методов построения гиперграфовых моделей верхнего уровня;

— исследование структурной сложности гиперграфовых моделей, а также вычислительной сложности (на базе обоснования свойства полноты) алгоритмов распознавания и нахождения допустимых решений задач о совершенных сочетаниях и покрытии гиперграфа звездами;

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

Методы исследования. Для решения поставленных в работе научных задач использованы методы теории алгоритмов с оценками, теории графов и гиперграфов, многокритериальной оптимизации, комбинаторного анализа и математического программирования, теории экспертных систем, теории нечетких множеств и интервального исчисления,.

Научная новизна. Научную новизну диссертационного исследования содержат следующие положения:

1. Построены на базе аппарата теории гиперграфов математические модели многокритериальных задач обучения сотрудников организации, назначения учителей в классы с учетом используемых технологий обучения, управления космическим командно-измерительным комплексом, выбора стратегии ведения строительства строительной компанией.

2. Достижимые верхние оценки количества ребер в полном многодольном однородном гиперграфе, а также максимальной мощности множества совершенных сочетаний и множества покрытий звездами многодольных гиперграфов.

3. Обоснование свойства полноты задачи о совершенных сочетаниях и о покрытии звездами многодольного гиперграфа, а также обоснование труднорешаемости этих задач в многокритериальной постановке.

4. Полиномиальное сведение задачи о совершенных сочетаниях на многодольном гиперграфе к задаче о максимальной клике на специальном графе.

5. Полиномиальный алгоритм проверки выполнения необходимых условий существования совершенного сочетания в много дольном гиперграфе.

6. Алгоритм бесповторного перебора всех совершенных сочетаний в много до льном гиперграфе.

7. Полиномиальный алгоритм сведения задачи покрытия многодольного однородного гиперграфа звездами к задаче о совершенных сочетаниях на гиперграфе.

8. Обоснование неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенном сочетании с векторной целевой функцией, состоящей из критериев весового вида.

Практическая ценность полученных результатов и их реализация. Практическая значимость результатов исследования заключается в том, что полученные в работе результаты могут быть использованы при формировании систем поддержки принятия решений в процессе математического моделирования задач управления сложными системами в условиях неопределенности, в том числе задачи обучения сотрудников организации [68], задачи назначения учителей в классы с учетом технологий обучения [70], задачи управления космическим командно-измерительным комплексом [41, 42] и задачи выбора стратегии ведения строительства строительной компанией. Идеи обоснования неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенном сочетании на гиперграфе, обоснование представленных алгоритмов могут быть использованы в дальнейших исследованиях в области дискретной многокритериальной оптимизации.

На защиту выносятся следующие основные положения:

1. Обоснованное свойство полноты задачи о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами.

2. Вывод достижимых верхних оценок структурной сложности многодольных однородных гиперграфов, на которых базируются рассматриваемые в диссертации математические модели: верхняя оценка количества ребер в полном многодольном однородном гиперграфе, оценка максимальной мощности множества совершенных сочетаний и максимальной мощности множества покрытий многодольного гиперграфа звездами.

3. Обоснование труднорешаемости задач о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами в многокритериальной постановке.

4. Полиномиальный алгоритм проверки выполнения необходимых условий существования в многодольном однородном гиперграфе совершенного сочетания.

5. Алгоритм выделения всех совершенных сочетаний в много дольном однородном гиперграфе, включая вывод оценки вычислительной сложности этого алгоритма.

6. Полиномиальный алгоритм сведения задачи о покрытии^{-дольного} £-однородного гиперграфа звездами к задаче о совершенном сочетании.

7. Структурирование задачи управления в условиях неопределенности данных сложной системы методом двухуровневого моделирования. Алгоритм реализации метода аналитической иерархии для слабоструктурированной задачи выбора стратегии ведения строительства строительной компанией.

8. Доказательство неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенном сочетании на гиперграфе с целевой функцией весового вида.

Апробация работы. Результаты исследования и основные его положения докладывались и обсуждались на заседаниях научно-методического семинара кафедры прикладной математики (КЧГТА, г. Черкесск, 2002;2004 гг.) и получили положительную оценку на следующих конференциях и симпозиумах, проводимых различными академическими учреждениями и высшими учебными заведениями России:

— на VIII Международном семинаре «Дискретная математика и ее приложения» (МГУ, 2004);

— на IV Международной конференции «Новые технологии в управлении, бизнесе и праве» (Невинномысск, 2004);

— на VIII Международной конференции «Образование. Экология. Экономика.

Информатика" (Астрахань, 2003);

— на IV Международной конференции молодых ученых и студентов (Самара,.

2003);

— на Международной научно-практической конференции «Наука и практика.

Диалоги нового века" (Набережные Челны, 2003);

— на III Международной конференции «Новые технологии в управлении, бизнесе и праве) (Невинномысск, 2003);

— на III Международной конференции молодых ученых и студентов (Самара,.

2002);

— на Международной школе-семинаре по геометрии и анализу памяти Н. В. Ефимова (Абрау-Дюрсо, база отдыха Ростовского госуниверситета «Лиманчик», 2002);

— на 11-ой Всероссийской конференции молодых ученых «Математическое моделирование в естественных науках» (Пермь, ПГТУ, 2002);

— на Дальневосточной конференции студентов, аспирантов и молодых ученых по математическому моделированию (Владивосток, 2002);

— на Y Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 2002);

— на X Международной конференции «Математика. Экономика. Образование». II Международный симпозиум «Ряды Фурье и их приложения» (Ростов-на-Дону, 2002);

— на IV научно-практической конференции «Решение научно-технических и социально-экономических проблем современности» (Черкесск, 2002);

А также на научно-исследовательских семинарах по графам и гипергафам под руководством проф. А. А. Зыкова (Одесса, 2002, 2003) [71].

Теоретические и практические результаты диссертационной работы использованы при выполнении НИР по гранту РФФИ, проект № 00−01−652 «Математическое моделирование структуры слабо формализованных систем в условиях неопределенности», НИР Министерства Обороны РФ (в/ч 32 103) «Исследование вопросов создания системы оценки космической обстановки для учета изменяющихся условий управления космическими аппаратами» [42] и «Исследование путей и способов повышения эффективности управления орбитальными группировками на основе адаптации системы управления КА к изменяющимся условиям космической обстановки» [41]. В результате внедрения разработанного научно-методического аппарата повышена оперативность решения задач управления космическими средствами на 20−25% при возможности сокращения на 7−12% трудозатрат, а использование разработанных в диссертации полиномиального алгоритма и алгоритма выделения всех совершенных сочетаний позволило на 53% повысить оперативность формирования исходных данных в системе поддержки принятия решений.

Материалы диссертации опубликованы в 13 научных статьях и в 14 тезисах докладов.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы, содержащего 101 наименование, а также приложений, включающих в себя программу реализации алгоритма.

3.4. Выводы по третьей главе.

Основным результатом третьей главы является предложенный автором конструктивный (т.е. реализованный конкретным алгоритмом) двухуровневый подход к математическому моделированию таких дискретных слабо структурированных многокритериальных задач, у которых исходные данные представляют собой экспертные оценки. Теоретическая и прикладная ценность этого подхода состоит в том, что слабоструктурированная задача полностью структурируется, т. е. сводится к четкой математической постановке в виде векторной задачи о совершенных сочетаниях на 3-дольном 3-однородном гиперграфе. Эта постановка включает в себя также известный случай наибольшей неопределенности, когда исходные данные (экспертные оценки) представляются в виде интервалов.

Исследованию последнего, т. е. интервального, случая посвящена заключительная часть третьей главы. Доказанные в этой части теоремы 3.1 и 3.2, во-первых, конструктивно обосновывают сведение интервальной задачи к двукритериальной и, во-вторых, выявляют факт неразрешимости интервальной задачи с помощью алгоритмов линейной свертки критериев. Особая ценность первого из этих результатов заключается в том, что в научных публикациях отсутствуют алгоритмы решения экстремальных интервальных задач, сформулированных как на графах, так и на гиперграфах.

ЗАКЛЮЧЕНИЕ

.

В ходе проделанной исследовательской работы получены следующие основные результаты:

1. Обосновано свойство полноты задачи о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами.

2. Дан строгий вывод достижимых верхних оценок структурной сложности многодольных однородных гиперграфов: верхняя оценка количества ребер в полном многодольном однородном гиперграфе, оценка максимальной мощности множества совершенных сочетаний и максимальной мощности множества покрытий многодольного гиперграфа звездами.

3. Обоснована труднорешаемость задач о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами в многокритериальной постановке.

4. Построен полиномиальный алгоритм проверки выполнения необходимых условий существования совершенного сочетания в много дольном гиперграфе.

5. Построен алгоритм бесповторного перебора всех совершенных сочетаний в много дольном гиперграфе.

6. Построен полиномиальный алгоритм сведения задачи покрытия многодольного однородного гиперграфа звездами к задаче о совершенных сочетаниях на гиперграфе.

7. Сформулирована концепция двухуровневого моделирования дискретных задач в условиях неопределенности: на нижнем уровне осуществляется моделирование исходных данных для модели верхнего уровня, математическая модель верхнего уровня — это модель теории оптимизации, на базе которой строится и обосновывается наиболее целесообразное управление рассматриваемым процессом. В качестве конкретной реализации двухуровневого моделирования представлена модель процесса выбора и принятия стратегии ведения строительства некоторой строительной компании. 8. Доказана неразрешимость с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенных сочетаниях с критериями вида MAXSUM на 3-дольных гиперграфах.