СОДЕРЖАНИЕ

На правах рукописи




Омельченко Галина Георгиевна




ГИПЕРГРАФОВЫЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ
ДИСКРЕТНЫХ ЗАДАЧ УПРАВЛЕНИЯ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ




Специальность 05.13.18 – математическое моделирование, численные методы и
комплексы программ




АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук




Ставрополь – 2004
Работа выполнена
в Карачаево-Черкесской государственной технологической академии
на кафедре «Прикладная математика»

Научный руководитель: доктор физико-математических наук, профессор
Перепелица Виталий Афанасьевич

Официальные оппоненты: доктор физико-математических наук, профессор
Наац Игорь Эдуардович

доктор технических наук, профессор
Сигал Израиль Хаимович

Ведущая организация: Кабардино-Балкарский государственный
университет им. Бербекова Х.М., г. Нальчик



Защита состоится 24 декабря 2004 г. в 14-30 часов на заседании диссертационного
совета Д 212.256.05 по присуждению ученой степени кандидата физико-
математических наук в Ставропольском государственном университете по адресу:
355009, г. Ставрополь, ул. Пушкина, 1, ауд. 214



С диссертацией можно ознакомиться в научной библиотеке СГУ по адресу:
г. Ставрополь, ул. Пушкина, 1.




Автореферат разослан « » ________ 2004 г.




