+7(495)506-57-36, +7(968)575-10-99
sovnauka@mail.ru
Опубликовать статью
Контакты
ISSN 2079-4401
Учредитель:
ООО «Законные решения»
Адрес редакции: 123242, Москва, ул. Большая Грузинская, д. 14.
Статей на сайте: 429
Главная
О журнале
О нас
Учредитель
Редакционная коллегия
Политика журнала
Этика научных публикаций
Порядок рецензирования статей
Авторам
Правила и порядок публикации
Правила оформления статей
Правила оформления аннотаций
Правила оформления библиографического списка
Требования к структуре статьи
Права на произведениеЗадать вопрос авторуКонтакты
ЖУРНАЛ
Сентябрь, 2016
2017: 1
2016: 1, 2, 3, 4
2015: 1, 2, 3, 4
2014: 1, 2, 3, 4
2013: 1
2012: 1
2011: 1, 2, 3, 4
2010: 1, 2, 3
ИНДЕКСИРУЕТСЯ
Российский индекс научного цитирования
Google scholar
КиберЛенинка
СОЦИАЛЬНЫЕ СЕТИ
№ 3, 2016
КЛАССИФИКАЦИЯ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ НА МНОГОВЗВЕШЕННЫХ ПРЕДФРАКТАЛЬНЫХ ГРАФАХ
Автор/авторы:
Кочкаров Расул Ахматович,
заместитель директора по информационным технологиям, кандидат экономических наук
Финансовый университет при Правительстве РФ
Контакты: Ленинградский пр., д. 49, Москва, Россия, 125993
E-mail: rasul_kochkarov@mail.ru
Кочкаров Азрет Ахматович,
заместитель директора НТЦ-3 ОАО «РТИ», доцент Департамента анализа данных, принятия решений и финансовых технологий, кандидат физико-математических наук
Финансовый университет при Правительстве РФ
Контакты: ул. 8 Марта, д. 10, стр. 1, Москва, Россия, 127083
E-mail: akochkar@gmail.com
УДК: 519.17
Аннотация: Приведено описание множества альтернативных решений многокритериальных задач на предфрактальных графах. Предложена общая математическая постановка дискретной многокритериальной задачи. Описан подход к оценке сложности нахождения множества альтернатив. Осуществлена классификация многокритериальных задач на многовзвешенных предфрактальных графах, дано определение вычислительной сложности алгоритмов.
Ключевые слова: вычислительная сложность, классификация задач, многовзвешенный граф, многокритериальная задача, множество альтернатив, предфрактальный граф
Дата публикации: 30.09.2016
Дата публикации на сайте: 27.06.2017
PDF версия статьи: Скачать PDF
РИНЦ: Перейти на страницу статьи в РИНЦ
Библиографическая ссылка на статью: Кочкаров Р.А., Кочкаров А.А. Классификация многокритериальных задач на многовзвешенных предфрактальных графах//Современная наука. № 3. 2016. С. 4-8
Права на произведение:

Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная

Множества альтернатив

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

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

Множество альтернатив (МА) представляет собой множество всевозможных альтернативных решений задачи, включая оптимальные и около-оптимальные решения. Понятие МА является первичным понятием и вводится для нужд теории выбора и принятия решений. На практике в отношении МА предъявляются противоречивые требования: оно должно быть наиболее представительным, включать в себя все «наилучшие» и близкие к ним решения, и в тоже время — должно быть обозримым для лица, принимающего решение (ЛПР). Понятие МА появилось в следствие необходимости принятия решения в условиях нескольких одновременных критериев. В этом случае возникает ситуация существования альтернативных решений, каждое из которых лучше другого хотя бы по одному критерию.

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

Процесс нахождения МА должен завершается представлением элементов в том или ином виде. В теории выбора и принятия решений наиболее распространенными являются три способа:

1) перечисление всех конкурирующих альтернатив в явном виде;

2) представление элементов МА в неявном виде со помощью дополнительных систем ограничений;

3) построение детерминированного формального механизма, позволяющего генерировать альтернативы.

