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

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

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

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

Специальность 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 = m. l На рис.1 представлен 9-вершинный 3-дольный 3-однородный гиперграф G = (V1 ,V2 ,V3 , E ) с множеством ребер E = {e} , где e1 = (1,4,7) , e2 = (2,5,8) ,

ставляет некоторое ребро e ∈ E . Из этого следует, что мощность E x =

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 )

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

6

9

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

4

7

2

5

8

3

6

9

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

1

4

7

2

5

8

3

6

9

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

1

и

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

2

11

6

12

7

13

8

14

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

1

3

9

4

10

5

2

11

6

12

7

13

8

14

Рис.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 критериев которой имеют вид MAXSUM Fν ( x) =

∑ wν (e) → max ,ν = 1, N

e∈E x

1

, N1 ≤ N , а

остальные ( 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 . l Следствие 2.1. Максимальная мощность µ1 (n, l) МДР задачи о совершенных

µ1 (n, l) = (m !) l −1 , где m =

сочетаниях на гиперграфе растет экспоненциально от размерности 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 = m , максимальная мощность МДР задачи о покрытии l −1 t =1 n -вершинного l -дольного l -однородного гиперграфа звездами на гиперграфе

щего условию

n1

∑r

t

=

(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 , который распознаl ет и отсеивает ребра e ∈ E , не принадлежащие никакому совершенному сочетанию в G . Алгоритм α 1 базируется на идее реализации гиперграфа G = (V1 ,...,Vl , E ) m Vk = 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 = Ø, то G не содержит совершенного сочетания.

14

( ).

Верхняя оценка трудоемкости алгоритма α 1 составляет τ (α 1 ) ≤ O E

e1 e4

e2

3

e3 e6

e5

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

e2 e1

e4

e3 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 l -однородном

l -дольном n -вершинном гиперграфе n τ (α 2 ) ≤ O( R )(m !) l −1 , m = . l Далее в главе 2 описывается процесс нахождения множества допустимых решений задачи покрытия l -дольного l -однородного гиперграфа звездами, который состоит из трех этапов. Суть первого этапа заключается в полиномиальном сведении задачи покрытия звездами к задаче о совершенных сочетаниях на гиперграфе. Второй этап представляет собой последовательное выполнение алгоритмов α 1 и α 2 , т.е. ных

сочетаний

в

результатом второго этапа является МДР задачи о совершенных сочетаниях. Третий этап на базе МДР задачи о совершенных сочетаниях находит МДР задачи покрытия звездами данного l -дольного гиперграфа. Если в исходном гиперграфе

Vs = m =

G = (V1 ,...,Vl , E ) , в котором

V1 = n1 ,

n − n1 , s = 2, l , для заданного вектора степеней r = (r1 , r2 ,..., rn ) выполняl −1 1

ется необходимое условие

n1

∑r t =1

t

= m , то полиномиальное сведение задачи о покрытии

такого гиперграфа звездами к задаче о совершенных сочетаниях осуществляется с помощью алгоритма α 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} задается интервальная целевая функция (ИЦФ) вида MAXSUM w( x) =

∑ w(e) → max . Согласно определению

e∈E x

операции сложения интервалов получим значение ИЦФ w( x) = [ w1 ( x), w2 ( x)] , где

wi ( x) =

∑ w ( e) ,

e∈E x

i

i = 1,2 . Под решением интервальной задачи понимается такой эле-

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

F1 ( x) =

∑ w ( x) → max ,

e∈E x

1

F2 ( x) =

∑ d (e) → max , d (e) = w

e∈E x

2

(e) − w1 (e) .

Теорема 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. Economics. 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 г.