Ученый секретарь
диссертационного совета
канд.физ.-мат. наук, доцент Л.Б. Копыткова
3
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность проблемы. Диссертационная работа посвящена разработке ме-
тодов математического моделирования дискретных слабо структурированных про-
цессов, для которых характерны множественность критериев, стохастичность, ин-
тервальность или нечеткость значений исходных данных. Классические подходы мо-
делирования таких задач оказываются недостаточными по той причине, что пред-
ставление структуры этих задач с помощью инструментария классической теории
графов оказывается в принципе неадекватным в силу невозможности отразить в сис-
темном единстве сложную организацию их внутренних взаимосвязей, ограничиваясь
только понятиями и обозначениями этой теории.
Автором предлагается концепция двухуровневого моделирования дискретных
задач управления в условиях неопределенности. На нижнем уровне осуществляется
моделирование исходных численных данных на базе экспертного оценивания. Мате-
матическое моделирование верхнего уровня приводит к математическим постанов-
кам многокритериальных задач на взвешенных гиперграфах. Весами ребер этих ги-
перграфов могут быть как действительные числа, так и интервалы или нечеткие
множества. Заслуживает внимания следующий факт, что к настоящему времени из-
вестен лишь весьма ограниченный перечень задач на гиперграфах, относительно ко-
торых можно утверждать, что они являются NP-трудными, и тем более, отсутствуют
алгоритмы (точные или приближенные) для экстремальных задач на гиперграфах.
Это утверждение в полной мере относится и к рассмотренным в диссертационной
работе задачам о совершенных сочетаниях и о покрытии многодольного однородно-
го гиперграфа простыми звездами. Поэтому актуальной является разработка как точ-
ных переборных, так и приближенных малотрудоемких (полиномиальных) алгорит-
мов решения этих задач. Вместе с тем актуальными являются методы структуриро-
вания содержательных описаний дискретных задач управления в условиях неопреде-
ленности, исходные данные которых в математической постановке заданы эксперт-
ными оценками.
Цель и задачи диссертационного исследования. Основной целью настоящей
работы является разработка (на содержательном примере задачи выбора стратегии
ведения строительства строительной компанией) двухуровневого подхода к матема-
тическому моделированию дискретных задач со сложной внутренней структурой в
условиях неопределенности. Поставленная цель требует решения следующих задач:
- разработка на базе конкретных слабоструктурированных задач методов по-
строения гиперграфовых моделей верхнего уровня;
- исследование структурной сложности гиперграфовых моделей;
4
- разработка алгоритмов проверки выполнения необходимых условий сущест-
вования в многодольном гиперграфе совершенного сочетания и алгоритмов нахож-
дения допустимых решений задачи о совершенных сочетаниях на гиперграфе и зада-
чи покрытия гиперграфа звездами, а также исследование (на базе обоснования свой-
ства полноты) вычислительной сложности этих алгоритмов.
- разработка в качестве основной составляющей модели нижнего уровня но-
вых методов структурирования данных на базе идеи метода аналитической иерархии.
Методы исследования. Для решения поставленных в работе научных задач
использованы методы теории алгоритмов с оценками, теории графов и гиперграфов,
многокритериальной оптимизации, комбинаторного анализа и математического про-
граммирования, теории экспертных систем, теории нечетких множеств и интерваль-
ного исчисления.
Достоверность и обоснованность полученных в диссертационной работе
теоретических результатов и формулировок обеспечивается корректным применени-
ем аппарата теории графов и гиперграфов, математического программирования и
теории вычислительной сложности алгоритмов, математического аппарата интер-
вального исчисления и нечетких множеств. Информационную базу исследования со-
ставили аналитические и статистические материалы Карачаево-Черкесского проект-
ного института, учебно-методического кабинета средней школы №4 г. Черкесска.
Эффективность и адекватность предложенных методов подтверждается валидацией
результатов, полученных в результате проведения численных расчетов.
На защиту выносятся следующие основные положения:
1. Обоснование свойства полноты задачи о совершенных сочетаниях и о покрытии
многодольного однородного гиперграфа звездами.
2. Вывод достижимых верхних оценок структурной сложности многодольных одно-
родных гиперграфов, на которых базируются рассматриваемые в диссертации мате-
матические модели: верхняя оценка количества ребер в полном многодольном одно-
родном гиперграфе, оценка максимальной мощности множества совершенных соче-
таний и максимальной мощности множества покрытий многодольного гиперграфа
звездами.
3. Обоснование труднорешаемости задач о совершенных сочетаниях и о покрытии
многодольного гиперграфа звездами в многокритериальной постановке.
4. Полиномиальный алгоритм проверки выполнения необходимых условий сущест-
вования в многодольном однородном гиперграфе совершенного сочетания.
5. Алгоритм выделения всех совершенных сочетаний в многодольном однородном
гиперграфе, включая вывод оценки вычислительной сложности этого алгоритма.
5
6. Полиномиальный алгоритм сведения задачи о покрытии l -дольного l -
однородного гиперграфа звездами к задаче о совершенном сочетании.
7. Структурирование задачи управления в условиях неопределенности данных
сложной системы методом двухуровневого моделирования.
8. Доказательство неразрешимости с помощью алгоритмов линейной свертки крите-
риев интервальной задачи о совершенном сочетании на гиперграфе с целевой функ-
цией весового вида.
Научная новизна. Научную новизну диссертационного исследования содержат
следующие положения:
1. Построены на базе аппарата теории гиперграфов математические модели много-
критериальных задач обучения сотрудников организации, назначения учителей в
классы с учетом используемых технологий обучения, управления космическим ко-
мандно-измерительным комплексом, выбора стратегии ведения строительства строи-
тельной компанией.
2. Достижимые верхние оценки количества ребер в полном многодольном однород-
ном гиперграфе, а также максимальной мощности множества совершенных сочета-
ний и множества покрытий звездами многодольных гиперграфов.
3. Обоснование свойства полноты задачи о совершенных сочетаниях и о покрытии
звездами многодольного гиперграфа, а также обоснование труднорешаемости этих
задач в многокритериальной постановке.
4. Полиномиальный алгоритм проверки выполнения необходимых условий сущест-
вования совершенного сочетания в многодольном гиперграфе.
5. Алгоритм бесповторного перебора всех совершенных сочетаний в многодольном
гиперграфе.
6. Полиномиальный алгоритм сведения задачи покрытия многодольного однородно-
го гиперграфа звездами к задаче о совершенных сочетаниях на гиперграфе.
7. Обоснование неразрешимости с помощью алгоритмов линейной свертки критери-
ев интервальной задачи о совершенном сочетании с векторной целевой функцией,
состоящей из критериев весового вида.
Практическая ценность полученных результатов заключается в том, что
они могут быть использованы при формировании систем поддержки принятия реше-
ний в процессе математического моделирования задач управления в условиях неоп-
ределенности. Идеи обоснования неразрешимости с помощью алгоритмов линейной
свертки критериев интервальной задачи о совершенном сочетании на гиперграфе,
обоснования представленных алгоритмов могут быть использованы в дальнейших
исследованиях в области дискретной многокритериальной оптимизации.
6
Апробация работы. Результаты исследования и основные его положения док-
ладывались и обсуждались на заседаниях научно-методического семинара кафедры
прикладной математики (КЧГТА, г. Черкесск, 2002-2004 гг.) и получили положи-
тельную оценку на следующих Международных конференциях и симпозиумах, про-
водимых различными академическими учреждениями и высшими учебными заведе-
ниями России:
– на VIII Международном семинаре «Дискретная математика и ее приложе-
ния» (МГУ, 2004);
– на научно-практической конференции «Научно-практические аспекты со-
вершенствования управления КА и информационного обеспечения запусков КА»
(Москва, МО РФ, в/ч 32103, 2004);
– на III и IV Международных конференциях «Новые технологии в управлении,
бизнесе и праве» (Невинномысск, 2003 и 2004);
– на VIII Международной конференции «Образование. Экология. Экономика.
Информатика» (Астрахань, 2003);
– на III, IV и V Международных конференциях молодых ученых и студентов
(Самара, 2002, 2003 и 2004);
А также на научно-исследовательских семинарах по графам и гипергафам под
руководством проф. А.А.Зыкова (Одесса, 2002, 2003).
Реализация результатов исследования. Теоретические и практические ре-
зультаты диссертационной работы использованы при выполнении НИР по гранту
РФФИ, проект № 00-01-00652 «Математическое моделирование структуры слабо
формализованных систем в условиях неопределенности», НИР Министерства Обо-
роны РФ (в/ч 32103) «Исследование вопросов создания системы оценки космической
обстановки для учета изменяющихся условий управления космическими аппарата-
ми» и «Исследование путей и способов повышения эффективности управления орби-
тальными группировками на основе адаптации системы управления КА к изменяю-
щимся условиям космической обстановки». В результате внедрения разработанного
научно-методического аппарата повышена оперативность решения задач управления
космическими средствами на 20-25% при возможности сокращения на 7-12% трудо-
затрат, а использование разработанных в диссертации полиномиального алгоритма и
алгоритма выделения всех совершенных сочетаний позволило на 53% повысить опе-
ративность формирования исходных данных в системе поддержки принятия реше-
ний.
Публикации. Материалы диссертации опубликованы в 9 научных статьях (из
них 3 – в рецензируемых журналах) и в 3 тезисах докладов.
7
Структура и объем работы. Диссертация состоит из введения, трех глав, за-
ключения, списка литературы, содержащего 101 наименование, а также приложений,
включающих в себя программу реализации алгоритма проверки выполнения необхо-
димых условий существования совершенного сочетания в многодольном гиперграфе,
описание нечеткой экспертной системы диагностики факторов выполнения работы, а
также двух актов внедрения результатов диссертационной работы.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы диссертационного исследо-
вания, сформулирована его цель, описана структура и дан краткий обзор работы, из-
ложены основные научные результаты, выносимые на защиту, раскрыта научная но-
визна и практическая значимость полученных результатов.
В главе 1 дан краткий анализ видов неопределенности информации, харак-
терных для экономических, социальных и других систем, связанных с участием че-
ловека. Для математического моделирования дискретных слабо структурированных
процессов и систем, в которых присутствуют множественность критериев, стохас-
тичность, интервальность или нечеткость значений исходных данных, одним из наи-
более подходящих математических инструментариев структурирования объектов
моделирования является инструментарий теории гиперграфов. Математическое мо-
делирование на гиперграфах позволяет отразить в системном единстве взаимосвязь и
взаимодействие основных факторов, составляющих содержание исследуемой задачи.
В главе 1 приведены основные понятия теории гиперграфов, которые исполь-
зуются в работе, поскольку, в отличие от графов, в научной и учебной литературе на
русском языке практически отсутствуют доступные публикации. Пусть 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 ? = (V ?, E ?) называется частью гипер-
графа G = (V , E ) , если V ? ? V и E ? ? E . Часть G ? = (V ?, E ?) гиперграфа G = (V , E )
называется его подгиперграфом, если он образуется из исходного гиперграфа G пу-
тем удаления некоторых его вершин вместе с инцидентными им ребрами. Часть
8
G ? = (V , E ?) гиперграфа G = (V , E ) назовем реберным подгиперграфом, если из G
удаляются только ребра. Если в l -однородном гиперграфе G = (V , E ) число вершин
n = V кратно l , то совершенным сочетанием ( l -сочетанием) называется такой его
реберный подгиперграф x = (V , E x ) , в котором каждая компонента связности пред-
n
ставляет некоторое ребро e ? E . Из этого следует, что мощность E x = = m.
l
На рис.1 представлен 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) . На рис.2 и рис.3 для гиперграфа
G = (V1 ,V2 ,V3 , E ) x1 = (V , E x )
представлены его совершенные сочетания и
1



