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

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

Тебуева Фариза Биляловна

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

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

1 з фев т

005545191

Работа выполнена в Северо- Кавказском федеральном университете в г. Ставрополе.

Официальные оппоненты: Гликлих Юрий Евгеньевич

доктор физико-математических наук, профессор, ФГБОУ ВПО «Воронежский государственный университет», профессор кафедры алгебры и топологических методов анализа

Наталуха Игорь Анатольевич доктор физико-математических наук, профессор, НОУ ВПО «Кисловодский институт экономики и права», профессор кафедры математики и информационных технологий

Осипян Валерий Осипович доктор физико-математических наук, доцент, ФГБОУ ВПО «Кубанский государственный университет», профессор кафедры информационных технологий

Ведущая организация: ФГБОУ ВПО «Санкт-Петербургский государственный политехнический университет»

Защита состоится «20» марта 2014 г. в 14-20 часов на заседании диссертационного совета Д 212.208.22 при Южном федеральном университете по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, г. Ростов-на-Дону, ул. Пушкинская, д. 148.

Диссертация в электронном виде доступна по адресу:

sfedu.ru/novosti-kafedry-mos/516-dissertacya-tebueva

Автореферат разослан «Ц » ^^оЬсцплЯ- 2014 г.

Ученый секретарь

диссертационного совета Д 212.208.22, доктор технических наук, профессор

А.Н. Целых

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

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

Положения работы поддержаны грантами Российского фонда фундаментальных исследований: «Математическое моделирование структуры слабо формализованных систем в условиях неопределенности», «Структурирование, выявление несоответствий и прогнозирование эволюционных дискретных процессов и систем при наличии долговременных корреляций».

По теме диссертационной работы выполнены следующие проекты Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы»: «Разработка вычислительных методов структурирования, выявления несоответствий и прогнозирования эволюционных дискретных процессов с долговременными кор-

реляциями в системах обработки информации» (2010-2012), «Разработка технологий проектирования эволюционирующих информационных систем на основе моделирования регламентов в специальных средах» (2010-2012).

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

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

Степень разработанности темы исследования. Задачам математического моделирования систем в условиях детерминированности исходных данных посвящены публикации ученых: Самарский A.A., Партыка Т.Л., Попов Э.В., Мышкис А .Д., Плотинский Ю.М., Сергиенко И.В. и др.

Развитию методов многокритериальной оптимизации и принятия решений посвящены научные труды отечественных и зарубежных авторов: Саати Т., Прокушева А.П., Прокушев Я.Е., Подиновский В.В., Ногин В.Д., Пападимитриу X., Стайглиц К., Моисеев H.H., Михалевич B.C., Трубин В.А., Шор Н.З., Майника Э., Львович Я.Е., Чернышева Г.Д., Каширина И.Л., Лесин В.В., Лисовец Ю.П., Ларичев О.И., Иванов Б.Н., Дубов Ю.А., Травкин С.И., Якимец В.Н.

В развигие теории моделирования нечетких и интервальных данных внесли существенный вклад научные исследователи: Заде Л., Зайченко Ю.П., Нариньяни A.C., Орловский С.А., Мелькумова Е.М., Левин В.И., Куржанский А.Б., Курдюмов И.В., Мосолова М.В., Назайкинский В.Е., Кофман А., Корченко А.Г., Ким-Гю-Пхир, Калмыков С.А., Шокин Ю.И., Юлдашев З.Х., Дробязко О.Н., Нефедов С.Ф., Дилигенский Н.В., Дымова Л.Г., Севастьянов П.В., БерштеПн Л.С., Мелихов А.Н., Боженюк A.B. и др.

Анализу и прогнозированию временных рядов посвящено огромное количество публикаций, среди которых можно выделить публикации авторов: Мацдельброт Б.Б., Отнес Р., Петере Э., Осборн М„ Песаран М„ При-гожин А.И., Пуарье Д., Мартино Дж., Хакен Г., Сигел Э., Хейс Д., А. Хос-кинг, Базаров В.А., Громан В.Г., Канторович Л.В., Кондратьев Н.Д., Новожилов В.В., Перепелица В.А., Фельдман Г.А., Шаталин С.С. и др.

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

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

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

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

Поставленная цель требует решения следующих частных научных задач;

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

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

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

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

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

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

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

В области математического моделирования:

1) математическая модель сведения размерностей нечетких множеств к единой величине, позволяющая реализовываггь более экономные арифметические операции по принципу «векторное получение носителя и теоретико-множественные операции над степенью принадлежности» (с. 80-98);

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

3) математический метод сравнения вложенных интервалов, использующий взвешенную свертку границ интервала, и, являющийся развитием метода сравнения в центральном смысле (с. 102-107);

4) математический метод вычисления глубины долговременных корреляций в персистентных временных рядах, базирующийся на свойстве фраетапьности, для определения длины конфигурации с памятью и осуществления настройки клеточно-автоматной прогнозной модели (с. 110111);

5) методы преобразования числовых временных рядов в лингвистические временные ряды: огибающих ломаных, трендовых коридоров, локального размаха (с. 123-129);

6) математическая модель прогнозирования персистентных временных рядов на базе линейных клеточных автоматов для надежного прогно-

зирования временных рядов с признаками фрактальности: наличие долговременных зависимостей значений, неподчинение нормальному закону, частая смена тренда, нестационарность (с. 122-135);

7) математические методы получения оценок «суммарный эффект» и «оценка по наихудшему» для допустимых решений задачи многокритериального выбора на графах со структурированными исходными данными (с. 155-181);

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

9) асимптотически точный и статистически эффективный алгоритмы для подкласса задач покрытия граф звездами одного типа с весами ребер в виде интервалов равной ширины (с. 230-238).

В области численных методов:

1) численный метод сведения размерностей нечетких множеств к единой величине для реализации арифметических операций по принципу «векторное получение носителя и теоретико-множественные операции над степенью принадлежности» (с. 197-198);

2) численный метод реализации дефазификации по центрам тяжести носителя и функции принадлежности для сравнения нечетких множеств с пересекающимися и вложенными носителями (с. 198);

3) численный метод сравнения вложенных интервалов на базе взвешенной свертки границ интервала (с. 199);

4) численный метод вычисления глубины долговременных корреляций в персистентных временных рядах (с. 199-200);

5) численные методы преобразования числовых временных рядов в лингвистические временные ряды: огибающих ломаных, трендовых коридоров, локального размаха (с. 201-204);

6) численный метод прогнозирования персистентных временных рядов базе клеточно-автоматной прогнозной модели (с. 204-206);

7) численный метод адаптированного метода Парего для многокритериального сравнения альтернатив на графах со структурированными весами ребер (с. 207-209).

В области комплексов программ разработан комплекс проблемно-ориентированных программ «Многокритериальная оптимизация на графах в условиях стохастической неопределенности исходных данных», позволяющий производить расчет количественных оценок допустимых альтернатив на основе предложенных методов и моделей в условиях недетерминированности весов ребер графа и осуществления дальнейшего многокритериального сравнения (с. 240-267).

Теоретическая и практическая значимость работы. Разработанный метод решения задач многокритериального выбора на графах в условиях недетерминированности исходных данных на этапе структурирования подготавливает веса ребер к возможности их адекватного суммирования или сравнения в зависимости от вида частных критериев предпочтительности, что значительно сокращает количество промежуточных расчетов. Комплекс проблемно-ориентированных программ «Многокритериальная оптимизация на графах в условиях стохастической неопределенности исходных данных» является универсальным инструментальным средством для нахождения количественных оценок рассматриваемых альтернатив в задачах многокритериального сравнения и выбора предпочтительных альтернатив. Предложенные в диссертации модели, методы и алгоритмы представляют собой эффективный математический инструментарий для информационных систем аналитических служб предприятий и организаций различного рода деятельности.

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

Положения, выносимые на защиту:

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

2. Классификация исходных данных в виде нечетких множеств по признаку «Близость к более вероятной величине», позволяющая выполнять операции сжатия функции принадлежности и дискретизации.

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

