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

• Автор: Тебуева, Фариза Биляловна
• Шифр специальности: 05.13.18
• Научная степень: Докторская
• Год защиты: 2013
• Место защиты: Ставрополь
• Количество страниц: 312 с. : ил.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ
1 АНАЛИЗ ВОЗМОЖНЫХ НЕОПРЕДЕЛЕННОСТЕЙ ИСХОДНЫХ ДАННЫХ В ЗАДАЧАХ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА НА ГРАФАХ И ИССЛЕДОВАНИЕ ПРОБЛЕМЫ ОТЫСКАНИЯ ПРЕДПОЧТИТЕЛЬНОЙ АЛЬТЕРНАТИВЫ
1.1 Формализация прикладных задач в виде задач многокритериального выбора на графах в условиях недетерминированности исходных данных
1.2 Математическая постановка и исследование вычислительной сложности задач многокритериального выбора на графах в условиях недетерминированности исходных данных

1.3 Обоснование необходимости структурирования

недетерминированности исходных данных в задачах многокритериального выбора на графах
1.3.1 Недостаточность информативности результата и неприемлемая трудоемкость расчетов при выполнении арифметических операций над нечеткими исходными данными с различной размерностью носителя
1.3.2 Отсутствие методов сравнения нечетких множеств без использования процедуры нормализации и несравнимость вложенных интервалов
1.3.3 Необходимость структурирования исходных данных, представленных временными рядами, и неадекватность классического математического аппарата прогнозирования для персистентных временных рядов
1.4 Оценка применимости методов многокритериального выбора предпочтительной альтернативы с детерминированными исходными данными для случая недетерминированности
1.5 Формулировка научной проблемы и постановка научных задач диссертационного исследования
1.6 Выводы по главе
2 РАЗРАБОТКА МЕТОДОВ СТРУКТУРИРОВАНИЯ ИСХОДНЫХ ДАННЫХ В ВИДЕ НЕЧЕТКИХ МНОЖЕСТВ И ИНТЕРВАЛОВ ЗНАЧЕНИЙ
2.1 Обоснование выбора классификации нечетких множеств по признаку «Близость к более вероятной величине»
2.2 Разработка метода сведения размерностей дискретных нечетких множеств к единой величине для возможности применения нечетких арифметических операций на базе векторного получения носителя
2.3 Разработка метода упорядочения по предпочтительности двух нечетких множеств с вложенными границами носителя
2.4 Обоснование необходимости использования взвешенной свертки границ интервалов при решении экстремальных задач на графах с интервальными весами
2.5 Выводы по главе
3 РАЗРАБОТКА ПРОГНОЗНОЙ МОДЕЛИ ДЛЯ СТРУКТУРИРОВАНИЯ ИСХОДНЫХ ДАННЫХ В ВИДЕ ПЕРСИСТЕНТНЫХ ВРЕМЕННЫХ РЯДОВ
3.1 Разработка метода последовательного я 18 - анализа для вычисления глубины долговременных корреляций в персистентных временных рядах
3.2 Применение алгоритма последовательного я /Я -анализа для получения циклических характеристик персистентных временных рядов
3.3 Разработка математической модели для прогнозирования персистентных временных рядов на базе инструментария клеточных автоматов
3.3.1 Разработка методов трансформации числовых временных рядов в клеточные автоматы
3.3.2 Оценка частотной памяти временного ряда, представленного клеточным автоматом
3.3.3 Получение прогноза и оценка погрешности
3.4 Сравнительный анализ результатов прогнозирования временных
рядов из классификации по признаку «Персистентность»
3.5 Выводы по главе
4 РАЗРАБОТКА МЕТОДА РЕШЕНИЯ ДИСКРЕТНЫХ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ НА ГРАФАХ В УСЛОВИЯХ НЕДЕТЕРМИНИРОВАННОСТИ ИСХОДНЫХ ДАННЫХ
4.1 Описание общей схемы метода решения задач многокритериального выбора на графах в условиях недетерминированности исходных данных
4.2 Разработка методов получения оценок «суммарный эффект» и «оценка по наихудшему» для допустимых решений задачи многокритериального выбора на графах с недетерминированными весами ребер
4.3 Адаптация метода Парето для реализации многокритериального сравнения допустимых решений в задачах на графах с
недетерминированными весами ребер
4.4 Пример нахождения многокритериального оптимума в задаче на графах с недетерминированными весами ребер
4.5 Выводы по главе
5 РАЗРАБОТКА ЧИСЛЕННЫХ МЕТОДОВ И ОЦЕНКА ЭФФЕКТИВНОСТИ РЕШЕНИЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА НА ГРАФАХ В УСЛОВИЯХ НЕДЕТЕРМИНИРОВАННОСТИ ИСХОДНЫХ ДАННЫХ
5.1 Численные методы решения задач многокритериального выбора на графах в недетерминированности исходных данных
5.2 Методология оценки эффективности вычислительного алгоритма... 2]
5.3 Исследование вычислительной сложности многокритериальных задач на графах с недерминированными весами ребер
5.4 Оценка эффективности методики решения задач многокритериального выбора на графах в условиях недерминированности исходных данных
5.5 Разработка приближенных алгоритмов для некоторых подклассов задач на графах в условиях недетерминированности исходных данных. 2:

*іИ=І"»=Е2'’5ви» (1.29)
еєЕ, ^И= И^(е) = 0-^Г=П-Р^), * = 1.2, (1.30)
еєЕ л
где константа о = (2 + 2і-)с.
Рассмотрим множества Мх2 =МХ М2 и М2Л =М7М], выделим в них максимальные элементы г' = тахг г2 = тах ґ ■ Поскольку Л/, *М, и
г}Шхл ' г?еМ2л ‘
|М,| = |М2|, то М12 ГМ2,, =0, в силу чего г' Фг2. Пусть имеет место строгое неравенство г1 <г2, тогда с учетом равенства мощностей [М12| = |Л/21| для значений (1.35) и (1.36) выполняются следующие соотношения:
Е(х')<2г'+> <2ГІ ^(х2);:^2)^*1). (1.31)
Сравнивая (1.37) и (1.31), согласно определению 1.6 можем утверждать, что для интервальной целевой функции (1.20) ее интервальные значения (1.28) являются несравнимыми. Таким образом, с учетом произвольного выбора графа Ое5(и) и х'.х2 є Х((},0) получаем, что согласно определению 1.6 и неравенств (1.29) рассматриваемая интервальная задача обладает свойством полноты.
Теорема 1.1 доказана.
Рассматривая класс однородных множеств компонент связности £7, условимся нумеровать их индексом к-1,2,..., т.е. мы рассматриваем класс В = {(У}. Класс В определяет собой класс массовых задач на графах. Например, значения к = 1,2,3,4 могут соответствовать следующим задачам: О1 - задача о совершенных паросочетаниях; О2 - задача об остовных деревьях; 0А - задача коммивояжера; О1 - задача покрытия графа звездами одинаковой степени, т.е. О1 = {г,7}, где Т2 - А-вершинная звезда, п кратно И. Для всякого множества типовых графов Ок при фиксированном значении п можно вычислить максимум мощности множества допустимых решений