x 2 = (V , E x ) , в которых E x = {e1 , e2 , e3 ) и E x = {e3 , e4 , e5 } .
2 1 2




1 4 7


2 5 8



3 9
6

Рис.1. 9-вершинный 3-дольный 3-однородный гиперграф G = (V1 ,V2 ,V3 , E )

4
1 7


5 8
2


3 6 9


Рис.2. Совершенное сочетание x1 = (V , E x ) гиперграфа G = (V1 ,V2 ,V3 , E )
1




4
1 7


5 8
2


3 6 9


Рис.3. Совершенное сочетание x2 = (V , E x ) гиперграфа G = (V1 ,V2 ,V3 , E )
2
9
В гиперграфе G = (V1 ,V2 ,V3 , E ) простой звездой называется такая его часть
z = (V1 z ,V2z ,V3z , E z ) , Vs z ? Vs , s = 1,3 , в которой всякая пара ребер e?, e?? ? E z пересе-
кается только в одной вершине v ? V1 z . Степенью звезды r (v) называют число ребер
в ней. Допустимым покрытием гиперграфа звездами x = (V x , E x ) , V x ? V , E x ? E
называем подгиперграф G ? = (V ?, E ?) гиперграфа G = (V , E ) , каждая компонента
связности которого является простой звездой степени r (v) с центром в некоторой
вершине v ? V1 , и каждая вершина v ? V3 инцидентна только одному ребру некото-
рой звезды с центром v ? V1 .