4. Метод дефазификации центров тяжести носителя и функции принадлежности, позволяющий сравнивать нечеткие множества с пересекающимися и вложенными носителями.

5. Метод взвешенной свертки границ вложенных интервалов, являющийся развитием метода сравнения «в центральном смысле» для случая не равнозначности границ интервала.

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

7. Метод вычисления глубины долговременных корреляций персистентных временных рядов, являющийся развитием алгоритма нормированного размаха Херста и использующий понятия «окончание памяти о начальной точке», «глубина долговременной памяти».

8. Адаптированный метод Парето для нахождения множества несравнимых альтернатив в условиях интервальное™ или нечеткости количественных характеристик допустимых решений.

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

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

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

Апробация результатов. Результаты диссертационного исследования и его основные положения обсуждались на конференциях и симпозиумах Всероссийского и Международного уровня: Российская конференция «Дискретный анализ и исследование операций» (Новосибирск, 2002); Международная школа-семинар по геометрии и анализу памяти Н.В. Ефимова (Абрау-Дюрсо, 2002, 2004); VIII Международная конференция «Нелинейный мир. Образование. Экология. Экономика. Информатика» (Астрахань, 2003); III и IV Международные конференции «Новые технологии в управлении, бизнесе и праве» (Невинномысск, 2003, 2004); Международный Российско-Узбекского и Российско-Казахский симпозиумы «Уравнения смешанного типа и родственные проблемы анализа и информатики» (Нальчик - п. Эльбрус, 2003, 2004); I и II Всероссийская научно-практической конференции «Экономическое прогнозирование: модели и методы - 2004» (Воронеж, 2004, 2007); Одиннадцатая Международная конференция «Математика. Компьютер. Образование» (Дубна, 2004); Одесский семинар по дискретной математике Южного научного центра HAH и МОИ Украины (Одесса, 2004); Международная научно- техническая конференция «Интеллектуальные системы (IEEE AIS'04)» и «Интеллектуальные САПР» (CAD-2004) (Дивноморское, 2004); VI INTERNATIONAL CONGRESS OF MATHEMATICAL

MODELING(Nizhniy Novgorod, 2004); 1-ый Международный форум «Актуальные проблемы современной науки. Естественные науки» (Самара, 2005); VII Международный симпозиум «Математическое моделирование и компьютерные технологии» (Кисловодск, 2005); IV Международная научно-практическая конференция «Проблемы регионального управления, экономики, права и инновационных процессов в образовании» (Таганрог, 2005); Международная междисциплинарная научная конференция «Вторые Курдюмовские чтения Идеи синергетики в естественных науках» (Тверь, 2006); IX Международная конференция «Интеллектуальные системы и компьютерные науки» (Москва, МГУ, 2006); Proceedings 17th International Conference on the Application of Computer Science and Mathematics Architecture and Civil Engineering K. Gurlebeek and C. Konke(eds) (Weimar, 2006); III Международная конференция «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (Нальчик, 2006); IX Международный семинар «Дискретная математика и ее приложения» (Москва, МГУ, 2007); XI Междуна-

родная научно-практическая конференция «Системный анализ в проектировании и управлении» (Таганрог, 2007); Международная научно-практической конференции «Современные тенденции развития теории и практики управления в России и за рубежом» (Ставрополь, 2009); Международная научно-практическая конференция «Современные достижения в науке и образовании: математика и информатика» (Архангельск, 2010); 55-я, 56-я, 57-я научно-методические конференции «Современное состояние и приоритеты развития фундаментальных и прикладных исследований в области физики, математики и компьютерных наук» (Ставрополь, СГУ, 2010, 2011, 2012); IV Международная научно-практическая конференция «Моделирование производственных систем и совершенствование информационных технологий» (Ставрополь, 2012); II Международная научно-практическая конференция «Актуальные проблемы современной науки» (Ставрополь, 2013); на научных семинарах Ставропольского государственного университета и Северо-Кавказского федерального университета (Ставрополь, 2012,2013).

По теме диссертации опубликовано: 118 печатных работах, из них: 23 — в научных журналах, рекомендованных ВАК, 88 - тезисов докладов и сборниках статей, 5 - в свидетельствах о государственной регистрации программы для ЭВМ, 3 - в монографиях.

Структура и объем диссертации. Диссертация изложена на 303 страницах основного текста, включает 65 рисунка, 35 таблиц, состоит из введения, шести глав, заключения, списка использованных источников из 298 наименований и 3 приложений.

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

СОДЕРЖАНИЕ РАБОТЫ

ВО ВВЕДЕНИИ обоснована актуальность диссертационного исследования, определена предметная область, оценена степень разработанности темы, обозначены научная и прагматическая проблемы, сформулиро-

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

В ПЕРВОЙ ГЛАВЕ проведен анализ возможных неопределенностей исходных данных в задачах многокритериального выбора на графах и исследована проблема отыскания предпочтительной альтернативы.

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

G = (v,e) со множеством вершин K = {v,.....v„} и множеством ребер

E = {ev...,eL). Каждому ребру ее Е приписаны N неотрицательных весов, которые заданы не детерминированными величинами, а стохастическими неопределенностями 3 видов:

1) интервальное число w(e) = [w,, w2 ] с началом wl и концом w2;

2) нечетким множеством w(e) = \ .1 с носителем {w, } и функцией

IMwJJ

принадлежности

3) динамический временной ряд W(e) = (wi), / = 1,...,и , значений рассматриваемого показателя.

Задается структура допустимого решения Q = {qi,-,?„), представляющая собой упорядоченное множество требуемых степеней всех вершин графа G. Допустимым решением * является подграф x=(v,ej, £,с£, в котором для упорядоченного множества степеней вершин D = (deg(v,),..., deg(v„)) выполняется требование Q.

Для численной оценки допустимых альтернатив х е X и возможности их многокритериального сравнения задается векторная целевая функция

F{x) = {Fl{x\FAx\...,FN{x)), (1)

состоящей из критериев предпочтительности вида

MaxSum: Fy(*) = £wy(e)-> max, и = Ц77,; (2)

ieE,

MinSum: Fy (x) = (e) -> min, v = Nl+l,N2; (3)

et£.

MaxMirt: Fr (x) = £ wK (e) ->■ min, v = N2+\,N3; (4)

eeE,

MinMax: Fv(x) = min wv(e)-> max, v = N3+l, N. (5)

eeE,

Задача состоит в том, чтобы во множестве X выделить элемент *„, который является предпочтительным согласно векторной целевой функции F (1), т.е. на элементе х„ векторная целевая функция F принимает значения min или max по критериям (2) - (5). Под математическим решением индивидуальной задачи многокритериального выбора следует понимать нахождение множества несравнимых альтернатив.

Теорема 1. Всякая задача многокритериального выбора на графах G е S(n) со стохастическими неопределенностями весов ребер и векторной целевой функцией (1) - (5) является полной в случае, если структура допустимого решения Q = (<?,,...,?„) является однородной.

Теорема 2. Всякая задача многокритериального выбора на графах G 6 s(n) со стохастическими неопределенностями весов ребер и векторной целевой функцией (1) - (5) является труднорешаемой, если максимальная мощность множества допустимых решений \x(G,Q)j не ограничена сверху никаким полиномом от п.

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

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

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

- при использовании минимаксного MinMax или максиминного MaxMin показателя предпочтительности для случая исходных данных в виде интервалов с вложенными границами возникает случай несравнимости;

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

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

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

- сведение размерности нечетких множеств к единой величине;

- дефазификация нечетких множеств по центрам тяжести носителя и функции принадлежности;

- получение взвешенной суммы границ интервалов;

- получение прогнозных значений временных рядов.

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

ВО ВТОРОЙ ГЛАВЕ разработаны методы структурирования исходных данных в виде нечетких множеств и интервалов. В главе отмечено, что для обработки исходных данных в виде нечетких множеств существует ряд методов, каждый из которых имеет свои характерные ограничения относительно их применимости для различных классов нечетких множеств. В диссертационной работе рассматриваются дискретные нечеткие числа с признаком для классификации «Близость к наиболее вероятной величине». Согласно этой классификации нечеткие множества могут иметь следующие тренды функции принадлежности: линейный (Л), экспоненциальный (Э), логарифмический (Лог), полиномиальный (П). На рисунке 1 показаны нечеткие множества, принадлежащие этим классам.

в) логарифмический тренд (Лог) г) полиномиальный тренд (П)

