Многокритериальная задача Эйлера на предфрактальных графах тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Коркмазова, Зарема Османовна

• Коркмазова, Зарема Османовна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Коркмазова, Зарема Османовна

Г ВВЕДЕНИЕ.

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

1.1. Эйлеровы графы и задача "китайского почтальона".

1.2. Фрактальные и предфрактальные графы.

1.3. Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами.

1.4. Вывод.

I ГЛАВА 2. АЛГОРИТМЫ С ОЦЕНКАМИ ПОСТРОЕНИЯ ПОКРЫТИЙ * ЦИКЛАМИ НА ПРЕДФРАКТАЛЬНОМ ГРАФЕ.

2.1. Алгоритм ах построения покрытия L-ранговыми циклами.

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

2.3. Алгоритм аъ выделения /-смешанных циклов.

2.4. Алгоритм а4 выделения эйлерова подграфа.

2.4.1. Алгоритм (Хр выделения эйлерова подграфа на полном графе.

2.4.2. Алгоритм aF выделения эйлерова подграфа на полном графе.

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

2.6. Алгоритм а6 выделения эйлерова подграфа на предфрактальном графе, смежность старых ребер которого сохраняется.

2.7. Выводы.

ГЛАВА 3. АЛГОРИТМЫ ПОРОЖДЕНИЯ ЭЙЛЕРОВЫХ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ. НЕКОТОРЫЕ ХАРАКТЕРИСТИКИ

НЕЭЙЛЕРОВЫХ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ.

3.1. Алгоритм Д порождения эйлерова предфрактального графа.

3.2. Алгоритм Д, порождения ориентированного эйлерова предфрактального графа.

3.3. Выводы.

Введение диссертации (часть автореферата) на тему «Многокритериальная задача Эйлера на предфрактальных графах»

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

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

Любая целенаправленная деятельность требует планирования, проектирования (конструирования) и прогнозирования. Каждая из составляющих не возможна без понимания сути процесса в той области, где осуществляется деятельность. Достичь понимания, как уже отмечалось, можно с помощью адекватно построенной математической модели. Это и есть главное обоснование необходимости построения математических моделей. На основе имеющейся математической модели возможна постановка оптимизационной задачи [10, 11], решение которой позволяет точно оценить сложившуюся ситуацию, а значит, сделать правильный прогноз и провести планирование дальнейших действий. Задачи оптимального и автоматического управления, автоматизации проектирования, эколого-экономического планирования, принятия решений, компромисса в условиях неполной информации, математического программирования и т.п. находятся в сфере деятельности специалистов по исследованию операций [12- 16]. Предметом исследования операций, как правило, являются сложные системы.

В русском языке термин "сложность" имеет двоякий смысл. С одной стороны, его можно понимать как сложность устройства (complication, compound), т.е. как наличие в некоторой системе большого числа элементов и (или) нетривиальных связей между ними. А с другой стороны, речь может идти о сложности внешних проявлений системы (complexity) безотносительно ее внутреннего устройства, т.е. о нетривиальном поведении. Эти две "сложности" во многом взаимосвязаны, но не эквивалентны. Поэтому сложные системы требуют "объемного" всестороннего анализа. В этом смысле методы исследования операций перемежаются с задачами системного анализа [8].

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

F(*) = (1)

Fj (х) extr{max/ min), / = 1, п, где F(x) - векторно-целевая функция (ВЦФ) с критериями Fj(x), i = \,n, которые оптимизируются на множестве допустимых решений (МДР) X = {х].

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

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

- выделение из множества допустимых решений оптимальных по Паре-то, так называемого паретовского множества (ПМ) или множества эффективных решений. Решение Парето-оптимально, если значение любого из критериев можно улучшить лишь за счет ухудшения значений других критериев. Такие решения еще называют векторно-несравнимыми. Наименование указанного понятия связанно с именем итальянского ученого В. Парето (1848-1923), который одним из первых начал его использовать при математических исследованиях процесса рыночного обмена товаров [18]. В отечественной научной литературе наиболее полное и систематическое изложение проблем посвященных Парето-оптимальных решений можно найти в книгах [19,20];

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

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

Дискретная многокритериальная оптимизация

Одной из широко используемых и хорошо развитых областей дискретной математики является теория графов [38-53]. Методы теории графов нашли свои приложения во многих областях современной прикладной науки: в технике [54 - 57], экономике [58 - 59], биологии и химии [60 - 63], в исследовании надежности, стойкости и живучести систем [64-71], моделировании динамических систем и управлении [72 - 79], и т.д. Нередко использование методов теории графов в перечисленных областях исходило из постановки оптимизационных задач. Напомним, что введение самих графов произошло при решении J1. Эйлером по сути оптимизационной задачи о кенигс-бергских мостах [80]. Поиск решений оптимизационных задач на графах осуществляется специализированными алгоритмами [40, 42,43,44, 81 - 90].

Качество поиска решения алгоритмом оценивается его трудоемкостью или, говоря иначе, вычислительной слоэ/сностью [83].

Вычислительная слоэюностъ - это общее число всех элементарных операций, произведенных алгоритмом за время его работы. Вообще говоря, вычислительная сложность - это функция /(п), которая ставит в соответствие размерности п задачи количество производимых алгоритмом элементарных операций. Будем считать, что /(«) есть 0(g(n)), если существует константа с, такая, что |/(и)| < c\0{g(n))\ для всех значений п> 0. Полиномиальным алгоритмом (или алгоритмом полиномиальной вычислительной сложности) называют алгоритм, у которого вычислительная сложность равна 0(р(п)), где р{п) - некоторая полиномиальная функция. Алгоритмы, которые не поддаются подобной оценке, называются экспоненциальными. С ростом размерности задачи предпочтительность полиномиальных алгоритмов перед экспоненциальными вполне очевидна. Поэтому первые называют эффективными, а вторые неэффективными. Задача называется труднорешае-мой, если для ее решения не существует полиномиального алгоритма. Таким образом, обоснованный полиномиальный алгоритм решения графовой оптимизационной задачи является наиболее полезным результатом проводимого исследования.

Идеи многокритериальной оптимизации нашли свое продолжение и в задачах дискретной оптимизации [91 - 129]. Среди задач дискретной многокритериальной оптимизации можно выделить две группы. Первая группа -многокритериальные задачи целочисленного линейного программирования [111-119]. К этой группе относятся задача о назначениях, целочисленная транспортная задача, задача землепользования и т.д. Вторая группа - многокритериальные задачи на графах [92 - 110], и сетях [122 - 126]. В эту группу входит значительно более широкий класс задач по сравнению с первой группой. Рассмотрим более подробно группу многокритериальных задач на графах.

В формулировке многокритериальной задачи (I) на конкретном графе (орграфа) G = (V,E) [38-58], который, как правило, является моделью структуры означенной в задаче системы, считается, что ее допустимое решение х&Х представляет собой определенный подграф х = (VX,EX) графа (орграфа) G с множеством вершин F^cF и множеством ребер (дуг) Ех q Е. Подграф х называется остовным, если Vx = V. Часто остовный подграф называю покрытием. Определенное специальным образом допустимое решение хеХ является отличительной особенностью многокритериальных задач на графах. Вид подграфа x = (Vx,Ex) определяет множество многокритериальных задач на графах, среди которых можно выделить основные:

- задача о совершенных паросочетаниях;

- задача об остовных деревьях;

- задача о путях (цепях) между парой вершин;

- задача о покрытии графа цепями;

- задача о покрытии графа звездами.

В качестве критериев F/ (х), / = 1, п, в таких задачах используются степень подграфа [38-58] л;, его диаметр [38-58], количество компонент связности [38 — 58] и общий (суммарный) вес, если граф G взвешен [38 - 58].

Структурная динамика, фрактальные графы и многокритериальная оптимизация

Современные исследования сложных систем, таких, как информационные, электроэнергетические, WWW (Internet), коммуникационные системы показывают, что структуры этих систем по истечении времени претерпевают определенные изменения, вызываемые различными внешними обстоятельствами [130-134]. Структуру системы произвольной природы (социальной, социально-экономической, технической, химико-биологической и т.п.) можно представить в виде графа. Граф — это абстрактный объект, как правило, вершины графа соответствуют элементам системы, а ребра - связям между элементами этой системы. Изменения, происходящие в структуре сложной системы, могут быть описаны простейшими теоретико-графовыми операциями: стягивание ребра, удаление (добавление) ребра, удаление (добавление) вершины. Изменения структуры системы могут быть разовыми, а могут быть постоянными. Для второго случая разумно ввести понятие структурной динамики — изменение структуры системы с течением времени. Несомненно, для описания структурной динамики лучше всего подходит аппарат теории графов.

Одним из наиболее распространенных сценариев структурной динамики является рост структуры. Рост структуры - это регулярное появление новых элементов и связей в структуре системы. Рост структуры может происходит по строго сформулированным правилам, не исключая наличие в них фактора случайности [130- 134].

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

Фрактальный граф - сложный абстрактный объект, совмещающий в себе свойства, характеристики и достоинства фракталов и "обычных" графов.

Понятие фрактал, введенное Бенуа Мандельбротом [135], объединило объекты, обладающие особым свойством - свойством самоподобия (self-similarity) или масштабной инвариантности. Работы, связанные с исследованием фрактальных объектов (фрактальных множеств), долгое время считались занимательными, но неимеющими значительных приложений. Мнения в мировой научной среде изменились с изданием книги [136]. В настоящее время о перспективности и значимости исследований, связанных с фрактальными множествами, можно судить по регулярно проводимым конференциям и периодическим изданиям (журнал "Chaos, Solitons & Fractals"), целиком посвященных соответствующей тематике и множеству книг (учебников и монографий) [135-141]. Это позволяет говорить о сформировавшемся круге прикладных физических модельных задач на основе фрактальных множеств [142- 154]. Среди них выделяются задачи и модели, где фрактальные множества представлены как самоподобные (фрактальные или масштабно-инвариантные) графы большой размерности, т.е. с большим числом вершин. К ним относятся, например, задачи о броуновском движении (случайном блуждании), диффузии и просачиваемости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем [153], таких как коммуникационные сети.

Активное изучение фрактальных графов и областей их приложения ведется в научной школе профессора A.M. Кочкарова. Исследования ведутся по трем направлениям: распознавание фрактальных графов [128, 155], их свойства и характеристики [156- 170], задачи многокритериальной оптимизации в системах с масштабно-инвариантной структурой [171-196]. Надо отметить, что масштабная инвариантность структур моделируемых систем является следствием структурной динамики в этих системах.

Краткое содержание и структура диссертационной работы

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

Публикации. По результатам выполненной работы имеется 17 публикация, в том числе 2 статьи в журналах из списка ВАК РФ, 3 статьи, депонированные в ВИНИТИ, 2 препринта, тезисы докладов в материалах 4 международных конференций, тезисы докладов в материалах 2 Всероссийских симпозиумов и т.д.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Коркмазова, Зарема Османовна

З.З.Выводы

В третьей главе диссертационной работы предложены два алгоритма порождения эйлерова предфрактального графа. Алгоритм Д порождает эйлеров предфрактальный граф, где смежность старых ребер сохраняется. Алгоритм Р2 порождает эйлеров предфрактальный орграф, где затравка также является эйлеровым орграфом.

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

-предфрактальный граф порожден эйлеровой затравкой, у которого старые ребра одного ранга не пересекаются (число вершин нечетной степени й nL~2(n-l) + \ больше или равно ------2 q, максимальная степень п-1 max deg((j£ )<n + L-2);

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

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

ЗАКЛЮЧЕНИЕ

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

При этом получены следующие новые научные результаты:

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

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

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

1) предфрактальный граф порожден эйлеровой затравкой, у которого старые ребра одного ранга не пересекаются (число вершин нечетной степени max deg(GL) < п + L - 2);

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

• 2 q, максимальная степень вершин нечетной степени больше или равно

Список литературы диссертационного исследования кандидат физико-математических наук Коркмазова, Зарема Османовна, 2006 год

1. Самарский А.А., Михайлов А.П. Математическое моделирование: идеи, методы, примеры. -М.: Физматлит, 2001.

2. Краснощекое П. С., Петров А.А. Принципы построения моделей. М.: Издательство МГУ, 1983.

3. Краснощекое П. С., Петров А.А., Федоров В.В. Информатика и проектирование. -М.: Знание, 1986.

4. Петров А.А. Экономика. Модели. Вычислительный эксперимент. М.: Наука, 1996.

5. Тихонов А.Н., Костомаров Д. И Вводные лекции по прикладной математике. М.: Наука, 1984.

6. Моисеев Н.Н. Математика ставит эксперимент. М.: Наука, 1979.

7. Моисеев Н.Н. Алгоритм развития. М.: Наука, 1987.

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

9. ПоспеловГ.С., ИриковВ.А. Программно-целевое планирование и управление. М.: Сов. радио, 1976.

10. Гилл Ф., МюрейУ., Райт М. Практическая оптимизация. М.: Мир, 1985.

11. Понтрягин JI.C., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: Наука, 1976.

12. Петров А. А. Исследование операций и математическое моделирование // материалы учредительной конференции Российского научного общества исследования операций. М.: ВЦ РАН, 1996

13. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

14. ТахаХ. Введение в исследование операций. М.: Диалект, 2005.

15. Венцелъ Е.С. Введение в исследование операций. М.: Сов. радио, 1964.16