3 9


4 10
1
5
11

12
6


2 7 13


8 14


Рис.4. 14-вершинный 3-дольный 3-однородный гиперграф G = (V1 ,V2 ,V3 , E )

3 9


10
4
1

5
11

12
6


2 7 13


14
8

Рис.5. Допустимое покрытие гиперграфа звездами


На рис.4 представлен 14-вершинный 3-дольный 3-однородный гиперграф
G = (V1 ,V2 ,V3 , E ) с множеством ребер E = {e} , где e1 = (1,3,9) , e2 = (1,5,10) ,
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) . На
рис.5 показано допустимое покрытие гиперграфа G = (V1 ,V2 ,V3 , E ) звездами с векто-
ром степеней r = (r1 , r2 ) = (3,3) .
Ребро 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 . Математическое моделирование реальных задач приводит зачастую к
многокритериальным постановкам, для которых «оптимальное решение» отсутству-
ет. В условиях многокритериальности возникает необходимость вместо оптимума
искать множество альтернатив. Качество допустимых решений x ? X оценивается
векторной целевой функцией (ВЦФ) F ( x) = ( F1 ( x), F2 ( x),..., FN ( x)) , первые N1 кри-

? w? (e) > max ,? = 1, N , N1 ? N , а
териев которой имеют вид MAXSUM F? ( x) = 1
e?E x


остальные ( N ? N1 ) критериев имеют вид MAXMIN (оценка по наихудшему)
F? ( x) = min w? (e) > max ,? = N1 , N . В определении этих критериев используются ве-
e?E
x


са 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) обладает свойством полноты, если для всяко-
го ее МДР найдутся такие параметры ВЦФ, при которых выполняются равенства
˜
X0 = X = X .
Теорема 1.1. Всякая векторная задача о совершенных сочетаниях на l -
дольных гиперграфах является полной, если ее ВЦФ содержит не менее двух весо-
вых критериев вида MAXSUM и MAXMIN , и все ее допустимые решения
x = (V , E x ) состоят из одного и того же количества ребер E x , x ? X .
11
Теорема 1.2. Всякая векторная задача о покрытии l -дольного l -однородного
гиперграфа звездами является полной, если ее ВЦФ содержит не менее двух весовых
критериев вида MAXSUM и MAXMIN , и все ее допустимые решения x = (V , E x )
состоят из одного и того же количества ребер E x , x ? X .
В заключительной части главы 1 осуществляется постановка и построение
математических моделей на гиперграфах: двукритериальной задачи кадрового ме-
неджмента, задачи управления космическим командно-измерительным комплексом,
математической модели обучения сотрудников организации, математической модели
назначения учителей в классы с учетом используемых технологий обучения.
Глава 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 константу.
В контексте проблемы обоснования оценок вычислительной сложности век-
торных задач на гиперграфах обоснование их труднорешаемости существенным об-
разом опирается на оценки максимальной мощности их МДР. В случае полноты рас-
сматриваемой задачи мощности искомого ПМА и МДР совпадают, и максимальная
12
мощность МДР, очевидно, является нижней оценкой вычислительной сложности на-
хождения ПМА, и, следовательно, рассматриваемая задача труднорешаема, если эта
максимальная мощность растет экпоненциально от числа ребер в полном гипергра-
фе. Через µ1 (n, l) обозначим максимальную мощность МДР задачи о совершенных
сочетаниях на n -вершинном l -дольном l -однородном гиперграфе. Справедлива
Теорема 2.2. При n , кратном l , максимальная мощность МДР задачи о со-
вершенных сочетаниях на n -вершинном гиперграфе определяется равенством
n
µ1 (n, l) = (m !) l ?1 , где m =
.
l
Следствие 2.1. Максимальная мощность µ1 (n, l) МДР задачи о совершенных
сочетаниях на гиперграфе растет экспоненциально от размерности n .
С учетом представленного в теореме 1.1 свойства полноты и следствия 2.1
является справедливой следующая теорема.
Теорема 2.3. Задача о совершенных сочетаниях на n -вершинном l -дольном
гиперграфе является труднорешаемой, если ее ВЦФ содержит не менее двух крите-
риев вида MAXSUM .
В задаче о покрытии n -вершинного l -дольного l -однородного гиперграфа
звездами обозначим через r = (r1 , r2 ,..., rn ) вектор степеней звезд в допустимом по-
1