Рисунок 1 - Виды функций принадлежности нечетких множеств в классификации «Близость к наиболее вероятной величине»

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

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

Пусть имеем некоторое дискретное нечеткое множество

А=\ .;...: ч[ с размерностью носителя р, которую нужно умень-

шить до величины к. И пусть тренд функции принадлежности имеет один их видов

/} = а-х+Ь (линейныйтренд), (6)

¡л = а-еЬх (экспоненциальныйтренд), С)

¡i = a-\nxb (логарифмическийтренд), (8)

¿ = а,-х" +а2-х"'1 +...+an+i (полиномиальныйтренд). (9)

Тогда вначале нужно получить новый носитель нечеткого множества А размерности к путем определения в интервале la¡,ap] к равностоящих значений носителя А. Получим новый носитель

Новые степени принадлежности М* = |и(а*)...,Да,*)...,Да*)} вычисляются путем подстановки аргументов a*,al.....ак в выбранную функцию

принадлежности (6) - (9).

Итогом выполнения этого метода структурирования является новое дискретное нечеткое множество размерности к:

(П)

№П' Áa't)i

Структурирование «Дефазификация нечетких множеств по центру тяжести носителя и функции принадлежности» состоит в следующем.

Пусть имеем нечеткое множество A=\~jj,,,L 11 ' нег0

вычисляются вначале величины:

к к к (12)

/=1 /=1 i=i Далее, вычисляются центры тяжести носителя и функции принадлежности:

- ¿(а) (13)

" М(а)'М N(a)'

Из полученных центров тяжести (13) составляется интервал [/2;ï] и задаются коэффициенты важности его границ: А = (Л,,Л2), Х1+Х2=1- Результат дефазификации представляет величину

Структурирование «Получение взвешенной суммы границ интерва-

лов» предназначено для сравнения вложенных интервалов и использует формулу (14) для свертки интервала [м*,,^]:

IV* =Я,1У|+Я2м'2, Л1+Л2 =1. (15)

Величины и ¿2 являются коэффициентами важности границ интервала. Если границы интервала являются равнозначными, то \ = = 0,5.

В ТРЕТЬЕЙ ГЛАВЕ приведено описание структурирования вида «Получение прогнозных значений временных рядов». Глава посвящена методам анализа и прогнозирования исходных данных в виде временных рядов. Отмечено, что при прогнозировании временных рядов корреляционно-регрессионными методами возникают две трудности:

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

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

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

Классификационным показателем является показатель Херста, который является мерой смещения в частично броуновском движении:

- Н = 0,50 для броуновского движения (хаотического временного ряда);

- 0,50 < Я < 1,00 для персистентного или трендоустойчивого ряда;

- 0,00<Я<0,50 для антиперсистентной или возвратной к среднему системы.

Для вычисления глубины долговременных корреляций предложен метод последовательного «/¿'-анализа на базе метода нормированного размаха Херста. Описание предлагаемого метода последовательного я/Б -анализа состоит в следующем. Как и в методе Д / 5-анализа временной ряд 2 = (г,), / = 1,л разбивается на начальные отрезки гг, где т = ^п. Для этих отрезков вычисляется размах Я=й(г)=тах2г^-ттг^, который нормирует-

ся на стандартное отклонение s(r). Показатель Херста составляет величину

м (log(A(r)/5(r))) Я(г)= Ю^г/2) '

Глубина памяти временного ряда представляет собой нечеткую величину. Для ее получения необходимо вначале сформировать класс временных рядов s(z»), q = 1,2,3,..., где каждый последующий временной ряд получается из предыдущего путем удаления первого по порядку значения.

Далее следует сформировать последовательности точек окончания памяти о начальном значении для каждого элемента класса .s(z?), q = 1,2,3,.... Условиями окончания памяти являются:

1. на я-траектории я(/)г 0,6, tf(/+l)<0,6;

2. на R IS -траектории сменился тревд.

Вычисление искомой глубины памяти всего временного ряда в целом происходит следующим образом. Формируется носитель нечеткого множества м(г)={тк) глубины памяти временного ряда путем выбора и упорядочения всех возможных разновидностей значений точек окончания памяти о начальном значений внутри класса ■Ф»), <7 = 1,2,3,.... Находятся частости возникновения всех возможных разновидностей значений точек окончания памяти: щ=—■ Функция принадлежности находится по формулам:

п

м = max(wt), р-Щ-, p(mk)~wk -Р-Результирующим нечетким множеством яв-м'

ляется M{z) = {imlr,fj(mk))}.

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

На подшаге 1.1 шага 1 следует выбрать мощность и состав терм-множества. Например, терм-множество W = {H,C,B} имеет мощность т = 3 и состоит из термов: щ=Н - низкий уровень, н>2 = С - средний уровень, w,=B - высокий уровень. Для перевода числового временного ряда в лингвистический временной ряд, реализуемого на подшаге 1.2, разработаны 3 графических метода: трендовых коридоров, локального размаха, огибающих ломаных.

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

и,•••>",..> 1 = 1к, (16)

где к является глубиной долговременных корреляций временного ряда и.

Рисунок 1 — Схема клеточно-автоматной прогнозной модели

Под конфигурацией с памятью понимается следующее. Пусть терм-множество лингвистической переменной IV имеет мощность = 3 и состав {V = {н,С,в}. Тогда, если в лингвистическом временном ряде V встречаются отрезки длины /, переходящие в одно фиксированное состояние, то эти отрезки называют конфигурациями с памятью длины /.

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

{и„,и„_1и„, ип_2ип^ип,...,ип_к...ип_хи„}, (17)

где к - длина конфигурации с памятью.

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

-»Я), *,(«.->£), *,(«.-»в). (18)

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

-> и)> Ф.-Р. С), -> в). (19)

Аналогично, вычисляются частоты и частости переходов из конфигураций и^—и».,«., где к = 3,...,/ в состояния н, С, В:

~>Н), ^в). (20)

На подшаге 3.1 получается прогноз терма к„, в виде лингвистического нечеткого множества £/„, = {(я,- цн),(С;), (й; )}, где сумма полученных степеней принадлежности равна 1: + цс + ц, = 1. Для нахождения величин цн, ИсРв вначале необходимо найти суммы частот из соотношений (18)-(20):

м'н =фп -»я) + *2(и „_,«„ ->Я) + ... + ^(и„^...«„ч1/„ -> Я),

Мс =Фп ->-С)+52(ип.,ал ->С) + ... + 5*(и„_4..лп_,и„ ->С), (21)

Мв В)+Фп-\ип - + -"п-^л ""»Я)-

Далее частоты из (21) нужно нормировать на величину =/4

/'я -"с /4 , (22)

<73 £7з С7з

Прогноз лингвистического временного ряда имеет вид

