автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Гиперграфовые модели и методы решения дискретных задач управления в условиях неопределенности

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

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

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

Специальность 05.13.18- шгешпмажое моделирование чисжнньв мяоды и комплексы программ

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

Ставрополь - 2004

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

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

Перепелица Виталий Афанасьевич

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

Наац Игорь Эдуардович

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

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

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

Ведущая организация: Кабардино-Балкарский государственный

университет им. Бербекова Х.М., г. Нальчик

Ученый секретарь диссертационного совета канд.физ.-мат. наук, доцент

Л.Б Копыткова

у

2 ¡О

3

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

- исследование структурной сложности гипер

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

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

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

Достоверность и обоснованность полученных в диссертационной работе теоретических результатов и формулировок обеспечивается корректным применением аппарата теории графов и гиперграфов, математического программирования и теории вычислительной сложности алгоритмов, математического аппарата интервального исчисления и нечетких множеств Информационную базу исследования составили аналитические и статистические материалы Карачаево-Черкесского проектного института, учебно-методического кабинета средней школы №4 г. Черкесска. Эффективность и адекватность предложенных методов подтверждается валидацией результатов, полученных в результате проведения численных расчетов. На защиту выносятся следующие основные положения:

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

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

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

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

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

, , ,.. ы* |

-ч.-й'Л'»»1 > \

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- на научно-практической конференции «Научно-практические аспекты совершенствования управления КА и информационного обеспечения запусков КА» (Москва, МО РФ, в/ч 32103, 2004);

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

- на УШ Международной конференции «Образование Экология Экономика Информатика» (Астрахань, 2003);

- на Ш, IV и V Международных конференциях молодых ученых и студентов (Самара, 2002,2003 и 2004);

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

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

Публикации. Материалы диссертации опубликованы в 9 научных статьях (из них 3 - в рецензируемых журналах) и в 3 тезисах докладов.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы диссертационного исследования, сформулирована его цель, описана структура и дан краткий обзор работы, изложены основные научные результаты, выносимые на защиту, раскрыта научная новизна и практическая значимость полученных результатов.

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

В главе 1 приведены основные понятия теории гиперграфов, которые используются в работе, поскольку, в отличие от графов, в научной и учебной литературе на русском языке практически отсутствуют доступные публикации Пусть V - конечное непустое множество, а Е = {е} - некоторое семейство непустых подмножеств е а V, тогда пара (У,Е) называется гиперграфом й = (У,Е) с множеством вершин V = {у} и множеством ребер Е = {е}. Гиперграф О = (У,Е) называется (.-дольным, если его множество вершин разбито на доли (подмножества) И, .$ = 1,2,. .1, так, что: 1) всякая пара вершин из одной доли является не смежной; 2) у всякого ребра е е Е каждая пара вершин е е принадлежит различным долям. Если в гиперграфе в нет кратных ребер и степень всякого ребра е е Е равна I (\е\ = I), то такой гиперграф называют ¿-однородным. Гиперграф С ~ (У',Е') называется частью гиперграфа в = (У,Е), если V с V и Е' с Е. Часть С = (У\Е") гиперграфа в = <У,Е) называется его подгиперграфом, если он образуется из исходного гиперграфа О путем удаления некоторых его вершин вместе с инцидентными им ребрами. Часть

С = (У ,Е') гиперграфа О = (У,Е) назовем реберным подгиперграфом, если из б удаляются только ребра. Если в ¿-однородном гиперграфе О = (У, Е) число вершин п = \У\ кратно £, то совершенным сочетанием (I -сочетанием) называется такой его реберный подгиперграф х = (У,ЕХ), в котором каждая компонента связности представляет некоторое ребро е е Е. Из этого следует, что мощность \Ех\ = П- = т.

На рис.1 представлен 9-вершинный 3-дольный 3-однородный гиперграф О = (У1,УгУъ,Е) с множеством ребер Е = {е}, где е, = (1,4,7), е2= (2,5,8), е, =(3,6,9), е, =(1,5,8), е, =(2,4,7), е6 =(3,5,8). На рис.2 и рис.3 для гиперграфа й = (У1,У1,У3,Е) представлены его совершенные сочетания х1=(У,Ех) и х2 = (У, Ех>), в которых ЕХ[ ={е,,е2,е3) и ={е3,е,,е,}.

•' /1 Г^ О

С'' 'О

Рис.2. Совершенное сочетание х1 = (У,Е^) гиперграфа О = (У1,Уг,У],Е)

Рис.3. Совершенное сочетание х2 = (У,Е^) гиперграфа в = (У1,У2,У,,Е)

в гиперграфе О-^.Ю ДР— -ездой на— такая его час. П,. Vz V Е) V с V,, 5 = . в которой всякая пара ребер ^се-

Z = (Kl ' ттной вершине v е ^. Степенью звезды r(v) называют чисяо ребер

кается только в одной вершине v е г t , у у Е qE

„ Wro — — —^I™ ребрУ —

„ерши™ ..V,,.»-«!-

рой звезды с центром v е Vl.

Рис.4.14-вершинный 3-дольный 3-одноро,

|дный гиперграф G = (У^-У^Е)

/ «3 »0

jlbs^ •7 13«)