n1
крытии x ? X ; сумму этих степеней обозначим m = ? rt . Через J (n, l, n1 ) = {G} обо-
t =1

значим множество всех 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 ) , и является спра-
1


ведливой
13
Теорема 2.4. Для всякого вектора степеней r = (r1 , r2 ,..., rn ) , удовлетворяю-
1



n ? n1
n1

? rt = = m , максимальная мощность МДР задачи о покрытии
щего условию
l ?1
t =1

n -вершинного l -дольного l -однородного гиперграфа звездами на гиперграфе
(m !) l ?1
G ? J (n, l, n1 ) определяется равенством µ 2 (n, l, r ) = µ 2 (n, l) = .
r1 !r2 !...rn !
1



Следствие 2.2. Максимальная мощность µ 2 (n, l) МДР задачи покрытия ги-
перграфа звездами растет экспоненциально от размерности n .
С учетом представленного в теореме 1.2 свойства полноты и следствия 2.2
является справедливой следующая теорема.
Теорема 2.5. Задача о покрытии n -вершинного l -дольного l -однородного
гиперграфа звездами является труднорешаемой, если ее ВЦФ содержит не менее
двух критериев вида MAXSUM .
Для проверки выполнения необходимых условий существования совершен-
G = (V1 ,...,Vl , E ) ,
ного сочетания в многодольном однородном гиперграфе
n
, k = 1, l предлагается полиномиальный алгоритм ? 1 , который распозна-
Vk = m =
l
ет и отсеивает ребра e ? E , не принадлежащие никакому совершенному сочетанию в
G . Алгоритм ? 1 базируется на идее реализации гиперграфа G = (V1 ,...,Vl , E ) m -
дольным специальным графом S = S (G ) = (U 1 ,...,U k ,...,U m , R) . Между ребрами
m
e ? E и гипервершинами e ? U , U = U U k существует взаимно однозначное соот-
k =1