= {{н;мЛ{С;цЛ(в;мв)}- (23)

На подэтапе 3.2 прогноз представляется прогноз для числового временного ряда в виде числового нечеткого множества

*•« = {(*« (24)

где х„, гс, — числовые соответствия соответствующих термов я, С, в в заключительном отрезке временного ряда.

Для возможности представления прогноза в виде числа на подэтапе 3.3 предлагается произвести дефазификацию числового нечеткого множества

где индексом < = 1,2.....т перенумерованы элементы терм-множества.

Шаг 4 посвящен валидации результатов прогнозирования. На подша-ге 4.1 для оценки погрешности прогнозирования с помощью разработанной клеточно-автоматной модели последовательно рассматриваем лингвистические временные ряды

и,, 1 = \,2,...,т, т = п-г, г = \,п-к. (26)

Лингвистические временные ряды (26) формируются в результате удаления из V последних его значений. Для определенного помеченного номера т следует спрогнозировать терм и„м, представляемый в виде лингвистического нечеткого множества и„+1 = {(н-,р„\{С;ис1(В-,/1в)}- Относительная погрешность лингвистического прогноза определяется формулой

г. (27)

£,=—•100%,

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

Оценку относительной погрешности числового прогноза, реализуемую на подшаге 4.2, можно получить следующим образом. Необходимо осуществить ретропрогноз, т.е. спрогнозировать значения имеющихся во временном ряде г значений с номерами / = ь,ь +1 ,...,п

Ошибку прогнозирования можно найги как относительную погреш-

I

ность прогнозов /е {¿,¿+1.....п) по формуле с(г°)= г » где г, - фактическое значение временного ряда, г° - элемент с максимальной функцией принадлежности в прогнозном числовом нечетком множестве. Соответственно вычисляется относительная погрешность прогнозирования для

|г ~2°\

прогноза в виде числа = -—-. где г, - фактическое значение временного ряда, г' - прогноз в виде числа элемента временного ряда с индексом 1. В качестве оценки точности прогнозирования принимаем средние значения г = или £ = —±—

В ЧЕТВЕРТОЙ ГЛАВЕ описана разработанная методика решения дискретных многокритериальных задач на графах в условиях недетерми-

нированности исходных данных. Вычислительная схема предлагаемой методики состоит из 5 этапов, приведенных на рисунке 2.

Рисунок 2 — Схема метода решения задач многокритериального выбора на графах в условиях недетерминированности исходных данных Исходными данными, вводимыми на этапе 1, являются:

— «нечеткое число» й' (е) =

1) п- вершинный граф О = (у,Ё) с множеством вершин V = {у,,...,у„} и множеством ребер Е = .....еь}\

2) веса и>„(е) ребер фафа в = {у,е), которые могут иметь тип:

У ^ ч 1 с носителем №'(е) и функцией

принадлежности Дн>'(е)),

-«интервал» н>2(е)= [и1,2^),»^)] с началом и>,2(е) и концом м»|(е), - «временной ряд» = , 1 = 1,...,т.

Примечание 1. Для каждого ребра ееЕ выполняется однородность его весов т.е. являются фиксированными типы весов, соответствующие конкретному номеру у. К примеру, если весу и = 1 соответствует тип «нечеткое множество», то этот тип относится к весам под номером у = 1 для практически всех ребер графа в.

На подэтапе 2.1 задаются требования <2 = {д1,...,?„) к структуре допустимого решения х = (У,Ех). Под требованиями <2 понимаются необходимые степени вершин

<?1 = ), ?2 = 'МпгХ <^(у/л), (28)

где индексы / = 1 ,...,п представляют собой зафиксированные изначально номера вершин графа С.

На подэтапе 2.2 формируется множество допустимых решений X - {*}, удовлетворяющих требованиям Q.

Векторная целевая функция и частные критерии для оценки предпочтительности решений х задаются на подэтапе 2.3. Количество критериев в векторной целевой функции соответствует количеству весов V ребер рассматриваемого графа С. Критерии векторной целевой функции могут быть как максимизируемыми, так и минимизируемыми и иметь вид «суммарный эффект» (МЫБит или МахБит) (2), (3) либо «оценка по наихудшему» (МтМах или МахМ'т) (4), (5). Следует отметить, что для оценки качества допустимых альтернатив могут применяться только весовые критерии (2) -(5), и не могут применяться топологические критерии, т.е. топология допустимого решения задается изначально в условии такого класса задач.

На подэтапе 3.1 происходит структурирование весов в виде нечетких множеств. Нечеткие арифметические операции на базе векторного получения носителя выполняются следующим образом.

Пусть имеем два нечетких множества, размерности которых на этапе структурирования сведены к единой величине р:

(29)

1Ж) /Ц) ^ы]

В диссертации предлагается нечёткие арифметические операции ре-ализовывать по приведенным ниже формулам: - нечеткое суммирование

х- +г = { Х,1.+У1 .,..., х;,+у' .....х,".+у',\

"(*Г+ >-*)' 'Ж + у')' 'Ур\

где /¿(г* + у*)= тах(ы(**

- нечеткое вычитание

х' ~У\ . X, -УI

(31)

(32)

где м(х' - у' ) = тт(р(х' ) 1 - /¿(у* )): - нечеткое умножение

* * 1 V „

*1 -У\ -У! хр Ур

(33)

'Ж ' У р)]'

где р{х' ~ у*)== тт^

- нечеткое деление

~ у * - : х< :у' ■ *р'Ур

(34)

[4*1 Ж^л)' ' У р))

где Ддг* ? у' )= тах(д(г*) 1 - /¿(у*)).

На подэтапе 3.2 выполняется дефазификация нечетких множеств по центру тяжести носителя и функции принадлежности. Данная процедура относится к структурированию нечетких данных для возможности их дальнейшего сравнения. На подэтапе 3.3 выполняется структурирование вида «Получение взвешенной свертки границ интервалов» применимо для интервалов с вложенными границами.

Если веса ребер заданы временными рядами, то для последующих вычислений количественных показателей Ру(х) допустимых решений X

необходимо выполнить прогнозирование временных рядов. Структурирование в виде «Получение прогнозных значений временных рядов» выполняется на подэтапе 3.4. В главе 3 описана предлагаемая в диссертации прогнозная модель для персистенгных временных рядов. Данная модель базируется на инструментарии клеточных автоматов и использует свойство иметь конфигурации с памятью.

Перед началом прогнозирования конкретного временного ряда рекомендуется:

- вычислить методом последовательного R/S- анализа показатель Херста;

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

Выбирать аппарат для прогнозирования рекомендуется в зависимости от класса принадлежности временного ряда:

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

- если отнесен к классу хаотических, то есть все основания использовать для прогнозирования трендовые модели корреляционно-регрессионные анализа;

- если отнесен к классу антиперсистентных, то видимо, адекватным математическим обеспечением будет аппарат Марковских цепей.

На этапе 4 вычисляются количественные характеристики Fv(x) допустимых решений X. Под количественными характеристиками понимаются величины:

Ые), (35)

F„(;c)=mmwK(e), (36)

Fv{x) = max«v(e). (37)

В случае (35) количественной характеристикой некоторого допустимого решения х является сумма весов ребер w„(e) графа G, вошедших в подграф x = (v,Ex). Эту характеристику называют также «суммарным эффектом». В случаях (37) и (38) количественными характеристиками являются, соответственно, минимальный или максимальный вес ребра из спис-

ка ребер, вошедших в допустимый подграф х = {У,Ех). Эти характеристики называют также «оценка по наихудшему».

На этапе 5 выполняется многокритериальное сравнение множества допустимых решений X по вычисленным количественным характеристикам /V (х). Для осуществления многокритериального выбора в задачах с детерминированными исходивши данными можно воспользоваться одним из 6 методов:

- полный перебор возможных альтернатив X, многокритериальное сравнение количественных оценок £"к(х) методом Парето;

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

- приближенные алгоритмы с оценками нахождения оптимальных или субоптимальных альтернатив;

- сведение многокритериальной задачи к однокритериальной задаче;

- условная максимизация;

- поиск альтернативы с заданными свойствами.

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

Для суммирования нечетких весов графа предлагается использовать формулу (33).

Для реализации суммирования интервальных весов графа необходимо воспользоваться известным граничным методом. Пусть имеем два интервала а = [а|,а2] и Ь = \ь1,Ъ2]. Их сумма равна величине

с = а + Ь = \ах+Ь1,а2+Ь2\ (38)

Для реализации суммирования весов ребер в виде временных рядов следует воспользоваться спрогнозированными значениями временных рядов. Пусть имеем два временных ряда Я'1 IV2 где > = \,Т, г = 1,/?. Сумма весов в ввде временных рядов и IV2 равна величине:

(39)

где и полученные прогнозные значения временных рядов IV1 и И'2.

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

Пусть имеем множество упорядоченных допустимых решений = (*,.), г = \к. И пусть для каждого решения хг найдены его количественные оценки Fv{x), которые могут иметь вид нечеткого множества, интервала или числа.