Математическая постановка дискретной многокритериальной задачи состоит из описания условий, определяющих конечное или счетное множество допустимых решений  и заданной на этом множестве векторной целевой функции (ВЦФ):

                                            (I)

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

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

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

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

Возвращаясь к множествам альтернатив, рассматривается три вида МА, каждое из которых представляет собой собственное либо несобственное подмножество паретовского множества .

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

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

Полное множество альтернатив (ПМА) — подмножество  минимальной мощности, такое что где , для любого .

Если для индивидуальной задачи ПМ и ПМА не совпадают: то ПМА определяется не однозначно и существует как минимум  различных вариантов ПМА для этой задачи.

Лексикографическое множество альтернатив (ЛМА) определяется следующим образом. Отыскание какого-либо одного лексикографического оптимума адекватно такой постановке многокритериальной задачи, в которой критерии упорядочены по важности и пронумерованы так, что каждый предыдущий несравненно важнее, чем все последующие. Тогда говорят о лексикографической задаче, суть которой — добиваться сколь угодно малого улучшения важного критерия за счет сколь угодно больших потерь по всем остальным менее важным критериям. Нахождение ЛМА в ряде случаев является более легкой проблемой по сравнению с нахождением ПМА. В случае использования распространенных методов — алгоритмов линейной свертки, то в классе этих алгоритмов проблема нахождения ПМА не разрешима, в то время, как проблема нахождения ЛМА является разрешимой. В контексте алгоритмических проблем дискретной оптимизации ЛМА является одной из возможных аппроксимаций искомого ПМА [2, 3].

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

а) , ;

б) существует  такое, что  и .

Пусть  — множество всех лексикографических оптимумов, определенных на , . Тогда ЛМА — это минимальное по мощности подмножество  такое, что . Всякое ЛМА  можно определить как пересечение определенного ПМА  с : . При этом ЛМА также, как и ПМА, в случае  определяется неоднозначно и существует как минимум  различных вариантов ЛМА для данной индивидуальной задачи.

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

 

Классификация многокритериальных задач

Анализ описаний дискретных задач говорит о том, что состав критериев ВЦФ обычно меняется от одной индивидуальной задачи к другой. Например, остовное дерево в оптимизационной задаче может оцениваться критериями веса, степени и диаметра дерева, «пропускной способности» ребер и т.д. Таким образом, существуют различные варианты задач об остовных деревьях. Общим у этих задач является определения множества допустимых решений.

По этой причине математическая постановка многокритериальной задачи какого-либо вида будет представляться обще с описанием множества допустимых решений. После будут конкретизироваться критерии индивидуальных задач и приводится алгоритмы поиска их решений [4, 5].

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

Приведем некоторые определения и обозначения:

— множество всех -вершинных предфрактальных графов;

  — множество всех -вершинных взвешенных предфрактальных графов;

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

 — задача о центрах: -центр предфрактального графа

 — задача о -медианах: медиана предфрактального графа ;

— задача об остовных лесах: — остовный лес предфрактального графа ;

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

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

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

 — задача о коммивояжере: — гамильтонов цикл (контур) предфрактального графа (орграфа)

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

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

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

 — задача о вершинной раскраске: — правильная раскраска (разбиение) множества вершин  предфрактального графа , — число цветов в раскраске

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

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

 — задача о покрытии подграф-затравок ранга  предфрактельного графа подграфами. В частности,  — задача о покрытии подграф-затравок с 1-го по -ый ранг включительно, что соответствует покрытию всего предфрактельного графа .

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

 

Полные задачи и их множества альтернативных решений

Говоря о задаче , будем подразумевать множество всех ее индивидуальных задач. Через множество  обозначаем множество допустимых решений задачи , полученное объединением МДР всех ее индивидуальных задач.

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

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

Лемма 1. Для всякой задачи с ВЦФ вида  выполняется равенство мощностей , где  — Евклидово пространство конечной размерности .

Лемма 2. Добавление новых критериев к ВЦФ какой-либо индивидуальной задачи либо оставляет ее ПМ и ПМА неизменными, либо пополняет их новыми альтернативами.

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

Индивидуальные задачи одного семейства имеют одинаковые определения допустимого решения, но различаются размерностью ВЦФ, составом критериев ВЦФ, количеством наборов весов и т.д.

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