ветствие, причем ребро ? = (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 = O, то G не содержит совершенного сочетания.
14
( ).
Верхняя оценка трудоемкости алгоритма ? 1 составляет ? (? 1 ) ? O E
3




e1 e2 e3

e6
e4
e5

Рис.6. Специальный граф S (G )

e2
e1
e3

e4
e5



Рис.7. Тупиковый подграф S (G )
На рис.6 представлен 6-вершинный 3-дольный специальный граф S (G ) для
гиперграфа, изображенного на рис.1.
На рис.7 изображен полученный в результате работы алгоритма ? 1 тупиковый
подграф S (G ) , содержащий две клики.
Если в результате работы алгоритма ? 1 получен непустой тупиковый подграф
S (G ) , то для выделения совершенных сочетаний в гиперграфе используется пред-
ставленный далее алгоритм ? 2 . На вход алгоритма ? 2 подается m -дольный тупико-
вый подграф S (G ) , из которого в ходе работы алгоритма выделяются m -вершинные
клики, каждая из которых однозначно определяет собой некоторое допустимое ре-
шение исходной задачи о нахождении множества X = X (G ) всех совершенных со-
четаний на l -дольном l -однородном гиперграфе. На выходе алгоритма ? 2 форми-
руется множество клик размерности m , которое определяет собой МДР X = X (G )
задачи о совершенных сочетаниях на гиперграфе. Оценивая вычислительную слож-
ность ? (? 2 ) , отметим, что все клики формируются последовательно и бесповторно,
при этом каждое ребро ? ? R просматривается не более, чем количество этих клик.
Отсюда получаем оценку сложности перечисления алгоритмом ? 2 всех совершен-
15
n -вершинном гиперграфе
ных сочетаний в l -дольном l -однородном
n
? (? 2 ) ? O( R )(m !) l ?1 , m = .
l
Далее в главе 2 описывается процесс нахождения множества допустимых ре-
шений задачи покрытия l -дольного l -однородного гиперграфа звездами, который
состоит из трех этапов. Суть первого этапа заключается в полиномиальном сведении
задачи покрытия звездами к задаче о совершенных сочетаниях на гиперграфе. Вто-
рой этап представляет собой последовательное выполнение алгоритмов ? 1 и ? 2 , т.е.
результатом второго этапа является МДР задачи о совершенных сочетаниях. Третий
этап на базе МДР задачи о совершенных сочетаниях находит МДР задачи покрытия
звездами данного l -дольного гиперграфа.
G = (V1 ,...,Vl , E ) , в котором V1 = n1 ,
Если в исходном гиперграфе
n ? n1
Vs = m = , s = 2, l , для заданного вектора степеней r = (r1 , r2 ,..., rn ) выполня-
l ?1 1



n1

?r = m , то полиномиальное сведение задачи о покрытии
ется необходимое условие t
t =1

такого гиперграфа звездами к задаче о совершенных сочетаниях осуществляется с
помощью алгоритма ? 3 следующим образом. Каждая вершина первой доли vt ? V1
окрашивается в свой цвет t , t = 1,2,..., n1 и заменяется множеством вершин V1t = {vtk } ,
k = 1, rt , окрашенных в один и тот же цвет t . В результате в данном гиперграфе G
n1
его первая доля V1 преобразуется в множество V1 = UV1t = {vtk } , k = 1, rt , t = 1, n1 ,
t =1

n1
причем его мощность V1 = ? rt = m . В процессе замены доли V1 на долю V1 осуще-
t =1

ствляется преобразование множества ребер E данного гиперграфа G . Для каждой
вершины vt ? V1 из E выделяется множество Et , состоящее из ребер e ? E , инци-
дентных вершине vt . Далее множество E t порождает собой rt равномощных под-
множеств Etk , E tk = E t , k = 1,2,..., rt следующим образом. Для каждого фиксирован-
ного индекса k в множестве Et в каждом его ребре вершина vt заменяется на вер-
шину vtk . Полученное в результате таких замен множество обозначаем E tk ,
rt
k = 1, rt .Объединяя по индексу k , получаем множества Et = U Etk , t = 1, n1 ; обозна-
k =1

n1
чим E = U Et . Полученное множество E по своему определению образует n -
t =1
16
вершинный l -дольный l -однородный гиперграф G = (V1 ,V2 ,...,Vl , E ) с равномощ-
n1
ными долями, где n = n + ? (rt ? 1) = n + (m ? n1 ) = ml . Результатом применения ал-
t =1


горитмов ? 1 и ? 2 к гиперграфу G является множество всех его совершенных соче-
таний X (G ) = {x} .
Лемма 2.10. Всякое совершенное сочетание x в гиперграфе G однозначно оп-
ределяет собой допустимое покрытие x гиперграфа G звездами, причем, это покры-
тие получается в результате применения операции совмещения одноцветных вершин
первой доли в ребрах из x .
В главе 3 дано содержательное описание предложенного двухуровневого под-
хода в математическом моделировании дискретных задач в условиях многокритери-
альности и неопределенности данных. Двухуровневое моделирование заключается в
следующем:
1) разработка общей схемы двухуровневого моделирования и выбор численных ме-
тодов ее реализации;
2) разработка модели нижнего уровня, т.е. моделирование исходных данных и пара-
метров задачи для модели верхнего уровня;
3) разработка модели верхнего уровня, т.е. формулировка и исследование экстре-
мальной (векторной) задачи с нечеткими или интервально заданными параметрами,
которые были получены на нижнем уровне моделирования. Математическая модель
верхнего уровня – это модель теории оптимизации, на базе которой строится и обос-
новывается наиболее целесообразное решение поставленной задачи.
В качестве конкретной реализации двухуровневого моделирования в главе 3
приведен пример моделирования процесса выбора и принятия стратегии ведения
строительства некоторой строительной компании. На нижнем уровне моделирования
осуществляется структурирование экспертной информации об имеющихся в распо-
ряжении строительной компании трудовых, временных и технических ресурсах, о
предпочтениях клиентов. На верхнем уровне моделирования формулируется и ис-
следуется задача нахождения альтернативных проектов стратегии ведения строи-
тельства и выбор лучшей из них. Математическая постановка этой задачи представ-
ляет собой векторную задачу о совершенных сочетаниях в 3-дольном 3-однородном
гиперграфе.
Далее в главе 3 исследуется разрешимость интервальной задачи о совершен-
ных сочетаниях на 3-дольном гиперграфе с помощью алгоритмов линейной свертки
критериев (АЛСК). Интервальная задача заключается в том, что в гиперграфе
17
G = (V , E ) вес всякого ребра e ? E представляется интервалом, т.е. отрезком число-
вой прямой w(e) = [ w1 (e), w2 (e)] . Следует отметить, что интервальные задачи явля-
ются крайним случаем неопределенности и возникают в условиях неточных задан-
ных параметров задачи. В этом случае на МДР X = {x} задается интервальная целе-
? w(e) > max . Согласно определению
вая функция (ИЦФ) вида MAXSUM w( x) =
e?E x