Многокритериальное сравнение по адаптированному методу Парето состоит в следующем. На первом этапе первое по порядку допустимое решение jc, попарно сравнивается с допустимыми решениями х2,...,хк. Для возможности реализации сравнения двух допустимых решений х{,х2еХ следует ввести отношение предпочтения (доминирования) для них.

Определение 1. Для двух решений xt,x2 еХ задачи на графах G = (V, Е) с векторной целевой функцией вида f(x) (1) и максимизируемыми (минимизируемыми) критериями Fv(x) вида (2) - (5) при весах wv(e) ре-

чений »(<?) = , ] или временными рядами УУ(е)={к1), предикат х, >-х х2 считается истинным, если /ч.(хг1)>Гу(х2) и = 1,среди

которых хотя бы одно является строгим. При истинности предиката ~>~х х2 считают, что допустимое решение х, предпочтительнее допустимого решения х2. Если предикат оказался ложным, то удалять из рассмотрения допустимые решения не следует, т.к. возникает ситуация несравнимости. Таким образом, на первом этапе реализовано сравнение к-1 пар. Если некоторое допустимое решение х1 явилось доминируемым хотя бы в одной паре, то его следует удалить из рассмотрения. Подмножество допустимых решений, оставшихся после удаления на первом этапе, можно обозначить X,.

На втором этапе подобным образом следует попарно сравнить допустимое решение х2 с допустимыми решениями х3,...,хк и составить подмножество недоминируемых допустимых решений Х2. На последующих этапах выполняются аналогичные попарные сравнения и составляются подмножества недоминируемых допустимых решений ХЪ,...,Хк__х. Резуль-

бер, заданными нечеткими множествами

тирующее множество недоминируемых альтернатив или множество Паре-то X получается в результате объединения множеств Х^.^Х^.

В ПЯТОЙ ГЛАВЕ разработаны численные методы предложенных в диссертации математических моделей и методов для задач многокритериального выбора на графах в условиях недетерминированности исходных данных. Кроме того, оценена эффективность решения этого класса задач. Отмечено, что эффективность моделирования и алгоритма, обеспечивающего получение результатов, можно оценить по следующим трем показателям качества: диапазон исходных данных, точность, вычислительная сложность.

Показатель качества «диапазон исходных данных» определяет объем памяти ЭВМ, необходимой для ввода исходной информации. Исходной информацией в рассматриваемом классе задач является: количество вершин графа, список ребер графа, веса ребер графа, структура допустимого решения, векторная целевая функция с критериями предпочтительности альтернатив. При сравнении эффективности разработанной методики относительно существующих подходов решения задач многокритериального выбора в условиях недетерминированности весов ребер графа диапазон исходных данных сужаться не будет.

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

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

Относительная погрешность нахождения многокритериального оптимума колеблется в пределах от 5% до 16,9%. В то время, как решение таких задач существующими методами обработки нечетких и интервальных данных, а также прогнозированием временных рядов имеют неприемлемую погрешность в пределах от 25,5% до 71,3%. Понижение трудоемко-

сти составляет величину Дг = у"6-^у"5+у"3+у"2где

л - размерность входной информации (количество вершин в графе).

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

В ШЕСТОЙ ГЛАВЕ приводится описание разработанного комплекса проблемно-ориентированных программ - приводятся алгоритмы в виде блок-схемы и описываются характеристики программного обеспечения.

В ЗАКЛЮЧЕНИИ приведены основные научные и практические результаты диссертационного исследования с описанием степени новизны.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В области математического моделирования:

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

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

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

В области численных методов:

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

5. Предложен метод построения исходных данных в виде нечетких множеств в классификации по признаку «Близость к более вероятной величине».

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

7. Разработан метод последовательного Л/5- анализа для вычисления глубины долговременных корреляций в персистенгных временных рядах, позволяющий выполнять выводы об окончании памяти о начальных точках временного ряда и получать оценки минимальной, средней и максимальной конфигураций с памятью в клеточно-автоматной модели прогнозирования.

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

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

В области комплексов программ

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

РАБОТЫ В ИЗДАНИЯХ, РЕКОМЕНДОВАННЫХ ВАК РФ

1. Тебуева Ф.Б., Перепелица В.А., Касаева М.Д., Темирова Л.Г. Использование инструментария клеточных автоматов для формирования прогнозных нечетких значений урожайностей на базе временного ряда// Известия вузов. Естественные науки. Северо-Кавказский регион. -№4,2003. - С. 5-11.

2. Тебуева Ф.Б., Перепелица В.А Предпрогнозный фрактальный анализ временных рядов индекса роста промышленного производства страны и региона// Вестник Ставропольского государственного университета. - 2005. - Вып.44. - С. 21-29.

3. Тебуева Ф.Б., Перепелица В.А., Гречкин В.А. Задача инвестора с интервальными данными// Вестник Ставропольского государственного университета - 2005 -Вып.43-С. 9-13.

4. Тебуева Ф.Б., Перепелица В.А., Лукашов С.А., Мелихов Э.В. Фрактальная статистика в экономико-математическом моделировании// Гуманитарные и социально-экономические науки. - №5,2006. - С.62-65.

5. Тебуева Ф.Б., Темирова Л.Г., Коркмазова Ф.А., Биджиев А.З. Структурирование данных для дискретных эволюционных процессов и прогнозирование временных рядов// Гуманитарные социально-экономические науки. - №5,2006. - С. 75-79.

6. Тебуева Ф.Б., Перепелица В.А., Овчаренко Н.Ф. Роль и развитие статистики и экономике-математических методов//История науки и техники -№12 2005 -С 3649. '

7. Тебуева Ф.Б., Перепелица В.А., Гречкин В.А., Шенкао Т.М. Исследование мощности множества альтернатив 2-критериальной задачи инвестора// Вестник Ставропольского государственного университета. - 2006. - Вып.47 - 4.2. - С. 9-13.

8. Тебуева Ф.Б. Два подхода к реализации фрактального анализа временных рядов// Научно-технические ведомости СПбГПУ. - Т2. - №4,2007. - С. 105-112.

9. Тебуева Ф.Б. Новые арифметические операции над нечеткими весами в дискретных задачах оптимизации на графах// Горный информационно-аналитический бюллетень. - №6. - 2008. - С. 373-381.

10. Тебуева Ф.Б. Принятие решений в дискретных задачах оптимизации на графах с нечеткими весами// Горный информационно-аналитический бюллетень - №6 -2008.-С. 381-392.

11. Тебуева Ф.Б., Перепелица В.А. Об одной однородной структуре для прогнозирования эволюционных процессов с памятью// Обозрение прикладной и примышленной математики. - №6. - 2008. - С. 714-715.

12. Тебуева Ф.Б., Торопцев Е.Л., Тоторкулова М.А. Прогнозирование эволюционных процессов инвестирования в основной капитал экономики региона// Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. - №5,2008. - С. 322-327.

13. Тебуева Ф.Б., Зайцева И.В., Коркмазова Ф.А Математическая модель и анализ устойчивости регионального рынка труда// Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. - №5 2008 - С 332-336.

14. Тебуева Ф.Б., Копытов В.В. Прогнозирование чрезвычайных ситуаций техногенного характера по коротким временным рядам// Научные и образовательные проблемы гражданской защиты. -№2. - 2009. - С. 33-36.

15. Тебуева Ф.Б., Перепелица В.А. Задачи дискретной оптимизации с интервальными параметрами// Журнал вычислительной математики и математической физики. - Вып.50 (5), 2010. - С. 836-847.

16. Тебуева Ф.Б., Перепелица В.А. Подходы к решению дискретных задач оптимизации на графах с нечеткими весами// Вестник Ставропольского государственного университета. - Вып.70 (5), 2010. - С. 5-10.

17. Тебуева Ф.Б., Торопцев ЕЛ., Перепелица В.А. Краткосрочное прогнозирование процесса ветрогенерации методом клеточных автоматов// Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. - №3(130), 2011. - С. 51-60.

18. Тебуева Ф.Б., Гриценко Ан.В., Русаков Д.А. Методика вычисления классификационных показателей временных рядов эволюционных процессов с долговременными корреляциями// Вестник Ставропольского государственного университета. - Вып. 75 (4), 2011. - С. 39-43.

