Книги, научные публикации
Pages: | 1 | 2 | -- [ Страница 1 ] --
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ КАРАЧАЕВО-ЧЕРКЕССКАЯ ГОСУДАРСТВЕННАЯ ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ
на правах рукописи
Омельченко Галина Георгиевна ГИПЕРГРАФОВЫЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ДИСКРЕТНЫХ ЗАДАЧ
УПРАВЛЕНИЯ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ 05.13.18 - Математическое моделирование, численные методы и комплексы программ Диссертация на соискание ученой степени кандидата физико-математических наук
Научный руководитель доктор физ.-мат.наук, профессор В.А. Перепелица Черкесск - 2004 2 Содержание ВВЕДЕНИЕ.............................................................................................................. 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. Выводы по второй главе.......................................................................... ГЛАВА 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 ЛИТЕРАТУРА................................................................................................. ВВЕДЕНИЕ Актуальность проблемы. Диссертационная работа посвящена разработке методов математического моделирования дискретных слабо структурированных процессов, для которых характерны множественность критериев, стохастичность, интервальность или нечеткость значений исходных данных. Как часть этой проблемы в настоящей работе рассматриваются различные постановки дискретных задач управления: задача обучения сотрудников организации [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), приводящий к появлению несуществующего элемента в исходных данных гиперграфовой задачи.
e e e Рис.1. 4-вершинный гиперграф G = (V, E ), E = {e1, e2, e3 }, e1 = (1,2,3), e2 = (1,3,4), e3 = (1,2,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. Полиномиальный алгоритм сведения задачи о покрытии 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 дан краткий анализ видов неопределенности информации, характерных для экономических, социальных и других систем, связанных с участием человека [10, 21, 51]. Для математического моделирования дискретных слабо структурированных процессов и систем, в которых присутствуют множественность критериев, стохастичность, интервальность или нечеткость значений исходных данных [5, 47, 49], одним из наиболее подходящих математических инструментариев структурирования объектов моделирования является инструментарий теории гиперграфов. Математическое моделирование на гиперграфах позволяет отразить в системном единстве взаимосвязь и взаимодействие основных факторов, составляющих содержание исследуемой задачи. В главе 1 приведены основные понятия теории гиперграфов [28, 32], которые используются в работе, поскольку, в отличие от графов, в научной и учебной литературе на русском языке практически отсутствуют доступные публикации. Пусть V - конечное непустое множество, а E = {e} - некоторое семейство непустых подмножеств e V, тогда пара (V, E ) называется гиперграфом G = (V, E ) с множеством вершин V = {v} и множеством ребер E = {e}. Гиперграф G = (V, E ) называется l -дольным, если его множество вершин разбито на доли (подмножества) Vs, s = 1,2,...l, так, что: 1) всякая пара вершин из одной доли является не смежной;
2) у всякого ребра e E каждая пара вершин v, v e принадлежат различным долям. Если в гиперграфе G нет кратных ребер и степень всякого ребра e E равна l ( e = l ), то такой гиперграф называют l -однородным. Гиперграф G называется 3-дольным 3-однородным, если множество вершин V разбито на три подмножества Vs, s = 1,3 так, что в каждом ребре e = (v1, v 2, v3 ) E его вершины принадлежат различным долям, т.е. v s Vs, s = 1,3. В этом случае гиперграф G будем обозначать через G = (V1,V2,V3, E ). Гиперграф G = (V, E ) называется частью гиперграфа G = (V, E ), если V V и E E.
Часть G = (V, E ) гиперграфа G = (V, E ) называется его подгиперграфом, если он образуется из исходного гиперграфа G путем удаления некоторых его вершин вместе с инцидентными им ребрами. Часть G = (V, E ) гиперграфа G = (V, E ) назовем реберным подгиперграфом, если из G удаляются только ребра. Если в l -однородном гиперграфе G = (V, E ) число вершин n = V кратно l, то совершенным сочетанием ( l -сочетанием) называется такой его реберный подгиперграф x = (V, E x ), в котором каждая компонента связности представляет некоторое ребро e E. Из этого следует, что мощность Ex = n = m. l В гиперграфе G = (V1,V2,V3, E ) простой звездой называется такая его часть z = (V1 z,V2z,V3z, E z ), Vsz Vs, s = 1,3, в которой всякая пара ребер e, e E z пересекается только в одной вершине v V1 z. Степенью звезды r (v) называют число ребер в ней. Допустимым покрытием гиперграфа звездами x = (Vx, E x ), Vx V, E x E называем подгиперграф G = (V, E ) гиперграфа G = (V, E ), каждая компонента связности которого является простой звездой степени r (v) с центром в некоторой вершине v V1, и каждая вершина v V3 инцидентна только одному ребру некоторой звезды с центром v V1. Ребро e E гиперграфа G называется N -взвешенным, если ему поставлена в соответствие последовательность неотрицательных чисел w (e) 0, = 1,2,..., N. Гиперграф называется N -взвешенным, если каждое его ребро является N -взвешенным. Если задача формулируется на гиперграфе G = (V, E ), то ее допустимое решение определяется в виде реберного подгиперграфа x = (V x, E x ), V x V, E x E, который может представлять собой совершенное сочетание (покрытие гиперграфа звездами);
X = X (G ) = {x} - множество всех допустимых решений (МДР) задачи на G. Математическое моделирование реальных задач приводит зачастую к многокритериальным постановкам, для которых лоптимальное решение отсутствует. В условиях многокритериальности возникает необходимость вместо оптимума искать множество альтернатив [79, 83]. Качество допустимых решений x X оценивается векторной целевой функцией (ВЦФ) F ( x) = ( F1 ( x), F2 ( x),..., FN ( x)), первые N1 критериев которой имеют вид MAXSUM F ( x) = eE x w (e) max, = 1, N вид MAXMIN, N1 N, а остальные ( N N1 ) (оценка определении критериев x имеют по этих наихудшему) критериев F ( x) = min w (e) max, = N1, N. eE В используются веса w (e), = 1,2,..., N, приписанные ребрам e E. ВЦФ F (x) ~ определяет собой в МДР X паретовское множество X X. В качестве искомого решения принимается полное множество альтернатив (ПМА), ~ обозначаемое через X 0. Подмножество X 0 X называется ПМА, если оно имеет минимальную мощность X 0, и при этом выполняется равенство ~ F ( X 0 ) = F ( X ), где F ( X * ) = {F ( x) : x X * } X * X. Принято говорить, что задача с ВЦФ F (x) обладает свойством полноты, если для всякого ее МДР найдутся такие параметры ВЦФ, при которых выполняются равенства ~ X 0 = X = X [26]. Теорема 1.1. Всякая векторная задача о совершенных сочетаниях на l дольных гиперграфах является полной, если ее ВЦФ содержит не менее двух весовых критериев вида MAXSUM и MAXMIN, и все ее допустимые решения x = (V, E x ) состоят из одного и того же количества ребер E x, x X. Теорема 1.2. Всякая векторная задача о покрытии l -дольного l однородного гиперграфа звездами является полной, если ее ВЦФ содержит не менее двух весовых критериев вида MAXSUM и MAXMIN, и все ее допустимые решения x = (V, E x ) состоят из одного и того же количества ребер E x, x X. В заключительной части главы 1 осуществляется постановка и построение математических моделей на гиперграфах: двукритериальной задачи кадрового менеджмента [68], задачи управления космическим командно-измерительным комплексом [41, 42], математической модели обучения сотрудников организации, математической модели назначения учителей в классы с учетом технологий обучения [70].
Глава 2 посвящена оценке структурной сложности многодольных однородных гиперграфов, обоснованию труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе, оценкам максимальной мощности МДР задачи о совершенных сочетаниях на гиперграфе и задачи покрытия гиперграфа звездами. задачи В о главе 2 также представлены: сочетаниях на полиномиальное сведение совершенных многодольном гиперграфе к задаче о максимальной клике на специальном графе, полиномиальный алгоритм 1 проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе, алгоритм 2 бесповторного перебора всех совершенных сочетаний в многодольном гиперграфе, полиномиальный алгоритм 3 сведения задачи покрытия многодольного однородного гиперграфа звездами к задаче о совершенных сочетаниях, включая вывод оценок вычислительной сложности этих алгоритмов. Одним из важнейших структурных свойств n -вершинного гиперграфа G = (V, E ) является количество ребер E в нем. В общем случае, когда речь идет о l -дольном l -однородном гиперграфе G = (V1,V2,...,Vl, E ), справедлива следующая Теорема 2.1. В любом n -вершинном l -дольном l -однородном l n гиперграфе число ребер ограничено сверху полиномом, причем, эта l верхняя оценка является достижимой, если n кратно l, т.е. в случае, когда доли гиперграфа G равномощны. Из теоремы 2.1 следует, что для задач, формулируемых на l -дольных l -однородных гиперграфах, объем исходных данных является полиномиально ограниченным в случае, когда l представляет собой независящую от n константу. Важно отметить, что предлагаемые в главе 1 математические модели базируются именно на гиперграфах такого вида. В контексте проблемы обоснования оценок вычислительной сложности векторных задач на гиперграфах обоснование их труднорешаемости существенным образом опирается на оценки максимальной мощности их МДР. В случае полноты рассматриваемой задачи мощности искомого ПМА и МДР совпадают, и максимальная мощность МДР, очевидно, является нижней оценкой вычислительной сложности нахождения ПМА, и, следовательно, рассматриваемая задача труднорешаема, если эта максимальная мощность растет экпоненциально от числа ребер в полном гиперграфе. Через 1 (n, l) обозначим максимальную мощность МДР задачи о совершенных сочетаниях на n -вершинном l -дольном l -однородном гиперграфе. Справедлива Теорема 2.2. При n, кратном l, максимальная мощность МДР задачи о совершенных сочетаниях на n -вершинном n. l гиперграфе определяется равенством 1 (n, l) = (m !) l 1, где m = Следствие 2.1. Максимальная мощность 1 (n, l) МДР задачи о совершенных сочетаниях на гиперграфе растет экспоненциально от размерности n. С учетом представленного в теореме 1.1 свойства полноты и следствия 2.1 является справедливой следующая теорема. Теорема 2.3. Задача о совершенных сочетаниях на n -вершинном l дольном гиперграфе является труднорешаемой, если ее ВЦФ содержит не менее двух критериев вида MAXSUM. В задаче о покрытии n -вершинного l -дольного l -однородного гиперграфа звездами обозначим через r = (r1, r2,..., rn ) вектор степеней звезд в допустимом покрытии x X ;
сумму этих степеней обозначим m = rt.
t = n Через J (n, l, n1 ) = {G} обозначим множество всех n -вершинных l -дольных l -однородных гиперграфов G = (V1,...,Vl, E ), n = n1 + m(l 1), в которых мощности долей Vs = n s, s = 1, l удовлетворяют следующим условиям:
V1 = n1, n1 m и оставшиеся доли являются равномощными ns = m, s = 2, l.
При выполнении этих условий допустимым решением задачи о покрытии гиперграфа звездами является такой реберный подгиперграф x = (V1,...,Vl, E x ) гиперграфа G J (n, l, n1 ), в котором каждая компонента связности представляет простую звезду степени rt r с центром в соответствующей вершине vt V1, t = 1,2,..., n1. Количество таких звезд в покрытии x равно числу n1 вершин в первой доле. Через 2 (n, l, r ) обозначим максимальную по всем векторам степеней r мощность МДР задачи о покрытии n -вершинного l -дольного l -однородного гиперграфа звездами. Оказывается, что эта максимальная мощность не зависит от варьирования компонент данного вектора степеней r = (r1, r2,..., rn ), и является справедливой Теорема 2.4.
Для всякого вектора степеней r = (r1, r2,..., rn ), удовлетворяющего условию r t = n t = n n1 = m, максимальная мощность МДР l определяется равенством задачи о покрытии n -вершинного l -дольного l -однородного гиперграфа звездами на гиперграфе G J (n, l, n1 ) (m!) l 1 2 ( n, l, r ) = 2 ( n, l ) =. r1 !r2 !...rn !
Следствие 2.2. Максимальная мощность 2 (n, l) МДР задачи покрытия гиперграфа звездами растет экспоненциально от размерности n. С учетом представленного в теореме 1.2 свойства полноты и следствия 2.2 является справедливой следующая теорема. Теорема 2.5. Задача о покрытии n -вершинного l -дольного l однородного гиперграфа звездами является труднорешаемой, если ее ВЦФ содержит не менее двух критериев вида MAXSUM. Для распознавания наличия совершенного сочетания в многодольном однородном гиперграфе G = (V1,...,Vl, E ), Vk = m = n, k = 1, l предлагается l полиномиальный алгоритм 1, который распознает и отсеивает ребра e E, не принадлежащие никакому совершенному сочетанию в G. Алгоритм 1 базируется на идее реализации гиперграфа G = (V1,...,Vl, E ) m -дольным специальным графом S = S (G ) = (U 1,...,U k,...,U m, R). Между ребрами e E и гипервершинами e U, U = UU k k = m существует взаимно однозначное соответствие, причем ребро = (e, e) принадлежит R тогда и только тогда, когда ребра e, e E не пересекаются в G. Идея алгоритма 1 заключается в том, что всякому совершенному сочетанию в гиперграфе G взаимно однозначно соответствует m -гипервершинная клика в специальном графе S. Сформулированы и доказаны необходимые условия принадлежности e U m -гипервершинной клике.
Неудовлетворяющие этим условиям гипервершины удаляются из S. На выходе алгоритма 1 получается тупиковый подграф S = S (G ). Доказаны следующие достаточные условия. Лемма 2.8. Если гиперграф G содержит совершенное сочетание, то на выходе алгоритма 1 получаем непустой тупиковый подграф S. Лемма 2.9. Если для гиперграфа G на выходе алгоритма 1 получаем тупиковый подграф S =, то G не содержит совершенного сочетания.
Верхняя оценка трудоемкости алгоритма 1 составляет ( 1 ) O E ( ).
Если в результате работы алгоритма 1 получен непустой тупиковый подграф S (G ), то для выделения совершенных сочетаний в гиперграфе используется представленный далее алгоритм 2. На вход алгоритма 2 подается m -дольный тупиковый подграф S (G ), из которого в ходе работы алгоритма выделяются m -вершинные клики, каждая из которых однозначно определяет собой некоторое допустимое решение исходной задачи о нахождении множества X = X (G ) всех совершенных сочетаний на l дольном l -однородном гиперграфе. На выходе алгоритма 2 формируется множество клик размерности m, которое определяет собой МДР X = X (G ) задачи о совершенных сочетаниях на гиперграфе. Оценивая вычислительную сложность ( 2 ), отметим, что все клики формируются последовательно и бесповторно, при этом каждое ребро R просматривается не более, чем количество этих клик. Отсюда получаем оценку сложности перечисления алгоритмом 2 всех совершенных сочетаний в l -дольном l -однородном n вершинном гиперграфе ( 2 ) O( R )(m !) l 1, m = n. l l -дольного l -однородного Далее в главе 2 описывается процесс нахождения множества допустимых решений задачи покрытия гиперграфа звездами, который состоит из трех этапов. Суть первого этапа заключается в полиномиальном сведении задачи покрытия звездами к задаче о совершенных сочетаниях на гиперграфе. Второй этап представляет собой последовательное выполнение алгоритмов 1 и 2, т.е. результатом второго этапа является МДР задачи о совершенных сочетаниях. Третий этап на базе МДР задачи о совершенных сочетаниях находит МДР задачи покрытия звездами данного l -дольного гиперграфа. Если в исходном гиперграфе G = (V1,...,Vl, E ), в котором V1 = n1, Vs = m = n n1, s = 2, l, для заданного вектора степеней r = (r1, r2,..., rn ) l выполняется необходимое условие r t = n t = m, то полиномиальное сведение задачи о покрытии такого гиперграфа звездами к задаче о совершенных сочетаниях осуществляется с помощью представленного в работе алгоритма 3. На выходе алгоритма 3 имеем n -вершинный l -дольный l -однородный гиперграф n G = (V1,V2,...,Vl, E ) с равномощными долями, где n = n + (rt 1) = n + (m n1 ) = ml. Результатом применения алгоритмов 1 и t = 2 к гиперграфу G является множество всех его совершенных сочетаний X (G ) = {x}. Лемма 2.10. Всякое совершенное сочетание x в гиперграфе G однозначно определяет собой допустимое покрытие x гиперграфа G звездами.
В главе дано содержательное и описание предложенного данных.
двухуровневого подхода в математическом моделировании дискретных задач в условиях многокритериальности неопределенности Двухуровневое моделирование заключается в следующем: 1) разработка общей схемы двухуровневого моделирования и выбор численных методов ее реализации;
2) разработка модели нижнего уровня, т.е. моделирование исходных данных и параметров задачи для модели верхнего уровня;
3) разработка модели верхнего уровня, т.е. формулировка и исследование экстремальной (векторной) задачи с нечеткими или интервально заданными параметрами, которые были получены на нижнем уровне моделирования. Математическая модель верхнего уровня - это модель теории оптимизации, на базе которой строится и обосновывается наиболее целесообразное решение поставленной задачи [6]. В качестве конкретной реализации двухуровневого моделирования в главе 3 приведен пример моделирования процесса выбора нижнем уровне моделирования осуществляется и принятия стратегии ведения строительства некоторой строительной компании. На структурирование экспертной информации об имеющихся в распоряжении строительной компании трудовых, временных и технических ресурсах, о предпочтениях клиентов. Построен алгоритм реализации метода аналитической иерархии для слабоструктурированной задачи выбора стратегии ведения строительства строительной компанией. На верхнем уровне моделирования формулируется и исследуется задача нахождения альтернативных проектов стратегии ведения строительства и выбор лучшей из них. Математическая постановка этой задачи представляет собой векторную задачу о совершенных сочетаниях в 3-дольном 3-однородном гиперграфе. Далее в главе 3 исследуется разрешимость интервальной задачи о совершенных сочетаниях на 3-дольном гиперграфе с помощью алгоритмов линейной свертки критериев (АЛСК). Интервальная задача заключается в том, что в гиперграфе G = (V, E ) вес всякого ребра e E представляется интервалом, т.е. отрезком числовой прямой w(e) = [ w1 (e), w2 (e)]. Следует отметить, что интервальные задачи являются крайним случаем неопределенности и возникают в условиях неточных заданных параметров задачи [40]. В этом случае на МДР X = {x} задается интервальная целевая функция (ИЦФ) вида MAXSUM w( x) = eE x w(e) max.
i = 1,2. Под Согласно определению операции сложения интервалов получим значение ИЦФ w( x) = [ w1 ( x), w2 ( x)], где wi ( x) = eE x w ( e), i решением интервальной задачи понимается такой элемент x 0 X, на котором значение ИЦФ достигает максимума. В этом случае рассматриваемая задача сводится к 2-критериальной задаче с тем же множеством допустимых решений X и векторной целевой функцией ВЦФ F ( x) = ( F1 ( x), F2 ( x)), где F1 ( x) = eE x w ( x) max, F2 ( x) = eE x d (e) max, d (e) = w (e) w1 (e).
Теорема 3.1. Паретовское множество задач с ИЦФ w(x) и ВЦФ F (x) совпадают. Алгоритмы линейной свертки критериев являются традиционными методами нахождения парето-оптимальных решений многокритериальных задач. Утверждение 3.1. Для любого вектора N = { = (1, 2,..., N ) : = 1, > 0, = 1,2,..., N } максимизирующий N элемент x*, на МДР X линейную свертку критериев F ( x) = F ( x) целевых функций F ( x), = 1,2,..., N, является ПО.
= Заметим, что АЛСК не всегда гарантируют нахождение всех ПО ~ ~ ~ X. Если ПМ X индивидуальной интервальной задачи и 2-критериальной x задачи содержит такой элемент x *, на котором не достигает максимума значение свертки F (x) ни при каком 2, то эти задачи неразрешимы с помощью АЛСК. Теорема 3.2. Для всякого 3-дольного гиперграфа G интервальная задача о совершенных сочетаниях с критериями вида MAXSUM неразрешима с помощью АЛСК. В Заключении сформулированы основные результаты и выводы диссертации, которые выносятся на защиту. Пользуясь возможностью, автор выражает глубокую благодарность своему научному руководителю зав. кафедрой прикладной математики Карачаево-Черкесской государственной технологической академии доктору физ.-мат.наук, профессору Виталию Афанасьевичу Перепелице. Хочу выразить огромную признательность руководителю Одесского научно исследовательского семинара по теории графов и гиперграфов профессору Александру Александровичу Зыкову за постоянную поддержку и внимание к моей работе. Особую благодарность и признательность выражаю профессору Израилю Хаимовичу Сигалу за многократные полезные консультации и помощь, а также за доверие, оказанное мне как молодому ученому. Благодарю профессора Елену Витальевну Попову, оказавшую техническую помощь при оформлении материалов диссертации.
ГЛАВА 1. ОСНОВЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ СЛОЖНЫХ СИСТЕМ НА БАЗЕ ТЕОРИИ ГИПЕРГРАФОВ 1.1. Учет неопределенности параметров в математическом моделировании В настоящее время наблюдается новый всплеск интересов к применению современных математических методов и дискретных моделей в экономике, бизнесе, сфере управления [21, 23, 30]. Отправной точкой, как в теории, так и в практике управления служат определенные заранее цели. Естественное желание узнать, как улучшить поведение системы и желание найти наилучшую стратегию управления, которая приведет к достижению поставленных целей, определили тематику этой работы. Наиболее поразительным свойством человеческого интеллекта является способность принимать правильные решения в обстановке неполной и нечеткой информации [80]. Построение моделей приближенных рассуждений человека и использование их в компьютерных системах будущих поколений представляет сегодня одну из важнейших проблем науки управления, а проблемы принятия решений в условиях неопределенности занимают в настоящее время особое место в информационных технологиях [33]. Математические методы стали широко применяться для описания и анализа сложных экономических, социальных и других систем [84]. Теория оптимизации создала совокупность методов, помогающих с использованием ЭВМ эффективно принимать решения при известных и фиксированных параметрах. Определенные успехи имеются и в том случае, когда параметры - случайные величины с известными законами распределения. Однако основные трудности возникают тогда, когда параметры обстановки оказываются неопределенными (хотя, может быть, и не случайными) и когда они в то же время сильно влияют на результаты решения.
Специалисты часто сталкиваются с необходимостью расчетов при наличии нечетко заданных параметров или неточной информации. Такого рода ситуации могут возникать как вследствие недостаточной изученности объектов, так и из-за участия в управлении человека или группы лиц. Особенность подобных систем состоит в том, что значительная часть информации, необходимой для их математического описания, существует в форме представлений или пожеланий экспертов. Но в языке традиционной математики нет объектов, с помощью которых можно было бы достаточно точно отразить нечеткость представлений экспертов. В связи с тем, что при построении формальных моделей чаще всего пользуются детерминированными методами, то тем самым вносят определенность в те ситуации, где ее в действительности не существует. Таким образом, точный количественный анализ подобных систем по своей сути мало пригоден и неэффективен, а в реальных экономических, социальных и других системах, связанных с участием человека, не имеет требуемого практического значения. Он не в состоянии охватить нечеткость человеческого мышления. Мир руководителя - нечеткий. Это утверждение наводит на мысль о том, что для моделей процессов управления больше подошли бы нечеткие математические методы, нежели классические. Значительное продвижение в этом направлении сделал Лотфи Заде в 1965 году. Предложенная им теория нечетких (размытых) множеств предназначалась для преодоления трудностей представления неточных понятий, анализа и моделирования систем, в которых участвует человек. Л.Заде расширил классическое канторовское понятие множества, допустив, что характеристическая функция (функция принадлежности элемента множеству) может принимать любые значения в интервале [0,1], а не только значения 0 либо 1. Такие множества были названы им нечеткими (fuzzy). Л.Заде определил также ряд операций над нечеткими множествами и предложил обобщение известных методов логического вывода. Введя затем понятие лингвистической переменной и допустив, что в качестве ее значений (термов) выступают нечеткие множества, Л.Заде создал аппарат для описания процессов интеллектуальной деятельности, включая нечеткость и неопределенность выражений. Дальнейшие работы профессора Л.Заде и его последователей заложили прочный фундамент новой теории и создали предпосылки для внедрения методов нечеткого управления в практику. Для обращения с неточно известными величинами также применяется аппарат теории вероятностей. Однако случайность связана с неопределенностью, касающейся принадлежности или непринадлежности некоторого объекта к обычному нерасплывчатому множеству. Это различие между нечеткостью и случайностью приводит к тому, что математические методы нечетких множеств совершенно не похожи на методы теории вероятностей. Они во многих отношениях проще вследствие того, что понятию вероятностной меры в теории вероятностей соответствует более простое понятие функции принадлежности в теории множеств. По этой причине даже в тех случаях, когда неопределенность в процессе принятия решений может быть представлена вероятностной моделью, обычно удобнее оперировать с ней методами нечетких множеств без привлечения аппарата теории вероятностей [91]. При управлении различными процессами необходимо обеспечить в реальном масштабе времени расчет и оптимизацию режима, который гарантированно будет лежать в области допустимых режимов. Стандартно применяемые методы мало подходят для решения задач такого класса из-за возможности появления произвольных неконтролируемых ошибок в результатах при наличии погрешностей в исходных данных. Поэтому при управлении такими системами приходится ориентироваться на самое неблагоприятное (экстремальное) сочетание факторов неопределенности и использовать понятие гарантированного результата [38, 48]. Наиболее перспективными особенностей в для нахождения решений с учетом отмеченных интервальные условиях неопределенности являются [35,66,96,99,100] и нечеткие [1,65] методы. Применение интервальных методов в вычислительных процессах позволяет находить интервалы, гарантированно содержащие решения (множество решений) тех или иных задач, что позволяет более адекватно учитывать имеющуюся неопределенность постановки задачи. В моделях управления наличие неопределенности может быть учтено представлением неопределенных параметров как случайных величин с известными вероятностными характеристиками, как нечетких величин с заданными функциями принадлежности или как интервальных величин с фиксированными интервалами изменения и нахождения решения задачи с помощью методов стохастического, Как нечеткого или интервального использование программирования. показывает практика, детерминированных моделей с четкими значениями параметров приводит к тому, что модель оказывается излишне грубой. Методы интервального анализа дают возможность построить модель для случая, когда для каждого из параметров задан интервал допустимых значений. Однако на практике в связи с наличием информации о том, что какие-то значения коэффициентов более допустимы, чем другие, описание этих параметров в виде нечетких множеств является более удачным. В этом случае на интервале дополнительно задается функция принадлежности, причем, если информация о различии допустимости имеет статистический характер, то эта функция может быть определена объективно, если нет - то субъективно, на основе приближенного отражения экспертом в агрегированном виде имеющегося у него неформализованного представления о значении этого параметра. Основные приложения математического моделирования в условиях вышеуказанной неопределенности находятся в таких областях, как искусственный интеллект, лингвистика, поиск информации, процессы принятия решений, распознавание образов, медицинская диагностика, психология, педагогика, право, экономика и других областях человеческой деятельности.
1.2. Гиперграфы. Некоторые определения и свойства К настоящему времени математическое моделирование дискретных слабо структурированных процессов и систем, для которых характерны множественность критериев, стохастичность, интервальность или нечеткость значений исходных данных, находится еще в зачаточном состоянии. Вместе с тем уже появилась ясность того, что наиболее подходящим математическим аппаратом для структурирования объектов моделирования является инструментарий теории гиперграфов, который позволяет отразить в системном единстве взаимосвязь и взаимодействие основных факторов, составляющих содержание исследуемой задачи. Отметим, что все недостающие термины и определения понятий теории графов достаточно полно изложены в монографиях [8,28,72,85,89]. Однако, в отличие от графов, в научной и учебной литературе на русском языке практически бы отсутствуют теории доступные гиперграфов публикации, [32]. которые это представляли основы Учитывая обстоятельство, приведем определения используемых в настоящей работе терминов и понятий, относящихся к гиперграфам. При этом будем придерживаться терминологии и обозначений, принятых в [28]. Пусть V - конечное непустое множество, Е - некоторое семейство непустых подмножеств множества V. Пара (V, E ) называется гиперграфом G = (V, E ) с множеством вершин V = {v} и множеством ребер E = {e}.
Число V вершин гиперграфа G называется порядком или размерностью этого гиперграфа. Если V = n и E = m (с учетом кратности ребер), то G называется (n, m) -гиперграфом. Если вершина v V принадлежит ребру e E, то будем говорить, что они инцидентны. Каждой вершине v V множество гиперграфа G сопоставим deg(v) = E (v) E (v) всех инцидентных ей ребер. Число называется степенью вершины v, а число вершин в ребре deg(e) = e - степенью ребра e. Поскольку ребрами гиперграфа могут быть лишь непустые подмножества вершин, то степень любого ребра не меньше единицы, т.е. deg(e) 1. Если в гиперграфе G = (V, E ) имеются пары ребер e, e E, представляющие собой равные подмножества вершин, то ребра e, e будем называть кратными, а сам гиперграф G, содержащий хотя бы одну пару кратных ребер, - мультигиперграфом. Вершина гиперграфа, не инцидентная никакому ребру, называется изолированной. Две вершины v и v гиперграфа G называются смежными, если существует ребро e E, содержащее обе эти вершины, и несмежными - в противном случае. Два некратных ребра e и e гиперграфа G назовем смежными, если e e. Петлей назовем ребро, инцидентное только одной вершине. Гиперграф G называется простым, если он не содержит петель и кратных ребер.
e e1 e v v6 e6 v7 v v8 e v1 v e e3 v 4 v Рис.1.1. Гиперграф G = (V, E ) На рис. 1.1 изображен гиперграф G = (V, E ) с множеством вершин V = {v1, v2,..., v9 }, n = 9, и множеством ребер E = {e1, e2,..., e7 }, где e1 = {v1, v2, v8 ), e2 = (v2, v3 ), e3 = (v3, v4, v7 ), e4 = (v6, v7, v8 ), e5 = (v5, v6 ), e6 = (v7 ), e7 = (v1, v2, v8 ). В гиперграфе G вершина v9 является изолированной, а ребра e1 и e7 кратными. Ребра нарисованы в виде эллипсов, охватывающих инцидентные им вершины. Заметим, что ребра степени 2 можно изображать вместо эллипсов простыми линиями, как в случае обычных графов. Гиперграфы G = (V, E ) и G = (V, E ) называются изоморфными, если существует сохраняющее отношение инцидентности взаимно однозначное соответствие между множествами вершин V, V и множествами ребер E, E.
Гиперграф G = (V, E ) называется частью гиперграфа G = (V, E ), если V V и E E. Часть G = (V, E ) гиперграфа G = (V, E ) называется его подгиперграфом, если он образуется из исходного гиперграфа G путем удаления некоторых его вершин вместе с инцидентными им ребрами. Часть G = (V, E ) гиперграфа G = (V, E ) назовем реберным подгиперграфом, если из G удаляются только ребра [28]. Сочетанием в гиперграфе G называется такое подмножество E E, для любых двух различных ребер e и e которого их пересечение e e =, т.е. любые два ребра из E не смежные. Это сочетание называется максимальным, если оно содержит максимальное число несмежных ребер. Сочетание назовем совершенным, если его ребра покрывают все вершины гиперграфа G, и каждая вершина v V инцидентна в точности одному ребру этого сочетания. Среди всех совершенных сочетаний выделяем такое, у которого число сочетания (G ) = E является минимальным, и называем его минимальным совершенным сочетанием данного гиперграфа G. Если в гиперграфе G нет кратных ребер и степень всякого ребра e E равна l ( e = l ), то такой гиперграф называют l -однородным. Из этого определения следует, что у n -вершинного l -однородного гиперграфа G каждое сочетание является минимальным совершенным сочетанием, и число этого сочетания равно n. Ясно, что всякий 2-однородный гиперграф l является графом. Таким образом, гиперграф - обобщение известного понятия граф [8,28,72,89]. При l = 3 гиперграф G будем называть 3-однородным.
V V V 8 e 2 e4 e 3 e e 6 Рис. 1.2. 11-вершинный 3 -дольный 3 -однородный гиперграф G = (V1,V2,V3, E ) Гиперграф G = (V, E ) называется l -дольным, если множество V его вершин разбито на доли (подмножества) Vs, s = 1, l так, что выполняются два условия: 1) всякая пара вершин из одной доли является не смежной;
2) у всякого ребра e E каждая пара вершин v, v e принадлежит различным долям. Гиперграф G называется 3-дольным 3-однородным, если множество вершин V разбито на три подмножества Vs, s = 1,3 так, что в каждом ребре e = (v1, v 2, v3 ) E его вершины принадлежат различным долям, т.е. v S VS, s = 1,3. В этом случаем гиперграф G будем обозначать через G = (V1,V2,V3, E ). Рассмотрим гиперграф G = (V1,V2,V3, E ), V1 = {1,2,3,4}, V2 = {5,6,7}, V3 = {8,9,10,11}, E = {e1, e2,..., e5 }, где e1 = (1,5,9), e2 = (3,6,10), e3 = (4,7,11), e4 = (1,7,10), e5 = (2,5,8), представленный на рис. 1.2. Нетрудно увидеть, что в рассматриваемом гиперграфе имеются три тупиковых сочетания E1 = {e1, e2, e3 }, E2 = {e2, e3, e5 }, E3 = {e4, e5 }, Ei E, i = 1,3. Сочетание E0 E называется тупиковым, если любое ребро e ( E \ E0 ) пересекается хотя бы с одним ребром из E0. Отметим, что максимальное (совершенное) сочетание, согласно этого определения, также является тупиковым. Гиперграф, изображенный на рис. 1.2, содержит два максимальных сочетания E1 и E2. На рис.1.3 представлен 9-вершинный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ) с множеством ребер E = {e}, где e1 = (1,4,7), e2 = (2,5,8), e3 = (3,6,9), e4 = (1,5,8), e5 = (2,4,7), e6 = (3,5,8).
1 4 Рис.1.3. 9-вершинный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ) 7 Рис.1.4. Совершенное сочетание x1 = (V, E x ) На рис.1.4 и рис.1.5 для гиперграфа G = (V1,V2,V3, E ) представлены его совершенные сочетания x1 = (V, E x ) и x 2 = (V, E x ), в которых E x = {e1, e2, e3 ) 1 2 и E x = {e3, e4, e5 ).
Рис.1.5. Совершенное сочетание x 2 = (V, E x ) В гиперграфе G = (V1,V2,V3, E ) звездой называется такая его часть z = (V1Z,V2Z,V3Z, E Z ), VSZ VS, s = 1,3, в которой любые ребра e, e E Z пересекаются в одной и той же вершине v V 1 Z, т.е. мощность V1Z = 1, и не пересекаются ни в какой вершине v V3Z. Звезда называется простой, если всякая пара ребер e, e E Z пересекается только в одной вершине v V1Z. Степенью звезды r называют число рёбер в ней. Если в подгиперграфе G = (V, E ) гиперграфа G = (V, E ) каждая компонента связности является звездой с центром в некоторой вершине v V1, то G называем покрытием гиперграфа звездами. Допустимым является такое покрытие гиперграфа G простыми ребру некоторой звезды с центром v V1.
3 звёздами, степени которых равны r (v), и каждая вершина v V3 инцидентна только одному 4 5 11 Рис.1.6. 14-вершинный 3-дольный 3-однородный гиперграф G( ) На рис.1.6 представлен 14-вершинный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ) с множеством ребер E = {e}, где e1 = (1,3,9), e2 = (1,5,10), e3 = (1,6,11), e4 = (2,4,12), e5 = (2,7,13), e6 = (2,8,14), e7 = (1,4,9), e8 = (2,6,13). По своему определению допустимое покрытие 3-дольного гиперграфа G = (V, E ) = (V1,V2,V3, E ) звездами представляет собой такой его подгиперграф x = (Vx, E x ), V x V, E x E, в котором каждая компонента связности является звездой с центром в определенной вершине v V1, причем ее степень равна r (v). На рис.1.7 показано допустимое покрытие звездами с вектором степеней r = (r1, r2 ) = (3,3) гиперграфа, изображенного на рис.1.6.
3 9 5 6 2 Рис 1.7. Допустимое покрытие гиперграфа звездами Ребро e E гиперграфа G называется взвешенным ( N -взвешенным), если ему поставлено в соответствие некоторое неотрицательное число w(e) 0 (последовательность чисел w (e) 0, = 1,2,..., N ). Гиперграф называется взвешенным ( N -взвешенным), если каждое его ребро является взвешенным ( N -взвешенным).
1.3. Формулировка и обоснование свойства полноты векторных задач на однородных гиперграфах Математической постановке рассматриваемых в настоящей главе векторных задач предпошлем следующие обозначения:
Z 1 - задача о совершенных сочетаниях на гиперграфах;
Z 2 - задача о покрытии гиперграфа простыми звездами. При формулировке задачи Z 1 считается заданным взвешенный n вершинный l -однородный гиперграф G = (V, E ). Допустимым решением задачи Z 1 является совершенное сочетание x = (V, E x ), E x E на гиперграфе G. При формулировке задачи Z 2 считается заданным взвешенный n вершинный l -однородный гиперграф G = (V, E ). Допустимым решением этой задачи является такой реберный подгиперграф x = (V, E x ), E x E гиперграфа G, в котором каждая компонента связности представляет собой простую звезду. Обозначим через X = X (G ) = {x} множество всех допустимых решений (МДР) задачи Z 1 ( Z 2 ). Математическое моделирование реальных задач приводит зачастую к многокритериальным постановкам, для которых понятие лоптимальное решение отсутствует. В условиях многокритериальности возникает необходимость вместо оптимума искать множество альтернатив (МА) [79,83]. Среди различных постановок векторных задач в обзоре [27] рассмотрим многокритериальную задачу, в которой качество допустимых решений x X оценивается векторной целевой функцией (ВЦФ) F ( x) = ( F1 ( x), F2 ( x),..., FN ( x)), первые N 1 критериев которой имеют вид MAXSUM (1.1) F ( x) = eE x w (e) max, = 1,2,..., N 1, N 1 N, (1.2) а остальные ( N N 1 ) критериев имеют вид MAXMIN F ( x) = min w (e) max, = N 1 + 1, N 1 + 2,..., N. eE x (1.3) В определении этих критериев используются веса w (e), = 1,2,..., N, приписанные ребрам e E. ВЦФ (1.1) - (1.3) определяет собой на МДР X ~ задачи Z s, s = 1,2 паретовское множество (ПМ) X X, состоящее из паретовских оптимумов [79,83]. В качестве задачи искомого принимаем решения полное X 0. рассматриваемой множество ( N + 1) -критериальной (ПМА) [79,83], альтернатив обозначаемое через ~ Подмножество X 0 X называется ПМА, если оно имеет минимальную ~ мощность X 0 и при этом выполняется равенство F ( X 0 ) = F ( X ), где F ( X * ) = {F ( x) : x X * } X * X.
Принято говорить, что задача Z s, s = 1,2 с ВЦФ (1.1) - (1.3) обладает свойством полноты [26,73], если для всякого МДР X = X (G ) = {x} этой задачи существуют такие параметры ее ВЦФ, при которых выполняются равенства ~ X0 = X = X. К настоящему времени свойство полноты установлено (1.4) для ряда многокритериальных дискретных задач, сформулированных на графах [26]. Однако для многокритериальных задач на гиперграфах вопрос о свойстве полноты до сих пор оставался открытым. Рассмотрим этот вопрос в отношении сформулированных выше задач на гиперграфах. Пусть R N - евклидово пространство размерности N. Из определения ПМ и ПМА [79,83] вытекает, что справедлива следующая Лемма 1.1. Для всякой задачи с ВЦФ вида F : X R N выполняется ~ равенство мощностей X 0 = F ( X ). Для какой-либо задачи Z s, s = 1,2 с ВЦФ (1.1) - (1.3) рассмотрим ~ конкретную индивидуальную задачу с МДР X, ПМ X и ПМА X 0. Добавим к ВЦФ (1.1) - (1.3) новые критерии. Тогда получим другую индивидуальную задачу, у которой новая (расширенная) ВЦФ определяет на прежнем МДР X другие множества альтернатив (МА). Возникает вопрос о том, как соотносятся старые и новые МА. С учетом того, что добавление новых критериев не изменяет значений старых критериев (1.1) - (1.3) на всех допустимых решениях x X, справедлива следующая Лемма 1.2. При любом N 2 для всякой индивидуальной задачи с ВЦФ (1.1) - (1.3) добавление новых критериев к этой ВЦФ либо оставит ПМ ~ X и ПМА X 0 неизменным, либо пополнит их новыми решениями.
Теорема 1.1. Всякая векторная задача о совершенных сочетаниях на l однородных гиперграфах является полной, если ее ВЦФ (1.1) содержит не менее двух весовых критериев вида (1.2) - (1.3) и все ее допустимые решения x = (V, E x ) состоят из одного и того же количества ребер E x, x X.
Доказательство. Рассмотрим какую-либо задачу Z S, s = 1,2,... и выберем произвольное МДР X = X (G ), которое определяется данным n вершинным гиперграфом G = (V, E ). Для тривиальных случаев ( X = и X = 1) утверждение теоремы 1.1 очевидно.
Пусть X = X (G ) имеет мощность X 2 и на X определена ВЦФ (1.1) - (1.3). Покажем возможность задания весов ребер w(e) гиперграфа G так, ~ что для определяемых этой ВЦФ ПМ X и ПМА X 0 будут выполняться равенства (1.4). Для этого в гиперграфе G ребра e E перенумеруем числами t = t (e) = 1,2,..., E и веса этих ребер определим следующим образом:
w1 (t ) = 2 t, w2 (t ) = r 0 w1 (t ), t = 1,2,..., m, m = E, где r 0 = 2 m + 1.
(1.5) В настоящем доказательстве существенным образом используется равенство E x = q = q (n) x X, (1.6) которое выполняется для каждого МДР X = X (G ), определяемого для всякого n -вершинного гиперграфа G. Из (1.5) и (1.6) получаем F1 ( x) + F2 ( x) = q r x X.
(1.7) Обозначим разность R1, 2 = E1 \ E 2 для пары допустимых решений x1, x 2 X. Тогда для всякой пары x1, x 2 X имеем R1, 2 R2,1 =, R1, 2 = R2,1.
(1.8) Пусть среди элементов множества R1, 2 R2,1 ребро e с наименьшим номером t = t (e) принадлежит R1, 2. Тогда из (1.1) - (1.8) вытекают неравенства F1 ( x1 ) > F1 ( x 2 ), F2 ( x1 ) > F2 ( x 2 ), которые означают, что любая пара x1, x 2 X является векторно несравнимой по ВЦФ (1.1) - (1.3).
Последнее с учетом леммы 1.1 означает выполнение равенства (1.4). Для N = 2 теорема 1.1 доказана.
В силу леммы 1.2 равенства (1.4) выполняются и при N 3, если для = 1,2 критерии (1.2) - (1.3) определим согласно (1.5), а для = 3,4,..., N критерии (1.2) - (1.3) определим произвольным образом. Теорема 1.1 доказана. Рассматривая задачу Z покрытия l -дольного l -однородного гиперграфа звездами, отметим, что для нее, как и для рассмотренной выше задачи Z1 выполняется равенство (1.6). Отсюда, фактически повторяя доказательство теоремы 1.1, получаем, что является справедливой Теорема 1.2. Всякая векторная задача о покрытии l -дольного l однородного гиперграфа звездами является полной, если ее ВЦФ (1.1) содержит не менее двух весовых критериев вида (1.2) - (1.3) и все ее допустимые решения x = (V, E x ) состоят из одного и того же количества ребер E x, x X.
1.4. Постановка задач и построение математических моделей на гиперграфах 1.4.1. Двукритериальная задача кадрового менеджмента Рассмотрим экономико-математическую модель процесса кадрового обеспечения организации с учетом основных положений и методов индустриально-организационной психологии [20]. Объекты моделирования представлены в виде трех множеств: M 1 - множество людей, прошедших отбор и рассматриваемых в качестве претендентов на множество M 2. Элементами множества M 2 являются вакантные (условно вакантные) должности, которые включены в бизнес-план данной организации. поддерживающую M 3 - множество видов обучения, выполняющих функцию, функцию социализации и мотивации представителей множества M 1 [20]. Элементами множества M 3 являются виды начального, повторного и развивающего обучения:
рабочий инструктаж, ротация должностей, обучение в учебном центре на базе организации, обучение в вечерней школе, обучение на курсах повышения квалификации и переподготовки кадров, обучение в лицеях, колледжах, ВУЗах и академиях. Сформулируем следующую задачу. Претендента из M 1, прошедшего определенный вид обучения из M 3, назначить на соответствующую его способностям, образованию и ожиданиям должность из M 2. Результатом такого назначения должно стать повышение эффективности деятельности организации, выраженное в повышении общего уровня выполнения работы, реализации профессионального резерва потенциала людей, каждого сотрудника и формирования талантливых способностями которых организация могла бы воспользоваться в будущем.
С точки зрения математического моделирования эта задача представляет собой обобщение известной в теории дискретной оптимизации задачи о назначениях [82]. При определении допустимых решений этой задачи должны быть учтены ограничения на финансовые, производственные, трудовые и временные ресурсы, имеющиеся в распоряжении данной организации. Качество этих решений оценивается как экономическими (в рублях), так и социальнопсихологическими критериями. Значениями социально-психологических критериев могут служить результаты тестов (в баллах), которые проводятся для оценки детерминант, определяющих уровень и качество выполнения работы. Например, такими детерминантами в [20] являются способность, готовность и возможность выполнять работу. Таким образом, рассматриваемая задача формулируется как многокритериальная. Математическая постановка рассматриваемой задачи базируется на 3дольном 3-однородном гиперграфе G = (V1,V2,V3, E ), который определяется следующим образом. Вершины первой доли V1 (второй доли V2 ) поставлены во взаимно однозначное соответствие указанному выше множеству претендентов M 1 (множеству должностей M 2 ), т.е. имеет место равенство мощностей: V1 = M 1 ограничений ( V2 = M 2 ). Вершины третьей доли V3 отражают образом. Пусть элементы множества M множество видов обучения претендентов с учетом представленных выше следующим перенумерованы индексом r = 1,2,..., L, и для каждого значения r определено максимально возможное количество mr людей, для которых организация может осуществить r -й вид обучения;
обозначим R = mr. Каждому r =1 L индексу r {1,2,..., L} поставим в соответствие множество V3r = {v} мощности V3r = mr. Тогда третья доля V3 определяется как теоретико-множественное объединение всех множеств V, т.е. V3 = UV3r.
r 3 r = L Рассмотрим пару элементов v1 V1, v2 V2, где v означает определенного претендента, а v2 представляет определенную должность. Тогда, если кандидат v1 может заполнить вакансию v2 после прохождения r го вида обучения, согласно стратегии принятия решений о распределении вакантных должностей в данной организации [20], то считаем, что множество E содержит mr ребер вида e = (v1, v2, v), v V3r, V3r V.
(1.9) В противном случае множество E не содержит ни одного ребра вида (1.9). Ребро вида (1.9) условимся называть допустимой тройкой. Множество E всех ребер гиперграфа G = (V1,V2,V3, E ), V3 = UV3r образуется в результате r =1 L теоретико-множественного объединения допустимых троек вида (1.9) по всем элементам v1 V1, v2 V2, v3 V3, r = 1,..., L. В классической постановке задачи о назначениях, сформулированной на 2-дольном графе, как правило, термин допустимое решение означает совершенное (максимальное) паросочетание на этом графе. Допустимым решением рассматриваемой задачи на гиперграфе является всякое тупиковое сочетание. Для данного гиперграфа G = (V, E ) тупиковое сочетание представляем в виде его подгиперграфа x = (Vx, Ex ), Vx V, Ex E. Через X = X (G ) = {x} обозначим множество всех допустимых решений (МДР) задачи о сочетаниях на гиперграфе G. Каждому ребру e E вида (1.9) гиперграфа G = (V, E ) приписаны два веса w (e), = 1,2, которые означают w1 (e) = f1 (v1, v2, v3 ) - экономический эффект, т.е. ожидаемый доход организации (в рублях) претендент, представленный вершиной в случае, когда вид обучения, v1, прошел представленный вершиной v3, и назначен на должность, представленную вершиной v2 ;
w2 (e) = f 2 (v1, v2, v3 ) - социально-психологический эффект, т.е. ожидаемый уровень социализации [20] претендента (в баллах) в этом же случае. Качество допустимых решений этой задачи x X помощью векторной целевой функции (ВЦФ) F ( x) = ( F1 ( x), F2 ( x)), оценивается с (1.10) состоящей из критериев вида MAXSUM F ( x) = eE x w (e) max, = 1,2.
(1.11) Критерий F1 ( x) означает ожидаемый суммарный доход организации от указанного выше назначения. Критерий F2 ( x) означает ожидаемый уровень социализации должности. ВЦФ (1.10) - (1.11) определяет в МДР X паретовское множество (ПМ) % % X, состоящее из паретовских оптимумов (ПО) x [27]. В случае, если всех претендентов, назначенных на соответствующие одинаковые по значению ВЦФ решения % X x, x X считаются эквивалентными (неразличимыми), то из ПМ множество альтернатив (ПМА) X0.
выделяется полное представляет собой ПМА X % % максимальную систему векторно несравнимых ПО из X, X 0 X.
Наиболее целесообразное решение выбирается из ПМА с помощью процедур теории выбора и принятия решений [50].
1.4.2. Математическая модель задачи управления космическим командно-измерительным комплексом Командно-измерительный комплекс - это система сооружений и оборудования, него необходимого мощные для потоки контроля и управления высокий полетом уровень космических объектов, приема от них информации и ее обработки [7]. Для характерны информации, автоматизации, широкое применение различного рода радиотехнических систем и ЭВМ, Любое применение спутников предполагает, что с ними поддерживается хорошо налаженная, устойчивая двусторонняя радиосвязь. Связь с космическим объектом ведут радиотехнические станции, которые размещены во многих измерительных пунктах на суше и на море. Измерительные пункты по наземным, радио или космическим линиям связи соединены с Центром управления. В центр передаются результаты траекторных и телеметрических измерений, а на измерительные пункты из Центра - командная информация для космических объектов. Центр управления и измерительные пункты являются элементами командноизмерительного комплекса. Командно-измерительный комплекс управляет одновременно несколькими десятками космических объектов различного назначения. Поэтому возникает задача - наряду с планированием работы измерительных пунктов оптимально координировать использование командных, измерительных станций, ЭВМ и каналов связи, относящихся к каждому измерительному пункту. Для необходимо построения обозначить математической исходные модели поставленной задачи данные, объекты моделирования, выделить основные параметры, определяющие решение задачи, а также выбрать метод ее решения.
Основными параметрами, определяющими решение поставленной задачи, являются продолжительность (t ) и стоимость (s ) проводимого со спутником сеанса радиосвязи, а также достоверность и качество (k ) передаваемой на спутник и получаемой от него информации. Продолжительность сеанса радиосвязи со спутником (t ) равна интервалу времени между двумя моментами: первым, когда спутник входит в зону видимости, и вторым, когда спутник выходит из нее. Зона видимости - это область земной поверхности, пролетая над которой спутник может наблюдаться с измерительного пункта. Размеры зоны видимости определяются видом орбиты спутника (круговой или эллиптической), ее высотой, а также расстоянием смещения трассы спутника от центра зоны видимости. Кроме того, передача и прием сигналов со спутника, находящегося близко от горизонта, бывают неустойчивыми. Сеанс связи начинается не сразу от горизонта, а когда спутник поднимается над ним на некоторый угол, называемый минимальным углом возвышения антенны. Поэтому продолжительность сеанса связи (t ) с учетом вышеуказанных условий рассчитывается специалистами Центра управления для каждой пары спутник - измерительный пункт и, очевидно, представляет собой интервальную оценку. Стоимость сеанса связи (s ) отражает экономические затраты на обслуживание используемых в сеансе радиотехнических систем и ЭВМ, на создание программ и оплату работы сотрудников командноизмерительного комплекса, задействованных в данном сеансе связи. Очевидно, что стоимость сеанса связи является экспертной оценкой. Качество передаваемой и получаемой информации (k ) определяется ее достоверностью. Достоверность информации - это вероятность того, что передаваемая и получаемая информация не является ошибочной из-за ее трансформации помехами. Помехи сигнала возникают как при прохождении его по электрическим схемам, так и при прохождении его в атмосфере. Существуют различные способы повышения помехоустойчивости сигналов и повышения достоверности информации. Например, достоверность можно повысить во много раз, если использовать при передаче обратный канал, по которому на передающую сторону поступают сведения о том, как принята команда на спутнике. Между тем возрастание информации, передаваемой со спутников, как правило, нежелательно. В системах без обратного канала достоверность обеспечивается избыточностью команд. Кроме того, в зависимости от уровня помех, которые носят случайный характер, передача информации может повторяться несколько раз. Все эти способы ведут к уменьшению отношения количества полезной информации I p к общему количеству передаваемой и получаемой информации I. Таким образом, качество информации (k ), определяемое отношением Ip I и достоверностью, носит либо вероятностный характер, либо является экспертной оценкой. Содержательный смысл перечисленных выше основных параметров поставленной задачи убеждает нас в том, что мы имеем дело со сложной системой, для которой характерно одновременное наличие разнородной информации: 1) 2) 3) допустимых интервалов параметра t ;
статистических законов распределения и вероятностных оценок параметра k ;
экспертных (лингвистических) оценок параметров k и s. Все эти параметры отражают ту или иную степень неопределенности данных задачи. Исходные данные задачи представлены в виде нижеследующих множеств M i, i = 1,3.
M 1 - множество программ, которые специалисты готовят в Центре управления, а затем по линиям связи эти программы поступают на измерительные пункты и оттуда во время сеансов связи передаются на космические объекты. Программы отличаются друг от друга количеством передаваемой информации, т.е. числом команд, которое зависит от бортовых систем спутника, его программно-временного устройства (жесткая или гибкая у него программа управления), а также от объема решаемых этим спутником задач. Команды могут сначала вводиться в наземное программновременное устройство измерительного пункта, а затем при наступлении сеанса связи передаваться на спутник. Команды также могут передаваться спутнику прямо из Центра управления. В этом случае они проходят через измерительный пункт транзитом, не задерживаясь там. Первый способ уменьшает вероятность ошибок, возникающих в наземных линиях связи, т.к. представляет достаточное время для проверки правильности командной информации.
M 2 - множество измерительных пунктов космического комплекса, которые отличаются своими функциями и сложностью радиотехнического оборудования, а значит, и техническими возможностями проведения различного рода операций: управления полетом, траекторный контроль, телеметрический контроль, прием научной и прикладной информации. Существуют многофункциональные командно-измерительные системы: командно-траекторные, траекторно-телеметрические, командно-траекторнотелеметрические и т.д. В технике передачи и приема нет принципиальной разницы между научной и прикладной информацией, впрочем, так же как и между ними и телеметрической информацией.
M 3 - множество спутников, контроль полета которых и управление осуществляет командно-измерительный комплекс. Это множество составляют метеорологические, навигационные, геодезические, научные спутники и спутники связи. Содержательная суть задачи заключается в том, чтобы информацию (программу) из M 1 через задействованный измерительный пункт из M 2 передать на космический объект (спутник) из M 3. В результате полученное распределение с минимальными затратами экономических и временных ресурсов должно привести к повышению уровня достоверности передаваемой и получаемой информации. При определении решений этой задачи должны быть учтены ограничения на технические, временные, а также экономические ресурсы командно-измерительного комплекса. С точки зрения математического моделирования эта задача представляет собой обобщение известной задачи о назначениях [82]. Математическая постановка рассматриваемой задачи базируется на 3 дольном 3 -однородном гиперграфе G = (V1,V2,V3, E ), который определяется следующим образом. Вершины первой доли v V1 взаимно однозначно соответствуют элементам множества программ M 1. Каждая вершина второй доли v V2 взаимно однозначно соответствует элементам множества M 2 задействованных комплекса. измерительных третьей пунктов v V командно-измерительного поставлены во взаимно Вершины доли однозначное соответствие элементам множества спутников M 3. Для построения множества ребер E = {e} рассматриваем всевозможные тройки вершин (v1, v 2, v3 ) такие, что v1 V1, v2 V2, v3 V3. Всякую тройку называем допустимой, если программу v1 можно передать через измерительный пункт v 2 на космический объект v3. Множество всех ребер E = {e} определяется как множество всех допустимых троек e = (v1, v 2, v3 ), v s Vs, s = 1,3. Допустимым решением рассматриваемой задачи является всякое совершенное сочетание в гиперграфе G. Через X = X (G ) = {x} обозначим множество всех допустимых решений (МДР) задачи о сочетаниях на гиперграфе G. Содержательно МДР представляет множество всевозможных вариантов организации одновременных сеансов связи измерительных пунктов командно-измерительного комплекса со спутниками. Каждому ребру e E гиперграфа G = (V1,V2,V3, E ) приписаны три веса w (e), = 1,3, которые означают следующее:
w1 (e) = f 1 (v1, v 2, v3 ) - продолжительность сеанса связи со спутником (t, мин) в случае, когда спутник, представленный вершиной v3, наблюдается измерительным пунктом, представленным вершиной v 2 ;
w2 (e) = f 2 (v1, v 2, v3 ) - стоимость сеанса связи ( s, руб ), отражает экономические затраты в случае, когда программа, представленная вершиной v1, передается на спутник, представленный вершиной v3, через измерительный пункт, представленный вершиной v 2 ;
w3 (e) = f 3 (v1, v 2, v3 ) - качество передаваемой информации (k,%) в этом же случае. Качество допустимых решений этой задачи x X F1 ( x) = min w1 (e) max eE x оценивается с помощью векторной целевой функции (ВЦФ) F ( x) = ( F1 ( x), F2 ( x), F3 ( x)), где - критерий вида MAXMIN, гарантирует максимальное время для наихудшей по продолжительности сеанса связи пары спутник eE x - измерительный пункт в данном решении;
F2 ( x) = w (e) min - критерий вида MINSUM означает суммарный эффект, т.е. минимизацию всех финансовых затрат;
экономический eE x F3 ( x) = w3 (e) max - мультипликативная целевая функция, отражает достоверность всей передаваемой и получаемой командно-измерительным комплексом информации в данном варианте распределения сеансов связи. ВЦФ F ( x) = ( F1 ( x), F2 ( x), F3 ( x)) определяет в МДР X = X (G ) = {x} ~ паретовское множество (ПМ) X, состоящее из паретовских оптимумов (ПО) ~ [27]. В случае, если одинаковые по значению ВЦФ решения x, x X x ~ считаются эквивалентными (неразличимыми), то из ПМ X выделяется полное множество альтернатив (ПМА) X 0. ПМА X 0 представляет собой ~ ~ максимальную систему векторно несравнимых ПО из X, т.е. X 0 X. Решение задачи заканчивается тем, что из ПМА выбирается наиболее целесообразное решение с помощью процедур теории выбора и принятия решений [50].
1.4.3. Математическая модель обучения сотрудников организации Одним из важных этапов процесса социализации является обучение сотрудников организации [20]. Существует три варианта проведения обучения: на рабочем месте, на базе организации и в учебных заведениях. В выборе места обучения каждая организация учитывает особенности конкретной ситуации, характер работы, а также ресурсы, которые выделяются на обучение. Обучение на базе организации, как правило, проводят кадровые инструкторы в специальном помещении - учебном центре, и таким образом организация защищена от последствий слишком медленного или неправильного выполнения работы и, кроме этого, осуществляет полный контроль над качеством обучения. Требования к знаниям и умениям, которых должны достичь обучаемые в центре сотрудники, определяют программу обучения, в которой основным элементом является педагогическая методика, применяемая для научения в данной ситуации. Методы обучения для удобства разбиты на категории: методы пассивного, индивидуального активного и группового активного обучения [20]. Три основных метода обучения различаются в плане использования практики, обратной связи и подкрепления желаемого результата. Обучающий потенциал метода зависит не только от заложенных в нем возможностей, но и от того, как эти возможности используются. Эффективность любого метода можно повысить, если его будет применять высококвалифицированный инструктор. При выборе программы обучения следует учитывать и то, что ученики сильно отличаются друг от друга по своим способностям к учебе и в результате обучения достигают разных уровней того или иного умения. На эффективность конкретной программы обучения также влияют установки и ожидания обучающихся. Тесты способностей позволяют формировать группы по уровню обучаемости, чтобы, применив в программе обучения соответствующую обучения. этому уровню методику, достичь эффективности Исходными данными для построения математической модели обучения сотрудников на базе организации являются: G = {g} - множество групп учебного центра, сформированных по целям и задачам обучения, а также по уровню обучаемости на основании проведенного тестирования;
M = {m} - множество методов обучения [20]. Например, методы пассивного обучения, программированное обучение, компьютеризированное обучение, моделирование, дискуссионные методы, проигрывание ролей и следование образцу поведения, обучение с использованием видеоконференции;
I = {i} - множество кадровых инструкторов учебного центра, причем каждый инструктор, в зависимости от опыта, владеет несколькими методиками и может обучать одновременно несколько групп. Содержательная суть формулируемой задачи состоит в следующем. В каждую группу g G требуется назначить одного из инструкторов учебного центра i I, рекомендуя ему использовать в процессе обучения один из методов m M с учетом уровня обучаемости группы, знаний и умений, которых должны достичь обучающиеся сотрудники. Результатом такого назначения должно стать повышение эффективности обучения, оценку которой можно проводить на основе внутренних или внешних критериев. Внутренними критериями являются оценки эффективности, сделанные в период обучения. К ним относятся формальные тесты знаний и умений учеников и оценки, которые инструкторы выставляют ученикам за продвижение вперед и выполнение работы. Для оценки эффективности обучения по внешним критериям необходимо определить, в какой степени поведение учеников на работе после обучения соответствует желательному. При наличии положительных оценок, как по внутреннему, так и по внешнему критерию можно говорить об эффективности обучения. Это выражается в повышении общего уровня выполнения работы в организации, повышении общего уровня социализации сотрудников, а также усилении их мотивации, так как эффективное обучение повышает уверенность в успехе трудовой деятельности.
Математическая модель рассматриваемой в настоящей работе задачи базируется на специальном 3-дольном 3-однородном гиперграфе G = (V, E ) = (V1, V2, V3, E ), который строится следующим образом. Вершины первой доли, т.е. v V1, взаимно однозначно соответствуют элементам множества инструкторов учебного центра I. Каждой вершине v V1, соответствующей инструктору i I, приписано число n(v), определяемое числом групп, в которых данный инструктор будет работать. Вершинами второй доли v V2 являются элементы множества методов обучения M, а вершины третьей доли v V3 взаимно однозначно соответствуют элементам множества групп учебного центра. Для построения множества ребер E рассматриваем всевозможные тройки вершин (v1, v 2, v3 ) такие, что v1 V1, v 2 V2, v3 V3. Всякую тройку называем допустимой, если инструктор v1 может обучать группу v3, используя метод обучения v 2. Множество всех ребер E = {e} определяется как множество всех допустимых троек v i Vi, i = 1,3. Тем самым 3 -дольный 3 -однородный e = (v1, v 2, v3 ), гиперграф G = (V1, V2, V3, E ) построен. В рассматриваемой задаче для данного гиперграфа G = (V, E ) определены следующие условия: 1) в каждом ребре e = (v1, v 2, v3 ) E выделена пара вершин v1, v3, называемых концевыми для этого ребра;
2) 3) вершины v V2 являются внутренними вершинами;
концевые вершины v3 V3Z (степени 1);
4) для каждой вершины v из V1 указано число n(v ), которое служит ограничением на степень звезды с центром в вершине v. Допустимым является такое покрытие гиперграфа G звёздами, степени которых равны r (v), и каждая вершина v V3 инцидентна только одному ребру некоторой звезды. являются висячими вершинами Допустимым решением рассматриваемой задачи является всякий подгиперграф x = (V x, E x ), где Vx V, E x E, каждая компонента X = X (G ) = {x} связности которого представляет собой звезду. Через обозначим множество всех допустимых решений (МДР) задачи покрытия гиперграфа G звездами. Каждому ребру e E гиперграфа G = (V, E ) приписаны три веса w (e ), = 1,3, которые означают следующее: w1 (e ) = f 1 (v1, v 2, v3 ) - экономический эффект обучения, т.е. ожидаемый доход организации (в рублях) в случае, когда группа, представленная метода v2 вершиной под v3, прошла обучение с v1 ;
использованием руководством инструктора w2 (e ) = f 2 (v1, v 2, v3 ) - ожидаемый уровень обученности группы (в %);
w3 (e ) = f 2 (v1, v 2, v3 ) - социально-психологический эффект, т.е. ожидаемый уровень мотивации членов группы (в %) в этом же случае. Качество допустимых решений этой задачи помощью векторной целевой функции (ВЦФ) x X оценивается с (1.12) F ( x ) = (F1 ( x ), F2 ( x ), F3 ( x )), состоящей из критериев вида MAXSUM F ( x ) = eE x w (e ) max, Критерий = 1,3.
(1.13) Критерий F1 ( x ) означает ожидаемый суммарный доход организации от указанного выше обучения. F2 ( x ) означает ожидаемый организацией уровень специфических умений, знаний всех сотрудников, прошедших обучение. Критерий мотивации. ВЦФ (1.12) - (1.13) определяет в МДР X паретовское множество (ПМ) ~ X, состоящее из паретовских оптимумов (ПО) ~ [27]. В случае, если x одинаковые по значению ВЦФ решения ~ X F3 означает ожидаемый уровень их x, x X считаются эквивалентными (неразличимыми), то из ПМ выделяется полное множество представляет ~ ~ максимальную систему векторно несравнимых ПО из X, X 0 X.
альтернатив (ПМА) X 0. ПМА X собой Наиболее целесообразное решение выбирается из ПМА с помощью процедур теории выбора и принятия решений [50].
1.4.4. Математическая модель назначения учителей в классы с учетом технологий обучения Цели и задачи современного образования, положенные в основу концепции личностно-ориентированного обучения школьников, направлены на разрешение противоречий между базой знаний, умений и навыков, которые закладывает традиционная школа, и постоянно меняющимися требованиями, предъявляемыми к личности современными общественноэкономическими отношениями. Возникающие противоречия между уникальностью каждой личности и авторитарной методикой обучения с её набором педагогических штампов усиливают направленность школьного образования на его гуманизацию, на формирование личности ученика как наивысшей ценности. Изменения в целевых установках общеобразовательной школы, ориентация на создание оптимальных условий для развития творческого потенциала ребёнка с учётом его индивидуальных особенностей обозначили нижеследующую задачу. На пути реализации личностно-ориентированного обучения администрацией школы и педагогическим коллективом решается множество проблем. Одной из них является задача оптимального назначения учителейпредметников в классы. Решение этой задачи особенно важно при переходе параллели классов из начальной в общеобразовательную школу. В конце учебного года учителем и школьным психологом с помощью анкетирования, тестов и итоговых оценок проводится диагностика обучаемости, обученности, а также способности учащихся самостоятельно учиться, которая выражается показателем эффективности самостоятельной умственной деятельности [9,54,86,87]. Полученные при этом результаты каждой диагностики классов заносятся в таблицу, что позволит учителю в дальнейшем наиболее целесообразно спланировать свою работу с классом по формированию необходимых знаний, умений и навыков по предмету, включая наиболее самоконтроль и самоуправление распределении для построения развитием. учителей Более по того, совокупность всех результатов диагностики позволяет ставить вопрос о целесообразном данными классам модели данной рассматриваемой параллели с учетом их профессионального мастерства. Исходными U = {u} - параллели. T = {t} - множество современных педагогических технологий обучения [87]. Например, технология модульного обучения, интегральная технология, технология обучения с применением глобальных информационных сетей, технология уровневой дифференциации и методики диагностического целеполагания. K = {k } - множество классов данной параллели. Классы на основании результатов проведённых тестов отнесены к одному из уровней q Q сформированности учебно-организационных умений. Множество этих уровней Q = {q} определяется следующим образом: q = 0 - математической в классы организации личностно-ориентированного обучения в школе являются: множество учителей, назначаемых у учащихся отсутствует мотивация учебной деятельности;
q = 1 - учащиеся работают на репродуктивном уровне;
q = 2 - учащиеся работают на конструктивном уровне;
q = 3 - учащиеся работают на творческом уровне. Сформулируем следующую задачу. В каждый класс k K требуется назначить одного из учителей u U, рекомендуя ему использовать в процессе обучения одну из технологий должно стать повышение t T с учетом психологоучебной деятельности, педагогических характеристик этого класса. Результатом такого назначения уровня мотивации эффективности обучения в школе, повышение уровня обученности и самостоятельной умственной деятельности учащихся. Математическая модель рассматриваемой в настоящей работе задачи базируется на 3-дольном 3-однородном гиперграфе G = (V, E ) = (V1, V2, V3, E ), который строится следующим образом. Вершины первой доли, т.е. v V1, взаимно однозначно соответствуют элементам множества учителей U. Каждой вершине v V1, соответствующей учителю u U, приписано число m(v ), определяемое нагрузкой учителя, а именно количеством классов рассматриваемой параллели, в которых данный учитель будет работать. Каждая вершина второй доли v V2 однозначно соответствует некоторому элементу из множества технологий обучения T. Вершины третьей доли v V3 взаимно однозначно соответствуют элементам множества классов K.
Для построения множества рёбер E = {e} рассматриваем всевозможные тройки вершин (v1, v 2, v3 ) такие, что v1 V1, v 2 V2, v3 V3. Всякую такую тройку называем допустимой, если учитель v1 может вести занятия в классе v 3, используя технологию обучения v 2. Множество всех рёбер E = {e} определяется как множество всех допустимых троек e = (v1, v2, v3 ), vi Vi, i = 1,3. Тем самым 3-дольный 3-однородный гиперграф G = (V1, V2, V3, E ) построен. В рассматриваемой задаче для данного гиперграфа G = (V1,V2,V3, E ) выполняются следующие условия: 1) в каждом ребре e = (v1, v 2, v3 ) E выделена пара вершин v1, v3, вершины v V2 являются внутренними вершинами, и множество называемых концевыми для этого ребра;
2) V2 состоит из непустых попарно непересекающихся множеств V2 (v3 ), v3 V3, причем каждый элемент v V2 (v3 ) однозначно соответствует некоторой технологии t T ;
3) концевые вершины v3 V3Z являются висячими вершинами (степени 1);
4) для каждой вершины v из V1 указано число m(v ), которое является параметром следующего условия: принадлежащая допустимому покрытию звезда с центром в вершине v имеет степень r (v) = m(v) и при этом выполняется равенство m(v ) = V3.
vV По своему определению допустимое покрытие 3-дольного гиперграфа G = (V, E ) = (V1,V2,V3, E ) представляет собой такой его подгиперграф x = (V x, E x ), V x V, E x E, в котором каждая компонента связности является звездой с центром в определенной вершине v V1, причем ее степень равна r (v). Для определенных параметров r (v), v V1 в гиперграфе G = (V, E ) = (V1,V2,V3, E ) допустимым решением рассматриваемой задачи является всякий такой его подгиперграф x = (V X, E X ), V X V, E X E, в котором каждая компонента связности представляет собой простую звезду степени r (v) с центром в вершине v V1. Через X = X (G ) = {x} обозначим множество всех допустимых решений (МДР) задачи покрытия гиперграфа G звездами. Каждому ребру e E гиперграфа G = (V, E ) приписаны три веса w (e ), = 1,3, которые означают следующее: w1 (e ) = f1 (v1, v 2, v3 ) - ожидаемое изменение коэффициента мотивации учебно-познавательной деятельности учащихся класса (в %) в случае, когда учитель, представленный вершиной v1, назначен в класс, представленный вершиной v3 с использованием технологии обучения, представленной вершиной v2 ;
w2 (e ) = f 2 (v1, v 2, v3 ) - ожидаемое изменение (в том же случае) коэффициента обученности учащихся класса (в %);
w3 (e ) = f 3 (v1, v 2, v3 ) - ожидаемое изменение показателя эффективности активной самостоятельной умственной деятельности учащихся (в %) в этом же случае. Качество допустимых решений этой задачи x X оценивается с помощью векторной целевой функции (ВЦФ) F ( x ) = (F1 ( x ), F2 ( x ), F3 ( x )), (1.14) где F1 ( x ) - критерий вида MAXMIN, F1 ( x ) = min w1 (e ) max, что означает ожидаемый уровень мотивации учебно-познавательной деятельности F3 ( x ) - учащихся класса параллели, находящихся на самом низком уровне сформированности учебно-организационных умений;
критерии вида MAXSUM F ( x ) = eE x F2 ( x ) и w (e ) max, = 2,3, где критерий F2 ( x ) означает суммарное изменение ожидаемого уровня обученности учащихся всей параллели классов по предмету, а критерий F3 ( x ) - деятельности учащихся всех классов параллели. ~ ВЦФ F ( x ) определяет в МДР X паретовское множество (ПМ) X, состоящее из паретовских оптимумов (ПО) ~ [4]. В случае, если одинаковые x по решения x, x X считаются эквивалентными ~ (неразличимыми), то из ПМ X выделяется полное множество альтернатив значению ВЦФ суммарное изменение ожидаемого уровня активной самостоятельной умственной (ПМА) X 0. ПМА X 0 представляет собой максимальную систему векторно ~ ~ несравнимых ПО из X, X 0 X. Наиболее целесообразное решение выбирается из ПМА с помощью процедур теории выбора и принятия решений [50]. В качестве примера рассмотрим следующую ситуацию. Параллель состоит из пяти классов, которые обозначим K = {k1, k 2, k 3, k 4, k 5 }. Результаты проведенных тестов в этих классах определили множество рекомендуемых для использования технологий T = {t1, t 2, t3, t 4 }. Администрацией школы запланировано, что в этой параллели классов будут работать два учителя U = {u1, u 2 }, причем u1 будет работать в двух классах, а u 2 - в трех, и при этом принято решение, что учитель u1 (u 2 ) должен обязательно работать в классе k1 (k 5 ). Опишем процесс построения гиперграфа G = (V1,V2,V3, E ). Доля взаимно однозначное V1 = {v1, v2 } (V3 = {v1, v2, v3, v4, v5 }) поставлена во соответствие множеству U (K ). Доля V2 поставлена во взаимно однозначное соответствие множеству T, элементы которого рекомендованы методистом и школьным психологом для каждого класса и занесены в таб.1.1.
Таблица 1.1. Классы k1 k2 k3 Рекомендованные технологии t1 t1,t 3 t k4 k Построим множество ребер. e1 = (u1, t1, k1 ) t 2,t 4 t e7 = (u 2, t1, k 2 ) e2 = (u1, t1, k 2 ) e3 = (u1, t3, k 2 ) e4 = (u1, t 4, k 3 ) e5 = (u1, t 2, k 4 ) e6 = (u1, t 4, k 4 ) e8 = (u 2, t 3, k 2 ) e9 = (u 2, t 4, k 3 ) e10 = (u 2, t 2, k 4 ) e11 = (u 2, t 4, k 4 ) e12 = (u 2, t 3, k 5 ) Веса ребер w 0, = 1,3 заданы следующей таб.1.2.
Таблица 1.2. w1 (e) e1 e2 23 25 13 21 17 21 14 11 7 18 20 19 w2 (e) 20 13 10 18 12 23 19 15 12 15 8 16 w3 (e) 18 13 13 12 9 18 17 26 20 13 8 e3 e e5 e6 e7 e e9 e e11 e Представим все элементы МДР X = {x} рассматриваемой задачи.
x1 = (e1, e2, e9, e10, e12 ), x5 = (e1, e4, e7, e10, e12 ), x9 = (e1, e5, e7, e9, e12 ) x2 = (e1, e2, e9, e11, e12 ), x6 = (e1, e4, e7, e11, e12 ), x10 = (e1, e5, e8, e9, e12 ) x3 = (e1, e3, e9, e10, e12 ), x7 = (e1, e4, e8, e11, e12 ), x11 = (e1, e6, e8, e9, e12 ) x4 = (e1, e3, e9, e11, e12 ), x8 = (e1, e4, e8, e10, e12 ), x12 = (e1, e6, e7, e9, e12 ) Запишем в таб.1.3 значения критериев ВЦФ (1.14): Таблица 1.3. x1 x2 x3 x4 F1 ( x) 7 7 7 7 F2 ( x) 76 69 73 66 F3 ( x) 83 78 83 x5 x6 x7 x8 x9 x10 x11 x 14 14 11 11 7 7 7 88 81 77 84 79 75 86 79 74 83 88 83 92 101 На рис.1.8 представлено одно из допустимых решений x 4.
t k u t1 t t k k u t1 t k t k Рис. 1.8. Допустимое решение x ~ Из таб.1.3 получаем, что ВЦФ определяет в МДР X ПМ X, которое в ~ данном примере совпадает с ПМА X 0 : X = {x5, x8, x11, x12 } = X 0.
Найдем лексико-графический оптимум ЛГО этой задачи. Пусть критерии ВЦФ упорядочены и пронумерованы в порядке их относительной важности как в таб.1.3. Это означает, что для администрации школы в первую очередь необходимо повышение мотивации учебно-познавательной деятельности учащихся классов самого низкого уровня сформированности учебно-организационных умений, а затем повышение уровня обученности по предмету и повышение уровня активной самостоятельной деятельности учащихся всех классов параллели. Найдем X (1) - подмножество всех элементов x X, оптимальных по первому критерию F1 ( x), X (1) = {x5, x 6 }. X (2) - подмножество всех элементов x X (1), оптимальных по критерию F2 ( x), X ( 2 ) = {x5 }. Заметим, что x5 является ЛГО, а также ПО этой задачи. Это означает, что администрации школы можно рекомендовать назначить учителя u1 в класс k1 с использованием технологии t1 и в класс k 3 с использованием t 4, а учителя u 2 назначить в класс k 2 с использованием технологии обучения t1, в класс k 4 с использованием технологии t 2 и в класс k 5, рекомендуя при этом t3.
1.5. Выводы по первой главе Основной теоретический результат первой главы представляют теоремы 1.1 и 1.2 о достаточных условиях выполнения свойства полноты соответственно для многокритериальных задач о совершенных сочетаниях и о покрытии звездами l -дольного l -однородного гиперграфа. Важность этого результата заключается в том, что он является базой для обоснования факта труднорешаемости рассматриваемых в диссертации задач на гиперграфах. Представленные в первой главе математические модели на гиперграфах показывают, во-первых, практическую ценность применения инструментария теории гиперграфов в математическом моделировании, вовторых, демонстрируют прикладную универсальность этого инструментария и, в-третьих, дают общее представление о методике построения гиперграфовых моделей по содержательному описанию рассматриваемых задач.
ГЛАВА 2. АЛГОРИТМЫ НАХОЖДЕНИЯ ВСЕХ СОВЕРШЕННЫХ СОЧЕТАНИЙ И ПОКРЫТИЙ ЗВЕЗДАМИ МНОГОДОЛЬНЫХ ОДНОРОДНЫХ ГИПЕРГРАФОВ 2.1. Оценки числа ребер в l -дольных l -однородных гиперграфах Одним из важнейших свойств n -вершинного гиперграфа G = (V, E ) является количество ребер E в нем. Нетрудно видеть, что в гиперграфе с петлями величина E может достигать значения 2 n 1, т.е. является результатом суммирования биномиальных коэффициентов C q = n q n, где q = соответствует петлям, q = 2 соответствует ребрам графа, остальные q 3 соответствуют ребрам степени q {3,4,..., n}. Термины полный гиперграф с петлями и полный гиперграф относятся к таким гиперграфам G = (V, E ), у которых мощность n -вершинным ребер множества соответственно равна E = 2 n 1 и E = 2 n 1 n. Представленные в главе 1 математические модели базируются на 3дольных 3-однородных гиперграфах G = (V1,V2,V3, E ), V1 + V2 + V3 = n.
Важно отметить, что для таких гиперграфов мощность множества ребер E ограничена сверху полиномом 3-й степени от n. В общем случае, когда речь идет о l -дольном l -однородном гиперграфе G = (V1,V2,...,Vl, E ) справедлива следующая Теорема 2.1. В любом n -вершинном l -дольном l -однородном l n гиперграфе число ребер ограничено сверху полиномом, причем, эта l верхняя оценка является достижимой, если n кратно l, т.е. в случае, когда доли гиперграфа G равномощны.
Доказательство. Рассмотрим n -вершинный l -дольный l -однородный гиперграф G = (V1,V2,...,Vl, E ), для которого через ns обозначим мощность s й доли Vs = ns, n s = l s = n.
(2.1) Обозначим через E (v) множество всех ребер e E, инцидентных вершине v V1. Для мощности этого множества m(v) из определения l -дольного l однородного гиперграфа вытекает следующая верхняя оценка m(v) = E (v) ns, s = l (2.2) которая является достижимой. В силу условия l -однородности l -дольного гиперграфа для мощности множества его ребер с учетом (2.2) справедлива следующая верхняя оценка E m(v) n1 ns = ns, vV1 s=2 s = l l (2.3) которая также является достижимой. Правую часть выражения (2.3) можно интерпретировать, как объем l -мерного параллелепипеда в l -мерном евклидовом пространстве при условии, что сумма длин его сторон вида (2.1) равна одной и той же величине. Иными словами, вычисление верхней оценки мощности E свелось к известной изопериметрической задаче. Согласно этой задаче максимальное значение правой части оценки (2.3) достигается при выполнении равенств ns = l n, s = 1, l. Таким образом, получаем верхнюю l n оценку E, которая оказывается достижимой в случае, когда n кратно l l, т.е. доли являются равномощными.
Теорема 2.1 доказана. Примечание 2.1. Рассмотрим отмеченный в теореме 2.1 случай, когда в данном n -вершинном l -дольном гиперграфе G = (V1,V2,...,Vl, E ) его доли являются равномощными, т.е. их мощности Vs = m, s = 1, l, n = ml. Задачу Z 1 о сочетаниях в этом случае по аналогии с задачами на графах называем термином задача о совершенных сочетаниях на l -дольном l -однородном гиперграфе. Последний термин условимся обозначать символом Z1l. В дальнейшем, рассматривая задачу Z 1l на n -вершинном гиперграфе G = (V1,V2,...,Vl, E ) n = ml.
всегда будем подразумевать выполнение равенства Из теоремы 2.1 следует, что для задач, формулируемых на l -дольных l однородных гиперграфах, объем исходных данных является полиномиально ограниченным в случае, когда l представляет собой независящую от n константу. Важно отметить, что предлагаемые в главе 1 математические модели базируются именно на гиперграфах такого вида.
2.2. Обоснование труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе Принято говорить, что задача Z s, s = 1,2 с ВЦФ (1.1) - (1.3) обладает свойством полноты [27], если для всякого МДР X = X (G ) = {x} этой задачи существуют такие параметры ее ВЦФ, при которых выполняются равенства ~ X0 = X = X (2.4) К настоящему времени свойство полноты установлено для ряда многокритериальных дискретных задач, сформулированных на графах, в том числе и для задач о сочетаниях и гамильтоновых контурах [27]. Однако для многокритериальных задач на гиперграфах вопрос о свойстве полноты до сих пор оставался открытым. Рассмотрим этот вопрос в отношении сформулированных выше задач на гиперграфах. Пусть R N - евклидово пространство размерности N. Из определения ПМ и ПМА [27, 79] вытекает, что справедлива следующая Лемма 2.1. Для всякой задачи с ВЦФ вида F : X R N выполняется ~ равенство мощностей X 0 = F ( X ).
Для какой-либо задачи Z s, s = 1,2 с ВЦФ (1.1) - (1.4) рассмотрим ~ конкретную индивидуальную задачу с МДР X, ПМ X и ПМА X 0. Добавим к ВЦФ (1.1) - (1.3) новые критерии. Тогда получим другую индивидуальную задачу, у которой новая (расширенная) ВЦФ определяет на прежнем МДР X другие множества альтернатив (МА), например, ПМ или ПМА. Возникает вопрос о том, как соотносятся старые и новые МА. С учетом того, что добавление новых критериев не изменяет значение старых критериев (1.1) - (1.3) на всех допустимых решениях x X, справедлива следующая Лемма 2.2. При любом N 2 для всякой индивидуальной задачи с ВЦФ (1.1) - (1.3) добавление новых критериев к этой ВЦФ либо оставит ПМ ~ X и ПМА X 0 неизменными, либо пополнит их новыми решениями. Через J (n) = {G} условимся обозначать множество всех n -вершинных гиперграфов (графов). Пусть X = X (G ) = {x} - множество всех допустимых решений x = (Vx, E x ) рассматриваемой задачи на гиперграфе G = (V, E ), Vx V, E x E. Сформулированную на n -вершинных гиперграфах или графах G = (V, E ) задачу будем называть однородной, если для всякого гиперграфа G J (n) каждое допустимое решение x X (G ) содержит одинаковое количество ребер E x. С учетом п.1.3 будем считать, что однородные задачи на гиперграфах занумерованы индексом s = 1,2,... и обозначаются Z s. Лемма 2.3. Всякая однородная векторная задача на гиперграфах является полной, если ее ВЦФ (1.1) содержит не менее двух весовых критериев вида MAXSUM (1.2). Доказательство. Рассмотрим какую-либо задачу Zs и ее МДР X = X (G ) на произвольном n -вершинном гиперграфе G = (V, E ). Для тривиальных случаев ( X = и X = 1) утверждение леммы 2.3 очевидно. Пусть X = X (G ) имеет мощность X 2 и на X определена ВЦФ (1.1) - (1.3). Покажем возможность задания весов ребер w(e) гиперграфа G так, ~ что для определяемых этой ВЦФ ПМ X и ПМА X 0 будут выполняться равенства (2.4). Для этого в гиперграфе G ребра e E перенумеруем числами t = t (e) = 1,2,..., E и веса этих ребер определим следующим образом:
w1 (t ) = 2 t, w2 (t ) = w1 (t ), t = 1,2,..., r, r = E, где = 2 r + 1.
(2.5) В настоящем доказательстве существенным образом используется равенство E x = q = q (n) x X, (2.6) которое в силу условия однородности рассматриваемой задачи выполняется для каждого МДР X = X (G ), определяемого для всякого n -вершинного гиперграфа G. Из (2.5) и (2.6) получаем F1 ( x) + F2 ( x) = q x X.
(2.7) Обозначим разность R1, 2 = E1 \ E2 для пары допустимых решений x1, x2 X. Тогда для всякой пары x1, x2 X имеем R1, 2 R2,1 =, R1, 2 = R2,1.
(2.8) Пусть среди элементов множества R1, 2 R2,1 ребро e с наименьшим номером t = t (e) принадлежит R1, 2. Тогда при выполнении неравенства N1 2 в ВЦФ (1.1) - (1.3) из соотношений (2.5) - (2.8) вытекают неравенства F1 ( x1 ) > F1 ( x2 ), F2 ( x1 ) > F2 ( x2 ), которые означают, что любая пара x1, x2 X является векторно-несравнимой по ВЦФ (1.1) - (1.3). Последнее с учетом леммы 2.1 означает выполнение равенства (2.4). Для N = 2 лемма 2.3 доказана. В силу леммы 2.2 равенства (2.4) выполняются и при N 3, если для = 1,2 критерии вида MAXSUM (1.2) определим согласно (2.5), а для = 3,4,..., N критерии (1.2) - (1.3) определим произвольным образом.
Лемма 2.3 доказана. В контексте проблемы обоснования оценок вычислительной сложности векторных задач на гиперграфах полезно напомнить, что при рассмотрении этой же проблемы для векторных задач на графах обоснование их труднорешаемости существенным образом опиралось на оценки максимальной мощности их МДР [27]. В случае полноты рассматриваемой задачи мощности искомого ПМА и МДР совпадают, максимальная мощность МДР, очевидно, является нижней оценкой вычислительной сложности нахождения ПМА и, следовательно, рассматриваемая задача труднорешаема, если эта максимальная мощность растет экспоненциально от числа ребер в полном графе [27]. Это рассуждение остается в силе и для задач на гиперграфах. При обосновании оценок максимальной мощности МДР для задач на графах учитывалось свойство монотонность по ребрам для этих задач [43]. Суть этого свойства состоит в следующем. Пусть дан граф G = (V, E ) и определено его МДР X (G ) = {x}. Пополним множество E некоторым новым ребром e, в результате чего получен новый граф G = (V, E ), где E = E {e}. Тогда свойство монотонности по ребрам заключается в том, что для мощностей полученных МДР всегда выполняется неравенство X (G ) X (G ). В частности, задача о паросочетаниях на графах является монотонной по ребрам. Можно считать очевидным, что свойство монотонности по ребрам присуще и сформулированным выше в главе 1 задачам о сочетаниях на гиперграфе и о покрытии гиперграфа звездами. Поэтому обоснование оценок максимальной мощности МДР для задач Z s, s = 1,2 будем осуществлять, рассматривая эти задачи только на полных гиперграфах. Через 1 (n, l) обозначим максимальную мощность МДР задачи Z 1l о совершенных сочетаниях на гиперграфе. Справедлива n -вершинном l -дольном l -однородном Теорема 2.2. При n, кратном l, максимальная мощность МДР задачи Z1l на n -вершинном гиперграфе определяется равенством 1 (n, l) = (m!) l 1, где m = n. l X (G ) = {x}, x = (V1,V2,...,Vl, E x ) на n -вершинном гиперграфе Доказательство. Сначала отметим, что множество совершенных сочетаний G = (V1,V2,...,Vl, E ) является непустым только в случае равномощности долей этого гиперграфа, т.е. Vs = m = обозначение n, s = 1, l. Для вершин s -й доли введем l 1 s l. По определению, всякое s Vs = {v1s,..., vks,..., vm }, допустимое решение x состоит из m ребер, которые обозначим через ek, где индекс k {1,2,..., m} приписан тому ребру, которое содержит вершину 1 vk V1. Через E (v1 ) будем обозначать подмножество всех ребер e E, k инцидентных вершине v1 из первой доли V1. k С учетом этих обозначений в полном гиперграфе G будем последовательно строить элементы x X (G ), выбирая для очередного совершенного сочетания x его ребра e в порядке возрастания индекса k : k x = (V1,...,Vl, E x ), E x = {e1, e,..., e }. 2 m При выборе первого ребра e1 = (v1, v, v3,..., vl ) E (v11 ) для фиксированной вершины v1 выбор каждой из оставшихся вершин v из соответствующих долей Vs, s = 2, l можем s осуществить количеством способов, равным Vs = m. Таким образом, ребро e1 можем выбрать m l 1 различными способами.
Например, в представленном на рис.2.1 подмножестве E (v1 ) 9вершинного 3-дольного 3-однородного ( l = 3, m = 3 ) полного гиперграфа G = (V1,V2,V3, E ) ребро e1 E (v1 ) можем выбрать числом способов, равным E (v1 ) = m l 1 = 32 = 9.
6 Рис.2.1. Подмножество E (v1 ) E полного 9-вершинного 3-дольного 3однородного гиперграфа G = (V1,V2,V3, E ) После выбора для e в каждой из долей выбора Vs, по s = 2, l m остаются вершин.
незапрещенными последующего Следовательно, ребро e можно выбрать (m 1) l 1 способами. Пусть выбраны k 2 ребер, составляющих сочетание x. Тогда выбор очередного (k + 1) -го ребра e +1 можно осуществить числом способов, равным (m k ) l 1. Отсюда k следует, что число всех различных способов, которыми можно выбрать l ребер m для l 1 m сочетаний x X (G ) l равно произведению (m k + 1) k = = ( (m k + 1)) k = = (m!) l 1.
Теорема 2.2 доказана. Согласно теории вычислительной сложности [18] оценки величины этой сложности представляются в виде функций от длины записи исходной информации о задаче, задачи представляемой Z 1l на вход с алгоритма. точностью Для до рассматриваемой длина этой записи мультипликативной константы определяется числом ребер E в данном гиперграфе. Согласно теореме 2.1 имеем n l E O l (2.9) Следствие 2.1. Максимальная мощность 1 (n, l) МДР задачи о совершенных сочетаниях растет экспоненциально от размерности n. С учетом представленного в теореме 1.1 свойства полноты и следствия 2.1 является справедливой следующая теорема. Теорема 2.3. Задача Z1l является труднорешаемой, если ее ВЦФ (1.1) - (1.3) содержит не менее двух критериев вида MAXSUM (1.2). Доказательство. Рассмотрим задачу Z 1l, ВЦФ которой содержит не менее двух критериев вида MAXSUM. Согласно теореме 2.2 и лемме 2.3 в случае полного n -вершинного l -дольного l -однородного гиперграфа для записи искомого ПМА X 0 потребуется не менее (m!) l 1 операций, m = n. l При представлении этой трудоемкости в качестве единицы измерения используем оценку (2.9), т.е. разделим (m!) l n на = m l. В результате l l получим нижнюю оценку трудоемкости записи ПМА, равную 1 ((m 1)!)l1, m = n. l m Используя известную формулу Стирлинга (2.10) n! (n e) n 2n, нетрудно убедиться, что для достаточно ограниченных значений l величина (2.10) растет экспоненциально с ростом n. Теорема 2.3 доказана.
2.3. Оценки вычислительной сложности векторной задачи покрытия гиперграфа звездами Среди поставленных в п.1.2 задач реальную практическую значимость имеет задача покрытия l -дольного l -однородного гиперграфа простыми звездами.
Сформулируем математическую постановку этой задачи, обозначив ее через Z 2l (r ), где r = (r1, r2,..., rn ) представляет собой вектор степеней звезд в допустимом покрытии x X ;
сумму этих степеней обозначим через m = rt. Через J (n, l, n1 ) = {G} обозначим множество всех t =1 n n -вершинных l -дольных l -однородных гиперграфов G = (V1,...,Vl, E ), n = n1 + m(l 1), в которых мощности долей Vs = ns, s = 1, l удовлетворяют следующим условиям: мощность первой доли V1 = n1, n1 m и оставшиеся доли являются равномощными с количеством вершин в каждой из них:
ns = m, s = 2, l. При выполнении этих условий допустимым решением формулируемой задачи Z 2l (r ) является такой реберный подгиперграф x = (V1,...,Vl, E x ) гиперграфа G J (n, l, n1 ), в котором каждая компонента связности представляет собой простую звезду степени rt r с центром в соответствующей вершине vt V1, t = 1,2,..., n1. Количество таких звезд в покрытии x равно числу n1 вершин в первой доле;
X = X (G ) = {x} - МДР задачи Z 2l (r ) на гиперграфе G. При фиксированных значениях параметров n, l, r через 2 (n, l, r ) обозначим максимальную по всем векторам степеней r мощность МДР задачи Z 2l (r ) о покрытии n -вершинного l -дольного l -однородного гиперграфа звездами. Оказывается, что эта максимальная мощность не зависит от варьирования компонент данного вектора степеней r = (r1, r2,..., rn ), и является справедливой Теорема 2.4. Для всякого вектора степеней r = (r1, r2,..., rn ), удовлетворяющего условию r t = n t = n n1 = m, максимальная мощность МДР l задачи Z 2l (r ) на гиперграфе G = (V1,V2,...,Vl, E ) J (n, l, n1 ) определяется равенством (n, l, r ) = 2 (n, l) = (m!) l 1. r1 !r2 !...rn !
Доказательство.
Для бесповторного перечисления допустимых покрытий x X (G ) будем использовать специальный полный (n n1 ) вершинный (l 1) -дольный гиперграф G * = (V2,V3,...,Vl, E * ), равномощные доли которого унаследованы от рассматриваемого исходного гиперграфа G = (V1,...,Vl, E ), т.е. мощности e * = (v2, v3,..., vl ) E * Vs = n n1, l s = 2, l, а всякое ребро удаления из ребра получается путем e = (v1, v2, v3,..., vl ) E вершины v1 V 1. Через X (G * ) обозначим множество всех совершенных сочетаний в специальном полном гиперграфе G *. Примечание 2.2. Согласно теореме 2.2 мощность X (G * ) множества всех совершенных сочетаний в полном (l 1) -дольном гиперграфе G * определяется формулой 1 (n n1, l 1) = X (G * ) = (m!) l 2. Процесс построения звезд, образующих допустимое покрытие x = (V1,...,Vl, E x ) X (G ), E x E, осуществляется в два этапа. На первом этапе в специальном гиперграфе G * выделяется совершенное сочетание x * = (V2,V3,...,Vl, E x* ), E x* E *, состоящее из m ребер ek* = (v2k,..., v sk,..., vlk ), * * v sk Vs, s = 2, l, перенумерованных индексом k = 1,2,..., m. На втором этапе множество этих ребер разбивается на n1 подмножеств, перенумерованных индексом t = 1,2,..., n1 так, что t -ое подмножество состоит из rt ребер, где rt - степень звезды с центром в вершине vt V1, * ek r t = n t = m. Пополняя каждое ребро получаем ребро t -го подмножества вершиной vt V1, ek = (vt, v2k,..., vsk,..., vlk ) размерности l, принадлежащее исходному гиперграфу G. Тогда для фиксированного t полученные таким образом rt ребер образуют звезду степени rt с центром в вершине vt, причем эта звезда принадлежит исходному гиперграфу G. Множество полученных таким образом звезд с центрами в вершинах vt V1, t = 1,2,..., n1 образует по построению допустимое покрытие x X (G ). Обозначим через * алгоритм перечисления всех допустимых * покрытий звездами x X (G ). Этот алгоритм состоит из этапов 1* и 2. Этап 1* представляет собой алгоритм перечисления элементов множества X (G * ) = {x * } всех совершенных сочетаний (l 1) -дольного полного * гиперграфа G *. На этапе 2 всякое совершенное сочетание x * X (G * ) порождает множество M ( x * ) X (G ) всех допустимых решений x X (G ), каждое их которых состоит из звезд таких, что в результате удаления центров в этих звездах получаем ребра, образующие совершенное сочетание x *. Для описания процесса порождения множества M ( x * ) и вычисления его мощности рассмотрим фиксированное сочетание x * = (V2,V3,...,Vl, E x* ), * E x* E *, состоящее из m * ребер ek* = (v2k,..., v sk,..., vlk ), v sk Vs, s = 2, l, k = 1,2,..., m. При порождении всех звезд степени r1 с центром в вершине r v1 V1 можем из множества E x* выбрать r1 ребер C m различными способами.
* Далее при порождении следующей звезды с центром v2 V1 можем выбрать r r2 ее ребер C mr различными способами. Продолжая это рассуждение, 2 получаем, что мощность множества M ( x * ) составляет r r M ( x * ) = C m C m r...C m r r... r = 1 rn n m!, r1 !r2 !...rn !
(2.11) rn где с учетом равенства r1 + r2 +... + rn = m полагаем C m r r... r = C0 = 1.
rn 1 1 2 n Перенумеруем элементы множества X (G * ) и выберем из него пару совершенных сочетаний x1* = (V2,V3,...,Vl, E x* ), * * x2 = (V2,V3,...,Vl, E x* ). Для * всякой такой пары по определению множества X (G * ) всегда выполняется неравенство E x* E x*.
* 1 * (2.12) На основании определения множества M ( x * ), x * X (G * ) для всякого полного гиперграфа G * и соответствующего ему специального гиперграфа G * рассуждением от противного из неравенства (2.12) непосредственно получаем, что является справедливой следующая * * Лемма 2.4. Каждая пара совершенных сочетаний x1*, x2 X (G * ), x1* x порождает пару непересекающихся множеств допустимых решений * M ( x1* ), M ( x2 ) X (G ) ;
т.е. разные сочетания из X (G * ) не могут породить хотя бы одно одинаковое покрытие гиперграфа G звездами:
* M ( x1* ) M ( x2 ) =.
Заметим, что для всякой пары полный гиперграф G = (V1,...,Vl, E ) - его специальный гиперграф G * множество всех совершенных сочетаний X (G * ) можно получить путем последовательного удаления из всех ребер e E x вершин первой доли, являющихся и центрами звезд в покрытии x = (V1,...,Vl, E x ) X (G ), объединения * последующего теоретико-множественного сочетаний от противного получающихся Отсюда совершенных рассуждением x * = (V2,V3,...,Vl, E x* ) X (G * ).
непосредственно получаем, что является справедливой Лемма 2.5. Для всякой пары полный гиперграф G = (V1,...,Vl, E ) - его специальный гиперграф G * объединение множеств M ( x * ) по всем совершенным сочетаниям x * X (G * ) составляет МДР задачи Z 2l (r ) на гиперграфе G :
x*X ( G * ) U M (x * ) = X (G ).
Поскольку соотношение (2.11) выполняется для каждого x * X (G * ), то из лемм 2.4, 2.5 и теоремы 2.2 с учетом примечания 2.2 и равенств (2.11) получаем, что объединение всех порождаемых множеств M ( x * ) X (G ) по всем совершенным сочетаниям x * X (G * ) составляет МДР X (G ).
Мощность этого МДР является максимальной (т.е. определяется формулой X (G ) = 2 (n, l) ) и 2 (n, l) = M ( x * ) 1 (n n1, l 1) = Теорема 2.4 доказана.
(m!) l 1 m! (m!) l 2 =. r1 !r2 !...rn ! r1 !r2 !...rn !
1 Следствие 2.2. Максимальная мощность 2 (n, l) МДР задачи покрытия гиперграфа звездами растет экспоненциально от размерности n. С учетом представленного в теореме 1.2 свойства полноты и следствия 2.2 является справедливой следующая теорема. Теорема 2.5. Задача Z 2l (r ) является труднорешаемой, если ее ВЦФ (1.1) - (1.3) содержит не менее двух критериев вида MAXSUM (1.2). Доказательство. Рассмотрим такой полный n -вершинный l -дольный гиперграф G = (V1,...,Vl, E ), G J (n, l, n1 ), для которого выполняется условие n1 = n n1 n n. Тогда m = = и, согласно теореме 2.4 и лемме 2.3, для записи l l 1 l искомого ПМА X потребуется не менее (m!) l n = ! l l операций.
Используя в качестве единицы измерения трудоемкости оценку (2.9), разделим (m!) l на n. В результате получим нижнюю оценку l n ! l 1 l = (m!). l ml n l l l трудоемкости записи ПМА, равную (2.13) Используя формулу Стирлинга n! (n e) n 2n, нетрудно убедиться, что для достаточно ограниченных значений l величина (2.13) растет экспоненциально с ростом n. Тем самым по аналогии с теоремой 2.3 получаем доказательство теоремы 2.5. Теорема 2.5 доказана.
2.4. Алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе Пусть n кратно l и для пары n, l задан n -вершинный l -дольный l однородный гиперграф G = (V, E ) = (V1,...,Vl, E ), в котором доли равномощны ( V1 = V2 =... = Vl ), что является необходимым условием существования в G совершенного сочетания. Для этого гиперграфа через S = S (G ) = (U, R ) обозначим так называемый специальный граф. Элементами множества U являются гипервершины, каждая из которых представляет собой определенное (взаимно однозначным соответствием) ребро исходного гиперграфа G ;
R = { } - множество ребер графа S. Таким образом, количество гипервершин специального графа S совпадает с количеством ребер гиперграфа G : U = E. Условимся гипервершины в U обозначать символами ребер в гиперграфе G, т.е. U = {e}. Специальный граф S по своему определению является m -дольным, где m = доли гиперграфа n - мощность каждой l долей в G, k - индекс нумераций S, т.е.
S = (U 1,U 2,...,U m, R ).
Использование специального графа S = S (G ) обусловлено самой идеей предлагаемых ниже алгоритмов распознавания наличия и нахождения совершенных сочетаний в гиперграфе G. Суть этой идеи заключается в том, что всякому совершенному сочетанию в гиперграфе G взаимно однозначно соответствует (максимальная) m -вершинная клика в специальном графе S. Вершины, составляющие такую клику в специальном графе S, однозначно определяют собой в гиперграфе специального графа S = S (G ). На рис.2.2 и 2.3 представлены 12-вершинный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ) и соответствующий ему специальный граф G множество ребер, образующих совершенное сочетание. Ниже приводится описание процедуры построения S = S (G ) = (U 1,U 2,U 3,U 4, R ), который, согласно представленному определению, является 10-вершинным (т.к. в исходном гиперграфе G число ребер E = 10 ) и 4-дольным (т.к. в гиперграфе G мощность первой доли V1 = 4 ).
Рис.2.2. 12-вершинный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ) e1 = (1,5,9) e2 = (2,6,10) e3 = (3,7,11) e4 = (4,8,12) e5 = (1,7,12) e6 = (4,8,9) e7 = (3,6,10) e8 = (2,5,11) e9 = (1,6,11) e10 = (3,7,12) e1 e2 e e3 e4 e7 e6 e e8 e Рис.2.3. Специальный граф S = S (G ) для гиперграфа G на рис.2. Построение специального графа S = S (G ) = (U, R) = (U 1,...,U k,...,U m, R) осуществляется следующим образом. Пусть в гиперграфе G первая доля представляет собой множество V1 = {v1, v2,..., vm }.
Множество вершин специального графа U = {e} ставится во взаимно однозначное соответствие множеству ребер E = {e} так, что всякий элемент e U специального графа S представляет собой подмножество вершин v V данного гиперграфа G = (V, E ), образующих некоторое ребро e E, т.е. e V. Затем множество U разбивается на m долей таким образом, что доля U 1 состоит из всех таких вершин e U, каждая из которых содержит вершину v1 в первой доле исходного гиперграфа G, т.е. v1 V1 (на рис.2.3 доля U 1 состоит из вершин e1, e5, e9, каждая из которых содержит вершину v1 гиперграфа G на рис.2.2);
доля U 2 состоит из всех таких вершин e U, каждая из которых содержит вершину v2 также в первой доле исходного гиперграфа G, т.е. v2 V1 (на рис.2.3 доля U 2 состоит из вершин e2, e8, каждая из которых содержит вершину v2 гиперграфа G на рис.2.2);
Е ;
доля U m состоит из всех таких вершин, каждая из которых содержит вершину vm также в первой доле исходного гиперграфа G, т.е. vm V1 (на рис.2.3 доля U m, m = 4 состоит из вершин e4, e6, каждая из которых содержит вершину v4 в первой доле гиперграфа G на рис.2.2). Далее определяется множество ребер R = { } специального графа S. Для всякой пары вершин e, e U ребро = (e, e) включается в R тогда и только тогда, когда пересечение этой пары является пустым, т.е. e e = (среди десяти вершин e1, e2,..., e10 специального графа S = (U, R) на рис.2.3 двадцать пять пар вида (ei, e j ), 1 i < j 10 имеют пустое пересечение ei e j =, в силу чего мощность R = 25 ).
Формированием множества ребер R завершается построение специального графа S.
Обозначим через предлагаемый ниже алгоритм проверки выполнения необходимых условий существования совершенного сочетания в l -дольном l -однородном гиперграфе G. На вход этого алгоритма подается специальный граф S = S (G ) = (U, R ), в котором вершины первой доли перенумерованы индексом q = 1,2,..., L1, т.е. U 1 = {e1,..., e q,..., e L }, L1 = U 1.
Работа алгоритма 1 состоит из L1 этапов. Начало очередного q -го этапа состоит в фиксации очередной вершины e q U 1. Обозначим через U kq подмножество всех вершин, принадлежащих доле U k и смежных с фиксированной вершиной e q, k = 2,3,..., m. Объединение этих подмножеств вместе m k = с вершиной eq обозначим q U q = {e q } UU kq = {e q } U 2q... U kq... U m. В процессе своей работы этап q проверяет наличие m -вершинных клик в множестве U q и в случае их существования выделяет их. Если хотя бы одно из подмножеств U kq, k = 2, m является пустым, то этап q завершает работу безрезультатно, установив, что множество U q искомой клики не содержит. Например, в специальном графе на рис.2.3 для вершины e 3 = e9 подмножество U 23 является пустым, и поэтому этап q = 3 завершает работу безрезультатно. В противном случае в начале своей работы этап q объединяет эти подмножества вместе с e q и образует множество смежности этой вершины U q, U q U. Например, в специальном графе на рис.2.3 для вершины e1 = e1 это 1 1 множество имеет вид U = {e } UU k1, где U 2 = {e2 }, U 3 = {e3, e7, e10 }, 1 k = 1 U 4 = {e4 }, и таким образом, множество смежности вершины e1 = e представляется как U 1 = {e1} {e2 } {e3, e7, e10 } {e4 }. Индуцированный этим множеством в специальном графе S подграф обозначим через q S q = (U q, R q ) = (U 1q,...,U kq,...,U m, R q ). Отметим, что в специальном графе на рис.2.3 индуцированный множеством подграф S 1 представлен на рис.2.4.
U 1 = {e1} {e2 } {e3, e7, e10 } {e4 } e3 e1 e4 e7 e Рис.2.4. Подграф S 1 специального графа S на рис.2.3 Цель работы этапа q состоит в проверке ряда определенных ниже необходимых условий принадлежности рассматриваемой вершины какойлибо m -вершинной клике в подграфе S q. Если хотя бы одно из этих условий не выполняется, то этап q завершает свою работу безрезультатно. Работа этапа q реализуется на базе так называемой таблицы множеств смежности (кратко таблицы МС) T q = Tikq, в которой индекс k = 1,2,..., m представляет собой номера долей подграфа S q, а индекс i = 1,2,..., N q представляет собой новую порядковую нумерацию вершин этого подграфа. Более точно, множество q Uq представляется в следующем виде:
q U q = {e1q, e2q,..., eiq,..., e N }, N q = U q - мощность множества вершин подграфа S q. Условимся, что элементы множества U q нумеруются в порядке исчерпания долей U kq, k = 1, m подграфа S q. В таблице T q клетка Tikq представляет собой множество смежности (МС), более точно это МС является подмножеством Tikq U kq, состоящим из всех таких вершин доли U kq, каждая из которых смежна с вершиной eiq в подграфе S q. Если вершина eiq является элементом доли U kq, то согласно этому определению получаем одноэлементное МС Tikq = {eiq }, считая, что всякая вершина всегда смежна сама с собой. С учетом дольности подграфа S q таблица T q естественным образом разбивается на части Tkq, k = 1,2,..., m, где часть Tkq состоит из всех таких строк, которые соответствуют вершинам одной и той же доли U kq m -дольного подграфа S q. Число строк N kq, составляющих часть Tkq, равно числу вершин в доле U kq : N kq = U kq. В качестве иллюстративного примера построим таблицу МС для подграфа S 1 = (U 1, R1 ) на рис.2.4, у которого значение индекса q = 1 и вершина e q = e1 = e1. Элементы множества вершин этого подграфа в новой перенумерации индексом i = 1,2,...,6 получают следующие обозначения:
1 1 1 e1 = e11, e2 = e1, e3 = e3, e7 = e1, e10 = e5, e4 = e6. Т.к. число долей в S 1 равно 4, 2 то таблица МС T 1 = Tik1 для подграфа S 1 получает размерность N1 m = 6 4 (см. таб.2.1). Таблица 2. k =1 k = 2 e11 = e e1 = e2 1 e3 = e k = {e3, e7, e10 } k= {e4 } {e1} {e2 } {e1} {e1} {e1} {e2 } {e2 } {e3, e10 } {e3 } {e7 } {e4 } {e4 } {e4 } {e4 } e1 = e7 1 e5 = e10 {e1} 1 e6 = e {e2 } {e2 } {e10 } {e3, e7 } {e1} С учетом определения понятия л m -вершинная клика рассуждением от противного легко доказываются следующие ниже леммы о необходимых условиях принадлежности рассматриваемой вершины какой-либо вершинной клике в подграфе S q.
m Лемма 2.6 (Условие 1). Если вершина eiq принадлежит какой-либо m вершинной клике, то в i -ой строке таблицы МС T q каждая клетка Tik не является пустым множеством: Tik, k = 1,2,..., m. Для рассматриваемого иллюстративного примера таб.2.1 в строках i = 4 и i = 5 содержатся клетки с пустыми множествами. Эти строки соответствуют вершинам e7 и e10. Т.о. эти вершины можно исключить из рассмотрения и соответствующие им строки в таблице МС вычеркнуть. Рассмотрим в данной таблице МС размерности N m пару строк i, j, соответствующих вершинам ei, e j. Условимся, что термин пересечение МС строк i, j означает новую строку, состоящую из m множеств ( Tik T jk ), для каждого k = 1,2,..., m. Это пересечение называется непустым, если каждое из составляющих его множеств является непустым, т.е.
Tik T jk, k = 1,2,..., m. С учетом этих терминов, а также разбиения таблицы T q на части Tkq, k = 1, m сформулируем следующее необходимое условие. Лемма 2.7 (Условие 2). Если вершина eiq принадлежит какой-либо m вершинной клике, то i -я строка таблицы T q имеет непустое пересечение хотя бы с одной строкой из каждой части Tkq, k = 1, m этой таблицы. Для иллюстрации необходимого условия 2, представленного леммой 2.7, рассмотрим 5-дольный подграф S на рис.2.5. Соответствующая ему таблица МС представлена в виде таб.2.2, в которой каждая клетка Tik не является пустым множеством, т.е. имеет место выполнение необходимого условия 1, представленного леммой 2.6, для каждой вершины данного подграфа S. С учетом представленного разбиения таб.2.2 на части Tk, k = 1,5 рассмотрим пересечения МС строки 8 и строк 2 и 3, составляющих часть T2, Для этих пересечений имеем следующее невыполнение необходимого условия 2: T84 T24 = {e5 } {e6 ) = и T82 T32 = {e } {e3 } =. Следовательно, вершина e8 не принадлежит никакой 5-вершинной клике в данном 5-дольном подграфе S. Аналогично необходимое условие 2 не выполняется для строки 7 в таб.2.2. Поскольку рассмотренная пара вершин составляет всю 5-ю долю данного подграфа S, то является справедливым утверждение о том, что подграф S на рис.2.5 не содержит m -вершинных клик, откуда следует, что соответствующий ему исходный гиперграф не содержит совершенного сочетания, включающего ребро e1.
Pages: | 1 | 2 | Книги, научные публикации