Теорема 1. Всякая задача  об остовных лесах является полной, если ее ВЦФ содержит не менее двух весовых критериев.

Теорема 2. Всякая задача  о совершенных паросочетаниях является полной, если ее ВЦФ содержит не менее двух весовых критериев.

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

Теорема 2. Всякая задача  о коммивояжере является полной, если ее ВЦФ содержит не менее двух весовых критериев.

Остальные задачи требует отдельного анализа для выявления свойства полноты.

Введем дополнительные обозначения:

 — конкретная ВЦФ, состав критериев которой полностью определен;

 — множество всех ВЦФ, у которых каждая из компонент представляет собой некоторый критерий из определенного перечня.

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

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

Теорема 2. Проблема нахождения ПМ  (ПМА ) типовой задачи  на многовзвешенном предфрактальном графе () неразрешима с помощью алгоритмов линейной свертки.

Тем не менее алгоритмы линейной свертки можно использовать для нахождения нетривиальных МА, в частности ЛМА.

Теорема 2. Проблема нахождения ЛМА типовой целочисленной задачи  при условии только весовых критериев на многовзвешенном предфрактальном графе () разрешима с помощью алгоритмов линейной свертки.

 

Вычислительная сложность алгоритмов и их классификация

Определение вычислительной сложности алгоритма в наихудшем случае для трудноразрешимых и сложных задач является малоинформативным. В этом случае используется подход «алгоритмы с оценками», когда качество алгоритмов оценивается посредством вычислительной сложности, точности решения и др. [6, 7].

Получить удобоваримый результат для общей задачи класса , как правило, затруднительно. Далее будем рассматривать класс индивидуальных задач  с заданным ВЦФ и МА. Алгоритм , который может быть применен к задаче , обозначаем . Результатом работы алгоритма  является МА , либо элемент из  в зависимости от настройки алгоритма. Алгоритм  является приближенным, если найдется такая индивидуальная задача, для которой  — непустое множество. Вычислительная сложность алгоритма  обозначается , рассчитывать ее приято от размерности задачи — сложность нахождения алгоритмом  указанного МА  индивидуальной задачи из .

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

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

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

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

Литература
1. Перепелица В.А. Многокритериальные модели и методы для задач оптимизации на графах. Lambert Academic Publishing, 2013. 333 с.
2. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976. 166 с.
3. Кофман А. Введение в теорию нечетких множеств. М.: Радио и связь, 1982. 432 с.
4. Кочкаров А.А., Малинецкий Г.Г., Кочкаров Р.А. Некоторые аспекты динамической теории графов // Журнал вычислительной математики и математической физики. 2015. Т. 55. № 9. С. 1623-1629.
5. Павлов Д.А. Многокритериальная задача покрытия предфрактального графа простыми цепями: Дисс. … канд. физ.-мат. наук. Таганрогский государственный радиотехнический университет. Таганрог, 2004. 112 с.
6. Кочкаров А.М. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: РАН САО, 1998. 170 с.
7. Кочкаров Р.А. Задачи многокритериальной оптимизации на многовзвшенных предфрактальных графах. М.: Академинновация, 2014. 189 с. [
Просмотров: 229 Комментариев: 0
Комментарии
Комментариев пока нет.

Чтобы оставить комментарий, Вам нужно зарегистрироваться или авторизоваться под своими логином и паролем (можно войти, используя Ваш аккаунт в социальной сети, если такая социальная сеть поддерживается нашим сайтом).

Поиск по авторам
Поиск по статьям
ISSN 2079-4401
Учредитель: ООО «Законные решения»
Адрес редакции: 123242, Москва, ул. Большая Грузинская, д. 14.
Если не указано иное, материалы сайта доступны по лицензии: Creative Commons Attribution 4.0 International
Журнал зарегистрирован Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор). Свидетельство о регистрации средства массовой информации ПИ № ФС77-39293 от 30.03.2010 г.; журнал перерегистрирован: свидетельство о регистрации средства массовой информации ПИ No ФС77-70764 от 21.08.2017 г.
© Журнал «Современная наука», 2010-2018