операции сложения интервалов получим значение ИЦФ w( x) = [ w1 ( x), w2 ( x)] , где
? w ( e) ,
wi ( x) = i = 1,2 . Под решением интервальной задачи понимается такой эле-
i
e?E x


мент x 0 ? X , на котором значение ИЦФ достигает максимума. В этом случае рас-
сматриваемая задача сводится к 2-критериальной задаче с тем же множеством допус-
тимых решений X и векторной целевой функцией ВЦФ F ( x) = ( F1 ( x), F2 ( x)) , где
? w ( x) > max , ? d (e) > max , d (e) = w
F1 ( x) = F2 ( x) = (e) ? w1 (e) .
1 2
e?E x e?E x


Теорема 3.1. Паретовское множество задач с ИЦФ w(x) и ВЦФ F (x) совпа-
дают.
Алгоритмы линейной свертки критериев являются традиционными методами
нахождения парето-оптимальных решений многокритериальных задач.
Утверждение 3.1. Для любого вектора
? ? ? N = {? = (?1 , ?2 ,..., ? N ) : ? ?? = 1, ?? > 0,? = 1,2,..., N } элемент x * , мак-
N
симизирующий на МДР X линейную свертку критериев F ( x) = ? ?? F? ( x) целевых
?

? =1

функций F? ( x),? = 1,2,..., N , является ПО.
˜
Заметим, что АЛСК не всегда гарантируют нахождение всех ПО ˜ ? X . Если
x
˜
ПМ X индивидуальной интервальной задачи и 2-критериальной задачи содержит
такой элемент x * , на котором не достигает максимума значение свертки F ? (x) ни
при каком ? ? ? 2 , то эти задачи неразрешимы с помощью АЛСК.
Теорема 3.2. Для всякого 3-дольного гиперграфа G интервальная задача о
совершенных сочетаниях с критериями вида MAXSUM неразрешима с помощью
АЛСК.
ЗАКЛЮЧЕНИЕ
Основные результаты, полученные в ходе исследований можно предста-
вить в виде следующего перечня:
1. Обосновано свойство полноты задачи о совершенных сочетаниях и о покрытии
многодольного гиперграфа звездами.
18
2. Дан вывод достижимых верхних оценок структурной сложности многодольных
однородных гиперграфов: верхняя оценка количества ребер в полном многодольном
однородном гиперграфе, оценка максимальной мощности множества совершенных
сочетаний и максимальной мощности множества покрытий многодольного гипер-
графа звездами.
3. Обоснована труднорешаемость задач о совершенных сочетаниях и о покрытии
многодольного гиперграфа звездами в многокритериальной постановке.
4. Построен полиномиальный алгоритм проверки выполнения необходимых усло-
вий существования совершенного сочетания в многодольном гиперграфе.
5. Построен алгоритм бесповторного перебора всех совершенных сочетаний в мно-
годольном гиперграфе.
6. Построен полиномиальный алгоритм сведения задачи покрытия многодольного
однородного гиперграфа звездами к задаче о совершенных сочетаниях на гипергра-
фе.
7. Сформулирована концепция двухуровневого моделирования дискретных задач в
условиях неопределенности: на нижнем уровне осуществляется моделирование ис-
ходных данных для модели верхнего уровня, математическая модель верхнего уров-
ня – это модель теории оптимизации, на базе которой строится и обосновывается
наиболее целесообразное управление рассматриваемым процессом. В качестве кон-
кретной реализации двухуровневого моделирования представлена модель задачи вы-
бора стратегии ведения строительства некоторой строительной компанией. Построен
алгоритм реализации метода аналитической иерархии для слабоструктурированной
задачи, исходные данные которой на нижнем уровне моделирования заданы эксперт-
ными оценками.
8. Доказана неразрешимость с помощью алгоритмов линейной свертки критериев
интервальной задачи о совершенных сочетаниях с критериями вида MAXSUM на 3-
дольных гиперграфах.
Список основных трудов по теме диссертации
1. Омельченко Г.Г., Салпагаров С.И. Двукритериальная задача о назначениях инду-
стриально-организационной психологии //Современные аспекты экономики. –
Санкт-Петербург. – 2002 г. – №1(14). – С.139 – 144.
2. Омельченко Г.Г., Салпагаров С.И. Об одной вектороной задаче индустриально-
организационной психологии на гиперграфе //Успехи современного естествознания.
– 2002. – № 1. – С. 65 – 71.
3. Омельченко Г.Г., Салпагаров С.И. Об одной многокритериальной модели на ги-
перграфах //Современные аспекты экономики. – Санкт-Петербург. – 2002 г. –
№6(19). – С. 308 – 313.
19
4. Омельченко Г.Г., Салпагаров С.И. Многокритериальная модель организации
школьного образования//Успехи современного естествознания. – 2003. – № 3. – С.
101.
5. Омельченко Г.Г., Перепелица В.А. Исследование вычислительной сложности век-
торной задачи покрытия гиперграфа звездами. Сб.: Актуальные проблемы современ-
ной науки. Естественные науки. Ч.1-3. Математика. Механика. Машиностроение:
Тр.4-й Международной конференции молодых ученых, г. Самара, 10-12 сентября
2003г. – Самара: Электронное издание, 2003. – http://poman.sstu.edu.ru – C.63 – 67.
6. Omelchenko G.G., Salpagarov S.I. About one problem of hypergraph covering with
stars /VIII International Conference Nonlinear World Series. Education. Ecology. Econom-
ics. Computer Science. Astrakhan. September 15 – 20, 2003. – Astrakhan, 2003. – p. 360.
7. Омельченко Г.Г., Перепелица В.А. Оценки сложности векторной задачи покрытия
многодольного гиперграфа звездами. Материалы Всероссийской конференции «Про-
блемы оптимизации и экономические приложения», Омск, 1 – 5 июля 2003 г./Омский
филиал Института математики СО РАН. – Омск: Изд-во Наследие. Диалог Сибирь,
2003. – С. 105.
8. Омельченко Г.Г., Салпагаров С.И. Математическая модель организации личност-
но-ориентированного обучения учащихся на гиперграфе//Успехи современного есте-
ствознания. – 2004. – № 1. – С. 9 – 12.
9. Омельченко Г.Г., Перепелица В.А. Полиномиальный алгоритм распознавания со-
вершенного сочетания в многодольном однородном гиперграфе. Материалы VIII
Международного семинара «Дискретная математика и ее приложения», МГУ, 2 – 6
февраля 2004 г./ Под ред.О.Б.Лупанова. – М.: Изд-во мех.-мат. ф-та МГУ, 2004. –
С.344 – 348.
10. Омельченко Г.Г., Перепелица В.А. Необходимые условия распознавания с поли-
номиальной сложностью совершенного сочетания в многодольном однородном ги-
перграфе// Электронный журнал «Исследовано в России». – 2004. – С. 1276 – 1281,
http://zhurnal.ape.relarn.ru/articles/2004/120.pdf
11. Омельченко Г.Г., Перепелица В.А. «Алгоритм оптимизации управления космиче-
скими средствами на основе нахождения совершенных сочетаний многодольного ги-
перграфа»// Материалы научно-практической конференции: «Научно-практические
аспекты совершенствования управления КА и информационного обеспечения запус-
ков КА». Научно-информационный сборник (труды). Выпуск 11. – М.: в/ч 32103,
2004. – С. 234 – 246.
12. Омельченко Г.Г., Перепелица В.А. Алгоритм выделения совершенных сочетаний
на многодольном гиперграфе/ Доклады Одесского семинара по дискретной матема-
тике. Южный научный центр НАН и МОН Украины. №1. – Одесса: «Астропринт».
2004. – С. 26 – 44.
Отпечатано в ОАО «Полиграфист». Формат 60 ? 84 1. Печать офсетная.
16
Подписано в печать 01.11.04. Заказ № 2199. Тираж 100. Лицензия 040035 от 14.06.99 г.



СОДЕРЖАНИЕ