19. 'Гебуева Ф.Б., Перепелица В.А. Разработка методики количественной оценки долговременной памяти эволюционных дискретных процессов // Вестник Ставропольского государственного университета. — Вып. 75 (4), 2011. - С. 39-43.

20. Тебуева Ф.Б., Кабиняков М.Ю. Статистический анализ персистентных временных рядов (на примере потребления электроэнергии) // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. -№4 (131), 2011.

21. Тебуева Ф.Б., Дубинин Е.А., Копытов В.В. Обработка результатов экспертной оценки ущерба информационной системе для вывода интегральной функции принадлежности // Инфокоммуникационные технологии. - №1. - 2012. - С. 89-96.

22. Тебуева Ф.Б., Перепелица В.А, Кабиняков М.Ю. Технология прогнозирования регулярной компоненты временных рядов эволюционных дискретных процессов с долговременными корреляциями// Вестник СевКавГТИ. — №13. - 2012. - С. 21-25.

23. Тебуева Ф.Б., Перепелица В.А., Кабиняков М.Ю. Декомпозиция и прогнозирование временных рядов с долговременными корреляциями // Известия Южного федерального университета. Технические науки. —№1. —2013. -С. 111 —120.

ПУБЛИКАЦИИ В ДРУГИХ ИЗДАНИЯХ

24. Тебуева Ф.Б., Перепелица В.А, Темирова Л.Г. Моделирование экстремальных задач на графах с нечеткими данными/ Труды участников Международной школы-семинара по геометрии и анализу памяти Н.В. Ефимова. Абрау-Дюрсо, 5-11 сентября 2002, Ростов-на-Дону: Ростовское математическое общество, 2002. - С. 214-216.

25. Тебуева Ф.Б., Перепелица В.А., Узденов Р.Х. Фрактальный анализ устойчивости развивающихся агросистем / Материалы III Международной научно-практической конференции «Математическое моделирование в образовании, науке и производстве», Тирасполь, 17-20 сентября, 2003. - Тирасполь: РИО ПГУ, 2003. - С. 4647.

26. Тебуева Ф.Б., Перепелица В.А., Узденов Р.Х. Оценки глубины памяти дня временного ряда жилищного строительства / Тез. докладов VIII Международной конференции серии «Нелинейный мир. Образование, экология, экономика, информатика».

- Астрахань: ГУП «Издательско-полиграфический комплекс «Волга», 2003. - С. 241.

27. Тебуева Ф.Б., Перепелица В.А. Темирова Л.Г. Иерархический подход к вероятностному анализу одного класса временных рядов / Труды Международной школы

- семинара по геометрии и анализу памяти Н.В. Ефимова, Абрау-Дюрсо, база отдыха Ростовского госуниверситета «Лиманчик», 5-11 сентября 2004, Ростов-на-Дону: Изд-во ООО «ЦВВР», 2004. - С. 219-220.