lT*)

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

1Л «хитинный 3-дольный 3-однородный гиперграф На рис.4 представлен * где ei=(U9), ег=(1ДЮ),

= (у^г,Уг,Е) с множеством ребер Е-{е}, где 1

е, =(1,6,11), е4 =(2,4,12), е, =(2,7,13), е6 = (2,8,14), е7 =(1,4,9), е8 =(2,6,13) На рис 5 показано допустимое покрытие гиперграфа G = (Vt ,V2 ,V}, Е) звездами с вектором степеней г = (г1гг2) = (3,3).

Ребро е е Е гиперграфа G называется N -взвешенным, если ему поставлена в соответствие последовательность неотрицательных чисел wv(e)>0,^ = 1,2,. ,N Гиперграф называется N -взвешенным, если каждое его ребро является N-взвешенным. Если задача формулируется на гиперграфе G = (V,E), то ее допустимое решение определяется в виде реберного подгиперграфа x = (Vx,Ex), Г сГ, Ех ciE, который может представлять собой совершенное сочетание (покрытие гиперграфа звездами); X = X(G) - {х} - множество всех допустимых решений (МДР) задачи на G. Математическое моделирование реальных задач приводит зачастую к многокритериальным постановкам, для которых «оптимальное решение» отсутствует В условиях многокритериальное™ возникает необходимость вместо оптимума искать множество альтернатив. Качество допустимых решений хеХ оценивается векторной целевой функцией (ВЦФ) F(x) = (F1(x),F2(x),...,FK(xy), первые Nt критериев которой имеют вид MAXSUM Fv(х) = (е) —»max,v = 1,Nl, Nl <N, a

«г,

остальные (N - Л7,) критериев имеют вид MAXMIN (оценка по наихудшему) F„(х) = шшw¥(е) —> max,v = NltN. В определении этих критериев используются веса wv(e),v = \,2,...,N, приписанные ребрам ее Е ВЦФ F(x) определяет собой в МДР X паретовское множество X с: X В качестве искомого решения принимается полное множество альтернатив (ПМА), обозначаемое через Х° Подмножество X" с X называется ПМА, если оно имеет минимальную мощность jX"!, и при этом

выполняется равенство F(X°) = F(X), где F(X') = {F(x) ■ х е X'} VT' с X. Принято говорить, что задача с ВЦФ F(x) обладает свойством полноты, если для всякого ее МДР найдутся такие параметры ВЦФ, при которых выполняются равенства Х'=Х=Х.

Теорема 1.1. Всякая векторная задача о совершенных сочетаниях на £ -дольных гиперграфах является полной, если ее ВЦФ содержит не менее двух весовых критериев вида MAXSUM и MAXMIN, и все ее допустимые решения x = (V,Ex) состоят из одного и того же количества ребер \ЕХ\, х е X.

Теорема 1 2 Всякая векторная задача о покрытии I -дольного I -однородного гиперграфа звездами является полной, если ее ВЦФ содержит не менее двух весовых критериев вида МАХБЦМ и МАХМШ, и все ее допустимые решения х = (У,Ех) состоят из одного и того же количества ребер \Ех\. хеХ

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

Глава 2 посвящена оценке структурной сложности многодольных однородных гиперграфов, обоснованию труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе, оценкам максимальной мощности МДР задачи о совершенных сочетаниях на гиперграфе и задачи покрытия гиперграфа звездами В главе 2 также представлены полиномиальный алгоритм ал проверки необходимых условий существования совершенного сочетания в многодольном гиперграфе, алгоритм аг бесповторного перебора всех совершенных сочетаний в многодольном гиперграфе, полиномиальный алгоритм а3 сведения задачи покрытия многодольного однородного гиперграфа звездами к задаче о совершенных сочетаниях, включая вывод оценок вычислительной сложности этих алгоритмов.

Одним из важнейших структурных свойств «-вершинного гиперграфа С = (V, Е) является количество ребер Щ в нем В общем случае, когда речь идет о £ -дольном I -однородном гиперграфе О = (У1,У1, ., Ус, Е), справедлива следующая Теорема 2.1 В любом п -вершинном I -дольном I -однородном гиперграфе

число ребер ограничено сверху полиномом ^ ^ , причем, эта верхняя оценка является достижимой, если п кратно I, т.е. в случае, когда доли гиперграфа О равномощ-ны.

Из теоремы 2.1 следует, что для задач, формулируемых на ¿-дольных I-однородных гиперграфах, объем исходных данных является полиномиально ограниченным в случае, когда I представляет собой независящую от п константу.

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

мощность МДР, очевидно, является нижней оценкой вычислительной сложности нахождения ПМА, и, следовательно, рассматриваемая задача труднорешаема, если эта максимальная мощность растет экпоненциально от числа ребер в полном гиперграфе. Через обозначим максимальную мощность МДР задачи о совершенных сочетаниях на и-вершинном ¿-дольном I -однородном гиперграфе. Справедлива

Теорема 2.2. При п, кратном I, максимальная мощность МДР задачи о совершенных сочетаниях на п -вершинном гиперграфе определяется равенством

Следствие 2.1. Максимальная мощность /V, (и, I) МДР задачи о совершенных сочетаниях на гиперграфе растет экспоненциально от размерности и.

С учетом представленного в теореме 1.1 свойства полноты и следствия 2.1 является справедливой следующая теорема.

Теорема 2.3. Задача о совершенных сочетаниях на и -вершинном ¿ -дольном гиперграфе является труднорешаемой, если ее ВЦФ содержит не менее двух критериев вида МАХБЦМ.

В задаче о покрытии п -вершинного ¿ -дольного £ -однородного гиперграфа звездами обозначим через г = (г1,г2,...,г ) вектор степеней звезд в допустимом покрытии х € X; сумму этих степеней обозначим т = . Через J(n,£,ní) = {О} обо-

1=1

значим множество всех «-вершинных ¿-дольных ¿-однородных гиперграфов О = (У[,...,У/,Е), п = п1 + т (¿-1), в которых мощности долей ¿ = \,е удов-

летворяют следующим условиям: = я15 п 1<т и оставшиеся доли являются рав-

номощными п1 = т, $ = 2, ¿ При выполнении этих условий допустимым решением задачи о покрытии гиперграфа звездами является такой реберный подгиперграф х = (У1,...,У/,Ех) гиперграфа б е J(n,¿,n1), в котором каждая компонента связности представляет простую звезду степени е г с центром в соответствующей вершине у, еУп / = 1,2,...,и,. Количество таких звезд в покрытии х равно числу и1 вершин в первой доле. Через цг(п,1,г) обозначим максимальную по всем векторам степеней '

г мощность МДР задачи о покрытии и-вершинного ¿-дольного ¿-однородного гиперграфа звездами. Оказывается, что эта максимальная мощность не зависит от варьирования компонент данного вектора степеней г - , гг,..., гн ), и является справедливой

Теорема 2 4 Для всякого вектора степеней г = (ri,r1, ,г ), удовлетворяющего условию = -—— = т, максимальная мощность МДР задачи о покрытии t=i i — \

п -вершинного i -дольного I -однородного гиперграфа звездами на гиперграфе

(т IV"1

G е J(n,£,n.) определяется равенством ц, (и, I, г) = ц, (и, €) =---.

W Гц'

Следствие 2.2. Максимальная мощность /лг (п, I) МДР задачи покрытия гиперграфа звездами растет экспоненциально от размерности п

С учетом представленного в теореме 1.2 свойства полноты и следствия 2 2 является справедливой следующая теорема.

Теорема 2.5. Задача о покрытии п-вершинного ¿-дольного ¿-однородного гиперграфа звездами является труднорешаемой, если ее ВЦФ содержит не менее двух критериев вида MAXSUM.

Для проверки выполнения необходимых условий существования совершенного сочетания в многодольном однородном гиперграфе G = (Vt, ,Vt,E),

\Vt\ = m = ^, к = \,£ предлагается полиномиальный алгоритм а1, который распознает и отсеивает ребра е е Е, не принадлежащие никакому совершенному сочетанию в G Алгоритм а, базируется на идее реализации гиперграфа G = (Vl,...,Vl,E) отдельным специальным графом S = S(G) = (U^. ,,Ut,...,Um,R). Между ребрами

т

е е Е и гипервершинами е е U, U = t существует взаимно однозначное соответствие, причем ребро р - (е',е") принадлежит R тогда и только тогда, когда ребра е', е" е Е не пересекаются в G. Идея алгоритма а1 заключается в том, что всякому совершенному сочетанию в гиперграфе G взаимно однозначно соответствует т-гипервершинная клика в специальном графе S. Сформулированы и доказаны необходимые условия принадлежности е eU т -гипервершинной клике. Неудовлетворяющие этим условиям гипервершины удаляются из S На выходе алгоритма а1 получается тупиковый подграф S = S(G). Доказаны следующие достаточные условия

Лемма 2.8. Если гиперграф G содержит совершенное сочетание, то на выходе алгоритма а1 получаем непустой тупиковый подграф S.

Лемма 2.9. Если для гиперграфа G на выходе алгоритма яг, получаем тупиковый подграф S = 0, то G не содержит совершенного сочетания.

Верхняя оценка трудоемкости алгоритма а, составляет т(а1) < О^Е^

ег

Рис.7 Тупиковый подграф ¡5(0) На рис.6 представлен 6-вершинный 3-дольный специальный граф Я (О) для гиперграфа, изображенного на рис. 1.

На рис.7 изображен полученный в результате работы алгоритма а, тупиковый подграф 5 (О), содержащий две клики.

Если в результате работы алгоритма а1 получен непустой тупиковый подграф 5(С}), то для выделения совершенных сочетаний в гиперграфе используется представленный далее алгоритм аг. На вход алгоритма аг подается т -дольный тупиковый подграф Б (О), из которого в ходе работы алгоритма выделяются т -вершинные клики, каждая из которых однозначно определяет собой некоторое допустимое решение исходной задачи о нахождении множества X = Х(0) всех совершенных сочетаний на £ -дольном £ -однородном гиперграфе. На выходе алгоритма аг формируется множество клик размерности т, которое определяет собой МДР X = Х(Сг) задачи о совершенных сочетаниях на гиперграфе. Оценивая вычислительную сложность т(аг), отметим, что все клики формируются последовательно и бесповторно, при этом каждое ребро р е Я просматривается не более, чем количество этих клик. Отсюда получаем оценку сложности перечисления алгоритмом а1 всех совершен-

I I

ных сочетаний в (. -дольном i -однородном п -вершинном гиперграфе

т(а.)50(|й|Х»!)м, и = j.

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

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

Если в исходном гиперграфе G = (Ví,...,Vl,E), в котором = и,,

|F | = т = " , s = 2,1, для заданного вектора степеней г = (г\,гг, ,г^) выполняется необходимое условие ¿r, = т, то полиномиальное сведение задачи о покрытии

t=1

такого гиперграфа звездами к задаче о совершенных сочетаниях осуществляется с помощью алгоритма аг следующим образом. Каждая вершина первой доли v, е Vl окрашивается в свой цвет t, t = 1,2,...,и1 и заменяется множеством вершин V' = {v*}, к = 1, r¡, окрашенных в один и тот же цвет í В результате в данном гиперграфе G

его первая доля V¡ преобразуется в множество К, =(J V{ ={v"t}, k = l,rt, t = \ ,и,,

i-i

_ «i __

причем его мощность = JV, = m. В процессе замены доли Vl на долю V¡ осуще-

/=i

ствляется преобразование множества ребер Е данного гиперграфа G Для каждой вершины v, е Vt из Е выделяется множество Et, состоящее из ребер е е Е, инцидентных вершине v,. Далее множество Е, порождает собой rt равномощных подмножеств Е], [jE*^| = |, к = 1,2,...,г, следующим образом. Для каждого фиксированного индекса к в множестве Et в каждом его ребре вершина v, заменяется на вершину v,*. Полученное в результате таких замен множество обозначаем Е\,

k=\,rt .Объединяя по индексу к, получаем множества Е, = \}Е*, t = 1,м1; обозна-— _ —

чим Е = [JEt Полученное множество Е по своему определению образует «-(=i

вершинный ¿-дольный I-однородный гиперграф О =(У1У2, У,,Е) с равномощ-

ными долями, где л = и + ¿(г, - V) = п + (т -пу) = т(.. Результатом применения ал-(=1

горитмов а1 и аг к гиперграфу С является множество всех его совершенных сочетаний Х((Э)={х}.

Лемма 2.10. Всякое совершенное сочетание х в гиперграфе О однозначно оп- •■

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

В главе 3 дано содержательное описание предложенного двухуровневого подхода в математическом моделировании дискретных задач в условиях многокритери-альности и неопределенности данных. Двухуровневое моделирование заключается в следующем:

1) разработка общей схемы двухуровневого моделирования и выбор численных методов ее реализации;

2) разработка модели нижнего уровня, т.е. моделирование исходных данных и параметров задачи для модели верхнего уровня;

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

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

Далее в главе 3 исследуется разрешимость интервальной задачи о совершенных сочетаниях на 3-дольном гиперграфе с помощью алгоритмов линейной свергай критериев (АЛСК) Интервальная задача заключается в том, что в гиперграфе

I !

G = (V,E) вес всякого ребра e e E представляется интервалом, т e отрезком числовой прямой w(e) = [w,(e), w2(e)] Следует отметить, что интервальные задачи являются крайним случаем неопределенности и возникают в условиях неточных заданных параметров задачи. В этом случае на МДР X = {х} задается интервальная целевая функция (ИЦФ) вида MAXSUM w(x) = ^ w(e) -> max Согласно определению

в€2,

операции сложения интервалов получим значение ИЦФ w(x) = [wt(x), и>2 (х)], где (х) = X w, (е) > ' = 1>2 • Под решением интервальной задачи понимается такой элемент б X, на котором значение ИЦФ достигает максимума В этом случае рассматриваемая задача сводится к 2-критериальной задаче с тем же множеством допустимых решений X и векторной целевой функцией ВЦФ F(x) = (Fi (х), F2 (х)), где ад = wi(х) ~~> max, F2(x) = -»max, J(e) = w2(e) -м'Де).

««я, вея.

Теорема 3.1. Паретовское множество задач с ИЦФ w(x) и ВЦФ F(x) совпадают.

Алгоритмы линейной свертки критериев являются традиционными методами нахождения парето-оптимальных решений многокритериальных задач Утверждение 3.1. Для любого вектора

Л е = {Л = (Л1,Л1, ,Л„)-£ЛУ = 1,ЛУ >0,v = l,2,...,A^} элемент х', мак-

N

симизирующий на МДР X линейную свертку критериев F* (х) = (х) целевых

функций Fv(x),v = 1,2,...,N, является ПО.

Заметим, что AJICK не всегда гарантируют нахождение всех ПО х е X. Если ПМ X индивидуальной интервальной задачи и 2-критериальной задачи содержит такой элемент х', на котором не достигает максимума значение свертки F*(x) ни при каком Л е Л г, то эти задачи неразрешимы с помощью AJICK

Теорема 3 2 Для всякого 3-дольного гиперграфа G интервальная задача о совершенных сочетаниях с критериями вида MAXSUM неразрешима с помощью АЛСК.

ЗАКЛЮЧЕНИЕ

Основные результаты, полученные в ходе исследований можно представить в виде следующего перечня-

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

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

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

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

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

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

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

8 Доказана неразрешимость с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенных сочетаниях с критериями вида МАХЗХШ на 3-дольных гиперграфах.

Список основных трудов по теме диссертации 1 Омельченко Г.Г., Салпагаров С.И. Двукритериальная задача о назначениях индустриально-организационной психологии //Современные аспекты экономики -Санкт-Петербург. - 2002 г. - №1(14). - С.139 - 144

2. Омельченко Г.Г., Салпагаров С.И Об одной вектороной задаче индустриально-организационной психологии на гиперграфе //Успехи современного естествознания. -2002. -№ 1. - С. 65-71.

3. Омельченко Г.Г., Салпагаров С.И. Об одной многокритериальной модели на гиперграфах //Современные аспекты экономики. - Санкт-Петербург. - 2002 г. -№6(19).-С. 308-313.

4 Омельченко Г.Г, Салпагаров С.И Многокритериальная модель организации школьного образования//Успехи современного естествознания - 2003 - № 3. - С 101.

5 Омельченко Г Г, Перепелица В. А Исследование вычислительной сложности векторной задачи покрытия гиперграфа звездами Сб • Актуальные проблемы современной науки. Естественные науки Ч1-3 Математика. Механика Машиностроение' Тр.4-й Международной конференции молодых ученых, г Самара, 10-12 сентября 2003г. - Самара' Электронное издание, 2003 - httpV/poman sstu edu.ru - С 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.relam.ni/articles/2004/120.pdf

11. Омельченко Г.Г., Перепелица В.А. «Алгоритм оптимизации управления космическими средствами на основе нахождения совершенных сочетаний многодольного гиперграфа»// Материалы научно-практической конференции: «Научно-практические аспекты совершенствования управления КА и информационного обеспечения запусков КА». Научно-информационный сборник (труды). Выпуск 11. - М: в/ч 32103,

2004.-С. 234-246.

12.Омельченко Г.Г., Перепелица В.А Алгоритм выделения совершенных сочетаний на многодольном гиперграфе/ Доклады Одесского семинара по дискретной математике. Южный научный центр HAH и МОН Украины. №1. - Одесса: «Астропринт». 2004.-С. 26 - 44.

• 2 675 О

РНБ Русский фонд

2006-4 230

Подписано в печать 01.11.04. Заказ № 2199. Тираж 100. Лицегоия 040035 от 14.06.99 г.

ВВЕДЕНИЕ.

ГЛАВА 1. ОСНОВЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ

СЛОЖНЫХ СИСТЕМ НА БАЗЕ ТЕОРИИ ГИПЕРГРАФОВ.

1.1. Учет неопределенности параметров в математическом моделировании

1.2. Гиперграфы. Некоторые определения и свойства.

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

1.4. Постановка задач и построение математических моделей на гиперграфах.

1.4.1. Двукритериальная задача кадрового менеджмента.

1.4.2. Математическая модель задачи управления космическим командно-измерительным комплексом.

1.4.3. Математическая модель обучения сотрудников организации.

1.4.4. Математическая модель назначения учителей в классы с учетом технологий обучения.

1.5. Выводы по первой главе.

ГЛАВА 2. АЛГОРИТМЫ НАХОЖДЕНИЯ ВСЕХ СОВЕРШЕННЫХ

СОЧЕТАНИЙ И ПОКРЫТИЙ ЗВЕЗДАМИ МНОГО ДОЛЬНЫХ ОДНОРОДНЫХ ГИПЕРГРАФОВ.

2.1. Оценки числа ребер в I -дольных t -однородных гиперграфах.

2.2. Обоснование труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе.

2.3. Оценки вычислительной сложности векторной задачи покрытия гиперграфа звездами.

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

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

2.6. Алгоритм нахождения множества допустимых решений задачи покрытия I -дольного I -однородного гиперграфа звездами.

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

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

3.1. Проблема неопределенности в математическом моделировании.

3.2. Двухуровневый подход в математическом моделировании.Ю

3.2.1. Моделирование на нижнем уровне.

3.2.2. Моделирование на верхнем уровне.

3.3. Интервальные модели и многокритериальность.

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

3.3.2. Сведение интервальной задачи к 2-критериальной.

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

3.3.4. Исследование разрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о сочетаниях с критериями вида MAXSUM наЗ-дольном гиперграфе.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2003);

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

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

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

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

2002);

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

1. Абрамович Ф.П., Вагенкнехт М.А., Хургин ЯМ. Решение нечетких систем линейных алгебраических уравнений LR-типа. - В сб.: Методы и системы принятия решений. Рига: РПИ, 1987, с.35 -47.

2. Айзерман М.А., Алексеров Ф.Т. Выбор вариантов. Основы теории. -М.: Наука, ГРФМЛ, 1990.-236 с.

3. Алефельд Г., Хельцбергер Ю. Введение в интервальные вычисления. -М.: Мир, 1987. -542с.

4. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях: Монография. Тюмень: Издательство Тюменского государственного университета, 2000. 352с.

5. Алтунин А.Е., Чуклеев С.Н., Семухин М.В., Крел Л.Д. Методическое руководство по технологическим расчетам сложных систем газодобычи при неточных параметрах. Тюмень, 1984, 48 с.

6. Аоки М. Введение в методы оптимизации. М.: Наука, 1977, 344 с.

7. Безбородов В.Г., Жаков A.M. Суда космической службы. Л.: Судостроение, 1980, с.248

8. Берж К. Теория графов и ее применения. —М.: Изд. иностр. лит-ры, 1962.-320с.

9. Беспалько В. П. Педагогика и прогрессивные технологии обучения. —М.:Школа, 1995.-255с.

10. Бэстенс Д.-Э., Ван Ден Берг В.-М., Вуд Д. Нейронные сети и финансовые рынки. М.: ТВП Научное издательство, 1998.

11. Волконский В.А., Еганян Г.К., Поманский А.Б. О множестве эффективных точек в линейных многокритериальных задачах //Сиб. Матем. Журнал. 1983. 24-№2.-С.9-17

12. Вощинин А.П., Сотиров Г.Р. Оптимизация в условиях неопределенности. —М.: Наука, 1989.-420с.

13. Вязгин В.А.Б Федоров В.В. Математические методы автоматизированного проектирования. М.: Высшая школа, 1989. - 184 с.

14. Гермейер Ю.Б. Введение в теорию исследования операций. —М.: Наука, ГРФМЛ, 1971.-383 с.

15. Глушков В.М. О системной оптимизации//Кибернетика. 1980. -№5,-С.89-90.

16. Гудмен И. Нечеткие множества как классы эквивалентности случайных множеств. В сб.: Нечеткие множества и теория возможностей. -М: Радио и связь, 1986, с.241 264.

17. Гуткин Л. С. Оптимизация радиоэлектронных устройств по совокупности показателей качества. М.: Сов. радио. 1975. - 368 с.

18. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. —М.: Мир, 1982.-416 с.

19. Демченко А.И. Синтез транспортных сетей в условиях неопределенности исходной информации// Труды семинара по интервальной математике, Саратов, 29-31 мая, 1990: Саратов, 1990. С. 10 - 16.

20. Джуэлл Л. Индустриально-организационная психология. —СПб.: Питер,2001.-720с.

21. Дресслер Г. Управление персоналом. М.: Бином, 1997. 418 с.

22. Евдокимов М.В., Медницкий В.Г., Сигал И.Х. Бикритериальная задача переоборудования производства. //Известия РАН. Теория и системы управления. -№ 5. 2001. -С. 90-96.

23. Ежов А.А., Шумский С.А. Нейрокомпьютинг и его применение в экономике и бизнесе. М.: ЭАИ МИФИ, 1998.

24. Емеличев В.А., Кравцов М.К., Янушкевич О.Я. Разрешимость векторной траекторной задачи на «узкие места» с помощью алгоритма линейной свертки // Доклады Академии наук Белоруси. 1996. 40-№4. —С.29-33

25. Емеличев В.А., Перепелица В.А. К вычислительной сложности дискретных многокритериальных задач // Изв. АН СССР. Техн.кибернетика. 1988. №1.С.78-85

26. Емеличев В.А., Перепелица В.А. Полные задачи многокритериальной дискретной оптимизации//Сообщения АН ГССР. 1988. - Т. 131, №3. - С.501 -504.

27. Емеличев В. А., Перепелица В. А. Сложность дискретных многокритериальных задач // Дискретная математика. 1994. - Т.6, №1.-С.З-33

28. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. —М.: Наука, 1990. —384с.

29. Емеличев В.А., Перепелица В.А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах// Журн. вычис. математики и мат.физики. 1989. - Т.29., №2. - С. 171 - 183.

30. Жак СВ. Математические модели менеджмента и маркетинга. -Ростов-на-Дону: ЛаПО, 1997. 320 с.

31. Заде Л.А. Понятие, лингвистической переменной и его применение к принятию приближенных решений. —М.: Мир, 1976,165с.

32. Зыков А.А. Гиперграфы//Успехи Матем. наук. 1974. -Т. 29. вып.6.-С. 89-154.

33. Ивченко Б.П., Мартыщенко Л.А., Монастырский МЛ. Теоретические основы информационно-статистического анализа сложных систем. СПб.: Питер, 1997.

34. Ильин Н.И., Лукманова И.Г. и др. Управление проектами. СПб.: «Два - ТрИ», 1996. - 610 с.

35. Калмыков С.А., Шокин Ю.А., Юлдашев З.Х. Методы интервального анализа.-Новосибирск: Наука, Сибирское отделение, 1986. 590с.

36. Кандель А., Байатт У.Дж. Нечеткие множества, нечеткая алгебра, нечеткая статистика. Труды американского общества инженеров радиоэлекгронников, т.66, 1978, с.37-61

37. Карповский Е.Я., Чижов С. А. Оценка показателей качества программных средств с использованием лингвистических переменных. Управляющие системы и машины, №2, 1987, с. 17 -19

38. Кейн JI.A. Искусственный интеллект в обрабатывающих отраслях промышленности. Нефть, газ и нефтехимия за рубежом, №9, 1986,с. 117-122

39. Кейн В.М. Оптимизация систем управления по минимаксному критерию. М.: Наука, 1985, 248 с.

40. Ким-Гю-Пхир. Оптимальное распределение ресурса в условиях интервальной неопределенности// Международная конференция по интервальным и стохастическим методам в науке и технике (Интервал 92): Сборник трудов - Москва, 1992. - T.I. С.60 - 63.

41. Ковалев В.И., Бондарева М.К., Омельченко Г.Г. и др. «Исследование вопросов создания системы оценки космической обстановки для учета изменяющихся условий управления космическими аппаратами»// Отчет о НИР «Голкипер». М.: МО РФ, в/ч 32103, 2000 г. 112 с.

42. Коршунов А.Д. Основные свойства случайных графов с большим числом вершин и ребер//Успехи матем. наук. 1985. - Т.40, №1 (241).-С. 107173.

43. Кофман А. Введение в теорию нечетких множеств. М: Радио и связь, 1982,432 с.

44. Кравцов М.К. Неразрешимость задач векторной дискретной оптимизации в классе алгоритмов линейной свертки критериев //Дискретная математика. 1996.8 - №2. - С.89 - 96

45. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-432с.

46. Куржанский А.Б. Управление и наблюдение в условиях неопределенности. М.: Наука, 1977, 392 с.

47. Кучин Б.Л. Оперативная информация в АСУ магистральных газопроводов. М: Недра,1979.

48. Кучин Б.Л., Алтунин А.Е. Управление системой газоснабжения в осложненных условиях эксплуатации. М.: Недра, 1987, 209 с.

49. Ларичев О.И. Наука и искусство принятия решения. М.: Наука, 1979.-200с.

50. Лебедев В.В. Математическое моделирование социально-экономических процессов. -М.: Изограф, 1997.

51. Лизинский В.М. Диагностико-аналитические процедуры и активно-игровые формы в управлении. М.: Новая школа, 1996. - 300с.

52. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии М.: Мир, 1998. - 653 с.

53. Машарова Т.В. Педагогические теории, системы и технологии обучения. Киров: ВГПУ, 1997. - 370с.

54. Меламед И. И., Сигал И. X. Исследование линейной свертки критериев в многокритериальном дискретном программировании. //Журнал вычислительной математики и математической физики. 1995. Т.35. - №8. -С. 1260-1270.

55. Меламед И. И., Сигал И. X. Теория и алгоритмы решения многокритериальных задач комбинаторной оптимизации. М.:ВЦ РАН. 1996.-52 с.

56. Меламед И.И. Методы оптимизации в транспортном процессе. -И НТ. ВИНИТИ. Сер. Оптимизация управления транспортом. Т.10.-М.: ВИНИТИ. 1991.-162 с.

57. Меламед И.И., Сигал И.Х. Вычислительное исследование линейной свертки критериев в многокритериальном дискретном программировании // Докл. РАН. 1995. Т.345. №4. С.463 466

58. Меламед И.И., Сигал И.Х. Распределение эффективных решений в некоторых бикритериальных задачах дискретного программирования. М.: ВЦ РАН, 2001

59. Меламед И.И., Сигал И.Х. Теория и алгоритмы решения многокритериальных задач комбинаторной оптимизации. М.: ВЦ РАН, 1996

60. Меламед И.И., Сигал И.Х. Вычислительное исследование трикритериальных задач о деревьях и назначениях // Ж. вычисл.матем. и матем. физ. 1998. Т.38 №10. С.1780-1787

61. Михалевич B.C., Волкович B.JI. Вычислительные методы исследования и проектирования сложных систем. М.: Наука, 1982. 286 с.

62. Моисеев Н.Н. Математические задачи системного анализа. М.: Наука, 1981,488 с.

63. Моисеев Н.Н. Элементы теории оптимальных систем. М.: Наука, 1975,528с.

64. Негойце К. Применение теории систем к проблемам управления. М: Мир, 1981, 179 с.

65. Норри Д., Ж. де Фриз. Введение в метод конечных элементов. М: Мир, 1981,304с.

66. Омельченко Г.Г., Салпагаров С.И. Диагностика дефляции пахотных площадей// Успехи современного естествознания. 2003-№4. - С.99-100

67. Омельченко Г.Г., Салпагаров С.И. Двукритериальная задача оназначениях индустриально-организационной психологии// Современные аспекты экономики. 2002. - 1(14). - С. 139-144.

68. Омельченко Г.Г., Салпагаров С.И. Математическая модель организации личностно-ориентированного обучения учащихся на гиперграфе// Успехи современного естествознания. 2004. - №1. - С. 9 - 12.

69. Омельченко Г.Г., Перепелица В.А. Алгоритм выделения совершенных сочетаний на многодольном гиперграфе/ Доклады Одесского семинара по дискретной математике. Южный научный центр НАН и МОН Украины. -Одесса: «Астропринт». 2004. - №1. - С. 26 - 43.

70. Оре О. Теория графов. М.: Наука, 1980. - 336 с.

71. Перепелица В. А., Мамедов А. А. Исследование сложности и разрешимости векторных задач на графах: Уч.пособие. Черкесск, 1995. 68 с.

72. Перепелица В.А., Сергеева JI.H. Исследование неразрешимости с помощью алгоритма линейной свертки 3-невырожденных дискретных многокритериальных задач // Кибернетика и системный анализ. 1996. - №2. -С. 71-77

73. Перепелица В.А., Сергиенко И.В. Исследование одного класса целочисленных многокритериальных задач// Журн. вычислит, математики и мат. физики. 1988. - Т.28., №3. - С. 400 - 419

74. Петере Э. Хаос и порядок на рынках капитала. Новый аналитический взгляд на циклы, цены и изменчивость рынка: Пер. с англ. -М.: Мир. 2000. -333 с.

75. Пищулин Н.П., Ананишнев В.М. Образование и управление. М.: «Жизнь и мысль», 1999. - 296 с.

76. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. -М.: Сов. Радио, 1975.-192с.

77. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. -М.: Наука, 1982. 256 с.

78. Пратусевич Ю.М., Сербиненко М.В., Орбачевская Г.Н. Системный анализ процесса мышления. М.: Медицина, 1989.

79. Саати Т., Керне К. Аналитическое планирование. Организация систем. -М.: Радио и связь, 1991.

80. Сакович В.А. Исследование операций. -Минск.: Вышэйшая школа, 1984.-256 с.

81. Сергиенко И.В., Перепелица В.А. К проблеме нахождения множеств альтернатив в дискретных многокритериальных задачах //Кибернетика. -1987. №5. - С. 85 -93.

82. Сидоренко Е.В. Методы математической обработки в психологии. -СПб.: Социально-психологический центр, 1996.

83. Татт У. Теория графов. М.: Мир, 1988. - 320 с.

84. Третьяков П.И. Управление школой по результатам. М.: Новая школа, 1997.-288 с.

85. Третьяков П.И., Сенновский И.Б. Технология модульного обучения в школе. М.: Новая школа, 1997. - 160 с.

86. Трояновский В.М. Математическое моделирование в менеджменте. -М.: Русская Деловая Литература, 1999. 240 с.

87. Харари Ф. Теория графов. М.: Мир, 1973. - 300 с.

88. Хубаев Г.Н. Сложные системы: экспертные методы сравнения/ Приложение к журналу «Известия высших учебных заведений: СевероКавказский регион, общественные науки», 1999 г., №3. С. 7-24.

89. Atsushi Degawa. Улучшение методов обнаружения и подавления "плохой" информации при оценке состояния энергосистем. "Дэнки гаккай ромбуси, Trans. Inst. Elec. Eng. Jap.", 1984, №2, p.69 76 (яп.)

90. Brucker P. Discrete Parameter optimization problem and essential efficient points//Operat.Res. 1972/16 №5. pp.189 - 197

91. Charnes A., Cooper W.W. Management Models and Industrial Application of Linear Programming. N.Y.: Wiley, 1961.

92. Csendes T. An Interval Method for Bounding Level Sets of Parameter Estimation Problems/ Computing 41 (1989), pp.75 86.

93. Emelichev V.A. and Perepelitsa V.A. Multiobjective problems on the spanning trees of a graph. Soviet Math. Dokl. Vol. 37 (1988), 1, pp.114 117.

94. Gessing R. Two-level hierarchical control for stochastic optimal resource allocation. "Int. J. Contr.", 1985, №1, p.161 175.

95. Kitowski J. Zastosowanie relacyjnych rownan rozmytych."Zesz.nauk.AGH: Autom." 1984, №37, 107p.

96. Koopmans T.C. Analysis of production as an efficient combination ofactivities / Ed. T.C. Koopmans. Activity Analysis Production andAllocation. N.Y.: Wiley, 1951. P. 33-97

97. Moor R.E. A servey of interval methods for differential equations, "Proc. 23 rd IEEE Conf. Decis. And Contr., Las Vegas, Nev., 1984, v.3", New York, 1984, p.1529 1535.

98. Schwandt H. An interval arithmetic approach for the constraction of an almost globally convergent method for the solution of the nonlinear on the unit square. "SIAM J. Sci. A St. Comput.", 1984, v.5, №2, p.427 452.

99. Voloshin V.I. Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. Fields Institute for Research in Mathematical Sciences, 2002, 182 p.