28. Тебуева Ф.Б., Перепелица В.А. Темирова Л.Г. Реализация генетического алгоритма прогнозирования на базе клеточного автомата/ Труды Международных научно- технических конференций «Интеллектуальные системы (IEEE AIS'04)» и «Интеллектуальные САПР» (CAD-2004). Научное издание в 3-х томах. - М.: Изд-во Физико-математической литературы, 2004. - Т.1, с. 75-78.

29. Tebueva F.B., Perepelitsa V.A., Temirova L.G. Two-level approach to econom-ic-mathema-tical modeling of evolutionary processes and systems/VI INTERNATIONAL CONGRESS OF MATHEMATICAL MODELING/ BOOK OF ABSTRACTS/ September 20-26,2004, Nizhniy Novgorod, Univercity of Nizhniy Novgorod. P. 427.

30. Тебуева Ф.Б., Перепелица B.A., Савина Л.А. Формирование предпрогноз-ной информации методами фазового анализа для временных рядов с памятью/ Труды 1-го Международного форума «Актуальные проблемы современной науки». Естествен-

ные науки. - Части 1, 2: Математика. Математическое моделирование. - Самана- Изд-во СамГТУ, 2005. - С. 76-79.

31. Тебуева Ф.Б., Шенкао Т.М. Теоретико-графовая модель сегментации рынка по видам продукции / Сблрудов IV Международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании». - Том 2. «Современные образовательные и информационные технологии в практике вузовского образования, управления и экономики» - Таганрог Изд-во ТИУиЭ, 2005. - С. 172-176.

32. Тебуева Ф.Б., Кошелев И.В. Из опыта применения новых информационных технологий дня прогнозирования временных рядов со слабой трендоустойчивостью / Сб.трудов IV Международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании». -Том 2. «Современные образовательные и информационные технологии в практике вузовского образования, управления и экономики». - Таганрог: Изд-во ТИУиЭ 2005 -С 150-155.

33. Тебуева Ф.Б., Джашеева Ф.М., Беляков С.С. Агрегирование временного ряда как инструментарий улучшения его предпрогнозных характеристик / Сб.трудов IV Международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании». - Том 2. «Современные образовательные и информационные технологии в практике вузовского образования, управления и экономики».- Таганрог: Изд-во ТИУиЭ, 2005. -С. 155-160.

34. Тебуева Ф.Б., Перепелица В.А., Коркмазова С.С. Трехуровневая иерархия циклической компоненты временного ряда солнечной активности / Материалы Международной междисциплинарной научной конференции «Вторые Курдюмовские чтения Идеи синергетики в естественных науках», Тверь, 20-23 апреля 2006 г. Тверь- Твер гос ун-т, 2006.-С.90-92.

35. Тебуева Ф.Б., Биджиев А.З., Лукашов С.А. Использование агрегирования и клеточного автомата для прогнозирования временных рядов заболеваемости / Материалы Международной междисциплинарной научной конференции «Вторые Курдюмовские чтения Идеи синергетики в естественных науках», Тверь, 20-23 апреля 2006 г -Тверь: Твер. гос. ун-т, 2006. - С. 93-95.

36. Тебуева Ф.Б., Перепелица В.А., Лукашов С.А. Гибридное прогнозирование временного ряда на базе клеточного автомата и фазового анализа / Материалы Международной междисциплинарной научной конференции «Вторые Курдюмовские чтения Идеи синергетики в естественных науках», Тверь, 20-23 апреля 2006 г. Тверь- Твер гос ун-т, 2006.-С. 87-89.

37. Тебуева Ф.Б., Перепелица В.А. Методы нелинейной динамики в моделировании эволюции солнечной активности / Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки», 23-27 октября 2006, М.: Изд-во механико-математического факультета МГУ. -Т.1, часть 2, 2006. - С. 195-Ш.

38. Тебуева Ф.Б., Шенкао Т.М. Алгоритмы с оценками для дискретной задачи сегментации / Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки», 23-27 октября 2006, М.: Изд-во механико-математического факультета МГУ, 2006.

39. Tebueva F.B., Perepelitsa V.A., Shenkao Т.М. Solvability exploration of segmentation problem with linear convolution algorithms / Proceedings 17th International Conference on the Application of Computer Science and Mathematics Architecture and Civil Engineering K. Gurlebeek and C. Konke(eds), 12-14 July 2006, Weimar, Germany. - C. 1-13.

40. Тебуева Ф.Б., Перепелица B.A., Темирова M.A. Методы прогнозирования временных рядов, имеющих иерархическую структуру циклической компоненты / Материалы III Международной научно-практической конференции «Экономическое про-

гнозирование: модели и методы», Воронеж, 5-6 апреля 2007 г., Воронеж: Воронежский государственный университет, 4.1. - 2007. - С. 47-55.

41. Тебуева Ф.Б., Перепелица В.А. К вопросу о математическом моделировании на графах задачи землепользования / Материалы IX Международного семинара «Дискретная математика и ее приложения», Москва, МГУ, 18-23 июля 2007, М.: Изд-во механико-математического факультета МГУ, 2007. - С. 287-290.

42. Тебуева Ф.Б., Мохамед-Боташева З.А. Циклическая компонента временных рядов как мера их устойчивости/ Труды XI Междунар. науч. - практ. конф. «Системный анализ в проектировании и управлении», 28 июня-10 июля 2007 г. - СПб.: Изд-во Политехи. Ун-та, 2007. - С. 143-145.

43. Тебуева Ф.Б., Коркмазова С.С. Фрактальные процессы в задачах землепользования / Материалы II Международной междисциплинарной научной конференции «Четвертые юбилейные Курдюмовские чтения: Синергетика в естественных науках», Тверь, 10-13 апреля 2008 г. Тверь: Твер. гос. ун-т, 2008. - С.

44. Тебуева Ф.Б. Методы реализации арифметических операций и сравнение для обработки нечетких чисел/ Материалы II Международной научно-практической конференции «Актуальные проблемы современной науки», Ставрополь, 13-16 марта 2013 года, Ставрополь: НОУ ВПО «СевКавГТИ», 2013.-222с.

45. Тебуева Ф.Б., Перепелица В.А., Темирова Л.Г. Математическая модель землепользования на базе нечетких множеств и клеточных автоматов// Электронный журнал «Исследовано в России», 2003, С. 2429-2438 http:// 7humal.ape.relam.ru/articles/003/207.pdf

46. Тебуева Ф.Б., Зеляковская В.М., Перепелица В.А., Завгороднева О.В., Зеля-ковский Е.В., Узденов Р.Х. Проблемы формирования инвестиционных условий развития агропромышленного комплекса/ Препринт. - Волгоград: Изд-во ВГСХА, 2004. - 48 с.

47. Тебуева Ф.Б., Перепелица В.А., Тамбиева Д.А., Темирова Л.Г. Клеточно-графовый автомат для прогнозирования временных рядов // Доклады Одесского семинара по дискретной математике Южного научного центра HAH и МОН Украины, август 2004. - Одесса: Астропринт, 2004. - С. 44-50.

48. Тебуева Ф.Б., Беляков С.С., Овчаренко Н.Ф. Выявление фрактальных характеристик для процесса прогнозирования временных рядов налоговых поступлений// Успехи современного естествознания. - М.: Изд-во РАЕ. - №2. - 2005. - С. 54-55.

49. Тебуева Ф.Б., Перепелица В.А., Шенкао Т.М. Исследование многокритериальной постановки теоретико-графовой задачи сегментации // Известия вузов. СевероКавказский регион. Естественные науки. Приложение 11'05. - 2005. - С. 48-56.

50. Тебуева Ф.Б., Перепелица В.А., Кошелев И.В. Предпрогнозный анализ и прогнозирование временного ряда на базе методов нелинейной динамики // Известия вузов. Северо-Кавказский регион. Общественные науки. Приложение 1'06. - 2006. - С. 32-41.

51. Тебуева Ф.Б., Перепелица В.А., Эбзеева Н.С., Овчаренко Н.Ф. Использование долговременной памяти временных рядов для их предпрогнозного анализа // Известия вузов. Северо-Кавказский регион. Общественные науки. Приложение 8'05. - 2005. -С. 43-54.

52. Тебуева Ф.Б., Перепелица В.А., Шенкао Т.М. О вычислительной сложности интервальных задач на графах // Известия вузов. Северо-Кавказский регион. Естественные науки. Приложение 12'06. - 2006. - С. 18-30.

53. Тебуева Ф.Б., Дубинин Е.А. Исследование методик анализа информационных рисков / Деп. в ВИНИТИ, 2010. - 42 с, №59- В2010.

МОНОГРАФИИ

54. Тебуева Ф.Б., Перепелица В.А., Темирова Л.Г. Структурирование данных методами нелинейной динамики для двухуровневого моделирования. - Ставрополь: Ставропольское книжное издательство, 2006. - 284 с.

55. Тебуева Ф.Б. Многокритериальная задача покрытия графа звездами и ее приложения. - Ростов н/Д: Изд-во ЮФУ, 2007. - 128 с.

56. Тебуева Ф.Б., Перепелица В.А Дискретная оптимизация и моделирование в условиях неопределенности данных. — М.: Академия Естествознания. - 2007. - 151 с.

СВИДЕТЕЛЬСТВА О ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ ПРОГРАММ ДЛЯ ЭВМ

57. Тебуева Ф.Б., Перепелица В.А, Темирова Л.Г., Власов К. Клеточно-автоматное прогнозирование временных рядов с памятью («КАПВРП»), Свидетельство №2004612017 от

58. Тебуева Ф.Б., Копытов В.В., Дубинин Е.А. Оценка ущерба информационной системе предприятия («ОУИСП»), Свидетельство №2012613193 от 04.04.2012.

59. Тебуева Ф.Б., Гриценко Ан.В., Гриценко Ар.В. Декомпозиция временных рядов с долговременной памятью («ДВРСДП»), Свидетельство №2012611486 от

08.02.2012 г.

60. Тебуева Ф.Б., Крестьянинов А.Ю. Моделирование дискретных временных рядов с долговременной памятью («МДВРСДП»), Свидетельство №2013611706 от

31.01.2013 г.

61. Тебуева Ф.Б., Коновалов С.С. Программный комплекс «Многокритериальная оптимизация на графах в условиях стохастической неопределенности исходных данных». Свидетельство №2013616697 от 17.07.2013 г.

Личный вклад автора в работах, опубликованных в соавторстве: разработка математической модели сведения размерности нечетких множеств к единой величине [16, 24, 41, 45, 54, 56], разработка математической модели де-фазификации нечетких множеств по принципу взвешенной свертки центров тяжести носителя и функции принадлежности [6, 10, 44, 50, 51], разработка кле-точно-автоматной модели для прогнозирования персистентных временных рядов [1, 11, 12, 17, 22, 47], разработка метода оценки глубины долговременной коррелированное™ временного ряда [2, 4, 25, 26, 43, 51], разработка метода сравнения интервалов с вложенными границами [3, 15], разработка методов сравнения альтернатив с нечеткими параметрами [16, 24, 45, 21], разработка методов сравнения альтернатив с нечеткими параметрами [15, 52, 53], разработка методики вычисления классификационных характеристик для временных рядов [18, 19, 20, 30, 32, 33], исследование вычислительной сложности и устойчивости [7, 13, 38, 52, 53, 55], развитие клеточно-автоматной прогнозной модели для временных рядов с выраженной циклической компонентой [27, 34, 35, 40, 42], развитие методов декомпозиции временных рядов [5, 22, 23, 36, 48, 59], разработка численных методов [14, 28, 29, 31, 37, 46], разработка приближенных алгоритмов нахождения многокритериального оптимума [39, 49, 55], разработка программного комплекса [57-61].

Соискатель ( / Ш^-л Ф-Б. Тебуева

■л

СЕВЕРО-КАВКАЗСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

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

05.13.18 - Математическое моделирование, численные методы

и комплексы программ

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

0520145066

Тебуева Фариза Биляловна

Диссертация на соискание ученой степени доктора физико-математических наук

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

СОДЕРЖАНИЕ

С

ВВЕДЕНИЕ............................................................................ 6

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

1.1 Формализация прикладных задач в виде задач многокритериального выбора на графах в условиях недетерминированности исходных данных.... И

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

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

1.3.1 Недостаточность информативности результата и неприемлемая трудоемкость расчетов при выполнении арифметических операций над нечеткими исходными данными с различной размерностью носителя......... 3$

1.3.2 Отсутствие методов сравнения нечетких множеств без использования процедуры нормализации и несравнимость вложенных интервалов.................................................................................... 41

1.3.3 Необходимость структурирования исходных данных, представленных временными рядами, и неадекватность классического математического аппарата прогнозирования для персистентных временных рядов...........................................................................................

1.4 Оценка применимости методов многокритериального выбора предпочтительной альтернативы с детерминированными исходными данными для случая недетерминированности....................................... 61

1.5 Формулировка научной проблемы и постановка научных задач диссертационного исследования........................................................ 7(

1.6 Выводы по главе.................................................................. 7(

2 РАЗРАБОТКА МЕТОДОВ СТРУКТУРИРОВАНИЯ ИСХОДНЫХ ДАННЫХ В ВИДЕ НЕЧЕТКИХ МНОЖЕСТВ И ИНТЕРВАЛОВ ЗНАЧЕНИЙ.............................................................................. Г,

2.1 Обоснование выбора классификации нечетких множеств по признаку «Близость к более вероятной величине»................................. 11

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

2.3 Разработка метода упорядочения по предпочтительности двух нечетких множеств с вложенными границами носителя........................... 9<

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

2.5 Выводы по главе................................................................. 1 (

3 РАЗРАБОТКА ПРОГНОЗНОЙ МОДЕЛИ ДЛЯ СТРУКТУРИРОВАНИЯ ИСХОДНЫХ ДАННЫХ В ВИДЕ ПЕРСИСТЕНТНЫХ ВРЕМЕННЫХ РЯДОВ........................................ 1(

3.1 Разработка метода последовательного я/£ - анализа для вычисления глубины долговременных корреляций в персистентных временных рядах.... 11

3.2 Применение алгоритма последовательного Я /я -анализа для получения циклических характеристик персистентных временных рядов.... 11

3.3 Разработка математической модели для прогнозирования персистентных временных рядов на базе инструментария клеточных автоматов.................................................................................... 11

3.3.1 Разработка методов трансформации числовых временных рядов в клеточные автоматы........................................................................ 11

3.3.2 Оценка частотной памяти временного ряда, представленного клеточным автоматом...................................................................... 1;

3.3.3 Получение прогноза и оценка погрешности............................ 1;

3.4 Сравнительный анализ результатов прогнозирования временных рядов из классификации по признаку «Персистентность»......................... 1:

3.5 Выводы по главе................................................................ и

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

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

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

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

4.4 Пример нахождения многокритериального оптимума в задаче на графах с недетерминированными весами ребер............................................... И

4.5 Выводы по главе................................................................... 1 $

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

5.1 Численные методы решения задач многокритериального выбора на графах в недетерминированности исходных данных............................... И

5.2 Методология оценки эффективности вычислительного алгоритма... 21

5.3 Исследование вычислительной сложности многокритериальных задач на графах с недерминированными весами ребер............................. 2]

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

5.5 Разработка приближенных алгоритмов для некоторых подклассов задач на графах в условиях недетерминированности исходных данных........ 2:

5.5 Выводы по главе.................................................................. 22

6 РАЗРАБОТКА КОМПЛЕКСА ПРОБЛЕММНО-ОРИЕНТИРОВАННЫХ ПРОГРАММ ДЛЯ МОДЕЛИРОВАНИЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА НА ГРАФАХ С НЕДЕТЕРМИНИРОВАННЫМИ ИСХОДНЫМИ ДАННЫМИ............... 2'

6.1 Разработка алгоритма методики решения задач многокритериального выбора на графах в условиях недетерминированности исходных данных........................................................................... 2^

6.2 Описание комплекса проблемно-ориентированных программ «Многокритериальная оптимизация на графах в условиях стохастической неопределенности исходных данных»............................................... 2(

6.3 Выводы по главе.................................................................. 2(

ЗАКЛЮЧЕНИЕ......................................................................... 2(

СПИСОК ЛИТЕРАТУРЫ............................................................ Т,

ПРИЛОЖЕНИЯ......................................................................... 3(

ВВЕДЕНИЕ

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

Положения работы поддержаны грантами Российского фонда фундаментальных исследований: «Математическое моделирование структуры слабо формализованных систем в условиях неопределенности», «Структурирование, выявление несоответствий и прогнозирование

эволюционных дискретных процессов и систем при наличии долговременных корреляций».

По теме диссертационной работы выполнены следующие проекты Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы»: «Разработка вычислительных методов структурирования, выявления несоответствий и прогнозирования эволюционных дискретных процессов с долговременными корреляциями в системах обработки информации» (2010-2012), «Разработка технологий проектирования эволюционирующих информационных систем на основе моделирования регламентов в специальных средах» (2010-2012).

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

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

Степень разработанности темы исследования. Задачам математического моделирования систем в условиях детерминированности исходных данных посвящены публикации ученых: Самарский A.A., Партыка Т.Д., Попов Э.В., Мышкис А.Д., Плотинский Ю.М., Сергиенко И.В. и др.

Развитию методов многокритериальной оптимизации и принятия решений посвящены научные труды отечественных и зарубежных авторов: Саати Т., Прокушева А.П., Прокушев Я.Е., Подиновский В.В., Ногин В.Д., Пападимитриу X., Стайглиц К., Моисеев H.H., Михалевич B.C., Трубин В.А., Шор Н.З., Майника Э., Львович Я.Е., Чернышева Г.Д., Каширина И.Л., Лесин В.В., Лисовец Ю.П., Ларичев О.И., Иванов Б.Н., Дубов Ю.А., Травкин С.И., Якимец В.Н.

В развитие теории моделирования нечетких и интервальных данных внесли существенный вклад научные исследователи: Заде Л., Зайченко Ю.П., Нариньяни A.C., Орловский С.А., Мелькумова Е.М., Левин В.И., Куржанский А.Б., Курдюмов И.В., Мосолова М.В., Назайкинский В.Е., Кофман А., Корченко А.Г., Ким-Гю-Пхир, Калмыков С.А., Шокин Ю.И., Юлдашев З.Х., Лообязко О.Н.. НесЬедов С.Ф.. Лилигенский Н.В.. Лымова Л Г . Севастьянов

» ' л. ■ • 'Г 1 У Г Л - У ~ -

П.В., Берштейн Л.С., Мелихов А.Н., Боженюк A.B. и др.

Анализу и прогнозированию временных рядов посвящено огромное количество публикаций, среди которых можно выделить публикации авторов: Мандельброт Б.Б., Отнес Р., Петере Э., Осборн М., Песаран М., Пригожин А.И., Пуарье Д., Мартино Дж., Хакен Г., Сигел Э., Хейс Д., А. Хоскинг, Базаров В.А., Громан В.Г., Канторович Л.В., Кондратьев Н.Д., Новожилов В.В., Перепелица В.А., Фельдман Г.А., Шаталин С.С. и др.

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

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

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

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

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

Поставленная цель требует решения следующих частных научных задач:

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

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

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

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

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

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

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

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

В области математического моделирования:

1) математическая модель сведения размерностей нечетких множеств к единой величине, позволяющая реализовывать более экономные арифметические операции по принципу «векторное получение носителя и теоретико-множественные операции над степенью принадлежности» (с. 8098);

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

3) математический метод сравнения вложенных интервалов, использующий взвешенную свертку границ интервала, и, являющийся развитием метода сравнения в центральном смысле (с. 102-107);

4) математический метод вычисления глубины долговременных корреляций в персистентных временных рядах, базирующийся на свойстве фрактальности, для определения длины конфигурации с памятью и осуществления настройки клеточно-автоматной прогнозной модели (с. 110111);

5) методы преобразования числовых временных рядов в лингвистические временные ряды: огибающих ломаных, трендовых коридоров, локального размаха (с. 123-129);

6) математическая модель прогнозирования на базе инструментария линейных клеточных автоматов для временных рядов с признаками фрактальности: наличие долговременных зависимостей значений, неподчинение нормальному закону, частая смена тренда, нестационарность (с. 122-135);

7) математические методы получения оценок «суммарный эффект» и «оценка по наихудшему» для допустимых решений задачи многокритериального выбора на графах со структурированными исходными данными (с. 155-181);

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

9) асимптотически точный и статистически эффективный алгоритмы для подкласса задач покрытия граф звездами одного типа с весами ребер в виде интервалов равной ширины (с. 230-238).

В области численных методов:

1) численный метод сведения размерностей нечетких множеств к единой величине для реализации арифметических операций по принципу «векторное получение носителя и теоретико-множественные операции над степенью принадлежности» (с. 197-198);

2) численный метод реализации дефазификации по центрам тяжести носителя и функции принадлежности для сравнения нечетких множеств с пересекающимися и вложенными носителями (с. 198);

3) численный метод сравнения вложенных интервалов на базе взвешенной свертки границ интервала (с. 199);

4) численный метод вычисления глубины до